Create Presentation
Download Presentation

Download Presentation
## Chapter 6: Network Models

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**Network Models**• There is a many of operation research situation is modeled and solved as network ( nodes can connected by branches) • There are five network models algorithms 1- Minimal spanning tree 2- shortest-route algorithms 3- maximum-flow algorithms 4- minimum cost capacitated network algorithms 5- Critical path( CPM) algorithms**Network Models (CONT.)**1-Design of an offshore gas pipeline network connecting wellheads in gulf of Mexico to an inshore delivery points.; the objective of the model is minimize the cost constructing the pipeline. • The situation represented as Minimal spanning tree. 2- Determination of the shortest route between two cities in a network of roads. • This situation is shortest-route algorithms**Network Models (CONT.)**3- determination the maximum capacity (in ton per year) of a coal slurry pipeline network • This situation is maximum flow algorithms 4- determination of the minimum-cost flow schedule from oil field to refineries through a pipeline network. • This situation is minimum-cost capacitated network algorithms**Network Models (CONT.)**5- determination the time schdule (start and completion date) for activities • This situation is (CPM) algorithms**Network definitions**• A network consist of set of nodes linked by arcs ( or branches) • The notion for describing a network is (N, A) where: • N is set of nodes • A set of arc**Network definitions (cont.)**• Example • Flow : the amount sent from node i to node j, over an arc that connects them. 3 5 1 2 4 N ={ 1,2,3,4,5} A={(1,2), (1,3),(2,3),(2,5),(3,4),(3,5),(4,2),(4,5)}**Network definitions (cont.)**• Directed/undirected arcs : • when flow is allowed in one direction the arc is directed; (that means allow positive flow in one direction and zero flow in the opposite direction) • When flow is allowed in two directions, the arc is undirected. • Path : sequence of distinct arcs that join two nodes through other nodes regardless of the direction of flow in each arcs • The nodes are said to be connected if there is a path between them.**Network definitions (cont.)**• Cycle : a path starting at a certain node and returning to the same node without using any arc twice. (or connects a node to itself through other nodes) Example: • (2,3),(3,5),(5.2) form of loop • Cycle is directed if it consists of directed path (2,3),(3,4) and( 4,2) 3 5 1 2 4**Network definitions (cont.)**• Tree : is connected network that may involve only a subset of all nodes of network without cycle. • Spanning tree : a tree that connects all the nodes in a network with no cycle( it consists of n -1 arcs). 3 5 1 1 1 3 3 2 4 2 2 5 Spanning Tree Tree 4**Minimal Spanning tree**• It deals with linking the nodes of network, directly or indirectly, using shortest length of connecting branches. • The typical application occurs in construction of paved roads that link several towns.**Minimal Spanning tree**• The step of procedure are given as follows: • Let N={ 1,2,…n} set of nodes • Ck= set of nodes that have been permanently connected at iteration K • Ck`= set of nodes as yet to be connected permanently. • Step 0: set C0= 0, C0`=N • Step 1: start with any node I; set C1={i}, C1`=N-{i} • General step: selected node j in unconnected set Ck-1` that yield in shortest arcs to a node in the connected set . Link j permanently to Ck-1 and remove it from Ck-1` - If the set of unconnected nodes is empty stop. Otherwise set k=K+1 and repeat the step**Example (cont.)**• Midwest TV cable company is in the process of providing cable service to five new housing development service areas. 3 2 5 6 4 1 9 1 5 3 10 7 5 6 8 4 3**Example (cont.)**• The algorithms start at node 1 3 2 5 6 4 1 9 1 5 3 10 7 5 6 8 4 3**Example (cont.)**• Iteration 1 C1 ` 3 2 5 6 4 1 9 C1 1 5 3 10 7 5 6 8 4 3**Example (cont.)**C1 ` 3 2 5 6 4 1 9 C1 1 5 3 10 7 5 6 8 4 3**Example (cont.)**3 2 5 C2 6 4 1 9 1 5 3 10 7 5 6 8 4 3**Example (cont.)**C2 ` 3 3 2 2 5 5 C2 6 6 4 4 1 1 9 9 1 1 5 5 3 3 10 10 7 7 5 5 6 6 8 8 4 4 3 3**Example (cont.)**• iteration2 C2 ` 3 2 C2 5 6 4 1 9 1 5 3 10 7 5 6 8 4 3**Example (cont.)**C2 ` 3 2 C2 5 6 4 1 9 1 5 3 10 7 5 6 8 4 3**Example (cont.)**3 3 2 2 C3 5 5 6 6 4 4 1 1 9 9 1 1 5 5 3 3 10 10 7 7 5 5 6 6 8 8 4 4 3 3 C3 `**Example (cont.)**• iteration3 3 2 C3 5 6 4 1 9 1 5 3 10 7 5 6 8 4 3 C3 `**Example (cont.)**3 2 C3 5 6 4 1 9 1 5 3 10 7 5 6 8 4 3 C3 `**Example (cont.)**3 3 2 2 C4 5 5 6 6 4 4 1 1 9 9 1 1 5 5 3 3 10 10 7 7 C4 ` 5 5 6 6 8 8 4 4 3 3**Example (cont.)**• iteration4 3 2 C4 5 6 4 1 9 1 5 3 10 7 C4 ` 5 6 8 4 3**Example (cont.)**3 2 C4 5 6 4 1 9 1 5 3 10 7 C4 ` 5 6 8 4 3**Example (cont.)**C5 3 3 2 2 5 5 6 6 4 4 1 1 9 9 C5 ` 1 1 5 5 3 3 10 10 7 7 5 5 6 6 8 8 4 4 3 3**Example (cont.)**• iteration5 C5 3 2 5 6 4 1 9 C5 ` 1 5 3 10 7 5 Alternate links 6 8 4 3**Example (cont.)**3 C5 2 5 6 4 1 9 C5 ` 1 5 3 10 7 5 Alternate links 6 8 4 3**Example (cont.)**3 2 5 6 4 1 9 1 5 3 10 7 5 6 8 4 3**Example (cont.)**• Summery of solution**Example 2**• Apply minimal spanning tree D 7 4 B 5 9 F 2 C 8 A 8 3 7 E**Solution**D D 7 7 4 4 B B 5 5 9 9 F F 2 2 C C 8 8 A A 8 8 3 3 7 7 E E**Solution (cont.)**D D 7 7 4 4 B B 5 5 9 9 F F 2 2 C C 8 8 A A 8 8 3 3 7 7 E E**Solution (cont.)**D D 7 7 4 4 B B 5 5 9 9 F F 2 2 C C 8 8 A A 8 8 3 3 7 7 E E**Example 3**4 H 4 F 1 9 J 3 5 B 9 I 2 7 9 6 10 4 E 8 2 G 9 C A 3 8 9 18 9 D**Solution**4 H 4 F 1 9 J 3 5 B 9 I 2 7 6 10 4 E 8 2 G 9 C A 3 8 9 18 9 D**Solution (cont.)**4 H 4 F 1 9 J 3 5 B 9 I 2 7 6 10 4 E 8 2 G 9 C A 3 8 9 18 9 D**Solution (cont.)**4 H 4 F 1 9 J 3 5 B 9 I 2 7 6 10 4 E 8 2 G 9 C A 3 8 9 18 9 D**Solution (cont.)**4 H 4 F 1 9 J 3 5 B 9 I 2 7 6 10 4 E 8 2 G 9 C A 3 8 9 18 9 D**Solution (cont.)**4 H 4 F 1 9 J 3 5 B 9 I 2 7 6 10 4 E 8 2 G 9 C A 3 8 9 18 9 D**Solution (cont.)**4 H 4 F 1 9 J 3 5 B 9 I 2 7 6 10 4 E 8 2 G 9 C A 3 8 9 18 9 D**Solution (cont.)**4 H 4 F 1 9 J 3 5 B 9 I 2 7 6 10 4 E 8 2 G 9 C A 3 8 9 18 9 D**Solution (cont.)**4 H 4 F 1 9 J 3 5 B 9 I 2 7 6 10 4 E 8 2 G 9 C A 3 8 9 18 9 D**Solution (cont.)**4 H 4 F 1 9 J 3 5 B 9 I 2 7 6 10 4 E 8 2 G 9 C A 3 8 9 18 9 D**Solution (cont.)**4 H 4 F 1 9 J 3 5 B 9 I 2 7 6 10 4 E 8 2 G 9 C A 3 8 9 18 9 D**Shortest- Route problem**• The shortest route problem determines the shortest route between a source and destination. • There are two algorithms to solve shortest-route problems: • 1- Dijkstra’s algorithm that design to determine the shortest routes between the source node every other node in the network • 2- Floyd’s algorithms is general because it allow the determination of the shortest route between any two node in network**Dijkstra’a algorithm**Step0: label the source node(node1) with the permanent label [0,--]. Set i=1 Stepi= (a) compute the temporary labels[ui+dij,i] for each node j that can be reached through node i. provided j is not permanently label. If node j is already label with [uj,k] through another node k and if ui+dij< uj, replace [uj,k] with [ ui+ dij, i] (b) if all node have premanent label stop. Otherwise select the label [Ur,s] having the shortest distance (=ui) among all temporary label. Set i=r and repeat step i**Example**• The figure give the route and their length in miles between city 1 and four other cities. Determine the shortest route between city 1 and each of the remaining four cities. 15 2 4 100 50 20 10 1 60 3 5 30