Simplex algorithm

The graph illustrates the Simplex algorithm solving a linear programming problem with two variables.

In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is an algorithm for linear programming.

The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are not actually used in the method, but one interpretation of it is that it operates on simplicial cones, and these become proper simplices with an additional constraint. 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 constraints applied to the objective function.

A system of linear inequalities defines a polytope as a feasible region. The simplex algorithm begins at a starting vertex and moves along the edges of the polytope until it reaches the vertex of the optimal solution. Polyhedron of simplex algorithm in 3D

The simplex algorithm operates on linear programs in the canonical form

maximize 𝐱≥0

with 𝐱=(x1,…,xn) are the variables of the problem, 𝐱 such that x1≥5

a new variable, x1 from the linear program. In this way, all lower bound constraints may be changed to non-negativity restrictions.

Second, for each remaining inequality constraint, a new variable, called a slack variable, is introduced to change the constraint to an equality constraint. This variable represents the difference between the two sides of the inequality and is assumed to be non-negative. For example, the inequalities

z1 is unrestricted then write

𝐀𝐱=𝐛,∀ xi≥0

It is also useful to assume that the rank of [1−𝐜T0𝟎𝐀𝐛]

The first row defines the objective function and the remaining rows specify the constraints. The zero in the first column represents the zero vector of the same dimension as the vector p (the number of rows in 0, 1, 1 in its column is equal to the B, then the result is a tableau in canonical form.

Let

cT
B  from the objective function. This process is called pricing out and results in a canonical tableau

−𝐜¯T) of the tableau is negative. (If the objective function is to be minimized, one would instead select a column where the entry in the objective row is positive.)

There is typically more than one column with a negative entry in the objective row, and the choice of which one to add to the set of basic variables is guided by one of several entering variable choice rules such as Devex algorithm.

If none of the entries in the objective row is negative then no choice of entering variable can be made and the solution is in fact at the maximum. It is easily seen to be maximal since the objective row now corresponds to an equation of the form

ârc > 0. This is called the minimum ratio test. If there is more than one row for which the minimum is achieved then a dropping variable choice rule can be used to make the determination.

Example

edit

Z=2x+3y+4z

Subject to

x=y=z=0,s=10,t=15.

Columns 2, 3, and 4 can be selected as pivot columns. For this example, suppose column 4 is selected. The values of z resulting from the choice of rows 2 and 3 as pivot rows are 10/1 = 10 and 15/3 = 5 respectively. Of these the minimum is 5, so row 3 must be the pivot row. Performing the pivot produces

Z=20−23x−113y−43t

so the maximum value of Z is 20.

Finding an initial canonical tableau

edit

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.

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.

Example

edit

Consider the linear program

Maximize

x=y=0,z=5 violates the first constraint. This new problem is represented by the (non-canonical) tableau

[10574002501−2−3−4000003211010002530115]

Select column 5 as a pivot column, so the pivot row must be row 4, and the updated tableau is

[702501300710150011725]

This is, fortuitously, already optimal and so the optimum value for the original linear program is 130/7. This value is "worse" than 20 which is to be expected for a problem which is more constrained.

Advanced topics

edit

Implementation

edit

Another method to analyze the performance of the simplex algorithm studies the behavior of worst-case scenarios under small perturbation – are worst-case scenarios stable under a small change (in the sense of structural stability), or do they become tractable? This area of research, called smoothed analysis, was introduced specifically to study the simplex method. Indeed, the running time of the simplex method on input with noise is polynomial in the number of variables and the magnitude of the perturbations.

Other algorithms

edit

Other algorithms for solving linear-programming problems are described in the linear-programming article. Another basis-exchange pivoting algorithm is the criss-cross algorithm. There are polynomial-time algorithms for linear programming that use interior point methods: these include Khachiyan's ellipsoidal algorithm, Karmarkar's projective algorithm, and path-following algorithms. The Big-M method is an alternative strategy for solving a linear program, using a single-phase simplex. Cohen et al. is the representative of a branch of algorithms that apply fast matrix multiplication algorithms to linear programs.

Linear-fractional programming

edit

Strang, Gilbert (1 June 1987). "Karmarkar's algorithm and its place in applied mathematics". The Mathematical Intelligencer. 9 (2): 4–10. doi:10.1007/BF03025891. ISSN 0343-6993. MR 0883185. S2CID 123541868.

↑ Dantzig, George (May 1987). "Origins of the simplex method" (PDF). In Nash, Stephen G. (ed.). A History of Scientific Computing. Association for Computing Machinery. pp. 141–151. doi:10.1145/87252.88081. ISBN 978-0-201-50814-7. Archived (PDF) from the original on May 29, 2015.

↑ Murty (1983, Theorem 3.3)

↑ Murty (1983, p. 143, Section 3.13)

1 2 Murty (1983, p. 137, Section 3.8)

1 2 3 George B. Dantzig and Mukund N. Thapa. 1997. Linear programming 1: Introduction. Springer-Verlag.

1 2 3 4 Evar D. Nering and Albert W. Tucker, 1993, Linear Programs and Related Problems, Academic Press. (elementary)

1 2 Robert J. Vanderbei, Linear Programming: Foundations and Extensions, 3rd ed., International Series in Operations Research & Management Science, Vol. 114, Springer Verlag, 2008.