Egwald Operations Research - Linear Programming - Dual Simplex Tableau Generator

Egwald Web Services
Domain Names
Web Site Design

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:

example problem | your l.p. problem | simplex algorithm | references

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:

Primal Linear Program
Maximize the Objective Function (P)
P = 15 x₁ + 10 x₂ + 17 x₃ subject to
L1: 1.0 x₁ + 1.0 x₂ + 1.0 x₃ <= 85
L2: 1.25 x₁ + 0.5 x₂ + 1.0 x₃ >= 90
L3: 0.6 x₁ + 1.0 x₂ + 0.5 x₃ = 55
x₁ >= 0; x₂ >= 0; x₃ >= 0

with diagram:

Primal Linear Programming 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.

L.P. Problem Name: My L.P. Problem
Number of variables: n = 3	Number of constraints: m = 3
Number of <= constraints: m1 = 1	Number of >= constraints: m2 = 1	Number of = constraints: m3 = 1

Certain restrictions apply to to the parameters:
m = m1 + m2 + m3; n <= 6; m <= 10; n > 0;
m > 0; m1 >= 0; m2 >= 0; m3 >= 0.

Your L.P. Parameter Form.

Your Linear Programming Problem's Parameters
L.P. Problem Name:
Number of variables: n =	Number of constraints: m =
Number of <= constraints: m1 =	Number of >= constraints: m2 =	Number of = constraints: m3 =

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.

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₃
0	-c^T	O₃^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⁰
	b⁰	x⁰₁	x⁰₂	x⁰₃	s⁰₁	s⁰₂	s*⁰₃	row sum
L⁰₁	85	1	1	1	1	0	0	89
L⁰₂	-90	-1.25	-0.5	-1	0	1	0	-91.75
L⁰₃	55	0.6	1	0.5	0	0	1	58.1
P⁰	0	-15	-10	-17	0	0	0	-42
	0	0	0	0	0	0	0	0

Basis for Tableau⁰: [s₁, s₂, s₃, ]. Value of Objective Function = 0.

Proceed to the next tableau as follows:

Phase 0: Drive the artificial variables from the basis.

A. In Tableau⁰:

1. Select an artificial variable in the basis: s^*₃. The pivot row = 3.

2. Select a nonzero element in row L₃ as pivot: Û_3,2 = 1. The pivot column = 2.

B. To create Tableau¹:

3. Compute row L¹₃ = L⁰₃ / (1).

4. Subtract multiples of row L¹₃ from all other rows of Tableau⁰ so that x¹₂ = e₃ in Tableau¹.

Phase I: Goal: get � >= 0.

Tableau¹
	b¹	x¹₁	x¹₂	x¹₃	s¹₁	s¹₂	s*¹₃	row sum
L¹₁ = L⁰₁ - (1) * L¹₃	30	0.4	0	0.5	1	0	-1	30.9
L¹₂ = L⁰₂ - (-0.5) * L¹₃	-62.5	-0.95	0	-0.75	0	1	0.5	-62.7
L¹₃ = L⁰₃ / (1)	55	0.6	1	0.5	0	0	1	58.1
P¹ = P⁰ - (-10) * L¹₃	550	-9	0	-12	0	0	10	539
-P¹ / L¹₃	0	15	0	24	0	0	0	0

Basis for Tableau¹: [s₁, s₂, x₂, ]. Value of Objective Function = 550.

Proceed to the next tableau as follows:

Phase 0: Complete.

Phase I: Goal: get � >= 0.

A. In Tableau¹:

1. Select a target column, tcol, with �_tcol < 0: �¹₁ = -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. Compute the ratios -� / L₃ 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₂ will leave the basis; variable x₁ will enter the basis.

B. To create Tableau²:

4. Compute row L²₃ = L¹₃ / (0.6).

5. Subtract multiples of row L²₃ from all other rows of Tableau¹ so that x₁ = e₃ in Tableau².

Tableau²
	b²	x²₁	x²₂	x²₃	s²₁	s²₂	s*²₃	row sum
L²₁ = L¹₁ - (0.4) * L²₃	-6.667	0	-0.667	0.167	1	0	-1.667	-7.833
L²₂ = L¹₂ - (-0.95) * L²₃	24.583	0	1.583	0.042	0	1	2.083	29.292
L²₃ = L¹₃ / (0.6)	91.667	1	1.667	0.833	0	0	1.667	96.833
P² = P¹ - (-9) * L²₃	1375	0	15	-4.5	0	0	25	1410.5
-P² / L²₃	0	0	0	5.4	0	0	0	0

