Simplex method

The Primalsimplex process runs from one corner of a LP - polyhedron to another until no improvement is possible.

A simplex method (also simplex algorithm ) is an optimization method of the numerical analysis for the solution of linear optimization problems referred to also as a linear programming (LP). It solves such a problem exactly after a finite number of steps or determines its unsolvability or unlimitedness. The basic idea of ​​the simplex method was introduced in 1947 by George Dantzig ; since then, through numerous improvements, they have become the most important solution methods for linear optimization in practice. Simplex processes are pivot processes .

Although it has been possible to construct an example for each variant of the method in which the algorithm requires exponential runtime , a simplex algorithm usually runs faster than other methods in practice, although there are other competitive methods for solving individual linear programs, such as . B. Inner point method . The great advantage of a simplex algorithm, however, is that if the problem changes slightly - for example, adding an additional condition - it can perform a "warm start" from the last solution used and therefore usually only needs a few iterations for a new solution, while others Procedures have to start over. In addition, a simplex method takes advantage of the close connections between a linear optimization task and its dual task and basically solves both problems at the same time. Both properties are important in integer linear or non-linear optimization where a large number of similar linear tasks have to be solved in sequence.

The basic geometric idea of ​​the algorithm is to run from any corner of a polyhedron , which is defined by the linear optimization problem, along its edges to an optimal corner. The name of the procedure comes from the fact that the nonnegative linear combinations of the base columns describe a simplicial cone in each iteration . A namesake of this method called the Downhill Simplex method (Nelder and Mead 1965) is also based on a simplex , but is an iterative method for nonlinear optimization.

history

The foundations of linear optimization were laid in 1939 by the Russian mathematician Leonid Witaljewitsch Kantorowitsch in his book "Mathematical Methods in the Organization and Planning of Production". Shortly afterwards (1941) the American Frank L. Hitchcock (1875–1957) presented a work on a transport problem . In 1947 George Dantzig published the Simplex method, with which linear programs could be solved systematically for the first time. One of the first documented applications of the new method was the diet problem by George Stigler , whose goal was a food composition for soldiers that was as cost-effective as possible, which fulfilled certain minimum and maximum amounts of vitamins and other ingredients. At the time, nine people were working on the optimal solution of this linear program with nine inequalities and 77 variables , which together required around 120 man-days of arithmetic work. The American military, especially the US Air Force , which wanted to optimize military operations , initially showed interest in this work . In the following years, John von Neumann and Oskar Morgenstern developed the process further.

With the advent of computers in the mid-1950s, bigger problems could also be solved. Special variants of the simplex method were developed, such as the revised simplex method , which was very economical with the then scarce and expensive main memory . In 1954, William Orchard-Hays launched the first commercial implementation of this process. In the same year Carlton Lemke and EML Beale published the dual simplex method , which today - after further improvements - has developed into one of the standard methods for solving linear programs.

The theoretical complexity of the simplex method has long been unclear. It was not until 1972 that Victor Klee and George Minty constructed an example in which the algorithm runs all exponentially many vertices of a polyhedron, and thus showed the exponential running time of the process. Similar examples have so far been found for all known variants of the method.

From the 1970s onwards, the simplex algorithm - like other methods of linear optimization - benefited from algorithmic advances in numerical linear algebra , especially in solving large systems of linear equations . In particular, the development of numerically stable LR decompositions for thinly populated matrices contributed significantly to the success and spread of the simplex method.

From the mid-1970s to the early 1990s, the process was significantly improved through the development of new pivot strategies. Above all, the growing importance of integral linear optimization in the 1980s and the development of dual steepest edge pricing in the implementation of JJ Forrest and Donald Goldfarb (1992) made the dual simplex method a serious competitor for other solution methods. Conversely, this improvement of the dual simplex algorithm played a major role in the success of cutting plane methods and branch-and-cut for solving integer linear programs. In addition, new preprocessing methods in the 1990s ensured that ever larger LPs could be solved. Under the condition - which is almost always fulfilled in practical applications - that the occurring PCB matrices are sparsely populated , linear programs with several hundred thousand variables or inequalities can now be optimally solved within a few hours.

Basic idea

The simplex method is used to solve linear optimization problems , that is, the search for real variable values ​​that satisfy a system of linear inequalities and equations and thereby maximize or minimize a linear objective function. The starting point is the shape

(LP)  ${\displaystyle \max _{x\in \mathbb {R} ^{n}}\left\{c^{T}x\mid \;Ax\leq b,\;x\geq 0\right\}\,,}$

where is a matrix with real entries, the so-called objective function vector , and a column vector with nonnegative entries . The aim is to find a point that satisfies the linear inequality system and has the highest possible objective function value . ${\displaystyle A\in \mathbb {R} ^{m\times n}}$ ${\displaystyle c\in \mathbb {R} ^{n}}$ ${\displaystyle b\in \mathbb {R} ^{m}\!,~b\geq 0}$ ${\displaystyle b_{i}\geq 0}$ ${\displaystyle x}$ ${\displaystyle F(x)=c^{T}x}$

Any linear program can be converted into the form by simple transformations

(LP)  ${\displaystyle \max _{x\in \mathbb {R} ^{n}}\left\{c^{T}x\mid \;Ax\leq b,\;x\geq 0\right\}}$

are brought, in which the signs are of course still arbitrary . This is done as follows: ${\displaystyle b\in \mathbb {R} ^{m}}$

• A minimization problem can be transformed into a maximization problem by multiplying the objective function with . ${\displaystyle (-1)}$
• Inequalities can be written as. ${\displaystyle \textstyle {\sum _{j}A_{ij}x_{j}\geq b_{i}}}$ ${\displaystyle \textstyle {\sum _{j}(-A_{ij})x_{j}\leq -b_{i}}}$
• Existing equation groups can in Ungleichungsgruppen with are split. ${\displaystyle \forall i~~\textstyle {\sum _{j}A_{ij}x_{j}=b_{i}}}$ ${\displaystyle \forall i~~\textstyle {\sum _{j}A_{ij}x_{j}\leq b_{i}}}$ ${\displaystyle \textstyle {\sum _{j}{\big (}-\sum _{i}A_{ij}{\big )}x_{j}\leq -b_{i}}}$
• Variable groups  with any value range can be replaced by an additional variable and by non-negative variables . ${\displaystyle x_{j}}$ ${\displaystyle x_{j}=u_{j}-w}$ ${\displaystyle \forall j~~u_{j}\geq 0,~~w\geq 0}$

In contrast to these transformations, the always required start condition can only be achieved by solving an auxiliary task in a so-called "phase 1"; This auxiliary task is basically just as time-consuming as the actual optimization. ${\displaystyle b\geq 0}$

Geometrically, the set of feasible solutions, i.e. the set of points with nonnegative coordinates that satisfy the linear system of inequalities , can be interpreted as a convex polyhedron (multi-dimensional polygon) , the dimension of which is limited by the number of variables. The aim is a point in having a very high objective value to be found. Clearly, this corresponds to shifting the hyperplane as far as possible in the direction of the vector so that it just touches the polyhedron. All points of contact are then optimal. ${\displaystyle Ax\leq b}$ ${\displaystyle P}$ ${\displaystyle x}$ ${\displaystyle P}$ ${\displaystyle F(x)=c^{T}x}$ ${\displaystyle c^{T}x=0}$ ${\displaystyle c}$

