What does a Shadow Price of Zero mean in Linear Programming

As we have discussed in previous articles, the Shadow Price of a constraint represents the rate of change of the optimal value as a result of a marginal change in the right-hand side of a constraint. “Marginal” is understood as a modification that does not change the geometry of the problem, that is to say, the new optimal solution can be found by solving the system of equations that led to the original active constraints (previously updating the parameter we are modifying). In this context the shadow price can be a value that is positive, negative or zero, in this article we will be referencing the latter.

Consider the following Linear Programming model in 2 variables:

lp infinite solutions

The previous problem can be solved graphically using Geogebra, which generates a problem with infinite optimal solutions in the section of the straight line that connects vertexes B and C and can be generally described as: (X,Y)= λ(0.60)+(1- λ)(10.45) with λ in the interval between [0,1]. The optimal value is therefore V(P)=1,200.

infinite solutions

What are the active constraints at the optimal? If we consider for example vertex B (optimal solution), the active constraints are 3X+2Y<=120 and X>=0, nevertheless if we select vertex C (also optimal solution) the active constraints are 5X+2Y<=140 and 3X+2Y<=120.

Given the previously stated, will the optimal value increase if there are additional resource units available representing the right-hand side of the constraint 5X+2Y<=140? In order to answer this we try and keep the constraints of vertex C active by identifying the maximum variation (increasing the value of the right-hand side) that retains the original active constraints (this will produce a parallel shift of the constraints that we have shown with the red color dotted line) which is attained at the coordinate (X,Y)=(40,0). Similarly in order to determine the minimal variation for the right-hand side, we move the constraint in a decreasing direction to the coordinate (X,Y)=(0,60) trying to maintain the original active constraints (orange color dotted line).

zero shadow price

We evaluate this result in the following formula in order to calculate the Shadow Price value, obtaining the following:

shadow price zero

Therefore the shadow price of constraint 1 (5X+2Y<=140) is zero, which indicates that if the value of the parameter representing its right-hand side increases or decreases (currently b1=140) in the interval between [120,200] the optimal value of the problem will not be affected. The above is consistent with what was obtained using the confidentiality analysis of constraints by Solver in Excel:

shadow price zero in solver

In general a Shadow Price equaling zero means that a change in the parameter representing the right-hand side of such constraint (in an interval that maintains the geometry of the problem) does not have an impact on the optimal value of the problem. Nevertheless, there are special cases like the Linear Programming problems that support infinite solutions (like the one described in this article) where a constraint with a shadow price of zero can be active in one of the optimal vertexes (the most common case is a constraint with a shadow price of zero that is not active in the optimal).

Rating: 4.3. From 6 votes.
Please wait...

, , , , , , , ,

Sin Comentarios aun. Se el primero en comentar!

Leave a Reply