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
...
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]
