Tag Archives: unbounded

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.

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.