linopt::Transparent::simplex

Finish the current phase of the 2-phase simplex algorithm

Use only in the MuPAD Notebook Interface.

This functionality does not run in MATLAB.

Syntax

linopt::Transparent::simplex(tableau)

Description

linopt::Transparent::simplex runs the current phase of the 2-phase simplex algorithm until the end, i.e. if phase I was explicitly started (see linopt::Transparent::phaseI_tableau) the first phase will lead the optimal tableau. Sometimes it can be necessary to eliminate some slack variables of phase one by using linopt::Transparent::clean_basis.

If there was no phase I started by the user, (linopt::Transparent)::simplex returns the last optimal tableau or the empty set if there was no feasible solution found.

Examples

Example 1

We apply linopt::Transparent::simplex to an ordinary simplex tableau of a linear program and we get the optimal tableau:

k := [{x + y >= 2}, x, NonNegative]:    
t := linopt::Transparent(k);
t := linopt::Transparent::simplex(t)

Let us proof the obtained result:

linopt::Transparent::suggest(t)

delete k, t:

Example 2

If the first phase of the simplex algorithm was started explicitly,linopt::Transparent::simplex returns only the optimal tableau of the first phase:

k := [{x + y >= 2}, y, NonNegative]:    
t := linopt::Transparent(k):
t := linopt::Transparent::phaseI_tableau(t);
t := linopt::Transparent::simplex(t)

The next step of the simplex algorithm is computed:

linopt::Transparent::suggest(t)

With linopt::Transparent::autostep we execute the first step of the second phase of the simplex algorithm. One can see that the simplex algorithm is not finished yet:

t := linopt::Transparent::autostep(t):
linopt::Transparent::suggest(t);

If we then apply linopt::Transparent::simplex again we get the optimal solution. Here we don't had to use linopt::Transparent::clean_basis, before using linopt::Transparent::autostep, because there are no artificial variables in the basis computed by the first linopt::Transparent::simplex call above:

t := linopt::Transparent::simplex(t);
linopt::Transparent::suggest(t)

delete k, t:

Parameters

tableau

A simplex tableau of domain type linopt::Transparent

Return Values

Simplex tableau of domain type linopt::Transparent or the empty set if there was no feasible solution found.

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?