Network Models - modeling and simulation(lecture Three).ppt

modelling and simulation

1. NETWORK MODELS

2. INTRODUCTION
A common scenario of a network-flow problem arising in industrial logistics.
It concerns the distribution of a single homogeneous product from plants (origins) to
consumer markets (destinations).
The total number of units produced at each plant and the total number of units
required at each market are assumed to be known.
The product need not be sent directly from source to destination, but may be routed
through intermediary points reflecting warehouses or distribution centers.
There may be capacity restrictions that limit some of the shipping links. The
objective is to minimize the variable cost of producing and shipping the
products to meet the consumer demand.

3. INTRODUCTION CONT…
The sources, destinations, and intermediate points are collectively called
nodes of the network, and the transportation links connecting nodes are
termed arcs.
The nodes are represented by numbered circles and the arcs by arrows.
The arcs are assumed to be directed so that, for instance, material can be sent
from node 1 to node 2, but not from node 2 to node 1.

4. Basic Definitions
A graph or network is defined by two sets of symbols:
• Nodes: A set of points or vertices(call it V) are called
nodes of a graph or network.
• Arcs: An arc consists of an ordered pair of vertices and
represents a possible direction of motion that may
occur between vertices.
1 2
Nodes
1 2
Arc
Fig. 1.
Fig. 2.

5. • Chain: A sequence of arcs such that every arc has exactly one
vertex in common with the previous arc is called a chain.
1 2
Common vertex
between two arcs
Fig. 3.

6. • Path: A path is a chain in which the terminal node of
each arc is identical to the initial node of next arc.
For example in the figure below (1,2)-(2,3)-(4,3) is a chain
but not a path; (1,2)-(2,3)-(3,4) is a chain and a path,
which represents a way to travel from node 1 to node 4.
2 3
1 4
Fig. 4.

7. Directed Path . Example: 1, 2, 5, 3, 4
(or 1, a, 2, c, 5, d, 3, e, 4)
•No node is repeated.
•Directions are important.
Cycle (or circuit or loop)
1, 2, 3, 1. (or 1, a, 2, b, 3, e)
•A path with 2 or more nodes, except that the first node is
the last node.
•Directions are ignored.
Path: Example: 5, 2, 3, 4.
(or 5, c, 2, b, 3, e, 4)
•No node is repeated.
•Directions are ignored.
Directed Cycle: (1, 2, 3, 4, 1) or
1, a, 2, b, 3, c, 4, d, 1
•No node is repeated.
•Directions are important.
2 3 4
a b
c
1
5
d
e
2
3
4
a
b
c d
1
e
2 3 4
a b
c
1
5
d
e
2
3
4
a b
c d
1
e
ILLUSTRATIVE REPRESENTATION OF PATH

8. 8
Directed and Undirected Networks
2
34
1
a
b
c
d
e
An Undirected Graph
2
34
1
a
b
c
d
e
A Directed Graph
The field of Network Optimization concerns
optimization problems on networks
Networks are used to transport commodities
• physical goods (products, liquids)
• communication
• electricity, etc.

9. 9
MORE TERMINOLOGY
An undirected network is connected if every node
can be reached from every other node by a path
2
1
4
3
5
2
1
4
3
5
A directed network is connected if it’s undirected
version is connected.
This directed graph is connected, even though there
is no directed path between 2 and 5.

10. 10
Networks are Everywhere
•Physical Networks
•Road Networks
•Railway Networks
•Airline traffic Networks
•Electrical networks, e.g., the power grid
•Abstract networks
•organizational charts
•precedence relationships in projects
•Others?

11. EXAMPLES OF NETWORK FLOW PROBLEMS

12. WALKS
2
34
1
a
b
c
d
e
5
2
34
1
a
b
c
d
e
5
Walks are paths that can repeat nodes and arcs
Example of a directed walk: 1-2-3-5-4-2-3-5
A walk is closed if its first and last nodes are the same.
A closed walk is a cycle except that it can repeat nodes and arcs.

13. ON CONNECTIVITY
6
1
4
3
7
2
10
8
9
5
There are simple efficient procedures for determining if a graph is
connected.
Here is a graph with two components, that is
maximally connected subgraphs.
4
7
10 9
We will not describe these algorithms, but will do a more general algorithm later in
this lecture

