Kingfisher School of Business and Finance

Business Mathematics 42 – Management Science I

LESSON 3: CHAPTER 6: DISTRIBUTION AND NETWORK MODELS

TRANSPORATION MODEL
 Deals with the distribution of goods from several points of supply (origin of sources) to a number of points of
demand (destination)
 The transportation problem arises frequently in planning for the distribution of goods and services from several supply
locations to several demand locations. Typically, the quantity of goods available at each supply location (origin) is
limited, and the quantity of goods needed at each of several demand locations (destinations) is known.
 Usual objective in a transportation problem is to minimize the cost of shipping goods from the origins to the
destinations
o OBJECTIVE: Minimize cost of transportation of distribution

TRANSPORTATION ALGORITHM
The transportation algorithm is an iterative procedure in which a solution to a transportation problem is found and
evaluated using a special procedure to determine whether the solution is optimal.
 If it is optimal, the process stops.
 If it is not optimal, a new solution is generated. This new solution is at least as good as the previous one,
and it is usually better. This new solution is then evaluated, and if it is not optimal, another solution is
generated.
 The process continues until the optimal solution is found

Step #1 Set Up A Transportation Model

ILLUSTRATIVE EXAMPLE

Page 1 of 23
RJDC, RMQ
 AN EXAMPLE OF BALANCED PROBLEM (Demand = Supply)
Transportation Model
As reminders.
1. Tukuyin kung alin-alin ang SUPPLY ORIGIN OR POINTS. Sila yung magbibigay ng resources or supply sa mga
destinations. Ang catch is mayroon silang factory/ supply capacity na kaya lang nila mamaintain, kung kaya’t ang
Factory Capacity ang tinatawag natin na SUPPLY CONSTRAINTS
2. Tukuyin din kung alin-alin ang DESTINATION POINTS. Sila naman yung may demand na kailangang imeet ng
mga supply origins. Ang kanilang warehouse requirement ay tumutukoy sa DEMAND Constraints.
3. Yung mga nasa Gray shade, sila naman ung cost of shipping na assign from the origin to the destination.
4. In Association sa Lesson 1. Ang Objective Function natin sa Transportation problem ay to MINIMIZE COST of
transportation of distribution. Na subject to Demand and Supply Constraints.
5. Next ding icheck if ano ang status ng DEMAND at SUPPLY, Balanced or Equal ba OR Unbalanced ?

Step #2 Develop an INITIAL SOLUTION through NORTHWEST CORNER RULE

Page 2 of 23
RJDC, RMQ
Following the three steps of Northwest Corner Rule
1.0
AN INITIAL SOLUTION WOULD BE LIKE THIS

TATANDAAN!
Ang bilang ng nalagyan na box ay dapat nagcocorrespond sa ROW + COLUMN – 1 or m + n – 1
Where m refers to # of supply points
n refers to # of demand points
1.1

Once plotted, compute for the initial solution which in this case amounts to P4,200
TATANDAAN!
A feasible solution is reached when all demand and supply constraints are met. Candidate for optimal solution. Pero
tatandaan, not all feasible solution is an optimal solution; but an optimal solution is always one of the feasible solutions.
TATANDAAN!
This route-loading method totally ignored the costs of shipping over each of the routes. Kaya need ievaluate if optimal
solution ba or hindi through computing improvement index

Page 3 of 23
RJDC, RMQ
Step #3 Calculate an IMPROVEMENT INDEX for each empty cell using the STEPPING
STONE METHOD : Finding a Least Cost Solution

Approach: To evaluate the cost-effectiveness of shipping goods via transportation routes

not currently in the solution.

Note: The stepping-stone method involves testing each unused route to see if shipping one unit on that route
would increase or decrease total costs.

Each unused shipping route (or square) in the transportation table is tested by asking the following question: “What
would happen to total shipping costs if one unit of our product (in our example, one
desk) were tentatively shipped on an unused route?”

Step 1 and 2. Closed paths are used to trace alternate plus or minus signs. Note that every row and every column will have
either two changes or no changes.
Step 3. How to assign +/-? Para saan? To avoid violating constraints. It is as if distributing “what if” shipments.

Page 4 of 23
RJDC, RMQ
Step 4. Improvement index computation involves adding costs in squares with plus signs and subtracting costs in squares
with minus signs.
A path can go through any box but can only turn at a box or cell that is occupied.

Step 5. If the Improvement Index is greater than or equal to zero: OPTIMAL SOLUTION
If the Improvement Index is less than 0 : It is still possible to improve the current solution

