NETWORK MODELS (2/2)
Week 3
Maximum Flow Model (1/2)
The maximal flow problem is concerned with
determining the maximal volume of flow from one
node (called the source) to another node (called the
sink).
In the maximal flow problem, each arc has a
maximum arc flow capacity which limits the flow
through the arc.
It is possible that an arc, (i,j), may have a different
flow capacity from i to j than from j to i.
Maximum Flow Model (2/2)
Step 1: find any path from the source node to the sink node
that has positive flow capacities (in the direction of the flow)
for all arcs on the path. If no path is available, then the
optimal solution has been found.
Step 2: find the smallest arc capacity, pf, on the path selected
in step 1. Increase the flow through the network by sending
the amount, pf, over this path.
Step 3: For the path selected in step 1 reduce all arc flow
capacities in the direction of the flow by pf and increase all arc
flows in the opposite direction of the flow by pf. Go to step 1.
Example: Maximal Flow (1/13)
Find the maximal flow from node 1 to node 7 in the
following network:
2 3 3 5
2 2
0 4
3 3 0
4
4 0 4 3 0 7
1
5 1 0
3
0 3 1 5
3 6 0 6
Example: Maximal Flow (2/13)
Iteration 1
Step 1: find a path from the source node, 1, to the sink
node, 7, that has flow capacities greater than zero on all
arcs of the path. One such path is 1-2-5-7.
Step 2: The smallest arc flow capacity on the path 1-2-5-7
is the minimum of {4, 3, 2} = 2.
Step 3: reduce all arc flows in the direction of the flow by 2
on this path and increase all arc flows in the reverse
direction by 2:
(1-2) 4 - 2 = 2 (2-1) 0 + 2 = 2
(2-5) 3 - 2 = 1 (5-2) 3 + 2 = 5
(5-7) 2 - 2 = 0 (7-5) 0 + 2 = 2
Example: Maximal Flow (3/13)
Iteration 1 results
2 1 5 5
2 0
2 4
3 3 2
2
4 0 4 3 0 7
1
5 1
3 0
0 3 1 5
3 6 0 6
Example: Maximal Flow (4/13)
Iteration 2
Step 1: path 1-4-7 has flow capacity greater than zero on
all arcs.
Step 2: The minimum arc flow capacity on 1-4-7 is 3.
Step 3: reduce the arc flow capacities on the path in the
direction of the flow by 3, and increase these capacities in
the reverse direction by 3:
(1-4) 4 - 3 = 1 (4-1) 0 + 3 = 3
(4-7) 3 - 3 = 0 (7-4) 0 + 3 = 3
Example: Maximal Flow (5/13)
Iteration 2 results
2 1 5 5
2 0
2 4
3 3 2
2
1 3 4 0 3 7
1
5 1
3 0
0 3 1 5
3 6 0 6
Example: Maximal Flow (6/13)
Iteration 3
Step 1: path 1-3-4-6-7 has flow capacity greater than
zero on all arcs.
Step 2: The minimum arc capacity on 1-3-4-6-7 is 1.
Step 3: reduce the arc capacities on the path in the
direction of the flow by 1 and increase the arc capacities in
the reverse direction of the flow by 1:
(1-3) 3 - 1 = 2 (3-1) 0 + 1 = 1
(3-4) 3 - 1 = 2 (4-3) 5 + 1 = 6
(4-6) 1 - 1 = 0 (6-4) 1 + 1 = 2
(6-7) 5 - 1 = 4 (7-6) 0 + 1 = 1
Example: Maximal Flow (7/13)
Iteration 3 results
2 1 5 5
2 0
2 4
3 3 2
2
1 3 4 0 3 7
1
6 0
2 1
1 2 2 4
3 6 0 6
Example: Maximal Flow (8/13)
Iteration 4
Step 1: path 1-3-6-7 has flow capacity greater than zero
on all arcs.
Step 2: The minimum arc capacity on 1-3-6-7 is 2.
Step 3: reduce all arc flow capacities on the path in the
direction of the flow by 2 and increase the arc flow
capacities in the reverse direction by 2:
(1-3) 2 - 2 = 0 (3-1) 1 + 2 = 3
(3-6) 6 - 2 = 4 (6-3) 0 + 2 = 2
(6-7) 4 - 2 = 2 (7-6) 1 + 2 = 3
Example: Maximal Flow (9/13)
Iteration 4 results
2 1 5 5
2 0
2 4
3 3 2
2
1 3 4 0 3 7
1
6 0
0 3
3 2 2 2
3 4 2 6
Example: Maximal Flow (10/13)
Iteration 5
Step 1: using the shortest route algorithm, the shortest route
from node 1 to node 7 is 1-2-4-3-6-7.
Step 2: The smallest arc capacity on 1-2-4-3-6-7 is 2.
Step 3: reduce the arc flow capacities on the path in the
direction of the flow by 2 and increase these capacities in
the reverse direction of the flow by 2:
(1-2) 2 - 2 = 0 (2-1) 2 + 2 = 4
(2-4) 2 - 2 = 0 (4-2) 3 + 2 = 5
(4-3) 6 - 2 = 4 (3-4) 2 + 2 = 4
(3-6) 4 - 2 = 2 (6-3) 2 + 2 = 4
(6-7) 2 - 2 = 0 (7-6) 3 + 2 = 5
Example: Maximal Flow (11/13)
Note:
Arc 3-4 is a case where in iteration 3, flow of 1 unit was
directed from node 3 to node 4. In iteration 5 flow of 2
units was directed from node 4 to node 3.
By subtracting the assigned flow from the capacity of the
"sending" end of the arc and adding it to the "receiving"
end of the arc, the net effect of the oppositely directed flow
assignments is readily known.
Example: Maximal Flow (12/13)
Iteration 5 results
2 1 5 5
0 0
4 4
5 3 2
0
1
1 3 4 0 3 7
4 0
0 5
3 4 2 0
3 2 4 6
There are no arcs with positive flow into the sink node 7. Thus,
the maximal possible flow from node 1 to node 7 has been
found.
Example: Maximal Flow (13/13)
Solution summary
2
2 5
1 2
3
4 3
4 7
1
1
1
3 5
3 6
4
Some Notes
There is a degree of randomness to the maximal
flow algorithm.
Recall that step 1 states "find any path ...“, as long
as you follow the algorithm you will reach an
optimal solution, regardless of your path choice in
each iteration.
Two people solving the same problem might get
different solutions in regard to flow routings, but the
maximal flows will be the same.
Linier Programming Model for Maximal
Flow (1/2)
Linier Programming Model for Maximal
Flow (2/2)
Example LP Model
Build a LP model for maximum flow broblem in the
following network!
