Previous Page Next Page Contents

linopt::Transparent::simplex -- finish the current phase of the 2-phase simplex algorithm

Introduction

linopt::Transparent::simplex(tableau) finishes the current phase of the 2-phase simplex algorithm using the given tableau tableau.

Call(s)

linopt::Transparent::simplex(tableau)

Parameters

tableau - a simplex tableau of domain type linopt::Transparent

Returns

a simplex tableau of domain type linopt::Transparent or the empty set if there was no feasible solution found.

Related Functions

linopt::Transparent, linopt::Transparent::autostep, linopt::Transparent::convert, linopt::Transparent::dual_prices, linopt::Transparent::phaseI_tableau, linopt::Transparent::result, linopt::Transparent::suggest, linopt::Transparent::userstep

Details

Example 1

We apply linopt::Transparent::simplex to an ordinary simplex tableau of a linear program and we get the optimal tableau:

>> k := [[x + y >= 2], x, NonNegative]:    
   t := linopt::Transparent(k);
   t := linopt::Transparent::simplex(t)
                  +-                                   -+
                  |  "linopt", "restr", slk[1],  x,  y  |
                  |                                     |
                  |    "obj",     0,       0,    1,  0  |
                  |                                     |
                  |   slk[1],     -2,      1,   -1, -1  |
                  +-                                   -+
      
                   +-                                 -+
                   |  "linopt", "restr", slk[1], x, y  |
                   |                                   |
                   |    "obj",     0,       0,   1, 0  |
                   |                                   |
                   |      y,       2,      -1,   1, 1  |
                   +-                                 -+

Let us proof the obtained result:

>> linopt::Transparent::suggest(t)
                                  OPTIMAL
>> delete k, t:
     

Example 2

If the first phase of the simplex algorithm was started explicitly,
linopt::Transparent::simplex returns only the optimal tableau of the first phase:

>> k := [[x + y >= 2], x, NonNegative]:    
   t := linopt::Transparent(k):
   t := linopt::Transparent::phaseI_tableau(t);
   t := linopt::Transparent::simplex(t)
              +-                                           -+
              |  "linopt", "restr", slk[2], slk[1],  x,  y  |
              |                                             |
              |    "obj",     -2,      0,      1,   -1, -1  |
              |                                             |
              |   slk[2],     2,       1,     -1,    1,  1  |
              +-                                           -+
      
               +-                                         -+
               |  "linopt", "restr", slk[2], slk[1], x, y  |
               |                                           |
               |    "obj",     0,       1,      0,   0, 0  |
               |                                           |
               |      x,       2,       1,     -1,   1, 1  |
               +-                                         -+

The next step of the simplex algorithm is computed:

>> linopt::Transparent::suggest(t)
                  "linopt::Transparent::phaseII_tableau"

With linopt::Transparent::autostep we execute the first step of the second phase of the simplex algorithm. One can see that the simplex algorithm is not finished yet:

>> t := linopt::Transparent::autostep(t):
   linopt::Transparent::suggest(t);
                                   x, y

If we then apply linopt::Transparent::simplex again we get the optimal solution. Here we don't had to use linopt::Transparent::clean_basis, before using linopt::Transparent::autostep, because there are no artificial variables in the basis computed by the first linopt::Transparent::simplex call above:

>> t := linopt::Transparent::simplex(t);
   linopt::Transparent::suggest(t)                                        
                   +-                                 -+
                   |  "linopt", "restr", slk[1], x, y  |
                   |                                   |
                   |    "obj",     0,       0,   1, 0  |
                   |                                   |
                   |      y,       2,      -1,   1, 1  |
                   +-                                 -+
      
                                  OPTIMAL
>> delete k, t:
     

Background

Changes




Do you have questions or comments?


Copyright © SciFace Software GmbH & Co. KG 2000