________________________ ________________________________________________________________________ Production Models: Maximizing Profits As we stated in the Introduction, mathematical programming is a technique for solving certain kinds of problems notably maximizing profits and minimizing costs subject to constraints on resources, capacities, supplies, demands, and the like. AMPL is a language for specifying such optimization problems. It provides an algebraic notation that is very close to the way that you would describe a problem mathematically, so that it is easy to convert from a familiar mathematical description to AMPL. We will concentrate initially on linear programming, which is the best known and easiest case; other kinds of mathematical programming are taken up later in the book. This chapter addresses one of the most common applications of linear programming: maximizing the profit of some operation, subject to constraints that limit what can be produced. Chapters 2 and 3 are devoted to two other equally common kinds of linear programs, and Chapter 4 shows how linear programming models can be replicated and combined to produce truly large-scale problems. These chapters are written with the beginner in mind, but experienced practitioners of mathematical programming should find them useful as a quick introduction to AMPL. We begin with a linear program (or LP for short) in only two decision variables, motivated by a mythical steelmaking operation. This will provide a quick review of linear programming to refresh your memory if you already have some experience, or to help you get started if you're just learning. We'll show how the same LP can be represented as a general algebraic model of production, together with specific data. Then we'll show how to express several linear programming problems in AMPL and how to run AMPL and a solver to produce a solution. The separation of model and data is the key to describing more complex linear programs in a concise and understandable fashion. The final example of the chapter illustrates this by presenting several enhancements to the model. 1 2 PRODUCTION MODELS: MAXIMIZING PROFITS CHAPTER 1 1.1 A two-variable linear program An (extremely simplified) steel company must decide how to allocate next week's time on a rolling mill. The mill takes unfinished slabs of steel as input, and can produce either of two semi-finished products, which we will call bands and coils. (The terminology is not entirely standard; see the bibliography at the end of the chapter for some accounts of realistic LP applications in steelmaking.) The mill's two products come off the rolling line at different rates: Tons per hour: Bands Coils 200 140 and they also have different profitabilities: Profit per ton: Bands Coils $25 $30 To further complicate matters, the following weekly production amounts are the most that can be justified in light of the currently booked orders: Maximum tons: Bands Coils 6,000 4,000 The question facing the company is as follows: If 40 hours of production time are available this week, how many tons of bands and how many tons of coils should be produced to bring in the greatest total profit? While we are given numeric values for production rates and per-unit profits, the tons of bands and of coils to be produced are as yet unknown. These quantities are the decision variables whose values we must determine so as to maximize profits. The purpose of the linear program is to specify the profits and production limitations as explicit formulas involving the variables, so that the desired values of the variables can be determined systematically. In an algebraic statement of a linear program, it is customary to use a mathematical shorthand for the variables. Thus we will write X B for the number of tons of bands to be produced, and X C for tons of coils. The total hours to produce all these tons is then given by (hours to make a ton of bands) X B + (hours to make a ton of coils) XC This number cannot exceed the 40 hours available. Since hours per ton is the reciprocal of the tons per hour given above, we have a constraint on the variables: (1/200) X B + (1/140) X C There are also production limits: 0 0 XB XC 6000 4000 40. SECTION 1.1 A TWO-VARIABLE LINEAR PROGRAM 3 In the statement of the problem above, the upper limits were specified, but the lower limits were assumed it was obvious that a negative production of bands or coils would be meaningless. Dealing with a computer, however, it is necessary to be quite explicit. By analogy with the formula for total hours, the total profit must be (profit per ton of bands) X B + (profit per ton of coils) XC That is, our objective is to maximize 25 X B + 30 X C . Putting this all together, we have the following linear program: Maximize 25 X B + 30 X C Subject to (1/200) X B + (1/140) X C 0 X B 6000 0 X C 4000 40 This is a very simple linear program, so we'll solve it by hand in a couple of ways, and then check the answer with AMPL. First, by multiplying profit per ton times tons per hour, we can determine the profit per hour of mill time for each product: Profit per hour: Bands Coils $5,000 $4,200 Bands are clearly a more profitable use of mill time, so to maximize profit we should produce as many bands as the production limit will allow 6,000 tons, which takes 30 hours. Then we should use the remaining 10 hours to make coils 1,400 tons in all. The profit is $25 times 6,000 tons plus $30 times 1,400 tons, for a total of $192,000. Alternatively, since there are only two variables, we can show the possibilities graphically. If X B values are plotted along the horizontal axis, and X C values along the vertical axis, each point represents a choice of values, or solution, for the decision variables: Constraints 6000 Coils 4000 2000 feasible region Hours 0 Bands 0 2000 4000 6000 8000 4 PRODUCTION MODELS: MAXIMIZING PROFITS CHAPTER 1 The horizontal line represents the production limit on coils, the vertical on bands. The diagonal line is the constraint on hours; each point on that line represents a combination of bands and coils that requires exactly 40 hours of production time, and any point downward and to the left requires less than 40 hours. The shaded region bounded by the axes and these three lines corresponds exactly to the feasible solutions those that satisfy all three constraints. Among all the feasible solutions represented in this region, we seek the one that maximizes the profit. For this problem, a line of slope -25/30 represents combinations that produce the same profit; for example, in the figure below, the line from (0, 4500) to (5400, 0) represents combinations that yield $135,000 profit. Different profits give different but parallel lines in the figure, with higher profits giving lines that are higher and further to the right. Profit 6000 $220K Coils 4000 $192K 2000 $135K 0 Bands 0 2000 4000 6000 8000 If we combine these two plots, we can see the profit-maximizing, or optimal, feasible solution: 6000 Coils 4000 Optimal Solution 2000 0 Bands 0 2000 4000 6000 8000 SECTION 1.2 THE TWO-VARIABLE LINEAR PROGRAM IN AMPL 5 The line segment for profit equal to $135,000 is partly within the feasible region; any point on this line and within the region corresponds to a solution that achieves a profit of $135,000. On the other hand, the line for $220,000 does not intersect the feasible region at all; this tells us that there is no way to achieve a profit as high as $220,000. Viewed in this way, solving the linear program reduces to answering the following question: Among all profit lines that intersect the feasible region, which is highest and furthest to the right? The answer is the middle line, which just touches the region at one of the corners. This point corresponds to 6,000 tons of bands and 1,400 tons of coils, and a profit of $192,000 the same as we found before. 1.2 The two-variable linear program in AMPL Solving this linear program with AMPL can be as simple as typing AMPL's description of the linear program, var XB; var XC; maximize Profit: 25 * XB subject to Time: (1/200) subject to B_limit: 0 <= subject to C_limit: 0 <= + 30 * XC; * XB + (1/140) * XC <= 40; XB <= 6000; XC <= 4000; into a file call it p r o d0. mod and then typing a few AMPL commands: ampl: model prod0.mod; ampl: solve; MINOS 5.5: optimal solution found. 2 iterations, objective 192000 ampl: display XB, XC; XB = 6000 XC = 1400 ampl: quit; The invocation and appearance of an AMPL session will depend on your operating environment and interface, but you will always have the option of typing AMPL statements in response to the a mpl : prompt, until you leave AMPL by typing quit. (Throughout the book, material you type is shown in this slanted font.) The AMPL linear program that you type into the file parallels the algebraic form in every respect. It specifies the decision variables, defines the objective, and lists the constraints. It differs mainly in being somewhat more formal and regular, to facilitate computer processing. Each variable is named in a va r statement, and each constraint by a statement that begins with s u bj e c t t o and a name like Ti me or B_l i mi t for the constraint. Multiplication requires an explicit * operator, and the relation is written <=. The first command of your AMPL session, mod e l pr od0 . mod, reads the file into AMPL, just as if you had typed it line-by-line at a mpl : prompts. You then need only