"The tremendous power of the simplex method is a constant surprise to me."
- George Dantzig, History of Mathematical Programming: A Collection of Personal Reminiscences
The Simplex method is an algebraic way to solve linear programming problems. Once the technique is understood only basic arithmetic is required to actually process the problem, and it removes the need for graph plotting and hence the need to directly find extreme points for the feasible region or to solve the equations for that point. It was developed in 1947 by George Dantzig after his work at the Pentagon during world war II, and has stood the test of time as perhaps the key tool of linear programming despite the development of barrier or interior-point methods.
The process works by converting the equations which define the linear programming problem into a tableau, and then by performing operations on that tableau generate further tableau closer to the optimal solution until the optimality condition is reached, in which case the solution is optimal.
Dido observes: "the possible complexity of the algorithm should also be mentioned. As there are nCm sets of basis vectors that produce feasible solutions, that becomes the upper bound, making it an exponential time algorithm in the unlikely worst case. More likely the complexity is of the order m+n"
An example of the Simplex method
Maximise Z= 10x + 12y subject to the following constraints:
- 3x + 3y ≤ 120
- 2x + 4y ≤ 150
- x ≥ 0 , y ≥ 0
Note that often linear programming questions are not simply given in equations but as descriptions of "real" problems, such as a company that wishes to maximise its profit given the various products it can supply and the limitations on their production. However, it is usually easy to turn these into linear equations such as the above. If it is required to minimise Z = 10x + 12y then it is easiest to maximise Z = -(10x +12y).
Given a set of inequalities such as these, it is necessary to introduce slack variables to create equalities. For our example,
- 3x + 3y ≤ 120 becomes 3x + 3y + s = 120
- 2x + 4y ≤ 150 becomes 2x + 4y + t = 150
Where s,t are slack variables the value of which is unknown but which ensure that whatever values of x,y are chosen the
totals are 120 and 150 respectively.
This means that the problem is now to maximise:
Z = 10x + 12y + 0s + 0t. This
objective function is then re-written in the form Z - 10x -12y -0s -0t =0. This allows the
initial tableau to be created as follows:
Basic Variable x y s t Value
s 3 3 1 0 120
t 2 4 0 1 150
------------------------------------------------------
Z -10 -12 0 0 0
Where the top two lines are from the inequalities and the bottom line is the
objective row. The purpose of the Simplex method is to maximise the value of Z, that is the value in the bottom right corner which is initially zero.
The optimality condition is as follows:
If the objective row of a tableau has zero entries in the columns labelled by basic variables and no negative entries in the columns labelled by non-basic variables then the solution represented by the tableau is optimal.
To reach this condition it is necessary to identify pivots and use these to convert non-basic variables (s,t) into basic variables (x,y). At each stage the pivotal column chosen is the one with the most negative value in the objective row: in this example the y column. The pivot is then identified by the examination of θ values. These are calculated for all rows except the objective row by dividing the entry in the "value" column by the entry in the pivotal column (in this instance the "y" column). The pivot is then the entry in the pivotal column which generates the smallest (non negative) θ value.
In this example the θ values are 120/3 = 40 for the s row and 150/4 = 37.5 for the t row, and hence the pivot is the 4 in column y, row t.
Having identified the pivot, divide all values in the pivotal row by the value of the pivot, meaning that the pivot becomes 1, and replace the label of that row for the label of the pivotal column.
Basic Variable x y s t Value
s 3 3 1 0 120
y 0.5 1 0 0.25 37.5
------------------------------------------------------
Z -10 -12 0 0 0
Now each other value in the pivotal column must be reduced to zero. To do this, the relevant multiple of the pivotal row is added or subtracted for every entry on the row. This includes the objective row. For example, to turn the entry of 3 in row s, column y into 0 it is necessary to subtract 3 lots of the entry in row y, column y. Thus 3 lots of row y is subtracted from row s, meaning the entry in the x column becomes 3 - 3*0.5, the s column becomes 1- 3*0 and so on. Similarly 12 lots of row y is added to row Z to give the next tableau:
Basic Variable x y s t Value
s 1.5 0 1 -0.75 7.5
y 0.5 1 0 0.25 37.5
------------------------------------------------------
Z -4 0 0 3 450
This does not satisfy the optimality condition so the process is repeated. This time the pivotal column is x, and the pivotal row is s. Dividing the pivotal row by the pivot (1.5) and exchanging labels gives:
Basic Variable x y s t Value
x 1 0 2/3 -1/2 5
y 0.5 1 0 0.25 37.5
------------------------------------------------------
Z -4 0 0 3 450
Then addition or subtraction of the pivotal row from the others gives:
Basic Variable x y s t Value
x 1 0 2/3 -1/2 5
y 0 1 -1/3 1/2 35
------------------------------------------------------
Z 0 0 8/3 1 470
The entries for the basic variables x,y are now equal to zero, and the entries under the non-basic variables s,t are non-negative. Hence this tableau represents the optimal solution. The values of x and y are 5 and 35 from their respective rows, and this gives a maximum value of Z which is equal to 470.