emblem
Linear Programming (revised simplex), v. 3
Solves an LP problem in standard form by the revised simplex method.
2024.Nov.25 05:02:31
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, (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
(' ' or tabs; input not generalized !). •
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).

This follows the basic ("manual") procedure.

Basis problem is: Case 0 — Bronson 4.2; z*min = 71 2/3, X = (7/12, 5/12) = (0.58(3), 0.41(6))

NewOther data.pdf (copy-paste); Ramalhete.xlsx (copy-paste from Excel), z* = 1012.9; lp_diet .txt, .lp, .xlsx, z* = 14.86

A plot of the objective function, z, is presented as a function of the successive bases. The initial basis is № 0.

References: Plate: LP_revised3

• Wikipedia: Revised simplex method. Decimal mark

• Google: "revised simplex method"

• 1824-03-12: Kirchhoff, Gustav Robert (1887-10-17).

 
 
Valid HTML 4.01! IST http://web.ist.utl.pt/~mcasquilho/compute/or/Fx-LP-revised.php
Created: 2017-03-12 — Last modified: 2021-07-11