There are three options for the set of feasible solutions:

1. the LP has no admissible solutions, i.e. i.e., the polyhedron is empty (e.g. ). ${\displaystyle \max\{x\;|\;x\leq 1,\;x\geq 2\ \}}$
2. the LP is unlimited, i.e. That is, there are solutions with an arbitrarily high objective function value (e.g. ). ${\displaystyle \max\{x\;|\;x\geq 0\}}$
3. there is exactly one or an infinite number of optimal solutions, which then all lie on a common side surface ( corner , edge, ...) of the polyhedron . ${\displaystyle P}$

It can be shown that there is always an optimal corner if the optimization problem has feasible solutions at all and is bounded. When looking for optimal solutions, you can restrict yourself to the corners of the polyhedron, of which there can be very many.

The clear basic idea of ​​the simplex method now consists of gradually moving from one corner of the polyhedron to an adjacent corner with a better objective function value until there are no better neighbors. Since the linear optimization is a convex optimization problem , the locally optimal corner found in this way is then also globally optimal; In other words , there is no other corner with a better objective value. ${\displaystyle P}$

running time

The number of vertices of a polyhedron can be exponential in the number of variables and inequalities. For example, the -dimensional unit cube can be described by linear inequalities, but has corners. In 1972 Klee and Minty constructed a distorted unit cube, the so-called Klee-Minty cube , in which the variant of the simplex method presented by Dantzig actually visited all of these corners. Similar examples have been found so far for all row and column selection rules. This means that the simplex algorithm in all previously known variants has exponential running time in the worst case. ${\displaystyle n}$ ${\displaystyle 2n}$ ${\displaystyle 2^{n}}$

With degenerate linear programs, as they often occur in practice, so-called cycles can occur in which the simplex method repeatedly looks at the same corner and therefore does not terminate. However, this can be prevented by using the lexicographical row selection rule or by deliberate numerical perturbations.

From a theoretical point of view, the simplex method is therefore, for example, inferior to the interior point method with a polynomial running time . From a practical point of view, however, it has proven to be faster in many cases. The greatest advantage of the simplex algorithm over other methods, however, is that it allows a "warm start" in the event of small changes to the input data in the course of the algorithm, i.e. using the last calculated base as the starting point for a few further (primal or dual) iterations, while, for example, interior point processes must start from scratch in such a case. This case occurs very often when a large number of similar linear programs have to be solved in succession, for example in the context of cutting plane methods , branch-and-bound or branch-and-cut .

In practice, the running time of the simplex method often depends essentially linearly on the number of lines. In fact, Borgwardt and others showed in the 1980s that such cases as the Klee-Minty cube are extremely rare and that some variants of the simplex algorithm only require an average of polynomial running times under certain assumptions about the input . However, it is still unclear whether there is a variant with polynomial runtime for all instances.

Mathematical description

The simplex process consists of two phases:

• Phase I determines a valid starting solution or determines that the problem has no solution,
• Phase II continues to improve an existing solution until it is no longer possible to improve the objective function or the unlimitedness of the problem is determined.

The Big M method offers a possibility to combine both phases, i.e. to use the simplex, even if there is initially no admissible starting solution.

Determination of a starting solution (phase I)

First, a permissible starting solution must be calculated before you can start phase II. One possibility for this is to introduce an artificial variable for each line and then consider the following linear program: ${\displaystyle i}$ ${\displaystyle z_{i}}$

(LP1) ${\displaystyle \min \left\{\left.\sum _{i=1}^{m}z_{i}\;\right|\;Ax+z=b,\;x,z_{1},\cdots ,z_{m}\geq 0\right\}~.}$

In an optimal solution to this auxiliary problem, the artificial variables are as small as possible, and they always have to remain non-negative. The original problem (LP) has a feasible solution if and only if there is a solution to the auxiliary problem with which no artificial variables are used. ${\displaystyle z=0}$

The auxiliary problem (LP1) has a simple allowable starting solution, namely . In addition, for every admissible solution to the auxiliary problem , the objective function is limited by . This linear program has an optimal solution that can be determined on the basis of the initial solution with phase II of the auxiliary problem. We find this an optimal solution with , is obviously an allowable starting solution to the original problem (LP) can be started with its phase II. If this does not succeed, the initial problem cannot be solved and one can stop. ${\displaystyle b\geq 0}$ ${\displaystyle (x,z)=(0,b)}$ ${\displaystyle z\leq b}$ ${\displaystyle \textstyle \sum _{i=1}^{m}b_{i}}$ ${\displaystyle (0,b)}$ ${\displaystyle (x^{*},z^{*})}$ ${\displaystyle z^{*}=0}$ ${\displaystyle x^{*}}$

Determination of an optimal solution (phase II)

Phase II is an iterative procedure that tries in each step to construct a new solution with a better objective function value from a feasible solution until this is no longer possible. This essentially corresponds to the repeated solution of a system of linear equations using the Gaussian elimination method . In doing so, it may also be possible to determine the unlimited nature of the optimization problem. To explain this phase, it is necessary to define some terms.

Bases, basic solutions and corners

→ Main article : Permissible basic solution

In phase II of the simplex procedure, the concept of the basis plays an essential role. A base of is a subset of the columns of that form a regular sub-matrix . is displayed as an index vector over the columns of . The variables that belong to the basic columns, i.e. are contained in , are called basic variables , the other non- basic variables . The basic solution for a given basis is the unique vector whose basic variables result as and whose non- basic variables all have the value 0 (i.e. and ). Such a basic solution is therefore a feasible solution of the equation system with at most non-zero entries. In the case that all components are of nonnegative, there is also a feasible solution of (LP), i.e. a point of the polyhedron . ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A_{B}}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle x}$ ${\displaystyle A_{B}^{-1}b}$ ${\displaystyle A_{B}\cdot x_{B}=b}$ ${\displaystyle x_{N}=0}$ ${\displaystyle Ax=b}$ ${\displaystyle m}$ ${\displaystyle x_{B}}$ ${\displaystyle x\geq 0}$ ${\displaystyle P}$

One can show that every feasible basic solution corresponds to a corner ( extreme point ) of the polyhedron and vice versa. A basic solution is not called degenerate (not degenerate) if it has exactly non-zero basic entries, i.e. if it holds. In this case there is a clear associated basis. If all basic solutions are not degenerate, there is a bijective mapping between bases of the matrix and corners of the polyhedron . ${\displaystyle m}$ ${\displaystyle x_{B}>0}$ ${\displaystyle A}$ ${\displaystyle P}$

If, on the other hand , a basic solution is degenerate , it has fewer than non-zero entries and can belong to several bases. In this case, each base of the matrix defines exactly one corner of the polyhedron , but not the other way around. This case occurs when a vertex is defined by more than inequalities, which is almost always the case with practical planning problems. ${\displaystyle m}$ ${\displaystyle A}$ ${\displaystyle P}$ ${\displaystyle n}$

Iterative simplex steps

Phase II tries iteratively in every exchange step , from an existing basic solution, such as For example, it was determined in phase I to construct a new basic solution with at least as good an objective function value by removing a basic variable from the basis and instead adding a previous non-basic variable to the basis. This is repeated until no more improving exchange is possible.

