previous				contents				next

5. Ranging Information

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

5.2 Objective Ranging

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

- 5 x₁ - 4x₂

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 x₁ in the objective function. If we reduce the value of x₁'s cost coefficient from - 5 to - 6 the new objective function:

- 6 x₁ - 4 x₂

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

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

- 8x₁ - 4x₂

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 x₁'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 x₁'s cost coefficient to - 10 gives an objective function of:

- 10 x₁ - 4 x₂

represented by line P^†Q^†.

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

The value - 8.0 is sometimes referred to as x₁'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 x₁'s upper cost is - 4.0.

previous				contents				next