linopt::Transparent::simplex --
finish the current phase of the 2-phase simplex algorithm
Introductionlinopt::Transparent::simplex(tableau)
finishes the current phase of the 2-phase simplex algorithm using the
given tableau tableau.
Call(s)linopt::Transparent::simplex(tableau)
Parameterstableau |
- | a simplex tableau of domain type
linopt::Transparent |
Returnsa simplex tableau of domain type linopt::Transparent or
the empty set if there was no feasible solution found.
Related
Functionslinopt::Transparent, linopt::Transparent::autostep,
linopt::Transparent::convert,
linopt::Transparent::dual_prices,
linopt::Transparent::phaseI_tableau,
linopt::Transparent::result,
linopt::Transparent::suggest,
linopt::Transparent::userstep
Detailslinopt::Transparent::simplex runs the current phase of
the 2-phase simplex algorithm until the end, i.e. if phase I was
explicitly started (see linopt::Transparent::phaseI_tableau)
the first phase will lead the optimal tableau. Sometimes it can be
necessary to eliminate some slack variables of phase one by using
linopt::Transparent::clean_basis.(linopt::Transparent)::simplex returns the last optimal
tableau or the empty set if there was no feasible solution found.
Example
1We apply linopt::Transparent::simplex to an
ordinary simplex tableau of a linear program and we get the optimal
tableau:
>> k := [[x + y >= 2], x, NonNegative]: t := linopt::Transparent(k); t := linopt::Transparent::simplex(t)
+- -+
| "linopt", "restr", slk[1], x, y |
| |
| "obj", 0, 0, 1, 0 |
| |
| slk[1], -2, 1, -1, -1 |
+- -+
+- -+
| "linopt", "restr", slk[1], x, y |
| |
| "obj", 0, 0, 1, 0 |
| |
| y, 2, -1, 1, 1 |
+- -+
Let us proof the obtained result:
>> linopt::Transparent::suggest(t)
OPTIMAL
>> delete k, t:
Example
2If the first phase of the simplex algorithm was started
explicitly,
linopt::Transparent::simplex returns only the optimal
tableau of the first phase:
>> k := [[x + y >= 2], x, NonNegative]: t := linopt::Transparent(k): t := linopt::Transparent::phaseI_tableau(t); t := linopt::Transparent::simplex(t)
+- -+
| "linopt", "restr", slk[2], slk[1], x, y |
| |
| "obj", -2, 0, 1, -1, -1 |
| |
| slk[2], 2, 1, -1, 1, 1 |
+- -+
+- -+
| "linopt", "restr", slk[2], slk[1], x, y |
| |
| "obj", 0, 1, 0, 0, 0 |
| |
| x, 2, 1, -1, 1, 1 |
+- -+
The next step of the simplex algorithm is computed:
>> linopt::Transparent::suggest(t)
"linopt::Transparent::phaseII_tableau"
With linopt::Transparent::autostep we execute the
first step of the second phase of the simplex algorithm. One can see
that the simplex algorithm is not finished yet:
>> t := linopt::Transparent::autostep(t): linopt::Transparent::suggest(t);
x, y
If we then apply
linopt::Transparent::simplex again we get the optimal
solution. Here we don't had to use linopt::Transparent::clean_basis, before
using linopt::Transparent::autostep, because there are no
artificial variables in the basis computed by the first
linopt::Transparent::simplex call above:
>> t := linopt::Transparent::simplex(t); linopt::Transparent::suggest(t)
+- -+
| "linopt", "restr", slk[1], x, y |
| |
| "obj", 0, 0, 1, 0 |
| |
| y, 2, -1, 1, 1 |
+- -+
OPTIMAL
>> delete k, t:
BackgroundPapadimitriou, Christos H; Steiglitz, Kenneth: Combinatorial Optimization; Algorithms and Complexity. Prentice-Hall, 1982.
Nemhauser, George L; Wolsey, Laurence A: Integer and Combinatorial Optimization. New York, Wiley, 1988.
Salkin, Harvey M; Mathur, Kamlesh: Foundations of Integer Programming. North-Holland, 1989.
Neumann, Klaus; Morlock, Martin: Operations-Research. Munich, Hanser, 1993.
Duerr, Walter; Kleibohm, Klaus: Operations Research; Lineare Modelle und ihre Anwendungen. Munich, Hanser, 1992.
Suhl, Uwe H: MOPS - Mathematical OPtimization System. European Journal of Operational Research 72(1994)312-322. North-Holland, 1994.
Suhl, Uwe H; Szymanski, Ralf: Supernode Processing of Mixed Integer Models. Boston, Kluwer Academic Publishers, 1994.