Content deleted Content added
External links: add Archive.org link to simplex-m |
|||
| (21 intermediate revisions by 16 users not shown) | |||
Line 2:
{{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. |author-link=Katta G. Murty |year=2000 |title=Linear programming |publisher=John Wiley & Sons
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><ref name="Strang">{{cite journal|last=Strang|first=Gilbert|author-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.
==
[[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>
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|
==
{{further|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
Line 76:
\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. The zero in the first column represents the zero vector of the same dimension as the vector
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 127:
is the minimum over all ''r'' so that ''a''<sub>''rc''</sub> > 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.
===
{{see also|Revised simplex algorithm#Numerical example}}
Consider the linear program
Line 154:
:<math>
\begin{bmatrix}
0 & \frac{7}{3} & \frac{1}{3} & 0 &
0 & \frac{2}{3} & \frac{5}{3} &
\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 + \frac{
so the minimum value of ''Z'' is −20.
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 244 ⟶ 245:
</math>
This is, fortuitously, already optimal and the optimum value for the original linear program is −130/7. This value is "worse" than -20 which is to be expected for a problem which is more constrained.
==Advanced topics==
Line 254 ⟶ 255:
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 '''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 much more efficient than the standard simplex method. Commercial simplex solvers are based on the revised simplex algorithm.<ref name="Padberg" >{{cite book |first=M. |last=Padberg |title=Linear Optimization and Extensions |edition=Second |publisher=Springer-Verlag |year=1999 |isbn=3-540-65833-5 }}</ref><ref name="DantzigThapa2"/><ref>{{cite book |first1=Dmitris |last1=Alevras |first2=Manfred W. |last2=Padberg |title=Linear Optimization and Extensions: Problems and 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-8}}</ref>
===Degeneracy: stalling and cycling===
Line 282 ⟶ 283:
| 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
Line 293:
</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
===
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}}
Another method to analyze the performance of the simplex algorithm studies the behavior of worst-case scenarios under small perturbation – are worst-case scenarios stable under a small change (in the sense of [[structural stability]]), or do they become tractable? This area of research, called [[smoothed analysis]], was introduced specifically to study the simplex method. Indeed, the running time of the simplex method on input with noise is polynomial in the number of variables and the magnitude of the 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|citeseerx = 10.1.1.36.7658 |s2cid=6058077|issn=0254-5330}}</ref><ref>{{cite journal|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 B|volume=79|number=1–3|pages=369–395|editor1=Thomas M. Liebling |editor2=Dominique de Werra|publisher=North-Holland Publishing |___location=Amsterdam|year=1997|doi=10.1007/BF02614325|mr=1464775|s2cid=2794181 |url=http://infoscience.epfl.ch/record/77270 }}</ref> There are polynomial-time algorithms for linear programming that use interior point methods: these 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==
Line 310:
pages=198–214|year=1999|issn=0377-2217|doi=10.1016/S0377-2217(98)00049-6|first1=Tibor|last1=Illés|first2=Ákos|last2=Szirmai|first3=Tamás|last3=Terlaky|url=http://www.cas.mcmaster.ca/~terlaky/files/dut-twi-96-103.ps.gz |citeseerx=10.1.1.36.7090}}</ref>
==
{{div col}}
* [[Bland's rule|Pivoting rule of Bland]], which avoids cycling▼
* [[Criss-cross algorithm]]
* [[Cutting-plane method]]
Line 319 ⟶ 320:
* [[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}}
Line 328 ⟶ 329:
* {{cite book|last=Murty|first=Katta G.|author-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-9|mr=720547}}
==
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|0-262-03293-7}}. Section 29.3: The simplex algorithm, pp. 790–804.
* Frederick S. Hillier and Gerald J. Lieberman: ''Introduction to Operations Research'', 8th edition. McGraw-Hill. {{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-0}}
Line 336 ⟶ 337:
==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–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]
* [http://www.lokminglui.com/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://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)
* [
{{Optimization algorithms|convex}}
| |||