previous				contents				next

4. Sensitivity Analysis

4.6 Shadow Prices

Let us now change the objective function in our original problem in this section to :

Minimize - 5 x₁ - 4 x₂

Also, consider the ROW2 constraint:

2 x₁ + x₂ £ 5

Suppose we were to increase the right hand side of this constraint by 0.5 to 5.5. We refer to this as "relaxing" the constraint by 0.5 because it gives the model greater freedom. The geometric representation of the problem now appears in Figure 6.

Figure 6: Relaxing a Constraint

The original ROW2 constraint is represented by the line EF in Figure 6. The relaxed version of ROW2 is represented by the line E'F'. Note that the feasible region to the problem has now changed from OABC to OA'B'C because of the relaxed constraint. The dashed line represents the objective function. Note that the optimal solution to the original problem lies at vertex B. The solution at this point is:

x1  =  1.0
x2  =  3.0

OBJ  =  - 17.0

Because ROW2 passes through the optimal vertex (it is a binding constraint) and we have relaxed it, the optimal solution to the new problem (ROW2 relaxed) now lies at the "moved" vertex B'. The solution at this vertex is:

x1  =  1.5
x2  =  2.5

OBJ  =  - 17.5

Note that relaxing constraint ROW2 has improved the value of the objective function (it has decreased and we are minimising). We deduced that:

OBJ with ROW2 unrelaxed       	=   - 17.0
OBJ with ROW2 relaxed by 0.5	=    - 17.5

We can therefore define the unit cost of relaxing constraint ROW2 by:

Change in objective function value	=   0.5 	=   - 1.0
Change in RHS of ROW2		     0.5

Therefore the unit cost of relaxing constraint ROW2 is -1.0. This value is called the shadow price of ROW2 and implies that for every unit we relax the RHS of constraint ROW2 by the objective function will change by -1.0. This value is symmetric in that increasing ("tightening") the right hand side of ROW2 will change the value of the objective function by +1.0 / unit .

Note that, for a non-binding constraint such as ROW3 in our above problem, relaxing or tightening it has no affect on the optimal solution since, although the feasible region will be changed, the constraint does not pass through the optimal vertex B and therefore relaxing or tightening it will not "move" vertex B. The solution will therefore remain at vertex B. Consequently , the shadow price of a non binding constraint is zero.

On a more technical note, consider a constraint, say ROW1 in our model with its slack variable, say e₁ added:

x1  +   x2  +  e1   =   4		ROW1

If ROW1 is binding, the slack variable e₁ will be non basic at zero. Suppose we increase the right hand side of ROW1 by 1 unit, ie

x1  +  x2   £   4 + 1			ROW1

If ROW1 remains binding, we must have the following relationship:

x1  +  x2  - 1   =   4			ROW1

The slack variable e₁ must therefore, technically become -1. Now the reduced cost of a non- basic variable indicates how much the objective function will be worsened per unit increase of the non basic variable from its lower bound. This is also a measure of the improvement in the objective function value if the non-basic variable could be decreased below its lower bound, ie. in this case to -1. The shadow price of a constraint is actually therefore the reduced cost of the non-basic slack variable if the constraint is binding.

If the constraint is non-binding, its slack variable will be greater than zero and therefore basic. The reduced cost of a basic variable is zero. The shadow price of a non-binding constraint is therefore zero.

previous				contents				next