linopt::Transparent::phaseII_tableau

Start phase two of a 2-phase simplex algorithm

Use only in the MuPAD Notebook Interface.

This functionality does not run in MATLAB.

Syntax

linopt::Transparent::phaseII_tableau(tableau)

Description

linopt::Transparent::phaseII_tableau(tableau) starts the second phase of the simplex algorithm on the given simplex tableau tableau.

After the explicitly started first phase of the simplex algorithm (see linopt::Transparent::phaseI_tableau) 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.

Examples

Example 1

The 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))

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)

delete t:

Example 2

Again 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)

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:

linopt::Transparent::phaseII_tableau(t)
Error: Clean the basis from phase I slack variables first. [linopt::Transparent::phaseII_tableau]
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.

Was this topic helpful?