3
$\begingroup$

As the title says, in linear programming, is there a way to determine that the shadow price does not change linearly for a resource?

I understand one way is to simulate but is there a way to tell without simulation i.e.: looking at the variables or objective function, etc.

In other words, if I increase or decrease a certain resource linearly, the profit or cost is not going to increase/decrease linearly.

$\endgroup$
  • 1
    $\begingroup$ Your wording is a bit confusing. You start out asking if the shadow price changes linearly and end up asking if the objective value changes linearly. Which do you mean? $\endgroup$ – prubin Feb 28 at 18:54
  • $\begingroup$ Let’s say go with the main description - ignore the title. $\endgroup$ – Edv Beq Feb 29 at 2:47
  • $\begingroup$ The bit about shadow price changing is also in the first paragraph of the question. $\endgroup$ – prubin Feb 29 at 15:20
  • $\begingroup$ I feel like it’s the same - to get the objective function you multiply the shadow price with the variable. $\endgroup$ – Edv Beq Feb 29 at 23:46
  • $\begingroup$ To get the objective value, you multiply the shadow price by the constraint RHS (which is a parameter, not a variable). More to the point, as you adjust the resource availability (the RHS), the shadow price initially stays constant but the objective value changes. Beyond some point, however, the shadow price itself changes. The change in objective value is piecewise linear. The change in the shadow price is a jump discontinuity. $\endgroup$ – prubin Mar 2 at 0:45
2
$\begingroup$

The shadow prices are an optimal solution to the dual problem. Adjusting the right-hand side of the primal problem is equivalent to adjusting the objective coefficients of the dual, which changes the slope of the objective hyperplane tangent to the dual feasible region at the dual optimum. Let's assume that the initial dual optimum is non-degenerate, so that the objective hyperplane is tangent to the dual feasible region at just that one point. As you tilt the objective hyperplane more and more, initially the current optimum remains the sole point of tangency. After some amount of tilting, the hyperplane may become tangent to the dual feasible region along an edge (or possibly a higher dimensional face), meaning that the original dual optimum is still optimal but so are other points. Any further tilting and the original dual optimum is no longer a point of tangency, and thus no longer optimal.

So, short version, the shadow prices are initially unchanged as you start to futz with one of the constraint limits, then typically jump to a new dual solution (jump discontinuity). If you start at a degenerate dual optimum and tilt in the right direction, the jump (if any) is immediate.

Changes in some directions, though, may result in the current shadow prices sticking forever. As a trivial example, consider a maximization primal problem with $\le$ constraints, and suppose that at the optimum there is one constraint with positive slack (and so zero dual multiplier). If you ratchet up the right-side of that constraint, leaving the others alone, all that happens is that the slack gets bigger, so the dual multiplier for that constraint stays zero (and, for that matter, the other dual multipliers remain the same).

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.