14. MINIMUM COST FLOW PROBLEM
Determine a least cost shipment of a commodity through a network in order to satisfy demands at certain nodes
from available supplies at other nodes. Arcs have capacities and cost associated with them.
Distribution of products
Flow of items in a production line
Routing of cars through street networks
Routing of telephone calls
1
2
3
4
5
6
710 10
-5
-15
5
3
6
4
3 1
2
2
4
6
5

15. MINIMUM COST FLOW PROBLEM (CONTD.)
Mathematical Formulation:
Minimize cx
subjectto
biforeachnodeiN
xuforeacharcijN
ijij
ijA
ij ij
(,)
()
(,)



   
 
x x
ij ji
{j:(j,i)A}{j:(i,j)A}
0
where
Supply nodes (b(i) > 0); Demand nodes (b(i) < 0);
Transhipment nodes (b(i) = 0)
Mass balance constraints (flow in - flow out = supply/demand)
Flow bound constraints (lower and upper bound constraints)
bi
iN
().
 0

16. MINIMUM-COST FLOW PROBLEM

17. •A flow capacity is assigned to each arc, and second, a per-unit cost is specified for shipping along each
arc. These characteristics are shown next to each arc.
•Thus, the flow on arc 2–4 must be between 0 and 4 units, and each unit of flow on this arc costs $2.00.
•The1’s in the figure have been used to denote unlimited flow capacity on arcs 2–3 and 4–5.
•Finally, the numbers in parentheses next to the nodes give the material supplied or demanded at that
node.
•In this case, node 1 is an origin or source node supplying 20 units, and nodes 4 and 5 are destinations
or sink nodes requiring 5 and 15 units, respectively, as indicated by the negative signs.
•The remaining nodes have no net supply or demand; they are intermediate points, often referred to as
transshipment nodes.
•The objective is to find the minimum-cost flow pattern to fulfill demands from the source nodes.
•Such problems usually are referred to as minimum-cost flow or capacitated transshipment problems.

18. SHORTEST PATH PROBLEM
Identify a shortest path from a given source node to a given sink node.
1
2 4
3 5
6
10
25
35
20
15
35
40
30
20
s t
Applications:
Finding a path of minimum length
Finding a path taking minimum time
Finding a path of maximum reliability

19. MAXIMUM FLOW PROBLEM
Determine the maximum flow that can be sent from a given source node to a sink node in a capacitated network.
1
2 4
3 5
6
10
25
35
20
15
35
40
30
20
s t
Determining maximum steady-state flow of:
petroleum products in a pipeline network
cars in a road network
messages in a telecommunication network
electricity in an electrical network

20. MINIMUM SPANNING TREE PROBLEM
Find a spanning tree of an undirected network of minimum cost (or, length).
35
40
25
10
20 15
30
1
2
3
4
5
Constructing highways or railroads spanning several cities
Designing local access network
Making electric wire connections on a control panel
Laying pipelines connecting offshore drilling sites, refineries, and consumer markets

21. NETWORK NOTATION
Network (or graph) G = (N, A)
N : Node Set = {1, 2, 3, 4, 5, 6, 7}
A : Arc Set = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 6), (4, 5), (4, 7), (5, 2), (5, 3), (5, 7), (6, 7)}
1
2
3
4
5
6
7

22. TAILS AND HEAD NODES
1
2
3
4
5
6
7
Tail Node : Node i is the tail node of arc (i, j)
Head Node : Node j is the head node of arc (i, j)
Endpoints : Nodes i and j are endpoints of arc (i, j)
Arc Adjacency List A(i) = {(i, j) : (i, j)  A}
Observe that
|()|Aim
iN 

23. PATHS AND CYCLES
1
2
3
4
5
6
7
Path : A walk without any repetition of nodes.
Directed Path: A directed walk without any repetition of nodes.
Cycle: A closed path that starts and ends at the same node.
Directed Cycle: A directed version of a cycle.
Acyclic Network: A network is acyclic if it contains no directed cycle.

