Tag Archives: simplex method

Degenerate Optimal Solution

What is a Degenerate Optimal Solution in Linear Programming

When applying the Simplex Method to calculate the minimum coefficient or feasibility condition, if there is a tie for the minimum ratio or minimum coefficient it can be broken arbitrarily. In this instance, at least one basic variable will become zero in the following iteration, confirming that in this instance the new solution is degenerate. The practical implication of this condition indicates that the model has at least one redundant constraint.

Degenerate Optimal Solution

Let’s consider the following Linear Programming model which we will solve using the Simplex Method and which we will also represent graphically with Geogebra:

Degenerate Optimal Solution LP

We put the above problem in its minimized standard form, adding x_{3} and x_{4}, as slack variables for constraints 1 and 2, respectively.

standard-Degenerate-Optimal

Which produces the following Simplex Method initial tableau:

initial tableau Degenerate Optimal Solution

To facilitate the fast convergence of the algorithm we select x_{2} as the entering variable. Next we calculate the feasibility criteria (smallest coefficient): Min\begin{Bmatrix}\frac{8}{4};\frac{4}{2}\end{Bmatrix}=2 (if a tie exists we arbitrarily select variable x_{3} as the variable that leaves the basis. Then we update the tableau:

simplex Degenerate Optimal Solution

Now x_{1} enters the basis. The feasibility criteria determines that: Min\begin{Bmatrix}\frac{2}{1/4};\frac{0}{1/2}\end{Bmatrix}=0 x_{4}  leaves the basis. A new iteration is made:

Degenerate Optimal Solution simplex

The degenerate optimal solution is reached for the linear problem. Note that x_{1}=0, x_{2}=2, x_{3}=0, x_{4}=0, V(P)=18. As this is a two-dimensional problem, the solution is overdetermined and one of the constraints is redundant just like the following graph confirms:

Degenerate Optimal Solution

In practice knowing that some resources (like those associated with a constraint) are superfluous can be useful during the implementation of a solution. From a theoretical point of view, the degeneration has two implications: it produces the cycling or circling phenomenon (it’s possible that the Simplex Method repeats a series of iterations without ever improving the value of the objective function and the calculations are interminable, as can be observed in the previous example); the second theoretical aspect arises when iterations 1 and 2 are examined. Although they differ in the classification of basic and nonbasic variables, both produce identical values for all variables and for the objective value x_{1}=0, x_{2}=2, x_{3}=0, x_{4}=0, V(P)=18.

 

simplex method

10 Things You need to know about Simplex Method

The Simplex Method was developed by George Dantzing in 1947. It is without a doubt the most popular algorithm when it comes to solving a Linear Programming (LP) model, and it plays a major role in the introduction to Operations Research (OR).

Today we’re presenting a summary of 10 main concepts about the use and application of the Simplex Method for our users to be able to have a first approach to the method, while paying attention to some characteristic aspects:

Simplex Method (10 Things You need to know)

  1. History: In 1947 it was first published by George Dantzing, an American mathematician.
  2. Standard Form: The Simplex Method’s application requires the Linear Programming model to be on its standard form.
  3. Basic Feasible Solution (BFS): A basic feasible solution matches a vertices in domain of a Linear Programming model’s feasible solutions.
  4. Optimality Criterion: The Basic feasible solution is optimal if and only if the reduced costs of all the nonbasic variables are higher or equal to zero.
  5. Infinite Solutions: This case is seen when there are reduced costs equal to zero in one or more optimal nonbasic variables.
  6. Unbounded Problem: This case is seen when, while doing the calculus of the variable which leaves the base, all the elements ykj of the column j in the tableau are negative.
  7. Infeasible Problem: This is the case when the optimal value of the problem in Phase 1 (in a Two Phase Simplex Method) is nonzero.
  8. Rate of Convergence: If two or more nonbasic variables have negative reduced cost, the entrance to the base goes to the lowest reduced cost.
  9. Postoptimal Analysis: Once we achieve the optimal solution through the Simplex Method, we can analyze the impact in the results with the alteration of the parameters.
  10. Excel Solver: The Excel complement Solver allows us to use the Simplex Method as a solving method (Simplex LP)

This review is based on the experience we have teaching Operations Research and on the most frequent questions we receive daily from undergraduate students.

simplex method

You can download the infographic as a PDF file here: Simplex Method

We encourage you to check and share this infographic on your social webs. Also, if you think there’s an important aspect missing in the previous list, you can use the commentary section at the bottom of this page to let us know. This is how we can keep updating the article with the main characteristics of the Simplex Method.

How to Solve a Linear Programming model with Dual Simplex Method

The Dual Simplex Method offers an alternative when solving Linear Programming (LP) models with algorithms. This method may be used in particular when the standard way to carry a linear programming model is not available from an initial basic feasible solution. Consider the following LP problem to illustrate the application of the Dual Simplex Method:

lp-dual-simplex-method

To solve the problem above in a standard form, we must add 2 excess non-negative variables for constraints 1 and 2, which we will respectively call X4 and X5. Thus the problem in its standard format is defined by:

standard-lp-dual-simplex-me

Then we build the initial tableau of the Simplex Method:

initial-tableau-dual-simple

How to continue the iterations of the Simplex Method? Before that, it is necessary to have an initial basic feasible solution. In this context if we want to use X4 and X5 as basic variables (and hence X1, X2 and X3 as basic variables) it is required that X4 and X5 are greater than or equal to zero, however, their coefficients in the respective rows are negative and therefore we can’t use them (matrix with “1” as a diagonal, and all the other coefficients at zero). So to form the identity we can multiply by “-1” row 1 and 2, obtaining the following:

transformation-tableau-dual

Now X4 and X5 are basic variables and adopt the values of -1 and -3/2, respectively, which clearly does not satisfy the conditions of non-negativity for the decision variables, i.e. they do not correspond to a basic feasible solution. However, in this instance we can apply the Dual Simplex Method as an alternative resolution. To do this, we will select a variable to leave the base and adopt as a criterion for basic variable associated with “more negative” right hand side (RHS). In this instance the variable is X5. Then to determine which variable will go into the base we find a minimum quotient between the negative of the reduced cost of the non-basic variables and the strictly less than zero entries for non-core variables in row 2 (row associated with more negative right). I.e.: Min {-160/-2; -120/-2; -280/-2} = 60, then the minimum quotient is reached in the second column associated with the non-basic variable X2, therefore said variable enters the base.

Finally one iteration is done by performing the operations of the necessary rows, so we enter X2 into the base, meanwhile at the same time X5 leaves the base. The results are:

iteration-simplex-dual-meth

Note that now the basic variables are X4 and X2 where only X4 = -1/4 which does not satisfy the condition of being a feasible basic solution. Therefore we make a new iteration, in this case taking the base to the X4 variable and calculate the minimum quotient: Min {-40/-1; -160/-3; -60/-1/2} = 40, then the minimum quotient is in the first column, therefore variable X1 enters the base. Consequently the remaining table is updated as follows:

final-tableau-dual-simplex-

The basic variables are now X1=1/4 and X2=1/2 (which meet the conditions of non-negativity). Additionally, the reduced cost of the non-basic variables is greater than or equal to zero, therefore we face the optimal solution. We can additionally recognize that the optimum value is V(P)=100 that would be obtained by evaluating the optimal solution to the objective function, however, the value is obtained by said process with a changed sign.

The example above allowed us to appreciate how through the Dual Simplex Method can solve a linear programming model that after being solved by the standard form does not provide an initial basic feasible solution. Significantly, it is not the only algorithmic alternative to which we can appeal. For example we could have achieved the same results using the Two-Phase Simplex Method with some more work. Alternatively we can define the proposed problem with the dual model and solve it by the Simplex Method so that we may later use the conditions of Complementary Slackness Theorem. In summary before we use an optimization model we have several alternatives for resolution and it is the duty of solver to evaluate the different paths that we can take in terms of its complexity.

Fundamental Theorem of Linear Programming and its Properties

In this following article we will address properties set by the Fundamental Theorem of Linear Programming through a conceptual discussion and practical and simple examples. These properties are essential when taking into consideration algorithmic resolutions of this kind of mathematical optimization models, among them is what we call the Simplex Method.

Every Linear Programming (LP) problem in standard form complies with the following three properties:

  • Property 1: “If the problem has no optimal solution then it’s unbounded or infeasible”

Note that a linear problem with a domain of unbounded feasible solutions may (or may not) allow optimal solution, i.e. facing a model with these features does not determine the presence (or absence) of an optimal solution a priori.

In the implementation of the Simplex Method there is a detection of an unbounded problem without optimal solution when calculating the variable that leaves the base index of a variable, all elements of the J column in the table, are negative, for J the index of a non basic with negative reduced cost. For example, we will consider the following linear programming problem:

unbounded lp

After standardizing the previous model, adding X3 and X4 as slack variables for constraint 1 and 2, respectively, the following initial table is obtained.

unbounded simplex

X2 is a non-basic variable with a negative reduced cost and therefore must be incorporated into the base. However it is not practical to estimate the feasibility criteria or the minimum quotient because the entries in the column X2 are negative or zero. This shows clearly that the problem is unbounded and with no optimal solution.

Moreover a linear model is infeasible (The domain of feasible solutions is empty and therefore has no supported solution) if the value of the objective function at the end of Phase I of the The Two-Phase Simplex Method is not zero.

  • Property 2: “If it has a feasible solution, it has a basic feasible solution”

A basic property of linear programming models is that in case of admitting optimal solution, it will necessarily find a vertex or segment on the boundary of the domain of feasible solutions.

In this context the implementation of the Simplex Method as an algorithmic resolution strategy; we seek to provide solutions that meets the Ax=b (Standard restrictions) and x≥0 criteria defining a (not necessarily optimal) basic feasible solution.

For example the following graph represents a linear model in two variables that show that points A, B, C, D and E are feasible basic solutions.

linear-programing-two-decis
graphical-linear-programmin

  • Property 3: “If the problem has an optimal solution, then it has an optimal basic feasible solution”

Continuing with the same example, vertex C is not only a basic feasible solution but also an optimal basic feasible solution. If all reduced costs (of non-basic variables: S1 and S3) are greater than or equal to zero and we are in presence of a basic feasible solution (X=100, S2=400, Y=350 all ≥0), we meet the stopping criterion of the Simplex Method and consequently the current basic feasible solution is optimal.

optimal-tableau-simplex-method

How to detect that a Linear Programming problem is unbounded with the Simplex Method

The Simplex Method is an algorithm that allows us to solve Linear Programming models that sometimes helps us identify exceptional cases with infinite optimal solutions or that the problem is unbounded. In the implementation of the Simplex Method, an unbounded problem is encountered when in any iteration there are any non-basic variables with a negative reduced cost and all elements in the column of this variable are negative or zero. That is, you cannot select a pivot (minimum quotient) to determine the variable to leave the base.

Consider the following Linear Programming model:

unbounded linear programming model

If we solve the model graphically we can see that this is unbounded. Note that the domain of feasible solutions (shaded area) is unbounded since it grows indefinitely in the direction of X2. The contours of the objective function grow at their highest rate in the direction of the vector gradient (X1,X2)=(4,6) indicating that it could be moved in that direction and indefinitely always intersect the domain of feasible solutions.

unbounded linear programming

How can we detect this situation using the Simplex Method? For one, we will carry this model to the standard form, including X3 and X4 as slack variables for constraint 1 and 2, respectively. This defines the following initial tableau for the algorithm:

simplex unbounded

Note that X2 is the non-basic variable with the most negative reduced cost and following this criterion, it should be the one that we enter into the base. However, it is not feasible to use the minimum quotient because the elements in the column X2 are negative or zero. In this instance we can already say that the problem is unbounded.

Note: You can verify that if we had selected X1 as the variable to enter to the base and one iteration of the Simplex Method, a similar conclusion will be reached as the one presented above.