Words: 3600
Chapter 6 Network Optimization Problems Review Questions 6. 1-1A 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. 6. 1-2The maximum amount of flow allowed through an arc is referred to as the capacity of that arc. 6. 1-3The objective is to minimize the total cost of sending the available supply through the network to satisfy the given demand. 6. 1-4The 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. 6. 1-5As 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. 6. 1-6Network simplex method. 6. 1-7Applications 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. . 1-8Transportation problems, assignment problems, transshipment problems, maximum flow problems, and shortest path problems are special types of minimum cost flow problems. 6. 2-1One of the company’s most important distribution centers (Los Angeles) urgently needs an increased flow of shipments from the company. 6. 2-2Auto replacement parts are flowing through the network from the company’s main factory in Europe to its distribution center in LA. 6. 2-3The objective is to maximize the flow of replacement parts from the factory to the LA distribution center. 6. -1Rather 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. 6. 3-2The 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. 6. 3-3The amount is measured by either the amount leaving the source or the amount entering the sink. 6. 3-41. Whereas supply nodes have fixed supplies and demand nodes have fixed demands, the source and sink do not. . 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. 6. 3-5Applications 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. 6. 4-1The origin is the fire station and the destination is the farm community. . 4-2Flow can go in either direction between the nodes connected by links as opposed to only one direction with an arc. 6. 4-3The 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. 6. 4-4The length of a link can measure distance, cost, or time. 6. 4-5Sarah wants to minimize her total cost of purchasing, operating, and maintaining the cars over her four years of college. 6. 4-6When “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. 6. -7Quick’s management must consider trade-offs between time and cost in making its final decision. Problems 6. 1In this study, flight delay and cancellation problems faced by United Airlines (UA) are modeled as minimum-cost-flow network models. The overall objective is to minimize a weighted sum of various measures related to delay. These include the total number of delay minutes for every passenger, the number of passengers affected by delays and the number of aircraft swaps. Nodes represent “arriving and departing aircraft, spare aircraft, and recovered aircraft” on a two-dimensional network, with time and airport being the two dimensions.
Arcs represent “scheduled flights, connections, and aircraft substitutions” [p. 56]. Costs include the revenue loss, the costs from swapping aircraft and from delaying aircraft. The delay problem is solved for each airport separately as a minimum-cost-flow network problem. The flow on each arc can be at most one. The solution is a set of arcs starting at a supply node and ending at a demand node, which determines flight delays due to shortage in aircraft. The cancellation model is a minimum-cost-flow network problem on the entire network. Again, the flow on each arc cannot exceed one.
The solution determines which flight is canceled and what flight its aircraft is assigned to. This study has saved UA over half a billion dollars in delay costs alone in less than a year. Many potential delays were prevented and hence the number of flight delays was reduced by 50%. Customer inconveniences due to delays and cancellations were reduced. Additionally, developing an efficient way of addressing these problems helped UA respond to changes in the conditions quickly. 6. 2a) [pic] b) [pic] 6. 3a) [pic] b) [pic] c) [pic] 6. 4a) [pic] b) [pic] c) [pic] 6. 5a) [pic] b) [pic] c)The total shipping cost is $2,187,000. . 6a) [pic] b) [pic] c) [pic] d) [pic] e) [pic] f)$1,618,000 + $583,000 = $2,201,000 which is higher than the total in Problem 6. 5 ($2,187,000). 6. 7 [pic] 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. 6. 8Both Gassco and StatoilHydro use a management science tool called GassOpt to optimize the configuration of the offshore pipeline network on the Norwegian Continental Shelf and the routing of the natural gas through the network.
The routing done by GassOpt is based on a model that is a generalization of the model for the maximum flow problem. Like the maximum flow problem, the objective is to maximize the flow of natural gas through the network. However, rather than a single source and a single sink, this model has multiple sources (separate natural gas fields) and multiple sinks (separate markets). In addition, the model has a number of extra constraints mentioned in the application vignette. The use of GassOpt has had many important benefits. By optimizing the use of production possibilities, it has increased fulfillment of contractual obligations.
It has avoided decisions that would have reduced oil production and created new bottlenecks and system dependencies. It has led to better decisions regarding the booking of transport capacity. It has prevented poor investment decisions. It has provided new insights that improved market analysis. It has improved understanding of system effects in the transport network. It also has increased awareness and appreciation of management science models throughout the organization. In monetary terms, the accumulated savings from all these benefits are estimated to be $2 billion over the period 1995 to 2008. 6. 9 [pic] 6. 0a) [pic] b) [pic] 6. 11a) [pic] b) [pic] c) [pic] d) [pic] 6. 12Prior to this study, Canadian Pacific Railway (CPR) used to run trains only after a sufficient level of freight was attained. This policy resulted in unreliable delivery times, so poor customer service. In order to improve customer service and utilization of available resources, CPR designed the railway operating plan called Integrated Operating Plan (IOP). “The problem of designing a railway operating plan is to satisfy a set of customer requirements expressed in terms of origin-destination traffic movements, using a blocking plan and a train plan.
Thus, the primary variables are the blocks and trains. The constraints are the capacities of the lines and yards, the customer-service requirements, and the availability of various assets, such as crews and locomotives. The objective function in an abstract sense is to maximize profits” [p. 8]. Developing the blocking plan, i. e. , determining the group of railcars to move together at some point during their trips, involves solving a series of shortest-path problems over a directed graph. The train plan is based on the blocking plan. It includes departure and arrival times for the trains, blocks they pick up and crew schedules.
This problem is solved for each train using heuristics. Following this, simulation models and locomotive cycle plans are developed. This study enabled CPR to save $170 million in half a year. “Total documented cost savings through the end of 2002 have exceeded half a billion dollars” [p. 12]. More savings are expected in following years. The improvements in CPR’s profitability and operations can be attributed to the decrease in transit and dwelling times, lowered fuel consumption, reduction of the workforce and of the number of railcars, and balanced workloads.
CPR can now schedule the trains and the crew more efficiently and provide a more reliable customer service. By allowing variability in the parameters of its plans, CPR gained flexibility and agility. It can now respond to disruptions more effectively by shifting resources quickly. These improvements earned CPR many awards and more importantly a significant competitive advantage. 6. 13 [pic] Shortest path: Fire Station – C – E – F – Farming Community 6. 14a) [pic] b) [pic] c)Shortest route: Origin – A – B – E – D – Destination d)Yes e)Yes 6. 15a) [pic] b) [pic] 6. 16a)Times play the role of distances. ) [pic] Cases 6. 1a)The network showing the different routes troops and supplies may follow to reach the Russian Federation appears below. [pic] 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: [pic] Boston to Moscow: [pic] Boston to Rostov: [pic] Jacksonville to St. Petersburg: [pic]
Jacksonville to Moscow: [pic] Jacksonville to Rostov: [pic] The spreadsheets contain the following formulas: [pic][pic] [pic][pic] [pic] 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. [pic] )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. [pic] [pic][pic] 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, 50 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. [pic] 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. [pic] [pic] 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. pic] 6. 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 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. [pic] 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. 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. [pic] [pic][pic] [pic] [pic]
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. [pic] 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. [pic] 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. 6. 3a)Each node represents a potential airplane location and point in time (e. g. , Seattle at 8:00am, Seattle at 8:30am, Portland at 8:00am, etc. ). The arcs represent potential paths for airplanes. An airplane in a city at a given time can stay in that city (i. e. , sit on the ground), so there is an arc from each city-time node to the node representing the next point in time at that city (e. g. between Seattle at 8:00am and Seattle at 8:30am). Each potential flight will also be represented by an arc (e. g. , a plane in Seattle at 8:00am can do flight#1257 to San Francisco, in which case, it will arrive at the San Francisco node for 10:00am. Revenue is generated for each of the flights (represented by a positive number on the arc). The fixed costs are captured by a -$30 thousand cost on all of the arcs at the end of the day (if a plane starts through the network, it must end up somewhere at 8:00pm, in which case it will end up on one of the overnight arcs and incur the fixed cost).
If the plane remains on the ground, the cost is $30 thousand. If the plane flies overnight to another city, the cost is $35 thousand. [pic] The spreadsheet solution for this problem is shown below. 16 flights are operated generating a net profit of $307 thousand per day. [pic] b)A Data Table was generated, to show the NetProfit (D38) as the number in PlanesOwned (F33) is varied between 4 and 7. The results are shown below. The fifth plane increases the net profit from $307 thousand per day to $351 thousand per day. The sixth plane adds another $4 thousand to net profit.
The seventh plane does not have any effect on net profit because it is not used in the network. All flights are operated. If this seventh plane were actually leased, the net profit would be $30 thousand lower, or $325 thousand. [pic] c)The network from part a is modified so that all flight arcs end at the node that is 30 minutes later than the true arrival time of the flight. This does not allow the plane to take off again until at least 30 minutes after the true arrival time. The revised network with a few of the flight arcs is shown below. [pic] The spreadsheet solution for the revised network is shown below.
The new solution operates 15 flights and generates a net revenue of $287 thousand per day. [pic] d)The spreadsheet from part c was modified to add $5 thousand in revenue for each overnight flight to a different city (rather than subtracting a $5 cost). The new solution is shown below. The number of daytime flights remains at 15, but the number of overtime flights increases from 0 to 4. The new net profit is $307 thousand per day. [pic] 6. 4a)This is a maximum flow problem. The goal is to maximize the flow of data from node A to node G, where nodes B through F are transshipment nodes.
The solved spreadsheet is shown below. At most 27 GB/s can be transmitted from node A to node G. [pic] b)For each arc, a new set of changing cells are added to determine how much capacity to add to that arc. The NewCapacity (F5:F16) is then equal to the ExistingCapacity (H5:H16) plus the AddedCapacity (I5:I16). The AddedCapacity (I5:I16) is constrained to be no more than the MaximumAdditional (K5:K16). The goal is to achieve a total flow of data from A to G of at least 35 GB/s at the lowest possible total cost. By adding capacity as shown below, the needed capacity can be achieved for a cost of $33. 8 million. [pic]