Tag Archives: Right Hand Side (RHS)

zero shadow price

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).

graphical solution linear programming

How to Calculate the Shadow Price of a Constraint

The Shadow Price of a constraint in Linear Programming indicates how much the value of an objective (optimal) function changes due to a marginal variation in the right-hand side of a constraint. It is assumed that the rest of the model’s parameters remain constant. It should be noted beforehand that the Shadow Price can be positive, zero, or negative, and these different possibilities will be discussed in the Blog.

Computational tools like Excel’s Solver can be used for obtaining the Sensibility Analysis from a Linear Programming model; however, here we will be focusing on calculating the Shadow Price of a constraint graphically, which will help us later on to understand the concepts behind the Solver results.

Calculate the Shadow Price of a Constraint Graphically

We will now calculate the Shadow Price of a constraint for the following Linear Programming model:

linear programming example

The optimal solution of this model is X=100 and Y=350 with an optimal value V(P)=3,100 according to the graphical Geogebra solution or the Solver solution from Excel. The following diagram shows the optimal solution obtained graphically at vertex C, which corresponds to the intersection of constraint 1 (R1: red color) and constraint 3 (R3: black color), this being the optimal basic feasible solution.

graphical solution linear programming

Suppose we want to know how the optimal value will change (with respect to its current value) if the right-hand side of constraint 1 is raised by one unit but without having to re-solve the problem. The shadow price allows us to answer that question and can anticipate the new optimal value resulting from a marginal variation of the right-hand side of a constraint.

A marginal variation of a right-hand side means that the new optimal solution can still be found using the current active constraints, i.e., those that are satisfied with equality (this conserves the optimal basis).

For constraint 1 if we increase its right-hand side, it will be moved upward in a parallel manner. If we want to guarantee that the new optimal solution can still be found with R1 and R3 active, we reach the vertex where R2 and R3 currently intercept corresponding to the coordinate X=166.67 and Y=350 (this is the maximum variation). In the same fashion if we decrease the right-hand side of constraint 1 and try to maintain R1 and R3 active in the new optimal, the last point where this is guaranteed is at vertex B, whose coordinates are X=0 and Y=350 (this will be the smallest variation). With this information we calculate the shadow price of constraint 1:

shadow price constraint

This shadow price is valid if the right-hand side of constraint 1 (currently b1=1,600) varies between [1,400,1,733.33]. For example, if the right-hand side of R1 increases from 1,600 to 1,700 the new optimal value would be V(P)=3,100+100*1.5=3,250. Similarly if the right-hand side of R1 decreased from 1,600 to 1,550 the new optimal value would be V(P)=3,100-50*1.5=3,025. (It is recommended you confirm these results graphically with TORA or IORTutorial).

Note that if the right-hand side variation of constraint 1 is outside of the interval [1,400,1,733.33], the shadow price cannot be used to predict the new optimal value. In an upcoming analysis we will finish calculating the shadow price of constraints 2 and 3 along with other Sensibility Analysis in solving Linear Programming models.

How to Solve a Linear Programming (LP) problem with What’sBest!

The following tutorial will show how to solve a Linear Programming (LP) model with What’sBest! 11.1. Of course, you previously need to download and install What’sBest! as a add-in for Excel the way we explained it step by step in a previous tutorial.

In order to show how to use this Excel add-in we will use the Transportation Problem to find a distribution policy that minimizes logistics costs, while satisfying customer demands and respects the capacity of suppliers. The information is summarized in the following diagram for the particular case of 2 industrial plants (suppliers) and 3 customers, where the numbers on the arrows represent the unit costs of transportation between an industrial plant and a customer.

transportation-problem-diag

How to Solve a Linear Programming problem with What’sBest!

The steps to implement this Linear Programming problem in What’sBest! are:

Step A: Define the Decision Variables: Previously set the cells that you will use as variables in an Excel worksheet. In the example the Xij: transported units from industrial plant i to customer j. If i=1,2 and j=1,2,3 there are 6 decision variables.

decision-variables-whatsbes

Important: Complete the cells that will be decision variables with zero as shown in the image above. Then select the range of cells that correspond to the variables in the model and press “Make Adjustable”.

Step B: Define the Objective Function: As the name suggests, this cell corresponds to the goal of the optimization problem which in this case is to minimize the total costs of transportation. The cell contains a formula: SUMPRODUCT(C3:E4;C12:E13) previously uploaded that ponders the unit costs of transportation for the different combinations (data or parameters) and the decision variable previously defined (“SUMAPRODUCTO” is the name of the formula in the spanish version of Excel). Finally go to the cell of the objective function and select “Minimize” in this case.

