Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
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.
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).
