linopt::Transparent::convert
--
transform the given tableau into a structure printable on screenlinopt::Transparent::convert(
tableau)
converts the simplex tableau, into a two dimensional array.
linopt::Transparent::convert(tableau)
tableau |
- | a simplex tableau of domain type |
a two dimensional array, representing the given simplex tableau
tableau
.
linopt::Transparent
, linopt::Transparent::autostep
,
linopt::Transparent::phaseI_tableau
,
linopt::Transparent::phaseII_tableau
,
linopt::Transparent::suggest
,
linopt::Transparent::userstep
tableau
of domain type linopt::Transparent
contains a lot of more information than the simplex tableau which is
printed by some functions of the linopt
library, e.g.
linopt::Transparent::simplex
,
and which is visible on the screen. Furthermore it is not possible to
access the element in the i-th row and j-th
column of tableau
to get the corresponding element from
the simplex tableau which is visible on the screen.
linopt::Transparent::convert
converts
tableau
into a two dimensional array which corresponds
with the screen-tableau. One can now access the element in the
i-th row and j-th column of the simplex tableau
by accessing the corresponding element of the array.
While the internal structure of tableau
is not known
the structure of the two dimensional array is well defined. So it can
be easily used in own procedures. See example 2.
We convert a simplex tableau of domain type
linopt::Transparent
into a two dimensional array:
>> k := [[x + y >= 2], x, NonNegative]: t := linopt::Transparent(k): a := linopt::Transparent::convert(t): t, domtype(t); a, domtype(a)
+- -+ | "linopt", "restr", slk[1], x, y | | | | "obj", 0, 0, 1, 0 |, linopt::Transparent | | | slk[1], -2, 1, -1, -1 | +- -+ +- -+ | "linopt", "restr", slk[1], x, y | | | | "obj", 0, 0, 1, 0 |, DOM_ARRAY | | | slk[1], -2, 1, -1, -1 | +- -+
>> delete a, k, t:
We will write another simplex routine
mysimplex
for solving a linear program. For this we define
the function eigenpivot
for finding the pivot element of a
given simplex tableau. eigenpivot
assumes that the simplex
tableau is given as a two dimensional array.
Here is the procedure eigenpivot
, which is
not coded in every detail, e.g., the error checking isn't implemented
completely:
>> eigenpivot := proc(T: DOM_ARRAY) local i,j,m,n,k,l,mini; begin m := op(T,[0,2,2]): n := op(T,[0,3,2]): k := 0: l := 0: mini := unbesetzt: for j from 3 to n do if T[2,j] < 0 then l := j: break end_if: end_for: if l=0 then return(OPTIMAL) end_if: for i from 3 to m do if T[i,l] > 0 and (mini=unbesetzt or T[i,2]/T[i,l] < mini) then k := i: mini := T[k,2]/T[k,l] end_if end_for: if k=0 then return(UNBOUNDED) end_if: return(T[k,1],T[1,l]): end_proc:
This is the new simplex algorithm mysimplex
which uses eigenpivot
and some function from the
linopt
library:
>> mysimplex := proc(P) local T; begin T := linopt::Transparent(P): T := linopt::Transparent::phaseI_tableau(T): piv := eigenpivot(linopt::Transparent::convert(T)): while piv <> OPTIMAL and piv <> UNBOUNDED do T := linopt::Transparent::userstep(T,piv): piv := eigenpivot(linopt::Transparent::convert(T)) end_while: if piv = UNBOUNDED then error(" Phase I unbounded ?!?") end_if: if T[2,2] <> 0 then return(EMPTY) end_if: T := linopt::Transparent::clean_basis(T): T := linopt::Transparent::phaseII_tableau(T): piv := eigenpivot(linopt::Transparent::convert(T)): while piv <> OPTIMAL and piv <> UNBOUNDED do T := linopt::Transparent::userstep(T,piv): piv := eigenpivot(linopt::Transparent::convert(T)) end_while: if piv = OPTIMAL then return(linopt::Transparent::result(T)) else return(UNBOUNDED) end_if end_proc:
We now apply mysimplex
to a linear
program:
>> k := [[2*x + 2*y >= 4, -2*x + 4*y >= -2, -2*x + y>= -8, -2*x + y <= -2, y <= 6], -x - y]: k := append(k, NonNegative): mysimplex(k);
{x = 7, y = 6}
>> delete k, eigenpivot, mysimplex:
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.