Example of Infinite Solutions in the Simplex Method

One of the possibilities that we may face when solving a Linear Programming model through the Simplex Method is finding multiple or infinite solutions, this means there is a stretch of feasible solutions that report the same value for the objective function that cannot be improved. If after applying the necessary iterations of the Simplex Method to a Linear Programming model (optimal tableau) we must verify that a non-basic variable has zero reduced cost, this will tell us that this is a case of infinite solutions.

Consider the following Linear Programming model:

lineal model

We model it in a standard form to proceed with the implementation of the Simplex Algorithm, with S1 and S2 as slack variables of the constraint 1 and 2, respectively.

standar linear problem

The initial tableau with S1 and S2 as initial basic variables looks like this:

initial tableau simplex

Y enter in the base. For determining the variable that leaves the base we use the minimum quotient cut: Min {12/4; 16/3}=3 ==> S1 leaves the base. With this information we update the tableau:

infinite solutions simplex

After one iteration of the Simplex Method we find the optimal solution, where Y and S2 are basic variables. The optimal solution is X=0, Y=3, S1=0, S2=7. The optimal value is V(P)=6. Note that X (a non-basic variable) has zero reduced cost that determines the existence of multiple or infinite optimal solutions, so the current solution is one of the optimum vertex.

The diagram below shows the graphic resolution of the problem (using Geogebra) where the optimal solution we have encountered in applying the Simplex Method corresponds to vertex B. Note that the dotted blue line corresponds to the contour of the objective function with the same slope as constraint 1 (slope -1/2).

infinite solutions linear programming

How can we obtain vertex C which is the optimal solution through the Simplex Method? An alternative would be forcing it into the base of variable X in the optimal tableau. We then calculate which of the current basic variables leaves the database according to the criteria of minimum quotient: Min {3/1/2; 7/5/2}=14/5==> S2 leaves the base. Updating the tableau we obtain:

infinite solutions 2

The new optimal solution (with the same optimal value) is X=14/5, Y=8/5S1=0, S2=0, which corresponds to vertex C in the graph above. Now the non-basic variable S2 has reduced cost of zero in the optimal table and indicates multiple optimal solutions (in this example, section BC).

Rating: 3.3/5. From 10 votes.
Please wait...

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.