Network

Models
MAS 101– Management Science
Prepared by: Ross Catherine P. Lero, CPA
Professor: Earl Justine C. Santiago, CPA
 ●Arrangement of paths connected at various
points, through which items move.
●Examples of networks are highway
systems, telephone networks, railroad
Network systems, and cable networks.
●As a management science tool, it provides
a picture of a system and numerous
systems can be easily modeled as
networks. (Network Models)
 ●Shortest Route Possible
Network ●Minimal Spanning Tree
Models Problem
●Maximal Flow Problem
 ●Nodes – junction points or intersections
●Represented in the network diagram by
circles
●Branches – connects the nodes and
Network reflect the flow from one point to
Components another
●Represented in the network diagram by
lines connecting the nodes
●Typically a branch is assigned a value
that represents distance, time, or cost
between nodes.
This is a
Node
The numbers on
a branch could
represent
distance, time
travelled or cost
of moving from
Point A to B

This is a
Branch
Shortest Route
Problems
Determines the shortest distance between point of
origin and several destination points.
 ●For example, the Stagecoach Shipping
Company transports oranges by six trucks
from Los Angeles to six cities in the West
Shortest and Midwest. The different routes
between Los Angeles and the destination
Route cities and the length of time, in hours,
required by a truck to travel each route are
Problem shown on the next slide. The shipping
manager wants to determine the best
routes (minimum travel time) for the
trucks to take to reach their destination.
 {16, 1}
25
2 5
14
16 12 8
35 4 19
Determine 1 15
{35, 1} 7
9 17
shortest route 14
from Node 1 3 22
to each of the {9, 1} 6
Nodes (2 to 7) ● From your origin point, determine the nearest nodes and label it
with the time spent to travel to that node and the preceeding note
where it came from.
● For Node 2, the temporary label must be {16, 1} (16 mins from Node 1)
● For Node 3, the temporary label must be {9, 1} (9 mins from Node 1)
● For Node 4, the temporary label must be {35, 1} (35 mins from Node 1)
 {16, 1}
25
2 5
14
16 12 8
35 4 19
Determine 1 15
{35, 1} 7
9 {24, 3} 17
shortest route 14
from Node 1 3 22
to each of the {9, 1} 6
{31,
Nodes (2 to 7) ● The label with the lowest travel time becomes a permanent
3} label. And
from there, new temporary labels will be created to each closest point.
Node 3 with travel time of 9mins from Node 1 becomes a permanent
label.
● Another temporary label for Node 4 is created. From Node 3, time
travelled to Node 4 is 9+15=24mins (Node 1-3 is 9mins + Node 3-4 is
15mins)
● Node 6 will be temporary labelled as {31, 3} (9+22)
 {16, 1}
25 {41,
2 5 2}
14
16 12 8
35 4 19
Determine 1 15
{35, 1} 7
9 {24, 3} 17
shortest route 14
{28, 2}
from Node 1 3 22
to each of the {9, 1} {31, 6
Nodes (2 to 7) 3}
● Node 2 becomes a permanent label because it has the next
lowest travel time.
● Node 5 will be temporary labelled as {41, 2}
● Another temporary label for Node 4 is created. From Node 2,
time travelled to Node 4 is 16+12=28mins.
 {16, 1}
25 {41,
2 5 {38, 4}
2}
14
16 12 8
35 4 19
Determine 1 15
{35, 1} 7
9 {24, 3} 17
shortest route 14 {43, 4}
{28, 2}
from Node 1 3 22
{41, 4}
to each of the {9, 1} 6 {31,
Nodes (2 to 7) ● Node 4 becomes a permanent label with its lowest3}
travel time
of 24mins from Node 1, passing through Node 3, to Node 4.
● Another temporary label for Node 5 is created. From Node 4,
time travelled to Node 5 is 24+14=38mins.
● Another temporary label for Node 6 is created. From Node 4,
time travelled to Node 6 is 24+17=41mins.
● Node 7 is temporary labelled as {43, 4}
 {16, 1}
