Questions and Answers > Colorado Technical University MATH 451-1404B- Maximal-Flow Model.

Document Content and Description Below

Colorado Technical University MATH 451-1404B- Maximal-Flow Model. Maximal-Flow Model Introduction Maximal flow model can be used to determine the maximum amount that can flow from a node called... origin to another one called destination with the values of arcs provided in a network modeling. Unlike the transportation and assignment applications, in which they have numerous origin nodes and many destination nodes, the typical maximal flow has only one origin and one destination. You will consider an example of maximal flow and present the objective and flow balance equations. Learning Materials What is a maximal-flow model? Sometimes it becomes necessary to determine the maximum flow of goods from one node called the origin to another node called the destination in a network with the maximum capacity of each arc is provided. Example Consider a jetliner which transfers passengers among the cities of Rome, Frankfort, Amsterdam, and London. The jetliner uses Airbus 320, Airbus 330, and Airbus A380 in their freights. ·Airbus 320 can carry up to 220 passengers ·Airbus 330 can carry up to 330 passengers ·Airbus A380 can carry up to 525 passengers Chart for Example They use an Airbus A380 from Rome to Frankfort, 4 Airbus A320s from Frankfort to Rome, Rome to London, and roundtrip from Frankfort to London as shown in the following chart: ·Model 3: Rome to Frankfort ·Model 2: Amsterdam to Rome ·Model 1 is used in the following o Frankfort to Rome o Rome to London o Roundtrip from Frankfort to London Objective The objective of this problem is to maximize the number of passengers from London to Rome. The airliner uses a total of 6 Airbus jets. Assume that the number of passengers are not known at the time they schedule these flights. Therefore, they may assign a large wide body jet to a route that may not have many passengers for a given flight day. It is a waste of money and energy to fly 100 passengers on a scheduled A380 jet while if it can be replaced by an A320. Setting Up to Solve the Problem All nodes in maximal flow model are transshipment nodes. It means you neither create any passengers nor consume any passengers at any nodes. All the arriving passengers are on transfer flight to get into a city and then move on to another. Therefore, all the net flow balance equations should be equal to zero. To achieve the objective function, you assign a large number of passengers over the limit of any of the jets operated by the airliner. You can assign 600 passengers to be carried from London to Rome while not a single jet of any kind can carry them all at once. Figure 1 shows the Excel’s Solver program used to solve the maximal flow model containing all of the required excel functions. Figure 1: Excel’s Solver Program Used to Solve the Maximal Flow Model Figure 1b shows how to program the Solver Parameters window for Excel’s Solver program to achieve the results in Figure 1a. Figure 2 shows the same program containing the numerical values of the decision-making variables and the amount of resources consumed. Figure 2: Results of the Application Using Excel’s Solver Understanding the Results As you can see from the results from Figure 1 that it is beneficial to replace the A380 from Rome to Frankfort by an A320, and place the A380 from London to Rome to carry 440 passengers. The numbers shown in the cells B5–E8 are the actual number of passengers transferred between any two cities. A jetliner transfers passengers among the cities of Rome, Frankfort, Amsterdam, and London. The jetliner wants to maximize the number of passengers enroute from Frankfort to Rome. What is the objective function? Maximize XRF Minimize XRF Maximize XRF + XFR Maximize XFR What replace each bidirectional node in the network? A unidirectional path Two one-way paths with the same directions Another bidirectional node Two one-way paths with opposite directions, Unidirectional paths What determines the number of decision variables in a maximal flow model? Number of bidirectional nodes Number of bidirectional arcs Number of unidirectional arcs Number of unidirectional nodes Suppose that you have a source node 0, a destination node 9, and 8 intermediate trans-shipment nodes 1–8. The carrying capacities are as follows: Flows From To Limit If you wanted to increase the maximum flow, which of the following link limits would you increase? 2→8 0→2 3→7 7→9 Which of the following are nodes with the exception of the starting and the ending nodes? transshipment nodes destination nodes supply or destination nodes supply nodes To what value should the unidirectional dummy node be assigned? Very small number Same as the rest of the data within the arcs Infinity or an artificially large number No value should be assigned to this unidirectional dummy node How many starting nodes does a maximal flow model have? Two nodes Multiple nodes None One node A jetliner transfers passengers among the cities of Rome, Frankfort, Amsterdam, and London. The jetliner wants to maximize the number of passengers enroute from Frankfort to Rome. What is the actual number of passengers from Rome to London? 180 400 220 620 What modification is needed to solve a maximal flow model? creating a unidirectional dummy arc from the destination node to the origination node creating a unidirectional dummy arc from the origination node to the destination node creating a bidirectional dummy arc from the destination node to the origination node creating a bidirectional dummy arc from the origination node to the destination node A jetliner transfers passengers among the cities of Rome, Frankfort, Amsterdam, and London. The jetliner wants to maximize the number of passengers enroute from Frankfort to Rome. What is value of the objective function? 740 470 0 1,000 Suppose that you have 18 nodes, with node 1 as the source and node as 18 the destination, as well as the following link capacities: Suppose that the link from node 7 to node 13 is broken and cannot carry any traffic. By how much does the maximum flow decrease? 2 7 6 0 How many ending nodes does a maximal flow model have? None One node Multiple nodes Two nodes Suppose that you have 18 nodes, with node 1 as the source and node 18 as the destination, as well as the following link capacities: What is the maximum flow? 145.549 272.407 262.8 81.596 Suppose that you have 18 nodes, with node 1 as the source and node as 18 the destination, as well as the following link capacities: What is the flow from node 7 to node 13? 7 22 13 21 Which one of the following is correct regarding maximal flow model? The quantity of supply and demands is unknown. The quantity of supply is unknown, but the quantity of demand is known. The quantity of supply is known, but the quantity of demand is unknown. Both the quantity of supply and demand are known. Suppose that node 5 is wiped out. Thus, there can be no traffic to or from node 5. How much does the maximum flow decrease? 33 43 41 14 A jetliner transfers passengers among the cities of Rome, Frankfort, Amsterdam, and London. The jetliner wants to maximize the number of passengers enroute from Frankfort to Rome. What is the net flow for Frankfort? (XFR + XFA) - (XFR + XFA + XFL) = 0, (XFR + XFA) = (XFR + XFA + XFL) (XFR + XFA) - (XFR + XFA + XFL) < 0 (XFR + XFA) - (XFR + XFA + XFL) > 0 (XFR + XFA) + (XFR + XFA + XFL) = 0 Suppose that you have a source node 0, a destination node 9, and 8 intermediate transshipment nodes 1–8. The carrying capacities are as follows: If each limit is increased by 1, by how much will the maximum flow increase? 3 1 2 0 Suppose that you have 18 nodes, with node 1 as the source and node as 18 the destination, as well as the following link capacities: What is the maximum flow from node 1 to node 18? 191 133 159 61 Suppose that you have a source node 0, a destination node 9, and 8 intermediate transshipment nodes 1–8. The carrying capacities are as follows: What is the maximum flow from node 0 to node 9? 61 58 43 40 There has been some recent construction, and a new link from node 9 to node 14 has been added with a capacity of 15.34. Using this as a starting point, by how much will the new capacity increase if each capacity is increased by 1? 2 5 4 3 Suppose that you can add a link with a capacity of 17.23. Which of the following links will increase the maximum flow the most? 4, 7 4, 5 10, 7 16, 5 [Show More]

Last updated: 1 year ago

Preview 1 out of 6 pages