TATANDAAN! Sa Stepping Stone Method, sa occupied cells sya magsstep.

IMPROVEMENT INDEX SOLUTION

2.0
No quantities
All of these must
D to B DB to DA to EA to EB 4–5+8–4 3
be positive to be
D to C DC to DA to EA to EB to FB to FC 3 –5 + 8 – 4 +7 – 5 4
an optimal
E to C EC to EB to FB to FC 3–4 +7–5 1
solution
F to A FA to FB to EB to EA 9–7+4–8 -2

Ngayon, may isang negative, indication ito na pwede pang mag-improve ng transportation flow. Kung saan may negative,
iyon ang i-iimprove. In this case F to A.
TATANDAAN, in the case na what if may more than 2 ang may negative signs, pipiliin ung value na may largest
improvement. Anong ibig sabihin? For example ung index ng isa ay -2, yung index ng isa ay -6. Mas pipiliin mong i-
improve yung index na may -2 over doon sa -6.

From this, gagawa ng bagong transportation model

The next step, then, is to ship the maximum allowable number of units (or desks, in our case) on the new
route (Fort Lauderdale to Albuquerque). What is the maximum quantity that can be shipped on the money-
saving route? That quantity is found by referring to the closed path of plus signs and minus signs drawn for the
Page 5 of 23
RJDC, RMQ
route and selecting the smallest number found in those squares containing minus signs. To obtain a new
solution, that number is added to all squares on the closed path with plus signs and subtracted from all squares
on the path assigned minus signs. All other squares are unchanged.

Paano mag-reallocate? Tignan ung smallest number doon sa closed path ng unused route na need i-improve. Tas yung
quantity ang gagamitin pang plus or minus.

In this case 100 ang smallest number. Yun ang maximum allowable number of units.
Bale to reallocate.
From E to A, 200 -100 = 100,
From E to B, 100 + 100 = 200 ,
From F to A, +100 = 100.
From F to B 100-100 = 0

Sa Computation na ito, ito ang bagong model

2.1

Then compute for the Improvement Index again and Its initial Solution
Page 6 of 23
RJDC, RMQ
2.2

HINDI PA RIN OPTIMAL SO, ULIT ung PROCESS. I-improve si E to C

In this case 100 ang smallest number ulit. Yun ang maximum allowable number of units.
Bale to reallocate.
From E to C, +100 = 100,
From E to A, 100 - 100 = 0 ,
From F to A, 100+100 = 200
From F to C 200-100 = 100
2.3

Page 7 of 23
RJDC, RMQ
2.4

OPTIMAL SOLUTION 3,900

TRANSPORTATION MODEL: UNBALANCED TRANSPORTATION PROBLEMS

 Situation occurring quite frequently in real-life problems is the case in which total Demand ≠ total Supply
 In the event that total supply is greater than total demand, Supply > Demand, a dummy destination (warehouse),
with demand exactly equal to the surplus, is created.
 If total demand is greater than total supply, Demand > Supply, we introduce a dummy source (factory) with a supply
equal to the excess of demand over supply.

Dummy Destination Dummy Source

added to a transportation table artificial destination artificial source
Supply > Demand Demand > Supply
kulang si Demand kulang si Supply
transportation cost zero zero
set so that total supply and demand are equal.

Page 8 of 23
RJDC, RMQ
Dummy Rows or Columns  Extra rows or columns added in order to “balance” an assignment problem so that the
number of rows equals the number of columns.

DEMAND < SUPPLY

Step #1 Set Up A Transportation Model

UNBALANCED D < S : NEED MAGDAGDAG NG DUMMY DESTINATION
a dummy destination (warehouse), with demand exactly equal to the surplus, is created.

soooo

THEN SAME PROCESS

Page 9 of 23
RJDC, RMQ
STEP 2: INITIAL SOLUTION

SO 50 as the maximum allowable

Results to Dummy Destination (DD)

Alternative: D to DD = 0 - 5 + 8 - 3 + 5 - 0 = 5 F to A = 9 - 8 + 3 - 5 = - 1

Page 10 of 23
RJDC, RMQ
Alternative: D to DD = 0 – 0 + 9 – 5 = 2

DEMAND > SUPPLY

Page 11 of 23
RJDC, RMQ
Step #1 Set Up A Transportation Model
UNBALANCED D >S : NEED MAGDAGDAG NG DUMMY SOURCE
with a supply equal to the excess of demand over supply.

R + C – 1 = 6 SATISFIED PA
Same process.
Look for the Initial Solution or Northwest Corner Method, and test for Improvement Index using Stepping Stone.

