Simplex algorithm: Difference between revisions

Revision as of 11:31, 28 July 2014

Revision as of 08:38, 29 July 2014

Line 128:

=== Example ===

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

Consider the linear program

:Minimize

Line 267:

==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|id = {{citeseerx|10.1.1.36.7658}} |publisher=Springer Netherlands|issn=0254-5330|unused_data=<!-- authorlink1=Tamás Terlaky -->}}</ref><ref>{{cite articlenews|first1=Komei|last1=Fukuda|first2=Tamás|last2=Terlaky|title=Criss-cross methods: A fresh view on pivot algorithms |journal=Mathematical Programming: Series&nbsp;B|volume=79|number=1—3|pages=369–395|editors=Thomas&nbsp;M. Liebling and Dominique de&nbsp;Werra|publisher=North-Holland Publishing&nbsp;Co. |___location=Amsterdam|year=1997|doi=10.1007/BF02614325|MRmr=1464775}}</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"/>

==Linear-fractional programming==

Line 273:

[[Linear-fractional programming|Linear–fractional programming]] (LFP) is a generalization of [[linear programming]] (LP) where the objective function of linear programs are [[linear functional|linear functions]] and the objective function of a linear–fractional program is a ratio of two linear functions. In other words, a linear program is a fractional–linear program in which the denominator is the constant function having the value one everywhere. A linear–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=3-88538-404-3|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}}

</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}}

</ref> or by the [[criss-cross algorithm]].<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|id=[http://www.cas.mcmaster.ca/~terlaky/files/dut-twi-96-103.ps.gz PDF preprint]}}</ref>.

== See also ==

Line 286:

{{reflist|2}}

==References==

* {{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=harv}}