INTRODUCTION TO LINEAR PROGRAMMING:PROTOTYPE EXAMPLE

PROTOTYPE EXAMPLE

The WYNDOR GLASS CO. produces high-quality glass products, including windows and glass doors. It has three plants. Aluminum frames and hardware are made in Plant 1, wood frames are made in Plant 2, and Plant 3 produces the glass and assembles the products.

Because of declining earnings, top management has decided to revamp the company’s product line. Unprofitable products are being discontinued, releasing production capacity to launch two new products having large sales potential:

Product 1: An 8-foot glass door with aluminum framing Product 2: A 4 X 6 foot double-hung wood-framed window

Product 1 requires some of the production capacity in Plants 1 and 3, but none in Plant 2. Product 2 needs only Plants 2 and 3. The marketing division has concluded that the com- pany could sell as much of either product as could be produced by these plants. However, because both products would be competing for the same production capacity in Plant 3, it is not clear which mix of the two products would be most profitable. Therefore, an OR team has been formed to study this question.

The OR team began by having discussions with upper management to identify man- agement’s objectives for the study. These discussions led to developing the following defi- nition of the problem:

Determine what the production rates should be for the two products in order to maximize their total profit, subject to the restrictions imposed by the limited production capacities available in the three plants. (Each product will be produced in batches of 20, so the

An Application Vignette

Swift & Company is a diversified protein-producing business based in Greeley, Colorado. With annual sales of over $8 billion, beef and related products are by far the largest portion of the company’s business.

To improve the company’s sales and manufacturing performance, upper management concluded that it needed to achieve three major objectives. One was to enable the company’s customer service representatives to talk to their more than 8,000 customers with accurate informa- tion about the availability of current and future inven- tory while considering requested delivery dates and maximum product age upon delivery. A second was to produce an efficient shift-level schedule for each plant over a 28-day horizon. A third was to accurately deter- mine whether a plant can ship a requested order-line-item quantity on the requested date and time given the

availability of cattle and constraints on the plant’s capacity.

To meet these three challenges, an OR team devel- oped an integrated system of 45 linear programming models based on three model formulations to dynami- cally schedule its beef-fabrication operations at five plants in real time as it receives orders. The total audited benefits realized in the first year of operation of this sys- tem were $12.74 million, including $12 million due to optimizing the product mix. Other benefits include a reduction in orders lost, a reduction in price discounting, and better on-time delivery.

Source: A. Bixby, B. Downs, and M. Self, “A Scheduling and Capable-to-Promise Application for Swift & Company,” Inter- faces, 36(1): 39–50, Jan.–Feb. 2006. (A link to this article is provided on our website, www.mhhe.com/hillier.)

production rate is defined as the number of batches produced per week.) Any combination of production rates that satisfies these restrictions is permitted, including producing none of one product and as much as possible of the other.

The OR team also identified the data that needed to be gathered:

1. Number of hours of production time available per week in each plant for these new products. (Most of the time in these plants already is committed to current products, so the available capacity for the new products is quite limited.)

2. Number of hours of production time used in each plant for each batch produced of each new product.

3. Profit per batch produced of each new product. (Profit per batch produced was cho- sen as an appropriate measure after the team concluded that the incremental profit from each additional batch produced would be roughly constant regardless of the total number of batches produced. Because no substantial costs will be incurred to initiate the production and marketing of these new products, the total profit from each one is approximately this profit per batch produced times the number of batches produced.)

Obtaining reasonable estimates of these quantities required enlisting the help of key personnel in various units of the company. Staff in the manufacturing division provided the data in the first category above. Developing estimates for the second category of data required some analysis by the manufacturing engineers involved in designing the produc- tion processes for the new products. By analyzing cost data from these same engineers and the marketing division, along with a pricing decision from the marketing division, the accounting department developed estimates for the third category.

Table 3.1 summarizes the data gathered.

The OR team immediately recognized that this was a linear programming problem of the classic product mix type, and the team next undertook the formulation of the corre- sponding mathematical model.

