
Operations Research  Linear Programming  Dual Simplex Algorithm
by
Elmer G. Wiens
Egwald's popular web pages are provided without cost to users. Please show your support by joining Egwald Web Services as a Facebook Fan:
Follow Elmer Wiens on Twitter:
Graphical Solution 
Simplex Algorithm 
Primal Simplex Tableaux Generator 
Dual Simplex Algorithm 
Dual Simplex Tableaux Generator
Economics Application  Profit Maximization 
Economics Application  Least Cost Formula
introduction  example problem  simplex algorithm  unbounded & unfeasible problems  degeneracy  references
The dual simplex method is often used in situations where the primal problem has a number of equality constraints generating artificial variables in the l.p. canonical form. Like in the primal simplex method, the standard form for the dual simplex method assumes all constraints are <=, or = constraints, but places no restrictions on the signs of the RHS b_{i} variables.
The dual simplex algorithm consists of three phases. Phase 0 is identical to Phase 0 of the primal simplex method, as the artificial variables are replaced by the primal variables in the basis. However, the dual simplex algorithm in Phase 1 searches for a feasible dual program, while in Phase 2, it searches for the optimal dual program, simultaneously generating the optimal primal program.
Solve an example problem.
The following example will be solved using the dual simplex algorithm (Restrepo, Linear Programming, 8390), to illustrate this technique. It is the same problem solved with the primal simplex algorithm.
Primal Linear Program
Maximize the Objective Function (P)
P = 15 x_{1} + 10 x_{2} + 15 x_{3} subject to
L1: 1.0 x_{1} + 1.0 x_{2} + 1.0 x_{3} <= 85
L2: 1.25 x_{1} + 0.5 x_{2} + 1.0 x_{3} <= 90
L3: 0.6 x_{1} + 1.0 x_{2} + 0.5 x_{3} = 51.5
x_{1} >= 0; x_{2} >= 0; x_{3} >= 0

The following diagram illustrates the constraints and the objective function at its maximum value.
PPlane passing through (81.667, 0, 0), (0, 122.5, 0), and (40, 10, 35) when P = 1225
L1plane passing through (63.33, 21.67, 0), (0, 85, 0), (0, 0, 85), and (20, 0, 65)
L2plane passing through (72, 0, 0), (63.33, 21.67, 0), and (20, 0, 65)
L3plane passing through (67.63, 10.92, 0), (0, 51.5, 0), and (40, 10, 35)
L1plane & L2plane intersect along the line passing through (63.33, 21.67, 0) and (20, 0, 65)
With P = 1225, the Pplane intersects the primal feasible set only at the point (40, 10, 35).

If necessary, multiply any = constraints by 1 to get the RHS negative, and introduce the slack variables into the statement of the problem. The variable s_{3} is an artificial variable, since the third constraint is an equation.
Primal Linear Program
Maximize the Objective Function (P)
P = 15 x_{1} + 10 x_{2} + 15 x_{3} subject to
L1: 1.0 x_{1} + 1.0 x_{2} + 1.0 x_{3} + s_{1} = 85
L2: 1.25 x_{1} + 0.5 x_{2} + 1.0 x_{3} + s_{2} = 90
L3: 0.6 x_{1}  1.0 x_{2}  0.5 x_{3} + s_{3} = 51.5
x_{1} >= 0; x_{2} >= 0; x_{3} >= 0
s_{1} >= 0; s_{2} >= 0; s_{3} >= 0

Dual Linear Program
Minimize the Objective Function (D)
D = 85 y_{1} + 90 y_{2}  51.5 y_{3} subject to
G1: 1.0 y_{1} + 1.25 y_{2}  0.6 y_{3}  t_{1} = 15
G2: 1.0 y_{1} + 0.5 y_{2}  1.0 y_{3}  t_{2} = 10
G3: 1.0 y_{1} + 1.0 y_{2}  0.5 y_{3}  t_{3} = 15
y_{1} >= 0; y_{2} >= 0; y_{3} sign unrestriced
t_{1} >= 0; t_{2} >= 0; t_{3} >= 0

