Мануал по AMPL - языку программирования задач оптимизации

Подождите немного. Документ загружается.

________________________________________________________________________

____________________________________________________________________________________________________________________________________________________________________________________

set PROD; # products

param rate {PROD} > 0; # tons produced per hour

param avail >= 0; # hours available in week

param profit {PROD}; # profit per ton

param market {PROD} >= 0; # limit on tons sold in week

var Make {p in PROD} >= 0, <= market[p]; # tons produced

maximize total_profit: sum {p in PROD} profit[p] * Make[p];

# Objective: total profits from all products

subject to Time: sum {p in PROD} (1/rate[p]) * Make[p] <= avail;

# Constraint: total of hours used by all

# products may not exceed hours available

Figure 1-4a: Steel production model (steel.mod).

set PROD := bands coils;

param: rate profit market :=

bands 200 25 6000

coils 140 30 4000 ;

param avail := 40;

Figure 1-4b: Data for steel production model (steel.dat).

____________________________________________________________________________________________________________________________________________________________________________________

________________________________________________________________________

declarations have been put in a file called steel.mod, and the data specification has

been put in steel.dat:

ampl:

model steel.mod;

ampl:

data steel.dat;

ampl:

solve;

MINOS 5.4: optimal solution found.

2 iterations, objective 192000

ampl:

display Make;

Make [*] :=

bands 6000

coils 1400

;

The model and data commands each specify a file whose contents are to be read

immediately, as if all of its lines had been typed at that point. In this example, we first

read the model from steel.mod, then read the data from steel.dat. The use of two

separate commands encourages a clean separation of model from data.

Filenames can have any form recognized by your computer’s operating system; AMPL

doesn’t check them for correctness. The filenames here refer to the files on the disk that

accompanies the book.

12 PRODUCTION MODELS: MAXIMIZING PROFITS CHAPTER 1

Once the model has been solved, we can show all of the optimal values of the vari-

ables Make[p], by typing

display Make

. The output from display uses the same

formats as AMPL data input, so that there is only one set of formats to learn. (The [*]

indicates a variable or parameter with a single subscript. It is not strictly necessary for

input, since Make is one-dimensional, but display prints it as a reminder.)

Error messages

You will inevitably make some mistakes as you develop a model. AMPL detects vari-

ous kinds of incorrect statements, which are reported in error messages following the

model, data or solve commands.

AMPL catches many errors as soon as the model is read. For example, if you use the

wrong syntax for the bounds in the declaration of the variable Make, you will receive an

error message like this, right after you enter the model command:

steel.mod, line 8 (offset 250):

syntax error

context: var Make {p in PROD} >>> 0 <<< <= Make[p] <= market[p];

If you inadvertently use make instead of Make in an expression like profit[p] *

make[p], you will receive this message:

steel.mod, line 11 (offset 353):

make is not defined

context: maximize total_profit:

sum {p in PROD} profit[p] * >>> make[p] <<< ;

In each case, the offending line is printed, with the approximate location of the error sur-

rounded by >>> and <<<.

Other sources of error messages include a variable or parameter with the wrong num-

ber of subscripts, a model component used before it is declared, a missing semicolon at

the end of a command, or a reserved word like sum or in used in the wrong context.

(Appendix A.17 contains a list of reserved words.) Syntax errors in data statements are

similarly reported right after you enter a data command.

Errors in the data values are caught after you type solve. If the number of hours

were given as –40, for instance, we would see:

ampl:

model steel.mod; data steel.dat; solve;

error processing param avail:

failed check: param avail is not >= 0;

currently the check reads...

check -40 >= 0;

It is good practice to include as many validity checks as possible in the model. Errors

that are not caught at an early stage often lead to a mystifyingly wrong or meaningless

solution.

1.5 Adding lower bounds to the model

Once the model and data have been set up, it is a simple matter to change them and

then re-solve. Indeed, we would not expect to find an LP application in which the model

and data are prepared and solved just once, or even a few times. Most commonly, numer-

ous refinements are introduced as the model is developed, and changes to the data con-

tinue for as long as the model is used.

Let’s conclude this chapter with a few examples of changes and refinements. These

examples also highlight some additional features of AMPL.

Suppose first that we add another product, steel plate. The model stays the same, but

in the data we have to add plate to the list of members for the set PROD, and we have

to add a line of parameter values for plate:

set PROD := bands coils plate;

param: rate profit market :=

bands 200 25 6000

coils 140 30 4000

