CHAPTER 7NETWORK OPTIMIZATION PROBLEMS Review Questions7.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 negativenumber. 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 thatarc.7.1-3 The objective is to minimize the total cost of sending the available supply through thenetwork to satisfy the given demand.7.1-4 The feasible solutions property is necessary. It states that a minimum cost flow problemwill have a feasible solution if and only if the sum of the supplies from its supply nodesequals 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 flowproblem with feasible solutions is guaranteed to have an optimal solution with integervalues 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 atplants, and cash flow management.7.1-8 Transportation problems, assignment problems, transshipment problems, maximum flowproblems, 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 anincreased flow of shipments from the company.7.2-2 Auto replacement parts are flowing through the network from the company’s main factoryin 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 LAdistribution center.7.3-1 Rather than minimizing the cost of the flow, the objective is to find a flow plan thatmaximizes 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 thenode at which all flow through the network terminates. At the source, all arcs point awayfrom 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 thesink.7.3-4 1. Whereas supply nodes have fixed supplies and demand nodes have fixed demands, thesource and sink do not.2. Whereas the number of supply nodes and the number of demand nodes in a minimumcost flow problem may be more than one, there can be only one source and only onesink in a standard maximum flow problem.7.3-5 Applications of maximum flow problems include maximizing the flow through adistribution 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 ofaqueducts, 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 onlyone direction with an arc.7.4-3 The origin now is the one supply node, with a supply of one. The destination now is theone 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 carsover her four years of college.7.4-6 When “real travel” through a network can end at more that one node, a dummy destinationneeds 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 finaldecision.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 nodewithout 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 minimumpossible 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.17.5-8 Applications of minimum spanning tree problems include design of telecommunicationnetworks, 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.Problems7.1a)b)c)1[40] 6 S17 4[-30] D1 [-40] D2 [60] 5 8S2 6[-30] D37.2a)supply nodestransshipment nodesdemand nodesb)[200] P1560 [150]425 [125][0] W1505[150]490 [100]470 [100][-150]RO1[-200]RO2P2 [300]c)510 [175]600 [200][0] W2390 [125]410[150] 440[75]RO3[-150]7.3a)supply nodestransshipment nodesdemand nodesV1W1F1V2V3W2 F21P1W1RO1RO2P2W2RO3[-50] SE3000[20][0]BN5700[40][0]HA[50]BE 4000 6300[40][30] [0][0]NY2000[60]2400[20]3400[10] 4200[80][0]5900[60]5400[40]6800[50]RO[0]BO[0]2500[70]2900[50]b)c)7.4a)LA 3100 NO 6100 LI 3200 ST[-130] [70] [30] [40] [130]1[70]11b)c) The total shipping cost is $2,187,000.7.5a)[0][0] 5900RONY[60] 5400[0] 2900 [50]4200 [80][0] [40] 6800 [50]BO[0] 2500LA 3100 NO 6100 LI 3200 ST [-130][70][30] [40][130]b)c)SEBNHABERONYNY(80) [80] (50) [60](30)[40] ROBO (40)(50) [50] (70)[70]11d)e)f) $1,618,000 + $583,000 = $2,201,000 which is higher than the total in Problem 7.5 ($2,187,000). 7.6LA(70) NO[50](30)LI (30) ST[70][30] [40]There are only two arcs into LA, with a combined capacity of 150 (80 + 70). Because ofthis 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[-50] SE3000 [20] [0] BN 5700 [40][0] HA[50] BE4000 6300[40][0] NY2000 [60] 2400 [20][30] [0]5900RO [60]17.8 a) SourcesTransshipment Nodes Sinkb)7.9 a)AKR1[75]A [60]R2[65] [40][50][60] [45]D [120] [70]B[55]E[190]T [45][80] [70][70]R3CF[130][90]SE PT KC SL ATCHTXNOMES S F F CAb)Oil Fields Refineries Distribution CentersTXNOPTCACHATAKSEKCME c)SLSFTX[11][7] NO[5][9] PT[8] [2][5] CA [4] [7] [8] [7] [4] [6][8] CH [7][5][9] [4] ATAK [3][6][6][12] SE KC[8][9][4][8] [7] [12] [11]MESL [9]SF[15][7]d)3Shortest path: Fire Station – C – E – F – Farming Community 7.11 a)A70D40 60O60 5010 B 20 C5540 10 T50E801c)Shortest route: Origin – A – B – D – Destinationd)Yese)Yes7.12a)31,00018,000 21,00001238,000 10,000 12,000b)17.13a) Times play the role of distances.B 2 2 G5ACE 1 31 1b)7.14D F1. C---D: Cost = 14.E---G: Cost = 5E---F: Cost = 1 *choose arbitrarilyD---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 = 5F---G: Cost = 7C---B: Cost = 2 *lowestF---C: Cost = 3 *lowest5.E---G: Cost = 5 F---D: Cost = 4 D---A: Cost = 43. E---G: Cost = 5 B---A: Cost = 2 *lowestE---B: Cost = 7 F---G: Cost = 7 F---G: Cost = 7 C---A: Cost = 5F---D: Cost = 46.E---G: Cost = 5 *lowestC---D: Cost = 1 *lowestF---G: Cost = 7C---A: Cost = 5C---B: Cost = 2Total = $14 million7.151. B---C: Cost = 1 *lowest 4. B---E: Cost = 72. B---A: Cost = 4 C---F: Cost = 4 *lowestB---E: Cost = 7 C---E: Cost = 5C---A: Cost = 6 D---F: Cost = 5C---D: Cost = 2 *lowest 5. B---E: Cost = 7C---F: Cost = 4 C---E: Cost = 5C---E: Cost = 5 F---E: Cost = 1 *lowest3. B---A: Cost = 4 *lowest F---G: Cost = 8B---E: Cost = 7 6. E---G: Cost = 6 *lowestC---A: Cost = 6 F---G: Cost = 8C---F: Cost = 4C---E: Cost = 5D---A: Cost = 5 Total = $18,000D---F: Cost = 57.16B 34 2E HA D 2 G I K3C F 12J34B41E6A C41G2 FD1. F---G: Cost = 1 *lowest 6. D---A: Cost = 62. F---C: Cost = 6 D---B: Cost = 5F---D: Cost = 5 D---C: Cost = 4F---I: Cost = 2 *lowest E---B: Cost = 3 *lowestF---J: Cost = 5 F---C: Cost = 6G---D: Cost = 2 F---J: Cost = 5G---E: Cost = 2 H---K: Cost = 7G---H: Cost = 2 I---K: Cost = 8G---I: Cost = 5 I---J: Cost = 33. F---C: Cost = 6 7. B---A: Cost = 4F---D: Cost = 5 D---A: Cost = 6F---J: Cost = 5 D---C: Cost = 4G---D: Cost = 2 *lowest F---C: Cost = 6G---E: Cost = 2 F---J: Cost = 5G---H: Cost = 2 H---K: Cost = 7I---H: Cost = 2 I---K: Cost = 8I---K: Cost = 8 I---J: Cost = 3 *lowestI---J: Cost = 3 8. B---A: Cost = 4 *lowest4. D---A: Cost = 6 D---A: Cost = 6D---B: Cost = 5 D---C: Cost = 4D---E: Cost = 2 *lowest F---C: Cost = 6D---C: Cost = 4 H---K: Cost = 7F---C: Cost = 6 I---K: Cost = 8F---J: Cost = 5 J---K: Cost = 4G---E: Cost = 2 9. A---C: Cost = 3 *lowestG---H: Cost = 2 D---C: Cost = 4I---H: Cost = 2 F---C: Cost = 6I---K: Cost = 8 H---K: Cost = 7I---J: Cost = 3 I---K: Cost = 85. D---A: Cost = 6 J---K: Cost = 4D---B: Cost = 5 10. H---K: Cost = 7D---C: Cost = 4 I---K: Cost = 8E---B: Cost = 3 J---K: Cost = 4 *lowestE---H: Cost = 4F---C: Cost = 6F---J: Cost = 5G---H: Cost = 2 *lowest Total = $26 millionI---H: Cost = 2I---K: Cost = 8I---J: Cost = 37.17a) The company wants a path between each pair of nodes (groves) that minimizes cost(length of road).b)7---8 : Distance = 0.57---6 : Distance = 0.66---5 : Distance = 0.95---1 : Distance = 0.75---4 : Distance = 0.78---3 : Distance = 1.03---2 : Distance = 0.9Total = 5.3 miles7.18a) The bank wants a path between each pair of nodes (offices) that minimizes cost(distance).b) B1---B5 : Distance = 50B5---B3 : Distance = 80B1---B2 : Distance = 100B2---M : Distance = 70B2---B4 : Distance = 120Total = 420 milesHamburgBostonRotterdamSt. PetersburgNapoliMoscowA IRFIELD SLondonJacksonvilleBerlin RostovIstanbulCases7.1a) The network showing the different routes troops and supplies may follow to reach the Russian Federation appears below.PORTSb)The President is only concerned about how to most quickly move troops and suppliesfrom 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).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.-1c)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 (wemeasure 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, capacityconstraints 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.HamburgBoston Rotterdam St.Petersburg+500-320Napoli Moscow A IRF IELDSLondon -440Jacksonville Berlin Rostov+500-240Istanbul The total cost of the operation equals $412.867 million. The entire supply for SaintPetersburg 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 viaIstanbul, and 30 are shipped from Jacksonville via London. The paths used to shipsupplies to Saint Petersburg, Moscow, and Rostov are highlighted on the followingnetwork diagram.PORTSd)Now the President wants to maximize the amount of cargo transported from the US tothe 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 againmeasured in thousands of tons. The new restrictions can be transformed into arccapacities 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.PORTSHamburgBoston Rotterdam St.Petersburg+282.2 -225NapoliMoscowAIRFIELDS-104.8LondonJacksonvilleBerlin Rostov +240 -192.4Istanbule)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 120Ufa - Orenburg 75Saratov - Orenburg 95Saratov - Samara 100Samara - Kazan 95Ufa – Yekaterinburg 125Perm – Yekaterinburg 857.2a) 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 originatingfrom only the Yen supply node to illustrate the overall design of the network. In thisnetwork, 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 flowvariables as the amount in thousands of dollars that Jake converts from one currencyinto another one. His total holdings in Yen, Rupiah, and Ringgit are equivalent to $9.6million, $1.68 million, and $5.6 million, respectively (as calculated in cells I16:K18 inthe 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 onlydemand node US$ equals $16.88 million (the sum of the outflows from the sourcenodes). The transaction limits are capacity constraints for all arcs leaving from thenodes Yen, Rupiah, and Ringgit. The unit cost for every arc is given by the transactioncost 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 thetransactions.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.。
