Documentation

This is machine translation

Translated by Microsoft
Mouseover text to see original. Click the button below to return to the English verison of the page.

Note: This page has been translated by MathWorks. Please click here
To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.

linopt::Transparent::simplex

Finish the current phase of the 2-phase simplex algorithm

MuPAD® notebooks are not recommended. 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::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?