plate 160 29 3500 ;

param avail := 40;

We put this version of the data in a file called steel2.dat, and use AMPL as before to

get the solution:

ampl:

model steel.mod; data steel2.dat; solve;

MINOS 5.4: optimal solution found.

2 iterations, objective 196400

ampl:

display Make;

Make [*] :=

bands 6000

coils 0

plate 1600

;

Profits have increased compared to the two-variable version, but now it is best to produce

no coils at all! On closer examination, this result is not so surprising. Plate yields a pro-

fit of $4640 per hour, which is less than for bands but more than for coils. Thus plate is

produced to absorb the capacity not taken by bands; coils would be produced only if both

bands and plate reached their market limits before the available hours were exhausted.

In reality, a whole product line cannot be shut down solely to increase weekly profits.

The simplest way to reflect this in the model is to add lower bounds on the production

amounts, as shown in Figures 1-5a and 1-5b. We have declared a new collection of

parameters named commit, to represent the lower bounds on production that are

imposed by sales commitments, and we have changed >= 0 to >= commit[p] in the

declaration of the variables Make[p].

After these changes are made, we can run AMPL again to get a more realistic solution:

14 PRODUCTION MODELS: MAXIMIZING PROFITS CHAPTER 1

________________________________________________________________________

____________________________________________________________________________________________________________________________________________________________________________________

set PROD; # products

param rate {PROD} > 0; # produced tons per hour

param avail >= 0; # hours available in week

param profit {PROD}; # profit per ton

param commit {PROD} >= 0; # lower limit on tons sold in week

param market {PROD} >= 0; # upper limit on tons sold in week

var Make {p in PROD} >= commit[p], <= market[p]; # tons produced

maximize total_profit: sum {p in PROD} profit[p] * Make[p];

# Objective: total profits from all products

subject to Time: sum {p in PROD} (1/rate[p]) * Make[p] <= avail;

# Constraint: total of hours used by all

# products may not exceed hours available

Figure 1-5a: Lower bounds on production (steel3.mod).

set PROD := bands coils plate;

param: rate profit commit market :=

bands 200 25 1000 6000

coils 140 30 500 4000

plate 160 29 750 3500 ;

param avail := 40;

Figure 1-5b: Data for lower bounds on production (steel3.dat).

____________________________________________________________________________________________________________________________________________________________________________________

________________________________________________________________________

ampl:

model steel3.mod; data steel3.dat; solve;

MINOS 5.4: optimal solution found.

2 iterations, objective 194828.5714

ampl:

display commit,Make,market;

: commit Make market :=

bands 1000 6000 6000

coils 500 500 4000

plate 750 1028.57 3500

;

For comparison, we have displayed commit and market on either side of the actual

production, Make. Evidently, after the commitments are met, it is most profitable to pro-

duce bands up to the market limit, and then to produce plate with the remaining available

time.

1.6 Adding resource constraints to the model

Processing of steel slabs is not a single operation, but a series of steps that may pro-

ceed at different rates. To motivate a more general model, imagine that we divide pro-

________________________________________________________________________

____________________________________________________________________________________________________________________________________________________________________________________

set PROD; # products

set STAGE; # stages

param rate {PROD,STAGE} > 0; # tons per hour in each stage

param avail {STAGE} >= 0; # hours available/week in each stage

param profit {PROD}; # profit per ton

param commit {PROD} >= 0; # lower limit on tons sold in week

param market {PROD} >= 0; # upper limit on tons sold in week

var Make {p in PROD} >= commit[p], <= market[p]; # tons produced

maximize total_profit: sum {p in PROD} profit[p] * Make[p];

# Objective: total profits from all products

subject to Time {s in STAGE}:

sum {p in PROD} (1/rate[p,s]) * Make[p] <= avail[s];

# In each stage: total of hours used by all

# products may not exceed hours available

Figure 1-6a: Additional resource constraints (steel4.mod).

____________________________________________________________________________________________________________________________________________________________________________________

________________________________________________________________________

duction into a reheat stage that can process the incoming slabs at 200 tons per hour, and a

rolling stage that makes bands, coils or plate at the rates previously given. Further imag-

ine that there are only 35 hours of reheat time, even though there are 40 hours of rolling

time.

To cover this kind of situation, we can add a set STAGE of production stages to our

model. The parameter and constraint declarations are modified accordingly, as shown in

Figure 1-6a. Since there is a potentially different number of hours available in each

stage, the parameter avail is now indexed over STAGE. Since there is a potentially dif-

