linopt::maximize
-- maximize a
linear or mixed-integer programlinopt::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.
linopt::maximize([constr, obj])
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)
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 |
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. |
a list or a sequence of a list and a set containing the solution of the linear or mixed-integer program.
linopt::minimize
,
linopt::plot_data
,
linopt::corners
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 PHI subject to the state, and finally the
maximal objective function value, which can be either a number,
-infinity
or a linear function in Phi.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.setn
is given then only the
variables from setn
are constrained to be
nonnegative.seti
is given, then only the variables from
seti
are constrained to be integers.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.We try to solve the linear program
2*c1 <= 1, 2*c2 <= 1
with the linear objective function c1 + 2*c2:
>> linopt::maximize([{2*c1 <= 1, 2*c2 <= 1}, c1 + 2*c2])
[OPTIMAL, {c1 = 1/2, c2 = 1/2}, 3/2]
Now let's have a look at the linear program
3*x + 4*y - 3*z <= 23, 5*x - 4*y - 3*z <= 10, 7*x + 4*y + 11*z <= 30
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)
-- { 7 PHI1 } | UNBOUNDED, { y = 0, x = -PHI1, z = ------ + 30/11 }, -- { 11 } 25 PHI1 -- ------- + 60/11 | 11 --
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}))
[OPTIMAL, {x = 0, z = 1/2, y = 49/8}, 57/8] [OPTIMAL, {x = 0, z = 1/2, y = 49/8}, 57/8]
>> delete c:
The following linear program do not have a solution:
>> linopt::maximize([{x <= -1, x >= 0}, x])
[EMPTY, {}, -infinity]
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)
[OPTIMAL, {c1 = 1/2, c2 = 1/2}, 3/2], {[c1 <= 1/2, 1], [c2 <= 1/2, 2]}
We have a look at the knapsack problem with x1, x2, x3, x4 elements of 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])
[OPTIMAL, {x1 = 0, x2 = 0, x3 = 1, x4 = 1}, 17]
>> delete c, f:
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.