Page 379 -

MAXIMAL FLOW PROBLEM 359

Figure 8.17 Flow Over Arc from Node 7 to Node 1 to Represent Total Flow Through the
Glasgow System

3
2 5
8
5 3
2 2 1 1
7
7
6 7
1 3 6
3
5
5

4

The direction of flow for each arc is indicated, and the arc capacity is shown next
to each arc. Note that most of the streets are one-way. However, a two-way street
can be found between nodes 2 and 3 and between nodes 5 and 6. In both cases, the
capacity is the same in each direction.
We will show how to develop a capacitated transshipment model (see Chapter 7)
for the maximal flow problem. First, we will add an arc from node 7 back to node 1 to
represent the total flow through the highway system. Figure 8.17 shows the modified
network. The newly added arc shows no capacity; indeed, we will want to maximize
the flow over that arc. Maximizing the flow over the arc from node 7 to node 1 is
equivalent to maximizing the number of cars that can get through the east–west road
system passing through Glasgow.
As we did in Chapter 7 we define our decision variables as follows:

x ij ¼ amount of traffic flow from node i to node j

The objective function that maximizes the flow over the road system is:
Max x
71
As with all transshipment problems, each arc generates a variable and each
node generates a constraint. For each node, a conservation of flow constraint
represents the requirement that the flow out must equal the flow in. Or, stated
another way, the flow out minus the flow in must equal zero. For node 1, the
flow out is x 12 + x 13 + x 14 ,and theflowinis x 71 . Therefore, the constraint for
node 1 is:
x 12 þ x 13 þ x 14 x 71 ¼ 0
The conservation of flow constraints for the other six nodes are developed in a
similar fashion.

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.