ffiffi&p ffiffi
Network Models
There is a multitude of operations research situations that can be modeled and solved
as networks (nodes connected by branches). Some recent surveys report that as much
as 70Yo of the real-world mathem atícalprogramming probl"-, .u., be represented by
network-related models. The following list illustrates póssible applications of networks.
1-, Design of an offshore natural gas pipeline network connecting wellheads in the
Gulf of Mexico to an inshore delivery point. The objective of the model is to minimize
the cost of constructing the pipeline.
2, Determination of the shortest route between two cities in a network of roads.
3, Determination of the maximum capacity (in tons per year) of a coal slurry
PiPeline network joining the coal mines in Wyoming wiih the power plants in
Houston. (SlurrY PiPelines transport coal by pumpiňg water through specially
designed pipes.)
4, Determination of the minimum-cost flow schedule from oil fields to refineries
through a pipeline network.
5, Determination of the time schedule (start and completion dates) for the activities
of a construction project.
The solution of these situations, and others like it,
variety of network optimization algorithms. This chapter
algorithms.
1". Minimal spanning tree (situation 1)
2. Shortest-route algorithm (situation 2)
3. Maximum flow algorithm (situation 3)
4- Minimum-cost capacitated network algorithm (situation 4)
5. Critical path (CPM) algorithm (situation 5)
is accomplished through a
will present five of these
213
6.1
214 Chapter 6 Network Models
The situations for which these algorithms apply can also be formulated and
solved as explicit linear programs. However, the proposed network-based algorithms
are more efficient than the simplex method.
NETWoRK DEFlNlTloNs
A network consists of a set of nodes linked by arcs (or branches). The notation for
describing a network is (N Á), where N is the set of nodes, and A is the set of arcs. As
an illustration, the network in Figure 6.]_ is described as
l : {1, 2,3,4,5)
A:{(1,,2),(1,,3),(2,3),,(2,,5),(3,4),(3,5),(4,2),(4,5)}
FlGURE 6.1
Example of (N,,a) network
Associated with each network is some type of flow (e.g., oil products flow in a
pipeline and automobile traffic flows on highways).In general, the flow in a network is
limited by the capacity of its arcs, which may be finite or infinite.
An arc is said to be directed or oriented if it allows positive flow in one direction
and zero flow in the opposite direction. A directed ne work has all directed arcs.
A path is a sequence of distinct arcs that join two nodes through other nodes
regardleis of the direction of flow in each arc. A path forms a cycle if it connects a node
toltself through other nodes. For example, in Figure 6.1, arcs (2,3),(3,5), and (5,2) form
a loop. A cycle is directed if it consists of a directed path; e.E., (2,3), (3,4), and (4,2) in
Figure 6.1.
A connected network is such that every two distinct nodes are linked by at least
one path. The network in Figure 6.]_ demonstrates this type of network. A tree is a
connected network that may involve only a subset of all the nodes of the network
with no cycles allowed, and a spanning tree is a tree that links all the nodes of the
network, also with no cycles allowed. Figure 6.2 provides examples of a ttee and a
spanning tree for the network in Figure 6.1.
FlGURE 6.2
Examples of a tree and a spanning tree
given the network in Figure 6.1
Spanning tree
a,9\/
\/>--1
l)
Tree
__ ]
= - -]._1.1
, _._.,i1>
. f frll
.: _ -: _-\>
....,,, 11 t .1
.-. _-.1_:
. . l1l., l:
--: -*
:
- __]-__1_]L[c:
_ -. - ]-, ll l-
_oIn]
-, l
L1^
,,- -;aS,
rCe 1S.1
- -,., --l_
- -L- :
_ lLia
- _'- Ii r-] ,,_
6.2 Minimal Spanning Tree Algorithm 215
PRoBLEM sET 6.1A
1-, For each network in Figure 6.3 determine (a) a path, (b) a cycle, (c) a directed cycle, (d) a
tree, and (e) a spanning tree.
/
1)
\
J
FlGURE 6.3
Networks for Problem 1, Set 6.],a
(ii)
6,2
2. Determine the sets N and A for the networks in Figure 6.3.
3. Draw the network defined by
N : {1,2,3,4,5,6}
A:{(I,2),(1,5),Q,3),Q,4),(3,5),(3,4),(4,3),(4,6),(5,2),(5,6)}
4, Consider eight equal squares arranged in three rows, with two squares in the first row,
four in the second, and two in the third. The squares of each roware arranged symmetricalffibout
the vertical axis.It is desired to fillJhe squares with distinct numbers in the
range l, 2,... , and 8 so that no two adjacent vertical, horizontal, or diagonal squares hold
consecutive numbers. Use network representation as a vehicle to find the soluiion in a
systematic way.
5, Three inmates escorted by 3 guards must be transported by boat from San Francisco to
the Alcatraz penitentiary island to serve their senterr""r. Tň" boat cannot transfer more
than two PerSonS in either direction. The inmates are certain to overpower the guards if
theY outnumber them at any time, Develop a network model that deiigns the báat trips in
a manner that ensures a safe transfer of the inmates. Assume that the inmates will noi flee
if given a chance.
M!NlMAL sPANNlNG TREE ALGoRITHM
The minimal Spanning tree algorithm deals with linking the nodes of a network,
directlY or indirectly, using the shortest length of connectiňg branches. A typical appti_
cation occurs in the construction of paved roads that link several towns. The road
between two towns may pass through one or more other towns. The most economical
design of the road sYstem calls for minimizing the total miles of paved roads, a result
that is achieved by implementing the minimalipanning tree algorithm.
The stePs of the procedure are given as follows. Let 1i : {I,2, . . . , n} be the set
of nodes of the network and define
Ct : Set of nodes that have been permanently connected at iterationk
e t, : Set of nodes as yet to be connected permanently
2)
\aI)
(i)
216 Chapter 6 Network Models
SetC6:aanďeo:N.
Start with any node, i, in the unconnected set Č6and set C1 : {i}, which ren_
ders e1 - l/ - {l}. Set k : 2.
Step k. Select a node, i*, ir the unconnected set e1-1 that yields the shortest
urCto a node in the connected set Cu_r.Link i* permanently to C1_1 and
remove it from e o_r,that is,
Cr: Cr-t l {j-},eo:et,-, - f-}
If the set of unconnected nodes,,e t, is empty, stop. Otherwise, set k : k -l I
and repeat the step.
Step 0.
Step 1.
General
Example 6.2-1
Midwest TV Cable Company is in the process of providing cable service to five new
housing development aróas.-Figure 6.4 depicts possible TV linkages among the fjve
areas. Ťhe cabló miles are shown on each arc. Determine the most economical cable
network.
The algorithm starts at node 1 (any other node will do as well), which gives
Cl : {1}, e, : {2,3,4,5,6}
The iterations of the algorithm are summaňzed in Figure 6.5.The thin arcs provide all
the candidate links between C and C. the thick branches represent the permanent
links among the nodes of the connected set C, and the dashed branch represents the
new (permánent) link added at each iteration. For example, in iteration 1, branch
Q,z) ii tt
"
shortest link ( : 1 mile) among all the candidate branches from node 1 to
ňodés 2,3,4, and 5 of the unconnected set Cr. Hence, link (I,2) is made permanent
and i- : Z,which yields
Cz : {I,Z},ez : {3,4,5,,6}
The solution is given by the minimal spanning tree shown in iteration 6 of Figure
6.5. The resulting minimum cable miles needed to provide the desired cable service are
1 + 3 + 4 + 3 + 5 : 16 miles.
FIGURE 6.4
cable connections for Midwest Tv cable
Company
3 (miles)
}- which renthe
shortest
C;_1 and
;etk: k+I
r to five new
nong the five
nomical cable
t gir.es
rcs provide all
le permanent
epresents the
ion 1, branch
rom node 1 to
le permanent
rn 6 of Figure
ble service are
C3
C3
6,2 Minimal Spanning Tree Algorithm 217
Iteration 4Iteration 3
Iteration 6
(Minimal spanning tree)
FlGURE 6,5
solution iterations
for MidwestTV
Cable Company
Iteration 5
You can use TORA to generate the iterations of the minimal spanning tree. From
Main menu,SeleCtNetwork models * Minimal spanníngt tree.Next,fromroruauroorru
menU. SeleCt Solve prob;em + Co to output screen. In the output Screen. select a
Starting node oÍId then use Next iteration or Al1 iterations to generate the Succes_
sive iterations.You can restart the iterations by selecting a new s.l.cing node. Figure
6.6 gives TORA output for Example 6.2-I (file ch6ToraMinSpanBx6-2-y txt).
Iteration 1 Iteration2
,č5
/
218 Chapter 6 Network Models
FlGURE 6,6
Output of the minimal spanning tree of Example 6.2-1
PRoBLEM sET 6.2A
1. Solve Example 6.2-I starting at node 5 (instead of node 1), and show that the algorithm
produces the same solution.
2. Determine the minimal spanning tree of the network of Example 6.2-1, under each of the
following separate conditions:
(a) Nodes 5 and 6 are linked by a Z-mile cable.
(b) Nodes 2 and 5 cannot be linked.
(c) Nodes 2 and6 are linked by a 4-mile cable.
(d) The cable between nodes ]. and 2 is 8 miles long.
(e) Nodes 3 and 5 are linked by a Z,mile cable.
(f) Node 2 cannot be linked directly to nodes 3 and 5.
3. In intermodal transportation,loadeďtruck trailers are shipped between railroad terminals
by placing the trailer on special flatbed carts. Figure 6.7 shows the location of the
main railroad terminals in the United States and the existing railroad tracks. The objective
is to decide which tracks should be "revitalízed" to handle the intermodal traffic.In
particular, the Los Angeles (LA) terminal must be linked directly to Chicago (CH) to
accommodate expected heavy traffic. Other than that, all the remaining terminals can be
linked, directly or indirectly, such that the total length (in miles) of the selected tracks is
minimized. Determine the segments of the railroad tracks that must be included in the
r ev italtzatio n p ro gr am.
::-_'
ileorithm
:ach of the
rd termir
of the
Le objec-
traffic.In
CH) to
als can be
ltracks is
d in the
6.2 Minimal Spanning Tree Algorithm 21g
FlGURE 6.7
Network for Problem 3, Set 6.2a
Figure 6.8 gives the mileage of the feasible links connecting nine offshore natural gas
wellheads with an inshore delivery point. Because the location of wellhead 1 is the closest
to shore, it is equipped with sufficient pumping and storage capacity to pump the output
of the remaining eight wells to the delivery point. Determine the minimum pipeline net_
work that links the wellheads to the delivery point.
FlGURE 6.8
Network for Problem 4.Set 6.2a
In Figure 6,8 of Problem 4, suppose that the wellheads can be divided into two groups
dePending on gas pressure: a high-pressure group that includes wells 2,3,4,and 6; u.rd u
low-Pressure group that includes wells 5,7,8,and 9. Because of pressure difference, well_
heads from the two groups cannot be linked.At the same time, both groups must be connected
to the delivery point through wellhead 1. Determine the minimumpipeline
network for this situation.
Electro Produces 15 electronic parts on 10 machines.The company wants to group the
machines into cells designed to minimize the "dissimilarities" ámong the parts processed
220 Chapter 6 Network Models
in each cell. A measure of "dissimilarity," dii,among the parts processed on machines l
andi can be expressed as
ílii
4,' :I - '
nii + mii
where nilis títe number of parts shared between machines i and j, and milis the number of
parts that are used by either machine i ori only.
The following table assigns the parts to machines:
Machine Assigned parts
L
2
J
4
5
6
7
8
9
10
I,6
2,3,7,8,9,12,13,15
3,5,I0,1,4
2,7,8,11,12,13
3,5,I0,It,1,4
I,4,5,9,I0
z,5,,7,8,9, 10
3,4,15
4,I0
3,8, 10, 14, ].5
(a) Express the problem as a network model.
(b) Show that the determination of the cells can be based on the minimal spanning tree
solution.
(c) For the data given in the preceding table, construct the two- and three-cell solutions.
6.3 SHoRTEST_RoUTE PRoBLEM
The shortest-route problem determines the shortest route between a source and destination
in a transportation network. Other situations can be represented by the same
model as illustrated by the following examples.
6.3.1 Examples of the Shortest-Route Applications
Example 6.3-1 (Equipment Replacement)
RentCar is developing a replacement plan for its car fleet for a 4-year planning horizonthat
starts January I,200t, and terminates December 31,2004. At the start of each
yeat)a decision is made as to whether a caíshould be kept in operation or replaced. A
car must be in service a minimum of t yeat and a maximum of 3 years. The following
table provides the replacement cost as a function of the year a car is acquired and the
number of years in operation.
Replacement cost ($) for given years in operation
Equipment
acquired at start of
z00I
zOOz
2003
z004
4000
4300
4800
4900
5400
6200
7100
9800
8700
t
9800
.:-. ].íof
_ _.:ions,
d destile
Same
_. hori_
: each
:, -,ed. A
. _,_lrr ing
::d the
6,3 Shortest-Route Problem 221
FlGURE 6.9
Equipment replacement
problem as a
shortest-route model
The Problem can be formulated as a network in which nodes 1 to 5 represent the
s.tart of years 2001, to 2005. Arcs from node 1 (year 200I) can reach only node s 2,3, and,
4 because a Car must be in operation between 1 and 3 years. The arcŠfrom the other
nodes can be interprete,d similarly.The length of each aic equals the replacement cost.
The solution of the problem is equivalent to finding the shortest routebetween nodes
1 and 5.
Figure 6.9 shows
_the
resulting network. Using TORA,1 the shortest route (shown
9l t,t: thick path) is 1 + 3 + 5. The solution meáns that a car acquired at the itart of
200Í (node J.) musJ be replaced after 2 yeurs at the start of 2003 (node 3). The replacement
car will then be kept in service until the end oí2004.The total cost of this replace_
ment policy is $ ]_2,500 (: $ 5400 + $ 7100).
Example 6.3-2 (Most Reliable Route)
I. Q. Smart drives daily to work. Having just completed a course in network analysis,
Smart is able to determine the shortest route tó work. Unfortunately, the seleóted
route is heavily, patrolled by police, and with all the fines paid for speediňg, the shortest
route may not be the best choice. Smart has thus decided to chooie a route that maximizes
the probability oínot being stopped by police.
The network,in Flgure 6.10 shows the possible routes between home and work,
and the associated probabilities of not being stopped on each segment. The probability
ot
lot being stopped on the way to work is the pioduct of the p}obabilities associated
with the successive segments of the selected route. For examplé, the probability of not
FlGURE 6.10
Most-reliable-route network model
lFrom l{ain menu, select setwork
=žShortest routes.
noce,s * S]-.or:es: TOj"e . From so'-/l,-\4oD-tV menu, select so-r Ve prob]F.
222 Chapter 6 Network Models
FlGURE 6.11
Most-reliable-route
representation as a shortestroute
model
receivingafineontheroute1-+3-+5-+7is.9 X.3 X .25: .0675.Smart'sobjective
is to select the route that maximizes the probability of not being fined.
The problem can be formulated as a shortest-route model by using a logarithmic
transformation that converts the product probability into the sum of the logarithms of
probabilities-that is, if pu, : pt X pz X X pt is the probability of not being
stopped, then log ptk : logp, + 1og pz * -l logpp.
Mathematically, the maximization of pu, is equivalent to the maximization of
logpro. Because logpro < 0, the maximization of logpro is, in turn, equivalent to the
minimization of - logp16. Using this transformation, the individual probabilities p7
in Figure 6.].0 are replaced with - Iogpifor all i in the network, thus yielding the
shortest-route network in Figure 6.11.
Using TORA, nodes 1,,3,5, and 7 define the shortest route in Figure 6.]_]. with a
corresponding "length" of I.I707 (: -1ogp17). Thus, the maximum probability of not
being stopped is pr, : .0675.
Examp|e 6,3-3 (Three-Jug Puzzle)
An 8-gallon jug is filled with fluid. Given two empty 5- and 3-gallon j.rgs, we want to
divide the 8 gallons of fluid into two equal parts using the three jugs. No other measuring
devices are allowed. What is the smallest number of pourings needed to achieve
this result?
You probably can guess the solution of this pllzzle. Nevertheless, the solution
process can be systematizedby representing the problem as a shortest-route problem.
A node is defined to represent the amount of fluid in the 8-, 5-, and 3-gallon jugs,
respectively. This means that the network starts with node (8,0, 0) and terminates with
the desired solution node (4,4,0).A new node is generated from the current node by
pouring fluid from one jug into another.
Figure 6.]-2 shows different routes that lead from start node (8,0,0) to end node (4,
4,0).The arc between two successive nodes represents a single pouring, and hence can
be assumed to have a length of ]_ unit.The problem reduces to determining the shortest
route between node (8,0,0) and node (4,4,0).
The optimal solution, given by the bottom path in Figure 6.I2,requires 7 pourings.
t-
; objective
lgarithmic
arithms of
not being
ization of
ent to the
rbilities p7
elding the
i.11 with a
liry of not
l.; rr-ant tO
-: measur::
achieve
. solution
:roblem.
:.: jlon ]UgS.
:_etes with
:_: node by
:
j node (4,
]ence can
l e shortest
-pourings.
6.3 Shortest-RouteProblem
FlGURE 6.12
Three-jug puzzle representation as a shortest-route model
PRoBLEM sET 6,3A
1. Reconstruct the equipment replacement model of Example 6.3-I,assuming that a car
must be kept in service at least 2years,with a maximum service life of 4 years. The planning
horizon is from the start of 2001, to the end of 2005.The following table provides the
necessary data.
Replacement cost ($) for given years in operation
Year acquired
3800
4000
4200
4800
5300
Figure 6.13 provides the communication network between two stations,1 and 7.The
Probability that a link in the network will operate without failure is shown on each arc.
Messages are sent from station 1 to station 7,and the objective is to determine the route
that will maximize the probability of a successful transmission. Formulate the situation as
a shortest-route model, and solve with TORA.
An old-fashioned electric toaster has two spring-loaded base-hinged doors. The two doors
oPen outward in opposite directions away from the heating element. A slice of bread is
toasted one side at a time by pushing open one of the doors with one hand and placing
the slice with the other hand. After one side is toasted, the slice is turned over to get the
other side toasted.It is desired to determine the sequence of operations (placing, toasting,
turning, and removing) needed to toast three slices of bread in the shortest possible
4100
4800
5300
5700
z001,
2002
2003
2004
2005
6800
7000
7200
224 Chapter 6 Network Models
F|GURE 6.1 3
Network for Problem Z,Set6.3a
time. Formulate the problem as a shortest-route model using the following elemental
times for the different operations:
Operation Time (seconds)
place one slice in either side 3
Toast one side 30
Turn slice already in toaster 1
Remove slice from either side 3
Production Planning. DirectCo sells an item whose demand over the next 4 months is
100, 140, 2I0, and ]_80 units, respectively. The company can stock just enough supply to
meet each month's demand, or it can overstock to meet the demand for two or more successive
and consecutive months.In the latter case, a holding cost of $1.20 is charged per
overstocked unit per month. DirectCo estimates the unit purchase prices for the next 4
months to be $15, $]_2, $10, and $14, respectively. A setup cost of $200 is incurred each
time a purchase order is placed.The company wants to develop a purchasing plan that
will minimíze the total costs of ordering, purchasing, and holding the item in stock.
Formulate the problem as a shortest-route model, and use TORA to find the optimum
solution.
Knapsack Problem. A hiker has a 5-ft3 backpack and needs to decide on the most valuable
items to take on the hiking trip.There are three items from which to choose.Their
volumes are 2,3, and 4 ft3, and the hiker estimates their associated values on a scale from
0 to ].00 as 30,50, and 70, respectively. Express the problem as a longest-route network,
and find the optimal solution. (Hint: A node in the network may be defined as [l, v],
where i is the item number considered for packing, and y is the volume remaining immediately
before the decision is made on i.)
6,3.2 Shortest-Route Algorithms
This section presents two algorithms for solving both cyclic (i.e., containing loops) and
acyclic networks:
1. Dijkstra's algorithm
2. Floyd's algorithm
4.
5.
t
6.3 Shortest-Route Problem 225
Dijkstra's algorithm is designed to determine the shortest routes between the
Source node and every other node in the network. Floyd's algorithm is general because
it allows the determination of the shortest route between any two nodesin the network.
Dijkstra's Algorithm. Let ui be the shortest distance from source node 1 to node 4
and define d,i (= 0) as the length of arc (i, j).Then the algorithm defines the label for
an immediately succeeding node i as
|ri,if : |r, + d,i,,if, d,j
= 0
The label for the starting node is [0,
-],
indicating that the node has no predecessor.
Node labels in Dijkstra's algorithm are of two types: temporary and, permanent. A
temporary label is modified if a shorter route to a node can be found.At the point when
no better routes can be found, the status of the temporary label is changed to permanent.
Step 0. Label the source node (node 1) with the permanentlabel [0,-].Set i : ]..
Step Í. (a) Compute the temporary labels Iu, + dil,i)for each node jthatcan be
reached from node i, provided j i, not permanently labeled.If node i is
already labeled with [z7, k] through another node k andif ui * di1 1 u1,
replace lri, k]with [z, + dij, i7.
(b) If all the nodes have permanenr labels, stop. Otherwise, select the label
|r,,
'l
having the shortest distance (:u) among all the temporary labels
(break ties arbitrarily). Set l : r andrepeat step i.
Example 6.3-4
The network in Figure 6.1-4 gives the routes and their lengths in miles between city 1
(node 1) and four other cities (nodes 2 to 5). Determine Íheshortest routes between
city 1 and each of the remaining four cities.
Iteration 0. Assign the permanentlabel [0,-] to node 1.
I eration 1. Nodes 2 and 3 can be reached from (the last permanently labeled) node
1.Thus, the list of labeled nodes (temporary and permanent) becomes
Node Label Statusrlu-
ir
t)nn
k_
1 [0,-l
2 I0 + 100, 1] : [100, 1]
3 [0 + 30, 1] : [30, 1]
permanent
Temporary
Temporary
FlGURE 6.14
Network example for Dijkstra's
shortest-route algorithm
\
ť ,o,A,o
30
2
100
UU
1 _) 5
226 Chapter 6 Network Models
For the two temporary labels [100, 1] and [30, 1_], node 3 yields the
smaller distance (u, : 30). Thus, the status of node 3 is changed to per-
manent.
Iteration 2. Nodes 4 and 5 can be reached from node 3, and the list of labeled nodes
becomes
Node Label Status
1"
z
3
4
5
[0,-]
[100,1]
[30, u
[30 + 10, 3] : [40, 3]
[30 + 60, 3] : [90, 3]
permanent
Temporary
permanent
Temporary
Temporary
The status of the temporary label [40,3] at node 4 is changed to permanent
(ua: 40).
Iteration 3. Nodes 2 and 5 can be reached from node 4. Thus, the list of labeled
nodes is updated as
Node Label Status
1
2
3
4
5
[0,-]
[40+15,4]:[55,4]
[30,1]
[40,3]
[90,3] or [40 + 50, 4] : [90, 4]
permanent
Temporary
permanent
permanent
Temporary
Node 2's temporary label [1_00, 1] in iteration2 is changed to [55,4] in
iteration 3 to indicate that a shorter route has been found through node
4. Also, in iteration 3, node 5 has two alternative labels with the same
distance u5 : 90.
The list for iteration 3 shows that the label for node 2 is now perma-
nent.
Iteration 4. Only node 3 can be reached from node 2. However, node 3 has a permanent
label and cannot be relabeled. The new list of labels remains the
same as in iteration 3 except that the label at node 2 is now permanent.
This leaves node 5 as the only temporary label. Because node 5 does not
lead to other nodes, its status is converted to permanent, and the process
ends.
The computations of the algorithm can be carried out more easily on the network
as Figure 6.].5 demonstrates.
The shortest route between nodes ]. and any other node in the network is determined
by starting at the desired destination node and backtracking through the nodes
using the information given by the permanent labels. For example, the following
sequence determines the shortest route from node 1 to node 2:
Q)- [55,4] +(4) +|40,3] +(3)- [30,1] +(1)
Thus, the desired route is 1 + 3 -> 4+ 2 with a total length of 55 miles.
t-_
6.3 Shortest-RouteProblem
3
) perl
nodes
:]]ln-
-in
: :ode
:]1e
]aima-
:;Ima::S
the
] -.-nent.
: _S not
:: f,ceSS
; .'* Ork
jeter-
]odeS
,,-,rr ing
#oo*ffi
[55,4](3.)
[0,-]rrl
( ) : iteration
[90.3](2)
[90,4]i3;
F|GURE 6.15
Dijkstra's labeling procedure
TORA can be used to generate Dijkstra's iterations. From the solvn/MoDll.y
menU, SeleCt Soive probLen ==)fceracíons=*Dijkscra,s a]gorir,nm. Figure 6.16 provides
TORA's iterations output for Exam pte 6.3-4 (file ch6ToraDijkstraĚx6-3-+.txi).
F|GURE 6.16
TORA Dijkstra iterations for Example 6.3-4
í40,3]Q)
[30,1](1)
i
228 Chapter 5 Network Models
PRoBLEM sET 6.38
1_. The network in Figure 6.17 gives the distances in miles between pairs of cities I,2, ,,. , and
8. Use Dijkstra's algorithm to find the shortest route between the following cities:
(a) Cities 1 and 8
(b) Cities ]. and 6
(c) Cities 4 and 8
(d) Cities 2 and 6
FlG U RE 6.1 7
Network for Problem ]., Set 6.3b
2. Use Dijkstra's algorithm to find the shortest route between node 1 and every other node
in the network of Figure 6.18.
FlGURE 6.18
Network for Problem 2, Set 6.3b
3. Use Dijkstra's algorithm to determine the optimal solution of each of the following
problems:
(a) Problem ]., Set 6.3a
(b) Problem 2,Set6.3a
(c) Problem 4, Set 6.3a
Floyd's Algorithm. Floyd's algorithm is more general than Dijkstra's because it
determines the shortest route between any two nodes in the network. The algorithm
represents an n-node network as a square matrix with n rows and n columns. Entry (i7)
of the matrix gives the distance dijfrom node l to node7, which is finite if l is linked
directly to 7, and infinite otherwise.
L---
2- ... , and
:
her node
..-ause it
:_gorithm
: ltry (i,i)
_s iinked
6.3 Shortest-RouteProblem 229
FlGURE 6.19
Floyd's triple operation
The idea of Floyd's algorithm is straightforward. Given three nodes i, j, and k in
Figure 6.]-9 with the connecting distances shown on the three arcs, it is shorter to reach
k from i passing throughi if
dij +dltldit
In this case, it is optimal to replace the direct route from i + k with the indirect route
i + j + k. This triple operaúion exchange is applied systematically to the network
using the following steps:
Step 0. Define the starting distance matrix D6 and node sequence matrix S9 as given
below. The diagonal elements are marked with (-) to indicates that they are
blocked.Setk: ]_.
General Step /r. Define row k and column k as pivot row and pivot column. Apply the
triple operation to each element dilin D o_, for all l and 7. If the condition
dit * dti 1 d,i,Q + k, i + k,, andi + j)
is satisfied, make the following changes:
(a) Create Dtby replacing d;linDrrwithd,o * dni.
(b) Create,So by replacing s7 in, 1_1 with k Set k : k + 1, and repeat step k.
1
2
Do: i
i
n
1
z
So: :
i
n
d, dii dr,
d^ dzi dz,
d,,, d,, dij d',
Drt drZ d.,rj
z j n
1 j n
1 2 j n
1 2 j
23O Chapter 5 Network Models
Pivot
column column column
jkq
FlGURE 6.20
Implementation of triple operation in
matrix form
Row l
pivot row k
Rowp
Step k of the algorithm can be explained by representing D*, as shown in Figure
6.20.Here, row k and column k define the current pivot row and column. Row irepresents
any of the rows I,2,..., and k - 1,, and row p represents any of the rows
k + I, k + 2, ... , and n. Similarly, column i represents any of the columns ]_, 2, ... ,
andk - 1,andcolumnqrepresentsanyof thecolumns k + l, k + 2, ...,andn.With
the triple operation, if the sum of the elements on the pivot row and the pivot column
(shown by squares) is smaller than the associated intersection element (shown by a
circle), then it is optimal to replace the intersection distance by the sum of the pivot
distances.
After /? steps, we can determine the shortest route between nodes i andi from the
matrices D, and S, using the following rules:
1. From D,, dil gives the shortest distance between nodes i and j.
2. From ^S,,
determine the intermediate node n : siithat yields the route i + k + j.
If s;t : k and snj : i, stop; all the intermediate nodes of the route have been
found. Otherwise, repeat the procedure between nodes i and k, and between
nodes k and j.
ExampIe 6.3-5
For the network in Figure 6.21,,,find the shortest routes between every two nodes. The
distances (in miles) are given on the arcs. Arc (3,5) is directional so that no traffic is
allowed from node 5 to node 3. Al1 the other arcs allow traffic in both directions.
FlGURE 6.21
Network for Example 6.3-5
t-
6.3 Shortest-Route Problem 231
Iteration 0. The matrices D9 and ,56 give the initial,representation of the network. D6
is symmetrical except that dr, : oo beóause no traffic is allowed from
node 5 to node 3.
D0
1,2345
,s0
1,z345
1,
2
J
4
5
1,
z
a
J
4
5
I
2
a
J
4
5
1
2
J
4
5
l
2
a
J
4
5
10 oo oO
J .iii 5 oo
10 6 15
oo 5 6 4
oo oo oo 4
Iteration 1. Set k : 1.T!9 pivot row and column are shown by the lightly shaded
first row and first column in the D6-matrix. The darker ."Tl., ár, iid drr,
are_tbe only ones that canbe improved by the triple operati'oi.-Thus,li
and ,S1 are obtained from Dg andSo in théfoilowirrg .ra.rrr.r,
1. Replace drrwith dn -| dr : 3 + 10 : 13 and set szs : L
2. Replace drrwith dl t dn : 10 + 3 : 13 and set szz : I.
These changes are shown in bold in matrices D, and 51.
Iteration 2. Set k : 2, as shown by the lightly shaded row and column in D1. The
triPle operation is applied to the darker cells in D, and,S1. The ,i,.urii"g
changes are shown in bold in Drand,S2.
in Figure
r i reprelhe
rows
1- 2, ... ,
il n. With
l column
xrn by a
the pivot
from the
+k+ j.
rve been
between
rdes. The
traffic is
ns.
D1
1,2345
s1
12345
1,
2
J
4
5
D2
1z345 s2
1,2345
2 3 4 5
r 4 5
I 4 5
1 2 J 5
1 2
a
J 4
J 10
ri:ii;:iti#
oo
3 13 ,oó
10 13 6 1,5
;i.1..ffi ), 6 4
oo oo oo 4
z J iffi 5
1 1 4 5
1 1 4 5
2 J 5
1 2 J 4
J 10 8 u:l#+
3 13 5
10 13 6 15
8 5 6 4
oo oo óo 4
232 Chapter 6 Network Models
Iteration 3. Set k : 3, as shown by the shaded row and column in D2.The new
matrices are given by D, and , 3.
D1
J
.,r
J
1,
2
J
4
5
J 10 8
J i[E,i 5 ,i,ffi
10 ,;{$_j,,r 6 i.i.t$.
8 5 6 4
4
1
2
J
4
5
Iteration 4. Set k : 4, as shown by
new matrices are given
the lightly-shaded row and column in D3. The
by Do and Sa.
D4
a
_)
s4
J
1,
2
a
J
4
5
1
2
_,
4
5
Iteration 5. Set k : 5, as shown by the shaded row and column in Da.No further
improvements are possible in this iteration. Hence, D5 and 55 are the
same as Da and Sa.
The final matrices D5 and,S5 contain all the information needed to
determine the shortest route between any two nodes in the network. For
example, consider determining the shortest route from node ]- to node 5.
First, the associated shortest distance is given by d1, : 12 miles. To
determine the associated route, recall that a segment (i, j) represents a
direct link only if s4 : i. Otherwise, l and j are linked through at least
one other intermediate node. Because 15
: 4,the route is initially given
as ]. + 4 + 5.Now, because 14
: Z + 4,the segment (1,4) is not a
direct link, and I + 4 must be replaced with 1, +2 ) 4, and the route
1, + 4+ 5 now becomes 1, +2 + 4 +5.Next,because s12 : 2, s24 : 4,
and sa5 : 5, the route I +2 + 4 + 5 needs no further "dissecting" and
the process ends.
As in Dijkstra's algorithm,TORA can be used to generate Floyd's iterations. From
the sor,vn/1qopt,rv menu, select solve,prob.lerll * TLerations * E1o _d,r15, algóri'Ehm.
Figure 6.22illusírates TORAs output for Floyd's Example 6.3-5 (file ch6ToraFloydEx6-
3-5.txt).
2 J 2 $
1 t 4 3
1 1 4 \.
z 2 J 5
t z 4
J 10 8 12
J 11 5 9
10 11 6 10
8 5 6 4
t2 9 10 4
2 J 2 4
1, 4 4 4
1 4 4 4
z 2 J 5
4 4 4 4
t-
5.3 Shortest-Route Problem 233
5
---1-1 1
;3l--l3 .l
-: 5l
l
--t----
]-|
The
rther
e the
ťed to
rork. For
o node 5.
.To
sents a
t least
rlly given
ota
: route
-S",:4.
ing" and
i,]nS. From
].aatnm.
FioydEx6FlGURE
6.22
TORA Floyd iterations for Example 6.3-5
PRoBLEM sET 6,3c
3.
In Example 6.3-5,use Floyd's algorithm to determine the shortest routes between each of
the following pairs of nodes:
(a) From node 5 to node ].
(b) From node 3 to node 5
(c) From node 5 to node 3
(d) From node 5 to node 2
Apply Floyd's algorithm to the network in Figure 6.23. Arcs (7,6) and (6,4) areunidirectional,
and all the distances are in miles, Determine the shortest route between the following
pairs of nodes:
(a) From node 1 to node 7
(b) From node 7 to node ]_
(c) From node 6 to node 7
The Tell-All mobile phone company services six geographical areas. The satellite distances
(in miles) among the six areas are given in Figure 6.24.TeII-All needs to determine
the most efficient message routes that should be established between each two areas in
the network.
Six kids-Joe, Kay, Jim, Bob, Rae, and Kim-play a variation of the game of hide and
seek. The hiding place of a child is known only to a select few of the other children. A
234 Chapter 5 Network Models
FlGURE 6.23
Network for Problem 2, Set 6.3c
FlGURE 6.24
Network for Problem 3, Set 6.3c
child is then paired with another with the objective of finding his or her hiding place. This
may be achieved through a chain of other kids who eventually willlead to discovering
where the designated child is hiding. For example, suppose that Joe needs to find Kim and
that Joe knows where Jim is hiding, who in turn knows where Kim is.Thus, Joe can find
Kim by first finding Jim, who in turn willlead Joe to Kim.The following list provides the
whereabouts of the children:
Joe knows the hiding places of Bob and Kim.
Kay knows the hiding places of Bob, Jim, and Rae.
Jim and Bob know the hiding place of Kay only.
Rae knows where Kim is hiding.
Kim knows where Joe and Bob are hiding.
Devise a plan for each child to find every other child through the smallest number of contacts.
What is the largest number of contacts?
6.3.3 Linear Programmin9 Formulation of the Shortest-Route
Problem
This section provides two LP formulations for the shortest-route problem. The formulations
are general in the sense that they can be used to find the shortest route between
any two nodes in the network. In this regard, the LP formulations are equivalent to
Floyd's algorithm.
Suppose that the shortest-route network includes n nodes and that we desire to
determine the shortest route between any two nodes and r in the network.
Formulaúion 1: This formulation assumes that an external one unit of flow enters the
network at node s and leaves it at node /, where s and t aíe the two target nodes
between which we seek to determine the shortest route.
1
2
6
700 \ \ 200
300 \
2'200
;*Š 1-,5)
L
-. This
-_:
_i
,_1'_ .lfld
_:1J
- -L::
.1lc
5.3 Shortest-Route Problem 235
Define
;,4 : amount of flow in arc (l, i), for all feasible i and j
c,, : length of arc (i,7), for all feasibl e i and j
Because on|y one unit of flow can be in any arc at any one time, the variable xilmust
assume binary values (0 or 1) only. Thus, the objective function of the linear prógram
becomes
Minimizez: Zr,i*,i
all defined arcs (i, 7)
There is one constraint that represents the conservation of flow at each node-that is,
for any node 7,
Total input flow : Total output flow
Formulation 2z The second formulation is actually the dual problem of the LP in
Formulation 1. Because the number of constraints in Formulation 1 equals the number
of nodes, the dual problem will have as many variables as the number of nodes in the
network. Also, all the dual variables must be unrestricted because all the constraints in
Formulation 1 are equations.
Let
!1 : dual constraint associated with nodei
Given s and t are the start and terminal nodes of the network, the dual problem is
defined as
subject to
MaximizeZ:|t-!,
li - |i = ',,,
for all feasible i and j
all yi and ylunrestricted in sign
, Jon,_
l1ru_
, , ! ! 11
:,
=;li tO
;:_]-- tO
_ _-- *L- -: } Lllg
.:,..deS
Example 6,3-6
Consider the shortest route network of Example 6.3-4.Suppose that we want to determine
the shortest route from node 1 to node Z;that is, J : ]_ and t:2. Figure 6.25
shows how the unit of flow enters at node 1 and leaves at nod,e 2.
FlGURE 6.25
Insertion of unit flow to determine
shortest route between node s : ]_ and
nodet:2
4
JU
1 J 5
236 Chapter 6 Network Models
Using Formulation 1, the associated LP is listed below.
Xzl
Minimize z : 100
Xl<X alX.lsXltXnXn
501560102030
-1Node ].
Node 2
Node 3
Node 4
Node 5
-1
1 -1
1
1
- -l
1
l
U
-1 0
1, :0
-1
The constraints represent flow conservation at each node. For example, at node 2,
"input flow : output flow" yields xu * x42 : I + xrr.Note that one of the constraints
is always redundant. For example, adding the last four constraints simultaneously
yields xn l x13 : 1, which is the same as constraint ]_.
The optimal solution (obtained by TORA;z i.
Z : 55, X73 : I, Xsq : l, X42: 1,
This solution gives the shortest route from node ]- to node 2 as
associated distance is z : 55 (miles).
To use FormulationZ,the dual problem associated with the
subject to
Maximizez:lz-!l,
|z - |l, < 100 (Route 1_-2)
lz - lt = 30 (Route 1-3)
lz - lz < 20 (Route 2-3)
lq - lz = 10 (Route 3-4)
ls - |z < 60 (Route 3-5)
lz - |q = 1_5 (Route 4-2)
|s - jq < 50 (Route 4-5)
Il, |z,... , Is unrestricted
Although the dual problem given above is a pure mathematical definition derived
from the primal problem, we actually can interpret the problem in a logical manner.
Define
y; : Distance to node l
2TORA does not accept a negative right-hand side. You can get around this inconvenience by selecting
the redundant constraint as the one having the negative right-hand side, then make it redundant by
changing : to š and setting the right-hand side to a very large value. Another trick is to add a new variable
whose upper and lower bounds equal 1, effectively forcing it to equal 1 in any solution. The constraint coefficients
of the new variable equal those of the current right-hand side, but with opposite sign. The right-hand
side of the "new" problem must be changed to zero for all the constraints (see file ch6ToralpShortRoute
Ex6-3-6.txt).
-1
1
1+3+4->2andthe
LP above is given as
t
- - -]- t
-_. :.^*_
: ,_ _11].1L:
_,-],.
_-..]t1--
: _ _..,l !1lš
;: .1S
lerived
nanner.
; _: JtLI18
- __::]t b\
,:-::1ble
- _ - -!i]
- lťlll-
.,-1.1nd
.RrTute
6.3.4
6.3 Shortest-Route Problem 237
with this definition, the shortest distance from the start node 1 to the terminal node 2
is determined by maximizing lz - |t. The constraint associated with route (a 7) suys
that the distancó from node Íto'noďe'lcannot exceed the direct length of that route.It
can be less if node j can be reached from node l through other ,ro?., that provide a
shorter path. For example, the distance from node 1 to ňode 2 is atmost too. with ttre
definition of y; as the distance to node i, we can assume that all the variables are non_
negative (instead of being unrestricted). We can also assume that lt : O as the distance
to node 1.
Based on the discussion above, and assuming that all the variables are nonnegative,
the optimum solution is given as
Z : 55, ll:0, lz: 55, yr: 30, |q: 40,./s : 0
The value of z : 55 gives the shortest distance from node 1 to node 2, which also
equalsh-!t:55-0:55.
The determination of the route itself from this solution is somewhat tricky.
We note that the solution satisfies in equation form the constraints of routes I_3,3_4,
and 4-2 because their slacks equal zero-that is, y3 - |t : 30, yo - ls : ]_0, and
lz - lq : 15. This result identifiei the shortest route áš t + s -+ 4'-+ 2.
Alojhel way for identifying the constraints that are satisfied in equation form is to
consult the dual solution of the LP of FormulationZ.Any constraint that has a nonzero
dual value must be satisfied in equation form (see Secti on 4.2.4).The following table
pairs the routes (constraints) with their associated dual values.
Route (constraint) I-2
Associated dual value
PRoBLEM sET 6.3D
1. In ExamPle 6.3-6,use the two LP formulations to determine the shortest routes between
the following pairs of nodes:
(a) Node 1 to node 5.
(b) Node 2 to node 5.
Excel Spreadsheet solution of the shortest-Route problem
The Excel sPreadsheet developed for the general transportation model (Section 5.3.3)
can be modified readily to find the shortest route between two nodes. Tkre spreadsheet
is based on Formulation 1, Section 6.3.3,and is designed for problems with a maximum
of 10 nodes. Figure 6.26 shows the application of the spreadsheet to Example 6.3_4 (fi|e
ch6SolverShortestRoute.xls).Th" distance matrix resides in cells B6:K15.3 An infinite
distance (: 9999,or any relatively large value) is entered for nonexisting arcs. Because
We are seeking the shortest route between nodes 1 and Z,the supply amount for node 1
and the demand amount for node 2 is I unit. A zero amount is eňtered for the remain_
ing supply and demand entries.
3In Figure 6.26, rows 11 through 15 and column K are hidden to conserve space.
4-54-23-5z-J1-3
238 Chapter 6 Network Models
FlGURE 6.26
Excel solver solution of the shortest route
between nodes 1, and2 in Example 6.3-4
#,t
iq;
di?
;];
iď"3
l*s
1,,]!
: N2
|:l1 l]l]
1l : lll
!!:l|
lJ: Nl
l,ii . lr3
|ll l:]i
]']!: N!
[l3. Nl
!]: |]?
!t: l!.'1
lll , N5
li+ .'tlt
tll .'1,1;
|il : lll
|F . ll!
ry! |l1
|,l5- l.i;
N5 " l,]j
lls. tu
r,l1
nll
l{f
r,l+
|,]5
Once the unit cost and supply/demand data are entered, the remainder of the
spreadshe et (intermediate calculations and optimum solution sections) is generated
automatically. Solver parameters must correspond to the input data of the problem as
shown in highlighted columns B, C, F, and G. Column B specifies the changing cells
(arcs flow) of the problem (cells B2O:B39). Column C specifies the capacities of the
arcs of the network (cells C2O:C39). In the shortest-route model, these capacities do
not play a role in the computations and hence are infinite (:999199). The constraints of
the model represent the balance equation for each node. Cells F1,9:F23 define the lefthand
side and cells G].9:G23 represent the right-hand side of the flow equations. As
explained in Section 5.3.3,SUMIF is used to generate the proper net flow in each node
using the information in columns I and J. These calculations are automated by the
t-_
6.4 Maximal Flow Model 239
spreadsheet. Thus, all you need to do after entering the input data is to update
Changing Cells and Constraints specifications of Solver to match the input data. The
Tbrget Cell remains the same for all input data.In Example 6.3-4,we have
Changing Ce]fs: 82O:839
Constraints: FI9:.F23=Gl9 : G23
The output in Figure 6.26 yields the solution (Nl-N3 : 1, N3-N4 :
N4-I{2 : 1) with a total distance of 55 miles. This means that the optimal route
].+3-->4+2.
PRoBLEM sET 6.3E
1. Modify spreadsheet ch6SolverShortestRoute.xls (applied to Example 6.3-4) to find the
shortest route between the following pairs of nodes:
(a) Node 1 to node 5
(b) Node 4 to node 3
2. Adapt spreadsheet ch6SolverShortestRoute.xls for Problem 2, Set 6.3a,to find the shortest
routes between node 4 and node 7.
MAX|MAL FLOW MODEL
Consider a network of pipelines that transports crude oil from oil wells to refineries.
Intermediate booster and pumping stations are installed at appropriate design distances
to move the crude in the network. Each pipe segment has a finite maximum rate
of crude flow (or capacity). A pipe segment may be unidirectional or bidirectional,
depending on its design. A unidirectional segment has a finite capacity in one direction
and a zero capacity in the opposite direction. Figure 6.27 demonstrates a typical pipeline
network. How can we determine the maximum capacity of the network between
the wells and the refineries?
The solution of the proposed problem requires converting the network into one
with a single source and a single sink. This requirement can be accomplished by using
unidirectional infinite capacity arcs as shown by dashed arcs in Figure 6.27.
FlGURE 6.27
Capacitated network connecting wells and
refineries through booster stations
Wells Boosters
I,
is
:.r of the
l_ nerated
: _,blem as
::ng cells
r.s of the
..-ities do
,:raints of
= the left,:ions.
As
-:ch node
.J by the
6.4
Source (-f 1 Sink
I
I
fine
l\
I
i*"
I
I
I
I
I
I
l
I
|\|
,/,
I
I
I
I
l
I
I
L_
)
ries
240 Chapter 6 Network Models
Given arc
capacities in the
place Č4on the
6.28.
(i 7) with i < j, we use the notation (č,i,e,s to represent the flow
two directions i _+ jand 7 + l, respectively.To eliminate ambiguity, we
arc next to node l with e 1iplaced next to node 7, as shown in Figure
F|GURE 6.28 r_,,Cti Cii r->
ArcflowsCuíroml--+i and Č,,fromi--+i re
6.4.1 Enumeration of Cuts
A cut defines a set of arcs which when deleted from the network will cause a complete
disruption of flow between the source and sink nodes. The cut caPacitY equals the sum
of the capacities of the associated arcs. Among a// possible cuts in the network, the cut
with the imallest capacity gives the maximum flow in the network,
Example 6.4,1
Consider the network in Figure 6.29.
respective arcs using the convention in
limlt is ].0 units from 3 to 4 and 5 units
FlGURE 6.29
Examples of cuts in flow networks
The bidirectional capacities
Figure 6.28.For example, for
from 4to3.
are shown on the
arc (3,4), the flow
Figure 6.29 illustrates three cuts whose capacities are computed in the following
table.
Associated arcs CapacityCut
1
2
J
(1,,2), (I,3), (1,,4)
(1, 3), (]", 4), (z, 3), (2, 5)
(z,5),(3,5), (4,5)
z0+30+10:60
30+10+40+30:110
30+z0+20:70
l
l
l
l
_: i-lů,,,.
,-l
1I, j
- ": LrI !
,mplete
ňe sum
, the cut
on the
the flow
ollowing
6.4 Maximal Flow Model 241
We cannot tell what the maximal flow in the network is unless we exhaustively
enumerate all possible cuts. The only piece of information we can get from the partial
enumeration of three cuts is that the maximum flow in the network cannot exceed 60
units. Unfortunately, exhaustive enumeration of all cuts is not a simple task, thus making
it necessary to develop the efficient algorithm in Section 6.4.2.
PRoBLEM sET 6.4A
1. For the network in Figure 6.29,determine two additional cuts, and find their capacities.
6.4.2 Maxima! Flow Algorithm
The maximal flow algorithm is based on finding breakthrough paths with net positive
flow between the source and sink nodes. Each path commits part or all the capacities
of its arcs to the total flow in the network.
Consider arc (i,7) with (initial) capacities G,1, e ,S.As portions of these capacities
are committed to the flow in the arc, the residuals (or remaining capacities) of the arc
are updated. The network with the updated residuals is referred to as the residue network.
We use the notation (c4, cl)to represent these residuals.
For a node jthat receives flow from node l, we define a label Ioi, if,where a, is the
flow from node l to node 7. The steps of the algorithm are summarized as follows.
Step 1. For all arcs (i i), set the residuaI capaciíy equal to the initial capacity-that is
(c,i, ci : eCii, e,S.ret o1 : @ and label source node ]. with [*, -].Set i : 1,
and go to step 2.
Step 2. Determine ,S, as the set of unlabeled nodes jthat can be reached directly
from node l by arcs with positive residuals (that is, cu ) 0 for aII j e l). If
Si + g,go to step 3. Otherwise, go to step 4.
Step 3. Determine k e S; such that
cik : mqx {c,i}
,/eJi
Set a6 : cik and label node k with foo, i].If. k : n,the sink node has been
labeled, and a breakthrough path is found, go to step 5. Otherwise, set i : k,
and go to step 2.
Step 4. (Backtracking). If i : 1, no further breakthroughs are possible;go to step
6. Otherwise,let r be the node that has been labeled immediately before the
current node i and remove i from the set of nodes that are adjacent to r. Set
i : r,and go to step 2.
Step 5. (Determination of Residue Network). Let l/o : (I, kr, kr,..., n)define the
nodes of thepth breakthrough path from source node ]_ to sink node n.Then
the maximum flow along the path is computed as
Ío : min {a1, ak,, akr,... , ar}
The residual capacity of each arc along the breakthrough path ísdecreasedby
íoin the direction of the flow and increasedby ío in the reverse
z42 Chapter 6 Network Models
direction-that is, for nodes l andi on the path, the residual flow is changed
from the current(ci1, c,)to
(a) (r,i - f, cli + ír) if the flow is from i to j
(b) (r,i * fp, cli - ír) if the flow is from j to i
Reinstate any nodes that were removed in step 4. Set i : I, and return to
step 2 to attempt a new breakthrough path.
(Solution)
(a) Given that m breakthrough paths have been determined, the maximal
flow in the network is
F:fr+fz+ +í(b)
Given that the initial and final residuals of arc (i, j) arc given by (e a, Č)
and(c;1,, c7), respectively, the optimal flow in arc (l, i) is computed as follows:
Let (a, B) : (eu - gii,e
,, - c,).If ct ) 0, the optimal flow from l
toi is cr. Otherwise, if B > 0, the optimal flow from jto i is B. (It is
impossible to have both ct and B positive.)
The backtracking process of step 4 is invoked when the algorithm
becomes inadvertently "dead-ended" at an intermediate node before a
breakthrough can be realized. The flow adjustment in step 5 can be
explained via the simple flow network in Figure 6.30. Network (a) gives the
first breakthrough path iy't : {I, 2, 3, 4} with its maximum flow /, : 5.
Thus, the residuals of each of arcs (I,2),(2,3),and (3,4) are changed from
(5,0) to (0,5), per step 5. Network (b) now gives the second breakthrough
path A/2 : {1, 3, Z, 4} with f, : 5. After making the necessary flow adjustments,
we get network (c), where no further breakthroughs are possible.
What happened in the transition from (b) to (c) is nothing but a cancellation
of a previously committed flow in the direction 2 -->3.The algorithm is able
to "remember" that a flow from 2 to 3 has been committed previously only
because we have increased the capacity in the reverse direction from 0 to 5
(per step 5).
Step 6.
[5, 1]
[*, -] [-, -]
í5,2)
Path:I-+2-+3-+4, fi:5
(u)
FlGURE 6.30
use of residual to calculate maximum flow
[5,3]
[5, 1]
Path:1+3-+2-+4, íz:5
(b)
2]
No breakthrough
(")
1\
\
\5
5
0
0
0
\- l4
,/-'
,1
,
J
U
r-
6,4 Maximal Flow Model 243
Example 6,4-2
Determine the maximal flow in the network of Example 6.4-I (Figure 6,29). Figure
6.31 Provides a graphical summary of the iterations of the algoriihm. you will find it
helPful to compare the description of the iterations with the gňphical summary.
. . e,_.}
t_s folrom
l
i
I
s the
'.
)m
gh
iust-
e.
[ation
;able
onl},
to5
[-, -] [*, -]
[*, -] [30,2] [*, -]
(c) h:
[10, 1]
[-, -] [10,4]
FlGURE 6.31
Iterations of the maximum flow algorithm of Example 6.4-2
I20,3) íz0,4]
í20,2)
0\
10
[10,3]
0
30 10
(d)á: 10
400
(f) No breakthrough
244 Chapter 6 Network Models
Iúeration 1. Set the initial residuals (ci1, c1) equal to the initial capacities (e 11, e ).
Step 1_. Set a1 : oo and label node ]. with [*, -].Set
l : 1.
Step 2. & : {2,3, 4}e q.
Step3. k:3 because c13: max{c2, cB, cu) : max{20,30, 10} = 30.Set
a3 : cI3: 30, and label node 3 with [30,1]. Set l : 3, and repeat step2.
Step 2. 53 : (4, 5).
Step 3. k : 5 and a5 : c35: max{10,20} : 20. Label node 5 with í20,3].
Breakthrough is achieved. Go to step 5.
Step 5. Breakthrough path is determined from the labels starting at node 5 and ending
at node ].-that is, (5) -+ |20, 3] + (3) * [30, 1] -+ (1).Thus, N1 : {1, 3, 5}
and f1 : min{a1, a3,, a5} : { oo , 30,20} : 20.The residual capacities along
path N1 are
(cB, cst) : (30 - 20,0 + 20) : (10, 20)
(czs, csz) : (Z0 - 20,0 + 20) : (0, 20)
Iteration 2.
Step 1. Set a1 : Ň, and label node ]. with [-, -].Set
l : ]..
Step 2. Sr : {Z, 3, 4}.
Step 3. k : 2 and a2 : clz : max{20, 10, 10} : 20.Set i : 2, andrepeat step 2.
Step 2. Sz : {3, 5}.
Step 3. k : 3 and a3 : c23 : 40.Labe1 node 3 with |40,2].Set l : 3, and repeat
step 2.
Step 2. S: : {4} (note that ca5 : 0-hence, node 5 cannot be included in,S3).
Step3. k : 4 and aa : c34 : 10.Labelnode4with [10,3].Setl : 4,andrepeat
step2.
Step 2. S+ : {5} (note that nodes 1 and 3 are already,labeled-hence, they cannot be
included in,Sa).
Step 3. k : 5 and a5 : c45 : 20. Label node 5 with |20,4]. Breakthrough has been
achieved. Go to step 5.
Step 5. Nz : íI,2, 3, 4, 5) and f2 : min {oo, 20, 40, 10, 20} : ].0. The residuals
along the path of i/2 are
(co, czt) : (20 (rrr,
,rr) : (40 (czq,
c+z) : (10 (cr,
csl) : Q0 ]_0,0+10)
:(10, 10)
10,0 + 10): (30, 10)
].0,5+10) :(0, 15)
10,0+10) :(10,]_0)
Iteration 3.
Step 1. Set a1 : oo and label node 1 with [*, -].Set
i : ]_.
Step 2. St : {2, 3, 4}.
Step 3. k : 2 and a2 : cl2 : max{10, 10, 10} : ].0 (though ties are broken arbitrarily,TORA
always selects the tied node with the smallest index;we will
6.4 Maximal Flow Model 245
use this convention throughout the example). Label node 2 with [10,1]. Set
i : 2, and repeat step 2.
Step 2. ,S2 : {3, 5}.
SteP3. k : 3 and a3 : c23: 30.Labelnode 3 with í30,2].Setl : 3,andrepeat
step 2.
Step 2. S: : a (becalso c34 : c35 - 0). Go to step 4 to backtrack.
teP 4. The label l39,Z] at node 3 gives the immediately preceding node r : 2.
Remove node 3 from further consideration in thtŠiterattoňby crossing it out.
Set i : ť: Z,,and repeatstepZ.
SteP 2. Sz : {5} (note that node 3 has been removed in the backtracking step).
SteP 3. k : 5 and a5 : c25: 30. Label node 5 with |30,2l.Breakthrough has been
achieved;go to step 5.
SteP 5. N; : {I, 2,5} and c5 : min {oo, 10, 30} : ]-0. The residuals along the path
of A/3 are
(rrr, ,rr): (10 - ]_0, 10 + ]_0) : (0, 20)
(rrr, ,rr): (30 - ]_0, 0 + 10) : (20, 10)
Iteration 4. This iteration yields i/+ : {l, 3, 2, 5} with fo: 10 (verify!).
Iteration 5. This iteration yields AL : {1, 4, 5} with ís: L}(verify!).
Iteration 6. Al1 the arcs out of node 1 have zero residuals. Hence, no further break_
throughs are possible. We turn to step 6 to determine the solution.
Step6. Maximal flow in the network is F: ír+íz+ * fs:20 + {0 + 10+
]-0 + 10 : 60 units. The flow in the differeni árcs is computed by subtracting
the last residuals.(c;1, c) in iterations 6 from the initial capaciti"r (ču,Q),u.the following table shows.
Arc (eil,eli) - (ci1, c)a Flow amount Direction
(I,2) Q0,0) - (0, 20)
(1,3) (30, 0) - (0, 30)
(I,4) (10,0) - (0, 10)
(2,3) (40, 0) - (40, 0)
(2,5) (30, 0) - (10, 20)
(3,4) (10, 5) - (0, 15)
(3,5) (20, 0) - (0, 20)
(4,5) (20, 0) - (0,20)
you can use ToRA to solve the maximum flow model in an automated mode
or to Produce the iterations outlined above. From the solvn/MoDlF.y menu select
Solve Problem. After sPecifying the output format, go to output screen and select
either Maximum Flows of Tterations. Figure 6.32 illustrates the first two iterations of
Ex ample 6 . 4 -2 (file ch 6ToraM axFlo wEx6 - 4 -2. txt ).
: 1z0, -20)
: (30, -30)
: (10, -10)
: (0, 0)
: (20, -20)
: (10, -10)
: Q0, -20)
: (20, -20)
20
30
10
0
20
10
20
20
I _>2
1-+3
1--+4
2--+5
3-->4
3-+5
4_>5
246 Chapter 6 Network Models
FlGURE 6.32
TORAs maximum flow iterations for ExampIe 6,4-2
PRoBLEM sET 6.48
1. In Example 6-4-2,
(a) Determine the surplus capacities for all the arcs,
(b) Determine the amount of flow through nodes 2,3,and 4.
(c) Can the network flow be increased by increasing the capacities in the directions
3+5 and4-+5?
Determine the maximal flow and the optimum flow in each arc for the network in Figure
6.33.
Three refineries send a gasoline product to two distribution terminals through a PiPeline
network. Any demand that cannot be satisfied through the network is acquired from
other sources.The pipeline network is served by three pumping stations as shown in
Figure 6.34.The próduct flows in the network in the direction shown bY the arrows.The
calpacity of each pipe segment (shown directly on the arcs) is in million bbl Per daY,
Determine the following:
(a) The daily production at each refinery that matches the maximum caPacitY of the
network.
The daily demand at each terminal that matches the maximum capacity of the net_
work.
The daily capacity of each pump that matches the maximum capacity of the network,
(b)
(c)
6.4 Maximal Flow Model 247
FlGURE 6.33
Network for Problem 2. Set 6.4b
Pumping stations ., Terminals
FlGURE 6.34
Network for Problem 3" Set 6.4b
SuPPose that the maximum daily capacity of pump 6 in the network of Figure 6.34 is limited
to 60 million bbl per day. Remodel the netwoik to include this restriction. Then
determine the maximum capacity of the network.
Chicken feed is transported by trucks from three silos to four chicken farms. Some of the
silos cannot shiP directly to some of the farms. The capacities of the other routes are limited
by the number of trucks available and the number of trips made daily. The following
table shows the dailY amounts of supply at the silos and demand at the t*-. (in thousands
of Pounds).The cell entries of the table specify the daily capacities of the associated
routes.
, _jl
Farm
I
Silo 2
J
20
20
200
20
30 5 0 40
0 0 5 90
100 40 30 40
Chapter 6 Network Models
(a) Determine the schedule that satisfies the most demand.
(b) Will the proposed schedule satisfy all the demand at the farms?
6. In Problem 5, suppose that transshipping is allowed between silos 1 and2 and silos 2 and
3. Suppose also that transshipping is allowed between farms 1 and 2,2 and 3, and 3 and 4.
The maximum two-way daily capacity on the proposed transshipping routes is 50 (thousand)
lb. What is the effect of transshipping on the unsatisfied demands at the farms?
7. Aparent has five (teenage) children and five household chores to assign to them. Past
experience has shown that forcing chores on a child is counterproductive. With this in
mind, the children are asked to list their preferences among the five chores, as the following
table shows:
child preferred chore
3,4,or 5
1
lorZ
7,2,or 5
2
The parent's modest goal now is to finish as many chores as possible while abiding by
the children's preferences. Determine the maximum number of chores that can be completed
and the assignment of chores to children.
Four factories are engaged in the production of four types of toys. The following table
lists the toys that can be produced by each factory.
Factory Toy productions mix
Rif
Mai
Ben
Kim
Ken
1
z
J
4
1,,2,3
)?-) "
I,4
3,4
All toys require the same per unit labor and material. The daily capacities of the four
factories are 250,180, 300, and 100 toys, respectively. The daily demands for the four toys
arc200,150,350, and ].00 units, respectively. Determine the production schedules that will
most satisfy the demands for the four toys.
The academic council at the U of A is seeking representation from among six students
who are affiliated with four honor societies. The academic council representation includes
three areas: mathematics, art, and engineering. At most two students in each area can be
on the council.The following table shows the membership of the six students in the four
honor societies:
Society Affiliated students
1
2
J
4
1,,2,3
1,,3,5
3,4,5
1,,2,4,6
The students who are skilled in the areas of mathematics, art, and engineering are
shown in the following table:
E-.
6.4 Maximal Flow Model 249
skilled students
all,l
rd+
íxF
)
Mathematics
Art
Engineering
t,2,4
3,4
4,5,6
s
L
lh-n- 10.
A student who is skilled in more than one area must be assigned exclusively to one
area only. Can all four honor societies be represented on the council?
Maximal/Minimal Flow in Networks with Lower Bounds. The maximal flow algorithm
given in this section assumes that all the arcs have zero lower bounds.In some models, the
lower bounds may be strictly positive, and we may be interested in finding the maximal or
minimal flow in the network (see Comprehensive Problem 6-3).The pr"rérr." of the
lower bound Poses difficulty because the network may not have a feaiible flow at all.The
objective of this exercise is to show that any maximal and minimal flow model with posi_
tive lower bounds can be solved using two steps.
SteP 1. Find an initial feasible solution for the network with positive lower bounds.
SteP 2. Using the feasible solution in step 1, find the maximal or minimal flow in the
original network.
(a) Show that an arc (i,7) with flow limitedby t;, š xij
= uijcaíbe represented equivalentlY
bY a sink with demand l,,at node i and a source with supply t,,utnodei with
flow limited by 0 = x',j - uij - lii.
(b) Show that finding a feasible solution for the original network is equivalent to finding
the maximal flow xrinthe network after (1) modifying the bounds on xu to
0 = x',, = Ltii t,i,(2) 'olumping" all the resulting rórr.". into one supersource with
outgoing arc caPacíties li1, (3) "lumping" all the resulting sinks into one supersink
with incoming arc capacities I,1,and (4) connecting the terminal node / to the source
node s in the original network by a return infinite capacity arc. A feasible solution
exists if the maximal flow in the new network equals the sum of the lower bounds in
the original network.Apply the procedure to the following network and find a feasi_
ble flow solution:
Arc (i, j) (l,i, u,i)
(5,20)
(0,15)
(4,10)
(3,15)
(0,20)
Use the feasible solution for the network in (b) together with the maximal flow algo_
rithm to determine the minimal flow in the original network. (Hint: First compute the
residue network given the initial feasible solution. Next, determine the maximum
flow from the end node to the start node. This is equivalent to finding the maximum
flow that should be canceled from the start node to the end node. No*, combining the
feasible and maximal flow solutions yields the minimal flow in the original network.)
Use the feasible solution for the network in (b) together with the maximal flow
model to determine the maximal flow in the original network. (Hint:As in part [c],
start with the residue network. Next apply the breakthrough algorithm to the result_
ing residue network exactly as in the regular maximal flowmoJel.)
(I,2)
(1,3)
(2,3)
(2,4)
(3,4)
(c)
(d)
250 Chapter 6 Network Models
6.4,3 Linear Programming Formulation of the Maximum Flow Model
Define xiias the amount of flow in arc (i,7) and let cilbe the capacity of the same arc.
Assume that s and t are the start and terminal nodes between which we need to determine
the maximum flow in the capacitated network.
The constraints of the problem preserve the in-out flow at each node, with the
exception of start and terminal nodes. The objective function maximizes either the
total"out" flow from start node s or the total "in" flow to terminal node r.
Example 6,4-3
In the maximum flow model of Figure 6.29 (Example 6.4-2),s : ]- and t : 5. The following
table summarizes the associated LP with two different objective functions
depending on whether we are maximizingthe output from node 1 (:er)or the input to
node 5 (:zr).
X:sXzsXn
Maximize z1 :
Maximize z2:
Node 2
Node 3
Node 4
-I
1
-1 -0
-0
:0
-1
I
1
-1
-1
-I
Capacity 1010
The optimal solution using either objective function is
X12 : 20, X3: 30, XI4 : I0, X25 : 20, X34 : I0, 45 : 20, Xa5 : 20
The associated maximum flow is Z1, : Zz: 60.
PRoBLEM sET 6.4c
1. Rework Problem 2, Set 6.4b using linear programming.
2. Rework Problem 5, Set 6.4b using linear programming.
6.4.4 Excel Spreadsheet Solution of the Maximum Flow Model
The network-based Excel spreadsheet developed for the transportation model
(Section 5.3.3) is modified to determine the maximum flow in a capacitated network.
The spreadsheet is designed for problems with a maximum of ].0 nodes. Figure 6.35
shows the application of the spreadsheet to Example 6.4-2 (file ch6SolverMax
Flow.xls).The capacity flow matrix resides in cells B6:K15.aA blank cell in the capacity
matrix indicates that the associated arc has infinite capacity. A zerc entry corresponds
to a nonexisting flow arc. Otherwise, all the remaining arcs must have finite capacities.
Once the flow capacity data have been entered, the remainder of the spreadsheet
(intermediate calculations and optimum solution sections) is created automatically. A11
aln Figure 6.35, rows 11 through 16 and column K are hidden to conserve space.
l-
3
ťxp*ci"*y SŤ+lrix
x-iii#[#ffi
1']
_1_]
6,4 Maximal Flow Model 251
FlGURE 6.35
Excel solver solution of the maximum flow
model of Example 6.4-2
lr0 l l:I
that is needed now iS to uPdate Solver parameters to match the input data. Column BsPecifies the changing cells (arcs
{lo*) of the problem. rhe ,ang" ro. Changing Cellsmust encomPass all the arcs specified in column A (make ,u." tt"ui you give each nodea name in the inPut data matrix, else column A witi only show a hyphen in the associ_ated cells), In the Present example, cells B2O:B39 p;"rtd; Črrangingcett, range.Column C sPecifies the capacities of the arcs of the network (cells C2O:C39).
The constraints of the model represent the flow balance equutio1 for each node.The LP formulation in Section 6.4.3 shows that it is not n"..rrury to construct flowequations for the first and last nodes of the network (nodes 1 and 5 in Figure 6.35).Thus, cells F2O:F22 define the left-hand side and cells G20 :G22 represent the right_hand side of the flow equations.
-- 1,1]-hl
,ž |,,it_ F]J
:E: l'l2 li4
N2_ l!5
lrlj : li t
1,1
: lll
]i l',l3 - l,r4
:i- l,,Jj l!5
a: l,]4 - l,]1
Fl4 1,1!
252 Chapter 5 Network Models
Based on given information, Solver parameters for the examPle in Figure 6.26
are entered as
Changing Ceffs: 820 :839
Constraints: 820 :B3 9<=C20 :C39 (Arc capacíty)
F2O:F22=G2a:G22 (Flow equations for nodes 2, 3, and 4)
Note that Target Cell is automated and need not be changed. The Equal to Parameter
is Max because this is a maximizatiolproblem,
The output in Figure 6.35 yields the solution (Nl-N2 : 20,, Nl-N3 : 30,
Nl_N4 : 10, N2-N5 : iO,N3-N4 : 10, N3-N5 :20, N4-I{5 :}})withamaximum
flow of 60 units.
PRoBLEM sET 6.4D
1. Solve Problem 2, Set 6.4b using Excel Solver,
2. Solve Problem 5, Set 6.4b using Excel Solver,
6,5 MlNlMUM-cosT CAPAC|TATED FLoW PRoBLEM
The minimum-cost capacitated flow problem is based on the following assumPtions:
1_. A (nonnegative) unit flow cost is associated with each arc.
2. Arcs may have positive lower capacity limits,
3. Any node in the network may act as a source or as a sink.
The new model determines the flows in the different arcs that minimize the total
cost while satisfying the flow restrictions on the arcs and the suPPlY and demand
amounts at the ,rod"r. We first present the capacitated network flow model and its
equivalent linear programming formulation. The linear programming formulation is
the basis for the development of a special capacitated simplex algorithm for solving
the network flow model. The section ends with a presentation of a spreadsheet template
of the minimum-cost capacítated network.
6.5.1 Network Representation
Consider a capacitated network G : (N, Á), where N is the set of nodes, and A is the
set of arcs and define
yii : amount of flow from node l to node i
u;1(la) : upper (lower) capacity of arc (l, 7)
cu : unit flow cost from node l to node i
f,: netflow at node l
Figure 6.36 depicts these definitions on arc (i, j).The label ffi] assumes a positive
(negative) value when a net supply (demand) is associated with node l.
__ a L,,-l ,
..
: jmeter
,,: : 30.
.rimum
] . . t]IIS]
lthe total
. dernand
rl and its
ulation is
lr solving
heet tem-
dÁisthe
., positive
6.5 Minimum-Cost Capacitated Flow Problem
FlGURE 6,36
Capacitated arc with external flow
Example 6.5-1
GrainCo suPPlies corn from three,silos to three poultry farms. The supply amounts at
the three silos are 100, 200, and 50 thousand bushehj and the deman-d-at the three
farms is 150,80, and ].20 thousand bushels. GrainCo mostly uses railroads to transport
the corn to the farms, with the exception of three routes *ň.r" trucks are used.
Figure 6.37 shows the available route between the silos and the farms. The silos are
rePresentqO
9y nodes I, 2, and 3 who_se supply amounts are [100] ,, L200], and [50],
resP_ectivelY. The farms are represented by nodes 4,5, and,6 whbse o"r"uňo amounts
a.re [-150], [-9O],. and_|-,I}O], respectively. The routes allow transshipping between
the silos. Arcs (I,4), (3,,4), and (4,6) are iruck routes with minimum anO maximum
caPacities. For example, the capacity of route (I, 4) is between 50 and 80 thousand
bushels. Al1 other routes use trainloads, whose maximum capacity is practically unlim_
ited. The transportation costs per bushel are indicated on thó respective arcs.
[- 150] FlGURE 6.37
Capacitated network for Example 6.5-1[100]
[- 120]
[200]
PRoBLEM sET 6.5A
1. A Product is manufactured to satisfy demand over a 4-period planning horizon according
to the following data:
Period units of demand Unit production cost ($) Unit holding cost ($)
1
2
J
4
Given that no back-ordering is allowed, represent the problem as a network model.
In Problem 1, suppose that back-ordering is allowed at a penalty of $1.50 per unit per
period. Formulate the problem as a network model.
t
$g
100
110
95
125
1
z
1
2
24
26
2I
24
1
í
V,/ (100, 120i
(70,I20)
--y5)
s6\
50]
J
|\
|:
|_-
[-80]
Iíi] ó |,íi]
a\ o C,l /-\
W xtj
6
254 Chapter 6 Network Models
In Problem 1, suppose that the production capacities of periods 1, to 4 are ]_10, 95,I25,and
].00 units, respectively, in which case the given demand cannot be satisfied without backordering.
Assuming that the penalty cost for back-ordering is $1.50 per unit per period,
formulate the problem as a network model.
Daw Chemical owns two plants that manufacture a basic chemical compound for two
customers at the rate of 660 and 800 tons per month. The monthly production capacity of
plant ]. is between 400 and 800 tons and that of plant 2 is between 450 and 900 tons.The
production costs per ton in plants ]. and Z are $25 and $28, respectively. Raw material for
the plants is provided by two suppliers, who are contracted to ship at least 500 and 700
tons per month for plants 1 and 2 atthe costs of $200 and $210 per ton, respectively. Daw
Chemical also assumes the transportation cost of both the raw material and the final
compound. The costs per ton of transporting the raw material from supplier 1 to plants 1
and} are $10 and $12.Similar costs from supplier 2 are $9 and $13, respectively.The
transportation costs per ton from plant ]. to clients 1 and 2 are§3 and $4, and from plant2
costs are $5 and $2, respectively. Assuming that ]. ton of raw material produces 1 ton of
the final compound, formulate the problem as a network model.
Two nonintegrated public schools are required to change the racial balance of their
enrollments by accepting minority students. Minority enrollment must be between30o/"
and 40"/" in both schools. Nonminority students live in two communities, and minority
students live in three other communities. Traveled distances, in miles, from the five communities
to the two schools are summarized in the following table:
Round-trip miles from school to
Minority areas Nonminority areas
Maximum
school enrollment
3.
4.
1 1500
2 2000
Student population
20 12 10
15188
500 450 300
45
65
1000 1000
Formulate the problem as a network model to determine the number of minority
and nonminority students enrolled in each school.
6.5.2 Linear Programming Formulation
The formulation of the capacitated network model as a linear program provides the
foundation for the development of the capacitated simplex algorithm, which we will
present in the next section. Using the notation introduced in Section 6.5.1, the linear
program for the capacitated network is given as
Minimize z: >2r, ,,
(i. j)eA
subject to
)r,o- )*,,
:íi,jeN
(j, k)eA (i, j)eA
l,j =x,j ''4ii
1_ ',,'L
} _.lg
l _:_ Ir]r
Tl,,,,_. ll
__- ]
_: _-> -L
_,_,-_lL
]-
_l
:- ifl-
6.5 Minimum-Cost Capacitated Flow Problem 255
The equation for nodei measures the net flow fr in nodei as
(Outgoing flow from node 7) - (Incoming flow into node j) : íi
Nodei acts as a sourceif íj) 0 and as a sink iífj < 0.
We can always remove the lower bound l,,from the constraints by using the sub-
stitution
aii :x'i1 *li1
The new flow variable, x',,,has an upper limit oí u,, - /ť. Additionally, the net flow
at node l becomes Íi- 1,1, and that at node j i, íi+ /r. Figure 6.38 shows the transformation
of activity (i, j) after the lower bound is substituted out.
V + lii] FlGURE 6.38
Removal of the lower bound in arcs
Example 6.5-2
Write the linear program for the network in Figure 6.37, before and after the lower
bounds are substituted out.
The main constraints of the linear program relate the input-output flow at each
node, which yields the following LP:
XsaJ:_sXlnXzsXzzXtlXnXp.
Minimize
ides the
x-e will
le linear
Node 1
Node 2
Node 3
Node 4
Node 5
Node 6
Lower bounds
Upper bounds
1,
-1
: 100
: 200
:50
:-150
: -80
:-I20
-1
1
-1
0
oo
1
-1,
-1-1 I
-1
0
oo
-1
0 100
oo I20
070
oo IZ0
050
oo B0
0
oo
Note the arrangement of the constraints coefficients. The column associated with
variabfe xu has exactly one +1 in row i and one -1 in row7. The rest of the coefficients
are 0. This structure is typical of network flow models.
The variables with lower bounds are substituted as
XI4: x'y t 50
x34 : x|a -| 70
x46: y|ou + I00
256 Chapter 6 Network Models
The resulting linear program is
XsaXqsJ:sXzqXzsXzsx,,XrXn
Minimize
Node ],
Node 2
Node 3
Node 4
Node 5
Node 6
Upper bounds
I
-1 1
-1
oo
-1 1
-1
50
1
-1
20
:50
z00
: -20
: -]_30
1 :-80
-1, : -20
oo
-1
-1
The corresponding network after substituting out the lower bounds is shown in
Figure 6.39. Note that the lower-bound substitution can be effected directly from
Figure 6.37 using the substitution in Figure 6.38, and without the need to express the
problem as a linear program first.
-1
FlGURE 6.39
Network of Example 6.5-2 after [50]
substituting out lower bounds
[- 130]
$t
$
[200] t
|-20]
I
1, 4
J
$z
20)
6
x .Y5
[-80]
Example 6.5-3 (Employment Scheduling)
This example illustrates a network model that initially does not satisfy the "node flow,,
requirement (i.e.., node output flow less node input flow equals node ňet flow), but that
can be converted to this form readily through special maňipulation of the cónstraints
of the linear program.
T-Po EmPloyment Agency has a contract to provide workers over the next 4
months (January to April) according to the following schedule:
Month Jan. Mar. Apr.
No. of workers 100 I20 17080
Because of change in demand, it may be economical to retain
n9e_de.d in a given month. The cost of recruiting and maintaining a
of their employment period as the following table shows:
more workers than
worker is a function
Employment period (months)
Cost per worker ($) 130100 180 z20
\
Yl
6.5 Minimum-Cost Capacitated Flow Problem 257
Let
y,ii : number of workers hired at the start of month i and terminated at the
start of monthi
For example, xp gives the number of workers hired in January for ]. month only.
To formulate the problem as a linear program for the 4-month period, we add May
as a dummy month (month 5), so that xa5 defines hiring in April for April. The constraints
recognize that the demand for period k can be satisfied by aI| xilsuch that
i < k < i. Letting ; > 0 be the surplus number of workers in month l, the linear program
is given as
.",j,2,1-tl <J:sXl,XzsXzqXr Xt+ Xzl
Minimize 100 130 180 220 100 130 180 100 130 100
Jan.
Feb,
Mar.
Apr.
-1 :100
:l20
:80
-1 :170
-1
-1
=
ilorr"'
]:]t that
i::aints
:ext 4
The preceding LP does not have the (-1, +1) special structure of the network
flow model (see Example 6.5-2). Nevertheless, the given linear program can be converted
into an equivalent network flow model by using the following arithmetic
manipulations:
In an n-equation linear program, create a new equation, n l I, by multiplying
equation nby -1,.
Leave equation 1 unchanged.
For l : 2, 3, ..., ft,replace each equation l with (equation i) - (equation i - 1).
The application of these manipulations to the employment scheduling example
yields the following linear program whose structure fits the network flow model:
Xn Xn Xt,l Xs Xzl Xzq Xu
1.
.,
3.
.3S2S1X+s
Minimize 100 130 180 2Z0 100 130 180 100 130 100
Jan.
Feb.
Mar.
Apr.
May
1
-1 I
-1-t 1
-1
-1
1 -1
1 -1
11-I
-1 1
: 100
:Z0
: _40
90
:-I70-:S than
'*nction
-1-t
-1-1-I
Using the preceding formulation, the employment scheduling model can be represented
equivalently by the minimum-cost flow network shown in Figure 6.40.Actually,
because the arcs have no upper bounds, the problem can be solved also as a transshipment
model (see Section 5.5).
_
258 Chapter 6 Network Models
FlGURE 6.40
Network representation
of employment scheduling
problem
PRoBLEM sET 6,58
1. Write the linear program associated with the minimum-cost flow network in Figure 6.41,
before and after the lower bounds are substituted out.
F|GURE 6.41 [50]
Network for Problem ]., Set 6.5b
íz0]
[-40]
(10, oo; [-30](0,
)
3.
4.
Use inspection to find a feasible solution to the minimum-cost network model of the
employment scheduling problem in Example 6.5-3 (Figure 6.40).Interpret the solution by
showing the pattern of hiring and firing that satisfies the demand for each month, and
compute the associated total cost.
Reformulate the employment scheduling model of Example 6.5-3,assuming that a
worker must be hired for at least2 months.Write the linear program, and convert it to a
minimum-cost flow network.
Develop the linear program and the associated minimum-cost flow network for the
employment scheduling model of Example 6.5-3 using the following S-month demand
data. The per worker costs of recruiting and maintaining a worker for periods of ]. to 5
months are $50, $70, $85, $100, and $130, respectively.
(a)
Month 1, 2
No. of workers t70180
(b)
Month
No. of workers 240300
xzz [-40]
200
^
,,
6.5 Minimum-Cost Capacitated Flow Problem 25g
Conversion of a Capacitated Network into an Uncapacitated Network. Show that an arc
(' -+l) with capacitated flow x,7 3 urjcznbe replaced with two uncapacitated arcs (i -+ k)
and (7 + k) with a net (output) flow of |-ui] at node k and.an additional (input) no* oí
[+u,,] at node 7. The result is that the capacitated network can be converted to an
uncapacitated ttansportation cost model (Section 5.1). Apply the resulting transformation
to the network in Figure 6.42 andfind the optimum solution to the original network by
applying TORA to the uncapacitated transportation model.
z
4
FlGURE 6.42
Network for Problem 5, Set 6.5b
[100] [- 100]
nre 6.41,
:.re
_-:ion br
.. _,nd
.--.
:,.:toa
_--
--. . _ l
_1 11U
: _-, _i
6.5.3 Capacitated Network Simplex Algorithm
The algorithm is based on the exact steps of the regular simplex method, but designed
to exploit the special network structure of the minimum-cost flow model.
Given f is the net flow at node l as defined in the linear program of Section 6.5.2,
the capacitated simplex algorithm stipulates that the network must satisfy
ží,:o
í:1
The condition says that the total supply in the network equals the total demand.
We can always satisfy this requirement by adding a balancing dummy source or destination,
which We connect to all other nodes in the network by zero unit cost and infinite
caPacitY arcs. However, the balancing of the network does not guarantee a feasible
solution as this depends on the restrictin g capacities of the arcs.
We will now present the steps of the capacitated algorithm. Familiarity with the
simPlex method and duality theory (Chapters 3 and 4) is essential. Also, knowledge of
the upper-bounded simplex method (Section 7.3) is helpful.
SÚeP 0. Determine a starting basic feasible solution (set of arcs) for the network. Go
to step 1.
SteP 1. Determine an entering arc (variable) using the simplex method optimality
condition. If the solution is optimal, stop; otherwise, go to step 2.
SÚeP 2. Determine the leaving arc (variable) using the simplex method feasibility
condition. Determine the new solution, and then go to step 1.
An n-node network with zero net flow (i.e., fi + íz+ * í,:0) consists of
n - I indePendent constraint equations. Thus, an associated basic solution must
include n - I arcs. It can be proved that a basic solution always corresponds to a
spanning tree of the network (see Section 6.2).
260 Chapter 6 Network Models
The entering arc (step 1) is determined by computing z;1 - cri,the objective coefficients,
for all the current nonbasic arcs (i, j).If zl - cij
= 0 for all i and j, the current
basis is optimum. Otherwise, we select the nonbasic arc with the most positive zii - cii
to enter the basis.
The computation of objective coefficients is based on duality, exactly as we did
with the transportation model (see Section 5.3.4). Using the linear program defined in
Section 6.5.2,Iet wi be the dual variable associated with the constraint of node l; then
the dual problem (excluding the upper bounds) is given as
Maximize , : Ží,r,
subject to
i:I
wi - wj = ,,j, (i, j)eA
}ť; uflíestricted in sign, i : 1,, 2, .. . n
From the theory of linear programming, we have
wi - wi : crj, for basic arc(i, j)
Because the original linear program (Section 6.5.2) has one redundant constraint by
definition, we can assign an arbitrary value to one of the dual variables (compare with
the transportation algorithm, Section 5.3). For convenience, we will set w, :0. We
then solve the (basic) equations },t/, - wj : cilto determine the remaining dual values.
From Section 4.Z.3,Method 2,we know that the objective coefficient of nonbasic.r4 is
the difference between the left-hand side and the right-hand side of the dual associated
dual constraint-that is
Zij -Cij :Wi-Wi -C4
The only remaining detail is to show how the leaving variable is determined. We
do so by using a numeric example.
Example 6.5-4
A network of pipelines connects two water desalinization plants to two cities. The daily
supply amounts at the two plants are 40 and 50 million gallons, and the daily demand
amounts at cities 1 and 2 are 30 and 60 million gallons. Nodes 1 and 2 represent plants 1
andZ,and nodes 4 and 5 represent cities 1 and 2. Node 3 is a booster station between
the plants and the cities. The model is already balanced because the supply at nodes 1
and2 equals the demand at nodes 4 and 5. Figure 6.43 gives the associated network.
FlGURE 6.43
Network for Example 6.5-4
Unit cost
\
Arc capacity
$s
Plant 1 [40] [-30] City 1
|-60] City 2Plant 2 [50]
G$t
E-.
nint b1*
rre rrith
= 0. \\e
l l aluer
sic -r.. is
I associi:
J.tl.i\
- --. -,- j
- _ -_--l11u
_-:rLi! ^
_
-11 f :Ť]
- _ t, ! ! ]1
.. _ ]__ 1
'q-lJ} l
6,5 Minimum-Cost Capacitated Flow Problem 261
Iteration 0.
Step 0. Determination of a Starting Basic Feasible Solution: The starting feasible
spanning tree in Figure 6.44 (shown with solid arcs) is obtained by inspection.
Normally, we use an artificial variable technique to find such a solution (for
details, see Bazaraa et aI.,1990,pp. aaO-aQ.
w+: -5
30(35) [-30] Ztz- Ctz- 0 - (*5) -3 : Z
zzs - czs: -5 - (_15) _t: 9
Z+s- Cr - -5 - (-15) - 4:6
*) Atc (2,5) reaches upper bound at 30.
Substitute x25: 30 - x52.
Reduce x23 aíId 45 each by 30.
o
-) w5: -
[-60]
15
ArcQ,5):w2-w5-czs
Arc(4,5):wa-w5-cqs
Thus, arc (2,5) enters the basic solution.
FlGURE 6.44
Network for iteration 0
In Figure 6.44, the basic feasible solution consists of (solid) arcs (]., 3), (1,,4), (Z,3),
and (3, 5) with the feasible flows of ]_0, 30, 50, and 60 units, respectively. This leaves
(dashed) arcs (1, 2), (2,5), and (4,5) to represent the nonbasic variables. The notation
x(c) shown on the arcs indicates that a flow of x units is assigned to an arc with capacity
c. The default yalues for x and c are 0 and oo, respectively.
Iteration 1.
Step 1. Determination of the EnteringArc: We obtain the dual values by solving the
current basic equations
Wt: 0
wi - w j : cii, for basic (l, 7)
We thus get,
Arc (1, 3) : w1 - w3 : 7, hence w, : _,7
Arc (1-, 4) : w1 - w4: 5, henca wo : -5
Arc(Z, 3) : w2 - w3 : 2, henca w, : -5
Arc (3, 5) : w3 - w5 : 8, henca w, : -15
Now, we complte zi1 - cilfor the nonbasic variables as
Arc(1_, 2): w1 - w2 - cp - 0 - (-5) - 3 :2
: (-5) - (-15) - 1
: (-5) - (-15) - 4
:9
:6
tUl:0
[40]
1W7- l
I
I
I
$3 l
I
I
I
I
262 Chapter 6 Network Models
Step 2. Determination of the Leaving Arc: From Figure 6.44, arc (2,5) forms a loop
with basic arcs (2,3) and (3, 5). From the definition of the spanning tree, no
other loop can be formed. Because the flow in the new arc (2,5) must be
increased, we adjust the flow in the arcs of the loop by an equal amount to
maintain the feasibility of the new solution. To achieve this, we identify the
positive (+) flow in the loop by the direction of flow of the entering arc (i.e.,
from 2 to 5). We then assign (+) or (-) to the remaining arcs of the loop,
depending on whether the flow of each arc is with or against the direction of
flow of the entering arc. These sign conventions are shown in Figure 6.44.
Determination of the maximum level of flow in the entering arc (2,5) is based on
two conditions:
1. New flow in current basic arcs of the loop cannot be negative.
2. New flow in the entering arc cannot exceed its capacity.
The application of condition ]. shows that the flows in arcs (2,3) and (3, 5) cannot
be decreased by more than min {50, 60} : 50 units. Condition 2 stipulates that the
flow in arc (2,5) can be increased to at most the arc capacity (:30 units). Thus, the
maximum flow change in the loop is min {30, 50} : 30 units.The new flows in the loop
are thus 30 units in arc (2,5),50 - 30 : 20 units in arc (2,3),and 60 - 30 : 30 units
in arc (3,5).
Because none of the current basic arcs leave the basis atzero level, the new atc (2,
5) must remain nonbasic at the upper bound. However, to avoid dealing with nonbasic
arcs that ate at capacity (or upper bound) level, we implement the substitution
X25:30- Xsz,O=X52 <30
This substitution is effected in the flow equations associated with nodes 2 and 5 as follows.
Consider
Current flow equation at node 2: 50 * xo: x23 l xzs
Current flow equation at node 5: x25 * xzs * xqs: 60
Then, the substitution x25 : 30 - x52 gives
New flow equation at node 2: 20 l xn l xsz : x23
New flow equation at node 5: x35 l xqs : x52 + 30
The results of these changes are shown in Figure 6.45.The direction of flow in arc
(2,5) is now reversed to 5 + 2 with x52 : 0, as desired. The substitution also requires
changing the unit cost of arc (5, 2) to -$t. We will indicate this direction reversal on
the network by tagging the arc with an asterisk.
Iteration_ 2._. Figure 6.45 summarizes the new values of zij - cij (verify!) and shows
that arc (4,5) enters the basic solution.It also defines the loóp asŠociatedwith the new
entering arc and assigns the signs to its arcs.
The flow in arc (4,5) can be increased by the smallest of
1. Maximum allowable increase in enteringarc(4, 5) : oo
2. Maximum allowable increase in arc (1, 4) : 35 - 30 : 5 units
5.5 Minimum-Cost Capacitated Flow Problem 263
- _:1lttri
, - *L_
_ _ . Lllš
., -L _
--,, L11,.
_:'OP
jnitS
':.- 1'.
* _ - -] __
- -::1L
- - i-1
:.> lutlin
arc
quiíes
sal on
shows
le new
30(35)
w3: -7
[-30]
A
ztz-ctz-0- (-5)-3:2
Zsz- csz: -15 -(_5) _(_1) : -9
zqs - cls - -5 - (-15) -4 : 6
Arc (4,5) enters at level5.
Arc (1. 4) leaves at upper bound.
Substitute xy: 35 - x4,.
Reduce x13 and x35 each by 5.
[20]
[20]
(30)*
w2: -5 xc5 : -15
FlGURE 6.45
Network for
iteration 1
3. Maximum allowable decrease in arc (1, 3) : ]_0 units
4. Maximum allowable decrease in arc (3, 5) : 30 units
*#';^'"T {:::::.?,(a;2 ":n
be increaseg to 5 units, which will make (4,s)basicand will force basic arc (1; ! Íobe nonbasic at iWrrr IUIUe Daslc arc (l, 4) to be nonbasic at its upper bound ( : 35).
Using the substitution x14 : 35 - xal,the netwórt i, .h;;"d;',network is changed as shown in Figure
ífí,.:.':^n_*:íii,í_r,r)-:'éir),ál,a
g,\\i;;ffifi# il":i:"6'r:X,li,,ffi:$ilrlrr grv9 \-l J)> \2l J)> \Jl J)l arru (+, J/ Iormmg tne baslc (spanning tree) solution.
T: r:::1_9j flow.in ar c (t, +) changes Ít.u"ii.ost to - $5. Also, convince yourself
that the substitution in the flbw Óquatións ot ooJ". 1 and 4 will n"tŠ'|;ňfiirrť,H:iin^áonode.
yourself
5(*)
zD-cn-0- (-5)-3:2
Zlt- cqt: -11 -0 _(_5) = _6
Zsz - csz: -15 - (_5) _(_1) : _9
Arc (1,2) enters at level5.
Arc (1,3) leaves at level0.
Increase x4by 5.
(30)* FlGURE 6.46
Network for iteration 2
_$s U4:
__J(35)* \
-11
t5]
u2: -5
IteraÚion 3, The comPutations of the
!}* .zii .- 9,ifor the nonbasic arcs (1, 2), (4,I),and (5, 2) are summari}edin Figure 6.46,wňťctr shows that arc (I,z)enters at level 5,and arc (1,3) becomes nonbasic at level O. rn. nŇ solution i. á"'pi.t.o in Figure 6.47.
r eration 4. The new Zri - ciiin F'igure
The values of the originál uaiiaUles áre
Figure 6.47.
6.47 shows that the solution is optimum.
obtained by back substitution as sirown in
I
I
I
$3 l
I
I
I
I
wl :0 Ul: -5
I
I
I
$+ t 1-;
I
I
I
[-30]
264 Chapter 6 Network Models
(35)*
5(*)
zn-cn-0-(-5)-7:-2
Zqt- cqt: -9 -0 -(-5) : _4
z5z- csz: -I3 - (-3) -(-1): -g
Optimum solution:
X12:5,X13:0
xg:35 _ 0:35
x7:25
x25:30-0:30
X35:25,X45: 5
Total cost : $490
Wa: -9
t5]
5(*)
[-30]
13
lz0] (30)*
w2: -3
FlGURE 6.47
Network for iteration 3
PRoBLEM sET 6,5c
1. Solve Problem 1, Set 6.5a by the capacitated simplex algorithm, and also show that it can
be solved by the transshipment model.
2. Solve Problem 2, Set 6.5a by the capacitated simplex algorithm, and also show that it can
be solved by the transshipment model.
3. Solve Problem 3, Set 6.5a by the capacitated simplex algorithm.
4. Solve Problem 4, Set 6.5a by the capacitated simplex algorithm.
5. Solve Problem 5, Set 6.5a by the capacitated simplex algorithm.
6. Solve the employment scheduling problem of Example 6.5-3 by the capacitated simplex
algorithm.
7. Wyoming Electric uses existing slurry pipes to transport coal (carried by pumped water)
from three mining areas (1,,2,and 3) to three power plants (4,5, and 6). Each pipe can
transport at most ]_0 tons per hour. The transportation costs per ton and the supply and
demand per hour are given in the following table.
t
z
J
Demand
Supply
8
10
18
1416
8.
9.
Determine the optimum shipping schedule.
The network in Figure 6.48 gives the distances among seven cities. Use the capacitated
simplex algorithm to find the shortest distance between nodes 1 and 7. (Hint: Assume
that nodes ]. and 7 have net flows of [+1] and [-1], respectively. A1l the other nodes have
zero net flow.)
Show how the capacitated minimum-cost flow model can be specialized to represent the
maximum flow model of Section 6.4.Apply the transformation to the network in
Example 6.4-2. For convenience, assume that the flow capacity from 4 to 3 is zero. Al1 the
remaining data are unchanged.
$s $s
$0 $q
$: $t
$+
$rz
$s
wt: 0
t5]
E-
lat it can
lat it can
simplex
d t-ater)
)e can
pls and
ritated
$ rrme
ldes have
esent the
in
ro.All the
6.5 Minimum-Cost Capacitated Flow Problem
FlGURE 6.48
Network for Problem 8, Set 6.5c
6.5.4 Excel Spreadsheet 5olution of the Minimum-Cost Capacitated
Flow Model
As in the cases of the shortest-route and maximum flow models, the Excel spreadsheet
developed for the general transportation model (Section 5.3.3) applies readily to the
capacitated network flow model. Figure 6.49 shows the application of the spreadsheet
to Example 6.5-4 (file ch6SolverMinCostCapacitatedNetwork.xls).Th" spreadsheet is
designed for networks with a maximum of 10 nodes. In the capacity matrix (cells
N6:W15),5 a blank entry signifies an infinite capacity arc. A nonexisting arc is represented
by a zero-capacity entry. As an illustration, in Example 6.5-4, infinite capacity
arc 1,-2 is represented by a blank entry in cell 06, and nonexisting arc 3-4 is shown by a
zeto entty in cell Q8. The unit cost matrix resides in cells B6:K].5. We arbitrarily assign
zero unit cost to all nonexisting arcs.
Once the unit cost and capacity matrices are cteated, the remainder of the
spreadsheet (intermediate calculations and optimum solution sections) is created automatically,
delineating the cells needed to update Solver parameters for Changing Cells
and Constraints. Target Cell is already defined for any network (with 10 nodes or less).
Specifically, for Example 6.5-4,we have,
Changing ce]_]_s: 820 :839
Constraints :
i?3,i]3:;1:r',L"r1' lffi""?i:;'H,lation)
Figure 6.49 ptovides the following solution: Nl-N2 : 5, N]_-N4 : 35,N2-N3 : 25,
N2-N5 : 30,N3-N5 : 25,and N4-N5 : 5.The associated total cost is $490.
PRoBLEM sET 6.5D
1. Solve the following problem using the spreadsheet in Section 6.5.4:
(a) Problem 3, Set 6.5c
(b) Problem 4, Set 6.5c
5In Figure 6.49, rows 1_1 through 15 and column K are hidden to conserve space.
ffi
i*,:
a]
i$l
#
Ute tUsl
From.To
Chapter 5 Network Models
it
FF-6ffi_tEE;ili
: lťi |ťl , lť: l{4 iťj
ilí
íťí
ilt
J,s
:::,
/rt
9'
iJ
d.
il
$
!,t, ]i i
{;{J, ij. š
!, {
q' !
tíi
6,6
Frnm I0 ]Utttťo 1
FlGURE 6.49
Excel Solver output for
Example 6.5-4
(c) Problem 7, Set 6.5c
(d) Problem 8, Set 6.5c
CPM AND PERT
CPM (Critical Path Method) and PEF{T (Program Evaluation and Review Technique)
are network-based methods designed to assist in the planning, scheduling, and control of
projects. A project is defined as a collection of interrelated activities with each activity
consuming time and resources. The objective of CPM and PERT is to provide analytic
means for scheduling the activities. Figure 6.50 summarizes the steps of the techniques.
First, we define the activities of the project, their precedence relationships, and their
L-
6.6 CPM and PERT 267
Network Time schedule
FlGURE 6.50
Phases for project planning
with CPM-PERT
time requirements. Next, the project is translated into a network that shows the precedence
relationships among the activities. The third step involves specific network computations
that form the basis for the development of the time schedule for the project.
During the execution of the project, the schedule may not be realized as planned,
causing some of the activities to be expedited or delayed. In this case, it will be necessary
to update the schedule to reflect the realities on the ground. This is the reason for
including a feedback loop between the time schedule phase and the network phase as
shown in Figure 6.50.
The two techniques, CPM and PERT, which were developed independently, differ
in that CPM assumes deterministic activity durations, whereas PERT assumes
probabilistic durations. This presentation will start with CPM and then provide the
details of PERT.
6.6.1 Network Representation
Each activity of the project is represented by an arc pointing in the direction of
progress in the project. The nodes of the network establish the precedence relationships
among the different activities of the project.
Two rules are avallable for constructing the network.
Rule 1. Each activity is represented by one, and only one, arc.
Rule 2. Each activity must be identified by two distinct end nodes.
Figure 6.51 shows how a dummy activity can be used to represent two concurrent
activities, A and B. By definition, a dummy activity, which normally is depicted by a
dashed arc, consumes no time or resources. Inserting a dummy activity in one of the
four ways shown in Figure 6.51,,we maintain the concurrence of A and B, and also provide
unique end nodes for the two activities (to satisfy rule 2).
Rule 3. To maintain the correct precedence relationships, the following questions must
be answered as each activity is added to the network:
(a) What activities must immediately precede the current activity?
(b) What activities must follow the current activity?
(c) What activities must occur concurrently with the current activity?
,:rnique)
; _,ntrol of
.. activity
"
analytic
--iniques.
:;rd their
|_l
i iŇ;*-".k| |
iT.ol.,,loti^- T
|
-lcalculationi
1
| .-----J
rl
268 Chapter 6 Network Models
FlGURE 6.51
Use of dummy activity to produce unique representation of concurrent activities A and B
The answers to these questions may require the use of dummy activities to ensure
correct precedences among the activities. For example, consider the following segment
of a project:
1. Activity C starts immediately after A and B have been completed.
2. Activity E starts after B only has been completed.
Part (a) of Figure 6.52 shows the incorrect representation of the precedence relationship
because it requires both A and B to be completed before E can start. In part (b),
the use of a dummy activity rectifies the situation.
FlGURE 6.52
Use of dummy activity to ensufe
correct precedence relationship
Example 6.6-1
A publisher has a contract with an author to publish a textbook.The (simplified) activities
associated with the production of the textbook are given below. Develop the associated
network for the project.
Activity Predecessor(s) Duration (weeks)
AC
-Lr*t
ID
B AE
-(, (b)(u)
á: Manuscript proofreading by editor
B: Sample pages prepared by typesetter
C: Book cover design
D: Preparation of artwork for book figures
E: Author's approval of edited manuscript
and sample pages A,B
J
2
4
J
G\ (^
d <,, ,\o
ď, )b ó",
re*e"ď b"
E---
F: Book typesetting
G: Author checks typeset pages
.F1: Author checks artwork
I: Production of printing plates
]: Book production and binding
E
F
D
G,H
C,I
6.6 CPM and PERT
2
7
1,
2
4
Figure 6.53 provides the network describing the precedence relationships among
the different activities. Dummy activity (2,3) produces unique end nodes for concurrent
activities,4 and B. The numbering of the nodes is done in a manner that indicates
the direction of progress in the project.
FlGURE 6.53
Project network for Example 6.6-1
_ :._,'n:].
] .
_: - l ]\ :
_'">S,_]PRoBLEM
sET 6.6A
Construct the project network comprised of activities Á to l with the following precedence
relationships:
(a) A, B, and C, the first activities of the project, can be executed concurrently.
(b) A and B precede D.
(c) B precedes E, F, and H.
(d) Fand C precede G.
(e) E and.I/ precede I and I.
(f) C, D, E and "I
precede K.
(g) K precedes l,.
(h) I, G, and L are the terminal activities of the project.
Construct the project network comprised of activities,4 to P that satisfies the following
precedence relationships:
(a) A, B, and C, the first activities of the project, can be executed concurrently.
(b) D, E, and F follow Á.
(c) Iand G follow both B and D.
(d) I1follows both C and G.
(e) K and l, follow I
(f) "I succeeds both E and H.
(g) M and N succeed { but cannot start until both Ě and H are completed.
(h) O succeeds M and L
(D P succeeds J, L, and O.
0) K N, and P are the terminal activities of the project.
270 Chapter 6 Network Models
The footings of a building can be completed in four connected sections. The activities for
each section include (1) digging, (2) placing steel, and (3) pouring concrete. The digging of
one section cannot start until that of the preceding section has been completed. The same
restriction applies to pouring concrete. Develop the project network.
In Problem 3, suppose that1,0% of the plumbing work can be started simultaneously with
the digging of the first section. After each section of the footings is completed, an additional
5% of,the plumbing can be started provided that the preceding 5% portion is completed.
The remaining plumbing can be completed at the end of the project. Construct the
project network.
5. An opinion survey involves designing and printing questionnaires, hiring and training
personnel, selecting participants, mailing questionnaires, and analyzing the data.
Construct the project network, stating all assumptions.
6. The activities in the following table describe the construction of a new house. Develop
the associated project network.
Activity Predecessor(s) Duration (days)
3.
4.
A: Clear site
B: Bring utilities to site
C: Excavate
D: Pour foundation
E: Outside plumbing
F: Frame house
G: Do electric wiring
11: Lay floor
I: Lay roof
I: Inside plumbing
K: Shingling
L: Outside sheathing insulation
M: Install windows and outside doors
N: Do brick work
O: Insulate walls and ceiling
P: Cover walls and ceiling
Q: Insulate roof
R: Finish interior
S: Finish exterior
T: Landscape
A
C
B,C
D
F
G
F
E,H
I
El
F
L,M
G,J
o
I,P
P
1,N
s
1
2
I
z
6
10
J
1
1
5
z
I
2
4
2
2
1
7
7
J
7. A company is in the process of preparing a budget
lowing table provides the associated activities and
network.
for launching a new product.The foltheir
durations. Construct the project
Activity Predecessor(s) Duration (days)
Forecast sales volume
Study competitive market
Design item and facilities
Prepare production schedule
Estimate cost of production
Set sales price
Prepare budget
A
C
D
B,E
E,F
10
7
5
J
2
1
1,4
_ -. iol::.
lect
8.
6.6 CPM and PERT 271
The activities involved in a candlelight choir service are listed in the following table.
Construct the project network.
Activity Predecessor(s) Duration (days)
Á: Select music
B: Learnmusic
C: Make copies and buy books
D: Tryouts
,E: Rehearsals
F: Rent candelabra
G: Decorate candelabra
1: Set up decorations
I: order choir robe stoles
I: Check out public address system
K: Select music tracks
L: Set up public address system
M: Finalrehearsal
N: Choir party
O: Final progfam
A
A
B,C
D
D
F
D
D
D
J
K
E,G,L
H,L,M
I,N
2
t4
I4
J
70
1,4
1,
I
7
7
1,4
1,
1
1,
I
9. The widening of a road section requires relocating ("reconductoring") 1700 feet of 13.8kV
overhead primary line.The following table summarizes the activities of the project.
Construct the associated project network.
Activity Predecessor(s) Duration (days)
A:
B:
C:
D:
E:
F:
G:
H:
I:
J:
K:
L:
M:
N:
O:
P:
Q:
R:
^:
T:
U:
Job review
Advise customers of temporary outage
Requisition stores
Scout job
Secure poles and material
Distribute poles
pole location coordination
Re-stake
Dig holes
Frame and set poles
cover old conductors
pull new conductors
Install remaining material
Sag conductor
Trim trees
De-energize and switch lines
Energize and switch new line
Clean up
Remove old conductor
Remove old poles
Return material to stores
A
A
A
C,D
E
D
G
H
EI
1I
l,K
L
L
D
B,M,N,o
P
O
O
s
R,T
1
,5
J
3,5
,5
.5
J
4
I
2
2
2
2
.1
.5
I
1,
2
2
10. The following table gives the activities
work.
for buying a new car. Construct the project net-
272 Chapter 5 Network Models
Activity Predecessor(s) Duration (days)
Conduct feasibility study
Find potential buyer for present car
List possible models
Research all possible models
conduct interview with mechanic
Collect dealer propaganda
Compile pertinent data
Choose top three models
Test-drive all three choices
Gather warranty and financing data
choose one car
choose dealer
Search for desired color and options
Test-drive chosen model once again
purchase new car
A
A
C
C
C
D,E,F
G
H
H
I,J
K
L
L
B,M,N
J
1,4
I
J
1
2
1
1,
J
2
z
z
4
1
J
6,6.2 Critical Path (CPM) Computations
The ultimate result in CPM is the construction of the time schedule for the project (see
Figure 6.50). To achieve this objective conveniently, we carry out special computations
that produce the following information:
1_. Total duration needed to complete the project
2. Classification of the activities of the project as critical and noncritical
An activity is said to be critical if there is no "leeway" in determining its start and
finish times. A noncritical activity allows some scheduling slack, so that the start time
of the activity may be advanced or delayed within limits without affecting the completion
date of the entire project.
To carry out the necessary computations, we define an event as a point in time at
which activities are terminated and others are started. In terms of the network, an
event corresponds to a node. Define
T.
: Earliest occurrence time of event i
Al : Latest occurrence time of eventi
P,i : Duration of activity (l, 7)
The definitions of the earliest and latest occurrence times of event j are specified relative
to the start and completion dates of the entire project.
The critical path calculations involve two passes: The forward pass determines
the earliesl occurrence times of the events, and the backward pass calculates their latest
occurrence times.
Forward Pass (Earliest Occurrence Times, D). The computations start at node 1 and
advance recursively to end node n.
b-
6.6 CPM and PERT 273
Initial S ep. Set !, : 0 to indicate that the project starts at time 0.
General Step7. Given that nodes p, Q,, ... , and v ate linked directly to nodei by
incoming activities (p, j), (q, j),... , and (v, j) and that the earliest occurrence
times of events (nodes) p, Q,, ... , and y have already been computed, then
the earliest occurrence time of eventi is computed as
T: maxp, l Dpl,J, l Dq1,..., !u + D,}
The forward pass is complete when J, at node nhas been computed. By definition
Q. represents the longest path (duration) to node i.
Backward Pass (Latest Occurrence Times, A). Following the completion of the forward
pass, the backward pass computations start at node n and end at node 1.
Initial Step. Set A, : Jnto indicate that the earliest and latest occurrences of the last
node of the project are the same.
General Stepi. Given that nodes p, Q,. . . , and v are linked directly to node i by
outgoing activities (i, d, (j, q),. . . , and (j, ,) and that the latest occurrence
times of nodes p, Q,... , and y have already been computed, the latest occurrence
time of nodei is computed as
Ai : min{Ao - Dio,
^q
- Djr,..., Au - Dr}
The backward pass is complete when 41 at node 1 is computed.
Based on the preceding calculations, an activity (a 7) will be critical if ítsatisfies
three conditions.
1. A,:!;
2.Ai:!i
3. Ar-A,:ql-Ji:Dij
The three conditions state that the earliest and latest occurrence times of nodes i and j
are equal, and the duration D,,fits "tightly" in the specified time span. An activity that
does not satisfy all three conditionsis noncritical.
The critical activities of a network must constitute an uninterrupted path that
spans the entire network from start to finish.
Example 6.6-2
Determine the critical path for the project network in Figure 6.54.A1l the durations are
in days.
Forward pass
Node 1. Set !, : 6
Node2. a2: !r * Dn:0 i 5:5
274 Chapter 6 Network Models
Node 3.
Node 4.
Node 5.
Node 6.
FlGURE 6.54
Forward and backward
pass calculations for the
project of Example 6.6-2
End
backward
paSS .
\n
/o\r-:---,l
t
j_]
,í
Start'
forward
paSS
maxp1 l Drr,Jz + Drl} : max{0 + 6, 5 + 3} : 3
[J2+Dzq:5+8:!3
max{D3 * Drr, !4 + Dor}: max{S + 2, 13 + 0} : 13
maxfl3 * Dru, !+ i Dqa,Js + Dse)
max {8 + LI,13 + 1,, 13 + 12} : 25
Legend:
Forward pass:
Backward pass:
Critical path:
!g:
l)l
-
!s:
ou]
The computations show that the project can be completedin25 days.
Backward pass
Node 6. Set 46 : Do : 25
Node5. As : A6 - Dsa : 25 _ 12 : t3
NOde4. A+: min{A6 - Dou, A5 _ Dor}: min{25 _I, 13 _ 0}:13
NOde3. A:: min{A6 _ Dru, A5 _ D..o}: min{25 _1,1,,t3 _2}:11
NOde2. Lz: min{Aa _ Dr^, A3 _ Drr}: min{13 _ 8, ]_]_
_ 3}:5
Node1_. Ar: min{A3 _ Drr,
^2_
Drr}: min{ll _6,5 _ 5}:0
Correct computations will always end with Ar : 0.
The forward and backward pass computations are summaized in Figure 6.54. The
rules for determining the critical activities show that the critical path is defined by
1, +2 + 4 + 5 + 6, which spans the network from start (node 1-) to finish (node 6).
The sum of the durations of the critical activities I(I,2), (2,4), (4, 5), and (5, 6)] equals
the duration of the project (: 25 days). Observe that activity (4,6) satisfies the first two
conditions for a critical activity (A+ : !+ : ].3 and As : !s : 25) but not the third
(!u - Jq * Doe).Flence, the activity is not critical.
!--*E
A*--A
0-0
Start
backward
1 y' pass
.á5\
lÁllEnd
\ forward
pass
J
/6
1, C13
6
A
5 g/- e
D
1
L-----
: :j. The
_.:ed bl,
. ,-,,Je 6),
-
equals
_lst trvo
-:; third
Start
backward
'pass
End
. forward
paSs
6.6 CPM and PERT 275
PRoBLEM sET 6.68
1. Determine the critical path for the project network in Figure 6.55.
FlGURE 6,55
Project network for Problem ]", Set 6.6b
2. Determine the critical path for the project networks in Figure 6.56.
Project (a) Project (b)
FlGURE 6.56
Project network for Problem 2, Set 6.6b
3. Determine the critical path for the project in Problem 6, Set 6.6a.
4. Determine the critical path for the project in Problem 8, Set 6.6a.
5. Determine the critical path for the project in Problem 9, Set 6.6a.
6. Determine the critical path for the project in Problem 10, Set 6.6a.
6.6.3 Construction of the Time Schedule
This section shows how the information obtained from the calculations in section 6.6.2
can be used to develop the time schedule. We recognize that for an activity (i, Ď, J,
represents the earliest start time, and Al represents the latest completion time. This
means that (!,, A) delineates the (maximum) span during which activity (4 i) may be
scheduled.
Cons ruction of Preliminary Schedule. The method for constructing a preliminary
schedule is illustrated by an example.
!
l
!
!
!
I
l
276 Chapter 6 Network Models
Example 6.6-3
Determine the time schedule for the project of Example 6.6-2 (Figure 6.54).
We can get a preliminary time schedule for the different activities of the project by
delineating their respective time spans as shown in Figure 6.57. Two observations are in
order.
The critical activities (shown by solid lines) must be scheduled one right after the
other to ensure that the project is completed within its specifiedZí-day duration.
The noncritical activities (shown by dashed lines) encompass spans that are
larger than their respective durations, thus allowing slack (or "leeway") in scheduling
them within their allotted spans.
A-5
D-B
Critical
H-t2
Noncritical
Days
FlGURE 6.57
Preliminary schedule for the project of Example 6.6-2
How should we schedule the noncritical activities within their respective spans?
Normally, it is preferable to start each noncritical activity as early as possible. In this
manner, slack periods will remain opportunely available at the end of the allotted
span, where they can be used to absorb unexpected delays in the execution of the
activity. It may be necessary, however, to delay the start of a noncritical activity past its
earliest time. For example, in Figure 6.57,suppose that each of the noncritical activities
E and F requires the use of a bulldozer, and that only one is available. Scheduling both
E and F as early as possible requires two bulldozers between times 8 and 10. We can
remove the overlap by starting E at time 8 and pushing the start time of F to somewhere
between times ].0 and 14.
If all the noncritical activities can be scheduled as early as possible, the resulting
schedule automatically is feasible. Otherwise, some precedence relationships may be
violated if noncritical activities are delayed past their earliest time. Take, for example,
activities C and E in Figure 6.57.In the project network (Figure 6.54), though C must
1.
,,
6.6 CPM and PERT 277
be completed before E, the spans of C and E in Figure 6.57 allow us to schedule C
between times 6 and 9, and E between times 8 and 10. These spans, however, do not
ensure that C will precede E. The need for a "red flag" that automatically reveals
schedule conflict is thus evident. Such information is provided by computing the floats
for the noncritical activities.
Determination of the Floats. Floats are the slack times available within the allotted
span of the noncritical activity. The two most common floats are the total float and the
free float.
Figure 6.58 gives a convenient summary for computing the total float (TFi) and
the free float (FF) for an activity (i, j).The total float is the excess of the time span
defined from the earliesl occurrence of event l to the latest occurrence of event i over
the duration of (1,7)-that is,
'F,i
:Ar-!,-Pii
A F|GURE 6.58
__-'4ljiŘ7
Computation of total and free floats
.^.- Di\ _^
-\2t _?
,ťíii--')-"
2
u-
TIí'
,F,j : Jj - Ji- D ij
M: *ffi
]
The free float is the excess of the time span defined from the earliesl occurrence of
event l to the earliest occurrence of event i over the duration of (a 7)-that is,
FFii :!l-J,-D,i
By definition, FFii < TFij.
Red-Flagging Rule. For a noncritical activity (i, j)
(a) U FF,i : TF,j, then the activity can be scheduled anywhere within ifi (!i, A,) span
without causing s chedule conflict.
(b) IíFF,i .
'Fii,then
the start of activity (i, j) can be delayed by at most FF,1 relative
to its earliest start time (J) without causing schedule conflict. Any delay larger than
FFi1 @ut not more than TF;) must be accompanied by an equal delay relative toJ1
in the start time of all the activities leaving node j.
The implication of the rule is that a noncritical activity (l, r) will be red-flagged if
its FFu < TFii. This red flag is important only if we decide to delay the start of the
activity past its earliest start time, !,, in which case we must pay attention to the start
times of the activities leaving nodei to avoid schedule conflicts.