|
Linear Programming:
tableaux
Solves a (standard form) Linear Programming problem
by the simplex method in tabular form (tableaux, wide). |
|
|
| Optimization |
|
Maximization or
minimization. • |
| |
Case 1 — H&L Wyndor; z*max = 36, X=(2, 6, 2) |
| C |
Coefficients in the objective function,
z = C X (C, row; X, column)
(Here, 0 for artificial variables.)
• |
A | B
(m×n,
m×1) |
Constraints, A X = B
(m equality constraints): row(1), b(1)
[ : row(i), b(i), i = 2..n]
(':' = 'new line'.)
• |
| Artificial variables |
|
Which artificial variables (0 if none). • |
| Big M |
|
Big M (∞), ignored if not necessary. • |
| Initial basis (ordered) |
| Variables (m)
in initial basis, ordered (as in A). • |
|
Solves a Linear Programming
problem supplied in standard form, by Dantzig's simplex method
in tabular form (each iteration shown as a tableau).
In the standard form, all the constraints must be given as equations
(usually after insertion of slack or artificial variables).
If an artificial variable is present, its coefficient will be made
±M, according to the given direction
of optimization. |
| References: |
Plate: LP_tableaux |
• Dantzig, George, discoverer of the
simplex method.
• OTC 'The simplex method'
(MCS, ANL).
• Waner, Stefan, and
Steven Costenoble:
'The Simplex Method' ← Tutorials (Dept. of Mathematics, Hofstra University).
• Artificial variables.pdf.
• Reveliotis,
Spiridon: 'Linear Programming
(Georgia Tech).
• At Wolfram 'MathWorld';
at 'Wikipedia'.
• 1596-03-31: Descartes, RenĂ©, birthday. |
