Documentation

This is machine translation

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

`linopt`::`maximize`

Maximize a linear or mixed-integer program

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::maximize(`[constr, obj]`, <DualPrices>)
linopt::maximize(`[constr, obj, <NonNegative>, <seti>]`)
linopt::maximize(`[constr, obj, <NonNegative>, <All>]`)
linopt::maximize(`[constr, obj, <setn>, <seti>]`)
linopt::maximize(`[constr, obj, <setn>, <All>]`)
linopt::maximize(`[constr, obj, <NonNegative>]`, DualPrices)
linopt::maximize(`[constr, obj, <set>]`, DualPrices)
```

Description

`linopt::maximize([constr, obj])` returns the solution of the linear or mixed-integer program given by the constraints `constr` and the linear objective function `obj` which should be maximized.

The expression `obj` is the linear objective function to be maximized subject to the linear constraints `constr`. The function `linopt::maximize` returns a triple consisting of the state of the output, `OPTIMAL`, `EMPTY` or `UNBOUNDED`, a set of equations which describes the optimal solution of the specified linear program, which is empty or depends on a free variable Φ subject to the state, and finally the maximal objective function value, which can be either a number, -`infinity` or a linear function in Φ.

The states `OPTIMAL`, `EMPTY` or `UNBOUNDED` have the following meanings. `OPTIMAL` means an optimal solution for the linear program was found. If the state is `EMPTY` no optimal solution was found and if it is `UNBOUNDED` then the solution has no upper bound.

If the option `NonNegative` is used all variables are constrained to be nonnegative. If instead of `NonNegative` a set `setn` is given then only the variables from `setn` are constrained to be nonnegative.

If the option `All` is used all variables are constrained to be integers. If instead of `All` a set `seti` is given, then only the variables from `seti` are constrained to be integers.

As a second parameter for `linopt::maximize` the option `DualPrices` is provided for the linear case (the first parameter therefore must not have more than three elements). This option causes the output of the dual-prices in addition to the solution-tripel. In this case the result of `linopt::maximize` is a sequence of a list containing the solution-tripel and a set containing the dual prices. See Example 4.

Examples

Example 1

We try to solve the linear program

with the linear objective function c1 + 2 c2:

`linopt::maximize([{2*c1 <= 1, 2*c2 <= 1}, c1 + 2*c2])`

Example 2

Now let's have a look at the linear program

with the linear objective function - x + y + 2 z. If we make no restriction to the variables the result is unbounded:

```c := [{3*x + 4*y - 3*z <= 23, 5*x - 4*y - 3*z <= 10, 7*x + 4*y + 11*z <= 30}, -x + y + 2*z]: linopt::maximize(c)```

But if all variables are constrained to be nonnegative, we get a result. That's also the case if only x and y are constrained to be nonnegative:

```linopt::maximize(append(c, NonNegative)); linopt::maximize(append(c, {x, y}))```

`delete c:`

Example 3

The following linear program do not have a solution:

`linopt::maximize([{x <= -1, x >= 0}, x])`

Example 4

The output of the dual prices can be enforced with the option `DualPrices`:

```linopt::maximize([{2*c1 <= 1, 2*c2 <= 1},c1 + 2*c2], DualPrices)```

Example 5

We have a look at the knapsack problem with x1, x2, x3, x4 ∈ {0, 1}:

```c := {20*x1 + 15*x2 + 20*x3 + 5*x4 <= 25}: c := c union {x1 <= 1, x2 <= 1, x3 <= 1, x4 <= 1}: f := 10*x1 + 15*x2 + 16*x3 + x4: linopt::maximize([c, f, NonNegative, All])```

`delete c, f:`

Parameters

 `constr` A set or list of linear constraints `obj` A linear expression `seti` A set which contains identifiers interpreted as indeterminates `setn` A set which contains identifiers interpreted as indeterminates

Options

 `All` All variables are constrained to be integers `NonNegative` All variables are constrained to be nonnegative `DualPrices` This option is only available in the linear case. It causes the output of the dual-prices in addition to the solution-triple.

Return Values

List or a sequence of a list and a set containing the solution of the linear or mixed-integer program.

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.