Simplex algorithm

Simplex algorithm

In mathematical optimization theory, the simplex algorithm, created by the American mathematician George Dantzig in 1947, is a popular algorithm for numerical solution of the linear programming problem. The journal "Computing in Science and Engineering" listed it as one of the top 10 algorithms of the century. ["Computing in Science and Engineering", volume 2, no. 1, 2000]

An unrelated, but similarly named method is the Nelder-Mead method or downhill simplex method due to Nelder & Mead (1965) and is a numerical method for optimising many-dimensional unconstrained problems, belonging to the more general class of search algorithms.

In both cases, the method uses the concept of a simplex, which is a polytope of "N" + 1 vertices in "N" dimensions: a line segment in one dimension, a triangle in two dimensions, a tetrahedron in three-dimensional space and so forth.

Description

A linear programming problem consists of a collection of linear inequalities on a number of real variables and a given linear function (on these real variables) which is to be maximized or minimized.

In geometric terms we are considering a closed convex polytope, "P", defined by intersecting a number of half-spaces in "n"-dimensional Euclidean space; each half-space is the area which lies on one side of a hyperplane. If the objective is to maximise a linear functional "L"("x"), consider the hyperplanes "H"("c") defined by L(x) = c; as "c" increases, these form a parallel family. If the problem is well-posed, we want to find the largest value of "c" such that "H"("c") intersects "P" (if there is no such largest value of "c", this isn't a reasonable question for optimization as it stands). In this case we can show that the optimum value of "c" is attained on the boundary of "P". Methods for finding this optimum point on P work in several ways: some attempt to improve a possible point by moving through the interior of "P" (so-called "interior point methods"); others start and remain on the boundary searching for an optimum.

The simplex algorithm follows the latter method. The idea is to move along the facets of "P" in search of the optimum, from point to point. Note that, unless the optimum occurs on an edge or face that is parallel to "H", the optimum will be unique and occur at a vertex of the polytope. If an optimum is found on an edge or face that is parallel to "H" then the optimum is not unique and can be obtained at any point on the edge or face. Since the simplex algorithm is concerned only with finding a single optimal point (even if other equally-optimal points exist), it is possible to look solely at moves skirting the edge of a simplex, ignoring the interior. The algorithm specifies how this is to be done.

We start at some vertex of the polytope, and at every iteration we choose an adjacent vertex such that the value of the objective function does not decrease. If no such vertex exists, we have found a solution to the problem. But usually, such an adjacent vertex is nonunique, and a "pivot rule" must be specified to determine which vertex to pick. Various pivot rules exist.

In 1972, Klee and MintyGreenberg, cites: V. Klee and G.J. Minty. "How Good is the Simplex Algorithm?" In O. Shisha, editor, "Inequalities, III", pages 159–175. Academic Press, New York, NY, 1972] gave an example of a linear programming problem in which the polytope "P" is a distortion of an "n"-dimensional cube. They showed that the simplex method as formulated by Dantzig visits all 2"n" vertices before arriving at the optimal vertex. This shows that the worst-case complexity of the algorithm is exponential time. Similar examples have been found for other pivot rules. It is an open question if there is a pivot rule with polynomial time worst-case complexity.

Nevertheless, the simplex method is remarkably efficient in practice. Attempts to explain this employ the notion of average complexity or (recently) smoothed complexity.

Other algorithms for solving linear programming problems are described in the linear programming article.

Problem input

Consider a linear programming problem,: maximize mathbf{c}^T mathbf{x} : subject to mathbf{A}mathbf{x} le mathbf{b}, , mathbf{x} ge 0. The simplex algorithm requires the linear programming problem to be in augmented form. The problem can then be written as follows in matrix form:: Maximize "Z" in:: egin{bmatrix} 1 & -mathbf{c}^T & 0 \ 0 & mathbf{A} & mathbf{I} end{bmatrix} egin{bmatrix} Z \ mathbf{x} \ mathbf{x}_s end{bmatrix} = egin{bmatrix} 0 \ mathbf{b} end{bmatrix}: mathbf{x}, , mathbf{x}_s ge 0 where x are the variables from the "standard form", xs are the introduced slack variables from the augmentation process, c contains the optimization coefficients, A and b describe the system of constraint equations, and "Z" is the variable to be maximized.

