4.6 Ranging Information

Introduction

Let us now return to return to the 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

We will now consider the meaning of the Ranging Information provided by optimisation codes. There are two types of Ranging Information: Objective Ranging and Right Hand Side Ranging.


Objective Ranging

First we shall address Objective Ranging. Consider our current objective function:

- 5 x1 - 4x2

Figure 7 shows this objective function as the line PQ. It touches the feasible region OABC at the vertex B which is therefore the optimal solution.

Figure 7: Ranging the Objective Function

Let us now consider the cost coefficient of variable x1 in the objective function. If we reduce the value of x1's cost coefficient from - 5 to - 6 the new objective function:

- 6 x1 - 4 x2

is represented by the line P'Q'. Note that the optimal solution to the problem still lies at vertex B.

Now let us decrease x1's cost coefficient by a further 2 units to - 8. The new objective:

- 8x1 - 4x2

is represented by line P*Q* shown in Figure 8.

Figure 8: Cost Ranging and Alternative Optimal Solutions

Note that there is now a choice of optimal solutions at any point along the boundary AB of the feasible region. Because we consider solutions at vertices only we have a choice of solutions at vertex B or A. Suppose we now decrease x1's cost coefficient just beyond - 8. The objective function P*Q* will get slightly steeper and the optimal solution will lie at vertex A only. For instance, decreasing x1's cost coefficient to - 10 gives an objective function of:

- 10 x1 - 4 x2

represented by line PQ.

We can therefore deduce that the cost coefficient of variable x1 can be reduced to "just above" - 8.0 without a basis change (i.e. an optimal solution occurring at a different vertex). When x1's cost coefficient is reduced to - 8.0 there is a choice of solutions. When x1's cost coefficient is reduced below - 8.0 a basis change occurs.

The value - 8.0 is sometimes referred to as x1's Lower Cost and represents the value to which a variable's cost coefficient can be reduced immediately before a basis change occurs.

By an almost identical argument, a variable's Upper Cost represents the value to which its cost coefficient can be increased immediately before a basis change occurs. In this case it turns out that x1's upper cost is - 4.0.


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 x1 + x2 ≤ 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 x1 + x2 ≤ 8.0

The line EF 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 x2 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

Comments