Content deleted Content added
m →top: rm space |
→Implementation: {{main}} |
||
Line 248:
===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'' + 1)-by-(''m'' + ''n'' + 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''', '''I''']. This implementation is referred to as the "''standard'' simplex algorithm". The storage and computation overhead are 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 '''B'''.<ref name="DantzigThapa2"/>
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" >M. Padberg, ''Linear Optimization and Extensions'', Second Edition, Springer-Verlag, 1999.</ref><ref>Dmitris Alevras and Manfred W. Padberg, ''Linear Optimization and Extensions: Problems and Extensions'', Universitext, Springer-Verlag, 2001. (Problems from Padberg with solutions.)</ref><ref name="MarosMitra" >{{cite book|last1=Maros|first1=István|last2=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=1-4020-7332-1}}</ref>
| |||