Linear programming, shadow price range

Question

I'm not sure how to determine the range for which a shadow price is valid.

You might be able to skip straight to the question here.

I've been introduced to it using the following approach in 2D.

Context

Given an optimal solution which is at a corner, there are two intersecting lines. Say that these lines represent the following inequalities

\begin{equation} \begin{aligned} 2K + 3S & \leq 10 \\ K + 2S & \leq 6 \\ Z & = 30K + 50S \end{aligned} \end{equation}

Then the shadow price is the change in the objective function, $Z$, when the right hand side of an inequality is changed by one unit.

Computing this for the second equation is done as follows:

\begin{equation} \begin{aligned} 2K + 3S & \leq 10 \\ K + 2S & \leq 6 + \Delta\\ \end{aligned} \end{equation}

Then subtracting the second equation from the first twice

\begin{equation} \begin{aligned} S & = 2 + 2 \Delta \end{aligned} \end{equation}

Therefore

\begin{equation} \begin{aligned} K &= 2 - 3 \Delta \end{aligned} \end{equation}

And the objective function can be written as

\begin{equation} \begin{aligned} 30K + 50S &= 30(2 - 3 \Delta) + 50(2 + 2\Delta) \\ &= 160 + 10 \Delta \end{aligned} \end{equation}

And the shadow price is found from $z(1) - z(0)$, where $z(\Delta) = 160 + 10 \Delta$ which gives $10$.

Therefore the shadow price is 10.

But how do I compute the range for which this is valid? I can get through the algebra here pretty easily, but there's little meaning to it.

Question

How do I determine the range for which I can adjust the second inequality such that the difference made to the objective function is $10 \times \text{adjustment}$.

Answer 1

The shadow price is formally not the increase in the objective function for relaxing a constraint by a single unit, but by an infinitesimal relaxation. In the world of linear programming it can be valid for up to a unit but it doesn't have to be. In your example problem it is actually not. This becomes clearest when we use pictures.

I am going to assume that you were maximizing, not minimizing your objective function and furthermore that you have two additional constraints that you hadn't actually stated:

$K\geq0$ and $S\geq0$

That would result in the following graphic with K on the y-axis and S on the x-axis, and the optimum at the red dot. The black dotted lines are isoquants of Z, for Z=100, Z=150 and Z=200.

The feasible region is made up of the x and y axis, the blue line from the y-axis up to the crossing, and the orange line from that point on to the x axis.

Let us now relax your constraint $K+2S\leq6$ by one unit, as you propose. In essence this means that the constraint becomes $K+2S\leq7$ and when we draw the new constraints we get:

Turns out that the new constraint no longer plays a role in determining the optimum! The optimum is now determined by the constraints: $S\geq0$ and $2K+3S\leq10$.

The answer to your question should now be clear: the shadow price is valid up to the point where that particular combination of constraints continues to determine the optimum. In this case that means that you can increase 6 to $6\frac{2}{3}$, for a corresponding increase in the objective function of $10*\frac{2}{3}=\frac{20}{3}$ After that point the combination of constraints no longer determines the optimum.

As a side point let me add that at least the Excel solver (and I expect therefore many other solvers too) report up to which point you can relax the constraints before the optimum is determined by another set of constraints.