Page 380 -
P. 380
360 CHAPTER 8 NETWORK MODELS
x 23 þ x 25 x 12 x 32 ¼ 0 Node 2
x 32 þ x 34 þ x 35 þ x 36 x 13 x 23 ¼ 0 Node 3
x 46 x 14 x 34 ¼ 0 Node 4
x 56 þ x 57 x 25 x 35 x 65 ¼ 0 Node 5
x 65 þ x 67 x 36 x 46 x 56 ¼ 0 Node 6
x 71 x 57 x 67 ¼ 0 Node 7
Additional constraints are needed to enforce the capacities on the arcs. These 14
simple upper-bound constraints are given.
x 12 5 x 13 6 x 14 5
x 23 2 x 25 3
x 32 2 x 34 3 x 35 3 x 36 7
x 46 5
x 56 1 x 57 8
x 65 1 x 67 7
Note that the only arc without a capacity is the one we added out of node 7.
Part of the Excel solution to this 15-variable, 21-constraint linear programming
problem is shown in Figure 8.18. We note that the value of the optimal solution is 14.
This result implies that the maximal flow over the road system is 14000 vehicles.
Figure 8.19 shows how the vehicle flow is routed through the original road network.
We note, for instance, that 5000 vehicles per hour are routed between nodes 1 and 2,
Try Problem 11 for 2000 vehicles per hour are routed between nodes 2 and 3, and so on.
practise in solving a The results of the maximal flow analysis indicate that the planned road system
maximal flow problem.
will not handle the peak flow of 15 000 vehicles per hour. The transportation
planners will have to expand the network, increase current arc flow capacities,
or be prepared for serious traffic problems. If the network is extended or modified,
another maximal flow analysis will determine the extent of any improved flow.
Figure 8.18 The Excel Solution to the Glasgow Road System Maximal Flow Problem
EXCEL file OPTIMAL SOLUTION
ROAD SYSTEM
Objective Function Value = 14.000
Variable Value
-------------- ---------------
X12 5.000
X13 6.000
X14 3.000
X23 2.000
X25 3.000
X34 0.000
X35 3.000
X36 5.000
X32 0.000
X46 3.000
X56 0.000
X57 7.000
X65 1.000
X67 7.000
X71 14.000
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.