25 {41,
2 5 {38, 4}
2}
14
16 12 8
35 4 19
Determine 1 15 {24, 3} 7
9 17
shortest route 14 {43, 4}
from Node 1 3 22 {45, 6}
{41, 4}
to each of the {9, 1} 6 {31,
Nodes (2 to 7) 3}
● Node 6 becomes a permanent label with its lowest travel time
of 31mins from Node 1, passing through Node 3, to Node 6.
● Another temporary label for Node 7 is created. From Node 6,
time travelled to Node 7 is 31+14=45mins.
 {16, 1}
25 {41,
2 5 {38, 4}
2}
14
16 12 8
35 4 19
Determine 1 15 {24, 3} 7
9 17
shortest route 14 {43, 4}
from Node 1 3 22 {45, 6}
{46, 5}
to each of the {9, 1} {31, 6
Nodes (2 to 7) 3}
● Node 5 becomes a permanent label with its lowest travel time
of 38mins from Node 1, passing through Nodes 3 to 4 to
Node 5.
● Another temporary label for Node 7 is created. From Node 5,
time travelled to Node 7 is 38+8=46mins.
 {16, 1}
25
2 5 {38, 4}
14
16 12 8
35 4 19
Determine 1 15 {24, 3} 7
9 17
shortest route 14 {43, 4}
from Node 1 3 22 {45, 6}
{46, 5}
to each of the {9, 1} 6 {31,
Nodes (2 to 7) 3}

●Node 7 becomes a permanent label with its

lowest travel time of 43mins from Node 1,
passing through Nodes 3 to 4 to Node 7.
 {16, 1}
25
2 5 {38, 4}
Determine 16 12
14
8
shortest route 35 4 19
from Node 1 1 {24, 3} 7
15
to each of the 9 17 14 {43, 4}
Nodes (2 to 7) 3 22
{9, 1} 6 {31,
3}
 Point of Origin (Node 1 Time
Path
Therefore, the LA) to Destination travelled
shortest route Node 2 (Salt Lake City) 16 mins 1-2
from Node 1 Node 3 (Pheonix) 9 mins 1-3
to each of the Node 4 (Denver) 24 mins 1-3-4
Nodes (2 to 7) Node 5 (Des Moines) 38 mins 1-3-4-5
is summarized
Node 6 (Dallas) 31 mins 1-3-6
as follows:
Node 7 (St. Louis) 43 mins 1-3-4-7
 The Roanoke, Virginia, distributor of Rainwater Beer
delivers beer by truck to stores in six other Virginia
cities, as shown in the diagram below.
Distance (in miles) between each cities is shown along
each branch. Answer the questions on the next slide.

Activity
 1. How many miles will it take for Rainwater
Beer to distribute its products from
Roanoke to the following cities?
a. Danville
b. Charlottesville
Questions c. Richmond
(submit your
answers in the 2. If a liter of gasoline costing P65 could
Google Forms travel 2.5 miles, how much would it cost
posted) Rainwater Beer to deliver their products to
the following cities?
a. Staunton
b. Petersburg
c. Lynchburg
 2 31 5
85 72
61
7
53 3 117
1 24
88 65 6
137
4
Activity Point of Origin (Node 1 Roanoke) to
Distance travelled
Path
Destination Temp: Labels
Node 2 (Staunton) {85,1}
Node 3 (Lynchburg) {53,1}
Node 4 (Danville) {88,1}
Node 5 (Charlottesville)
Node 6 (Petersburg)
Node 7 (Richmond)
 2 31 5
85 72
61
7
53 3 117
1 24
88 65 6
137
4
Activity Point of Origin (Node 1 Roanoke) to
Distance travelled
Path
Destination Temp: Labels
Node 2 (Staunton) {85,1}
Node 3 (Lynchburg) 53 miles 1-3
Node 4 (Danville) {88,1} {118,3}
Node 5 (Charlottesville) {114, 3}
Node 6 (Petersburg)
Node 7 (Richmond) {170, 3}
 2 31 5
