linopt::Transparent::autostep --
perform the next simplex step
Introductionlinopt::Transparent::autostep(tableau)
perform the next step of the simplex algorithm for the given simplex
tableau tableau.
Call(s)linopt::Transparent::autostep(tableau)
Parameterstableau |
- | a simplex tableau of domain type
linopt::Transparent |
Returnsa simplex tableau of domain type linopt::Transparent or
a set which contains the solution of the linear program.
Related
Functionslinopt::Transparent, linopt::Transparent::convert,
linopt::Transparent::dual_prices,
linopt::Transparent::phaseI_tableau,
linopt::Transparent::result,
linopt::Transparent::simplex,
linopt::Transparent::suggest,
linopt::Transparent::userstep
Detailslinopt::Transparent::autostep(tableau)
performs the next step of the simplex algorithm. This is the same step
that linopt::Transparent::suggest would suggest for
the given simplex tableau tableau.linopt::Transparent::autostep returns the
next simplex tableau. If the calculation of the simplex algorithm is
finished linopt::Transparent::autostep returns a set
containing a solution of the given linear program described by
tableau.
Example
1The ordinary simplex tableau of a given linear program is created:
>> k := [[x + y >= 2], x, NonNegative]: t := linopt::Transparent(k)
+- -+
| "linopt", "restr", slk[1], x, y |
| |
| "obj", 0, 0, 1, 0 |
| |
| slk[1], -2, 1, -1, -1 |
+- -+
The next two steps of the simplex algorithm are executed for the given simplex tableau:
>> linopt::Transparent::autostep(t); linopt::Transparent::autostep(%)
+- -+
| "linopt", "restr", slk[1], x, y |
| |
| "obj", -2, 1, 0, -1 |
| |
| x, 2, -1, 1, 1 |
+- -+
+- -+
| "linopt", "restr", slk[1], x, y |
| |
| "obj", 0, 0, 1, 0 |
| |
| y, 2, -1, 1, 1 |
+- -+
>> delete k, t:
Example
2The ordinary simplex tableau of a given linear program is created:
>> k := [[x + y >= -1, x + y <= 3], x + 2*y, NonNegative]: t := linopt::Transparent(k)
+- -+
| "linopt", "restr", slk[1], slk[2], x, y |
| |
| "obj", 0, 0, 0, 1, 2 |
| |
| slk[1], 1, 1, 0, -1, -1 |
| |
| slk[2], 3, 0, 1, 1, 1 |
+- -+
If the end of the simplex algorithm is reached,
linopt::Transparent::autostep returns a solution of the
given linear program:
>> linopt::Transparent::suggest(t), linopt::Transparent::autostep(t)
OPTIMAL, {x = 0, y = 0}
>> delete k, 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.