Maximize a linear or mixedinteger program
This functionality does not run in MATLAB.
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)
linopt::maximize([constr, obj])
returns
the solution of the linear or mixedinteger 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 dualprices in addition to the
solutiontripel. In this case the result of linopt::maximize
is
a sequence of a list containing the solutiontripel and a set containing
the dual prices. See Example 4.
We try to solve the linear program
with the linear objective function c_{1} + 2 c_{2}:
linopt::maximize([{2*c1 <= 1, 2*c2 <= 1}, c1 + 2*c2])
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:
The following linear program do not have a solution:
linopt::maximize([{x <= 1, x >= 0}, x])
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)
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:

A set or list of linear constraints 

A linear expression 

A set which contains identifiers interpreted as indeterminates 

A set which contains identifiers interpreted as indeterminates 

All variables are constrained to be integers 

All variables are constrained to be nonnegative 

This option is only available in the linear case. It causes the output of the dualprices in addition to the solutiontriple. 
List or a sequence of a list and a set containing the solution of the linear or mixedinteger program.
Papadimitriou, Christos H; Steiglitz, Kenneth: Combinatorial Optimization; Algorithms and Complexity. PrenticeHall, 1982.
Nemhauser, George L; Wolsey, Laurence A: Integer and Combinatorial Optimization. New York, Wiley, 1988.
Salkin, Harvey M; Mathur, Kamlesh: Foundations of Integer Programming. NorthHolland, 1989.
Neumann, Klaus; Morlock, Martin: OperationsResearch. 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)312322. NorthHolland, 1994.
Suhl, Uwe H; Szymanski, Ralf: Supernode Processing of Mixed Integer Models. Boston, Kluwer Academic Publishers, 1994.