www.egwald.com Egwald Web Services

Egwald Web Services
Domain Names
Web Site Design

Egwald Website Search JOIN US AS A FACEBOOK FAN Twitter - Follow Elmer WiensRadio Podcasts - Geraldos Hour

 

Statistics Programs - Econometrics and Probability Economics - Microeconomics & Macroeconomics Operations Research - Linear Programming and Game Theory Egwald's Mathematics Egwald's Optimal Control
Egwald HomeOperations Research HomeGame Theory Home PageLinear Programming Home  PageGraphical SolutionSimplex AlgorithmLinear Programming AlgorithmTwo Person GameYour LP ProblemTry Problems
 

Operations Research - Linear Programming - Primal 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: JOIN US AS A FACEBOOK FAN
Follow Elmer Wiens on Twitter: Twitter - Follow Elmer Wiens

Graphical Solution | Simplex Algorithm | Primal Simplex Tableaux Generator | Dual Simplex Algorithm | Dual Simplex Tableaux Generator
Economics Application - Profit Maximization | Economics Application - Least Cost Formula

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

The primal 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 x1 + 10 x2 + 17 x3 subject to
L1: 1.0 x1 + 1.0 x2 + 1.0 x3 <= 85
L2: 1.25 x1 + 0.5 x2 + 1.0 x3 >= 90
L3: 0.6 x1 + 1.0 x2 + 0.5 x3 = 55
      x1 >= 0; x2 >= 0; x3 >= 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:    
Number of variables:
n =
Number of constraints:
m =
Number of <= constraints:
m1 =
Number of >= constraints:
m2 =
Number of = constraints:
m3 =
 
               

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.

FormTable =
My L.P. Problem
P = x1 + x2 + x3 subject to
L1 x1 + x2 + x3 <=
L2 x1 + x2 + x3 >=
L3 x1 + x2 + x3 =

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 primal 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.


Primal Simplex Algorithm.

The standard form for the initial primal simplex tableau is:

Initial Tableau
bAI3
0-cTO3T

The primal simplex algorithm calculates a sequence of tableaux. Tableauk has the form:

Tableauk
ßUB
µtTyT
=
Tableauk
ßÛ
µØ

after consolidating the center 2 by 2 block of matrices.

The "three-phase method" of the primal 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 primal program;

Phase II - generate tableaux that increase the value of µ, without dropping back into Phase 0 or I, until Ø >= 0 for all sign restricted variables, i.e. find a feasible primal program that maximizes the objective function.




Phase 0: Drive the artificial variables from the basis.

Tableau0
  b0 x01 x02 x03 s01 s02 s*03 row
sum
b / Ûk
L0185111100890
L02-90-1.25-0.5-1010-91.750
L03550.610.500158.10
P00-15-10-17000-42 

Basis for Tableau0: [s1, s2, s3, ]. Value of Objective Function = 0.

Proceed to the next tableau as follows:

Phase 0: Drive the artificial variables from the basis.

A. In Tableau0:

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

2. Select a nonzero element in row L3 as pivot: Û3,2 = 1. The pivot column = 2.

B. To create Tableau1:

3. Compute row L13 = L03 / (1).

4. Subtract multiples of row L13 from all other rows of Tableau0 so that x12 = e3 in Tableau1.

Phase I: Goal: get ß >= 0.

Tableau1
  b1 x11 x12 x13 s11 s12 s*13 row
sum
b / Ûk
L11 = L01 - (1) * L13300.400.510-130.975
L12 = L02 - (-0.5) * L13-62.5-0.950-0.75010.5-62.765.789
L13 = L03 / (1)550.610.500158.191.667
P1 = P0 - (-10) * L13550-90-120010539 

Basis for Tableau1: [s1, s2, x2, ]. Value of Objective Function = 550.

Proceed to the next tableau as follows:

Phase 0: Complete.

Phase I: Goal: get ß >= 0.

A. In Tableau1:

1. Select a target row, r, with br < 0: b12 = -62.5, r = 2.