The objective is to choose the values of x1 and x2 so as to maximize Z = 3x1 + 5x2, subject to the restrictions imposed on their values by the limited production capacities available in the three plants. Table 3.1 indicates that each batch of product 1 produced per week uses 1 hour of production time per week in Plant 1, whereas only 4 hours per week are available. This restriction is expressed mathematically by the inequality x1 < 4. Similarly, Plant 2 imposes the restriction that 2x2 < 12. The number of hours of production time used per week in Plant 3 by choosing x1 and x2 as the new products’ production rates would be 3x1 + 2x2. Therefore, the mathematical statement of the Plant 3 restriction is 3x1 + 2x2 < 18. Finally, since production rates cannot be negative, it is necessary to restrict the decision vari- ables to be nonnegative: x1 ::: 0 and x2 ::: 0.

(Notice how the layout of the coefficients of x1 and x2 in this linear programming model essentially duplicates the information summarized in Table 3.1.)

This problem is a classic example of a resource-allocation problem, the most common type of linear programming problem. The key characteristic of resource-allocation problems is that most or all of their functional constraints are resource constraints. The right-hand side of a resource constraint represents the amount available of some resource and the left-hand side represents the amount used of that resource, so the left-hand side must be < the right- hand side. Product-mix problems are one type of resource-allocation problem, but you will see examples of resource-allocations problems of other types in Sec. 3.4 along with examples of other categories of linear programming problems.

Graphical Solution

This very small problem has only two decision variables and therefore only two dimensions, so a graphical procedure can be used to solve it. This procedure involves constructing a two- dimensional graph with x1 and x2 as the axes. The first step is to identify the values of (x1, x2) that are permitted by the restrictions. This is done by drawing each line that borders the range of permissible values for one restriction. To begin, note that the nonnegativity restrictions x1 ::: 0 and x2 ::: 0 require (x1, x2) to lie on the positive side of the axes (includ- ing actually on either axis), i.e., in the first quadrant. Next, observe that the restriction x1 < 4 means that (x1, x2) cannot lie to the right of the line x1 = 4. These results are shown in Fig. 3.1, where the shaded area contains the only values of (x1, x2) that are still allowed.

In a similar fashion, the restriction 2x2 < 12 (or, equivalently, x2 < 6) implies that the line 2x2 = 12 should be added to the boundary of the permissible region. The final restriction, 3x1 + 2x2 < 18, requires plotting the points (x1, x2) such that 3x1 + 2x2 = 18 (another line) to complete the boundary. (Note that the points such that 3x1 + 2x2 < 18 are those that lie either underneath or on the line 3x1 + 2x2 = 18, so this is the limiting line above which points do not satisfy the inequality.) The resulting region of permissible values of (x1, x2),called the feasible region, is shown in Fig. 3.2. (The demo called Graphical Method in your OR Tutor provides a more detailed example of constructing a feasible region.)

The final step is to pick out the point in this feasible region that maximizes the value of Z = 3x1 + 5x2. To discover how to perform this step efficiently, begin by trial and error. Try, for example, Z = 10 = 3x1 + 5x2 to see if there are in the permissible region any val- ues of (x1, x2) that yield a value of Z as large as 10. By drawing the line 3x1 + 5x2 = 10 (see Fig. 3.3), you can see that there are many points on this line that lie within the region. Having gained perspective by trying this arbitrarily chosen value of Z = 10, you should

next try a larger arbitrary value of Z, say, Z = 20 = 3x1 + 5x2. Again, Fig. 3.3 reveals that a segment of the line 3x1 + 5x2 = 20 lies within the region, so that the maximum permis- sible value of Z must be at least 20.

Now notice in Fig. 3.3 that the two lines just constructed are parallel. This is no coin- cidence, since any line constructed in this way has the form Z = 3x1 + 5x2 for the chosen value of Z, which implies that 5x2 = -3x1 + Z or, equivalently,

increases when the These observations imply that our trial-and-error procedure for constructing lines in Fig. 3.3 involves nothing more than drawing a family of parallel lines containing at least one point in the feasible region and selecting the line that corresponds to the largest value of Z. Figure 3.3 shows that this line passes through the point (2, 6), indicating that the optimal solution is x1 = 2 and x2 = 6. The equation of this line is 3x1 + 5x2 = 3(2) + 5(6) = 36 = Z, indicating that the optimal value of Z is Z = 36. The point (2, 6) lies at the intersection of the two lines 2x2 = 12 and 3x1 + 2x2 = 18, shown in Fig. 3.2, so that this point can be calculated algebraically as the simultaneous solution of these two equations.