The standard forms for the primal and dual problems can be stated with the slack variables s and t:
Primal Linear Program
Maximize the Objective Function (P)
P = c^{T} x subject to



Dual Linear Program
Minimize the Objective Function (D)
D = y^{T} b subject to


A x + s = b, x >= 0, s >= 0

y^{T} A  t^{T} = c^{T}, y >= 0, t >= 0

Dual Simplex Algorithm
The standard form for the initial dual simplex tableau is:
Initial Tableau 
b  A  I_{3} 
0  c^{T}  O_{3}^{T} 
In the dual simplex algorithm, a sequence of tableaux are calculated. A given Tableau^{k} has the form:
Tableau^{k} 
ß  U  B 
µ  t^{T}  y^{T} 

= 

after consolidating the center 2 by 2 block of matrices.
Phase 0  drive all artificial variables (associated with = constraints) to zero, i.e. eliminate them from the basis;
Phase I  find a tableau with Ø >= 0, i.e. a feasible dual program;
Phase II  generate tableaux that decrease the value of µ turning ß >= 0, without dropping back into Phase 0 or I, i.e. find a feasible basic dual program that minimizes the objective function D.

Using the initial canonical from, label rows & columns. Use the data from the example to fill in the initial tableau. Label column s_{3} with a * to indicate that it is an artificial variable. Add the column of row sums used to check arithmetic, and the row labelled P / L, that will be used in Phases I and II.
Tableau^{0} 

b^{0} 
x^{0}_{1} 
x^{0}_{2} 
x^{0}_{3} 
s^{0}_{1} 
s^{0}_{2} 
s^{0}_{3}* 
row sum 
L^{0}_{1} 
85  1.00 
1.00  1.00 
1.00  0.00 
0.00  89 
L^{0}_{2} 
90  1.25 
0.50  1.00 
0.00  1.00 
0.00  93.75 
L^{0}_{3} 
51.5  0.60 
1.00  0.50 
0.00  0.00 
1.00  52.6 
P^{0} 
0.00  15 
10  15 
0.00  0.00 
0.00  40 
P / L 
 
 
 
 
Tableau^{0} solution:
Variables s_{1}, s_{2}, s_{3} are the basic variables, since their columns are e_{1}^{T} = (1, 0, 0, 0), e_{2}^{T} = (0, 1, 0, 0), and e_{3}^{T} = (0, 0, 1, 0). The primal program is s^{T} = (85, 90, 51.5), with x^{T} = (0.00, 0.00, 0.00). The primal objective function has the value P = c^{T}x = c_{1}x_{1} + c_{2}x_{2} + c_{3}x_{3} = 0.00.
Proceed to the next tableau as follows:
Phase 0. Drive the artificial variables from the basis.
A. In Tableau^{0}:
1. Select an artificial variable in the basis: s^{*}_{3} = e_{3}.
2. Select a nonzero element in row L3 as pivot: x_{3,1} = .6.
B. To Create Tableau^{1}:
3. Compute row L^{1}_{3} = L^{0}_{3} / (0.6).
4. Subtract multiples of row L^{1}_{3} from all other rows of Tableau^{0} so that x^{1}_{1} = e_{3} in Tableau^{1}.
Tableau^{1} 

b^{1} 
x^{1}_{1} 
x^{1}_{2} 
x^{1}_{3} 
s^{1}_{1} 
s^{1}_{2} 
s^{1}_{3}* 
row sum 
L^{1}_{1} = L^{0}_{1}  1.0 L^{1}_{3} 
0.8333  0.00 
0.6667  0.1667 
1.00  0.00 
1.667  1.3334 
L^{1}_{2} = L^{0}_{2}  1.25 L^{1}_{3} 
17.292  0.00 
1.5834  0.0417 
0.00  1.00 
2.0834  15.8333 
L^{1}_{3} = L^{0}_{3} / (0.6) 
85.8333  1.00 
1.6667  0.8333 
0.00  0.00 
1.6667  87.6667 
P^{1} = P^{0}  (15) L^{1}_{3} 
1287.5  0.00 
15  2.5 
0.00  0.00 
25  1275 
P^{1} / L^{1}_{1} 
 
