Welcome
In this video, I’ll be solving this LP model graphically, calculating the surplus values
for the constraints, calculating shadow or dual prices, and stating the all-integer solution
for the problem. For constraint 1, when x1 = 0, x2 = 6, and
when x2 = 0, x1 = 3. For constraint 2, when x1 = 0, x2 = 4, and
when x2 = 0, x1 = 4. For constraint 3, when x1 = 0, x2 = 2, and
when x2 = 0, x1 = 10. Here is the line for constraint 1, for constraint
2, and for constraint 3. Since they’re all “greater than” constraints,
the feasible region will be in the right upper side here. And the candidates for the optimal solution
will be these 4 extreme or corner points. Because points 2 and 3 are pretty close together,
I want to be a little careful and investigate every single point. The co-ordinates at point 1 are (0, 6) and
(10, 0) at point 4. We can also see here that they are (2, 2)
at point 2. For point 3, we can solve the 2 lines simultaneously. Multiplying the first equation by 2 and subtracting
from the second, we have x2 = 1.5, and x1 = 2.5. Plugging these points into the objective function,
we see that point 1 provides the minimum value of the objective function. So the optimal solution occurs at point 1
with x1 = 0, and x2 = 6. And the optimal objective function value is
6. Now for standard form, since these are all
“greater than” constraints, we introduce surplus variables for the 3 constraints
by subtracting s1, s2, and s3 from the left side, and changing the inequalities to equalities. Substituting the optimal solution, we have
surplus values s1 = 0, s2 = 2, and s3 = 40. As a result, only constraint 1 is binding
because it has a surplus value of 0. And on the graph we can see that, of the 3
constraints, only constraint 1 touches the optimal solution point. Let’s now calculate the shadow prices for
the constraints. Shadow price here is defined as the amount
of change in the optimal objective function value per unit increase in the right hand
side of a constraint. So for the first constraint, we want to increase
this right hand side, from 6 to 7, and then determine the amount of change in the objective
function value as a result. Recall that the optimal solution occurs here,
at the intersection of these 2 lines. So the binding lines are x1=0, and 2x1+x2=6. When calculating shadow prices for a constraint
graphically, we increase the right side of the constraint by 1 and solve its equation
simultaneously with the equation of a binding constraint. So for constraint 1, we increase it’s RHS
to 7, and solve it with simultaneously with x1 = 0. Since x1 = 0, x2 = 7. So the new objective function value is 7. We then subtract the old objective function
value from the new one to obtain a shadow price of 1. For constraint 2, a unit increase in the right
hand side gives 5. And solving it with the x1 = 0 gives x2 = 5. So we have a new objective function value
here of 5, and the shadow price is 5 minus 6 which gives -1. But wait a minute, we stated a moment ago
that the second constraint is not binding. Then by definition, it should have a 0 shadow
price. That is, if a constraint is not binding, it
will have a slack or surplus greater than 0, and should also have a 0 shadow price. So something must be wrong here. The shadow price should be 0. Let’s take a look at the graph to see where
the problem lies. If we increase the right side of this constraint
by 1, we have this new feasible region. The point (0, 5) occurs here which is outside
the feasible region. Therefore, it cannot be a new optimal point. In essence, the optimal solution remains here
at (0, 6). Note that if you have solved it simultaneously
with the first constraint here which is also binding, your solution will be (1, 4) here
with an objective value of 9, which is also not optimal. Therefore, the optimal solution remains at
0, 6 and the objective function value has not changed. So the shadow price for constraint 2 is still
0. Consequently, we don’t need to bother calculating
the shadow price for constraint 3. It is also not a binding constraint, so it
will have a shadow price of 0 as well. We can see here that constraint 1 is binding. It has a non-zero shadow price and a surplus
of 0 while constraints 2 and 3 are non-binding with 0 shadow prices and non-zero surplus
values. Now if x1 and x2 are required to be integers,
then the feasible region is a collection of dots. Since the optimal solution we obtained earlier,
which we now call LP relaxation solution, is already integer, then it is also the optimal
solution to this integer problem. And that concludes this video. Thanks for watching.
