Simplex algorithm: Difference between revisions

Revision as of 11:08, 1 November 2016

Revision as of 19:47, 20 January 2017

Line 1:

{{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.|authorlink=Katta G. Murty|title=Linear programming|publisher=John Wiley & Sons Inc.|___location=New York|year=1983|pages=xix+482|isbn=0-471-09725-X|mr=720547}}</ref><ref name="BasicDantzig">Richard W. Cottle1, ed. ''The Basic George B. Dantzig''. Stanford Business Books, Stanford University Press, Stanford, California, 2003. (Selected papers by2000 [[George B. Dantzig]])<http:/ref><ref name="DantzigThapa1">[[George B/www. Dantzig]] and Mukund Ncomputer. Thapaorg/csdl/mags/cs/2000/01/c1022.html 1997.html ''Linear programming 1: Introduction''. Springer-Verlag.version]</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]] |date=February 2002 | title = The many facets of linear programming | journal = Mathematical Programming | volume = 91 | issue = 3 | doi = 10.1007/s101070100261 | pages=417–436}} (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