linopt::Transparent::convert --
transform the given tableau into a structure printable on screen
Introductionlinopt::Transparent::convert(tableau)
converts the simplex tableau, into a two dimensional array.
Call(s)linopt::Transparent::convert(tableau)
Parameterstableau |
- | a simplex tableau of domain type |
Returnsa two dimensional array, representing the given simplex tableau
tableau.
Related
Functionslinopt::Transparent, linopt::Transparent::autostep,
linopt::Transparent::phaseI_tableau,
linopt::Transparent::phaseII_tableau,
linopt::Transparent::suggest,
linopt::Transparent::userstep
Detailstableau 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.
Example
1We 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:
Example
2We 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:
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.