Alternate Optima

We know that an optimal solution is a solution to a linear programming problem that satisfies the set of constraints of the problem (either maximization or minimization problem) and the corresponding objective function. An alternate optima arises when an LPP (linear programming problem) or integer programming problem contains more than one optimal solution. Also, an alternate optima is called an alternate optimal solution.

Learn: Linear programming problem

Alternate Optimal Solution in Graphical Method

Consider a graphical analysis of a problem (see figure) given with a set of constraints and an objective function of maximization. As we know, the optimal solution set is a smaller set within the feasible region. The below graph represents the feasible region obtained from three constraints of a linear programming problem.

In the above graph, the objective function is parallel to the line segment rs. Thus, all the rs points (x₁, x₂) provide maximum yield. That means there is an alternate optimal solution.

Alternate Optimal Solution in LPP

In LPP (linear programming problem), an alternate optimal solution or alternative optimal solution occurs when the given problem has more than one solution, which means when the objective function is similar to a nonredundant critical constraint. Here, the critical constraint is the constraint that is satisfied as an equation at the optimal solution. Also, the objective function can take the same optimal value for more than one solution point, thus providing us with alternative optima.

Alternate Optimal Solution in Simplex Method

Let us consider an example problem that contains infinite solutions and is solved using the simplex method. It also illustrates the practical consequence of identifying such solutions.

Example:

Find the solution of the problem given below using the simplex method (big M method)

Max Z = 2x₁ + 4x₂

subject to

x₁ + 2x₂ ≤ 5

x₁ + x₂ ≤ 4

and x₁, x₂ ≥ 0.

Solution:

Given LPP is:

Max Z = 2x₁ + 4x₂

x₁ + 2x₂ ≤ 5

x₁ + x₂ ≤ 4

and x₁, x₂ ≥ 0

The given problem can be converted into canonical form by adding suitable slack variables, surplus variables and artificial variables.

The first and second constraints are of type ‘≤’, in the given problem, so we should add slack variables S₁ and S₂, respectively.

Thus, we get the modified problem as:

Max Z = 2x₁ + 4x₂ + 0.S₁ + 0.S₂

subject to

x₁ + 2x₂ + S₁ = 5

x₁ + x₂ + S₂ = 4

and x₁, x₂, S₁, S₂ ≥ 0

Let’s make the table for iteration 1.

The negative minimum of Z_j – C_j is -4, and its column index is 2. Thus, the entering variable is x₂.

The minimum ratio is 2.5, and its row index is 1.

That means S₁ is the remaining basic variable.

∴ The pivot element (key element) is 2.

Now, perform the following operations on rows.

R₁ → R₁/2

R₂ → R₂ – new R₁

Here, all Z_j – C_j ≥ 0

Hence, the optimal solution has arrived with value of variables as :

x₁ = 0, x₂ = 5/2

Max Z = 2(0) + 4(5/2) = 10

Also, in the above iteration table, we have Z₁ – C₁ = 0 and x₁ is not in the basis (i.e. x₁ = 0).

This implies that there is more than 1 optimal solution to the problem.

Therefore, we may get another alternative optimal solution by entering the variable x₁ into the basis.

Here, the entering variable is x₁.

The minimum ratio is 3, and its row index is 2. That means S₂ is the remaining basis variable.

Also, the pivot or key element is 12.

Now, R₂ → R₂ × 2

R₁ → R₁ – (½) new R₂

Here, all Z_j – C_j ≥ 0

Hence, the optimal solution has arrived with the value of variables as:

x₁ = 3, x₂ = 1

Max Z = 2(3) + 4(1) = 6 + 4 10