linopt::Transparent::phaseII_tableau
-- start phase two of a 2-phase simplex algorithm
Introduction
linopt::Transparent::phaseII_tableau(tableau)
starts the second phase of the simplex algorithm on the given simplex
tableau tableau.
Call(s)linopt::Transparent::phaseII_tableau(tableau)
Parameterstableau |
- | a simplex tableau of domain type
linopt::Transparent |
Returnsa simplex tableau of domain type
linopt::Transparent.
Related
Functionslinopt::Transparent, linopt::Transparent::autostep,
linopt::Transparent::convert,
linopt::Transparent::clean_basis,
linopt::Transparent::dual_prices,
linopt::Transparent::phaseI_tableau,
linopt::Transparent::result,
linopt::Transparent::simplex,
linopt::Transparent::suggest,
linopt::Transparent::userstep
Detailslinopt::Transparent::phaseI_tanleau)
terminated with an optimal tableau with associated costs 0 and no phase
one slack variables in the basis (see linopt::Transparent::clean_basis)
this procedure can be used to start phase II. The procedure eliminates
all artificial variables of phase I and their associated columns and
reenters the old objective function modified for the new basis.
Example
1The first simplex tableau is created and the first phase of the simplex algorithm is finished:
>> t := linopt::Transparent([[x + y >= 2], x, NonNegative]):
t := linopt::Transparent::simplex(
linopt::Transparent::phaseI_tableau(t))
+- -+
| "linopt", "restr", slk[2], slk[1], x, y |
| |
| "obj", 0, 1, 0, 0, 0 |
| |
| x, 2, 1, -1, 1, 1 |
+- -+
One sees that the artificial slack variable slk[2] of
the first phase is removed by
linopt::Transparent::phaseII_tableau. In this example it
is not necessary to use
linopt::Transparent::clean_basis
for cleaning the basis:
>> linopt::Transparent::phaseII_tableau(t)
+- -+
| "linopt", "restr", slk[1], x, y |
| |
| "obj", -2, 1, 0, -1 |
| |
| x, 2, -1, 1, 1 |
+- -+
>> delete t:
Example
2Again the first simplex tableau is created and the first phase of the simplex algorithm is finished:
>> 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
)
In this example the artificial slack variable
slk[6] is an element of the optimal basis. So we have to
use linopt::Transparent::clean_basis
before continuing with
linopt::Transparent::phaseII_tableau, otherwise we will
get an error message. To get a smarter output in this example one
should use at least a TEXTWIDTH of 80:
>> linopt::Transparent::phaseII_tableau(t)
Error: Clean the basis from phase I slack variables first! [l\
inopt::Transparent::phaseII_tableau]
>> t := linopt::Transparent::clean_basis(t): linopt::Transparent::phaseII_tableau(t)
+- -+
| "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:
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.