85 72
61
7
53 3 117
1 24
88 65 6
137
4
Activity Point of Origin (Node 1 Roanoke) to
Distance travelled
Path
Destination Temp: Labels
Node 2 (Staunton) 85 miles 1-2
Node 3 (Lynchburg) 53 miles 1-3
Node 4 (Danville) {88,1} {118,3}
Node 5 (Charlottesville) {114, 3} {116,
2}
Node 6 (Petersburg)
Node 7 (Richmond) {170, 3}
 2 31 5
85 72
61
7
53 3 117
1 24
88 65 6
137
4
Activity Point of Origin (Node 1 Roanoke) to
Distance travelled
Path
Destination Temp: Labels
Node 2 (Staunton) 85 miles 1-2
Node 3 (Lynchburg) 53 miles 1-3
Node 4 (Danville) 88 miles 1-4
Node 5 (Charlottesville) {114, 3} {116,
2}
Node 6 (Petersburg) {225, 4}
Node 7 (Richmond) {170, 3}
 2 31 5
85 72
61
7
53 3 117
1 24
88 65 6
137
4
Activity Point of Origin (Node 1 Roanoke) to
Distance travelled
Path
Destination Temp: Labels
Node 2 (Staunton) 85 miles 1-2
Node 3 (Lynchburg) 53 miles 1-3
Node 4 (Danville) 88 miles 1-4
Node 5 (Charlottesville) 114 miles 1-3-5
Node 6 (Petersburg) {225, 4}
Node 7 (Richmond) {170, 3} {186,
5}
 2 31 5
85 72
61
7
53 3 117
1 24
88 65 6
137
4
Activity Point of Origin (Node 1 Roanoke) to
Distance travelled
Path
Destination Temp: Labels
Node 2 (Staunton) 85 miles 1-2
Node 3 (Lynchburg) 53 miles 1-3
Node 4 (Danville) 88 miles 1-4
Node 5 (Charlottesville) 114 miles 1-3-5
Node 6 (Petersburg) {225, 4} {194,
7}
Node 7 (Richmond) 170 miles 1-3-7
 2 31 5
85 72
61
7
53 3 117
1 24
88 65 6
137
4
Activity Point of Origin (Node 1 Roanoke) to
Distance travelled
Path
Destination Temp: Labels
Node 2 (Staunton) 85 miles 1-2
Node 3 (Lynchburg) 53 miles 1-3
Node 4 (Danville) 88 miles 1-4
Node 5 (Charlottesville) 114 miles 1-3-5
Node 6 (Petersburg) 194 miles 1-3-7-6
Node 7 (Richmond) 170 miles 1-3-7
 2 31 5
85 72
61
7
53 3 117
1 24
88 65 6
137
4
Activity Point of Origin (Node 1 Roanoke) to
Destination
Distance travelled
Delivery Cost
= D / 2.5 * 65
Node 2 (Staunton) 85 miles P 2,210
Node 3 (Lynchburg) 53 miles 1,378
Node 4 (Danville) 88 miles 2,288
Node 5 (Charlottesville) 114 miles 2,964
Node 6 (Petersburg) 194 miles 5,044
Node 7 (Richmond) 170 miles 4,420
Minimal
Spanning Tree
Problems
Connects all nodes in a network so that the total
branch lengths are minimized
 ●To demonstrate the minimal spanning tree
problem, we will consider the following
example. The Metro Cable Television Company
is to install a television cable system in a
community consisting of seven towns. Each of
Minimal the suburbs must be connected to the main cable
system. The cable television company wants to
Spanning Tree lay out the main cable network in a way that will
Problem minimize the total length of cable that must be
installed. The possible paths available to the
cable television company (by consent of the
town council) and the feet of cable (in thousands
of feet) required for each path are shown on the
next slide.
 25
2 5
14
16 12 8
35 4 19
1 15 7
9 17 14
Minimal
Spanning Tree 3 22
Problem 6

● The branch between Node 1 and Node 2 represents the

