the assignment problem has alternative solution if

Math Article

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 1 , x 2 ) 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.

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

Max Z = 2x 1 + 4x 2

x 1 + 2x 2 ≤ 5

x 1 + x 2 ≤ 4

and x 1 , x 2 ≥ 0.

Given LPP is:

and x 1 , x 2 ≥ 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 1 and S 2 , respectively.

Thus, we get the modified problem as:

Max Z = 2x 1 + 4x 2 + 0.S 1 + 0.S 2

x 1 + 2x 2 + S 1 = 5

x 1 + x 2 + S 2 = 4

and x 1 , x 2 , S 1 , S 2 ≥ 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 2 .

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

That means S 1 is the remaining basic variable.

∴ The pivot element (key element) is 2.

Now, perform the following operations on rows.

R 1 → R 1 /2

R 2 → R 2 – new R 1

Here, all Z j – C j ≥ 0

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

x 1 = 0, x 2 = 5/2

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

Also, in the above iteration table, we have Z 1 – C 1 = 0 and x 1 is not in the basis (i.e. x 1 = 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 1 into the basis.

Here, the entering variable is x 1 .

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

Also, the pivot or key element is 12.

Now, R 2 → R 2 × 2

R 1 → R 1 – (½) new R 2

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

x 1 = 3, x 2 = 1

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

Frequently Asked Questions on Alternate Optima

What is an alternative optima in the simplex method.

In the simplex method, an alternative optima arises when all z i – c i are greater than or equal to 0, and one of the variables cannot be the basis variable in interaction tables.

How do you determine if an LPP has an alternative optimal solution?

When the given LPP (linear programming problem) contains more than one optimal solution, then we can say that there exists an alternative optimal solution.

Can we have multiple optimal solutions for an LPP?

Yes, a linear programming problem (LPP) can have multiple optimal solutions, i.e. more than one or infinite solutions.

Register with BYJU'S & Download Free PDFs

IMAGES

Alternative Solution in Assignment Problem
Alternative Solution to Assignment problem & Solved Examples
Assignment Problem (Part-4) Unbalanced / Alternate Optimal Solution in Assignment Problem
Solution of Assignment Problems
The Assignment Problem: An Example / the-assignment-problem-an-example
Solution of assignment problems (Hungarian Method)