previous				contents				next

5. Ranging Information

5.3 Right Hand Side Ranging

We will now consider Right Hand Side Ranging. Earlier, we analyzed the effect of relaxing the right hand side of ROW2 by 0.5 in our problem:

Minimize

- 5 x1	-   4 x2			OBJ

subject to

   x1	+      x2	£   4		ROW1
2 x1	+      x2	£   5		ROW2
 - x1	+   4 x2	³    1		ROW3

x1  ³  0,  x2  ³  0

Figure 9 shows the relaxed ROW2 constraint as line E'F'. The new feasible region of the problem becomes OA'B'C.

Figure 9: Relaxing a Right Hand Side

Suppose we now consider the effect of relaxing ROW2 by a further 1.3 to 6.8. ROW2 now appears as:

2 x₁ + x₂ £ 6.8

Figure 10 shows the geometric representation of the modified problem.

Figure 10: Right Hand Side Ranging

ROW2 is represented by the line E*F*. The feasible region is now ODC. The objective function is represented by the dotted line and shows the optimal solution to lie at vertex D where:

x1  =  1.2
x2  =  2.8

OBJ  =  - 18.8

Note from our definition of shadow prices that the objective function at vertex D is given by:

Original Objective function value (at vertex B)

+ (shadow price of ROW2) * (Number of Units ROW2 is relaxed by)

i.e.

- 17.0 + ( -1.0 * 1.8 ) = - 18.8

Suppose we now relax ROW2 further than 1.8, say by a further 1.2 to 8.0 so ROW2 becomes:

2 x₁ + x₂ £ 8.0

The line E^†F^† represents the new constraint. Note from figure 10 that the feasible region is still defined by ODC. Because of constraints ROW1 and ROW3 the feasible region for the problem has remained the same and the newly relaxed ROW2 has become "redundant", lying completely outside the feasible region. From figure 10 it can be seen that this will be the case if ROW2 is relaxed any further than 6.8.

We can therefore deduce that ROW2 can be relaxed from its original RHS value of 5.0 to 6.8 and cause the objective function value to decrease by ROW2's shadow price per unit relaxation of the right hand side. Relaxing ROW2 beyond 6.8 has no effect on the optimal solution to the problem.

The value 6.8 is sometimes referred to as ROW2's Upper Activity and represents the value to which the RHS of a row can be increased at a change in the objective function value of (shadow price of that row) per unit change in the RHS. This represents a tightening or relaxation of the constraint depending on whether the constraint is a or type and if the RHS is positive or negative.

By an almost identical argument, a row's Lower Activity represents the value to which the RHS of a row can be reduced at a change in the objective function value of (shadow price of that row) per unit change in the RHS.

Note from figure 10 that if we tighten ROW2 from a RHS of 5.0 the feasible region will slowly be reduced until it is represented by OAC. This occurs when the RHS of ROW2 is reduced to 4.0. The optimal solution to the problem will now lie at point C. Tightening ROW2 further will have a direct effect on the optimal solution to the problem in that the optimal vertex C will "move down" the x₂ axis but the objective function will not change by (shadow price of that ROW2) per unit change in RHS. In fact it will change at a faster rate because we are now "moving" the vertex C rather than vertex B.

Since the upper and lower activities for each row are concerned with how much the constraint can be relaxed or tightened to give a constant change in objective function value the lower cost of ROW2 in this case is 4.0.

previous				contents				next