## `linopt::Transparent::dual_prices` -- get the dual solution belonging to the given tableau

#### Introduction

`linopt::Transparent::dual_prices(`tableau`)` returns the dual solution of the linear optimization problem given by `tableau`.

#### Call(s)

`linopt::Transparent::dual_prices(tableau)`

#### Parameters

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

#### Returns

a set of lists, each containing 2 elements.

#### Related Functions

`linopt::Transparent`, `linopt::Transparent::result`

#### Details

- This procedure returns the dual solution belonging to the given tableau in form of a set of lists containing two elements, the first one is a restriction and the second one is the value belonging to the slack variable connected to the restriction in the dual solution.

#### Example 1

Here it is demonstrated that the dual solution of the final tableau is similar to the second element of the result of `linopt::minimize` using the option `DualPrices`:

First we compute the final tableau of the simplex algorithm:

    >> k := [[x<=2, y<=2, x+2*y>=4], -x+y, NonNegative]:
       t := linopt::Transparent(k):
       t := linopt::Transparent::simplex(t)

test

               +-                                                 -+
               |  "linopt", "restr", slk[1], slk[2], slk[3], x, y  |
               |                                                   |
               |    "obj",     1,      3/2,     0,     1/2,  0, 0  |
               |                                                   |
               |      x,       2,       1,      0,      0,   1, 0  |
               |                                                   |
               |   slk[2],     1,      1/2,     1,     1/2,  0, 0  |
               |                                                   |
               |      y,       1,     -1/2,     0,    -1/2,  0, 1  |
               +-                                                 -+

Now we compute the solutions:

    >> linopt::Transparent::dual_prices(t);
       linopt::minimize(k, DualPrices)[2]

          {[0 <= x, 0], [0 <= y, 0], [y <= 2, 0], [x <= 2, 3/2],

             [4 <= x + 2 y, 1/2]}

          {[0 <= x, 0], [0 <= y, 0], [y <= 2, 0], [x <= 2, 3/2],

             [4 <= x + 2 y, 1/2]}

    >> delete k, t:

#### Example 2

We compute the dual solution of another linear program:

    >> k := [[x <= 2, y <= 2, x + 2*y >= 4], -x + y, NonNegative]:
       t := linopt::Transparent(k);
       linopt::Transparent::dual_prices(t)

              +-                                                   -+
              |  "linopt", "restr", slk[1], slk[2], slk[3],  x,  y  |
              |                                                     |
              |    "obj",     0,       0,      0,      0,   -1,  1  |
              |                                                     |
              |   slk[1],     2,       1,      0,      0,    1,  0  |
              |                                                     |
              |   slk[2],     2,       0,      1,      0,    0,  1  |
              |                                                     |
              |   slk[3],     -4,      0,      0,      1,   -1, -2  |
              +-                                                   -+

          {[0 <= x, -1], [0 <= y, 1], [x <= 2, 0], [y <= 2, 0],

             [4 <= x + 2 y, 0]}

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