ferent production rate for each product in each stage, the parameter rate is indexed over

both PROD and STAGE. In the Time constraint, the production rate for product p in

stage s is referred to as rate[p,s]; this is AMPL’s version of a doubly subscripted

entity like a

in algebraic notation.

The only other change is to the constraint declaration, where we no longer have a sin-

gle constraint, but a constraint for each stage imposed by limited time. In algebraic nota-

tion, this might have been written

Subject to

p∈P

( 1 / a

≤ b

, for each s ∈S.

Compare the AMPL version:

subject to Time {s in STAGE}:

sum {p in PROD} (1/rate[p,s]) * Make[p] <= avail[s];

As in the other examples, this is a straightforward analogue, adapted to the requirements

of a computer language. In complex models, most of the constraints are indexed collec-

tions like this one.

16 PRODUCTION MODELS: MAXIMIZING PROFITS CHAPTER 1

________________________________________________________________________

____________________________________________________________________________________________________________________________________________________________________________________

set PROD := bands coils plate;

set STAGE := reheat roll;

param rate: reheat roll :=

bands 200 200

coils 200 140

plate 200 160 ;

param: profit commit market :=

bands 25 1000 6000

coils 30 500 4000

plate 29 750 3500 ;

param avail := reheat 35 roll 40 ;

Figure 1-6b: Data for additional resource constraints (steel4.dat).

____________________________________________________________________________________________________________________________________________________________________________________

________________________________________________________________________

Since rate is now indexed over combinations of two indices, it requires a data table

all to itself, as in Figure 1-6b. This data also include the membership for the new set

STAGE, and values of avail for both reheat and roll.

After these changes are made, we use AMPL to get another revised solution:

ampl:

reset;

ampl:

model steel4.mod; data steel4.dat; solve;

MINOS 5.4: optimal solution found.

4 iterations, objective 190071.4286

ampl:

display Make.lb,Make,Make.ub,Make.rc;

: Make.lb Make Make.ub Make.rc :=

bands 1000 3357.14 6000 5.32907e-15

coils 500 500 4000 -1.85714

plate 750 3142.86 3500 3.55271e-15

;

ampl:

display Time;

Time [*] :=

reheat 1800

roll 3200

;

If your computer system lets you work on files while AMPL remains active, you can use

the reset command as shown above to erase the previous model and permit a new one

to be read in. Otherwise, you’ll need to type quit to leave AMPL, work on your files,

then start up AMPL again.

At the end of the example above we have displayed the ‘‘dual values’’ or ‘‘shadow

prices’’ associated with the Time constraints. The dual value of a constraint measures

how much the value of the objective function would improve if the constraint were

relaxed by a small amount. For example, here we would expect that up to some point,

additional reheat time would produce another $1800 of extra profit per hour, and addi-

tional rolling time would produce $3200 per hour; decreasing these times would decrease

the profit correspondingly. In output commands like display, AMPL interprets a

constraint’s name alone as referring to the associated dual values.

We also display several quantities associated with the variables Make. First there are

lower bounds Make.lb and upper bounds Make.ub, which in this case are the same as

commit and market. We also show the ‘‘reduced cost’’ Make.rc, which has the

same meaning with respect to the bounds that the shadow prices have with respect to the

constraints. Thus we see that, again up to some point, each increase of a ton in the lower

bound (or commitment) for coil production should reduce profits by about $1.86; each

one-ton decrease in the lower bound should improve profits by about $1.86. The produc-

tion levels for bands and plates are between their bounds, so their reduced costs are essen-

tially zero (recall that e-15 means 10

−15

), and changing their levels will have no effect.

Bounds, shadow prices, reduced costs and other quantities associated with variables and

constraints are explored further in Section 10.7.

Comparing this session with our previous one, we see that the additional reheat time

restriction reduces profits by about $4750, and forces a substantial change in the optimal

solution: much higher production of plate and lower production of bands. Moreover, the

logic underlying the optimum is no longer so obvious. It is the difficulty of solving LPs

by logical reasoning alone that necessitates computer-based systems such as AMPL.

Bibliography

Julius S. Aronofsky, John M. Dutton and Michael T. Tayyabkhan, Managerial Planning with Lin-

ear Programming: in Process Industry Operations. John Wiley & Sons (New York, NY, 1978). A

detailed account of a variety of profit-maximizing applications, with emphasis on the petroleum

and petrochemical industries.

Vas ˇek Chva ´ tal, Linear Programming, W. H. Freeman (New York, NY, 1983). An introduction to

theoretical and algorithmic topics in linear programming.

Tibor Fabian, ‘‘A Linear Programming Model of Integrated Iron and Steel Production.’’ Manage-

ment Science 4 (1958) pp. 415–449. An application to all stages of steelmaking — from coal and

ore through finished products — from the early days of linear programming.

David A. Kendrick, Alexander Meeraus and Jaime Alatorre, The Planning of Investment Programs

in the Steel Industry. The Johns Hopkins University Press (Baltimore, MD, 1984). Several detailed

mathematical programming models, using the Mexican steel industry as an example.

Exercises

1-1. This exercise starts with a two-variable linear program similar in structure to the one of Sec-

tions 1.1 and 1.2, but with a quite different story behind it.

(a) You are in charge of an advertising campaign for a new product, with a budget of $1 million.

You can advertise on TV or in magazines. One minute of TV time costs $20,000 and reaches 1.8

million potential customers; a magazine page costs $10,000 and reaches 1 million. You must sign

18 PRODUCTION MODELS: MAXIMIZING PROFITS CHAPTER 1

up for at least 10 minutes of TV time. How should you spend your budget to maximize your audi-

ence? Formulate the problem in

AMPL and solve it. Check the solution by hand using at least one

of the approaches described in Section 1.1.

(b) It takes creative talent to create effective advertising; in your organization, it takes three

person-weeks to create a magazine page, and one person-week to create a TV minute. You have

only 100 person-weeks available. Add this constraint to the model and determine how you should

now spend your budget.

requires only 1 person-day of time. How does this medium affect your solutions?

(d) How does the solution change if you have to sign up for at least two magazine pages? A maxi-

mum of 120 minutes of radio?

1-2. The steel model of this chapter can be further modified to reflect various changes in produc-

tion requirements. For each part below, explain the modifications to Figures 1-6a and 1-6b that

would be required to achieve the desired changes. (Make each change separately, rather than accu-

mulating the changes from one part to the next.)

(a) How would you change the constraints so that total hours used by all products must equal the

total hours available for each stage? Solve the linear program with this change, and verify that you

get the same results. Explain why, in this case, there is no difference in the solution.

(b) How would you add to the model to restrict the total weight of all products to be less than a

new parameter, max_weight? Solve the linear program for a weight limit of 6500 tons, and

explain how this extra restriction changes the results.

possible. How would you change the objective function to maximize total tons? For the data of

our example, does this make a difference to the optimal solution?

(d) Suppose that instead of the lower bounds represented by commit[p] in our model, we want to

require that each product represent a certain share of the total tons produced. In the algebraic nota-

tion of Figure 1-1, this new constraint might be represented as

≥ s

k∈P

, for each j∈P

where s

is the minimum share associated with project j. How would you change the AMPL model

to use this constraint in place of the lower bounds commit[p]? If the minimum shares are 0.4 for

bands and plate, and 0.1 for coils, what is the solution?

Verify that if you change the minimum shares to 0.5 for bands and plate, and 0.1 for coils, the lin-

ear program gives an optimal solution that produces nothing, at zero profit. Explain why this

makes sense.

(e) Suppose there is an additional finishing stage for plates only, with a capacity of 20 hours and a

rate of 150 tons per hour. Explain how you could modify the data, without changing the model, to

incorporate this new stage.

1-3. This exercise deals with some issues of ‘‘sensitivity’’ in the steel models.

(a) For the linear program of Figures 1-5a and 1-5b, display Time and Make.rc. What do these

values tell you about the solution? (You may wish to review the explanation of shadow prices and

reduced costs in Section 1.6.)

(b) Explain why the reheat time constraints added in Figure 1-6a result in a higher production of

plate and a lower production of bands.

AMPL to verify the following statements: If the available reheat time is increased from 35

to 36 in the data of Figure 1-6b, then the profit goes up by $1800 as predicted in Section 1.6. (To

change the reheat time without changing and reading the data file over again, type let

avail["reheat"] := 36.) If the reheat time is further increased to 37, the profit goes up by

another $1800. However, if the reheat time is increased to 38, there is a smaller increase in the

profit, and further increases past 38 have no effect on the optimal profit at all.

By trying some other values of the reheat time, confirm that the profit increases by $1800 per extra

hour for any number of hours between 35 and 37

, but that any increase in the reheat time

beyond 37

hours doesn’t give any further profit.

Draw a plot of the profit versus the number of reheat hours available, for hours ≥ 35.

(d) To find the slope of the plot from (c) — profit versus reheat time available — at any particular

reheat time value, you need only look at the shadow price of Time["reheat"]. Using this

observation as an aid, extend your plot from (c) down to 25 hours of reheat time. Verify that the

slope of the plot remains at $6000 per hour from 25 hours down to less than 12 hours of reheat

time. Explain what happens when the available reheat time drops to 11 hours.

1-4. Here is a similar profit-maximizing model, but in a different context. An automobile manu-

facturer produces several kinds of cars. Each kind requires a certain amount of factory time per car

to produce, and yields a certain profit per car. A certain amount of factory time has been scheduled

for the next week, and it is desired to use all this time; but at least a certain number of each kind of

car must be manufactured to meet dealer requirements.

(a) What are the data values that define this problem? How would you declare the sets and param-

eter values for this problem in

AMPL? What are the decision variables, and how would you declare

them in

AMPL?

(b) Assuming that the objective is to maximize total profit, how would you declare an objective in

AMPL for this problem? How would you declare the constraints?

T, C and L, that 120 hours are available, and that the time per car, profit per car and dealer orders

for each kind of car are as follows:

Car time profit orders

T 1 200 10

C 2 500 20

L 3 700 15

How much of each car should be produced, and what is the maximum profit? You should find that

your solution specifies a fractional amount of one of the cars. As a practical matter, how could you

make use of this solution?

(d) If you maximize the total number of cars produced instead of the total profit, how many more

cars do you make? How much less profit?

(e) Each kind of car achieves a certain fuel efficiency, and the manufacturer is required by law to

maintain a certain ‘‘fleet average’’ efficiency. The fleet average is computed by multiplying the

efficiency of each kind of car times the number of that car produced, and dividing by the total cars

produced. Extend your

AMPL model to contain a minimum fleet average efficiency constraint.

Rearrange the constraint as necessary to make it linear — no variables divided into other variables.

20 PRODUCTION MODELS: MAXIMIZING PROFITS CHAPTER 1

(f) Find the optimal solution for the case where cars T, C and L achieve fuel efficiencies of 50, 30

and 20 miles/gallon, and the fleet average efficiency must be at least 35 miles/gallon. Explain how

this changes the production amounts and the total profit. Dealing with the fractional amounts in

the solution is not so easy in this case. What might you do?

If you had 10 more hours of production time, you could make more profit. Does the addition of the

fleet average efficiency constraint make the extra 10 hours more or less valuable?

(g) Explain how you could further refine this model to account for different production stages that

have different numbers of hours available per stage, much as in the steel model of Section 1.6.

1-5. A group of young entrepreneurs earns a (temporarily) steady living by acquiring discontinued

items from electronics stores and re-selling them. Each item has a street value, a weight, and a vol-

ume; there are limits on the numbers of available items, and on the total weight and volume that

can be managed at one time.

(a) Formulate an

AMPL model that will help to determine how much of each item to pick up, to

maximize one day’s profit.

(b) Find a solution for the case given by the following table,

Value Weight Volume Available

TV 50 35 8 20

radio 15 5 1 50

camera 85 4 2 20

CD player 40 3 1 30

VCR 50 15 5 30

camcorder 120 20 4 15

and by limits of 500 pounds and 300 cubic feet.

for re-sale. Suppose in addition that there are upper bounds on how many of each item you can

reasonably expect to sell. How would you add these conditions to the model?

(d) How could the group use the dual variables on the maximum-weight and maximum-volume

constraints to evaluate potential new partners for their activities?

(e) Through adverse circumstances the group has been reduced to only one member, who can carry

a mere 75 pounds and five cubic feet. What is the optimum strategy now? Given that this requires

a non-integral number of acquisitions, what is the best all-integer solution? (The integrality con-

straint converts this from a standard linear programming problem into a much harder problem

called a Knapsack Problem. See Chapter 15.)

1-6. Profit-maximizing models of oil refining were one of the first applications of linear program-

ming. This exercise asks you to model a simplified version of the final stage of the refining pro-

cess.

A refinery breaks crude oil into some collection of intermediate materials, then blends these materi-

als back together into finished products. Given the volumes of intermediates that will be available,

we want to determine how to blend the intermediates so that the resulting products are most prof-

itable. The decision is made more complicated, however, by the existence of upper limits on cer-

tain attributes of the products, which must be respected in any feasible solution.