Page 12 of 23
RJDC, RMQ
FIRST SOLUTION

Choose the lowest negative value if madaming negative na lumabas in a stepping stone

SECOND SOLUTION

Resulted to degeneracy table

DEGENERACY: When the number of occupied routes is
less than this, the solution is called degenerate
Diba tinetest natin lagi na ung occupied cells ay equal sa R + C -1. Pag less than dito,
Degeneracy yung table.

 Babalik sa Northwest method and maglalagay ng value of 0 which is whether DB or DC.

To handle degenerate problems, we create an artificially occupied cell—that is, we place a zero (representing a fake
shipment) in one of the unused squares and then treat that square as if it were occupied. Para if pupunta na sa stepping
stone, pwedeng makadaan doon.

QUESTION, saan maglalagay ng “as if occupied” 0? Doon sa either cells na dapat pag nilagay mo ay makakapagclose ng
path na needed para sa stepping stone.

If DB is = 0 If DC = 0

Magkukulang ng 50 yung idedeliver kay A as it is a dummy sources

TRANSPORTATION MODEL: DEGENERACY

 R+C-1 is not satisfied

Page 13 of 23
RJDC, RMQ
 Degeneracy occurs when the number of occupied squares or routes in a transportation table solution is less than the
number of rows plus the number of columns minus 1
 Indicates that one blank value in a stepping stone will go dead end and hindi na makakabalik
 Thus, need to assume a zero-quantity using Northwest method. The most upper left ang lalagyan para parehas or
unified sa lahat ng problem

Number of Inputs = # of Columns + # of Rows – 1

FIRST: R + C -1 = 3 + 3 -1 = 5

SECOND:

THIRD

ASSIGNMENT PROBLEM
 An assignment problem can be viewed as a transportation problem in which the capacity from each source (or person
to be assigned) is 1 and the demand at each destination (or job to be done) is 1.
 An assignment problem is equivalent to a transportation problem with each supply and demand equal to 1.
 1:1 Ratio bawal more than 1
 involve determining the most efficient assignment of people to projects, sales people to territories, auditors to
companies for audits, contracts to bidders, jobs to machines, heavy equipment (such as cranes) to construction jobs,
and so on.

Page 14 of 23
RJDC, RMQ
 Objective is most often to minimize total costs or total time of performing the tasks at hand.
 One important characteristic of assignment problems is that only one job or worker is assigned to one machine or
project
 Generally, the rows contain the objects or people we wish to assign, and the columns comprise the tasks or
things we want them assigned to. The numbers in the table are the costs associated with each particular
assignment.

ILLUSTRATIVE EXAMPLE

Page 15 of 23
RJDC, RMQ
HUNGARIAN METHOD and the ASSIGNMENT METHOD/ ALGORITHM

Page 16 of 23
RJDC, RMQ
ASSIGNMENT ALGORITHM
1. Find the opportunity cost table
(Subtracting the smallest number in each row)  laging mauuna dapat
(Subtracting the smallest number in each column)
2. Test the table to see whether an optimal assignment can be made.
 Line is equal to the number of row/columns  If there is 3 column dapat may 3 row din
 Pag mag iislash dapat don sa may zero and matamaan agad yung dalawang zero to minimize the number of
lines bawal yung blackout
3. Revised the opportunity table if not satisfied and follow step 2.
 Use Hungarian Method through those na di pa na naiislash

The Hungarian method of assignment  provides us with an efficient means of finding the optimal solution without
having to make a direct comparison of every option. It operates on a principle of matrix reduction, which means that by
subtracting and adding appropriate numbers in the cost table or matrix, we can reduce the problem to a matrix of
opportunity costs

EXAMPLE:

Page 17 of 23
RJDC, RMQ
Opportunity Table = Rows Value – Lowest Row Value

By Row
Row A: Smallest = 6 11 – 6 , 14 – 6, 6 -6 = 5,8,0
Row B: Smallest = 8 8 -8, 10 -8, 11 -8
Row C Smallest = 7 9 – 7 , 12 – 7, 7-7

By Column

Pag mag iislash dapat don sa may zero and matamaan agad yung dalawang zero to minimize the lines
There are only 2 lines and di nameet yung 3. Minimize the number of lines bawal yung blackout

Hungarian Method
 Use it to those na di pa naiislash which are 5,6,2 and 3
 Choose the lowest which is 2 and subtract it to the others
 5 – 2 , 6 -2, 2 – 2 , 3 – 2
 Yung may value na naislash iaadd don yung lowest kanina na which is 2 resulting to 2 + 3 = 5