22.5  15 
 
 
Tableau^{1} solution:
Basis: x_{1}, s_{1}, s_{2}.
The primal unfeasible program: x^{T} = (85.8333, 0.00, 0.00); s^{T} = (0.8333, 17.292, 0).
The primal objective function has the value P = 1287.5.
Proceed to the next tableau as follows: Since the artificial variable s^{*}_{3} associated with the = constraint is not in the basis, Phase 0 is complete.
Phase I. Obtain nonnegative entries in Ø (the second last row) for the signrestricted primal and slack variables. Since Ø^{1}_{3} = 2.5 is negative, the algorithm is in Phase I.
Goal: Generate a feasible dual program so that Ø >= 0.
A. In Tableau^{1}:
1. Select a target column, col, with Ø_{col} < 0: Ø^{1}_{3} = 2.5, col = 3.
2. Select any row, r, with a positive entry in col 3 as the pivot row: row = 1 associated with constraint L_{1}: x_{1,3} = 0.1667.
3. Compute the ratios Ø / L_{1} as per the last row. Discard ratios which are not positive and ratios associated with artificial variables.
Select the column with the least positive ratio as the pivot column: 15 in col = 3. Thus x_{1,3} = 0.1667 is the pivot; slack variable s_{1} will leave the basis; x_{3} will enter the basis.
B. To Create Tableau^{2}:
4. Compute row L^{2}_{1} = L^{1}_{1} / (0.1667).
5. Subtract multiples of row L^{2}_{1} from all other rows of Tableau^{1} so that x^{2}_{3} = e_{1} in Tableau^{2}.
Tableau^{2} 

b^{2} 
x^{2}_{1} 
x^{2}_{2} 
x^{2}_{3} 
s^{2}_{1} 
s^{2}_{2} 
s^{2}_{3}* 
row sum 
L^{2}_{1} = L^{1}_{1} / ( 0.1667) 
5.00  0.00 
4.00  1.00 
6.00  0.00 
10.00  8.00 
L^{2}_{2} = L^{1}_{2}  (0.0417 ) L^{2}_{1} 
17.50  0.00 
1.75  0.00 
0.25  1.00 
2.5  15.5 
L^{2}_{3} = L^{1}_{3}  0.8333 L^{2}_{1} 
90.00  1.00 
5.00  0.00 
5.00  0.00 
10.00  81 
P^{2} = P^{1}  (2.5000 ) L^{2}_{1} 
1275  0.00 
5.00  0.00 
15.00  0.00 
0.00  1295 
P^{2} / L^{2}_{2} 
 
2.8571  
 
 
Tableau^{2} solution:
Basis: x_{1}, x_{2}, s_{2}.
The primal unfeasible program: x^{T} = (83.75, 1.25, 0.00); s^{T} = (0, 15.313, 0).
The primal objective function has the value P = 1275.
Proceed to the next tableau as follows: Since Ø^{2} >= 0. The algorithm is in Phase II.
Phase II. Goal: Generate an optimal program so that ß >= 0.
A. In Tableau^{2}:
1. Select a target row, r, with b_{r} < 0: b^{2}_{2} = 17.5, r = 2.
2. Compute the ratios Ø / L_{2} as per the last row. Discard ratios which are not positive, and ratios associated with artificial variables.
Select the column with the least positive ratio as the pivot column: 2.8571 in col = 2. Thus x_{2,2} = 1.75 is the pivot; slack variable s_{2} will leave the basis; x_{2} will enter the basis.
B. To Create Tableau^{3}:
3. Compute row L^{3}_{2} = L^{2}_{2} / (1.75).
4. Subtract multiples of row L^{3}_{2} from all other rows of Tableau^{2} so that x^{3}_{2} = e_{2} in Tableau^{3}.
Tableau^{3} 

