linopt::Transparent::phaseI_tableau
-- start an ordinary phase one of a 2-phase simplex algorithm
linopt::Transparent::phaseI_tableau(
tableau)
starts an (ordinary) phase one of the 2-phase simplex algorithm on the
given simplex tableau tableau
.
linopt::Transparent::phaseI_tableau(tableau)
tableau |
- | a simplex tableau of domain type
linopt::Transparent |
a simplex tableau of domain type
linopt::Transparent
.
linopt::Transparent
, linopt::Transparent::autostep
,
linopt::Transparent::convert
,
linopt::Transparent::clean_basis
,
linopt::Transparent::dual_prices
,
linopt::Transparent::phaseII_tableau
,
linopt::Transparent::result
,
linopt::Transparent::simplex
,
linopt::Transparent::suggest
,
linopt::Transparent::userstep
linopt::Transparent::phaseI_tableau
explicitly starts
an (ordinary) phase one of the simplex algorithm , i.e. rows associated
with infeasible basic variables are multiplied with -1 and another
identity matrix with new slack variables is added to the given tableau.
As soon as an optimal tableau with relative costs 0 is found the
calculation can be continued with linopt::Transparent::clean_basis
and the second phase of the simplex algorithm (linopt::Transparent::phaseII_tableau
).The first simplex tableau is created and the first phase of the simplex algorithm is started:
>> t := linopt::Transparent([[x + y >= 2], x, NonNegative]); t := linopt::Transparent::phaseI_tableau(t)
+- -+ | "linopt", "restr", slk[1], x, y | | | | "obj", 0, 0, 1, 0 | | | | slk[1], -2, 1, -1, -1 | +- -+ +- -+ | "linopt", "restr", slk[2], slk[1], x, y | | | | "obj", -2, 0, 1, -1, -1 | | | | slk[2], 2, 1, -1, 1, 1 | +- -+
We can see that a new slack variable, slk[2] was added
to the tableau. And if we now execute linopt::Transparent::simplex
we can see that we have just finished the first phase of the simplex
algorithm:
>> linopt::Transparent::suggest(t); t := linopt::Transparent::simplex(t): linopt::Transparent::suggest(t)
slk[2], x "linopt::Transparent::phaseII_tableau"
We continue the simplex algorithm by executing linopt::Transparent::clean_basis
,
linopt::Transparent::phaseII_tableau
and linopt::Transparent::simplex
.
Observe in this special case linopt::Transparent::clean_basis
is not necessary:
>> t := linopt::Transparent::clean_basis(t): t := linopt::Transparent::phaseII_tableau(t): 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 t:
Papadimitriou, 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.