## `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

- `linopt::Transparent::simplex` runs the current phase of the 2-phase simplex algorithm until the end, i.e. if phase I was explicitly started (see `linopt::Transparent::phaseI_tableau`) the first phase will lead the optimal tableau. Sometimes it can be necessary to eliminate some slack variables of phase one by using `linopt::Transparent::clean_basis`.
- If there was no phase I started by the user, `(linopt::Transparent)::simplex` returns the last optimal tableau or the empty set if there was no feasible solution found.

#### 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

- 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.

#### Changes

- new function
- The linopt library was completely rewritten in MuPAD version 2.0.

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000