2. Select any column, col, with a negative entry in row = 2 as the pivot column: col = 1 associated with Û2,1 = -0.95 and constraint L2.

3. Compute the ratios bi / Ûi,1 as per the last column. Select the row with the least positive ratio as the pivot row: row = 2 associated with constraint L2. Thus Û2,1 = -0.95 is the pivot; variable s2 will leave the basis; variable x21 will enter the basis.

B. To create Tableau2:

4. Compute row L22 = L12 / (-0.95).

5. Subtract multiples of row L22 from all other rows of Tableau1 so that x21 = e2 in Tableau2.

Phase II: Goal: get Ø >= 0.

Tableau2
  b2 x21 x22 x23 s21 s22 s*23 row
sum
b / Ûk
L21 = L11 - (0.4) * L223.684000.18410.421-0.7894.58.75
L22 = L12 / (-0.95)65.789100.7890-1.053-0.526660
L23 = L13 - (0.6) * L2215.526010.02600.6321.31618.524.583
P2 = P1 - (-9) * L221142.10500-4.8950-9.4745.2631133 

Basis for Tableau2: [s1, x1, x2, ]. Value of Objective Function = 1142.11.

Proceed to the next tableau as follows:

Phase 0: Complete.

Phase I: Complete.

Phase II: Goal: get Ø >= 0.

A. In Tableau2:

1. Select the pivot column, col, with the most negative value in Ø: col = 5, Ø5 = -9.474: s32 will enter the basis.

2. Compute the ratios bi / Ûi,5 as per the last column. Select the row with the least positive ratio as the pivot row: row = 1 associated with constraint L1. Thus Û1,5 = 0.421 is the pivot; variable s1 will leave the basis; variable s32 will enter the basis.

B. To create Tableau3:

3. Compute row L31 = L21 / (0.421).

4. Subtract multiples of row L31 from all other rows of Tableau2 so that s32 = e1 in Tableau3.

Tableau3
  b3 x31 x32 x33 s31 s32 s*33 row
sum
b / Ûk
L31 = L21 / (0.421)8.75000.4382.3751-1.87510.68820
L32 = L22 - (-1.053) * L3175101.252.50-2.577.2560
L33 = L23 - (0.632) * L311001-0.25-1.502.511.750
P3 = P2 - (-9.47) * L31122500-0.7522.50-12.51234.25 

Basis for Tableau3: [s2, x1, x2, ]. Value of Objective Function = 1225.

Proceed to the next tableau as follows:

Phase 0: Complete.

Phase I: Complete.

Phase II: Goal: get Ø >= 0.

A. In Tableau3:

1. Select the pivot column, col, with the most negative value in Ø: col = 3, Ø3 = -0.75: x43 will enter the basis.

2. Compute the ratios bi / Ûi,3 as per the last column. Select the row with the least positive ratio as the pivot row: row = 1 associated with constraint L1. Thus Û1,3 = 0.438 is the pivot; variable s2 will leave the basis; variable x43 will enter the basis.

B. To create Tableau4:

3. Compute row L41 = L31 / (0.438).

4. Subtract multiples of row L41 from all other rows of Tableau3 so that x43 = e1 in Tableau4.

Tableau4
  b4 x41 x42 x43 s41 s42 s*43 row
sum
b / Ûk
L41 = L31 / (0.438)200015.4292.286-4.28624.4290
L42 = L32 - (1.25) * L4150100-4.286-2.8572.85746.7140
L43 = L33 - (-0.25) * L4115010-0.1430.5711.42917.8570
P4 = P3 - (-0.75) * L41124000026.5711.714-15.7141252.571 

Basis for Tableau4: [x3, x1, x2, ]. Value of Objective Function = 1240.

Phase 0: Complete.

Phase I: Complete.

Phase II: Complete.

Primal Solution: [x3, x1, x2, ] = [20, 50, 15, ];   P = 1240.

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

Dual Solution: [y1, y2, y3, ] = [26.571, 1.714, -15.714, ];   D = 1240.

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

 
   

      Copyright © Elmer G. Wiens:   Egwald Web Services       All Rights Reserved.    Inquiries