NETWORK FLOW MODELS
Chapter Topics The Minimal Spanning Tree Problem The Shortest Route Problem
The Maximal Flow Problem
Critical Path
Overview
A network is an arrangement of paths connected at various points through which one or more items move from one point to another.
The network is drawn as a diagram providing a picture of the system thus enabling visual interpretation and enhanced understanding.
A large number of real-life systems can be modeled as networks which are relatively easy to conceive and construct. Network diagrams consist of nodes and branches. Nodes (circles), represent junction points, or locations.
Branches (lines), connect nodes and represent flow.
Characteristics of Network Models
A node is a specific location An arc connects 2 nodes Arcs can be 1-way or 2-way
Application
Nodes (vertices)
Intersection
Airports
Arcs (edges)
Roads
Air lanes
Flow
Vehicles
Aircraft
Switching points Wires, Channels
Pumping Station Pipes Work Centers Materialhandling routes
Messages,
Fluids Jobs
Example
Four nodes, four branches in figure. Atlanta, node 1, termed origin, any of others destination. Branches identified by beginning and ending node numbers.
Value assigned to each branch (distance, time, cost, etc.).
Figure 1 Network of Railroad Routes
6
Minimum Spanning Trees
Minimum Spanning Tree (MST)
A minimum spanning tree is a subgraph of an undirected weighted graph G, such that it is a tree (i.e., it is acyclic) it covers all the vertices V
contains |V| - 1 edges
the total cost associated with tree edges is the minimum among all possible spanning trees not necessarily unique
Concrete example
Imagine: You wish to connect telephone system in a town or all the computers in an office building using the least amount of cable a weighted graph problem !!
- Each vertex in a graph G represents a home (computer) - Each edge represents the amount of cable needed to connect all computers
Minimum-Spanning Trees
Problem: Laying Telephone Wire
Central office
11
Wiring: Nave Approach
Central office
Expensive!
12
Wiring: Better Approach
Central office
Minimize the total length of wire connecting the customers
13
How Can We Generate a MST?
9
b
6 4 5
b
6 4 5
a
5
2 4
d
5
a
5
2 4
d
5
14
The Minimal Spanning Tree Problem Definition and Example Problem Data
Problem: Connect all nodes in a network so that the total branch lengths are minimized.
Network of Possible Cable TV Paths
15
The Minimal Spanning Tree Problem Solution Approach (1 of 6)
Start with any node in the network and select the closest node to join the spanning tree.
Spanning Tree with Nodes 1 and 3
16
The Minimal Spanning Tree Problem Solution Approach (2 of 6)
Select the closest node not presently in the spanning area.
Spanning Tree with Nodes 1, 3, and 4
17
The Minimal Spanning Tree Problem Solution Approach (3 of 6)
Continue
Spanning Tree with Nodes 1, 2, 3, and 4
18
The Minimal Spanning Tree Problem Solution Approach (4 of 6)
Continue
Spanning Tree with Nodes 1, 2, 3, 4, and 5
19
The Minimal Spanning Tree Problem Solution Approach (5 of 6)
Continue
Spanning Tree with Nodes 1, 2, 3, 4, 5, and 7
20
The Minimal Spanning Tree Problem Solution Approach (6 of 6)
Optimal Solution
Minimal Spanning Tree for Cable TV Network
21
The Minimal Spanning Tree Problem Solution Method Summary
Select any starting node (conventionally, node 1).
Select the node closest to the starting node to join the spanning tree. Select the closest node not presently in the spanning tree (if there is a tie, select one arbitrarily). Repeat step 3 until all nodes have joined the spanning tree.
22
Lauderdale Construction Example
Building a network of water pipes to supply water to 8 houses (distance in hundreds of feet)
Steps 1 and 2 Starting arbitrarily with node (house) 1, the closest node is node 3
Second and Third Iterations
Fourth and Fifth Iterations
Sixth and Seventh Iterations
After all nodes (homes) are connected the total distance is 16 or 1,600 feet of water pipe
The Shortest Route Problem Definition and Example Problem Data
Problem: Determine the shortest routes from the origin to all destinations.
Shipping Routes from Los Angeles
28
The Shortest Route Problem Solution Method
Select the node with the shortest direct route from the origin.
Establish a permanent set with the origin node and the node that was selected in step 1. Determine all nodes directly connected to the permanent set nodes. Select the node with the shortest route (branch) from the group of nodes directly connected to the permanent set nodes. Repeat steps 3 and 4 until all nodes have joined the permanent set.
29
The Shortest Route Problem Definition and Example Problem Data (2 of 2)
Network of Shipping Routes
30
The Shortest Route Problem Solution Approach (1 of 8)
Determine the initial shortest route from the origin (node 1) to the closest node (3).
Network with Node 1 in the Permanent Set
31
The Shortest Route Problem Solution Approach (2 of 8)
Determine all nodes directly connected to the permanent set.
Network with Nodes 1 and 3 in the Permanent Set
32
The Shortest Route Problem Solution Approach (3 of 8)
Redefine the permanent set.
Network with Nodes 1, 2, and 3 in the Permanent Set
33
The Shortest Route Problem Solution Approach (4 of 8)
Continue
Network with Nodes 1, 2, 3, and 4 in the Permanent Set
34
The Shortest Route Problem Solution Approach (5 of 8)
Continue
Network with Nodes 1, 2, 3, 4, and 6 in the Permanent Set
35
The Shortest Route Problem Solution Approach (6 of 8)
Continue
Network with Nodes 1, 2, 3, 4, 5, and 6 in the Permanent Set
36
The Shortest Route Problem Solution Approach (7 of 8)
Optimal Solution
Network with Optimal Routes from Los Angeles to All Destinations
37
The Shortest Route Problem Solution Approach (8 of 8)
Solution Summary
Shortest Travel Time from Origin to Each Destination
38
Using LP for SPP
Want to find the shortest path from the factory to the warehouse Supply of 1 at factory Demand of 1 at warehouse
Decision Variables Xij = flow from node i to node j Note: flow on arc ij will be 1 if arc ij is used, and 0 if not used Roads are bi-directional, so the 9 roads require 18 decision variables
Shortest Path Problem LP Formulation
Minimize Z s.t.
c
i 1 j 1 n
ij
xij
Total Cost
j i 1 n 1 i 2
x ji
j i 1
x
ji
ij
f or i 1 f or i 1, j n f or j n
x x
ij i2
0 1
x x
i a ij ia
j 1
ji
xij 0 ( xij is binary, for all i and j )
Example
Objective Function (in distance) Min 100X12 + 200X13 + 100X21 + 50X23 + 200X24 + 100X25 + 200X31 + 50X32 + 40X35 + 200X42 + 150X45 + 100X46 + 40X53 + 100X52 + 150X54 + 100X56 + 100X64 + 100X65
Subject to the constraints:
(see next slide)
Constraints: Flow Balance For Each Node
Node
(X21 + X31) (X12 + X13)
= -1
1
3 4 6
(X12+X32+X42+X52)(X21+X23+X24+X25)=0 2 (X13 + X23 + X53) (X31 + X32 + X35) = 0 (X24 + X54 + X64) (X42 + X45 + X46) = 0 (X46 + X56) (X64 + X65) =1
(X25+X35+X45+X65)(X52+X53+X54+X56)=0 5
