Multiple Optimal Solutions: Simplex Method

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 linear program problem (LPP) has multiple optimal solutions (Alternative optimal solutions). For example, let us consider the following example of simplex method.

Multiple Optimal Solutions Example : LPP

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: Simplex Method

On small screens, scroll horizontally to view full calculation

Table 2

Since z_j-c_j ≥ 0 for all variables, x₁ = 0, x₂ = 100/9 is an optimum solution of the LPP. 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.