In this phase, at the beginning of each iteration, there is a so-called simplex table for the current base , in which the calculations are carried out. It substantially corresponds to the system of linear equations ,   after a basis transformation in the current basis. ${\displaystyle B}$ ${\displaystyle [A\;I\,]\,x=b\,}$ ${\displaystyle [c^{T}\;0]\,x=z}$

Simplex tableau

There are different possibilities for the formulation of the simplex table; the version presented here is based on a lecture script by Martin Grötschel . Each simplex step starts from a feasible basis . At the beginning of the step, the associated simplex tableau has the following form: ${\displaystyle B}$

${\displaystyle \left[\left.{\begin{matrix}{\bar {A}}&I&0\\{\bar {c}}&0&1\end{matrix}}\;\right|\;{\begin{matrix}{\bar {b}}\\{\bar {f}}\end{matrix}}\;\right]}$

To simplify the representation, the columns have been rearranged so that all non-base columns are on the left and all base columns are on the right.  is the -dimensional identity matrix . The -dimensional matrix and the rest of the above entries are defined by ${\displaystyle I}$ ${\displaystyle (m\!\times \!m)}$ ${\displaystyle (m\!\times \!n)}$ ${\displaystyle {\bar {A}}}$

${\displaystyle {\bar {A}}=A_{B}^{-1}A_{N}}$

${\displaystyle {\bar {b}}=A_{B}^{-1}b}$

${\displaystyle {\bar {c}}=c_{N}^{T}-c_{B}^{T}A_{B}^{-1}A_{N}}$

${\displaystyle {\bar {f}}=c_{B}^{T}A_{B}^{-1}b}$

It is

• ${\displaystyle A_{B}}$the regular sub-matrix of , which consists of the columns of the current base , ${\displaystyle A}$ ${\displaystyle B}$
• ${\displaystyle A_{N}}$the (mostly non-square) sub-matrix of , which consists of the non-base columns, ${\displaystyle A}$
• ${\displaystyle c_{B}}$the parts of the objective function vector that consist of the base columns, and ${\displaystyle c}$
• ${\displaystyle c_{N}}$the parts of the objective function vector that consist of the non-base columns. ${\displaystyle c}$

The right-hand side contains the values ​​of the basic variables of the basic solution that belongs to; is the objective function value of this basic solution. At the beginning of phase I, the variables form a permissible basis with the identity matrix as the basic matrix and the associated basic solution . Therefore, at the beginning on the right side there is simply the vector . ${\displaystyle {\bar {b}}}$ ${\displaystyle B}$ ${\displaystyle {\bar {f}}}$ ${\displaystyle z_{i}}$ ${\displaystyle (x,z)=(0,b)}$ ${\displaystyle b}$

The entries of the vector are called reduced costs of the non-basic variables. The value indicates the improvement in the objective function when the variable is increased by one unit. If all reduced cost coefficients are negative or 0 at the beginning of a simplex step, the current base and the associated base solution are therefore optimal, since the inclusion of a previous non-base variable in the base would worsen the objective function value. If, on the other hand, there are non-base variables with positive reduced costs, one of them is added to the base in the next simplex step and another variable is removed from the base. If the new variable can be increased within the constraints , the objective function value improves. ${\displaystyle {\bar {c}}}$ ${\displaystyle {\bar {c}}_{j}}$ ${\displaystyle x_{j}}$ ${\displaystyle Ax=b}$

A single simplex step

For the actual simplex step, one now selects a column of the non- basic variable to be inserted and a row of the basic variable to be removed from the base. Be the (matrix) elements of the current simplex tableau. Then the pivot element of the simplex tableau is called. The column is called the pivot column , the row is called the pivot row . An exchange step corresponds exactly to a step in solving a system of linear equations, in which the pivot line is solved for the variable and then inserted into the remaining equations. In the case of an exchange step, the new simplex tableau is calculated as follows: ${\displaystyle s}$ ${\displaystyle r}$ ${\displaystyle {\bar {a}}_{ij}}$ ${\displaystyle {\bar {a}}_{rs}}$ ${\displaystyle s}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle x_{s}}$ ${\displaystyle x_{s}}$

Pivot element:

(1) ${\displaystyle \qquad \;{\bar {a}}_{rs}:={\frac {1}{{\bar {a}}_{rs}}}}$

Pivot line for not equal : ${\displaystyle j}$ ${\displaystyle s}$

(2) ${\displaystyle \qquad \;{\bar {a}}_{rj}:={\frac {{\bar {a}}_{rj}}{{\bar {a}}_{rs}}}}$

(3) ${\displaystyle \qquad \;{\bar {b}}_{r}\;:={\frac {{\bar {b}}_{r}}{{\bar {a}}_{rs}}}}$

Pivot column for not equal : ${\displaystyle i}$ ${\displaystyle r}$

(4a) ${\displaystyle \qquad {\bar {a}}_{is}:=-{\frac {{\bar {a}}_{is}}{{\bar {a}}_{rs}}}}$

(4b) ${\displaystyle \qquad {\bar {c}}_{s}\;:=-{\frac {{\bar {c}}_{s}}{{\bar {a}}_{rs}}}}$

Remaining elements of the matrix and reduced costs:

(5a) ${\displaystyle \qquad {\bar {a}}_{ij}:={\bar {a}}_{ij}-{\frac {{\bar {a}}_{is}{\bar {a}}_{rj}}{{\bar {a}}_{rs}}}}$

(5b) ${\displaystyle \qquad {\bar {c}}_{j}\;:={\bar {c}}_{j}-{\frac {{\bar {c}}_{s}{\bar {a}}_{rj}}{{\bar {a}}_{rs}}}}$

Right side:

(6) ${\displaystyle \qquad \;{\bar {b}}_{i}\;:={\bar {b}}_{i}-{\frac {{\bar {b}}_{r}{\bar {a}}_{is}}{{\bar {a}}_{rs}}}}$

