Nội dung

3GCH10 09/03/2013 13:50:41 Page 257 Find more at www.downloadslide.com 10 10.1 Optimization of Network Models INTRODUCTION As mentioned in the previous chapter, there are four main types of linear programming structures, three of which we covered in that chapter. The fourth type is the network model, which is the subject of this chapter. Network models themselves fall into several categories, but what is common in our approach to all network models is that we use a diagram to help formulate and solve linear programming problems. The network model describes patterns of flow in a connected system, where the flow might involve material, people, or funds. The system elements may be locations, such as cities, warehouses, or assembly lines; or they may be points in time rather than points in space. When we construct diagrams to represent such systems, the elements are represented by nodes, or circles, in the diagram. The paths of flow are represented by arcs, or arrows. Figure 10.1 shows a very simple diagram, in which the network elements are a factory (node 1) and two warehouses (nodes 2 and 3). The arc from node 1 to node 2 carries the flow (truckloads of goods, perhaps) from the factory to the first warehouse; similarly, the arc from node 1 to node 3 carries the flow from the factory to the second warehouse. As we shall see, drawing a network diagram helps us formulate an appropriate linear programming model, and if we encounter difficulties in getting our model to work, the diagram can also be a helpful device for troubleshooting. 10.2 THE TRANSPORTATION MODEL A very common supply chain involves the shipment of goods from suppliers at one set of locations to customers at another set of locations. The supplier may own several factories that fabricate component parts, while the customers could be represented by the assembly plants that build and test products. Alternatively, the supplier may be a wholesaler who stocks food in several warehouses, while the customers are a chain of grocery stores that reorder separately on a regular basis. A supply-chain structure of this sort lends itself to representation as a transportation model. The classic transportation model is characterized by a set of supply sources (each with known capacities), a set of demand locations (each with known requirements), and the unit costs of transportation between supply-demand pairs. A case in point is Bonner Electronics. FIGURE 10.1 A Simple Network Diagram 2 1 3 257 3GCH10 09/03/2013 13:50:42 Page 258 Find more at www.downloadslide.com 258 CHAPTER 10 OPTIMIZATION OF NETWORK MODELS EXAMPLE Bonner Electronics Bonner Electronics is planning next week’s shipments from its three manufacturing plants to its four distribution warehouses and is seeking a minimum-cost shipping schedule. Each plant has a potential capacity, expressed in cartons of product, and each warehouse has a week’s requirement that must be met. There are twelve possible shipment routes, and for each route, the unit shipping cost is known. The following table provides the given information for this example: Warehouse Plant Atlanta Boston Chicago Denver Capacity Minneapolis Pittsburgh Tucson $0.60 0.36 0.65 $0.56 0.30 0.68 $0.22 0.28 0.55 $0.40 0.58 0.42 9,000 12,000 13,000 Requirement 7,500 8,500 9,500 8,000 & 10.2.1 Flow Diagram A flow diagram showing the possible routes is depicted in Figure 10.2. In the diagram, the node letters on the left designate manufacturing plants, which supply the product. The node letters on the right stand for warehouses, where the demands occur. In this case, all supply-demand pairs represent feasible routes for the shipment plan. Each route of flow incurs a cost: the unit cost of flow from any plant to any warehouse is given in the table containing the parameters of the problem. The flows along each of the twelve possible routes constitute the decision variables in the model. Although the diagram does not contain labels for the arcs, it would be natural to use the notation MA for the quantity shipped on the route from Minneapolis to Atlanta, MB for the quantity shipped on the route from Minneapolis to Boston, and so on. In the network diagram, each arc represents a decision. 10.2.2 Model Formulation The transportation model has two kinds of constraints: less-than capacity constraints and greater-than demand constraints, assuming total demand does not exceed capacity. For the Minneapolis plant, we can express the capacity constraint as follows: MA þ MB þ MC þ MD  9;000 In words, the total amount shipped out of Minneapolis must be less than or equal to the Minneapolis capacity. For Pittsburgh and Tucson, we have similar constraints: PA þ PB þ PC þ PD  12;000 TA þ TB þ TC þ TD  13;000 FIGURE 10.2 Diagram for Bonner Electronics A M B The left-hand side of these constraints simply adds the outbound shipment quantities from a given location. For that reason, we don’t really need to use the SUMPRODUCT formula in a spreadsheet representation; we can use the simpler SUM formula. For the Atlanta warehouse, the demand constraint reads: P MA þ PA þ TA  7;500 T In words, the amount received at Atlanta must be greater than or equal to the Atlanta requirement. Similarly, for the other three warehouses, the demand constraints become: C D MB þ PB þ TB  8;500 MC þ PC þ TC  9;500 MD þ PD þ TD  8;000 3GCH10 09/03/2013 13:50:45 Page 259 Find more at www.downloadslide.com 10.2 THE TRANSPORTATION MODEL 259 Again, the left-hand sides of these constraints can easily be expressed using the SUM formula. Putting both kinds of constraints together, and building an objective function from the same set of variables, we can create the following algebraic statement of the model: Minimize z ¼ 0:60MA þ 0:56MB þ 0:22MC þ 0:40MD þ 0:36PA þ 0:30PB þ 0:28PC þ 0:58PD þ 0:65TA þ 0:68TB þ 0:55TC þ 0:42TD subject to MA þ MB þ MC þ MD PA þ PB þ PC þ PD TA þ TB þ TC þ TD MA þ PA þ TA MB þ PB þ TB MC þ PC þ TC MD þ PD þ TD  9;000  12;000  13;000  7;500  8;500  9;500  8;000 10.2.3 Spreadsheet Model Figure 10.3 displays a worksheet for this problem. Notice the distinctive From/To structure in the table describing the problem’s data. This structure lends itself readily to a row-and-column format, which is the essence of spreadsheet layout. Here, we adopt the convention that flow moves conceptually from the rows of the worksheet to the columns—for example, from Minneapolis to Atlanta. Because of this From/To structure, it is helpful to depart from the standard linear programming layout of the previous chapter and adopt a special format for this type of model. In particular, we can construct a model in rows and columns to mirror the table of parameters that describes the problem. In the Parameters module of the worksheet, we see all of the unit costs displayed in an array. In the Decisions module, the decision variables (shaded for highlighting) appear in an array of the same size. At the right of each decision row is the “Sent” quantity, which is simply the sum of the flows along the row. These figures align with the capacities given in the Parameters module. Below each decision column is the “Received” quantity, which is the sum down the column. These figures align with the demands given in the Parameters FIGURE 10.3 Worksheet for the Bonner Electronics Model  To download spreadsheets for this chapter, go to the Student Companion site at www.wiley.com/college/powell. 3GCH10 09/03/2013 13:50:45 Page 260 Find more at www.downloadslide.com 260 CHAPTER 10 OPTIMIZATION OF NETWORK MODELS module. The objective function, which is expressed as a SUMPRODUCT in cell C18, is the total transportation cost for the system. A useful exercise for someone encountering the transportation model for the first time is to clear the decision-variable cells C12:F14 and search by trial and error for a low-cost shipment plan. EXCEL MINILESSON The SUMPRODUCT Function The SUMPRODUCT function in Excel takes the pairwise products of two sets of numbers and sums the products. The form of the function is the following: SUMPRODUCT(Array 1, Array 2)   Array1 references the first set of numbers. Array2 references the second set of numbers. In the standard form for linear programs, introduced in Chapter 9, the two arrays were each laid out as one row and several columns. However, in general, the arrays can be m rows by n columns, as long as both arrays are of the same size. It is this more general structure that we employ in the & transportation model and other, similar models. 10.2.4 Optimization Now, with this formulation in mind, we can invoke Solver and specify: Variables: C12:F14 Objective: C18 ðminimizeÞ Constraints: C15:F15  C8:F8 ðReceived  RequiredÞ G12:G14  G5:G7 ðSent  CapacityÞ On the Engine tab of the task pane, we select the Standard LP/Quadratic Engine (the linear solver) and check that the Assume Non-Negative option is set to True. We obtain the solution shown in Figure 10.4, which achieves the minimum cost of $12,025. All requirement constraints in this solution are binding, even though we permitted the model to send more than the requirement to each warehouse. This result makes intuitive sense, because shipping more than is required to any warehouse would merely incur excess cost. Once we understand why there is no incentive to exceed demand, we can anticipate that there will be some excess capacity in the solution. This follows from the fact that total capacity comes to 34,000 cartons, while total demand comes to only 33,500. In particular, capacity constraints are binding at Pittsburgh and Minneapolis, but an excess capacity of 500 cartons remains at Tucson. FIGURE 10.4 Optimal Solution to the Bonner Electronics Model 3GCH10 09/03/2013 13:50:46 Page 261 Find more at www.downloadslide.com 10.2 THE TRANSPORTATION MODEL FIGURE 10.5 Revised Flow Diagram for Bonner Electronics Capacities Flows Demands A 9000 P T B 8500 9000 4000 13000 7500 3500 M 8500 12000 261 C 9500 500 8000 D 8000 Now let’s return to the diagram for our problem and check the figures. This time, we simplify the diagram by ignoring the variables that turned out to be zero, and we include just the nonzero shipments. Figure 10.5 shows the revised version of the network diagram. At each node, arcs enter and arcs leave. We want to check that the configurations make sense at each location. For example, at node M, there is one outbound flow of 9,000 cartons, which exactly meets capacity. At node P, there are two outbound flows totaling 12,000, also meeting capacity. And at node T, there are three outbound flows totaling 12,500, which is less than capacity. A similar check shows that the inbound flows meet the various demand requirements. 10.2.5 Modifications to the Model The model layout in Figure 10.4 has another virtue: it is easily expandable. Consider, for example, how to adapt the model to the situation in which Bonner Electronics adds a warehouse facility to its system. In Excel, select column E and then select InsertI Columns. Figure 10.6 shows the result: both arrays (unit costs and decision variables) are expanded. The following steps are required to update the worksheet:   FIGURE 10.6 Expanded Version of the Bonner Electronics Model Enter the location of the new warehouse in cells E4 and E11. Enter the inbound costs to the new warehouse in cells E5:E7. 3GCH10 09/03/2013 13:50:47 Page 262 Find more at www.downloadslide.com 262 CHAPTER 10 OPTIMIZATION OF NETWORK MODELS FIGURE 10.7 Model Specifications Window for the Expanded Version of the Model  Enter the demand at the new warehouse in cell E8.  Copy the formula in cell D15 to E15. After taking these steps, we click the Refresh icon on the Model tab. The task pane tells us that the model is ready to solve, as shown in Figure 10.7. In other words, the constraint formulas in cells H12:H14 have automatically adapted to the expansion, and so has the objective function formula in cell C18. One last feature of the transportation model is worth noting: it lends itself readily to the use of range names in Excel. Working with the model of Figure 10.4, we can add range names in the following locations:       Cell C18 named “Cost” Cells C12:F14 named “Shipments” Cells G5:G7 named “Capacity” Cells G12:G14 named “Sent” Cells C8:F8 named “Demands” Cells C15:F15 named “Received” With these names assigned, the specification in the task pane takes the form shown in Figure 10.8. This format communicates the model to the user in a different way. The specification of the model is somewhat self-documenting in this form. The range names would be useful when the model is fully debugged and offered to users who are not comfortable with the cell details that usually appear. 10.2.6 Sensitivity Analysis The concepts of sensitivity analysis that were introduced in the previous chapter apply here as well. This means that the Optimization Sensitivity tool may be used with network linear programming models with no new considerations. It also means that we can interpret patterns in the optimal solution in terms of economic priorities. Shadow prices in our network example illustrate the concepts involved. (Recall from Chapter 9 that a shadow price is the break-even price at which it would be profitable to acquire more of a scarce resource.) In the transportation model, we have supply and demand constraints, and the solution to the model provides shadow prices on each. The shadow price on a demand 3GCH10 09/03/2013 13:50:48 Page 263 Find more at www.downloadslide.com 10.2 THE TRANSPORTATION MODEL 263 FIGURE 10.8 Bonner Electronics Model with Range Names Added constraint tells us how much it costs to ship the marginal unit to the corresponding location, and sometimes this figure is not obvious without some careful thought. Consider the demand at the Boston warehouse in the Bonner Electronics example. In the base case, shown in Figures 10.4 and 10.5, Boston demand is 8,500 cartons. This quantity is all supplied from Pittsburgh, incurring a shipping cost of $0.30 per carton. Suppose we vary the demand parameter from 8,200 to 8,800 in steps of 100 and examine the optimal solution. Figure 10.9 shows the resulting output from the Optimization Sensitivity tool. As expected, the optimal total cost increases when Boston demand increases, but from the Change column of the report, we note that the marginal cost of meeting this demand is $0.59. How do we reconcile the direct cost of $0.30 on the Pittsburgh–Boston route with the marginal cost of $0.59? One way to see the connection involves identifying the qualitative pattern in the problem’s solution. In the previous chapter, we introduced the process of discovering a pattern in the optimal solution to a linear programming model. The main idea was to focus on positive variables and binding constraints, and then to identify a priority list that specifies the sequence in which the variables may be calculated. In network models, the steps can be facilitated by using network diagrams. In this example, there are three supplies and four demands, giving rise to twelve possible shipment routes. However, the solution contains only six nonzero shipments: MC, PA, PB, TA, TC, and TD. The other routes can be ignored when constructing the pattern. This observation allows us to work with the simplified network diagram of Figure 10.5. As we previously observed, all of the demand constraints are binding. The solution also tells us that two of the supply capacities are binding—in particular, the capacities at Minneapolis and Pittsburgh. The decision variables associated with Tucson are not determined by the capacity at Tucson; instead, as we shall see, they are determined by other constraints in the model. FIGURE 10.9 Optimization Sensitivity Output for the Bonner Electronics Model 3GCH10 09/03/2013 13:50:52 Page 264 Find more at www.downloadslide.com 264 CHAPTER 10 OPTIMIZATION OF NETWORK MODELS FIGURE 10.10 Diagram for the Reduced Problem Capacities Flows Demands A 7500 3500 M B 3500 P 4000 500 C 500 500 T D In the optimal solution, some demands are met entirely from a unique source. For example, demand at Boston is all met from Pittsburgh, and demand at Denver is all met from Tucson. In some sense, these are high-priority allocations, and we can think of them as if they were made first. There is also a symmetric feature: supply from Minneapolis all goes to Chicago. Dedicating capacity to a unique demand also marks a high-priority allocation. Each of these variables appears alone (with no other positive variables) in a binding constraint. Once we assign the high-priority allocations, we can ignore the supply at Minneapolis and the demands at Boston and Denver, and we can turn to the problem that remains. Thus, we proceed to a second priority level, where we are left with a reduced problem containing two sources and two destinations, as shown in Figure 10.10. Here PA and TC are the high-priority allocations in the reduced problem. Setting PA ¼ 3,500 consumes the remaining capacity at Pittsburgh; setting TC ¼ 500 covers the remaining demand at Chicago. Having made the second priority assignments, we can ignore the supply at Pittsburgh and the demand at Chicago. We are left with a net demand at Atlanta and unallocated supply at Tucson, as shown in Figure 10.11. Thus, the last step, at the third priority level, is to meet the remaining demand with a shipment along route TA. This allocation leaves an excess supply of 500 cartons at the Tucson factory, demonstrating that the utilization of the Tucson supply has been dictated by the supply and demand constraints elsewhere in the problem. FIGURE 10.11 Diagram for the Last Stage of the Reduced Problem Capacities Flows Demands A M B P 4000 4500 C T D 4000 3GCH10 09/03/2013 13:50:52 Page 265 Find more at www.downloadslide.com 10.2 THE TRANSPORTATION MODEL 265 Here is a brief statement of the process, as it applies in general to the solution of a transportation model:  Identify a high-priority demand—one that is covered by a unique source—and allocate the entire demand to this route. Remove this demand from consideration.  Identify a high-priority capacity—one that supplies a single destination—and allocate the entire supply to this route. Remove this supply from consideration.  Repeat the previous two steps using remaining demands and remaining supplies each time, until all shipments are accounted for. Here is how the process works in the Bonner example: 1. Ship as much as possible on routes PB, TD, and MC. 2. Proceed to the reduced problem at the second priority level and ship as much as possible on routes PA and TC. 3. Proceed to the reduced problem at the third priority level and ship as much as possible on route TA. At each allocation, “as much as possible” is dictated by the minimum of remaining capacity and remaining demand. Looking back, we can see that this three-stage description characterizes the optimal solution without explicitly using a number. By describing the optimal solution without using the parameters in the problem, we have portrayed a qualitative pattern in the solution and translated it into a list of economic priorities. This retrospective description of the solution is complete and unambiguous. Anyone who constructs a solution using these steps will reach the same result. This pattern holds not just for the specific problem that we solved but also for similar problems that have some of the parameters slightly altered. For example, suppose that demand at Boston increased by 250 to 8,750. We could verify that the same pattern applies. The revised details of implementing the same pattern are shown in Figure 10.12, where we can see that three of the decision variables have been altered in response to the increased demand at Boston. Furthermore, if we track the cost implications of these changes, we can calculate that the increase in total transportation cost is 0:36ð3250  3500Þ þ 0:30ð8750  8500Þ þ 0:65ð4250  4000Þ ¼ 0:36ð250Þ þ 0:30ð250Þ þ 0:65ð250Þ ¼ 0:59ð250Þ ¼ $147:50: Thus, our calculations reveal that the incremental cost of shipment to Boston is $147.50/250 ¼ $0.59. Although the direct cost is only $0.30, the limited capacity at Pittsburgh forces us to compensate for the additional shipment to Boston by making adjustments elsewhere (while maintaining the optimal pattern). These adjustments lead us to a marginal cost of $0.59. More generally, we can alter the original problem in several ways at once. Suppose demands at Atlanta, Boston, and Chicago are each raised by 100 simultaneously. What will FIGURE 10.12 Changes in the Diagram for the Altered Problem Capacities Flows Demands A 9000 3250 M 8750 12000 P T B 8750 9000 4250 13000 7500 C 9500 500 8000 D 8000 3GCH10 09/03/2013 13:50:54 Page 266 Find more at www.downloadslide.com 266 CHAPTER 10 OPTIMIZATION OF NETWORK MODELS FIGURE 10.13 Changes in the Diagram When Three Demands Change Capacities Flows Demands A 9000 3400 M 8600 12000 P B 8600 9000 4200 13000 7600 C 9600 600 T 8000 D 8000 the optimal plan look like? In qualitative terms, we already know. The qualitative pattern of economic priorities allows us to write down the optimal solution to the revised problem without rerunning Solver, but rather by using the pattern’s three-stage priority list and adjusting the shipment quantities for the modifications in demands. Tracing the cost implications, as shown in the diagram of Figure 10.13, we find that the 100-unit increases in the three demands will combine to increase the optimal total cost by 0:36ð3400  3500Þ þ 0:30ð8600  8500Þ þ 0:65ð4200  4000Þ þ 0:55ð600  500Þ ¼ 0:36ð100Þ þ 0:30ð100Þ þ 0:65ð200Þ þ 0:55ð100Þ ¼ 1:79ð100Þ ¼ $179: On a per-unit basis, this is an increase of $1.79, which corresponds to the sum of the shadow prices on the first three demand constraints. 10.3 ASSIGNMENT MODEL An important special case of the transportation problem occurs when all capacities and all requirements are equal to one. In addition, total supply equals total demand. This special case is known as the assignment problem. The classic assignment model is characterized by a set of people, a set of tasks, and a score for each possible assignment of a person to a task. The problem is to find the best assignment of people to tasks. This model can be applied to the medley relay in swimming. EXAMPLE The Buchanan Swim Club Coach Kemppel is the coach of the Buchanan Swim Club’s co-ed team. Her team competes against other swim clubs, and a perennial question for the coach is how to organize the medley relay team. The medley relay requires four swimmers to each swim a different stroke: butterfly, breaststroke, backstroke, and freestyle. The relay is the final event in the competitions, and the outcome of the swim meet often depends on the performance of the relay team. During practice, Coach Kemppel has asked each of her top four swimmers to try each of the four strokes, and she has tracked their times (in seconds), as shown in the following table: Stroke Todd Betsy Lee Carly Butterfly Breaststroke Backstroke Freestyle 38 34 41 33 75 76 71 80 44 43 41 45 27 25 26 30 With this information, Coach Kemppel is ready to assign swimmers to strokes in the relay race, & but she can see that a lot of combinations are possible.