b^{3} 
x^{3}_{1} 
x^{3}_{2} 
x^{3}_{3} 
s^{3}_{1} 
s^{3}_{2} 
s^{3}_{3}* 
row sum 
L^{3}_{1} = L^{2}_{1}  (4.00) L^{3}_{2} 
35  0.00 
0.00  1.00 
5.4286  2.2857 
4.2857  43.4286 
L^{3}_{2} = L^{2}_{2} / (1.75) 
10.00  0.00 
1.00  0.00 
0.1429  0.5714 
1.4286  8.8571 
L^{3}_{3} = L^{2}_{3}  5.00 L^{3}_{2} 
40.00  1.00 
0.00  0.00 
4.2857  2.8571 
2.8571  36.7143 
P^{3} = P^{2}  5.00 L^{3}_{2} 
1225  0.00 
0.00  0.00 
15.7143  2.8571 
7.1429  1250.7143 
P / L 
 
 
 
 
Tableau^{3} solution:
Basis: x_{1}, x_{2}, x_{3}.
The primal feasible program: x^{T} = (40, 10, 35); s^{T} = (0, 0, 0).
The primal objective function has the value P = 1225.
For this tableau, b >= 0, the artificial variable, s^{*}_{3}, is not in the basis, and all entries in the last row corresponding to the variables x_{1}, x_{2}, x_{3}, s_{1}, and s_{2} are nonnegative.
The dual simplex algorithm terminates, since all conditions of Phase I and II are satisfied.
The optimal programs are:
x = (40, 10, 35), s = (0, 0, 0); y = (15.71, 2.86, 7.14), t = (0, 0, 0); P = 1225.
Unbounded and Unfeasible Problems.
As shown on the graphical web page, and on the simplex algorithm web page,
the next example has an unbounded primal solution, with an unfeasible dual problem.
Primal Linear Program
Maximize the Objective Function (P)
P = 15 x_{1} + 10 x_{2} subject to
L1: 0 x_{1} + 1.0 x_{2} <= 50
L2: 1.5 x_{1} + 1.0 x_{2} <= 20
x_{1} >= 0; x_{2} >= 0

Dual Linear Program
Minimize the Objective Function (D)
D = 50 y_{1}  20 y_{2} subject to
G1: 0 y_{1}  1.5 y_{2} >= 15
G2: 1.0 y_{1} + 1.0 y_{2} >= 10
y_{1} >= 0; y_{2} >= 0

To solve this problem using the dual simplex algorithm, set up the initial tableau as usual:
Tableau^{0} 

b^{0} 
x^{0}_{1} 
x^{0}_{2} 
s^{0}_{1} 
s^{0}_{2} 
row sum 
L^{0}_{1} 
50  0.00 
1.00  1.00 
0.00  52 
L^{0}_{2} 
20  1.5 
1.00  0.00 
1.00  19.5 
P^{0} 
0.00  15 
10  0.00 
0.00  25 
P / L 
 
10  
 
Phase 0: Complete since there are no artificial variables.
Phase I: Since Ø^{0}_{1} = 15 and Ø^{0}_{2} = 10 are negative, the algorithm is in Phase I.
Goal: Generate a feasible program so that Ø >= 0.
A. In Tableau^{0}:
1. Select a target column, col, with Ø_{col} < 0: Ø^{1}_{2} = 10, col = 2.
2. Select any row, r, with a positive entry in col 2 as the pivot row: row = 1 associated with constraint L_{1}: x_{1,2} = 1.00. (Note: must select target col = 2 for this to work)
3. Compute the ratios Ø / L_{1} as per the last row. Discard ratios which are not positive and ratios associated with artificial variables. Select the column with the least positive ratio as the pivot column: 10 in col = 2. Thus x_{1,2} = 1.00 is the pivot; slack variable s_{1} will leave the basis; x_{2} will enter the basis.
B. To Create Tableau^{1}:
4. Compute row L^{1}_{1} = L^{1}_{0} / (1.00).
5. Subtract multiples of row L^{1}_{1} from all other rows of Tableau^{0} so that x^{1}_{2} = e_{1} in Tableau^{1}.
Tableau^{1} 