These calculation steps correspond to the application of the Gaussian elimination method in order to transform the pivot column s in the tableau into a unit vector. As a result, the inverse matrix for the new basis is not completely recalculated, but is constructed by modifying the old basis inverse . ${\displaystyle A_{B'}^{-1}}$ ${\displaystyle B'}$ ${\displaystyle A_{B}^{-1}}$

A simplex step, which starts from a non-degenerate basic solution, leads in any case to a new basic solution and thus also to a new vertex of the polyhedron with a better objective function value. If, on the other hand, the basic solution has degenerated, it can happen that after the simplex step the new basis belongs to the same basic solution and thus also to the same corner, so that the objective function value does not change. If the pivot elements are chosen carelessly, so-called cycles can occur in which the same bases are visited again and again, so that the algorithm runs in an endless loop . However, this can be prevented, for example, by a suitable selection of the pivot line . In practice, another method of dealing with cycles is an intentional perturbation (numerical perturbation) of the data, which is calculated out again after a few iterations when the algorithm has left the relevant corner.

There are usually several options for choosing the pivot element. The method originally proposed by Dantzig selects one of the columns with the greatest reduced cost value and any row in which, after the simplex step, a permissible (especially non-negative) basic solution is created again. To do this, for a given pivot column, a pivot line must be selected for which the minimum ${\displaystyle s}$

${\displaystyle \lambda :=\min {\Bigl \{}\left.{\frac {{\bar {b}}_{i}}{{\bar {a}}_{is}}}\;\right|\;i=1,\ldots ,m,\,{\bar {a}}_{is}>0{\Bigr \}}}$

Is accepted. If all entries in column are negative, the optimization problem is unlimited, since one could construct solutions with arbitrarily good objective function value. In that case you can stop. ${\displaystyle s}$

Usually there are several columns with positive reduced costs as well as several rows where the minimum is assumed, so that there is a choice. Since the choice of the pivot element can have a major influence on the computing time, numerous improved pivot strategies have been developed over the past 60 years compared to the textbook version (see below ). ${\displaystyle \lambda }$

Sample calculation

Illustration of the example (explanation see text)

Using a simple example for production planning with two variables, the solution is to be shown step by step. In this simple case, an optimal solution is easy to find. Real problems, on the other hand, can easily consist of several hundred thousand variables and constraints, so that in most cases the existence of a solution or the value of an optimal solution cannot be seen immediately.

A company makes two different products. There are three machines A, B, C available. Machine A has a maximum monthly running time (capacity) of 170 hours, machine B of 150 hours and machine C of 180 hours. A unit of measure (MU) of product 1 provides a contribution margin of 300 euros, whereas a unit of measure of product 2 delivers 500 euros. If you manufacture 1 ME of product 1, you need 1 hour for machine A and an additional 1 hour for machine B. 1 ME of product 2 occupies 2 hours of machine A, 1 hour of machine B and 3 hours of machine C.

The following conditions are obtained from this:

${\displaystyle {\begin{matrix}1\cdot x_{1}&+&2\cdot x_{2}&\leq &170&{\mbox{(Maschine A)}}\\[2pt]1\cdot x_{1}&+&1\cdot x_{2}&\leq &150&{\mbox{(Maschine B)}}\\[2pt]0\cdot x_{1}&+&3\cdot x_{2}&\leq &180&{\mbox{(Maschine C)}}\\[2pt]\end{matrix}}}$

${\displaystyle x_{1}\geq 0,\ x_{2}\geq 0}$

The company wants to maximize the contribution margin : ${\displaystyle z\,}$

${\displaystyle \max \;z=300\cdot x_{1}+500\cdot x_{2}}$

${\displaystyle z\,}$ is therefore the so-called objective function value.

Any fixed costs are independent of the production volume and can therefore simply be deducted from the total contribution margin at the end of the calculation in order to maintain the profit.

Conversion into equations

For the simplex method, the inequalities are first converted into equations. For this purpose, so-called slip variables , and  , which represent the unused times of the individual machines, are introduced. Obviously, the slip variables must not be negative. This allows the problem to be formulated in such a way that one exposes the slack variables with respect to the original variables. Such a standardized system of equations is called in the English dictionary (named by V. Chvátal ): ${\displaystyle y_{A}\,}$ ${\displaystyle y_{B}\,}$ ${\displaystyle y_{C}\,}$

Maximize the objective function  under the constraints: ${\displaystyle z\,}$

${\displaystyle {\begin{matrix}z&=&~~~~~~0&+~300\,x_{1}&+~500\,x_{2}\\[3pt]y_{A}&=&~~~170&-~~~~1\,x_{1}&-~~~~2\,x_{2}\\[2pt]y_{B}&=&~~~150&-~~~~1\,x_{1}&-~~~~1\,x_{2}\\[2pt]y_{C}&=&~~~180&+~~~~0\,x_{1}&-~~~~3\,x_{2}\end{matrix}}}$

${\displaystyle x_{1}\geq 0,\ x_{2}\geq 0}$

${\displaystyle y_{A}\geq 0,\ y_{B}\geq 0,\ y_{C}\geq 0}$

The above equations can be transferred to the simplex table described above :

      -----------------------------
      |  x1     x2   | rechte Seite
  ---------------------------------
  -z  |  300   500  |      0
  ---------------------------------
  yA  |   1      2   |      170  = b1
  yB  |   1      1   |      150  = b2
  yC  |   0      3   |      180  = b3

The non- basic variables are in the header with the value 0, while the basic variables are in the first column. The top line - the equation for the objective function - contains the objective function coefficients , i.e. 300 and 500. On the right-hand side is the current basic solution, which is exactly what is in this case . The top line on the right-hand side shows the negative of the objective function value for the current basic solution, i.e. the negative of the total contribution margin in the example. This is currently 0 because nothing is being produced. ${\displaystyle x_{1},\,x_{2}}$ ${\displaystyle y_{i}\,}$ ${\displaystyle c_{i}\,}$ ${\displaystyle b\,}$

Determination of a permissible starting solution (phase I)

Since the constant values ​​of the above system of equations are not negative, the independent variables of the system of equations (non-base variables) can be set to zero and thus a trivial, permissible solution can be given, with which phase II can be started directly:

${\displaystyle x_{1}=0,\ x_{2}=0\qquad y_{A}=170,\ y_{B}=150,\ y_{C}=180}$

The variables form a valid basis , the basic matrix of which is the identity matrix. So the associated basic solution is . This solution corresponds to the case that nothing is produced ( ). The remaining capacity of the machines, which is indicated by the values ​​of , is their total capacity (170, 150 and 180), since the machines are not used. ${\displaystyle y_{i}\,}$ ${\displaystyle B\,}$ ${\displaystyle A_{B}\,}$ ${\displaystyle A_{B}^{-1}b=b}$ ${\displaystyle x_{i}=0\,}$ ${\displaystyle y_{i}\,}$

Improvement of the initial solution (phase II)

Since the just calculated initial solution is unsatisfactory, an attempt will now be made in phase II to find better permissible solutions.

Selection of a pivot column and row

In a simplex iteration , a basic variable is exchanged for one of the independent variables. Non-base variables with a positive objective function coefficient come into question, as their inclusion in the base can improve the objective function value. This variable should be increased until one or more of the base variables hit 0. Any of these basic variables then leaves the basic and is exchanged for the non-basic variable.

Variable  has the positive objective function coefficient 300; by increasing it, the objective function can be increased; it is therefore a possible base-entering pivot variable. As long as is  the only increased non-base variable, this increase should  be restricted by the following conditions: ${\displaystyle x_{1}\,}$ ${\displaystyle z\,}$ ${\displaystyle x_{1}\,}$ ${\displaystyle {\bar {x}}_{1}\,}$

${\displaystyle {\begin{matrix}0\leq {\bar {y}}_{A}=170-1\,{\bar {x}}_{1}&\quad {\text{(zu Basisvariable }}y_{A}{\text{)}}\\[2pt]0\leq {\bar {y}}_{B}=150-1\,{\bar {x}}_{1}&\quad {\text{(zu Basisvariable }}y_{B}{\text{)}}\\[2pt]\end{matrix}}}$

In other words,

${\displaystyle {\bar {x}}_{1}\leq {\frac {170}{1}},\quad {\bar {x}}_{1}\leq {\frac {150}{1}}}$  or  ${\displaystyle {\bar {x}}_{1}\leq \min {\Bigl \{}{\frac {170}{1}},\ {\frac {150}{1}}{\Bigr \}}=\min\{170,150\}=150}$

The first of the basic variables, which in this case hits zero, is obtained from the quotient  and is . This is the variable that might have to  be exchanged for. The new value of the objective function would then be . ${\displaystyle 150/1\,}$ ${\displaystyle y_{B}\,}$ ${\displaystyle x_{1}\,}$ ${\displaystyle {\bar {z}}=300\cdot (150/1)=45000}$

Variable also  has a positive objective function coefficient with 500, so it is also a possible non-basic variable. Following the above procedure, we get ${\displaystyle x_{2}\,}$

${\displaystyle {\begin{matrix}0\leq {\bar {y}}_{A}=170-2\,{\bar {x}}_{2}&\quad {\text{(zu Basisvariable }}y_{A}{\text{)}}\\[2pt]0\leq {\bar {y}}_{B}=150-1\,{\bar {x}}_{2}&\quad {\text{(zu Basisvariable }}y_{B}{\text{)}}\\[2pt]0\leq {\bar {y}}_{C}=180-3\,{\bar {x}}_{2}&\quad {\text{(zu Basisvariable }}y_{C}{\text{)}}\\[2pt]\end{matrix}}}$

and thus

${\displaystyle {\bar {x}}_{2}\leq \min {\Bigl \{}{\frac {170}{2}},\ {\frac {150}{1}},\ {\frac {180}{3}}{\Bigr \}}=\min\{85,150,60\}=60}$

The minimum quotient  belongs to the basic variable  . The new value of the objective function would be . ${\displaystyle (180/3)\,}$ ${\displaystyle y_{C}\,}$ ${\displaystyle {\bar {z}}=500\cdot (180/3)=30000}$

In order to increase the objective function in this step, it is therefore best to choose the first case and expose the independent variable  instead of the base variable  . ${\displaystyle x_{1}\,}$ ${\displaystyle y_{B}\,}$

Implementation of an exchange step

With the exchange step , the basic variable is exchanged for the non- basic variable . First we reveal in the equation for the independent unknown , ${\displaystyle y_{B}\,}$ ${\displaystyle x_{1}\,}$ ${\displaystyle y_{B}\,}$ ${\displaystyle x_{1}\,}$

${\displaystyle {\begin{matrix}y_{B}~=~150-1\,x_{1}-1\,x_{2}\qquad \qquad \qquad \qquad \qquad \\[3pt]\Longrightarrow \quad x_{1}~=~150-1\,y_{B}-1\,x_{2}\end{matrix}}}$

and then we replace in the remaining equations for the expression thus obtained: ${\displaystyle x_{1}\,}$

${\displaystyle {\begin{matrix}z&~=~&~~~~0&+~300\,(150-1\,y_{B}-1\,x_{2})&+~500\,x_{2}\\[2pt]y_{A}&~=~&~170&-~~~~1\,(150-1\,y_{B}-1\,x_{2})&-~~~~2\,x_{2}\\[2pt]y_{C}&~=~&~180&+~~~~0\,(150-1\,y_{B}-1\,x_{2})&-~~~~3\,x_{2}\end{matrix}}}$

This leads to the transformation rules described above for the simplex tableau after the pivot element . If the row is occupied by and the column is occupied by , then the new system of equations is ${\displaystyle a_{21}=1}$ ${\displaystyle x_{1}\,}$ ${\displaystyle y_{B}\,}$ ${\displaystyle y_{B}\,}$ ${\displaystyle x_{1}\,}$

${\displaystyle {\begin{matrix}z&=&45000&-~300\,y_{B}&+~200\,x_{2}\\[2pt]y_{A}&=&~~~~20&+~~~~1\,y_{B}&-~~~~1\,x_{2}\\[2pt]x_{1}&=&~~~150&-~~~~1\,y_{B}&-~~~~1\,x_{2}\\[2pt]y_{C}&=&~~~180&+~~~~0\,y_{B}&-~~~~3\,x_{2}\end{matrix}}}$

The unknown  has moved to the base, the now independent unknown  is a non-base variable and appears in the header. ${\displaystyle x_{1}\,}$ ${\displaystyle y_{B}\,}$

This solution means:  MUs of product 1 (equation with exposed ) are produced. Nothing is produced from product 2 ( is a non-basis variable). The company thus achieved a total contribution margin of 45,000 euros. Machine A stands  idle hours per month (it only runs 150 of the 170 possible hours). Machine B has no idle time. Machine C stands  still for hours, which means it is not needed at all. This also results directly from the task: machine C is only required for the production of product 2. Since this is not being manufactured, machine C is not yet needed. ${\displaystyle 150\,}$ ${\displaystyle x_{1}\,}$ ${\displaystyle x_{2}=0\,}$ ${\displaystyle 20\,}$ ${\displaystyle 180\,}$

The new simplex tableau belonging to the above system of equations is

      -----------------------------
      |  yB     x2   | rechte Seite
  ---------------------------------
  -z  |  -300   200  |      -45000
  ---------------------------------
  yA  |  -1      1   |       20  = b1
  x1  |   1      1   |      150  = b2
  yC  |   0      3   |      180  = b3

The entries in the new Simplex panel can be calculated using the above formulas.

Repeat the simplex steps

Since the objective function in the resulting simplex tableau still contains a positive coefficient, the solution can still be improved. This is done using a further simplex iteration. When selecting the pivot element, only the unknown comes into question, since the objective function coefficient is only positive here. The base variable of the pivot results from ${\displaystyle x_{2}\,}$

${\displaystyle {\begin{matrix}0\leq {\bar {y}}_{A}=~20-1\,{\bar {x}}_{2}&\quad {\text{(zu Basisvariable }}y_{A}{\text{)}}\\[2pt]0\leq {\bar {x}}_{1}=150-1\,{\bar {x}}_{2}&\quad {\text{(zu Basisvariable }}x_{1}{\text{)}}\\[2pt]0\leq {\bar {y}}_{C}=180-3\,{\bar {x}}_{2}&\quad {\text{(zu Basisvariable }}y_{C}{\text{)}}\\[2pt]\end{matrix}}}$

and thus

${\displaystyle {\bar {x}}_{2}\leq \min \left\{{\frac {20}{1}},\ {\frac {150}{1}},\ {\frac {180}{3}}\right\}=\min\{20,150,60\}=20}$

Line is the only base unknown that can be used for a pivot. The basic variable is exchanged for the non- basic variable ; the pivot element is . With the same conversions as above you get a new system of equations ${\displaystyle y_{A}\,}$ ${\displaystyle y_{A}\,}$ ${\displaystyle x_{2}\,}$ ${\displaystyle 1\,}$

${\displaystyle {\begin{matrix}z&=&49000&-~100\,y_{B}&-~200\,y_{A}\\[2pt]x_{2}&=&~~~~20&+~~~~1\,y_{B}&-~~~~1\,y_{A}\\[2pt]x_{1}&=&~~~130&-~~~~2\,y_{B}&+~~~~1\,y_{A}\\[2pt]y_{C}&=&~~~120&-~~~~3\,y_{B}&+~~~~3\,y_{A}\end{matrix}}}$

or a new simplex panel

      -----------------------------
      |  yB     yA   | rechte Seite
  ---------------------------------
  -z  | -100   -200  |   -49000
  ---------------------------------
  x2  |  -1      1   |       20
  x1  |   2     -1   |      130
  yC  |   3     -3   |      120

Since the objective function no longer contains any positive coefficients, an optimal solution has been achieved. There are  ME of product 1 and  made ME product. 2 The company thus achieved a total contribution margin of 49,000 euros. Machine A and machine B are fully utilized. Machine C runs for 60 hours and therefore still has an unused capacity of hours. ${\displaystyle 130\,}$ ${\displaystyle 20\,}$ ${\displaystyle y_{C}=120\,}$

Fractional entries

The above example was solved in algebraic notation by exposing the base variables in the equation system with respect to the remaining, independent variables. To avoid rounding errors, you can work with fractions and choose a common denominator for the entire system of equations (that this denominator was always above is a coincidence). In order to find the common denominator for the overall system in every step, we do not have to analyze the entries additionally. If the starting system is an integer (which can usually be achieved by expansion), the following rule applies: ${\displaystyle 1\,}$

• The numerator of the chosen pivot element is a common denominator for the following system

If we multiply the new tableau entries by this common denominator, we always get integer numerators. When calculating this numerator for the new tableau entries, it is then divided by the old denominator without checking , whereby the result must be an integer.

As an example of this approach, we solve the same task as above with Dantzig's pivot selection ; The incoming pivot variable is chosen as the one with the largest objective function coefficient:

${\displaystyle {\begin{matrix}z&=&(&~~~~~~~0&+~300\,x_{1}&+~500\,x_{2}&)~/~1\\[2pt]y_{A}&=&(&~~~~170&-~~~~~\,x_{1}&-~~~~2\,x_{2}&)~/~1\\[2pt]y_{B}&=&(&~~~~150&-~~~~~\,x_{1}&-~~~~~\,x_{2}&)~/~1\\[2pt]y_{C}&=&(&~~~~180&+~~~~0\,x_{1}&-~~~~\mathbf {3\,x_{2}} &)~/~1\end{matrix}}}$

The objective function can be increased by increasing the independent variable ; is the first of the basic variables that hits zero in this case . Consequently,  instead of uncovering , you get the following system with : ${\displaystyle x_{2}\,}$ ${\displaystyle z\,}$ ${\displaystyle y_{C}\,}$ ${\displaystyle x_{2}\,}$ ${\displaystyle y_{C}\,}$ ${\displaystyle {\bar {z}}=30000}$

${\displaystyle {\begin{matrix}z&=&(&~90000&+~900\,x_{1}&-~500\,y_{C}&)~/~3\\[2pt]y_{A}&=&(&~~~~150&-~~~~\mathbf {3\,x_{1}} &+~~~~2\,y_{C}&)~/~3\\[2pt]y_{B}&=&(&~~~~270&-~~~~3\,x_{1}&+~~~~~\,y_{C}&)~/~3\\[2pt]x_{2}&=&(&~~~~180&+~~~~0\,x_{1}&-~~~~~\,y_{C}&)~/~3\end{matrix}}}$

If you increase the independent variable , you increase the objective function; is the first of the base variables to hit zero . Consequently,  instead of exposing, you get the following system : ${\displaystyle x_{1}\,}$ ${\displaystyle y_{A}\,}$ ${\displaystyle x_{1}\,}$ ${\displaystyle y_{A}\,}$ ${\displaystyle {\bar {z}}=45000}$

${\displaystyle {\begin{matrix}z&=&(&135000&-~900\,y_{A}&+~100\,y_{C}&)~/~3\\[2pt]x_{1}&=&(&~~~~150&-~~~~3\,y_{A}&+~~~~2\,y_{C}&)~/~3\\[2pt]y_{B}&=&(&~~~~120&+~~~~3\,y_{A}&-~~~~~\mathbf {\,y_{C}} &)~/~3\\[2pt]x_{2}&=&(&~~~~180&+~~~~0\,y_{A}&-~~~~~\,y_{C}&)~/~3\end{matrix}}}$

If you increase the independent variable , you increase the objective function; is the first of the base variables to hit zero . Consequently,  instead of exposing, you get the following system : ${\displaystyle y_{C}\,}$ ${\displaystyle y_{B}\,}$ ${\displaystyle {y_{C}\,}}$ ${\displaystyle y_{B}\,}$ ${\displaystyle {\bar {z}}=49000}$

${\displaystyle {\begin{matrix}z&=&(&~49000&-~200\,y_{A}&-~100\,y_{B}&)~/~1\\[2pt]x_{1}&=&(&~~~~130&+~~~~~\,y_{A}&-~~~~2\,y_{B}&)~/~1\\[2pt]y_{C}&=&(&~~~~120&+~~~~3\,y_{A}&-~~~~3\,y_{B}&)~/~1\\[2pt]x_{2}&=&(&~~~~~20&-~~~~~\,y_{A}&+~~~~~\,y_{B}&)~/~1\end{matrix}}}$

The objective function has value and can no longer be increased; the solution is as above . We also observe that Dantzig's pivot selection took one more step to reach the solution compared to the alternative initially selected. ${\displaystyle {\bar {z}}=49000\,}$ ${\displaystyle {\bar {x}}_{1}=130,\,{\bar {x}}_{2}=20}$

Exemplary solution in Java

The simplex method is already available as a software implementation in numerous software libraries. An example is e.g. B. the Java package org.apache.commons.math3.optim from Apache Commons ™ . The function to be maximized is defined as LinearObjectiveFunction (line: 22) and corresponds to the contribution margin from the example above. The conditions are given as LinearConstraint (lines: 24–26). The SimplexSolver (line: 28) needs the number of maximum iterations, the function to be maximized, the conditions and the information whether a maximum or minimum is being sought (line: 29). In addition, the SimplexSolver receives the information with the NonNegativeConstraint that values ​​greater than 0 are being sought for the coordinates . ${\displaystyle x_{1},x_{2}}$

 1 package SimplexAlgorithmExample;
 2 
 3 import java.util.ArrayList;
 4 import java.util.Arrays;
 5 import java.util.Collection;
 6 
 7 import org.apache.commons.math3.optim.MaxIter;
 8 import org.apache.commons.math3.optim.PointValuePair;
 9 import org.apache.commons.math3.optim.linear.LinearConstraint;
10 import org.apache.commons.math3.optim.linear.LinearConstraintSet;
11 import org.apache.commons.math3.optim.linear.LinearObjectiveFunction;
12 import org.apache.commons.math3.optim.linear.NonNegativeConstraint;
13 import org.apache.commons.math3.optim.linear.Relationship;
14 import org.apache.commons.math3.optim.linear.SimplexSolver;
15 import org.apache.commons.math3.optim.nonlinear.scalar.GoalType;
16 
17 
18 public class SimplexAlgorithmExample
19 {
20     public static void main(String[] args)
21     {
22     	LinearObjectiveFunction oFunc = new LinearObjectiveFunction(new	 double[] {300, 500}, 0);
23     	Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
24     	constraints.add(new LinearConstraint(new double[] {1, 2}, Relationship.LEQ, 170));
25     	constraints.add(new LinearConstraint(new double[] {1, 1}, Relationship.LEQ, 150));
26     	constraints.add(new LinearConstraint(new double[] {0, 3}, Relationship.LEQ, 180));
27 
28     	SimplexSolver solver = new SimplexSolver();
29     	PointValuePair solution = solver.optimize(new MaxIter(100), oFunc, new LinearConstraintSet(constraints), GoalType.MAXIMIZE, new NonNegativeConstraint(true));
30     	System.out.println(Arrays.toString(solution.getPoint()) + " : " + solution.getSecond());
31     }
32 }

Dual information in the tableau

The information for solving the dual linear program belonging to the linear program (LP) can also be taken from the simplex table . For a given base can be next to the associated Primallösung which is in the right column of the panel, a dual solution calculated. These two vectors and always meet the condition ${\displaystyle B}$ ${\displaystyle x={\bar {b}}=A_{B}^{-1}b}$ ${\displaystyle \pi ^{T}=c_{B}^{T}A_{B}^{-1}}$ ${\displaystyle x}$ ${\displaystyle \pi }$

${\displaystyle \pi ^{T}b=c^{T}x}$,

which is necessary for optimal solutions. The vector remains the single Simplexiterationen construction always allowed for the primal LP, while the vector conditions may hurt the dual LPs. If both the associated primary solution and the corresponding dual solution are admissible for a basis (one then speaks of a primal and dual admissible basis ), then both are optimal for the primal or dual linear program. It can be shown that this is the case if and only if the reduced cost vector is non-positive. Although the goal of the simplex method is actually only the calculation of an optimal primary solution, an optimal dual solution also falls out in the end. ${\displaystyle x}$ ${\displaystyle \pi }$ ${\displaystyle x}$ ${\displaystyle \pi }$ ${\displaystyle {\bar {c}}}$

An example calculation for duality can be found in the article Pivot Procedure .

Variants and improvements

In the form presented here, which essentially corresponds to the original version by Dantzig , the simplex algorithm is no longer used in practical implementations today. In the course of time, some variants of the simplex method have been developed, which significantly shorten the computing time and memory requirements when solving linear programs compared to the standard method and are numerically significantly more stable. The most important improvements that are now standard in good LP solvers should be briefly presented here.

Selection of the pivot element

When choosing the pivot element, you usually have some freedom. The pivot column and the pivot line can be selected as desired, provided that ${\displaystyle s}$ ${\displaystyle r}$

• the pivot column has positive reduced costs and
• the pivot line leads again to a permissible basic solution.

The choice of the pivot element often has a great influence on the number of iterations and the numerical stability of the method, especially in the case of degenerate problems. The development of better pivot strategies, particularly for column selection, has made great strides over time in accelerating the solution process.

Column selection

There are various strategies for selecting the pivot column ( pricing ), which require different computing effort and work differently depending on the input data:

• Choose the first appropriate column. This is the simplest variant, but it often leads to a large number of iterations and is therefore not used in practice.
• The method originally proposed by Dantzig chooses one of the columns with the greatest reduced cost value. This variant can take a lot of computing time with many variables.
• The steepest-edge pricing is a combination of column and row selection, which together bring the greatest progress for the target function. This variant is very complex in each iteration, but often leads to a few iterations.
• The devex pricing is an approximation of steepest-edge pricing proposed by Paula Harris in 1974 and one of the standard procedures in today's LP solvers. The columns of the matrix and the reduced costs are scaled to a uniform standard before the selection in order to increase the informative value of the reduced costs.
• With partial pricing , the quantity of variables is divided into blocks and one of the previous methods is applied to a block. The next block is only considered if no suitable variable is found there.
• The multiple pricing once selects a set of suitable variables, which are then preferably considered as candidates in the next iterations. Only when none of these candidates have positive reduced costs are the other variables considered.
• The partial multiple pricing is a combination of the last two variants, which only ever determines new candidates from a part of all available variables. Along with devex pricing, this strategy is one of the standard strategies today.
• With hybrid pricing , several strategies are used alternately depending on the situation. Some LP solvers also use numerical criteria when selecting columns in order to limit the problems caused by rounding errors.
• RG Bland's rule first chooses the column with the smallest index among all the columns in question. This is useful if, when there are several lines available for selection, the one with the smallest index is also selected. Evidence that this rule prevents cycles is contained in, for example.

Line selection

If there are several suitable pivot lines, you can choose between several variants:

• Choose the first appropriate line. Although this variant is very fast per iteration, it often leads to many iterations and is numerically unstable.
• The lexicographical selection rule selects the (unambiguous) lexicographically smallest line from all the lines in question . This rule is not particularly good from the point of view of speed, but it prevents tableaus from being visited multiple times and the algorithm from cycling. For this reason, it can be used, for example, for a few iterations to get away from a basic solution before switching back to other selection methods.
• The Harris quotient test proposed by Paula Harris in 1973 , which is one of the standard procedures today, allows the new solution to be slightly inadmissible for reasons of numerical stability.
• Pick randomly among the appropriate lines. Cycles become very improbable, but not impossible.

Variable bounds

In practice, upper and lower bounds for the variables often have to be taken into account. This is especially true when linear programs are solved as a sub-problem, for example as part of a branch-and-cut process. For such simple types of inequalities as variable bounds there is the so-called bounded simplex method, in which the bounds are taken into account directly in the individual simplex steps. In contrast to the standard version, in which a non-basic variable always has the value 0, it can now also assume the value of one of its bounds. This entrainment of the bounds in the individual steps results in a smaller number of lines and thus a smaller basis compared to the obvious variant of writing variable bounds as inequalities in the LP.

Dual simplex method

In addition to an optimal primary solution , ie a solution for the given linear program, the primal simplex method described above also calculates an optimal dual solution , ie a solution for the associated dual linear program. Since the dual LP is essentially created from the primal by swapping rows and columns, the simplex method can also be used to solve the dual problem by using the Tucker tableau , which is slightly modified compared to the above variant , and rows and columns in the algorithm described reversed. This variant is then called the dual simplex method . It was first described in 1954 by Carlton Lemke and EML Beale, but has only been an integral part of commercial LP solvers since the early 1990s, when successful pivot strategies were developed for it, such as the dual steepest-edge pricing in the version by Forrest and Goldfarb from the Year 1992.

In practice, the running time of the simplex method often depends largely on the number of lines in the LP. This is especially true for thinly populated matrices , as they normally occur in practice. If a linear program has a lot of conditions but only a few variables, it can be worthwhile to solve the dual LP instead, in which the number of rows and columns are swapped, and to have an optimal primary solution delivered, which is included in the calculation .

Another big advantage of the primal-dual approach is that primal and dual simplex steps can be carried out alternately in the same tableau. Instead of explicitly transposing the tableau, row and column operations are simply swapped in the algorithm, depending on whether the primal or the dual algorithm is used. In contrast to the primal simplex method, which always retains a permissible primary solution and only reaches a permissible dual solution at the end, it is the other way around with the dual simplex method. So if the primary solution to a basis is not admissible, but the associated dual solution is admissible, one can try to come back to a primal admissible solution through dual simplex steps. This can be used in several contexts, which are briefly described here.

• In the course of cutting plane methods or branch-and-cut methods, a variable limit is very often changed in a LP that has just been solved or an inequality is added that is not fulfilled by the old solution, and the LP is then solved again. Since the old basic solution is no longer permissible, one of the basic conditions of the primal simplex table is violated, so that the primal simplex method has to start from the beginning in order to solve the new LP. If nothing has been changed in the target function, the old dual solution is still permissible, so that with a few dual simplex steps from the old starting basis, an optimal solution for the modified LP is usually found after a few iterations. With large LPs, this difference is often very clearly reflected in the total running time.
• If numerical difficulties arise in the course of the algorithm or there is no progress in the objective function for a very long time, it can be useful to temporarily allow a slight violation of variable bounds in order to move out of a critical corner of the polytope. This can then be remedied with a few dual simplex steps.
• If the linear program has certain structures, you can directly specify a primally impermissible but dual admissible starting basis without having to calculate. In such a case, you can start phase II with dual simplex steps directly from this base and save yourself phase I.

Revised simplex method

Although practically occurring linear programs can have several hundred thousand variables, the simplex method only ever works with a small part of them, namely the basic variables. The non-basic columns only have to be considered when selecting columns, whereby - depending on the pivot strategy - it is often sufficient to only consider a part of them. This fact makes use of the revised simplex method , which only ever saves the current basic matrix or its inverse, together with some additional information from which the current basic matrix or its inverse can be calculated. This means that it uses significantly less storage space than the original panel method. Today this procedure forms the basis of several good LP solvers. ${\displaystyle A_{B}}$

In the first commercial implementation of this method by William Orchard Hays in 1954, the basic inverse was completely recalculated in every step, which was a challenge with the punch card computers of the time. A little later he implemented the so-called product form of the inverse based on an idea by A. Orden. Only the first basic inverse was saved, together with update vectors from which the current inverse could be calculated in each step. The record at that time was a linear program with 71 variables and 26 inequalities that was optimally solved within eight hours. In implementations used today, it is more the case that the base matrix itself is stored with the help of a special form of LR decomposition , since the inverse of a sparse matrix is ​​usually not sparse.

LR decompositions

In the course of the simplex method, a large number of similar linear equation systems are solved. Since large systems of linear equations also occur frequently in other contexts (for example when solving differential equations ), methods for the LR decomposition of a matrix were developed in numerical linear algebra in the 1970s . The matrix is ​​broken down into a lower and an upper triangular matrix, which then allows you to efficiently solve many systems of equations with the same matrix but different right-hand sides.

In the case of the simplex method, this method is applied to the basic matrix . Since this changes constantly in the course of the simplex algorithm, its LR decomposition must be adapted with each simplex step, for example with the help of the Forest-Tomlin update named after its inventors . This adaptation requires only very little effort compared to the calculation of a completely new LR decomposition, because the base matrix only changes in one column in each iteration. In practical implementations, a completely new LR decomposition of the current matrix is ​​usually calculated every few hundred iterations for numerical reasons. Often the matrix can largely be brought into a triangular shape by cleverly rearranging the rows and columns, so that only a small part of the basic matrix, the so-called nucleus , actually has to be factored. For the calculation of the LR decomposition itself there are again different variants, of which the LR decomposition with dynamic Markowitz pivoting has prevailed in practice, since this largely preserves the sparseness of matrices during the decomposition. This method has led to significant reductions in computing time, especially for large linear programs that are almost always sparsely populated. ${\displaystyle A_{B}}$

Preprocessing

In the last ten years, improved preprocessing has made great strides in solution times. For example, numerical problems often arise when both very large and very small numbers appear in a system of linear equations. In some cases, this can be done through preconditioning , e.g. B. Avoid equilibration of the system of equations before starting the actual algorithm.

Another class of preprocessing methods tries to recognize redundancies in the linear system of equations or to tighten variable bounds in order to reduce the number of rows and columns:

• If a line is linearly dependent on other lines, it is superfluous and can be removed. However, apart from the special case that a line is a scalar multiple of another line, this is generally difficult to detect with reasonable effort.
• Very often variables are restricted to a certain range of values ​​due to conditions or determined by other variables. For example, the equation and the nonnegativity conditions restrict both variables to the range . Knowing this limit can accelerate the solution process. In addition, the value of is determined by the value of . This means that you can replace this variable with and remove it from the linear program in all conditions in which it occurs . ${\displaystyle x_{1}+x_{2}=1}$ ${\displaystyle [0,1]}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle 1-x_{1}}$ ${\displaystyle x_{2}}$
• If several variables have been fixed to a certain range of values, it is possible that some inequalities are always fulfilled or can no longer be fulfilled. In the first case the inequality can be removed, in the second case the inadmissibility of the linear program is shown immediately and one can stop.

