linopt::maximize -- maximize a
linear or mixed-integer program
Introductionlinopt::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.
Call(s)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)
Parametersconstr |
- | 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 |
OptionsAll |
- | 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. |
Returnsa list or a sequence of a list and a set containing the solution of the linear or mixed-integer program.
Related
Functionslinopt::minimize,
linopt::plot_data,
linopt::corners
Detailsobj 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.
Example
1We 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]
Example
2Now 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:
Example
3The following linear program do not have a solution:
>> linopt::maximize([{x <= -1, x >= 0}, x])
[EMPTY, {}, -infinity]
Example
4The 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]}
Example
5We 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:
BackgroundPapadimitriou, 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.