04.pdf

CHAPTER 4: LINEAR PROGRAMMING: MODELING EXAMPLES Overview In this chapter, more complex examples of model formulation are presented. These examples have been selected to illustrate some of the more popular application areas of linear programming. They also provide guidelines for...

CHAPTER 4: LINEAR PROGRAMMING: MODELING EXAMPLES Overview In this chapter, more complex examples of model formulation are presented. These examples have been selected to illustrate some of the more popular application areas of linear programming. They also provide guidelines for model formulation for a variety of problems and computer solutions with Excel and QM for Windows. You will notice as you go through each example that the model formulation is presented in a systematic format. First, decision variables are identified, then the objective function is formulated, and finally the model constraints are developed. Model formulation can be difficult and complicated, and it is usually beneficial to follow this set of steps in which you identify a specific model component at each step instead of trying to ―see‖ the whole formulation after the first reading. Learning Outcomes At the end of this lesson, students must be able to:  Apply model formulation in different application areas of linear programming COURSE MATERIALS A Product Mix Example Quick-Screen is a clothing manufacturing company that specializes in producing commemorative shirts immediately following major sporting events such as the World Series, Super Bowl, and Final Four. The company has been contracted to produce a standard set of shirts for the winning team, either State University or Tech, following a college football bowl game on New Year’s Day. tThe company has to complete all production within 72 hours after the game, at which time a trailer truck will pick up the shirts. The company will work around the clock. The truck has enough capacity to accommodate 1,200 standard-size boxes. A standardsize box holds 12 T- shirts, and a box of 12 sweatshirts is three times the size of a standard box. The company has budgeted $25,000 for the production run. It has 500 dozen blank sweatshirts and T-shirts each in stock, ready for production. This scenario is illustrated in Figure 4.1. 43 The company wants to know how many dozen (boxes) of each type of shirt to produce in order to maximize profit. Figure 4.1 Quick-Screen Shirts Decision Variables 44 This problem contains four decision variables, representing the number of dozens (boxes) of each type of shirt to produce: x1 = sweatshirts, front printing x2 = sweatshirts, back and front printing x3 = T-shirts, front printing x4 = T-shirts, back and front printing The Objective Function The company’s objective is to maximize profit. The total profit is the sum of the individual profits gained from each type of shirt. The objective function is expressed as maximize Z = $90x1 + 125x2 + 45x3 + 65x4 Model Constraints The first constraint is for processing time. The total available processing time is the 72-hour period between the end of the game and the truck pickup: 0.10x + 0.25x2 + 0.08x3 + 0.21x4 ≤ 72 hr The second constraint is for the available shipping capacity, which is 1,200 standard-size boxes. A box of sweatshirts is three times the size of a standard-size box. Thus, each box of sweatshirts is equivalent in size to three boxes of T-shirts. This relative size differential is expressed in the following constraint: 3x1 + 3x2 + x3 + x4 ≤ 1,200 boxes The third constraint is for the cost budget. The total budget available for production is $25,000: $36x1 + 48x2 + 25x3 + 35x4 ≤ $25,000 The last two constraints reflect the available blank sweatshirts and T-shirts the company has in storage: x1 + x2 ≤ 500 dozen sweatshirts x3 + x4 ≤ 500 dozen T-shirts Model Summary The linear programming model for Quick-Screen is summarized as follows: maximize Z = 90x1 + 125x2 + 45x3 + 65x4 45 subject to 0.10x1 + 0.25x2 + 0.08x3 + 0.21x4 ≤ 72 3x1 + 3x2 + x3 + x4 ≤ 1,200 36x1 + 48x2 + 25x3 + 35x4 ≤ 25,000 x1 + x2 ≤ 500 x3 + x4 ≤ 500 x1, x2, x3, x4 >_ 0 Computer Solution with Excel The Excel spreadsheet solution for this product mix example is shown in Exhibit 4.1. The decision variables are located in cells B14:B17. The profit is computed in cell B18, and the formula for profit, =B14*D5+B15*E5+B16*F5+B17*G5, is shown on the formula bar at the top of the spreadsheet. The constraint formulas are embedded in cells H7 through H11, under the column titled ―Usage.‖ For example, the constraint formula for processing time in cell H7 is =D7*B14+E7*B15+F7*B16+G7*B17. Cells H8 through H11 have similar formulas. Cells K7 through K11 contain the formulas for the leftover resources, or slack. For example, cell K7 contains the formula =J7–H7. These formulas for leftover resources enable us to Exhibit 4.1 demonstrate a spreadsheet operation that can save you time in developing the spreadsheet model. First, enter the formula for leftover resources, J7–H7, in cell K7, as we have already shown. Next, using the right mouse button, click on ―Copy.‖ Then cover cells K8:K11 with the cursor (by holding the left mouse button down). Click the right mouse button again and then click on ―Paste.‖ This will automatically insert the correct formulas for leftover resources in cells K8 through K11 so that you do not have to type them all in individually. This copying operation 46 can be used when the variables in the formula are all in the same row or column. The copying operation simply increases the row number for each cell that the formulas are copied into (i.e., J8 and H8, J9 and H9, J10 and H10, and J11 and H11). Also, note the model formulation in the box in the lower right-hand corner of the spreadsheet in Exhibit 4.1. The model formulations for the remaining linear programming models in this and other chapters are included on the Excel files on the companion website accompanying this text. The Solver Parameters window for this model is shown in Exhibit 4.2. Notice that we were able to insert all five constraint formulas with one line in the ―Subject to the Constraints:‖ box. We used the constraint H7:H11