With the help of such methods, especially with very large linear programs, the number of rows and columns can sometimes be significantly reduced, which is reflected in much shorter solution times.

literature

• George B. Dantzig : Linear Programming and Extensions. Springer-Verlag, 1966 (Original edition: Linear Programming and Extensions , Princeton University Press, ISBN 0-691-05913-6 ).
• V. Klee , GJ Minty : How Good is the Simplex Algorithm? In: O. Shisha (editor): Inequalities III. Academic Press, New York 1972, pp. 159-175.
• Vašek Chvátal : Linear Programming. WH Freeman and Company, New York 1983, ISBN 0-7167-1587-2 .
• Alexander Schrijver: Theory of Linear and Integer Programming. John Wiley and Sons, 1998, ISBN 0-471-98232-6 .
• Wolfgang Domschke, Andreas Drexl: Introduction to Operations Research. 7th edition. Springer, Berlin 2007, ISBN 978-3-540-70948-0 .
• Michael Sauer: Operations Research compact 1st edition. Oldenbourg, Munich 2009, ISBN 978-3-486-59082-1 .
• Winfried Hochstättler: Algorithmic Mathematics . Springer, Berlin / Heidelberg 2010, ISBN 978-3-642-05421-1 .

Web links

• Helpful OR summary of the TU Kaiserslautern
• simplex me - the simple simplex solver. (Solve linear optimization problems with the simplex algorithm - multilingual, PDF export)
• Simplex applet with text input of the program
• Visualization of the solution steps of the simplex algorithm (Java program)
• Computer simplex algorithm shows all intermediate steps with explanation
• GNU scientific library contains simplex code