b^{1} 
x^{1}_{1} 
x^{1}_{2} 
s^{1}_{1} 
s^{1}_{2} 
row sum 
L^{1}_{1} = L^{0}_{1} / 1 
50  0.00 
1.00  1.00 
0.00  52 
L^{1}_{2} = L^{0}_{2}  1 L^{1}_{1} 
70.00  1.50 
0.00  1.00 
1.00  71.50 
P^{1} = P^{0}  (15) L^{1}_{1} 
500  15.00 
0.00  10.00 
0.00  495 
P / L 
 
 
 
Phase I: Since Ø^{1}_{1} = 15 is negative, the algorithm is in Phase I. However, no positive entry exists in the target column = 1, so no pivot exists. The algorithm breaks down. The dual program is unfeasible.
As the following diagram shows, the primal objective function P is unbounded since it intersects the feasible set for any large positive number = P.
Degeneracy and Cycling.
The primal simplex algorithm breaks down in degenerate situations in the primal l.p. problem. Since the dual simplex algorithm works on the dual l.p. problem, primal degeneracy will not affect its execution. To see this,
click to pop a new window where this
primal degenerate problem is solved with the dual simplex method.
Linear Programming References.
 Budnick, Frank S., Richard Mojena, and Thomas E. Vollmann. Principles of Operations Research for Management. Homewood: Irwin, 1977.
 Dantzig, G., A. Orden, and P. Wolfe. "The Generalized Simplex Method for Minimizing a Linear Form under Inequality Restraints." Pacific Journal of Mathematics. 8, (1955): 183195.

Dantzig, George B. Linear Programming and Extensions. Princeton: Princeton U P, 1963.

Dorfman, R., P. Samuelson, and R. Solow. Linear Programming and Economics Analysis. New York: McGrawHill, 1958.

Hadley, G. Linear Algebra. Reading, Mass.: AddisonWesley, 1961.

Hadley, G. Linear Programming. Reading, Mass.: AddisonWesley, 1962.
 Hillier, Frederick S. and Gerald J. Lieberman. Operations Research.. 2nd ed. San Francisco: HoldenDay, 1974.

Karlin, S. Mathematical Methods in the Theory of Games and Programming. Vols. I & II. Reading, Mass.: AddisonWesley, 1959.
 Loomba, N. Paul. Linear Programming: An Introductory Analysis. New York: McGrawHill, 1964.
 Press, William H., Brian P. Flannery, Saul A. Teukolsky, and William T. Vetterling. Numerical Recipes: The Art of Scientific Computing. Cambridge: Cambridge UP, 1989.

Saaty, Thomas L. Mathematical Methods of Operations Research. New York: McGrawHill, 1959.
 Sierksma, Gerard. Linear and Integer Programming: Theory and Practice. 2nd ed. New York: Marcel Dekker, 2002.

Sposito, Vincent. Linear and Nonlinear Programming. Ames, Iowa: Iowa UP, 1975.

Sposito, Vincent. Linear Programming with Statistical Applications. Ames, Iowa: Iowa UP, 1989.

Strang, Gilbert. Linear Algebra and Its Applications.3rd ed. San Diego: Harcourt, 1988.

Restrepo, Rodrigo A. Theory of Games and Programming: Mathematics Lecture Notes. Vancouver: University of B.C., 1967.

Restrepo, Rodrigo A. Linear Programming and Complementarity. Vancouver: University of B.C., 1994.

Taha, Hamdy A. Operations Research: An Introduction. 2nd ed. New York: MacMillan, 1976.
 Wagner, Harvey M. Principles of Management Science: With Applications to Executive Decisions. 2nd ed. Englewood Cliffs: PrenticeHall, 1975.
 Wagner, Harvey M. Principles of Operations Research: With Applications to Managerial Decisions. 2nd ed. Englewood Cliffs: PrenticeHall, 1975.
 Wu, Nesa, and Richard Coppins. Linear Programming and Extensions. New York: McGrawHill, 1981.

