22
Aug

Linear Programming 3: Graphical Solution – with negative coefficients


Welcome! In this tutorial, we will solve this maximization
problem using graphical method. Let’s label the constraints C1 to C4 for
reference purposes. Let’s start by setting up tables to find
the points. The line equation for Constraint 1) is 7X
– Y=3 So when X=0, Y=-3
And when Y=0, X=0.43 These two points are not that useful to us
because the first has a negative which will take us far away from the feasible region
and make the graph very small. The other has a fractional value that cannot
be easily located on the graph. So let’s try finding more points.
To make it easy to find useful points, it is better to rewrite the equation in terms
of one variable. In this case, we can write it in terms of
Y. That is, Y=7X – 3.
We can now use trial and error to find better points.
For example, when X=0.5, Y also equals 0.5. And when X=1, Y equals 4. For Constraint 2) we have the line -3x + 6y
=10 when X=0, Y=1.67.
And when Y=0, X=-3.33. Again, let’s try more points.
Rewriting the equation we have 6Y=10 + 3X so that Y=(10 + 3X)/6.
When X=1, Y=2.17 And when X=2, Y=2.67.
So it is hard to find whole number points for this line. For Constraint 3) we have the line 3X + 4Y
=9 When X=0, Y=2.25.
And when Y=0, X=3. Let’s try one more point:
when X=1, Y=1.5 And finally for Constraint 4) we have the
line 3X + 3Y=3 So when X=0, Y=1
And when Y=0, X=1. And that should do it for that constraint. In drawing the line for the first constraint,
we can just plot the last 2 points (.5,.5) and (1, 4).
And then the constraint line. For the second constraint, we can use the
first point and the last 2. And that’s the line.
For the third constraint, we can use (3, 0) and (1, 1.5); and that’s the line.
And for the 4th constraint, we have (0, 1) and (1, 0); and that’s the line. Now the first 3 constraints are “less than”
constraints and are satisfied in the direction of the origin.
The last constraint a “greater than” constraint satisfied in this direction away from the
origin. The directions of the arrows show that the
feasible region is this area shaded in blue. To determine which of the extreme points of
this feasible region is optimal, let’s use the objective function line method.
The objective function is to maximize -3X + 12Y.
We begin by setting the objective function to any number of our choice.
Normally I will just multiply 3 by 12. But that will give us 36 which will give us a
line too far away from the feasible region. But since 12 is a multiple of 3, it will be
a better choice in this case. So let’s set the objective function equal
to 12. Next we find points to draw the objective
function line. When X=0, Y=1
And when Y=0, X=-4. Because of this -4, let’s just obtain one
more point. When X=2, Y=1.5.
So using these 2 points, the objective function line is this dotted line here. Since this is a maximization problem, we slowly
move the objective function line upwards away from the origin, parallel to itself, to obtain
the optimal solution point. Now moving the objective function line shows
that the optimal solution occurs here at the line intersection of constraints 2 and 3.
Let us now to solve these two lines simultaneously to determine the coordinates at that point.
Here are the equations. Since the coefficients of X in the two equations
are -3 and +3 respectively, we can simply add the 2 equations to eliminate X.
So -3X cancels 3X. 6Y + 4Y gives 10Y,
and 10 + 9 equals 19. On dividing both sides by 10 we have Y=1.9.
Substituting that Y value in C3 we have 3X + 4(1.9)=9.
That is 3X=1.4 And X=0.47.
So the optimal solution is X=0.47 and Y=1.9.
Plugging that point into the objective function we have
-3(0.47) + 12(1.9) which gives 21.4. So the optimal solution is X=0.47 and Y
=1.9 And the corresponding maximum value of the
objective function is 21.4. See you in the next video.
And thanks for watching.

Tags: , , , , , , , , , , , , , , , ,

22 Comments

  • Khaled Alqahtani says:

    thanx a lot you're the best
    Regards

  • Yusuf ağaç says:

    thank you so much your voice and hands

  • Katherine Balka says:

    You have a wonderful voice and your videos are so well made and good at explaining the solution! Thanks for the help!!!

  • itsdannyftw says:

    3:02: "are less than constraints and are satisfied in the direction of the origin".
    Is it just a coincidence that this worked for the negative coefficient constraint -3X +6Y <= 10 (purple line)?

    Because if you try it on this negative constraint: -3x + 2y ≤ -4
    You'll realise that even though this is a "less than constraint", it will NOT be satisfied in the direction of the origin (as far as I know, unless I graphed it incorrectly) , like you stated in the video.

    Rather, it will be satisfied away from the origin… and the only way to have worked this out is to have input a test coordinate, like you had suggested in the comments earlier. Funnily you didn't do this when graphing the purple line, so was it just a coincidence that you got lucky to know which direction to shade in? Or how did you know exactly without inputting test coordinates?

  • mohammad hassan says:

    thanx too much ..I hope that you can also be described the simplex method…in the same charming and understanding way

  • Sanjay Gupta says:

    Thnk u so much for explanation in detail….

  • chanandler bong says:

    best explanation ever!! thank yoU!

  • Dalia Al-saeed says:

    thank youuu!!

  • Programming Intellects says:

    you helped me in my exams … soo thankful to u

  • arif noman says:

    well explained..thank you so much
    sir explain simplex method. plz

  • Sejvi Hasani says:

    I couldn't not thank you. so, thank you very very much

  • Kathleen Ferguson says:

    Very clearly and thoroughly explained. You make it seem quite easy. Thank you.

  • rick delano says:

    Al hail Joshua !!!

  • Aslınur Akbulut says:

    i cant thank you enough !!!

  • Bisi Adeyoyin says:

    Thanks so much for very good explanation. You've helped me to prepare for a midterm. My God will continue to strengthen you and help you in all your endeavours.

  • chip buddy says:

    not a fucking indian accent finally

  • Lotanna Okujagu says:

    hi. sorry but when you say trial & error for 1:07 points, do you mean just randomly think of any number or is there like a range of specific numbers to pick from? can i just randomly use 0.75?

  • Lotanna Okujagu says:

    also for the second one, (-3X+6Y=10) why did'nt we use 0.5, why did we go straight to 1? what are we really looking for by getting other values? i thought it was just to offset the negatives. please explain 🙁

  • Lotanna Okujagu says:

    sorry last question, for the third constraint, (3X+4Y=9) why didnt we rearrange the equation when we found the third point. i rearranged the equation and when x=1, y=3. which is different than the un-rearranged equation where your y=1.5

  • Ahmed says:

    Great video

  • GEEWOO KIM says:

    Thank you so much !!!!!! (From South Korea)

  • 호탕한정언니 says:

    i'm korean thankyou for teacher you are helpful to me

Leave a Reply

Your email address will not be published. Required fields are marked *