linear-programming-in-whats

Step C: Define the Constrains: The constrains of the optimization model, i.e., the conditions to be fulfilled the decision variables at the time of the resolution are incorporated. For this purpose, select the “Constraints” option in the menu. The image below shows how, the restriction that guarantees that the number of units shipped by each plant (LHS) does not exceed (<=) the capacity of it, (RHS) is attached. As you can see the constrains of the capacity of Plant 1 and 2 are incorporated simultaneously.

constraints-whatsbest

Finally, to go ahead with the resolution of the model we select the option “Solve” from the menu:

solve-whatsbest

After which we get the following results:

optimal-solution-transporta

Optimal Solution: X11=80.000; X12=0; X13=40.000; X21=0; X22=70.000; X23=50.000. The Optimal Value (minimum cost) is $940.000.

Do you want to have the Excel file with the solution of this problem with What’sBest!? Recommend us on Facebook, Google or Twitter using the social network tool at the bottom of this article and then download the file.

Changes in the Right Hand Side (RHS) of the Constraint (Sensitivity Analysis in Linear Programming)

Vector on Right Hand Side (RHS) associated with the constrains of a Linear Programming model may have different practical interpretations such as the availability of inputs for the manufacture of certain products, limiting of capacity, demand requirements, among other. As a result it is interesting to analyze the impact of the change of one or more coefficients of the vector on right hand side over the original results of the model without the need of optimizing again. In particular if we verify that:

vector-xb

It can be said that the current optimal base is preserved. This implies that the basic variables of the model will remain so under this new scenario and therefore you will find the new optimal solution of the problem through the resolution of the original system of equations (the original active constrains are preserved). Now, if any of the coefficients in the calculation of the basic variables vector takes a negative value, we have an infeasible basic solution, which forces us to make an update of the results of the model to find the new solution, optimal base and optimal value, but not needing  to passing through the reoptimization of it.

Changes in the Right Hand Side (RHS) of the Constraint

Consider the following Linear Programming model:

linear-programing-two-decis

When solving this Linear Programming model with Simplex Method you reach the next final tableau, where s1, s2, and s3 are the slack variables of the constrains 1, 2, and 3, respectively:

simplex method optimal tableau

The basic variables are x=100, s2=400, y=350, all of which meet the conditions of non negativity (i.e. is a basic feasible solution) and also the reduced cost of the non-basic variables (s1 y s3) are bigger or equal to zero, the necessary and sufficient condition to ensure that we have the optimal solution of the problem (optimal basic feasible  solution). In addition and related with the previous proposition we can confirm the results we got:

basic variables vector

Now lets consider that the right hand side of the constrain 1 changes from its original value 1.600 to 1.650. Does it change the current optimal basis? To do this we recalculate the vector of the basic variables:

modify xb vector

You can see that all the coefficients of the vector of basic variables (Xb) are bigger or equal to zero, i.e. the optimum base (same basic variables) is preserved but the optimal solution changes to x=125, s2=250, y=350. Additionally the optimal value now is V(P)=3.175. However, it is not necessary to continue the iterations of the Simplex Method (as we are facing an optimal basic feasible solution) and preventing us from doing a reoptimization.

The natural question is: What happens if, when calculating the vector of the basic variables, at least one of the variables gets a negative value? Now let´s modify simultaneously the right sides of constrains 1 and 2 to 2.000 and 1.500, respectively. The new basic variables vector is defined in the following way:

xb vector 2

Notice that now the basic variable s2=-1.000 takes a value that does not satisfy the condition of non negativity for the decision variables. To address this situation of infeasibility  it is necessary to update the final tableau of the Simplex Method with the value of the basic variables and the objective function value:

simplex method tableau 2

In order to find the optimal solution of this problem from the above table, the Dual Simplex Method can be applied. The basic variable given by the base is s2 (basic variable associated with row 2 where we find the negative ‘right hand side’). In order to decide the variable that goes to the base, we calculate the minimum quotient: Min{-3/2/-3}=1/2 ==> s1 goes to the base. We update the tableau of the Simplex Method with the following:

optimal solution simplex method

You can see that it was only necessary to do an additional iteration to get the optimal solution for the new scenario (x=400/3, s1=1.000/3, y=350) with an optimal value of V(P)=3.200. The following chart made with Geogebra,  allows us to see the new optimal solution and structure of the problem, where now the optimal solution finds the 2 and 3 active constrains (the original problem in its optimal solution considered 1 and 3 as active constraints):

optimal solution linear programming with geogebra