Simplex algorithm: Difference between revisions

Revision as of 20:47, 16 March 2014

Latest revision as of 16:15, 18 August 2025

(238 intermediate revisions by more than 100 users not shown)

Line 1:

{{Short description|Algorithm for linear programming}}

{{about|the linear programming algorithm|the non-linear optimization heuristic|Nelder–Mead method}}

<!-- {{Context|date=March 2012}} -->

In [[optimization (mathematics)|mathematical optimization]], [[George Dantzig|Dantzig]]'s '''simplex algorithm''' (or '''simplex method''') is a popular [[algorithm]] for [[linear programming]].<ref name="Murty">{{cite book |last=Murty |first=Katta G. |authorlinkauthor-link=Katta G. Murty |year=2000 |title=Linear programming |publisher=John Wiley & Sons Inc.|___locationurl=New York|year=1983|pages=xix+482|isbn=0-471-09725-X|mr=720547}}<http://ref><ref name="BasicDantzig">Richard Wwww. Cottle, edcomputer. ''The Basic George Borg/csdl/mags/cs/2000/01/c1022. Dantzig''. Stanford Business Books, Stanford University Press, Stanford, California, 2003. (Selected papers by [[George B. Dantzig]])html}}</ref><ref{{failed nameverification|date="DantzigThapa1">[[GeorgeJune B.2025|reason=Could Dantzig]]not andlocate Mukund Nreference. Thapa. 1997. ''Linear programming 1: Introduction''. Springer-Verlag.</ref><ref name="DantzigThapa2" >}}

[[George B. Dantzig]] and Mukund N. Thapa. 2003. ''Linear Programming 2: Theory and Extensions''. Springer-Verlag.</ref><ref name="Todd" >{{cite journal|author=[[Michael J. Todd (mathematician)|Michael J. Todd]] | year = 2002 | title = The many facets of linear programming | journal = Mathematical Programming | volume = 91 | issue = 3 | month = February}} (Invited survey, from the International Symposium on Mathematical Programming.)</ref> The journal ''[[Computing in Science and Engineering]]'' listed it as one of the top 10 algorithms of the twentieth century.<ref>''Computing in Science and Engineering'', volume 2, no. 1, 2000 [http://www.computer.org/csdl/mags/cs/2000/01/c1022.html html version]</ref>

The name of the algorithm is derived from the concept of a [[simplex]] and was suggested by [[Theodore Motzkin|T. S. Motzkin]].<ref name="Murty22" >{{harvtxt|Murty|1983|loc=Comment 2.2}}</ref> Simplices are not actually used in the method, but one interpretation of it is that it operates on simplicial ''[[cone (geometry)|cone]]s'', and these become proper simplices with an additional constraint.<ref name="Murty39">{{harvtxt|Murty|1983|loc=Note 3.9}}</ref><ref name="StoneTovey">{{cite journal|last1=Stone|first1=Richard E.|last2=Tovey|first2=Craig A.|title=The simplex and projective scaling algorithms as iteratively reweighted least squares methods|journal=SIAM Review|volume=33|year=1991|issue=2|pages=220–237

|mr=1124362|jstor=2031142|doi=10.1137/1033049}}</ref><ref>{{cite journal|last1=Stone|first1=Richard E.|last2=Tovey|first2=Craig A.|title=Erratum: The simplex and projective scaling algorithms as iteratively reweighted least squares methods|journal=SIAM Review|volume=33|year=1991|issue=3|pages=461|mr=1124362|doi=10.1137/1033100|jstor=2031443|ref=harv}}</ref><ref name="Strang">{{cite journal|last=Strang|first=Gilbert|authorlinkauthor-link=Gilbert Strang|title=Karmarkar's algorithm and its place in applied mathematics|journal=[[The Mathematical Intelligencer]]|date=1 June 1987|issn=0343-6993|pages=4–10|volume=9|doi=10.1007/BF03025891|mr=883185|issue=2|s2cid=123541868}}</ref> The simplicial cones in question are the corners (i.e., the neighborhoods of the vertices) of a geometric object called a [[polytope]]. The shape of this polytope is defined by the [[System of linear inequalities|constraints]] applied to the objective function.

publisher=Springer|___location=New York|issn=0343-6993|pages=4–10|volume=9|doi=10.1007/BF03025891|mr='''883185'''|ref=harv|issue=2}}</ref> The simplicial cones in question are the corners (i.e., the neighborhoods of the vertices) of a geometric object called a [[polytope]]. The shape of this polytope is defined by the [[System of linear inequalities|constraints]] applied to the objective function.

== Overview History==

[[George Dantzig]] worked on planning methods for the US Army Air Force during World War II using a [[Mechanical_calculator#1900s_to_1970s|desk calculator]]. During 1946, his colleague challenged him to mechanize the planning process to distract him from taking another job. Dantzig formulated the problem as linear inequalities inspired by the work of [[Wassily Leontief]], however, at that time he didn't include an objective as part of his formulation. Without an objective, a vast number of solutions can be feasible, and therefore to find the "best" feasible solution, military-specified "ground rules" must be used that describe how goals can be achieved as opposed to specifying a goal itself. Dantzig's core insight was to realize that most such ground rules can be translated into a linear objective function that needs to be maximized.<ref>{{Cite journal|url = https://apps.dtic.mil/sti/pdfs/ADA112060.pdf|archive-url = https://web.archive.org/web/20150520183722/http://www.dtic.mil/cgi-bin/GetTRDoc?Location=U2&doc=GetTRDoc.pdf&AD=ADA112060|url-status = live|archive-date = May 20, 2015|title = Reminiscences about the origins of linear programming|date = April 1982|journal = Operations Research Letters|doi = 10.1016/0167-6377(82)90043-8|volume = 1|issue = 2 |pages=43–48|last1 = Dantzig|first1 = George B.}}</ref> Development of the simplex method was evolutionary and happened over a period of about a year.<ref>{{Cite journal|url = http://www.phpsimplex.com/en/Dantzig_interview.htm|title = An Interview with George B. Dantzig: The Father of Linear Programming|last = Albers and Reid|date = 1986|journal = College Mathematics Journal|volume = 17|issue = 4|doi = 10.1080/07468342.1986.11972971|pages = 292–314}}</ref>

{{further2|[[Linear programming]]}}

After Dantzig included an objective function as part of his formulation during mid-1947, the problem was mathematically more tractable. Dantzig realized that one of the unsolved problems that [[George Dantzig#Education|he had mistaken]] as homework in his professor [[Jerzy Neyman]]'s class (and actually later solved), was applicable to finding an algorithm for linear programs. This problem involved finding the existence of [[Lagrange multipliers]] for general linear programs over a continuum of variables, each bounded between zero and one, and satisfying linear constraints expressed in the form of [[Lebesgue integral]]s. Dantzig later published his "homework" as a thesis to earn his doctorate. The column geometry used in this thesis gave Dantzig insight that made him believe that the Simplex method would be very efficient.<ref>{{Cite encyclopedia|url = http://apps.dtic.mil/dtic/tr/fulltext/u2/a182708.pdf|archive-url = https://web.archive.org/web/20150529003047/http://www.dtic.mil/dtic/tr/fulltext/u2/a182708.pdf|url-status = live|archive-date = May 29, 2015|title = Origins of the simplex method|last = Dantzig|first = George|date = May 1987|encyclopedia = A History of Scientific Computing|editor-last=Nash|editor-first=Stephen G.|publisher=Association for Computing Machinery|pages = 141–151|doi = 10.1145/87252.88081|isbn = 978-0-201-50814-7}}</ref>

==Overview==

{{further2further|[[Linear programming]]}}

[[Image:Simplex-description-en.svg|thumb|240px|A [[system of linear inequalities]] defines a [[polytope]] as a feasible region. The simplex algorithm begins at a starting [[vertex (geometry)|vertex]] and moves along the edges of the polytope until it reaches the vertex

of the optimumoptimal solution.]]

[[Image:Simplex-method-3-dimensions.png|thumb|240px|Polyhedron of simplex algorithm in 3D]]

The simplex algorithm operates on linear programs in ''standardthe form'', that is linear programming problems of the[[canonical form,]]

:Minimize

::<math>\mathbf{c}^T \cdot \mathbf{x}</math>

:Subject to

::<math>\mathbf{A}\mathbf{x} = \mathbf{b},\, x_i \ge 0</math>

::maximize <math display="inline">\mathbf{c}^T \cdot} \mathbf{x}</math>

with <math>\scriptstyle x \;=\; (x_1,\, \dots,\, x_n)</math> the variables of the problem, <math>\scriptstyle c \;=\; (c_1,\, \dots,\, c_n)</math> are the coefficients of the objective function, ''A'' a ''p×n'' matrix, and <math>\scriptstyle b \;=\; (b_1,\, \dots,\, b_p)</math> constants with <math>\scriptstyle b_j\geq 0</math>. There is a straightforward process to convert any linear program into one in standard form so this results in no loss of generality.

::subject to <math>\mathbf{A}\mathbf{x} =\leq \mathbf{b},\,</math> x_iand <math>\mathbf{x} \ge 0</math>

with <math>\scriptstylemathbf{c} x \;=\; (x_1c_1,\, \dots,\, x_nc_n)</math> the variablescoefficients of the problemobjective function, <math>(\scriptstylecdot)^\mathrm{T}</math> cis the [[matrix transpose]], and <math> \;mathbf{x} =\; (c_1x_1,\, \dots,\, c_nx_n)</math> are the coefficientsvariables of the objective functionproblem, ''<math>A''</math> is a ''p×np''×''n'' matrix, and <math>\scriptstyle \mathbf{b} \;=\; (b_1,\, \dots,\, b_p)</math> constants with <math>\scriptstyle b_j\geq 0</math>. There is a straightforward process to convert any linear program into one in standard form, so using this form of linear programs results in no loss of generality.

In geometric terms, the [[feasible region]]

::<math>\mathbf{A}\mathbf{x} = \mathbf{b},\, x_i \ge 0</math>

isIn ageometric (possiblyterms, unbounded)the [[convexfeasible polytoperegion]]. Theredefined isby aall simple characterizationvalues of the extreme points or vertices of this polytope, namely <math>\scriptstyle mathbf{x \;=\; (x_1,\, \dots,\, x_n)}</math> issuch an extreme point if and only if the column vectorsthat <math display="inline">A\mathbf{x} \scriptstylele A_i\mathbf{b}</math>, whereand <math>\scriptstyleforall i, x_i \,\ne\,ge 0 </math>, areis a (possibly unbounded) [[Linearconvex independence|linearly independentpolytope]].<ref>{{harvtxt|Murty|1983|loc=Theorem 3.1}}</ref>An Inextreme thispoint contextor suchvertex aof pointthis polytope is known as a ''[[basic feasible solution]]'' (BFS).

It can be shown that for a linear program in standard form, if the objective function has a minimummaximum value on the feasible region, then it has this value on (at least) one of the extreme points.<ref>{{harvtxt|Murty|1983|loc=Theorem 3.3}}</ref> This in itself reduces the problem to a finite computation since there is a finite number of extreme points, but the number of extreme points is unmanageably large for all but the smallest linear programs.<ref>{{harvtxt|Murty|1983|loc=Section 3.13|p=143}}</ref>

It can also be shown that, if an extreme point is not a minimummaximum point of the objective function, then there is an edge containing the point so that the value of the objective function is strictly decreasingincreasing on the edge moving away from the point.<ref name="Murty137">{{harvtxt|Murty|1983|loc=Section 3.8|p=137}}</ref> If the edge is finite, then the edge connects to another extreme point where the objective function has a smallergreater value, otherwise the objective function is unbounded belowabove on the edge and the linear program has no solution. The simplex algorithm applies this insight by walking along edges of the polytope to extreme points with lowergreater and lowergreater objective values. This continues until the minimummaximum value is reached, or an unbounded edge is visited, (concluding that the problem has no solution). The algorithm always terminates because the number of vertices in the polytope is finite; moreover since we jump between vertices always in the same direction (that of the objective function), we hope that the number of vertices visited will be small.<ref name="Murty137"/>

The solution of a linear program is accomplished in two steps. In the first step, known as Phase I, a starting extreme point is found. Depending on the nature of the program this may be trivial, but in general it can be solved by applying the simplex algorithm to a modified version of the original program. The possible results of Phase I are either that a basic feasible solution is found or that the feasible region is empty. In the latter case the linear program is called ''infeasible''. In the second step, Phase II, the simplex algorithm is applied using the basic feasible solution found in Phase I as a starting point. The possible results from Phase II are either an optimum basic feasible solution or an infinite edge on which the objective function is unbounded belowabove.<ref name="DantzigThapa1">[[George B. Dantzig]] and Mukund N. Thapa. 1997. ''Linear programming 1: Introduction''. Springer-Verlag.</ref><ref name="NeringTucker"/><ref name="Vanderbei" >Robert J. Vanderbei, [http://www.princeton.edu/~rvdb/LPbook/ ''Linear Programming: Foundations and Extensions''], 3rd ed., International Series in Operations Research & Management Science, Vol. 114, Springer Verlag, 2008. ISBN {{isbn|978-0-387-74387-5}}. <!-- (An on-line second edition was formerly available. Vanderbei's site still contains extensive materials.) --></ref>

==Standard form==

Line 38:

:<math>x_1 \ge 5</math>

a new variable, ''y''<submath>1y_1</submath>, is introduced with

:<math> \begin{align} y_1 = x_1 - 5\\x_1 = y_1 + 5 \end{align}</math>

The second equation may be used to eliminate ''x''<submath>1x_1</submath> from the linear program. In this way, all lower bound constraints may be changed to non-negativity restrictions.

Second, for each remaining inequality constraint, a new variable, called a ''[[slack variable]]'', is introduced to change the constraint to an equality constraint. This variable represents the difference between the two sides of the inequality and is assumed to be nonnegativenon-negative. For example, the inequalities

:<math> \begin{align}

x_2 + 2x_3 &\le 3\\

Line 56:

\end{align}</math>

It is much easier to perform algebraic manipulation on inequalities in this form. In inequalities where ≥ appears such as the second one, some authors refer to the variable introduced as a {{anchor|Surplus variable}}'' surplus variable''.

Third, each unrestricted variable is eliminated from the linear program. This can be done in two ways, one is by solving for the variable in one of the equations in which it appears and then eliminating the variable by substitution. The other is to replace the variable with the difference of two restricted variables. For example, if ''z''<submath>1z_1</submath> is unrestricted then write

:<math>\begin{align}

&z_1 = z_1^+ - z_1^-\\

Line 64:

\end{align}</math>

The equation may be used to eliminate ''z''<submath>1z_1</submath> from the linear program.

When this process is complete the feasible region will be in the form

:<math>\mathbf{A}\mathbf{x} = \mathbf{b},\, \forall \ x_i \ge 0</math>

It is also useful to assume that the rank of '''<math>\mathbf{A'''}</math> is the number of rows. This results in no loss of generality since otherwise either the system '''Ax'''&nbsp;<math>\mathbf{A}\mathbf{x} =&nbsp;''' \mathbf{b'''}</math> has redundant equations which can be dropped, or the system is inconsistent and the linear program has no solution.<ref>{{harvtxt|Murty|1983|p=173}}</ref>

==CanonicalSimplex tableauxtableau==

A linear program in standard form can be represented as a ''tableau'' of the form

:<math>

\begin{bmatrix}

1 & -\mathbf{c}^T & 0 \\

\mathbf{0} & \mathbf{A} & \mathbf{b}

\end{bmatrix}

</math>

The first row defines the objective function and the remaining rows specify the constraints. (Note,The zero in the first column represents the zero vector of the same dimension as the vector <math>\mathbf{b}</math> (different authors use different conventions as to the exact layout.). If the columns of <math>\mathbf{A}</math> can be rearranged so that it contains the [[identity matrix]] of order ''<math>p''</math> (the number of rows in <math>\mathbf{A}</math>) then the tableau is said to be in ''canonical form''.<ref>{{harvtxt|Murty|1983|loc=section 2.3.2}}</ref> The variables corresponding to the columns of the identity matrix are called ''basic variables'' while the remaining variables are called ''nonbasic'' or ''free variables''. If the values of the nonbasic variables are assumedset to be 0, then the values of the basic variables are easily obtained as entries in ''<math>\mathbf{b''}</math> and this solution is a basic feasible solution. The algebraic interpretation here is that the coefficients of the linear equation represented by each row are either <math>0</math>, <math>1</math>, or some other number. Each row will have <math>1</math> column with value <math>1</math>, <math>p-1</math> columns with coefficients <math>0</math>, and the remaining columns with some other coefficients (these other variables represent our non-basic variables). By setting the values of the non-basic variables to zero we ensure in each row that the value of the variable represented by a <math>1</math> in its column is equal to the <math>b</math> value at that row.

Conversely, given a basic feasible solution, the columns corresponding to the nonzero variables can be expanded to a nonsingular matrix. If the corresponding tableau is multiplied by the inverse of this matrix then the result is a tableau in canonical form.<ref>{{harvtxt|Murty|1983|loc=section 3.12}}</ref>

Line 104:

==Pivot operations==

The geometrical operation of moving from a basic feasible solution to an adjacent basic feasible solution is implemented as a ''pivot operation''. First, a nonzero ''pivot element'' is selected in a nonbasic column. The row containing this element is [[Elementary matrix#Row-multiplying transformations|multiplied]] by its reciprocal to change this element to 1, and then multiples of the row are added to the other rows to change the other entries in the column to 0. The result is that, if the pivot element is in a row ''r'', then the column becomes the ''r''-th column of the identity matrix. The variable for this column is now a basic variable, replacing the variable which corresponded to the ''r''-th column of the identity matrix before the operation. In effect, the variable corresponding to the pivot column enters the set of basic variables and is called the ''entering variable'', and the variable being replaced leaves the set of basic variables and is called the ''leaving variable''. The tableau is still in canonical form but with the set of basic variables changed by one element.<ref name="DantzigThapa1"/><ref name="NeringTucker"/>

==Algorithm==

Let a linear program be given by a canonical tableau. The simplex algorithm proceeds by performing successive pivot operations which each of which give an improved basic feasible solution; the choice of pivot element at each step is largely determined by the requirement that this pivot improveimproves the solution.

===Entering variable selection===

Since the entering variable will, in general, increase from 0 to a positive number, the value of the objective function will decrease if the derivative of the objective function with respect to this variable is negative. Equivalently, the value of the objective function is decreasedincreased if the pivot column is selected so that the corresponding entry in the objective row of the tableau is positive.

If there is more than one column so that the entry in the objective row is positive then the choice of which one to add to the set of basic variables is somewhat arbitrary and several ''entering variable choice rules''<ref name="Murty66">{{harvtxt|Murty|1983|p=66}}</ref> such as [[Devex algorithm]]<ref>Harris, Paula MJ. "Pivot selection methods of the Devex LP code." Mathematical programming 5.1 (1973): 1–28</ref> have been developed.

If all the entries in the objective row are less than or equal to 0 then no choice of entering variable can be made and the solution is in fact optimal. It is easily seen to be optimal since the objective row now corresponds to an equation of the form

:<math display="block">z(\mathbf{x})=z_B+\text{nonnegativenon-positive terms corresponding to nonbasicnon-basic variables}</math>

Note that byBy changing the entering variable choice rule so that it selects a column where the entry in the objective row is negative, the algorithm is changed so that it finds the maximumminimum of the objective function rather than the minimummaximum.

===Leaving variable selection===

Once the pivot column has been selected, the choice of pivot row is largely determined by the requirement that the resulting solution be feasible. First, only positive entries in the pivot column are considered since this guarantees that the value of the entering variable will be nonnegative. If there are no positive entries in the pivot column then the entering variable can take any nonnegativenon-negative value with the solution remaining feasible. In this case the objective function is unbounded below and there is no minimum.

Next, the pivot row must be selected so that all the other basic variables remain positive. A calculation shows that this occurs when the resulting value of the entering variable is at a minimum. In other words, if the pivot column is ''c'', then the pivot row ''r'' is chosen so that

:<math>b_r / a_{crrc}\,</math>

is the minimum over all ''r'' so that ''a''_''crrc'' > 0. This is called the ''minimum ratio test''.<ref name="Murty66"/> If there is more than one row for which the minimum is achieved then a ''dropping variable choice rule''<ref>{{harvtxt|Murty|1983|p=67}}</ref> can be used to make the determination.

=== Example ===

{{seealsosee also|Revised simplex algorithm#Numerical example}}

Consider the linear program

:Minimize

Line 151:

:<math>x=y=z=0,\,s=10,\,t=15.</math>

Columns 2, 3, and 4 can be selected as pivot columns, for this example column 4 is selected. The values of ''xz'' resulting from the choice of rows 2 and 3 as pivot rows are 10/1&nbsp;=&nbsp;10 and 15/3&nbsp;=&nbsp;5 respectively. Of these the minimum is 5, so row 3 must be the pivot row. Performing the pivot produces

:<math>

\begin{bmatrix}

1 & -\tfracfrac{2}{3} & -\tfracfrac{11}{3} & 0 & 0 & -\tfracfrac{4}{3} & -20 \\

0 & \tfracfrac{7}{3} & \tfracfrac{1}{3} & 0 & 1 & -\tfracfrac{1}{3} & 5 \\

0 & \tfracfrac{2}{3} & \tfracfrac{5}{3} & 1 & 0 & \tfracfrac{1}{3} & 5

\end{bmatrix}

</math>

Line 164:

For the next step, there are no positive entries in the objective row and in fact

:<math display="block">Z = -20 + \tfracfrac{2}{3} x + \tfracfrac{11}{3} y + \tfracfrac{4}{3} t</math>

so the minimum value of ''Z'' is&nbsp;&minus;20.

==Finding an initial canonical tableau==

In general, a linear program will not be given in the canonical form and an equivalent canonical tableau must be found before the simplex algorithm can start. This can be accomplished by the introduction of ''artificial variables''. Columns of the identity matrix are added as column vectors for these variables. If the b value for a constraint equation is negative, the equation is negated before adding the identity matrix columns. This does not change the set of feasible solutions or the optimal solution, and it ensures that the slack variables will constitute an initial feasible solution. The new tableau is in canonical form but it is not equivalent to the original problem. So a new objective function, equal to the sum of the artificial variables, is introduced and the simplex algorithm is applied to find the minimum; the modified linear program is called the ''Phase&nbsp;I'' problem.<ref>{{harvtxt|Murty|1983|p=60}}</ref>

The simplex algorithm applied to the Phase I problem must terminate with a minimum value for the new objective function since, being the sum of nonnegative variables, its value is bounded below by 0. If the minimum is 0 then the artificial variables can be eliminated from the resulting canonical tableau producing a canonical tableau equivalent to the original problem. The simplex algorithm can then be applied to find the solution; this step is called ''Phase&nbsp;II''. If the minimum is positive then there is no feasible solution for the Phase I problem where the artificial variables are all zero. This implies that the feasible region for the original problem is empty, and so the original problem has no solution.<ref name="DantzigThapa1"/><ref name="NeringTucker"/><ref name="Padberg"/>

Line 184:

\end{align}</math>

It differs from the previous example by having equality instead of inequality constraints. The previous solution <math>x=y=0\, , z=5</math> violates the first constraint.

This new problem is represented by the (non-canonical) tableau

:<math>

\begin{bmatrix}

Line 203 ⟶ 204:

</math>

Note that theThe equation defining the original objective function is retained in anticipation of Phase II.

By construction, ''u'' and ''v'' are both basic variables since they are part of the initial identity matrix. However, the objective function ''W'' currently assumes that ''u'' and ''v'' are both&nbsp;0. In order to adjust the objective function to be the correct value where ''u''&nbsp;=&nbsp;10 and ''v''&nbsp;=&nbsp;15, add the third and fourth rows to the first row giving

After pricing out this becomes

:<math>

\begin{bmatrix}

Line 218 ⟶ 219:

:<math>

\begin{bmatrix}

13 & 0 & \tfrac{7}{3} & \tfrac{1}{3} & 0 & 0 & -\tfrac{4}{3} & 515 \\

0 & 13 & -\tfrac{2}{3} & -\tfrac{11}{3} & 0 & 0 & -\tfrac{4}{3} & -2060 \\

0 & 0 & \tfrac{7}{3} & \tfrac{1}{3} & 0 & 13 & -\tfrac{1}{3} & 515 \\

0 & 0 & \tfrac{2}{3} & \tfrac{5}{3} & 13 & 0 & \tfrac{1}{3} & 515

\end{bmatrix}

</math>

Line 228 ⟶ 229:

:<math>

\begin{bmatrix}

17 & 0 & 0 & 0 & 0 & -17 & -1 7 & 0 \\

0 & 17 & 0 & -\tfrac{25}{7} & 0 & \tfrac{2}{7} & -\tfrac{10}{7} & -\tfrac{130}{7} \\

0 & 0 & 17 & \tfrac{1}{7} & 0 & \tfrac{3}{7} & -\tfrac{1}{7} & \tfrac{15}{7} \\

0 & 0 & 0 & \tfrac{11}{7} & 17 & -\tfrac{2}{7} & \tfrac{3}{7} & \tfrac{25}{7}

\end{bmatrix}

</math>

Line 238 ⟶ 239:

:<math>

\begin{bmatrix}

17 & 0 & -\tfrac{25}{7} & 0 & -\tfrac{130}{7} \\

0 & 17 & \tfrac{1}{7} & 0 & \tfrac{15}{7} \\

0 & 0 & \tfrac{11}{7} & 17 & \tfrac{25}{7}

\end{bmatrix}

</math>

This is, fortuitously, already optimal and the optimum value for the original linear program is&nbsp;−130/7. This value is "worse" than -20 which is to be expected for a problem which is more constrained.

==Advanced topics==

Line 250 ⟶ 251:

===Implementation===

{{main|Revised simplex algorithm}}

The tableau form used above to describe the algorithm lends itself to an immediate implementation in which the tableau is maintained as a rectangular (''m''&nbsp;+&nbsp;1)-by-(''m''&nbsp;+&nbsp;''n''&nbsp;+&nbsp;1) array. It is straightforward to avoid storing the m explicit columns of the identity matrix that will occur within the tableau by virtue of '''B''' being a subset of the columns of ['''A''',&nbsp;'''I''']. This implementation is referred to as the "''standard'' simplex algorithm". The storage and computation overhead areis such that the standard simplex method is a prohibitively expensive approach to solving large linear programming problems.

In each simplex iteration, the only data required are the first row of the tableau, the (pivotal) column of the tableau corresponding to the entering variable and the right-hand-side. The latter can be updated using the pivotal column and the first row of the tableau can be updated using the (pivotal) row corresponding to the leaving variable. Both the pivotal column and pivotal row may be computed directly using the solutions of linear systems of equations involving the matrix '''B''' and a matrix-vector product using '''A'''. These observations motivate the "[[Revised simplex algorithm|''revised'' simplex algorithm]]", for which implementations are distinguished by their invertible representation of&nbsp;'''B'''.<ref name="DantzigThapa2" >{{cite book |first1=George B. |last1=Dantzig |authorlink=George B. Dantzig |first2=Mukund N. |last2=Thapa |year=2003 |title=Linear Programming 2: Theory and Extensions |publisher=Springer-Verlag }}</ref>

In large linear-programming problems '''A''' is typically a [[sparse matrix]] and, when the resulting sparsity of '''B''' is exploited when maintaining its invertible representation, the revised simplex algorithm is a much more efficient than the standard simplex method. Commercial simplex solvers are based on the revised simplex algorithm.<ref name="DantzigThapa2"/><ref name="Padberg" >{{cite book |first=M. |last=Padberg, ''|title=Linear Optimization and Extensions'', |edition=Second Edition, |publisher=Springer-Verlag, |year=1999. |isbn=3-540-65833-5 }}</ref><ref name="DantzigThapa2"/><ref>{{cite book |first1=Dmitris |last1=Alevras and |first2=Manfred W. |last2=Padberg, ''|title=Linear Optimization and Extensions: Problems and Extensions'',Solutions |series=Universitext, |publisher=Springer-Verlag, |year=2001. |isbn=3-540-41744-3 }} (Problems from Padberg with solutions.)</ref><ref name="MarosMitra" >{{cite book|last1=Maros|first1=István|last2=Mitra|author2-link=Gautam Mitra|first2=Gautam|chapter=Simplex algorithms|mr=1438309|title=Advances in linear and integer programming|pages=1–46|editor=J. E. Beasley|publisher=Oxford Science|year=1996}}</ref><ref>{{cite book|mr=1960274|last=Maros|first=István|title=Computational techniques of the simplex method|series=International Series in Operations Research & Management Science|volume=61|publisher=Kluwer Academic Publishers|___location=Boston, MA|year=2003|pages=xx+325|isbn=978-1-4020-7332-18}}</ref>

===Degeneracy: Stallingstalling and cycling===

If the values of all basic variables are strictly positive, then a pivot must result in an improvement in the objective value. When this is always the case no set of basic variables occurs twice and the simplex algorithm must terminate after a finite number of steps. Basic feasible solutions where at least one of the ''basic ''variables is zero are called ''degenerate'' and may result in pivots for which there is no improvement in the objective value. In this case there is no actual change in the solution but only a change in the set of basic variables. When several such pivots occur in succession, there is no improvement; in large industrial applications, degeneracy is common and such "''stalling''" is notable.

Worse than stalling is the possibility the same set of basic variables occurs twice, in which case, the deterministic pivoting rules of the simplex algorithm will produce an infinite loop, or "cycle". While degeneracy is the rule in practice and stalling is common, cycling is rare in practice. A discussion of an example of practical cycling occurs in [[Manfred W. Padberg|Padberg]].<ref name="Padberg"/> [[Bland's rule]] prevents cycling and thus guaranteeguarantees that the simplex algorithm always terminates.<ref name="Padberg"/><ref name="Bland">

{{cite journal

{{cite journal|title=New finite pivoting rules for the simplex method|first=Robert G.|last=Bland|journal=Mathematics of Operations Research|volume=2|issue=2|date=May 1977|pages=103–107|doi=10.1287/moor.2.2.103|jstor=3689647|mr=459599|ref=harv}}</ref><ref>{{harvtxt|Murty|1983|p=79}}</ref> Another pivoting algorithm, the [[criss-cross algorithm]] never cycles on linear programs.<ref>There are abstract optimization problems, called [[oriented matroid]] programs, on which Bland's rule cycles (incorrectly) while the [[criss-cross algorithm]] terminates correctly.</ref>

| title=New finite pivoting rules for the simplex method

| first1=Robert G. | last1=Bland | authorlink1=Robert G. Bland

| journal=[[Mathematics of Operations Research]]

| volume=2

| issue=2

| date=May 1977

| pages=103–107

| doi=10.1287/moor.2.2.103

| jstor=3689647

| mr=459599

{{cite journal|title=New finite pivoting rules for the simplex method|first=Robert G.|last=Bland|journal=Mathematics of Operations Research|volume=2|issue=2|date=May 1977|pages=103–107|doi=10.1287/moor.2.2.103|jstor=3689647|mr=459599|refs2cid=harv18493293}}</ref><ref>{{harvtxt|Murty|1983|p=79}}</ref> Another pivoting algorithm, the [[criss-cross algorithm]] never cycles on linear programs.<ref>There are abstract optimization problems, called [[oriented matroid]] programs, on which Bland's rule cycles (incorrectly) while the [[criss-cross algorithm]] terminates correctly.</ref>

History-based pivot rules such as [[Zadeh's rule]] and [[Cunningham's rule]] also try to circumvent the issue of stalling and cycling by keeping track of how often particular variables are being used and then favor such variables that have been used least often.

===Efficiency in the worst case===

The simplex method is remarkably efficient in practice and was a great improvement over earlier methods such as [[Fourier–Motzkin elimination]]. However, in 1972, [[Victor Klee|Klee]] and Minty<ref name="KleeMinty">{{cite book|title=Inequalities III (Proceedings of the Third Symposium on Inequalities held at the University of California, Los Angeles, Calif., September 1–9, 1969, dedicated to the memory of Theodore S. Motzkin)|editor-first=Oved|editor-last=Shisha|publisher=Academic Press|___location=New York-London|year=1972|mr=332165|last1=Klee|first1=Victor|authorlink1author-link1=Victor Klee|last2=Minty|first2= George J.|authorlink2author-link2=George J. Minty|chapter=How good is the simplex algorithm?|pages=159–175|ref=harv}}</ref> gave an example, the [[Klee–Minty cube]], showing that the worst-case complexity of simplex method as formulated by Dantzig is [[exponential time]]. Since then, for almost every variation on the method, it has been shown that there is a family of linear programs for which it performs badly. It is an open question if there is a variation with [[polynomial time]], or evenalthough sub-exponential worst-casepivot complexity.<refrules name="PapSte">[[Christosare Hknown. Papadimitriou]] and Kenneth Steiglitz, ''Combinatorial Optimization: Algorithms and Complexity'', Corrected republication with a new preface, Dover. (computer science)</ref><ref name="Schrijver" >[[Alexander Schrijver]], ''Theory of Linear and Integer Programming''. John Wiley & sons, 1998, ISBN 0-471-98232-6 (mathematical)</ref>{{Citation

| last1 = Hansen

| first1 = Thomas

| last2 = Zwick

| first2 = Uri

| title = Proceedings of the forty-seventh annual ACM symposium on Theory of Computing

| chapter = An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm

| author2-link = Uri Zwick

| pages = 209–218

| year = 2015

| doi = 10.1145/2746539.2746557

| citeseerx = 10.1.1.697.2526

| isbn = 9781450335362

| s2cid = 1980659

}}

</ref>

In 2014, it was proved{{citation-needed|date=January 2024}} that a particular variant of the simplex method is [[NP-mighty]], i.e., it can be used to solve, with polynomial overhead, any problem in NP implicitly during the algorithm's execution. Moreover, deciding whether a given variable ever enters the basis during the algorithm's execution on a given input, and determining the number of iterations needed for solving a given problem, are both [[NP-hardness|NP-hard]] problems.<ref>{{Cite journal|last1=Disser|first1=Yann|last2=Skutella|first2=Martin|date=2018-11-01|title=The Simplex Algorithm Is NP-Mighty|journal=ACM Trans. Algorithms|volume=15|issue=1|pages=5:1–5:19|doi=10.1145/3280847|issn=1549-6325|arxiv=1311.5935|s2cid=54445546}}</ref> At about the same time it was shown that there exists an artificial pivot rule for which computing its output is [[PSPACE-complete]].<ref>{{Citation | last1 = Adler | first1 = Ilan|author1-link=Ilan Adler | last2 = Christos | first2 = Papadimitriou | author2-link = Christos Papadimitriou | last3 = Rubinstein | first3 = Aviad | title = Integer Programming and Combinatorial Optimization | chapter = On Simplex Pivoting Rules and Complexity Theory | volume = 17 | pages = 13–24 | year = 2014 | arxiv = 1404.3320 | doi = 10.1007/978-3-319-07557-0_2| series = Lecture Notes in Computer Science | isbn = 978-3-319-07556-3 | s2cid = 891022 }}</ref> In 2015, this was strengthened to show that computing the output of Dantzig's pivot rule is [[PSPACE-complete]].<ref>{{Citation | last1 = Fearnly | first1 = John | last2 = Savani | first2 = Rahul | title = Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | chapter = The Complexity of the Simplex Method | pages = 201–208 | year = 2015 | arxiv = 1404.0605 | doi = 10.1145/2746539.2746558| isbn = 9781450335362 | s2cid = 2116116 }}</ref>

===Efficiency in practice===

Analyzing and quantifying the observation that the simplex algorithm is efficient in practice despite its exponential worst-case complexity has led to the development of other measures of complexity. The simplex algorithm has polynomial-time [[Best, worst and average case|average-case complexity]] under various [[probability distribution]]s, with the precise average-case performance of the simplex algorithm depending on the choice of a probability distribution for the [[random matrix|random matrices]].<ref name="Schrijver">[[Alexander Schrijver]], ''Theory of Linear and Integer Programming''. John Wiley & sons, 1998, {{isbn|0-471-98232-6}} (mathematical)</ref><ref name="Borgwardt">The simplex algorithm takes on average ''D'' steps for a cube. {{harvtxt|Borgwardt|1987}}: {{cite book|last=Borgwardt|first=Karl-Heinz|title=The simplex method: A probabilistic analysis|series=Algorithms and Combinatorics (Study and Research Texts)|volume=1|publisher=Springer-Verlag|___location=Berlin|year=1987|pages=xii+268|isbn=978-3-540-17096-9|mr=868467}}</ref> Another approach to studying "[[porous set|typical phenomena]]" uses [[Baire category theory]] from [[general topology]], and to show that (topologically) "most" matrices can be solved by the simplex algorithm in a polynomial number of steps.{{Citation needed|date=June 2019}}

The simplex method is remarkably efficient in practice and was a great improvement over earlier methods such as [[Fourier–Motzkin elimination]]. However, in 1972, Klee and Minty<ref name="KleeMinty">{{cite book|title=Inequalities III (Proceedings of the Third Symposium on Inequalities held at the University of California, Los Angeles, Calif., September 1–9, 1969, dedicated to the memory of Theodore S. Motzkin)|editor-first=Oved|editor-last=Shisha|publisher=Academic Press|___location=New York-London|year=1972|mr=332165|last1=Klee|first1=Victor|authorlink1=Victor Klee|last2=Minty|first2= George J.|authorlink2=George J. Minty|chapter=How good is the simplex algorithm?|pages=159–175|ref=harv}}</ref> gave an example showing that the worst-case complexity of simplex method as formulated by Dantzig is [[exponential time]]. Since then, for almost every variation on the method, it has been shown that there is a family of linear programs for which it performs badly. It is an open question if there is a variation with [[polynomial time]], or even sub-exponential worst-case complexity.<ref name="PapSte">[[Christos H. Papadimitriou]] and Kenneth Steiglitz, ''Combinatorial Optimization: Algorithms and Complexity'', Corrected republication with a new preface, Dover. (computer science)</ref><ref name="Schrijver" >[[Alexander Schrijver]], ''Theory of Linear and Integer Programming''. John Wiley & sons, 1998, ISBN 0-471-98232-6 (mathematical)</ref>

AnalyzingAnother andmethod quantifyingto analyze the observationperformance thatof the simplex algorithm is efficient in practice, even though it has exponential worst-case complexity, has led tostudies the developmentbehavior of other measures of complexity. The simplex algorithm has polynomial-time [[Best, worst and average case|average-case complexity]]scenarios under varioussmall [[probabilityperturbation distribution]]s,– withare the precise averageworst-case performancescenarios ofstable theunder simplexa algorithmsmall dependingchange on(in the choicesense of a probability distribution for the [[randomstructural matrix|random matricesstability]].<ref name="Schrijver"/><ref name="Borgwardt">The simplex algorithm takes on average ''D'' steps for a cube. {{harvtxt|Borgwardt|1987}}: {{cite book|last=Borgwardt|first=Karl-Heinz|title=The simplex method: A probabilistic analysis|series=Algorithms and Combinatorics (Study and Research Texts)|volume=1|publisher=Springer-Verlag|___location=Berlin|year=1987|pages=xii+268|isbn=3-540-17096-0|mr=868467|ref=harv}}</ref>, Anotheror approachdo tothey studyingbecome "[[poroustractable? set|typicalThis phenoma]]"area usesof [[Baireresearch, category theory]] fromcalled [[generalsmoothed topologyanalysis]], andwas tointroduced showspecifically thatto (topologically) "most" matrices can be solved bystudy the simplex algorithm in a polynomial number of stepsmethod. AnotherIndeed, methodthe torunning analyze the performancetime of the simplex algorithmmethod studieson theinput behaviorwith ofnoise worst-caseis scenariospolynomial under small perturbation – are worst-case scenarios stable under a small change (in the sensenumber of [[structuralvariables stability]]),and orthe domagnitude theyof becomethe tractable? Formally, this method uses random problems to which is added a [[normal distribution|Gaussian]] [[random vector]] ("[[smoothed complexity]]")perturbations.<ref>{{Cite book | last1=Spielman | first1=Daniel | last2=Teng | first2=Shang-Hua | author2-link=Shanghua Teng | title=Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing | publisher=ACM | isbn=978-1-58113-349-3 | doi=10.1145/380752.380813 | year=2001 | chapter=Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time| pages=296–305 | arxiv=cs/0111050| s2cid=1471 }}</ref><ref>{{Cite journal|last1=Dadush|first1=Daniel|last2=Huiberts|first2=Sophie|date=2020-01-01|title=A Friendly Smoothed Analysis of the Simplex Method|url=https://epubs.siam.org/doi/abs/10.1137/18M1197205|journal=SIAM Journal on Computing|volume=49|issue=5|pages=STOC18–449|doi=10.1137/18M1197205|s2cid=226351624|issn=0097-5397|arxiv=1711.05667}}</ref>

==Other algorithms==

Other algorithms for solving linear-programming problems are described in the [[linear programming|linear-programming]] article. Another basis-exchange pivoting algorithm is the [[criss-cross algorithm]].<ref>{{cite journal|last1=Terlaky|first1=Tamás|last2=Zhang|first2=Shu Zhong|title=Pivot rules for linear programming: A Survey on recent theoretical developments|issue=1|journal=Annals of Operations Research|volume=46–47|year=1993|pages=203–233|doi=10.1007/BF02096264|mr=1260019|idciteseerx = {{citeseerx|10.1.1.36.7658}} |publishers2cid=Springer Netherlands6058077|issn=0254-5330|unused_data=<!-- authorlink1=Tamás Terlaky -->}}</ref><ref>{{cite articlejournal|first1=Komei|last1=Fukuda|author1-link=Komei Fukuda|first2=Tamás|last2=Terlaky|author2-link=Tamás Terlaky|title=Criss-cross methods: A fresh view on pivot algorithms |journal=Mathematical Programming:, Series&nbsp; B|volume=79|number=1—31–3|pages=369–395|editorseditor1=Thomas&nbsp; M. Liebling and |editor2=Dominique de&nbsp; Werra|publisher=North-Holland Publishing&nbsp;Co. |___location=Amsterdam|year=1997|doi=10.1007/BF02614325|MRmr=1464775|s2cid=2794181 |url=http://infoscience.epfl.ch/record/77270 }}</ref> There are polynomial-time algorithms for linear programming that use interior point methods: Thesethese include [[Khachiyan]]'s [[ellipsoidal algorithm]], [[Karmarkar]]'s [[Karmarkar's algorithm|projective algorithm]], and [[interior point method|path-following algorithm]]s.<ref name="Vanderbei"/> The [[Big_M_method|Big-M method]] is an alternative strategy for solving a linear program, using a single-phase simplex.

==Linear-fractional programming==

{{Main|Linear-fractional programming}}

[[Linear-fractional programming|Linear–fractional programming]] (LFP) is a generalization of [[linear programming]] (LP). WhereIn LP the objective function ofis linear programsa are [[linear functional|linear functionsfunction]], while the objective function of a linear-fractionallinear–fractional program is a ratio of two linear functions. In other words, a linear program is a fractional-linearfractional–linear program in which the denominator is the constant function having the value one everywhere. A linear-fractionallinear–fractional program can be solved by a variant of the simplex algorithm.<ref>{{harvtxt|Murty|1983|loc=Chapter 3.20 (pp. 160–164) and pp. 168 and 179}}</ref><ref>Chapter five: {{cite book|last=Craven|first=B. D.|title=Fractional programming|series=Sigma Series in Applied Mathematics|volume=4|publisher=Heldermann Verlag|___location=Berlin|year=1988|pages=145|isbn=978-3-88538-404-35|mr=949209}}</ref><ref>{{cite journal|last1=Kruk|first1=Serge|last2=Wolkowicz|first2=Henry|title=Pseudolinear programming|journal=[[SIAM Review]]|volume=41|year=1999|issue=4|pages=795–805|mr=1723002|jstor=2653207|doi=10.1137/S0036144598335259|citeseerx=10.1.1.53.7355|bibcode=1999SIAMR..41..795K}}

</ref><ref>{{cite journal|last1=Mathis|first1=Frank H.|last2=Mathis|first2=Lenora Jane|title=A nonlinear programming algorithm for hospital management|journal=[[SIAM Review]]|volume=37 |year=1995 |issue=2 |pages=230–234|mr=1343214|jstor=2132826|doi=10.1137/1037046|s2cid=120626738 }}

</ref> They can be solvedor by the [[criss-cross algorithm]], also.<ref>{{cite journal|title=The finite criss-cross method for hyperbolic programming|journal=European Journal of Operational Research|volume=114|issue=1|

pages=198–214|year=1999|issn=0377-2217|doi=10.1016/S0377-2217(98)00049-6|url=http://www.sciencedirect.com/science/article/B6VCT-3W3DFHB-M/2/4b0e2fcfc2a71e8c14c61640b32e805a|first1=Tibor|last1=Illés|first2=Ákos|last2=Szirmai|first3=Tamás|last3=Terlaky|ref=harv|idurl=[http://www.cas.mcmaster.ca/~terlaky/files/dut-twi-96-103.ps.gz PDF preprint]|citeseerx=10.1.1.36.7090}}</ref>

== See also ==

{{div col}}

* [[Bland's rule|Pivoting rule of Bland]], which avoids cycling]]

* [[Criss-cross algorithm]]

* [[Cutting-plane method]]

* [[Devex algorithm]]

* [[Fourier–Motzkin elimination]]

* [[Gradient descent]]

* [[Karmarkar's algorithm]]

* [[Nelder–Mead method|Nelder–Mead simplicial heuristic]]

* [[Loss Functions]] - a type of Objective Function

* [[Bland's rule|Pivoting rule of Bland, which avoids cycling]]

{{colend}}

==Notes==

{{reflist|2}}

==References==

* {{cite book|last=Murty|first=Katta G.|authorlinkauthor-link=Katta G. Murty|title=Linear programming|publisher=John Wiley & Sons, Inc.|___location=New York|year=1983|pages=xix+482|isbn=978-0-471-09725-X9|mr=720547|ref=harv}}

== Further reading ==

These introductions are written for students of [[computer science]] and [[operations research]]:

* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''Introduction to Algorithms'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN {{isbn|0-262-03293-7}}. Section 29.3: The simplex algorithm, pp.&nbsp;790&ndash;804.

* Frederick S. Hillier and Gerald J. Lieberman: ''Introduction to Operations Research'', 8th edition. McGraw-Hill. ISBN {{isbn|0-07-123828-X}}

* {{cite book|title=Optimization in operations research|first=Ronald L.|last=Rardin|year=1997|publisher=Prentice Hall|pages=919|isbn=978-0-02-398415-50}}

==External links==

{{wikibooks|Operations Research|The Simplex Method}}

* [http://www.isye.gatech.edu/~spyros/LP/LP.html An Introduction to Linear Programming and the Simplex Algorithm] by Spyros Reveliotis of the Georgia Institute of Technology.

* Greenberg, Harvey J., ''Klee-MintyKlee–Minty Polytope Shows Exponential Time Complexity of Simplex Method'' the University of Colorado at Denver (1997) [http://glossary.computing.society.informs.org/notes/Klee-Minty.pdf PDF download]

*(dead link) [http://www.mathlokminglui.cuhk.edu.hk/course/math3210com/lpch3.pdf Simplex Method] A tutorial for Simplex Method with examples (also two-phase and M-method).

* [https://www.mathstools.com/section/main/simplex_online_calculator Mathstools] Simplex Calculator from www.mathstools.com

*[http://math.uww.edu/~mcfarlat/s-prob.htm Example of Simplex Procedure for a Standard Linear Programming Problem] by Thomas McFarland of the University of Wisconsin-Whitewater.

* [http://wwwmath.phpsimplexuww.comedu/simplex~mcfarlat/simplexs-prob.htm?l=en PHPSimplex:Example onlineof toolSimplex toProcedure solvefor a Standard Linear Programming ProblemsProblem] by DanielThomas Izquierdo and Juan José RuizMcFarland of the University of Málaga (UMA, Spain)Wisconsin-Whitewater.

* [http://www.phpsimplex.com/simplex/simplex.htm?l=en PHPSimplex: online tool to solve Linear Programming Problems] by Daniel Izquierdo and Juan José Ruiz of the University of Málaga (UMA, Spain)

* [https://web.archive.org/web/20180513100217/http://simplex-m.com/ simplex-m] Online Simplex Solver

{{Optimization algorithms|convex}}

{{Mathematical programming}}

{{Authority control}}

{{DEFAULTSORT:Simplex Algorithm}}

[[Category:Optimization algorithms and methods]]

[[Category:Operations1947 researchin computing]]

[[Category:1947 in computer science]]

[[Category:Exchange algorithms]]

[[Category:Linear programming]]

[[Category:Computer-related introductions in 1947]]