Chapter Seven: Network Flow Models
PROBLEM SUMMARY
33.
Maximal flow
34.
Maximal flow
35.
Maximal flow
36.
Maximal flow
Shortest route
37.
Maximal flow
6.
Shortest route
38.
Maximal flow
7.
Shortest route
8.
Shortest route
9.
Shortest route
10.
Shortest route
11.
Shortest route
12.
Shortest route
13.
Shortest route
14.
Shortest route
15.
Shortest route
16.
Minimal spanning tree
17.
Minimal spanning tree
18.
Minimal spanning tree
19.
Minimal spanning tree
20.
Minimal spanning tree
21.
Minimal spanning tree
22.
Minimal spanning tree
23.
Minimal spanning tree
24.
Minimal spanning tree
25.
Minimal spanning tree
26.
Minimal spanning tree
27.
Maximal flow
28.
Maximal flow
29.
Maximal flow
30.
Maximal flow
31
Maximal flow
32.
Maximal flow
1.
Shortest route
2.
Shortest route
3.
Shortest route
4.
Shortest route
5.
PROBLEM SOLUTIONS
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
10.
Step
Permanent Set
Branch Added Distance
1
{1}
2
{1,3}
3
{1,2,3}
4
{1,2,3,4}
5
{1,2,3,4,7}
6
{1,2,3,4,5,7}
7
{1,2,3,4,5,6,7}
8
{1,2,3,4,5,6,7,8}
9
{1,2,3,4,5,6,7,8,9}
10
{1,2,3,4,5,6,7,8,9,10}
11 {1,2,3,4,5,6,7,8,9,10,12}
12 {1,2,3,4,5,6,7,8,9,10,11,12}
13
12
14
37
25
36
48
79
710
912
811
1013
9.
98
11.
1 4 7 8 = 42 miles
12.
1 4 7 10 12 16 17 = 14 days
13.
1 3 11 14 = 13 days
14.
1 3 5 12 16 20 22 = 114
73
89
96
154
164
167
177
208
239
263
283
323
15.
This is an example of the application of the shortest route method to solve the scheduled replacement problem.
The branch costs are determined using the formula,
cij = maintenance cost for year i, i + 1,, + cost of purchasing new car at the beginning of year i-selling price
of a used car at the beginning of year j.
c12 = 3 + 26 15 = 14
c13 = 3 + 4.5 + 26 12 = 21.5
c14 = 3 + 4.5 + 6 + 26 8 = 31.5
c15 = 3 + 4.5 + 6 + 8 + 26 4 = 43.5
c16 = 3 + 4.5 + 6 + 8 + 11 + 26 2 = 56.5
c17 = 3 + 4.5 + 6 + 8 + 11 + 14 + 26 + 28.5 0 = 101
c23 = 3 + 26.5 15 = 14.5
c24 = 3 + 4.5 + 26.5 12 = 22
c25 = 3 + 4.5 + 6 + 26.5 8 = 32
c26 = 3 + 4.5 + 6 + 8 + 26.5 4 = 44
c27 = 3 + 4.5 + 6 + 8 + 11 + 26.5 2 = 57
c34 = 3 + 27 15 = 15
c35 = 3 + 4.5 + 27 12 = 22.5
c36 = 3 + 4.5 + 6 + 27 8 = 32.5
c37 = 3 + 4.5 + 6 + 8 + 27 4 = 44.5
c45 = 3 + 27.5 15 = 15.5
c46 = 3 + 4.5 + 27.5 12 = 23
c47 = 3 + 4.5 + 6 + 27.5 8 = 33
c56 = 3 + 28 15 = 16
c57 = 3 + 4.5 + 28 12 = 23.5
c67 = 3 + 28.5 15 = 16.5
Solution:
1 - 4 - 7 = $64.5 = $64,500
A car should be sold at end of year 3 (beginning of year 4) and a new one purchased.
98.5
57
56.5
44
43.5
32
31.5
22
21.5
14
14.5
44.5
32.5
23
22.5
15
Begining of
Year 1
33
15.5
23.5
16
16.5
7
End of
Year 6
99
16.
18.
minimum distance = 70
17.
1 3,
1 4,
2 3,
4 8,
5 6,
6 7,
7 8,
7 9,
9 10,
4.1
4.8
3.6
5.5
2.1
2.8
2.7
2.7
4.6
32.9 = 32,900 feet
12
13
24
36
56
67
78
13
24
34
46
47
57
19.
13
23
34
46
56
58
67
20.
12
23
36
48
56
67
79
78
910
21.
14
24
36
46
57
67
78
100
22.
25.
7
92
3
1
63
76
107
67
86
Total sidewalk = 1,086 ft.
14
23
34
35
56
57
58
23.
12
24
25
34
47
56
68
89
26.
24.
101
1 2 = 48
1 4 = 52
4 7 = 35
3 5 = 39
5 6 = 29
5 8 = 56
5 9 = 48
6 7 = 80
9 10 = 71
9 12 = 71
10 11 = 38
11 14 = 57
12 13 = 105
Total = 729
12
82
73
95
Length of ductwork = 790 ft
61
84
9
13
10
112
88
11
14
27.
102
28.
103
29.
104
30.
105
106
31.
107
Maximal flow network:
32.
108
33.
34.
109
solution
35.
x10,1 x12 x13 x14 = 0
x12 x25 x26 = 0
x13 x35 x36 = 0
x14 x45 x46 = 0
x25 + x 35 + x 45 x57 x58 x59 = 0
x26 + x 36 x68 x69 = 0
x57 x 7,10 = 0
x58 + x68 x8,10 = 0
x59 + x69 x9,10 = 0
x7,10 + x8,10 + x9,10 x10,1 = 0
x58 4
x59 1
x25 9
x68 6
x26 6
x69 8
x35 7
x7,10 8
x36 5
x8,10 7
x45 10
x9,10 7
x14 = 8
x58 = 4
x25 = 0
x59 = 1
x26 = 6
x68 = 2
x35 = 0
x69 = 6
x36 = 2
x7,10 = 3
Z = 16 = 16,000 units
36.
x14 8
x57 = 10
Total cost = 684 = $684,000
subject to:
x13 10
x13 = 2
x9,10 = 7
Maximize Z = x10, 1
x57 3
x45 = 8
x8,10 = 6
This problem is solved using Excel with the
addition of a cost constraint to the normal linear
programming formulation for a maximum flow
problem, as follows,
x12 7
x12 = 6
x10,1 100
3( x12 + x13 + x14 ) + 5( x25 + x26 ) + 7( x35 + x36 ) + 4( x45 )
+ 22( x57 + x58 + x59 ) + 19( x68 + x69 ) +12 x7,10 + 14 x8,10
+ 16 x9,10 700
110
37.
12610121315 = 25
126121315 = 35
1291215 = 10
136101215 = 30
137101315 = 20
147101315 = 20
1476101315 = 10
14761215 = 5
1481315 = 25
1581315 = 35
1581415 = 5
15111415 = 30
maximum flow = 250
Branch
12
13
14
15
26
29
36
37
47
48
58
511
610
612
710
38.
12 = 16
25 = 12
57 = 12
26 = 12
67 = 4
712 = 16
1215 = 22
13 = 22
39 = 6
911 = 2
1112 = 2
1312 = 4
Allocation
Branch
Allocation
70
50
60
70
25
45
30
20
35
25
40
30
65
5
40
76
813
814
912
1012
1013
1114
1213
1215
1315
1415
15
60
5
45
55
50
30
60
45
170
35
34 = 16
410 = 4
910 = 4
1013 = 8
1314 = 4
48 = 12
814 = 12
1415 = 16
Total traffic = 38,000 cars.
111
CASE SOLUTION: AROUND THE
WORLD IN 80 DAYS
end of the network. Additional branches were added to
connect Casablanca with Lisbon (5657) and Lisbon
with London (5657).
Using QSB + the following optimal route for Phileas
Fogg was determined (which is approximately the same
route he travelled in the book).
Although it appears that Phileas Fogg lost his wager,
recall that, as in the novel, he travelled toward the east
and eventually crossed the international date line. This
saved him one day and allowed him to win his wager
once he realized (just in time) the error in his
calculations.
1(London) 6(Paris) 7(Barcelona) 12(Naples)
17(Athens) 22(Cairo) 23(Aden)
28(Bombay) 31(Calcutta) 33(Singapore)
35(Hong Kong) 37(Shanghai)
39(Yokohama) 41(San Francisco)
47(Denver) 50(Chicago) 53(New York)
1(London) = 81 days
CASE SOLUTION: BATTLE OF THE
BULGE
(1) Verdun (2) Stenay = 8
(1) Verdun (3) Montmedy = 23
(1) Verdun (5) Etain = 26
(2) Stenay (11) Bouillon = 8
(3) Montmedy (6) Virton = 10
Note that 3 additional end nodes were added to the
network for computer solution 55, 56 and 57. Node 55
replaced node 3 (Casablanca); node 56 replaced node 2
(Lisbon), and node 57 replaced node 1 (London) at the
112
CASE SOLUTION: NUCLEAR WASTE
DISPOSAL AT PAWV POWER AND
LIGHT
(3) Montmedy (11) Bouillon = 15
(4) Longuyon (3) Montmedy = 2
(4) Longuyon (7) Longwy = 5
(5) Etain (4) Longuyon = 7
(5) Etain (8) Briey = 10
(5) Etain (9) Havange = 9
(6) Virton (13) Tintigny = 10
(7) Longwy (14) Arlon = 9
(8) Briey (10) Thionville = 10
(9) Havange (15) Luxembourg = 8
(10) Thionville (15) Luxembourg = 7
(10) Thionville (9) Havange = 3
(11) Bouillon (12) Florenville = 7
(11) Bouillon (16) Paliseul = 16
(12) Florenville (13) Tintigny = 7
(13) Tintigny (17) Neufchateau = 12
(14) Arlon (18) Martelange = 8
(15) Luxembourg (19) Diekirch = 21
(16) Paliseul (20) Recogne = 16
(17) Neufchateau (18) Martelange = 12
(18) Martelange (21) Bastogne = 23
(19) Diekirch (21) Martelange = 3
(19) Diekirch (21) Bastogne = 18
(19) Diekirch (18) Martelange = 3
(20) Recogne (21) Bastogne = 16
This is a modified shortest route problem. Instead of
the minimum time as the objective function the
population traveled through should be minimized. The
time (which would normally be the objective function)
should be a constraint 42 hours.
Solution:
(1) Pittsburgh - (4) Akron
(4) Akron - (6) Toledo
(6) Toledo - (10) Chicago
(10) Chicago - (16) Davenport/Moline/Rock Island
(16) Davenport/Moline/Rock Island - (19) Des Moines
(19) Des Moines - (23) Omaha
(23) Omaha - (28) Cheyenne
(28) Cheyenne - (31) Salt Lake City
(31) Salt Lake City - (33) Nevada Site
Total time = 39.95 hours
Total population (Z) = 15.83 million
Total flow = 57,000 troops
113
