Simplex Method

Special Cases

4. Multiple Optimal Solutions

The optimal solution may not be unique, if the non basic variables have a zero coefficient in the index row (z_j-c_j). This implies that bringing the non basic variable into the basis will neither increase nor decrease the value of the objective function. Thus, the problem has multiple optimal solutions (Alternative optimal solutions).

Example

Maximize 2000x₁ + 3000x₂

subject to

6x₁ + 9x₂ £ 100
2x₁ + x₂ £ 20

x₁, x₂ ³ 0

Solution.

After introducing slack variables, the corresponding equations are

6x₁ + 9x₂ + x₃ = 100
2x₁ + x₂ + x₄ = 20
x₁, x₂, x₃, x₄ ³ 0

Where x₃ and x₄ are slack variables.

Table 1

Table 2

Since z_j-c_j ³ 0 for all variables, x₁ = 0, x₂ = 100/9 is an optimum solution of the problem. The maximum value of the objective function is 100000/3. However, the z_j-c_j value corresponding to the non basic variable x₁ is zero. This indicates that there is more than one optimal solution of the problem. Thus, by entering x₁ into the basis we may obtain another alternative optimal solution.

However, the value of the objective function will not be improved, although the present solution x₁ = 0, x₂ = 100/9 is shifted to x₁ = 20/3 and x₂ = 20/3.

5. Degeneracy

In some cases, there may be ambiguity in selecting the variable that should be introduced into the basis, i.e., there is a tie between the replacement ratio of two variables. To resolve degeneracy, we select one of them arbitrarily.

Consider the following example.

Example

Maximize 3x₁ + 9x₂

subject to

x₁ + 4x₂ £ 8
x₁ + 2x₂ £ 4

x₁, x₂ ³ 0

Solution.

After introducing slack variables, the corresponding equations are:

x₁ + 4x₂ + x₃ = 8
x₁ + 2x₂ + x₄ = 4
x₁, x₂, x₃, x₄ ³ 0

Where x₃ and x₄ are slack variables.

Table 1

Minimum positive value (8/4, 4/2) = (2, 2)

There is a tie between the two values. So you are at liberty to break the tie arbitrarily.

In the following material, we will consider both the cases.

Case I

x₄ departs & x₂ enters.

Table 2

x₁ = 0, x₂ = 2, z = 18

Case II

x₃ departs & x₂ enters.

Table 2

x₄ departs & x₁ enters.

Table 3

x₁ = 0, x₂ = 2, z = 18

In this chapter, you learned the mechanics of obtaining an optimal solution to a linear programming problem by the simplex method. The simplex method is an appropriate method for solving a £ type linear programming problem with more than two decision variables. Two phase and M-method are used to solve problems of ³ or £ type constraints. Further, the simplex method can also identify multiple, unbounded and infeasible problems.