Linear Programming - Shadow Price, Slack/Surplus calculations - YouTube

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.