|
Linear Programming (revised simplex)
Solves an LP problem in standard form by the
revised simplex method. |
|
|
| Optimization |
|
Maximization or minimization. • |
| CT |
Coefficients in the objective function,
z = CT x .
|
• Use (here) 0 for the artificial variables
(RHS b ≥ 0).
• Decimal mark: American (.) or European (,)
• Separation by blanks or (Excel type) tabs. • |
A | b
(m×n,
m×1) |
Constraints, A x = b
(m equality constraints)
|
Insert:
row(1), b(1) [:row(i), b(i), i = 2..m]
(':' = 'new line') • |
| Artificial variables |
|
Which artificial variables (0 if none). • |
| Big M |
|
Big M (∞), ignored if unnecessary. • |
| Initial basis |
| Variables (m)
in initial basis. • |
| First graph basis |
|
First basis for graph (avoiding artificials). • |
| Show values ? |
Test: (0, 1, 2) |
Shows the coordinates of the graph; & test level. • |
Solves a Linear Programming problem
supplied by the user in standard form, by Dantzig's
simplex method in the revised simplex (i.e., matrix) form.
In the standard form: all the constraints must be given
as equations, typically after insertion of slack
(or surplus) or artificial variables;
and with non-negative right-hand side constants,
i.e., b ≥ 0.
If any artificial variable is present, its coefficient (given as 0)
will be (automatically) made ±M, according to the direction
of optimization ('+' for min, '−' for max).
Base problem is: Case 0 — Bronson 4.2; z*min = 71 2/3, X = (7/12, 5/12) =
(0.58(3), 0.41(6))
 Other data.pdf, Ramalhete.xlsx
Bland's anti-cycling rule is included (under observation).
A plot of the objective function, z, is presented
as a function of the successive bases.
The initial basis is № 0. |
| References: |
Plate: LP_revised_Bland |
• Bland,
Robert G., 1977, "New finite pivoting rules for the simplex method".pdf,
Mathematics of Operations Research, 2(2), pp 103–107.
• Wikipedia: Revised simplex method.
Decimal mark
• Google: "revised simplex method"
• 1799-02-26: Clapeyron, Benoit Paul Émile
(1864-01-28). |
