www.egwald.com Egwald Web Services

Egwald Web Services
Domain Names
Web Site Design

Egwald Website Search Twitter - Follow Elmer Wiens Radio 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 Home Operations Research Home Game Theory Home Page Linear Programming Home Page Graphical Solution Simplex Algorithm Linear Programming Algorithm Two Person Game Your LP Problem Try Problems
 

Operations Research - Linear Programming - Primal Simplex Tableaux Generator

by

Elmer G. Wiens

Egwald's popular web pages are provided without cost to users.
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.


Warning: Undefined array key "sformtable" in /services/webpages/e/g/egwald.ca/public/operationsresearch/lpprimalsimplexgenerator.php on line 150
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.


Fatal error: Uncaught TypeError: Unsupported operand types: string * int in /services/webpages/e/g/egwald.ca/public/operationsresearch/functions/primalsimplex.php:64 Stack trace: #0 /services/webpages/e/g/egwald.ca/public/operationsresearch/functions/primalsimplex.php(237): primaltableau(Array, 3, 3, 1, 1, 1, 0, 3, 2, 1.0, 3, 2, 1.0, Array, 0) #1 /services/webpages/e/g/egwald.ca/public/operationsresearch/lpprimalsimplexgenerator.php(247): primalsimplex(Array, Array, Array, 3, 3, 1, 1, 1, 0) #2 {main} thrown in /services/webpages/e/g/egwald.ca/public/operationsresearch/functions/primalsimplex.php on line 64
Tableau0
  b0 x01 x02 x03 s01 s02 s*03 row
sum		b / Ûk
L018511110089