Previous Page Next Page Contents

linopt::maximize -- maximize a linear or mixed-integer program

Introduction

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.

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)

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.

Returns

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

Related Functions

linopt::minimize, linopt::plot_data, linopt::corners

Details

Example 1

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]

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

Example 3

The following linear program do not have a solution:

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

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)
      [OPTIMAL, {c1 = 1/2, c2 = 1/2}, 3/2],
      
         {[c1 <= 1/2, 1], [c2 <= 1/2, 2]}

Example 5

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:
     

Background

Changes




Do you have questions or comments?


Copyright © SciFace Software GmbH & Co. KG 2000