<p>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. </p>

<p>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: </p>

<p>$K\geq0$ and
$S\geq0$</p>

<p>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.</p>

<p><a href="https://i.sstatic.net/Zahps.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Zahps.jpg" alt="enter image description here"></a></p>

<p>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.</p>

<p>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:</p>

<p><a href="https://i.sstatic.net/D4MYl.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/D4MYl.jpg" alt="enter image description here"></a></p>

<p>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$.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 4.0
2018-05-17T19:48:10.407Z
2018-05-17T19:48:10.407Z
Maarten Punt
<p>I'm not sure how to determine the range for which a shadow price is valid.</p>

<p><em>You might be able to skip straight to the question here.</em></p>

<p>I've been introduced to it using the following approach in 2D.</p>

<h1>Context</h1>

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

<p>\begin{equation}
  \begin{aligned}
    2K + 3S &amp; \leq 10 \\
    K + 2S &amp; \leq 6 \\
    Z &amp; = 30K  +  50S
  \end{aligned}
\end{equation}</p>

<p>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.</p>

<p>Computing this for the second equation is done as follows:</p>

<p>\begin{equation}
  \begin{aligned}
    2K + 3S &amp; \leq 10 \\ 
    K + 2S &amp; \leq 6 + \Delta\\
  \end{aligned}
\end{equation}</p>

<p>Then subtracting the second equation from the first twice</p>

<p>\begin{equation}
  \begin{aligned}
    S &amp; = 2 +  2 \Delta
  \end{aligned}
\end{equation}</p>

<p>Therefore </p>

<p>\begin{equation}
  \begin{aligned}
    K &amp;= 2 - 3 \Delta
  \end{aligned}
\end{equation}</p>

<p>And the objective function can be written as </p>

<p>\begin{equation}
  \begin{aligned}
    30K + 50S &amp;= 30(2 - 3 \Delta) + 50(2 + 2\Delta) \\
    &amp;= 160 + 10 \Delta
  \end{aligned}
\end{equation}</p>

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

<p><strong>Therefore the shadow price is 10.</strong></p>

<p>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.</p>

<h1>Question</h1>

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

<optimization><linear-programming>
Linear programming, shadow price range
wsx399
# Linear programming, shadow price range

(Asked by: username_0 on 2018-05-03)

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

**Tags:** optimization, linear-programming

---

## 1 answers

### Answer by username_1 on 2018-05-17. Score: 2

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.

[![enter image description here](https://i.sstatic.net/Zahps.jpg)](https://i.sstatic.net/Zahps.jpg)

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:

[![enter image description here](https://i.sstatic.net/D4MYl.jpg)](https://i.sstatic.net/D4MYl.jpg)

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.


---

