Operations Research - Linear Programming - Dual Simplex Tableaux Generator

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:

The dual simplex method transforms an initial tableau into a final tableau containing the solutions to the primal and dual problems. Each stage of the algorithm generates an intermediate tableau as the algorithm gropes towards a solution.

This web page permits you to enter your own linear programming problem and generate these tableaux with a user friendly interface. You can specify up to 6 variables and 10 constraints in the primal problem, with any mixture of <=, >=, and = constraints.

To illustrate the procedure you need to follow, consider the problem:

To generate the form used to enter the l.p. data you must set the parameters that specify your l.p. problem as I have done below for the problem above.

After you fill in your form and click submit paramters, a web page will pop with a table, like the one below, where you can enter the data of your l.p. problem. Notice that you need neither multiply = constrainst by -1, nor convert >= constraints to <= constraints.

FormTable =

After you fill in your data and click submit, the program will automatically calculate a sequence of tableaux that solves the primal and dual l.p. problems. Examine the tableaux that follow to see how the dual simplex method proceeds to find the solution.

To perform a sensitivity analysis on your linear programming problem, change the data in the table above, and click Submit L.P. again.

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}

The dual simplex algorithm calculates a sequence of tableaux. Tableau^{k} has the form:

Tableau^{k}

ß

U

B

µ

t^{T}

y^{T}

=

Tableau^{k}

ß

Û

µ

Ø

after consolidating the center 2 by 2 block of matrices.

The "three-phase method" of the dual simplex algorithm:

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.

Phase 0: Drive the artificial variables from the basis.

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

1

1

1

0

0

89

L^{0}_{2}

-90

-1.25

-0.5

-1

0

1

0

-91.75

L^{0}_{3}

55

0.6

1

0.5

0

0

1

58.1

P^{0}

0

-15

-10

-17

0

0

0

-42

0

0

0

0

0

0

0

0

Basis for Tableau^{0}: [s_{1}, s_{2}, s_{3}, ]. Value of Objective Function = 0.

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}. The pivot row = 3.

2. Select a nonzero element in row L_{3} as pivot: Û_{3,2} = 1. The pivot column = 2.

B. To create Tableau^{1}:

3. Compute row L^{1}_{3} = L^{0}_{3} / (1).

4. Subtract multiples of row L^{1}_{3} from all other rows of Tableau^{0} so that x^{1}_{2} = e_{3} in Tableau^{1}.

Phase I: Goal: get Ø >= 0.

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) * L^{1}_{3}

30

0.4

0

0.5

1

0

-1

30.9

L^{1}_{2} = L^{0}_{2} - (-0.5) * L^{1}_{3}

-62.5

-0.95

0

-0.75

0

1

0.5

-62.7

L^{1}_{3} = L^{0}_{3} / (1)

55

0.6

1

0.5

0

0

1

58.1

P^{1} = P^{0} - (-10) * L^{1}_{3}

550

-9

0

-12

0

0

10

539

-P^{1} / L^{1}_{3}

0

15

0

24

0

0

0

0

Basis for Tableau^{1}: [s_{1}, s_{2}, x_{2}, ]. Value of Objective Function = 550.

Proceed to the next tableau as follows:

Phase 0: Complete.

Phase I: Goal: get Ø >= 0.

A. In Tableau^{1}:

1. Select a target column, tcol, with Ø_{tcol} < 0: Ø^{1}_{1} = -9, tcol = 1.

2. Select any row, r, with a positive entry in tcol = 1 as the pivot row: row = 3 associated with Û_{3,1} = 0.6 and constraint L_{3}.

3. Compute the ratios -Ø / L_{3} 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: col = 1 associated with 15. Thus Û_{3,1} = 0.6 is the pivot; variable x_{2} will leave the basis; variable x_{1} will enter the basis.

B. To create Tableau^{2}:

4. Compute row L^{2}_{3} = L^{1}_{3} / (0.6).

5. Subtract multiples of row L^{2}_{3} from all other rows of Tableau^{1} so that x_{1} = e_{3} 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.4) * L^{2}_{3}

-6.667

0

-0.667

0.167

1

0

-1.667

-7.833

L^{2}_{2} = L^{1}_{2} - (-0.95) * L^{2}_{3}

24.583

0

1.583

0.042

0

1

2.083

29.292

L^{2}_{3} = L^{1}_{3} / (0.6)

91.667

1

1.667

0.833

0

0

1.667

96.833

P^{2} = P^{1} - (-9) * L^{2}_{3}

1375

0

15

-4.5

0

0

25

1410.5

-P^{2} / L^{2}_{3}

0

0

0

5.4

0

0

0

0

Basis for Tableau^{2}: [s_{1}, s_{2}, x_{1}, ]. Value of Objective Function = 1375.

Proceed to the next tableau as follows:

Phase 0: Complete.

Phase I: Goal: get Ø >= 0.

A. In Tableau^{2}:

