Documentation

This is machine translation

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

linopt::Transparent::convert

Transform the given tableau into a structure printable on screen

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::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?