The system is typically underdetermined, since the number of variables exceeds the number of equations. The difference between the number of variables and the number of equations gives us the "degrees of freedom" associated with the problem. Any solution, optimal or not, will therefore include a number of variables of arbitrary value. The simplex algorithm uses zero as this arbitrary value, and the number of variables with value zero equals the degrees of freedom.

Variables of nonzero value are called "basic variables", and variables of zero value are called "nonbasic variables" in the simplex algorithm. [This definition is problematic, since basic variables can also take zero value.]

This form simplifies finding the initial "basic feasible solution" (BF), since all variables from the "standard form" can be chosen to be nonbasic (zero), while all new variables introduced in the "augmented form" are basic (nonzero), since their value can be trivially calculated (mathbf{x}_{s,i} = mathbf{b}_{i} for them, since the augmented problem matrix is diagonal on its right half).

Revised simplex algorithm

Matrix form of the simplex algorithm

At any iteration of the simplex algorithm, the tableau will be of this form:: egin{bmatrix} 1 & mathbf{c}_B^T mathbf{B}^{-1}mathbf{A} -mathbf{c}^T & mathbf{c}_B^T mathbf{B}^{-1} \ 0 & mathbf{B}^{-1}mathbf{A} & mathbf{B}^{-1} end{bmatrix} egin{bmatrix} Z \ mathbf{x} \ mathbf{x}_s end{bmatrix} = egin{bmatrix} mathbf{c}_B^T mathbf{B}^{-1} mathbf{b} \ mathbf{B}^{-1}mathbf{b} end{bmatrix}where mathbf{c}_B are the coefficients of basic variables in the c-matrix; and B is the columns of [mathbf{A} , mathbf{I}] corresponding to the basic variables.

It is worth noting that B and mathbf{c}_B are the only variables in this equation (except "Z" and x of course). Everything else is constant throughout the algorithm.

Algorithm

* Choose a "basic feasible solution" (BF) as shown above: This implies that B is the identity matrix, and mathbf{c}_B is a zero-vector.

* While nonoptimal solution:
** Determine direction of highest gradient
*: Choose the variable associated with the coefficient in mathbf{c}_B^{T} mathbf{B}^{-1}mathbf{A} -mathbf{c}^{T} that has the highest "negative" magnitude. This nonbasic variable, which we call the "entering basic", will be increased to help maximize the problem.
** Determine maximum step length
*: Use the egin{bmatrix} mathbf{B}^{-1}mathbf{A} & mathbf{B}^{-1} end{bmatrix} egin{bmatrix} mathbf{x} \ mathbf{x}_s end{bmatrix} = mathbf{B}^{-1}mathbf{b} subequation to determine which basic variable reaches zero first when the "entering basic" is increased. This variable, which we call the "leaving basic" then becomes nonbasic. This operation only involves a single division for each basic variable, since the existing basic-variables occur diagonally in the tableau.
** Rewrite problem
*: Modify B and mathbf{c}_B to account for the new basic variables. This will automatically make the tableau diagonal for the existing and new basic variables.
** Check for improvement
*: Repeat procedure until no further improvement is possible, meaning all the coefficients of mathbf{c}_B^{T} mathbf{B}^{-1}mathbf{A} -mathbf{c}^{T} are positive. Procedure is also terminated if all coefficients are zero, and the algorithm has walked in a circle and revisited a previous state.

Common Implementations of The Revised Simplex Method

* The Bartels-Golub Method
* The Sparse Bartels-Golub Method
* The Forrest-Tomlin Method
* Reid’s Method

See also

* Nelder-Mead method
* Fourier-Motzkin elimination
* Bland's anti-cycling rule
* Karmarkar's algorithm

References

Further reading

