数据、模型与决策(运筹学)课后习题和案例答案007

Chapter 2 Chapter 7 Network Optimization Problems Review Questions 7.1-1 A supply node is a node where the net amount of flow generated is a fixed positive number. A demand node is a node where the net amount of flow generated is a fixed negative number. A transshipment node is a node where the net amount of flow generated is fixed at zero. 7.1-2 The maximum amount of flow allowed through an arc is referred to as the capacity of that arc. 7.1-3 The objective is to minimize the total cost of sending the available supply through the network to satisfy the given demand. 7.1-4 The feasible solutions property is necessary. It states that a minimum cost flow problem will have a feasible solution if and only if the sum of the supplies from its supply nodes equals the sum of the demands at its demand nodes. 7.1-5 As long as all its supplies and demands have integer values, any minimum cost flow problem with feasible solutions is guaranteed to have an optimal solution with integer values for all its flow quantities. 7.1-6 Network simplex method. 7.1-7 Applications of minimum cost flow problems include operation of a distribution network, solid waste management, operation of a supply network, coordinating product mixes at plants, and cash flow management. 7.1-8 Transportation problems, assignment problems, transshipment problems, maximum flow problems, and shortest path problems are special types of minimum cost flow problems. 7.2-1 One of the company’s most important distribution centers (Los Angeles) urgently needs an increased flow of shipments from the company. 7.2-2 Auto replacement parts are flowing through the network from the company’s main factory in Europe to its distribution center in LA. 7.2-3 The objective is to maximize the flow of replacement parts from the factory to the LA distribution center. 7.3-1 Rather than minimizing the cost of the flow, the objective is to find a flow plan that maximizes the amount flowing through the network from the source to the sink. 7.3-2 The source is the node at which all flow through the network originates. The sink is the node at which all flow through the network terminates. At the source, all arcs point away from the node. At the sink, all arcs point into the node. 7.3-3 The amount is measured by either the amount leaving the source or the amount entering the sink. 7.3-4 1. Whereas supply nodes have fixed supplies and demand nodes have fixed demands, the source and sink do not. 2. Whereas the number of supply nodes and the number of demand nodes in a minimum cost flow problem may be more than one, there can be only one source and only one sink in a standard maximum flow problem. 7.3-5 Applications of maximum flow problems include maximizing the flow through a distribution network, maximizing the flow through a supply network, maximizing the flow of oil through a system of pipelines, maximizing the flow of water through a system of aqueducts, and maximizing the flow of vehicles through a transportation network. 7.4-1 The origin is the fire station and the destination is the farm community. 7.4-2 Flow can go in either direction between the nodes connected by links as opposed to only one direction with an arc. 7.4-3 The origin now is the one supply node, with a supply of one. The destination now is the one demand node, with a demand of one. 7.4-4 The length of a link can measure distance, cost, or time. 7.4-5 Sarah wants to minimize her total cost of purchasing, operating, and maintaining the cars over her four years of college. 7.4-6 When “real travel” through a network can end at more that one node, a dummy destination needs to be added so that the network will have just a single destination. 7.4-7 Quick’s management must consider trade-offs between time and cost in making its final decision. 7.5-1 The nodes are given, but the links need to be designed. 7.5-2 A state-of-the-art fiber-optic network is being designed. 7.5-3 A tree is a network that does not have any paths that begin and end at the same node without backtracking. A spanning tree is a tree that provides a path between every pair of nodes. A minimum spanning tree is the spanning tree that minimizes total cost. 7.5-4 The number of links in a spanning tree always is one less than the number of nodes. Furthermore, each node is directly connected by a single link to at least one other node. 7.5-5 To design a network so that there is a path between every pair of nodes at the minimum possible cost. 7.5-6 No, it is not a special type of a minimum cost flow problem. 7.5-7 A greedy algorithm will solve a minimum spanning tree problem. 7.5-8 Applications of minimum spanning tree problems include design of telecommunication networks, design of a lightly used transportation network, design of a network of high-voltage power lines, design of a network of wiring on electrical equipment, and design of a network of pipelines. Problems 7.1 a) b) c) 7.2 a) b) c) 7.3 a) b) c) 7.4 a) b) c) The total shipping cost is $2,187,000. 7.5 a) b) c) d) e) f) $1,618,000 + $583,000 = $2,201,000 which is higher than the total in Problem 7.5 ($2,187,000). 7.6 There are only two arcs into LA, with a combined capacity of 150 (80 + 70). Because of this bottleneck, it is not possible to ship any more than 150 from ST to LA. Since 150 actually are being shipped in this solution, it must be optimal. 7.7 7.8 a) b) 7.9 a) b) c) d) 7.10 Shortest path: Fire Station – C – E – F – Farming Community 7.11 a) b) c) Shortest route: Origin – A – B – D – Destination d) Yes e) Yes 7.12 a) b) 7.13 a) Times play the role of distances. b) 7.14 1. C---D: Cost = 1 4. E---G: Cost = 5 E---F: Cost = 1 *choose arbitrarily D---A: Cost = 4 2. E---G: Cost = 5 E---B: Cost = 7 E---B: Cost = 7 F---G: Cost = 7 E---C: Cost = 4 C---A: Cost = 5 F---G: Cost = 7 C---B: Cost = 2 *lowest F---C: Cost = 3 *lowest 5. E---G: Cost = 5 F---D: Cost = 4 D---A: Cost = 4 3. E---G: Cost = 5 B---A: Cost = 2 *lowest E---B: Cost = 7 F---G: Cost = 7 F---G: Cost = 7 C---A: Cost = 5 F---D: Cost = 4 6. E---G: Cost = 5 *lowest C---D: Cost = 1 *lowest F---G: Cost = 7 C---A: Cost = 5 C---B: Cost = 2 Total = $14 million 7.15 1. B---C: Cost = 1 *lowest 4. B---E: Cost = 7 2. B---A: Cost = 4 C---F: Cost = 4 *lowest B---E: Cost = 7 C---E: Cost = 5 C---A: Cost = 6 D---F: Cost = 5 C---D: Cost = 2 *lowest 5. B---E: Cost = 7 C---F: Cost = 4 C---E: Cost = 5 C---E: Cost = 5 F---E: Cost = 1 *lowest 3. B---A: Cost = 4 *lowest F---G: Cost = 8 B---E: Cost = 7 6. E---G: Cost = 6 *lowest C---A: Cost = 6 F---G: Cost = 8 C---F: Cost = 4 C---E: Cost = 5 D---A: Cost = 5 Total = $18,000 D---F: Cost = 5 7.16 1. F---G: Cost = 1 *lowest 6. D---A: Cost = 6 2. F---C: Cost = 6 D---B: Cost = 5 F---D: Cost = 5 D---C: Cost = 4 F---I: Cost = 2 *lowest E---B: Cost = 3 *lowest F---J: Cost = 5 F---C: Cost = 6 G---D: Cost = 2 F---J: Cost = 5 G---E: Cost = 2 H---K: Cost = 7 G---H: Cost = 2 I---K: Cost = 8 G---I: Cost = 5 I---J: Cost = 3 3. F---C: Cost = 6 7. B---A: Cost = 4 F---D: Cost = 5 D---A: Cost = 6 F---J: Cost = 5 D---C: Cost = 4 G---D: Cost = 2 *lowest F---C: Cost = 6 G---E: Cost = 2 F---J: Cost = 5 G---H: Cost = 2 H---K: Cost = 7 I---H: Cost = 2 I---K: Cost = 8 I---K: Cost = 8 I---J: Cost = 3 *lowest I---J: Cost = 3 8. B---A: Cost = 4 *lowest 4. D---A: Cost = 6 D---A: Cost = 6 D---B: Cost = 5 D---C: Cost = 4 D---E: Cost = 2 *lowest F---C: Cost = 6 D---C: Cost = 4 H---K: Cost = 7 F---C: Cost = 6 I---K: Cost = 8 F---J: Cost = 5 J---K: Cost = 4 G---E: Cost = 2 9. A---C: Cost = 3 *lowest G---H: Cost = 2 D---C: Cost = 4 I---H: Cost = 2 F---C: Cost = 6 I---K: Cost = 8 H---K: Cost = 7 I---J: Cost = 3 I---K: Cost = 8 5. D---A: Cost = 6 J---K: Cost = 4 D---B: Cost = 5 10. H---K: Cost = 7 D---C: Cost = 4 I---K: Cost = 8 E---B: Cost = 3 J---K: Cost = 4 *lowest E---H: Cost = 4 F---C: Cost = 6 F---J: Cost = 5 G---H: Cost = 2 *lowest Total = $26 million I---H: Cost = 2 I---K: Cost = 8 I---J: Cost = 3 7.17 a) The company wants a path between each pair of nodes (groves) that minimizes cost (length of road). b) 7---8 : Distance = 0.5 7---6 : Distance = 0.6 6---5 : Distance = 0.9 5---1 : Distance = 0.7 5---4 : Distance = 0.7 8---3 : Distance = 1.0 3---2 : Distance = 0.9 Total = 5.3 miles 7.18 a) The bank wants a path between each pair of nodes (offices) that minimizes cost (distance). b) B1---B5 : Distance = 50 B5---B3 : Distance = 80 B1---B2 : Distance = 100 B2---M : Distance = 70 B2---B4 : Distance = 120 Total = 420 miles Cases 7.1 a) The network showing the different routes troops and supplies may follow to reach the Russian Federation appears below. b) The President is only concerned about how to most quickly move troops and supplies from the United States to the three strategic Russian cities. Obviously, the best way to achieve this goal is to find the fastest connection between the US and the three cities. We therefore need to find the shortest path between the US cities and each of the three Russian cities. The President only cares about the time it takes to get the troops and supplies to Russia. It does not matter how great a distance the troops and supplies cover. Therefore we define the arc length between two nodes in the network to be the time it takes to travel between the respective cities. For example, the distance between Boston and London equals 6,200 km. The mode of transportation between the cities is a Starlifter traveling at a speed of 400 miles per hour * 1.609 km per mile = 643.6 km per hour. The time is takes to bring troops and supplies from Boston to London equals 6,200 km / 643.6 km per hour = 9.6333 hours. Using this approach we can compute the time of travel along all arcs in the network. By simple inspection and common sense it is apparent that the fastest transportation involves using only airplanes. We therefore can restrict ourselves to only those arcs in the network where the mode of transportation is air travel. We can omit the three port cities and all arcs entering and leaving these nodes. The following six spreadsheets find the shortest path between each US city (Boston and Jacksonville) and each Russian city (St. Petersburg, Moscow, and Rostov). Boston to St. Petersburg: Boston to Moscow: Boston to Rostov: Jacksonville to St. Petersburg: Jacksonville to Moscow: Jacksonville to Rostov: The spreadsheets contain the following formulas: Comparing all six solutions we see that the shortest path from the US to Saint Petersburg is Boston London Saint Petersburg with a total travel time of 12.71 hours. The shortest path from the US to Moscow is Boston London Moscow with a total travel time of 13.21 hours. The shortest path from the US to Rostov is Boston Berlin Rostov with a total travel time of 13.95 hours. The following network diagram highlights these shortest paths. c) The President must satisfy each Russian city’s military requirements at minimum cost. Therefore, this problem can be solved as a minimum-cost network flow problem. The two nodes representing US cities are supply nodes with a supply of 500 each (we measure all weights in 1000 tons). The three nodes representing Saint Petersburg, Moscow, and Rostov are demand nodes with demands of –320, -440, and –240, respectively. All nodes representing European airfields and ports are transshipment nodes. We measure the flow along the arcs in 1000 tons. For some arcs, capacity constraints are given. All arcs from the European ports into Saint Petersburg have zero capacity. All truck routes from the European ports into Rostov have a transportation limit of 2,500*16 = 40,000 tons. Since we measure the arc flows in 1000 tons, the corresponding arc capacities equal 40. An analogous computation yields arc capacities of 30 for both the arcs connecting the nodes London and Berlin to Rostov. For all other nodes we determine natural arc capacities based on the supplies and demands at the nodes. We define the unit costs along the arcs in the network in $1000 per 1000 tons (or, equivalently, $/ton). For example, the cost of transporting 1 ton of material from Boston to Hamburg equals $30,000 / 240 = $125, so the costs of transporting 1000 tons from Boston to Hamburg equals $125,000. The objective is to satisfy all demands in the network at minimum cost. The following spreadsheet shows the entire linear programming model. The total cost of the operation equals $412.867 million. The entire supply for Saint Petersburg is supplied from Jacksonville via London. The entire supply for Moscow is supplied from Boston via Hamburg. Of the 240 (= 240,000 tons) demanded by Rostov, 60 are shipped from Boston via Istanbul, 150 are shipped from Jacksonville via Istanbul, and 30 are shipped from Jacksonville via London. The paths used to ship supplies to Saint Petersburg, Moscow, and Rostov are highlighted on the following network diagram. d) Now the President wants to maximize the amount of cargo transported from the US to the Russian cities. In other words, the President wants to maximize the flow from the two US cities to the three Russian cities. All the nodes representing the European ports and airfields are once again transshipment nodes. The flow along an arc is again measured in thousands of tons. The new restrictions can be transformed into arc capacities using the same approach that was used in part (c). The objective is now to maximize the combined flow into the three Russian cities. The linear programming spreadsheet model describing the maximum flow problem appears as follows. The spreadsheet shows all the amounts that are shipped between the various cities. The total supply for Saint Petersburg, Moscow, and Rostov equals 225,000 tons, 104,800 tons, and 192,400 tons, respectively. The following network diagram highlights the paths used to ship supplies between the US and the Russian Federation. e) The creation of the new communications network is a minimum spanning tree problem. As usual, a greedy algorithm solves this type of problem. Arcs are added to the network in the following order (one of several optimal solutions): Rostov - Orenburg 120 Ufa - Orenburg 75 Saratov - Orenburg 95 Saratov - Samara 100 Samara - Kazan 95 Ufa – Yekaterinburg 125 Perm – Yekaterinburg 85 The minimum cost of reestablishing the communication lines is $695,000. 7.2 a) There are three supply nodes – the Yen node, the Rupiah node, and the Ringgit node. There is one demand node – the US$ node. Below, we draw the network originating from only the Yen supply node to illustrate the overall design of the network. In this network, we exclude both the Rupiah and Ringgit nodes for simplicity. b) Since all transaction limits are given in the equivalent of $1000 we define the flow variables as the amount in thousands of dollars that Jake converts from one currency into another one. His total holdings in Yen, Rupiah, and Ringgit are equivalent to $9.6 million, $1.68 million, and $5.6 million, respectively (as calculated in cells I16:K18 in the spreadsheet). So, the supplies at the supply nodes Yen, Rupiah, and Ringgit are -$9.6 million, -$1.68 million, and -$5.6 million, respectively. The demand at the only demand node US$ equals $16.88 million (the sum of the outflows from the source nodes). The transaction limits are capacity constraints for all arcs leaving from the nodes Yen, Rupiah, and Ringgit. The unit cost for every arc is given by the transaction cost for the currency conversion. Jake should convert the equivalent of $2 million from Yen to each US$, Can$, Euro, and Pound. He should convert $1.6 million from Yen to Peso. Moreover, he should convert the equivalent of $200,000 from Rupiah to each US$, Can$, and Peso, $1 million from Rupiah to Euro, and $80,000 from Rupiah to Pound. Furthermore, Jake should convert the equivalent of $1.1 million from Ringgit to US$, $2.5 million from Ringgit to Euro, and $1 million from Ringgit to each Pound and Peso. Finally, he should convert all the money he converted into Can$, Euro, Pound, and Peso directly into US$. Specifically, he needs to convert into US$ the equivalent of $2.2 million, $5.5 million, $3.08 million, and $2.8 million Can$, Euro, Pound, and Peso, respectively. Assuming Jake pays for the total transaction costs of $83,380 directly from his American bank accounts he will have $16,880,000 dollars to invest in the US. c) We eliminate all capacity restrictions on the arcs. Jake should convert the entire holdings in Japan from Yen into Pounds and then into US$, the entire holdings in Indonesia from Rupiah into Can$ and then into US$, and the entire holdings in Malaysia from Ringgit into Euro and then into US$. Without the capacity limits the transaction costs are reduced to $67,480. d) We multiply all unit cost for Rupiah by 6. The optimal routing for the money doesn't change, but the total transaction costs are now increased to $92,680. e) In the described crisis situation the currency exchange rates might change every minute. Jake should carefully check the exchange rates again when he performs the transactions. The European economies might be more insulated from the Asian financial collapse than the US economy. To impress his boss Jake might want to explore other investment opportunities in safer European economies that provide higher rates of return than US bonds.