cable path between Town 1 and 2. The branch requires
16,000 feet of cable.
 25
2 5
14
16 12 8
Determine the 35 4 19
minimum 1 15 7
9 17 14
number of feet
of cable 3 22
required to 6
connect all 7 ● You may start at any node in the network. (We will start at
Node 1)
suburbs. ● Select the shortest branch from Node 1 going to an
unconnected node. That is, Node 3.
● Node 1 to 2 = 16,000 feet
● Node 1 to 4 = 35,000 feet
● Node 1 to 3 = 9,000 feet
 25
2 5
14
16 12 8
Determine the 35 4 19
minimum 1 15 7
9 17 14
number of feet
of cable 3 22
required to 6
connect all 7 ● The shortest branch to an unconnected Node is the branch
suburbs. going to Node 4.
● Node 1 to 2 = 16,000 feet
● Node 1 to 4 = 35,000 feet
● Node 3 to 4 = 15,000 feet
 25
2 5
14
16 12 8
Determine the 35 4 19
minimum 1 15 7
9 17 14
number of feet
of cable 3 22
required to 6
connect all 7 ● The shortest branch to an unconnected Node is the branch
going to Node 2.
suburbs. ● Node 1 to 2 = 16,000 feet
● Node 4 to 2 = 12,000 feet
● Node 4 to 5 = 14,000 feet
● Node 4 to 6 = 17,000 feet
● Node 3 to 6 = 22,000 feet
 25
2 5
14
16 12 8
Determine the 35 4 19
minimum 1 15 7
9 17 14
number of feet
of cable 3 22
required to 6
connect all 7 ● The shortest branch to an unconnected Node is the branch going to
Node 5.
suburbs. ● Node 2 to 5 = 25,000 feet
● Node 4 to 5 = 14,000 feet
● Node 4 to 6 = 17,000 feet
● Node 3 to 6 = 22,000 feet
 25
2 5
14
16 12 8
Determine the 35 4 19
minimum 1 15 7
9 17 14
number of feet
of cable 3 22
required to 6
connect all 7 ● The shortest branch to an unconnected Node is the branch
suburbs. going to Node 5.
● Node 4 to 6 = 17,000 feet
● Node 4 to 7 = 19,000 feet
● Node 5 to 7 = 8,000 feet
 25
2 5
14
16 12 8
35 4 19
72,000 feet of 1 15 7
9 17 14
cable is
required to 3 22
connect all 7 6
suburbs. ● The shortest branch to an unconnected Node is the
branch going to Node 6.
● Node 4 to 6 = 17,000 feet
● Node 7 to 6 = 14,000 feet
 2 5
14
12 8
4
72,000 feet of 1 15 7
9 14
cable is
required to 3
connect all 7 6
suburbs. ● Total cable required (in feet) = 9,000 + 15,000 +
12,000 + 14,000 + 8,000 + 14,000 = 72,000
● Try starting in another Node, you will get the same
Spanning tree.
 Minimal
Shortest Route
Spanning Tree
●Represents the shortest
Shortest Route paths between the
origin point and EACH
vs. of the destination ●Shows how to connect
point; all nodes in the
Minimal network so that the
●There will be as many
Spanning Tree routes as there are value in the branches
many destination are minimized.
points (ex. If there are
6 destination points,
there will be 6 routes)
 ●A major hotel chain is constructing a new resort
hotel complex in Greenbranch Springs, West
Virginia. The resort is in a heavily wooded area, and
the developers want to preserve as much of the
natural beauty as possible. To do so, the developers
want to connect all the various facilities in the
complex with a combination walking–riding path
Activity that will minimize the amount of pathway that will
have to be cut through the woods. The network on
the next slide shows possible connecting paths and
corresponding distances (in yards) between the
facilities.
●Determine the path that will connect all the facilities
with the minimum amount of construction and
indicate the total length of the pathway.
Activity
(submit your
answers in the
Google classroom
posted)

●If 1 yard of construction work costs P3,000,

how much would it cost Greenbach to
construct the pathway of the new resort?