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.

Leave a Reply

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