Having seen the trial-and-error procedure for finding the optimal point (2, 6), you now can streamline this approach for other problems. Rather than draw several parallel lines, it is sufficient to form a single line with a ruler to establish the slope. Then move the ruler with fixed slope through the feasible region in the direction of improving Z. (When the objective is to minimize Z, move the ruler in the direction that decreases Z.) Stop moving the ruler at the last instant that it still passes through a point in this region. This point is the desired optimal solution.

This procedure often is referred to as the graphical method for linear programming. It can be used to solve any linear programming problem with two decision variables. With con- siderable difficulty, it is possible to extend the method to three decision variables but not more than three. (The next chapter will focus on the simplex method for solving larger problems.)

Conclusions

The OR team used this approach to find that the optimal solution is x1 = 2, x2 = 6, with Z = 36. This solution indicates that the Wyndor Glass Co. should produce products 1 and 2 at the rate of 2 batches per week and 6 batches per week, respectively, with a resulting total profit of $36,000 per week. No other mix of the two products would be so profitable— according to the model.

However, we emphasized in Chap. 2 that well-conducted OR studies do not simply find one solution for the initial model formulated and then stop. All six phases described in Chap. 2 are important, including thorough testing of the model (see Sec. 2.4) and postopti- mality analysis (see Sec. 2.3).

In full recognition of these practical realities, the OR team now is ready to evaluate the validity of the model more critically (to be continued in Sec. 3.3) and to perform sensitiv- ity analysis on the effect of the estimates in Table 3.1 being different because of inaccurate estimation, changes of circumstances, etc. (to be continued in Sec. 7.2).

Continuing the Learning Process with Your OR Courseware

This is the first of many points in the book where you may find it helpful to use your OR Courseware on the book’s website. A key part of this courseware is a program called OR Tutor. This program includes a complete demonstration example of the graphical method introduced in this section. To provide you with another example of a model formulation as well, this demonstration begins by introducing a problem and formulating a linear pro- gramming model for the problem before then applying the graphical method step by step to

solve the model. Like the many other demonstration examples accompanying other sections of the book, this computer demonstration highlights concepts that are difficult to convey on the printed page. You may refer to Appendix 1 for documentation of the software.

If you would like to see still more examples, you can go to the Solved Examples section of the book’s website. This section includes a few examples with complete solu- tions for almost every chapter as a supplement to the examples in the book and in OR Tutor. The examples for the current chapter begin with a relatively straightforward prob- lem that involves formulating a small linear programming model and applying the graphi- cal method. The subsequent examples become progressively more challenging.

Another key part of your OR Courseware is a program called IOR Tutorial. This pro- gram features many interactive procedures for interactively executing various solution methods presented in the book, which enables you to focus on learning and executing the logic of the method efficiently while the computer does the number crunching. Included is an interactive procedure for applying the graphical method for linear programming. Once you get the hang of it, a second procedure enables you to quickly apply the graphical method for performing sensitivity analysis on the effect of revising the data of the problem. You then can print out your work and results for your homework. Like the other procedures in IOR Tutorial, these procedures are designed specifically to provide you with an effi- cient, enjoyable, and enlightening learning experience while you do your homework.

When you formulate a linear programming model with more than two decision vari- ables (so the graphical method cannot be used), the simplex method described in Chap. 4 enables you to still find an optimal solution immediately. Doing so also is helpful for model validation, since finding a nonsensical optimal solution signals that you have made a mistake in formulating the model.

We mentioned in Sec. 1.5 that your OR Courseware introduces you to four particularly popular commercial software packages—Excel with its Solver, a powerful Excel add-in called Analytical Solver Platform, LINGO/LINDO, and MPL/Solvers—for solving a variety of OR models. All four packages include the simplex method for solving linear programming mod- els. Section 3.5 describes how to use Excel to formulate and solve linear programming models in a spreadsheet format with either Solver or Analytical Solver Platform for Education (ASPE), descriptions of the other packages are provided in Sec. 3.6 (MPL and LINGO), Sup- plements 1 and 2 to this chapter on the book’s website (LINGO), Sec. 4.8 (LINDO and vari- ous solvers of MPL), and Appendix 4.1 (LINGO and LINDO). MPL, LINGO, and LINDO tutorials also are provided on the book’s website. In addition, your OR Courseware includes an Excel file, a LINGO/LINDO file, and an MPL/Solvers file showing how the respective software packages can be used to solve each of the examples in this chapter.