Consider the following problem with two variables.
The geometric representation of this problem appears in Figure 3.
The shaded area OABC represents the feasible region. The line PQ represents the objective function. The optimal solution to the problem lies at vertex C where:
Variable x
The geometric representation of the modified problem is shown in Figure 4.
The new solution to the problem now lies at vertex C where:
Note that forcing the non-basic variable off its lower bound has worsened the value of the objective function (it is greater and we are minimising). We have seen that:
We can therefore define the unit cost of forcing the non basic variable x
Therefore the unit cost of forcing the non basic variable x It is important to note that all sensitivity analysis information addresses
Let
us now return to our original problem and examine the effect of
lowering the cost coefficient in the objective function of the non
basic variable x
to
The geometric representation of the problem now appears as in Figure 5.
The line PQ in Figure 5 represents the original objective function and the line P'Q' the new objective. Note that there is now a choice of solutions at either vertex C or B. The solution at vertex B is:
Note that the variable x From
this last property of reduced costs, note that the reduced cost of a
basic variable is zero. This is logical since no change in its cost
coefficient is required for it to become basic since it already is. It
is possible to have a non basic variable with a reduced cost of zero.
This indicates that we can make this variable basic (and another
suitable variable non basic) with no change in the objective function
value. Thus, a non basic variable with zero reduced cost indicates that
an
Let us now change the objective function in our original problem in this section to :
Also, consider the ROW2 constraint:
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:
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:
Note that relaxing constraint ROW2 has improved the value of the objective function (it has decreased and we are minimising). We deduced that:
We can therefore define the unit cost of relaxing constraint ROW2 by:
Therefore the unit cost of relaxing constraint ROW2 is -1.0. This value is called the 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
If ROW1 is binding, the slack variable e
If ROW1 remains binding, we must have the following relationship:
The slack variable e 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. |

LP Training > 4. Interpretation of Results >