Simplex algorithm: Difference between revisions

Revision as of 00:55, 19 September 2014

Revision as of 01:12, 19 September 2014

Line 4:

[[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 }} (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 [[TheoTheodore 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|authorlink=Gilbert Strang|title=Karmarkar's algorithm and its place in applied mathematics|journal=[[The Mathematical Intelligencer]]|date=1 June 1987|

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.