24. NETWORK CONNECTIVITY
Connected Graph: If every pair of nodes is connected by a path.
Strongly Connected Graph: If every pair of nodes is connected by a directed path.
Disconnected Graph: If some pair of nodes is not connected by a path. Maximally
connected sub-graphs of a disconnected graph are called components.
1
2
3
4
5
6
71
2
3
4
5
6
7

25. CUTS
Cut:A cut is a set of arcs whose deletion disconnects
the network into two components S and and no subset
of it has this property. A cut is represented by [S, ].
S
S
1
2
3
4
5
6
7
SS

26. TREES
Tree: A tree is a connected graph that contains no cycle.
1
2
3
4
6
7
2
3
4
6
1
A tree on n nodes contains exactly (n-1) arcs.
A tree has at least two leaf nodes.
Every two nodes of a tree are connected by a unique path.

27. SPANNING TREES
Spanning Tree: A subgraph of a graph which is a tree and spans all nodes of the graph.
1
2
3
4
5
6
7 1
2
3
4
6
75
Forest: A graph that contains no cycle is a forest.
A forest on n nodes and k components has n-k arcs.

28. DIRECTED OUT-TREES AND IN-TREES
Directed-out-tree:A tree in which the unique path in the tree from node s to every other
node is a directed path.
Directed-in-tree: A tree in which the unique path in the tree from any node to node s is a
directed path.
1
2
3
4 5
6
7
8
1
2
3
4 5
6
7
8

29. 29
COMMON NETWORK REPRESENTATIONS
Node-arc incidence matrix
Node-node adjacency matrix
Adjacency list
Forward star representation
Reverse star representation
Forward and reverse star representations

30. Transportation Problem
•A typical transportation problem is shown in Table. 1. It deals with sources
where a supply of some commodity is available and destinations where the
commodity is demanded. The classic statement of the transportation
problem uses a matrix with the rows representing sources and columns
representing destinations. The algorithms for solving the problem are
based on this matrix representation. The costs of shipping from sources to
destinations are indicated by the entries in the matrix. If shipment is
impossible between a given source and destination, a large cost of M is
entered. This discourages the solution from using such cells. Supplies and
demands are shown along the margins of the matrix. As in the example,
the classic transportation problem has total supply equal to total demand.

31. Matrix model of a transportation problem
Fig. Table1.

32. Network flow model of the transportation problem
(Fig.5.)
•Sources are identified as the nodes on the left and destinations on the
right. Allowable shipping links are shown as arcs, while disallowed links
are not included.
Fig. 5.

33. Network flow model of the transportation
problem
•Only arc costs are shown in the network model, as these are the only
relevant parameters.
•All other parameters are set to the default values.
•The network has a special form important in graph theory; it is called a
bipartite network since the nodes can be divided into two parts with all
arcs going from one part to the other.
•On each supply node the positive external flow indicates supply flow
entering the network.
•On each destination node a demand is a negative fixed external flow
indicating that this amount must leave the network.
• The optimum solution for the example is shown in Fig. 6.

34. •Variations of the classical transportation problem are easily handled by
modifications of the network model.
•If links have finite capacity, the arc upper bounds can be made finite.
•If supplies represent raw materials that are transformed into products at the
sources and the demands are in units of product, the gain factors can be used
to represent transformation efficiency at each source.
•If some minimal flow is required in certain links, arc lower bounds can be set
to nonzero values.

35. ASSIGNMENT
There are five machines to be assigned to five jobs. The numbers in the matrix indicate
the cost of doing each job with each machine. Jobs with costs of M are disallowed
assignments. The problem is to find the minimum cost matching of machines to jobs.
Fig.1. Matrix model of the assignment problem

36. •The network model is in Assign. 1. is very similar to the transportation
model except the external flows are all +1 or -1. The only relevant
parameter for the assignment model is arc cost (not shown in the
figure for clarity) ; all other parameters should be set to default
values. The assignment network also has the bipartite structure.
Figure 2. Network model of the assignment problem.

37. Solution
•The solution to the assignment problem as shown in Fig. 3 has a total
flow of 1 in every column and row, and is the assignment that
minimizes total cost.
Figure 3. Solution to the assignment Problem