1. Select a target column, tcol, with Ø_{tcol} < 0: Ø^{2}_{3} = -4.5, tcol = 3.

2. Select any row, r, with a positive entry in tcol = 3 as the pivot row: row = 3 associated with Û_{3,3} = 0.833 and constraint L_{3}.

3. Compute the ratios -Ø / L_{3} 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: col = 3 associated with 5.4. Thus Û_{3,3} = 0.833 is the pivot; variable x_{1} will leave the basis; variable x_{3} will enter the basis.

B. To create Tableau^{3}:

4. Compute row L^{3}_{3} = L^{2}_{3} / (0.833).

5. Subtract multiples of row L^{3}_{3} from all other rows of Tableau^{2} so that x_{3} = e_{3} in Tableau^{3}.

Phase II: Goal: get ß >= 0.

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} - (0.167) * L^{3}_{3}

-25

-0.2

-1

0

1

0

-2

-27.2

L^{3}_{2} = L^{2}_{2} - (0.042) * L^{3}_{3}

20

-0.05

1.5

0

0

1

2

24.45

L^{3}_{3} = L^{2}_{3} / (0.833)

110

1.2

2

1

0

0

2

116.2

P^{3} = P^{2} - (-4.5) * L^{3}_{3}

1870

5.4

24

0

0

0

34

1933.4

-P^{3} / L^{3}_{1}

0

27

24

0

0

0

0

0

Basis for Tableau^{3}: [s_{1}, s_{2}, x_{3}, ]. Value of Objective Function = 1870.

Proceed to the next tableau as follows:

Phase 0: Complete.

Phase I: Complete.

Phase II: Goal: get ß >= 0.

A. In Tableau^{3}:

1. Select a pivot row, row, with b^{3}_{row} < 0: row = 1 associated with b^{3}_{1} = -25.

2. 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: col = 2 associated with 24. Thus Û_{1,2} = -1 is the pivot; variable s_{1} will leave the basis; variable x_{2} will enter the basis.

B. To create Tableau^{4}:

3. Compute row L^{4}_{1} = L^{3}_{1} / (-1).

4. Subtract multiples of row L^{4}_{1} from all other rows of Tableau^{3} so that x_{2} = e_{1} in Tableau^{4}.

Tableau^{4}

b^{4}

x^{4}_{1}

x^{4}_{2}

x^{4}_{3}

s^{4}_{1}

s^{4}_{2}

s*^{4}_{3}

row sum

L^{4}_{1} = L^{3}_{1} / (-1)

25

0.2

1

0

-1

0

2

27.2

L^{4}_{2} = L^{3}_{2} - (1.5) * L^{4}_{1}

-17.5

-0.35

0

0

1.5

1

-1

-16.35

L^{4}_{3} = L^{3}_{3} - (2) * L^{4}_{1}

60

0.8

0

1

2

0

-2

61.8

P^{4} = P^{3} - (24) * L^{4}_{1}

1270

0.6

0

0

24

0

-14

1280.6

-P^{4} / L^{4}_{2}

0

1.714

0

0

0

0

0

0

Basis for Tableau^{4}: [x_{2}, s_{2}, x_{3}, ]. Value of Objective Function = 1270.

Proceed to the next tableau as follows:

Phase 0: Complete.

Phase I: Complete.

Phase II: Goal: get ß >= 0.

A. In Tableau^{4}:

1. Select a pivot row, row, with b^{4}_{row} < 0: row = 2 associated with b^{4}_{2} = -17.5.

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: col = 1 associated with 1.714. Thus Û_{2,1} = -0.35 is the pivot; variable s_{2} will leave the basis; variable x_{1} will enter the basis.

B. To create Tableau^{5}:

3. Compute row L^{5}_{2} = L^{4}_{2} / (-0.35).

4. Subtract multiples of row L^{5}_{2} from all other rows of Tableau^{4} so that x_{1} = e_{2} in Tableau^{5}.

Tableau^{5}

b^{5}

x^{5}_{1}

x^{5}_{2}

x^{5}_{3}

s^{5}_{1}

s^{5}_{2}

s*^{5}_{3}

row sum

L^{5}_{1} = L^{4}_{1} - (0.2) * L^{5}_{2}

15

0

1

0

-0.143

0.571

1.429

17.857

L^{5}_{2} = L^{4}_{2} / (-0.35)

50

1

0

0

-4.286

-2.857

2.857

46.714

L^{5}_{3} = L^{4}_{3} - (0.8) * L^{5}_{2}

20

0

0

1

5.429

2.286

-4.286

24.429

P^{5} = P^{4} - (0.6) * L^{5}_{2}

1240

0

0

0

26.571

1.714

-15.714

1252.571

-P^{5} / L^{5}_{-1}

0

0

0

0

0

0

0

0

Basis for Tableau^{5}: [x_{2}, x_{1}, x_{3}, ]. Value of Objective Function = 1240.