Optimal Solution = P25

Satisfied na yung 3 lines = 3 rows and 3 columns. The zeroes are the optimal solutions to be assigned
A is assigned to project 3
B may either be assigned to project 1 or 2
C may either be assigned to project 1 or 3

In assigning, choose the first one who have no choice

A is assigned to project 3 at P6. Thus, project 3 is no longer available
Between B and C, C has no choice. Thus, C is assigned to Project 1 at P9
B is assigned to project 2 at P10
NOTE: In solving larger problems, however, it is best to rely on a more systematic approach to making valid assignments.
One such way is first to select a row or column that contains only one zero cell. Such a situation is found in the first row

Page 18 of 23
RJDC, RMQ
 NETWORK MODELS
 Networks  used to model a wide variety of problems
o Network Models  Find the shortest linkage or connection between points

1. Minimal Spanning Tree Technique

The minimal spanning tree technique determines the path through the network that connects all the points
while minimizing total distance. When 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,
and so on, in a way that minimizes the total distance or length of power lines or water pipes

2. Maximal Flow Technique

The maximal-flow technique finds the maximum flow of any quantity or substance through a network. This
technique can determine, for example, the maximum number of vehicles (cars, trucks, and so forth) that can go
through a network of roads from one location to another.
3. Shortest-route Technique
The 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.

TERMINOLOGY
The points on the network are referred to as nodes. Typically these are presented as circles, although sometimes squares
or rectangles are used for the nodes. The lines connecting the nodes are called arcs.

1. MINIMAL SPANNING TREE TECHNIQUE

 Involves connecting all the points of a network together while minimizing the distance between them
 Can have more than 1 optimal solution

STEPS
1) Select any node in the network
2) Connect this node to the nearest node that minimizes the total distance.
3) Considering all of the nodes that are connected, find and connect the nearest node that is not connected. If there is a
tie for the nearest node, select one arbitrarily. A tie suggests there may be more than one optimal solution.
4) Repeat the third step until all the nodes are connected

EXAMPLE:
The minimal-spanning tree technique involves connecting all the points of a network together while minimizing
the distance between them. It has been applied, for example, by telephone
companies to connect a number of phones together while minimizing the
total length of telephone cable. Let us consider the Lauderdale
Construction Company, which is currently developing a luxurious housing
project in Panama City Beach, Florida. Melvin Lauderdale, owner and
president of Lauderdale Construction, must determine the least expensive
way to provide water and power to each house. The network of houses is
shown in Figure 11.1. As seen in Figure 11.1, there are eight houses on the
gulf. The distance between each house in hundreds of feet is shown on the
network. The distance between houses 1 and 2, for example, is 300 feet.
(The number 3 is between nodes 1 and 2.) Now, the minimal spanning tree
technique is used to determine the minimal distance that can be used to
connect all of the nodes
Page 19 of 23
RJDC, RMQ
 Minimize total length of cable 1
 Always start at 1 given na madaming solution

Connected  cable is connected to houses

Unconnected  number of houses kung sino ang hindi pa binibigyan ng connectiion
Closest  alin ang closest sakanya; choose the smallest number if more than 1
Art selected  distance na meron like house 1 to 4; always start sa maliit na number;
Arc Length  ganon kahaba yung distance 1 to 3 has 2 arc length
Total Distance  distance between houses, like house 1 to 5; cumulative sum of Arc Length

Connected Unconnected Closest Arc Selected Arc Length Total Distance

