linopt::Transparent::clean_basis

Delete all slack variables of the first phase from the basis

MuPAD® notebooks will be removed in a future release. Use MATLAB® live scripts instead.

MATLAB live scripts support most MuPAD functionality, though there are some differences. For more information, see Convert MuPAD Notebooks to MATLAB Live Scripts.

Syntax

linopt::Transparent::clean_basis(tableau)

Description

linopt::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.

At the end of the phase one of the 2-phase simplex algorithm, explicitly started by using 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.

Examples

Example 1

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)

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. [linopt::Transparent::phaseII_tableau]

So we have to use linopt::Transparent::clean_basis before continuing with the appropriate function:

t := linopt::Transparent::clean_basis(t);
linopt::Transparent::phaseII_tableau(t)

delete t:

Parameters

tableau

A simplex tableau of domain type linopt::Transparent

Return Values

Simplex tableau of domain type linopt::Transparent.

References

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.