Content deleted Content added
No edit summary |
|||
Line 55:
\end{align}</math>
It is much easier to perform algebraic manipulation on inequalities in this form. In inequalities where ≥ appears such as the second one, some authors refer to the variable introduced as a {{anchor|Surplus variable}}'' surplus variable''.
Third, each unrestricted variable is eliminated from the linear program. This can be done in two ways, one is by solving for the variable in one of the equations in which it appears and then eliminating the variable by substitution. The other is to replace the variable with the difference of two restricted variables. For example, if <math>z_1</math> is unrestricted then write
Line 103:
==Pivot operations==
The geometrical operation of moving from a basic feasible solution to an adjacent basic feasible solution is implemented as a ''pivot operation''. First, a nonzero ''pivot element'' is selected in a nonbasic column. The row containing this element is [[Elementary matrix#Row-multiplying transformations|multiplied]] by its reciprocal to change this element to 1, and then multiples of the row are added to the other rows to change the other entries in the column to 0. The result is that, if the pivot element is in a row ''r'', then the column becomes the ''r''-th column of the identity matrix. The variable for this column is now a basic variable, replacing the variable which corresponded to the ''r''-th column of the identity matrix before the operation. In effect, the variable corresponding to the pivot column enters the set of basic variables and is called the ''entering variable'', and the variable being replaced leaves the set of basic variables and is called the ''leaving variable''. The tableau is still in canonical form but with the set of basic variables changed by one element.<ref name="DantzigThapa1"/><ref name="NeringTucker"/>
==Algorithm==
Line 119:
===Leaving variable selection===
Once the pivot column has been selected, the choice of pivot row is largely determined by the requirement that the resulting solution be feasible. First, only positive entries in the pivot column are considered since this guarantees that the value of the entering variable will be nonnegative. If there are no positive entries in the pivot column then the entering variable can take any
Next, the pivot row must be selected so that all the other basic variables remain positive. A calculation shows that this occurs when the resulting value of the entering variable is at a minimum. In other words, if the pivot column is ''c'', then the pivot row ''r'' is chosen so that
Line 167:
==Finding an initial canonical tableau==
In general, a linear program will not be given in the canonical form and an equivalent canonical tableau must be found before the simplex algorithm can start. This can be accomplished by the introduction of ''artificial variables''. Columns of the identity matrix are added as column vectors for these variables. If the b value for a constraint equation is negative, the equation is negated before adding the identity matrix columns. This does not change the set of feasible solutions or the optimal solution, and it ensures that the slack variables will constitute an initial feasible solution. The new tableau is in canonical form but it is not equivalent to the original problem. So a new objective function, equal to the sum of the artificial variables, is introduced and the simplex algorithm is applied to find the minimum; the modified linear program is called the ''Phase I'' problem.<ref>{{harvtxt|Murty|1983|p=60}}</ref>
The simplex algorithm applied to the Phase I problem must terminate with a minimum value for the new objective function since, being the sum of nonnegative variables, its value is bounded below by 0. If the minimum is 0 then the artificial variables can be eliminated from the resulting canonical tableau producing a canonical tableau equivalent to the original problem. The simplex algorithm can then be applied to find the solution; this step is called ''Phase II''. If the minimum is positive then there is no feasible solution for the Phase I problem where the artificial variables are all zero. This implies that the feasible region for the original problem is empty, and so the original problem has no solution.<ref name="DantzigThapa1"/><ref name="NeringTucker"/><ref name="Padberg"/>
Line 249:
===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
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" >
Line 261:
{{cite journal|title=New finite pivoting rules for the simplex method|first=Robert G.|last=Bland|journal=Mathematics of Operations Research|volume=2|issue=2|date=May 1977|pages=103–107|doi=10.1287/moor.2.2.103|jstor=3689647|mr=459599|s2cid=18493293|url=https://semanticscholar.org/paper/874b988e359f63c8068226c53ef0a9bcd54e5e4d}}</ref><ref>{{harvtxt|Murty|1983|p=79}}</ref> Another pivoting algorithm, the [[criss-cross algorithm]] never cycles on linear programs.<ref>There are abstract optimization problems, called [[oriented matroid]] programs, on which Bland's rule cycles (incorrectly) while the [[criss-cross algorithm]] terminates correctly.</ref>
History-based pivot rules such as [[Zadeh's rule]] and [[Cunningham's rule]] also try to circumvent the issue of stalling and cycling by keeping track of how often particular variables are being used
===Efficiency===
Line 321:
{{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
| |||