(House #) (House #) (House #) (House #) (100 ft each) Cumulative
1 2,3,4,5,6,7,8 3 1 to 3 2 2
1,3 2,4,5,6,7,8 4 3 to 4 2 4
1,3,4, 2,5,6,7,8 2,6 1 to 2 3 7
1,2,3,4 5,6,7,8 5,6 2 to 5 3 10
1,2,3,4,5 6,7,8 6 3 to 6 3 13
1,2,3,4,5,6 7,8 8 6 to 8 1 14
1,2,3,4,5,6,8 7 7 7 to 8 2 16 feet
16 x 100 feet = 1600 feet
1: Closest is 3 kasi distance is only 2 compared to those na ibang closest sakanya
1,3: Total distance is the sum of all arc lengths

1st 2nd 3rd 4th 5th 6th

EXAMPLE 2:
Roxie LaMothe, owner of a large horse breeding farm near Orlando, is
planning to install a complete water system connecting all of the various stables
and barns. The location of the facilities and the distances between them is given in
the network shown in Figure. Roxie must determine the least expensive way to
provide water to each facility. What do you recommend?

Connected Unconnected Closest Arc Selected Arc Length Total Distance

1 2,3,4,5,6,7,8 3 1 to 3 8 8
1,3 2,4,5,6,7,8 2 1 to 2 10 18
1,2,3 4,5,6,7,8 4,5 1 to 4 12 30
1,2,3,4 5,6,7,8 7 4 to 7 8 38
1,2,3,4,7 5,6,8 6 6 to 7 10 48
1,2,3,4,6,7 5,8 8 6 to 8 9 57
1,2,3,4,6,7,8 5 5 5 to 6 10 67

2. MAXIMAL FLOW TECHNIQUE

 Involves determining the maximum amount of material that can flow from one point (the source) to another (the sink)
in a network.
 Maximize amount of materials that can flow kasi hindi lahat nadadaanan due to varying sizes

Page 20 of 23
RJDC, RMQ
 Sa isang route pwedeng dalawang truck yung isa hindi

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. Connect this node to the nearest node that minimizes the total distance.
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. Repeat the third step until all the nodes are
connected.
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.

From 1 going to 2. And the maximum of 2 is 2 then pipiliin si 2

EXAMPLE
Waukesha, a small town in Wisconsin, is in the process of
developing a road system for the downtown area. Bill
Blackstone, one of the 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
 From west (1) to east (6)
 Will choose 1 route
 Pwedeng 1,2,6 or 1,4,6 or 1,3,5,6

Nadaanan (Deduct Hindi nadaanan;

Route Maximum
Max) Reverse (Add max)
Route 2 to 6: 2-2=0 Route 6 to 2: 2 + 2 = 4
1 to 2 to 6 2
Route 1 to 6: 3-2 = 0 Route 2 to 1: 1 + 2 = 3
4 to 6: 1 – 1 = 0 1+1=2
1 to 4 to 6 1
1 to 4: 2 - 1 = 1 0+1=1
1 to 3: 10 – 2 = 8 0+ 2 = 2
1 to 3 to 5
2 3 to 5: 2 – 2 = 0 1+2=3
to 6
5 to 6: 6 – 2 = 4 0+2=2
5
1 to 2  maximum na pwede dumaan is 3;
2 to 1  pwedeng dumaan is 1
2 to 6  maximum is 2 6 to 2  maximum is 2
1 to 4  max is 2 4 to 1  max is 0

Maximum 1 to 2 to 6; route 1 to2 has 3 maximum pero pagdating sa 2 to

6, 2 na lang maximum so maiiwan yung isang truck kaya ang maximum is
2

EXAMPLE
PetroChem, an oil refinery located on the Mississippi River south of Baton
Rouge, Louisiana, is designing a new plant to produce diesel fuel. Figure 11.17
shows the network of the main processing centers along with the existing rate
Page 21 of 23
RJDC, RMQ
of flow (in thousands of gallons of fuel). The management at PetroChem would like to determine the maximum amount of
fuel that can flow through the plant, from node 1 to node 7.
Route Maximum
1 to 2 to 4 to 7 3
1 to 5 to 7 5
1 to 3 to 6 to 7 1
5

3. SHORTEST – ROUTE TECHNIQUE

 The objective of the shortest-route problem is to find the shortest distance from one location to another.
 In a network, this often involves determining the shortest route from one node to each of the other nodes

STEPS
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 last distance at the ending node will be the
distance of the shortest route. You should note that the distance placed in the box by each node is the shortest route to
this node. These distances are used as intermediate results in finding the next-nearest node

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
in Figure.

Shortest Route: 1 to 2 to 3 to 5 to 6 Shortest Distance = 100 + 50 + 40 + 100 = 290

2 to 5 = 100 vs 2 to 3 to 5 = 50+40 = 90
NOTE: IF may same distance kahit alin don ang piliin okay lang.

EXAMPLE 2:
The network of Figure shows the highways and cities surrounding
Leadville, Colorado. Leadville Tom, a bicycle helmet manufacturer, must
transport his helmets to a distributor based in Dillon, Colorado. To do this,
he must go through several cities. Tom would like to find the shortest way
to get from Leadville to Dillon. What do you recommend?

Shortest Route: 1 to 2 to 5 to 7 Shortest Distance = 8 + 14 + 12 = 34

EXAMPLE 3:

Page 22 of 23
RJDC, RMQ
 Page 23 of 23
RJDC, RMQ