linopt::Transparent::clean_basis
-- delete all slack variables of the first phase from the basislinopt::Transparent::clean_basis(
tableau)
removes the additional slack variables of the phase one of the simplex
algorithm from the optimal basic (described by tableau
)
calculated by linopt::Transparent::phaseI_tableau
and linopt::Transparent::simplex
.
linopt::Transparent::clean_basis(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::dual_prices
,
linopt::Transparent::phaseII_tableau
,
linopt::Transparent::result
,
linopt::Transparent::simplex
,
linopt::Transparent::suggest
,
linopt::Transparent::userstep
linopt::Transparent::phaseI_tableau
,
it is necessary to eliminate all artificial variables from the optimal
basis before phase two can be started by using linopt::Transparent::phaseII_tableau
.
linopt::Transparent::clean_basis
performs some pivot steps
until all phase one slack variables do not occur in the basis any
longer.In this example we first compute an optimal basis for the first phase of the simplex algorithm:
>> t := linopt::Transparent([[x <= 1,y <= 1,x + y >= 2], 0,NonNegative]): t := linopt::Transparent::phaseI_tableau(t): t := linopt::Transparent::simplex(t)
array(1..5, 1..10, (1, 1) = "linopt", (1, 2) = "restr", (1, 3) = slk[4], (1, 4) = slk[5], (1, 5) = slk[6], (1, 6) = slk[1], (1, 7) = slk[2], (1, 8) = slk[3], (1, 9) = x, (1, 10) = y, (2, 1) = "obj", (2, 2) = 0, . . (4, 10) = 1, (5, 1) = slk[6], (5, 2) = 0, (5, 3) = -1, (5, 4) = -1, (5, 5) = 1, (5, 6) = -1, (5, 7) = -1, (5, 8) = -1, (5, 9) = 0, (5, 10) = 0 )
As we can see the artificial slack variable slk[6] is an
element of the optimal basis. An error message is returned if we apply
linopt::Transparent::phaseII_tableau
or linopt::Transparent::simplex
to this simplex tableau:
>> linopt::Transparent::phaseII_tableau(t);
Error: Clean the basis from phase I slack variables first! [l\ inopt::Transparent::phaseII_tableau]
So we have to use
linopt::Transparent::clean_basis
before continuing with
the appropriate function. To get a smarter output in this example one
should use at least a TEXTWIDTH
of 80:
>> t := linopt::Transparent::clean_basis(t); linopt::Transparent::phaseII_tableau(t)
array(1..5, 1..10, (1, 1) = "linopt", (1, 2) = "restr", (1, 3) = slk[4], (1, 4) = slk[5], (1, 5) = slk[6], (1, 6) = slk[1], (1, 7) = slk[2], (1, 8) = slk[3], (1, 9) = x, (1, 10) = y, (2, 1) = "obj", (2, 2) = 0, . . (4, 10) = 1, (5, 1) = slk[1], (5, 2) = 0, (5, 3) = 1, (5, 4) = 1, (5, 5) = -1, (5, 6) = 1, (5, 7) = 1, (5, 8) = 1, (5, 9) = 0, (5, 10) = 0 ) +- -+ | "linopt", "restr", slk[1], slk[2], slk[3], x, y | | | | "obj", 0, 0, 0, 0, 0, 0 | | | | x, 1, 0, -1, -1, 1, 0 | | | | y, 1, 0, 1, 0, 0, 1 | | | | slk[1], 0, 1, 1, 1, 0, 0 | +- -+
>> 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.