# Linear programming, shadow price range

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}$.

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.