Basis for Tableau²: [s₁, s₂, x₁, ]. Value of Objective Function = 1375.

Proceed to the next tableau as follows:

Phase 0: Complete.

Phase I: Goal: get � >= 0.

A. In Tableau²:

1. Select a target column, tcol, with �_tcol < 0: �²₃ = -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. Compute the ratios -� / L₃ 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₁ will leave the basis; variable x₃ will enter the basis.

B. To create Tableau³:

4. Compute row L³₃ = L²₃ / (0.833).

5. Subtract multiples of row L³₃ from all other rows of Tableau² so that x₃ = e₃ in Tableau³.

Phase II: Goal: get � >= 0.

Tableau³
	b³	x³₁	x³₂	x³₃	s³₁	s³₂	s*³₃	row sum
L³₁ = L²₁ - (0.167) * L³₃	-25	-0.2	-1	0	1	0	-2	-27.2
L³₂ = L²₂ - (0.042) * L³₃	20	-0.05	1.5	0	0	1	2	24.45
L³₃ = L²₃ / (0.833)	110	1.2	2	1	0	0	2	116.2
P³ = P² - (-4.5) * L³₃	1870	5.4	24	0	0	0	34	1933.4
-P³ / L³₁	0	27	24	0	0	0	0	0

Basis for Tableau³: [s₁, s₂, x₃, ]. 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³:

1. Select a pivot row, row, with b³_row < 0: row = 1 associated with b³₁ = -25.

2. Compute the ratios -� / L₁ 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₁ will leave the basis; variable x₂ will enter the basis.

B. To create Tableau⁴:

3. Compute row L⁴₁ = L³₁ / (-1).

4. Subtract multiples of row L⁴₁ from all other rows of Tableau³ so that x₂ = e₁ in Tableau⁴.

Tableau⁴
	b⁴	x⁴₁	x⁴₂	x⁴₃	s⁴₁	s⁴₂	s*⁴₃	row sum
L⁴₁ = L³₁ / (-1)	25	0.2	1	-0	-1	-0	2	27.2
L⁴₂ = L³₂ - (1.5) * L⁴₁	-17.5	-0.35	0	0	1.5	1	-1	-16.35
L⁴₃ = L³₃ - (2) * L⁴₁	60	0.8	0	1	2	0	-2	61.8
P⁴ = P³ - (24) * L⁴₁	1270	0.6	0	0	24	0	-14	1280.6
-P⁴ / L⁴₂	0	1.714	0	0	0	0	0	0

Basis for Tableau⁴: [x₂, s₂, x₃, ]. 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⁴:

1. Select a pivot row, row, with b⁴_row < 0: row = 2 associated with b⁴₂ = -17.5.

2. Compute the ratios -� / L₂ 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₂ will leave the basis; variable x₁ will enter the basis.

B. To create Tableau⁵:

3. Compute row L⁵₂ = L⁴₂ / (-0.35).

4. Subtract multiples of row L⁵₂ from all other rows of Tableau⁴ so that x₁ = e₂ in Tableau⁵.

Tableau⁵
	b⁵	x⁵₁	x⁵₂	x⁵₃	s⁵₁	s⁵₂	s*⁵₃	row sum
L⁵₁ = L⁴₁ - (0.2) * L⁵₂	15	0	1	0	-0.143	0.571	1.429	17.857
L⁵₂ = L⁴₂ / (-0.35)	50	1	-0	-0	-4.286	-2.857	2.857	46.714
L⁵₃ = L⁴₃ - (0.8) * L⁵₂	20	0	0	1	5.429	2.286	-4.286	24.429
P⁵ = P⁴ - (0.6) * L⁵₂	1240	0	0	0	26.571	1.714	-15.714	1252.571
-P⁵ / L⁵_-1	0	0	0	0	0	0	0	0

Basis for Tableau⁵: [x₂, x₁, x₃, ]. Value of Objective Function = 1240.

Phase 0: Complete.

Phase I: Complete.

Phase II: Complete.

Primal Solution: [x₂, x₁, x₃, ] = [15, 50, 20, ]; P = 1240.

(Primal x variables not in the basis have a value of 0).

Dual Solution: [y₁, y₂, y₃, ] = [26.571, 1.714, -15.714, ]; D = 1240.

End of the Linear Programming Dual Simplex Method

Linear Programming References.

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 Edition. New York: MacMillan, 1976.
Wu, Nesa, and Richard Coppins. Linear Programming and Extensions. New York: McGraw-Hill, 1981.