• nonlinear optimization ( memento from December 29, 2008 in the Internet Archive )

Individual evidence

1. ↑ John A. Nelder, R. Mead: A simplex method for function minimization . In: Computer Journal . 7, 1965, pp. 308-313. doi : 10.1093 / comjnl / 7.4.308 .
2. ^ Robert Bixby : Solving real-world linear programs: A decade and more of progress . In: Operations Research, Vol. 50, No. 1, 2002, pp. 3-15.
3. ↑ Harvey J. Greenberg: Klee-Minty Polytope Shows Exponential Time Complexity of Simplex Method. (PDF) University of Colorado at Denver, 1997.
4. ↑ Martin Grötschel : Algorithmische Diskrete Mathematik II: Linear Optimization , lecture script (PDF).
5. ↑ István Maros: A General Pricing Scheme for the Simplex Method. (PDF) Technical Report 2001/3, Department of Computing, Imperial College, London 2001, ISSN  1469-4174 .
6. ↑ Roland Wunderling: Parallel and Object-Oriented Simplex Algorithm . ( Memento from September 25, 2006 in the Internet Archive ) Dissertation, TU Berlin, 1996.
7. ^ R. Sedgewick: Algorithmen. Addison-Wesley Publishing Company, 1992, ISBN 3-89319-301-4 , p. 697.
8. ↑ M. Padberg: Linear Optimization and Extensions. Springer, Berlin / Heidelberg 1995.