Compare shadow prices of one specific constraint in two similar LPs.

51 Views Asked by At

I am working with two similar Linear Programming (LP) problems involving nine decision variables.

Here's a representation of the two problems, with the only difference in the third constraint:

LP1:

\begin{align*} \text{Maximize} \quad & c^T x \\ \text{subject to} \quad & a_1^T x_{1:3} \leq b_1 \\ & a_2^T x_{4:6} \leq b_2 \\ & a_3^T x_{7:9} \leq b_3 \\ & a_4^T x \leq b_4 \\ & x \geq 0 \end{align*}

LP2:

\begin{align*} \text{Maximize} \quad & c^T x \\ \text{subject to} \quad & a_1^T x_{1:3} \leq b_1 \\ & a_2^T x_{4:6} \leq b_2 \\ & a_3^T x_{7:9} \leq b_3' \\ & a_4^T x \leq b_4 \\ & x \geq 0 \end{align*}

where $b_3' = b_3 + 1$, and $a \geq 0, b \geq 0, c \geq 0$.

I am interested in comparing the shadow price of one of the first three constraints in these two LPs. My intuition is that the shadow price in the first LP is always larger than the second. This is because if we take the first three constraints as capacity constraints and the fourth as resource limitation, then the marginal reward by adding capacity in a condition with larger capacity should be smaller.

This looks like a classical result, but I don't know any general results, methods, or references that can be applied to derive this kind of conclusion. I was thinking about using convex analysis to derive it, but didn't have any luck.

Any insights, mathematical explanations, or guidance on how to approach this analysis would be greatly appreciated.