Chapter 12
Network Models
Prepared by Lee Revere and John Large
To accompany
Quantitative
12-1
2006 by
Prentice Hall,
Learning Objectives
Students will be able to:
1. Connect all points of a network while
minimizing total distance using the
minimal-spanning tree technique.
2. Determine the maximum flow through a
network using the maximal-flow
technique.
3. Find the shortest path through a network
using the shortest-route technique.
4. Understand the important role of
software in solving network problems.
To accompany
Quantitative
12-2
2006 by
Prentice Hall,
Chapter Outline
12.1 Introduction
12.2 Minimal-Spanning Tree
Technique
12.3 Maximal-Flow Technique
12.4 Shortest-Route Technique
To accompany
Quantitative
12-3
2006 by
Prentice Hall,
Introduction
The presentation will cover three
network models that can be used to
solve a variety of problems:
1. the minimal-spanning tree technique,
2. the maximal-flow technique,
and
3. the shortest-route technique.
To accompany
Quantitative
12-4
2006 by
Prentice Hall,
Minimal-Spanning
Tree Technique
Definition:
The minimal-spanning tree technique
determines the path through the network
that connects all the points while
minimizing total distance.
For example:
If the points represent houses in a
subdivision, the minimal spanning tree
technique can be used to determine the
best way to connect all of the houses to
electrical power, water systems, etc.
in a way that minimizes the total
distance or length of power lines or
water pipes.
To accompany
Quantitative
12-5
2006 by
Prentice Hall,
The Maximum Flow
Technique
Definition:
The maximal-flow technique finds the
maximum flow of any quantity or
substance through a network.
For example:
This technique can determine the
maximum number of vehicles (cars,
trucks, etc.) that can go through a
network of roads from one location
to another.
To accompany
Quantitative
12-6
2006 by
Prentice Hall,
Shortest Route
Technique
Definition:
Shortest route technique can find the
shortest path through a network.
For example:
This technique can find the shortest
route from one city to another through a
network of roads.
To accompany
Quantitative
12-7
2006 by
Prentice Hall,
Minimal-Spanning Tree
Steps
1. Selecting any node in the network.
2. Connecting this node to the nearest
node minimizing the total distance.
3. Finding and connecting the nearest
unconnected node.
If there is a tie for the nearest node, one
can be selected arbitrarily.
A tie suggests that there may be more than
one optimal solution.
4. Repeating the third step until all nodes
are connected.
To accompany
Quantitative
12-8
2006 by
Prentice Hall,
Minimal-Spanning
Tree Technique
Solving the network for Melvin
Lauderdale construction
Start by arbitrarily selecting node 1.
Since the nearest node is the third node at
a distance of 2 (200 feet), connect node 1
to node 3.
Shown in Figure 12.2 (2 slides hence)
Considering nodes 1 and 3, look for the
next-nearest node.
This is node 4, which is the closest to node 3
with a distance of 2 (200 feet).
Once again, connect these nodes (Figure
12.3a (3 slides hence).
To accompany
Quantitative
12-9
2006 by
Prentice Hall,
Figure 12.1: Network for
Lauderdale Construction
To accompany
Quantitative
12-10
2006 by
Prentice Hall,
Figure 12.2: First Iteration
Lauderdale Construction
To accompany
Quantitative
12-11
2006 by
Prentice Hall,
Fig 12.3a:
Second Iteration
To accompany
Quantitative
12-12
2006 by
Prentice Hall,
Fig 12.3b:
Third Iteration
To accompany
Quantitative
12-13
2006 by
Prentice Hall,
Summarize: MinimalSpanning Tree Technique
Step 1:
Step 2:
Step 3:
Step 4:
Select node 1
Connect node 1 to node 3
Connect the next nearest
node
Repeat the process
The total number of iterations to
solve this example is 7.
This final solution is shown in the
following slide.
To accompany
Quantitative
12-14
2006 by
Prentice Hall,
Fig 12.5b:
Third Iteration
To accompany
Quantitative
12-15
2006 by
Prentice Hall,
Final Solution to the
Minimal-Spanning
Tree Example
Nodes 1, 2, 4, and 6 are all connected to node
3. Node 2 is connected to node 5.
Node 6 is connected to node 8, and node 8 is
connected to node 7.
All of the nodes are now connected.
The total distance is found by adding the
distances for the arcs used in the spanning tree.
In this example, the distance is:
2 + 2 + 3 + 3 + 3 + 1 + 2 = 16 (or 1,600 feet).
To accompany
Quantitative
12-16
2006 by
Prentice Hall,
Maximal-Flow
Technique
The maximal-flow technique allows the
maximum amount of a material that can
flow through a network to be determined.
For example:
It has been used to find the maximum
number of automobiles that can flow
through a state highway system.
An example:
Waukesha is in the process of developing
a road system for downtown.
City planners would like to determine the
maximum number of cars that can flow
through the town from west to east.
The road network is shown in Figure 12.6
(next slide).
To accompany
Quantitative
12-17
2006 by
Prentice Hall,
Road Network for
Waukesha
Traffic can flow in both directions.
To accompany
Quantitative
12-18
2006 by
Prentice Hall,
Maximal-Flow
Technique (continued)
The Four Maximal-Flow Technique Steps:
1.
Pick any path from the start (source) to the
finish (sink) with some flow.
If no path with flow exists, then the
optimal solution has been found.
2. Find the arc on this path with the smallest
flow capacity available.
Call this capacity C.
This represents the maximum additional
capacity that can be allocated to this
route.
3. For each node on this path, decrease the flow
capacity in the direction of flow by the
amount C.
For each node on this path, increase the
flow capacity in the reverse direction by
the amount C.
4. Repeat these steps until an increase in flow is
no longer possible.
To accompany
Quantitative
12-19
2006 by
Prentice Hall,
Solving the Waukesha
Example
Start by arbitrarily picking the path
126, at the top of the network.
What is the maximum flow from west
to east? It is 2 because only 2 units (200
cars) can flow from node 2 to node 6.
Now we adjust the flow capacities
(Figure 12.7). As you can see, we
subtracted the maximum flow of 2
along the path 126 in the direction of
the flow (west to east) and added 2 to
the path in the direction against the
flow (east to west).
The result is the new path in Figure
12.7 (next slide).
To accompany
Quantitative
12-20
2006 by
Prentice Hall,
Capacity Adjustment
Iteration 1
Add 2
1
2
2
Subtract 2
West
Point 1
4
1
West
1
Point
To accompany
Quantitative
East
Point
6
New path
12-21
East
Point
2006 by
Prentice Hall,
Solving the Waukesha
Example
The New Path reflects the new relative capacity
at this stage.
The flow number by any node represents two
factors.
One factor is the flow that can come from that
node.
The second factor is flow that can be reduced
coming into the node.
The number 1 by node 1 indicates that 100 cars
can flow from node 1 to node 2.
3
0
4
West
1
Point
To accompany
Quantitative
6
New path
12-22
East
Point
2006 by
Prentice Hall,
Solving the Waukesha
Example
The number 0 by node 2 on the path from
node 2 to node 6 indicates that 0 cars can flow
from node 2 to node 6.
3
0
4
West
Point
6
New path
East
Point
The number 4 by node 6, on the path from node 6 to
node 2, indicates that we can reduce the flow into
node 6 by 2 (or 200 cars) and that there is a capacity
of 2 (or 200 cars) that can come from node 6.
These two factors total 4.
To accompany
Quantitative
12-23
2006 by
Prentice Hall,
Solving the
Waukesha Example
On the path from node 2 to node 1, the number 3
by node 2 shows that we can reduce the flow into
node 2 by 2 (or 200 cars) and that there is a
capacity of 1 (or 100 cars) from node 2 to node 1
3
0
4
West
Point
6
New path
East
Point
At this stage, there is a flow of 200 cars through
the network from node 1 to node 2 to node 6.
The new relative capacity reflects this.
To accompany
Quantitative
12-24
2006 by
Prentice Hall,
Repeat the Process
Now, repeat the process by picking another
path with existing capacity.
Can arbitrarily pick path 1246.
The maximum capacity along this path is 1.
In fact, the capacity at every node along this
path (1246) going from west to east is 1.
Remember, the capacity of branch 12 is
now 1 because 2 units (200 cars per hour)
are now flowing through the network.
So, need to increase the flow along path
1246 by 1 and adjust the capacity flow
(see next slide).
To accompany
Quantitative
12-25
2006 by
Prentice Hall,
Fig-12.8a: Second
Iteration for Waukesha
Add 1
2
1
4
Subtract 1
Old Path
To accompany
Quantitative
12-26
2006 by
Prentice Hall,
Fig-12.8b: Second
Iteration for Waukesha
4
2
0
4
West
Point
0 2 0
10
East
Point
6
0
32
New Network
To accompany
Quantitative
12-27
2006 by
Prentice Hall,
Continuing the Process
Now, there is a flow of 3 units (300 cars):
200 cars per hour along path 126
plus
100 cars per hour along path 1246
Can the flow be further increased?
Yes, along path 1356.
This is the bottom path.
The maximum flow is 2 because this is the
maximum from node 3 to node 5.
The increased flow along this path is shown
in the next slide.
To accompany
Quantitative
12-28
2006 by
Prentice Hall,
Third Iteration
4
2
0
4
West
Point
0 2 0
10
East
Point
Subtract 2
6
32
To accompany
Quantitative
Add 2
12-29
2006 by
Prentice Hall,
Continuing the Process
Again, repeat the process.
Try to find a path with any unused
capacity through the network.
Carefully checking the third iteration in
the last slide reveals that there are no
more paths from node 1 to node 6 with
unused capacity,
even though several other branches in the
network do have unused capacity.
The final network appears on the next
slide.
To accompany
Quantitative
12-30
2006 by
Prentice Hall,
Final Iteration
New Path
4
2
0
4
West
Point
0 2 0
10
East
Point
4
0
30
To accompany
Quantitative
Path = 1, 3, 5, 6
12-31
2006 by
Prentice Hall,
Final Network Flow
The maximum flow of 500 cars per hour is
summarized in the following table:
(Cars per Hour)
Hour
PATH
FLOW
1-2-6
1-2-4-6
1-3-5-6
200
100
200
=500
Total
To accompany
Quantitative
12-32
2006 by
Prentice Hall,
The Shortest-Route
Technique
The shortest-route technique minimizes
the distance through a network.
The shortest-route technique finds how a
person or item can travel from one
location to another while minimizing the
total distance traveled.
The shortest-route technique finds the
shortest route to a series of destinations.
To accompany
Quantitative
12-33
2006 by
Prentice Hall,
Example: From Rays
Plant to Warehouse
For example,
Every day, Ray Design, Inc., must
transport beds, chairs, and other furniture
items from the factory to the warehouse.
This involves going through several
cities.
Ray would like to find the route with the
shortest distance.
The road network is shown on the next
slide.
To accompany
Quantitative
12-34
2006 by
Prentice Hall,
Shortest-Route Technique
(continued)
Roads from Rays Plant to Warehouse:
Plant
200
0
10
10
50
20
10
0
150
6
0
10
To accompany
Quantitative
40
12-35
5
Warehouse
2006 by
Prentice Hall,
Steps of the ShortestRoute Technique
1. Find the nearest node to the origin
(plant). Put the distance in a box by the
node.
2. Find the next-nearest node to the origin
(plant), and put the distance in a box
by the node. In some cases, several
paths will have to be checked to find
the nearest node.
3. Repeat this process until you have
gone through the entire network.
The
The last
last distance
distance at
at the
the ending
ending node
node will
will
be
be the
the distance
distance of
of the
the shortest
shortest route.
route.
To accompany
Quantitative
12-36
2006 by
Prentice Hall,
Shortest-Route
Technique (continued)
Ray Design: 1st Iteration
100
Plant
200
0
10
10
50
10
150
20
0
6
0
10
40
5
Warehouse
The nearest node to the plant is node
2, with a distance of 100 miles.
Thus, connect these two nodes.
To accompany
Quantitative
12-37
2006 by
Prentice Hall,
Shortest Route
Technique (continued)
Ray Design: 2nd Iteration
100
200
2
0
10
10
50
10
150
20
0
6
0
10
40
150
The nearest node to the plant is node
3, with a distance of 50 miles.
Thus, connect these two nodes.
To accompany
Quantitative
12-38
2006 by
Prentice Hall,
Shortest-Route
Technique (continued)
Ray Design: 3rd Iteration
100
200
2
0
10
10
50
10
150
20
0
6
0
10
40
5
190
150
The nearest node to the plant is node
5, with a distance of 40 miles.
Thus, connect these two nodes.
To accompany
Quantitative
12-39
2006 by
Prentice Hall,
Shortest Route
Technique (continued)
4th and Final Iteration
100
200
2
0
0
1
10
50
20
10
0
290
150
6
0
10
40
5
190
150
Total Shortest Route =
100 + 50 + 40 + 100 = 290 miles.
To accompany
Quantitative
12-40
2006 by
Prentice Hall,