* Greenberg, Harvey J., "Klee-Minty Polytope Shows Exponential Time Complexity of Simplex Method" University of Colorado at Denver (1997) [http://glossary.computing.society.informs.org/notes/Klee-Minty.pdf PDF download]
* Frederick S. Hillier and Gerald J. Lieberman: "Introduction to Operations Research", 8th edition. McGraw-Hill. ISBN 0-07-123828-X
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. "Introduction to Algorithms", Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 29.3: The simplex algorithm, pp.790–804.
* Hamdy A. Taha: "Operations Research: An Introduction", 8th ed., Prentice Hall, 2007. ISBN 0-13-188923-0
* Richard B. Darst: "Introduction to Linear Programming: Applications and Extensions"

External links

* [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.
** [http://www2.isye.gatech.edu/~spyros/Panagiotis/JAVAstuff/HTML/Sim.html A step-by-step simplex algorithm solver] Solve your own LP problem. "Note: this does not work well. Sample problem: minimize z=x1+x2 subject to 2x1+3x2<=6 and -x1+x2<=1 should give 0 as answer. This applet gives the same answer for both maximize and minimize problem."
*Java-based [http://www-fp.mcs.anl.gov/otc/Guide/CaseStudies/simplex/ interactive simplex tool] hosted by Argonne National Laboratory.
* [http://people.hofstra.edu/faculty/Stefan_Waner/RealWorld/tutorialsf4/frames4_3.html Tutorial for The Simplex Method] by Stefan Waner, hofstra.edu. Interactive worked example.
* [http://learning.mazoo.net/archives/001240.html A simple example - step by step] by Mazoo's Learning Blog.
* [http://www.math.cuhk.edu.hk/~wei/lpch3.pdf Simplex Method] A good tutorial for Simplex Method with examples (also two-phase and M-method).
* [http://www.phpsimplex.com/en/index.htm PHPSimplex] Other good tutorial for Simplex Method with the Two-Phase Simplex and Graphical methods, examples, and a tool to solve Simplex problems online.
* [http://people.hofstra.edu/faculty/Stefan_Waner/RealWorld/simplex.html Simplex Method Tool] Quick-loading JavaScript-based web page that solves Simplex problems


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • simplex algorithm — simplex method …   Accounting dictionary

  • Simplex (disambiguation) — Simplex may refer to:*Simplex, a term in geometry *Simplex, a one way communications channel * Simplex was a trade name used by British railway locomotive manufacturers, The Motor Rail Tramcar Co Ltd *SimplexGrinnell, a brand of fire protection… …   Wikipedia

  • simplex method — simplex algorithm A method of obtaining a linear programming solution by producing a series of tableaux. The technique, a step by step iterative process, tests a number of feasible solutions in turn until the final optimal solution is obtained.… …   Accounting dictionary

  • Simplex — For other uses, see Simplex (disambiguation). A regular 3 simplex or tetrahedron In geometry, a simplex (plural simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimension. Specifically, an n… …   Wikipedia

  • Simplex-Verfahren — Das Simplex Verfahren läuft von einer Ecke eines LP Polyeders zur nächsten, bis keine Verbesserung mehr möglich ist. Das Simplex Verfahren (auch Simplex Algorithmus) ist ein Optimierungsverfahren der Numerik zur Lösung linearer… …   Deutsch Wikipedia

  • Simplex-Algorithmus — Das Simplex Verfahren läuft von einer Ecke eines LP Polyeders zur nächsten, bis keine Verbesserung mehr möglich ist. Das Simplex Verfahren (auch Simplex Algorithmus) ist ein Optimierungsverfahren der Numerik zur Lösung linearer… …   Deutsch Wikipedia

  • Simplex-Tableau — Das Simplex Verfahren läuft von einer Ecke eines LP Polyeders zur nächsten, bis keine Verbesserung mehr möglich ist. Das Simplex Verfahren (auch Simplex Algorithmus) ist ein Optimierungsverfahren der Numerik zur Lösung linearer… …   Deutsch Wikipedia

  • Algorithm — Flow chart of an algorithm (Euclid s algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≤ A yields yes… …   Wikipedia

  • Simplex noise — is a method for constructing an n dimensional noise function comparable to Perlin noise ( classic noise) but with a lower computational overhead, especially in larger dimensions. Ken Perlin designed the algorithm in 2001 [Ken Perlin, Noise… …   Wikipedia

  • Criss-cross algorithm — This article is about an algorithm for mathematical optimization. For the naming of chemicals, see crisscross method. The criss cross algorithm visits all 8 corners of the Klee–Minty cube in the worst case. It visits 3 additional… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”