linopt::Transparent::convert

Transform the given tableau into a structure printable on screen

Use only in the MuPAD Notebook Interface.

This functionality does not run in MATLAB.

Syntax

linopt::Transparent::convert(tableau)

Description

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.

Internally the given 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.

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.

Examples

Example 1

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)

delete a, k, t:

Example 2

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);

delete k, eigenpivot, mysimplex:

Parameters

tableau

A simplex tableau of domain type

Return Values

Two dimensional array, representing the given simplex tableau tableau.

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?