Quantitative Analysis for

Management
Thirteenth Edition, Global Edition

Module 8
Transportation, Assignment,
and Network Algorithms

Copyright © 2018 Pearson Education, Ltd. All Rights Reserved

 Introduction
■ In this chapter we will explore two special
linear programming models
■ The transportation model
■ The assignment model
■ Because of their structure, they can be
solved more efficiently than the simplex
method
■ These problems are members of a
category of LP techniques called network
flow problems
 Introduction
■ Transportation model
■ The transportation problem deals with the
distribution of goods from several points of
supply (sources) to a number of points of
demand (destinations)
■ Usually we are given the capacity of goods at
each source and the requirements at each
destination
■ Typically the objective is to minimize total
transportation and production costs
 Introduction
■ Example of a transportation problem in a network
format
Factories Warehouses
(Sources) (Destinations)

100 Des Albuquerqu 300

Units Moines e Units

300 Evansvill Bosto 200

Units e n Units

300 Fort Clevelan 200

Units Lauderdale d Units

Capacitie Shipping Requirement

s Routes s

Figure
10.1
 Introduction
■ Assignment model
■ The assignment problem refers to the class of
LP problems that involve determining the most
efficient assignment of resources to tasks
■ The objective is most often to minimize total
costs or total time to perform the tasks at hand
■ One important characteristic of assignment
problems is that only one job or worker can be
assigned to one machine or project
 Introduction
■ Special-purpose algorithms
■ Although standard LP methods can be used to
solve transportation and assignment problems,
special-purpose algorithms have been
developed that are more efficient
■ They still involve finding and initial solution
and developing improved solutions until an
optimal solution is reached
■ They are fairly simple in terms of computation
 Introduction
■ Streamlined versions of the simplex method are
important for two reasons
1 Their computation times are generally 100 times faster
2 They require less computer memory (and hence can
permit larger problems to be solved)
■ Two common techniques for developing initial
solutions are the northwest corner method and
Vogel’s approximation
■ The initial solution is evaluated using either the
stepping-stone method or the modified
distribution (MODI) method
■ We also introduce a solution procedure called the
Hungarian method, Flood’s technique, or the
reduced matrix method
 Setting Up a Transportation Problem

■ The Executive Furniture Corporation

manufactures office desks at three locations:
Des Moines, Evansville, and Fort Lauderdale
■ The firm distributes the desks through regional
warehouses located in Boston, Albuquerque,
and Cleveland
■ Estimates of the monthly production capacity of
each factory and the desks needed at each
warehouse are shown in Figure 10.1
 Setting Up a Transportation Problem

■ Production costs are the same at the three

factories so the only relevant costs are shipping
from each source to each destination
■ Costs are constant no matter the quantity
shipped
■ The transportation problem can be described as
how to select the shipping routes to be used and
the number of desks to be shipped on each route
so as to minimize total transportation cost
■ Restrictions regarding factory capacities and
warehouse requirements must be observed
 Setting Up a Transportation Problem

■ The first step is setting up the transportation

table
■ Its purpose is to summarize all the relevant data
and keep track of algorithm computations

Transportation costs per desk for Executive Furniture

TO
FROM ALBUQUERQUE BOSTON CLEVELAND
DES MOINES $5 $4 $3

EVANSVILLE $8 $4 $3

FORT LAUDERDALE $9 $7 $5

Table 10.1
 Setting Up a Transportation Problem

■ Geographical locations of Executive Furniture’s

factories and warehouses

Bosto
n

Clevelan
d Factor
y
Des
Moines
Evansto Warehouse
n
Albuquerqu
e

Fort
Lauderdale
Figure
10.2
 Setting Up a Transportation Problem

Des Moines
■ Transportation table for Executive Furniture capacity
constraint

TO WAREHOUSE WAREHOUSE WAREHOUSE

AT AT AT FACTORY
FROM ALBUQUERQUE BOSTON CLEVELAND CAPACITY
$
DES MOINES $5 $4
3 100
FACTORY

$
EVANSVILLE $8 $4
3 300
FACTORY

FORT $
$9 $7
LAUDERDALE 5 300
FACTORY
Cell representing a
Table 10.2
WAREHOUSE source-to-destination
Cost of shipping 300 200
1 unit from Cleveland Total supply
200 700
REQUIREMENTS and demand (Evansville to
Fort Lauderdale factory to warehouse Cleveland) shipping
Boston warehouse demand assignment that could
be made
 Setting Up a Transportation Problem

■ In this table, total factory supply exactly

equals total warehouse demand
■ When equal demand and supply occur, a
balanced problem is said to exist
■ This is uncommon in the real world and
we have techniques to deal with
unbalanced problems
 Developing an Initial Solution:
Northwest Corner Rule
■ Once we have arranged the data in a table, we
must establish an initial feasible solution
■ One systematic approach is known as the
northwest corner rule
■ Start in the upper left-hand cell and allocate
units to shipping routes as follows
1 Exhaust the supply (factory capacity) of each row
before moving down to the next row
2 Exhaust the demand (warehouse) requirements of
each column before moving to the right to the next
column
3 Check that all supply and demand requirements are
met.
■ In this problem it takes five steps to make the
initial shipping assignments
 Developing an Initial Solution:
Northwest Corner Rule
1 Beginning in the upper left hand corner, we
assign 100 units from Des Moines to
Albuquerque. This exhaust the supply from Des
Moines but leaves Albuquerque 200 desks short.
We move to the second row in the same column.
TO ALBUQUERQUE BOSTON CLEVELAND FACTORY
FROM (A) (B) (C) CAPACITY

DES MOINES $5 $4 $3
100 100
(D)

EVANSVILLE $8 $4 $3
300
(E)

FORT $9 $7 $5
300
LAUDERDALE (F)

WAREHOUSE
300 200 200 700
REQUIREMENTS
 Developing an Initial Solution:
Northwest Corner Rule
2 Assign 200 units from Evansville to Albuquerque.
This meets Albuquerque’s demand. Evansville
has 100 units remaining so we move to the right
to the next column of the second row.

TO ALBUQUERQUE BOSTON CLEVELAND FACTORY

FROM (A) (B) (C) CAPACITY

DES MOINES $5 $4 $3
100 100
(D)

EVANSVILLE $8 $4 $3
200 300
(E)

FORT $9 $7 $5
300
LAUDERDALE (F)

WAREHOUSE
300 200 200 700
REQUIREMENTS
 Developing an Initial Solution:
Northwest Corner Rule
3 Assign 100 units from Evansville to Boston. The
Evansville supply has now been exhausted but
Boston is still 100 units short. We move down
vertically to the next row in the Boston column.

TO ALBUQUERQUE BOSTON CLEVELAND FACTORY

FROM (A) (B) (C) CAPACITY

DES MOINES $5 $4 $3
100 100
(D)

EVANSVILLE $8 $4 $3
200 100 300
(E)

FORT $9 $7 $5
300
LAUDERDALE (F)

WAREHOUSE
300 200 200 700
REQUIREMENTS
 Developing an Initial Solution:
Northwest Corner Rule
4 Assign 100 units from Fort Lauderdale to Boston.
This fulfills Boston’s demand and Fort
Lauderdale still has 200 units available.

TO ALBUQUERQUE BOSTON CLEVELAND FACTORY

FROM (A) (B) (C) CAPACITY

DES MOINES $5 $4 $3
100 100
(D)

EVANSVILLE $8 $4 $3
200 100 300
(E)

FORT $9 $7 $5
100 300
LAUDERDALE (F)

WAREHOUSE
300 200 200 700
REQUIREMENTS
 Developing an Initial Solution:
Northwest Corner Rule
5 Assign 200 units from Fort Lauderdale to
Cleveland. This exhausts Fort Lauderdale’s
supply and Cleveland’s demand. The initial
shipment schedule is now complete.
Table 10.3
TO ALBUQUERQUE BOSTON CLEVELAND FACTORY
FROM (A) (B) (C) CAPACITY

DES MOINES $5 $4 $3
100 100
(D)

EVANSVILLE $8 $4 $3
200 100 300
(E)

FORT $9 $7 $5
100 200 300
LAUDERDALE (F)

WAREHOUSE
300 200 200 700
REQUIREMENTS
 Developing an Initial Solution:
Northwest Corner Rule
■ We can easily compute the cost of this shipping
assignment
ROUTE
UNITS PER UNIT TOTAL
FROM TO SHIPPED x COST ($) = COST ($)
D A 100 5 500
E A 200 8 1,600
E B 100 4 400
F B 100 7 700
F C 200 5 1,000
4,200

■ This solution is feasible but we need to check to

see if it is optimal
 Vogel’s Approximation Method:
Another Way To Find An Initial Solution
■ Vogel’s Approximation Method (VAM) is not as
simple as the northwest corner method, but it
provides a very good initial solution, often one
that is the optimal solution
■ VAM tackles the problem of finding a good initial
solution by taking into account the costs
associated with each route alternative
■ This is something that the northwest corner rule
does not do
■ To apply VAM, we first compute for each row and
column the penalty faced if we should ship over
the second-best route instead of the least-cost
route
 Vogel’s Approximation Method

■ The six steps involved in determining an initial

VAM solution are illustrated below beginning
with the same layout originally shown in Table
10.2
VAM Step 1. For each row and column of the
transportation table, find the difference between
the distribution cost on the best route in the row
or column and the second best route in the row
or column
■ This is the opportunity cost of not using the
best route
■ Step 1 has been done in Table 10.11
 Vogel’s Approximation Method

■ Transportation table with VAM row and column

differences shown
OPPORTUNITY
3 0 0 COSTS
TO TOTAL
FROM
A B C AVAILABLE
$5 $4 $3
D 100 100 1

$8 $4 $3
E 200 100 300 1

$9 $7 $5
F 100 200 300 2

TOTAL REQUIRED 300 200 200 700

Table 10.11
 Vogel’s Approximation Method

VAM Step 2. identify the row or column with the

greatest opportunity cost, or difference (column A
in this example)
VAM Step [Link] as many units as possible to the
lowest-cost square in the row or column selected
VAM Step 4. Eliminate any row or column that has
been completely satisfied by the assignment just
made by placing Xs in each appropriate square
VAM Step 5. Recompute the cost differences for the
transportation table, omitting rows or columns
eliminated in the previous step
 Vogel’s Approximation Method

■ VAM assignment with D’s requirements satisfied

OPPORTUNITY
31 03 02 COSTS
TO TOTAL
FROM
A B C AVAILABLE
$5 $4 $3
D 100 X X 100 1

$8 $4 $3
E 300 1

$9 $7 $5
F 300 2

TOTAL REQUIRED 300 200 200 700

Table 10.12
 Vogel’s Approximation Method

VAM Step 6. Return to step 2 for the rows and

columns remaining and repeat the steps until an
initial feasible solution has been obtained

■ In this case column B now has the greatest

difference, 3
■ We assign 200 units to the lowest-cost square in
the column, EB
■ We recompute the differences and find the
greatest difference is now in row E
■ We assign 100 units to the lowest-cost square in
the column, EC
 Vogel’s Approximation Method

■ Second VAM assignment with B’s requirements

satisfied
OPPORTUNITY
31 03 02 COSTS
TO TOTAL
FROM
A B C AVAILABLE
$5 $4 $3
D 100 X X 100 1

$8 $4 $3
E 200 300 1

$9 $7 $5
F X 300 2

TOTAL REQUIRED 300 200 200 700

Table 10.13
 Vogel’s Approximation Method

■ Third VAM assignment with E’s requirements

satisfied

TO TOTAL
FROM
A B C AVAILABLE
$5 $4 $3
D 100 X X 100

$8 $4 $3
E X 200 100 300

$9 $7 $5
F X 300

TOTAL REQUIRED 300 200 200 700

Table 10.14
 Vogel’s Approximation Method

■ Final assignments to balance column and row

requirements

TO TOTAL
FROM
A B C AVAILABLE
$5 $4 $3
D 100 X X 100

$8 $4 $3
E X 200 100 300

$9 $7 $5
F 200 X 100 300

TOTAL REQUIRED 300 200 200 700

Table 10.15
 Unbalanced Transportation Problems

■ In real-life problems, total demand is frequently

not equal to total supply
■ These unbalanced problems can be handled
easily by introducing dummy sources or dummy
destinations
■ If total supply is greater than total demand, a
dummy destination (warehouse), with demand
exactly equal to the surplus, is created
■ If total demand is greater than total supply, we
introduce a dummy source (factory) with a
supply equal to the excess of demand over
supply
 Unbalanced Transportation Problems

■ In either case, shipping cost coefficients of zero

are assigned to each dummy location or route as
no goods will actually be shipped
■ Any units assigned to a dummy destination
represent excess capacity
■ Any units assigned to a dummy source represent
unmet demand
 Demand Less Than Supply
■ Suppose that the Des Moines factory increases its
rate of production from 100 to 250 desks
■ The firm is now able to supply a total of 850 desks
each period
■ Warehouse requirements remain the same (700)
so the row and column totals do not balance
■ We add a dummy column that will represent a fake
warehouse requiring 150 desks
■ This is somewhat analogous to adding a slack
variable
■ We use the northwest corner rule and either
stepping-stone or MODI to find the optimal
solution
 Demand Less Than Supply
■ Initial solution to an unbalanced problem where
demand is less than supply
TO DUMMY TOTAL
FROM
A B C WAREHOUSE AVAILABLE

$5 $4 $3 0
D 250 250

$8 $4 $3 0
E 50 200 50 300

$9 $7 $5 0
F 150 150 300

WAREHOUSE
Total 300 + 200($4)
cost = 250($5) + 50($8) 200 200
+ 50($3) + 150($5) + 150(0)150
= 850
REQUIREMENTS
$3,350
New Des
Table 10.16
Moines capacity
 Demand Greater than Supply

■ The second type of unbalanced condition

occurs when total demand is greater than total
supply
■ In this case we need to add a dummy row
representing a fake factory
■ The new factory will have a supply exactly equal
to the difference between total demand and total
real supply
■ The shipping costs from the dummy factory to
each destination will be zero
 Demand Greater than Supply
■ Unbalanced transportation table for Happy
Sound Stereo Company

TO WAREHOUSE WAREHOUSE WAREHOUSE PLANT

FROM A B C SUPPLY
$6 $4 $9
PLANT W 200

$10 $5 $8
PLANT X 175

$12 $7 $6
PLANT Y 75
Totals
do not
WAREHOUSE 450 balance
250 100 150
DEMAND 500
Table 10.17
 Demand Greater than Supply
■ Initial solution to an unbalanced problem in
which demand is greater than supply
TO WAREHOUSE WAREHOUSE WAREHOUSE PLANT
FROM A B C SUPPLY
$6 $4 $9
PLANT W 200 200

$10 $5 $8
PLANT X 50 100 25 175

$12 $7 $6
PLANT Y 75 75

0 0 0
PLANT Y 50 50

WAREHOUSE
Total cost of initial solution
DEMAND
250 = 200($6) + 50($10) + 100($5)
100 150 + 25($8) + 75($6)
500
+ $50(0) = $2,850

Table 10.18
 Assignment Model Approach
■ The second special-purpose LP algorithm is the
assignment method
■ Each assignment problem has associated with it
a table, or matrix
■ 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
■ An assignment problem can be viewed as a
transportation problem in which the capacity
from each source is 1 and the demand at each
destination is 1
 Assignment Model Approach
■ The Fix-It Shop has three rush projects to repair
■ They have three repair persons with different
talents and abilities
■ The owner has estimates of wage costs for each
worker for each project
■ The owner’s objective is to assign the three
project to the workers in a way that will result in
the lowest cost to the shop
■ Each project will be assigned exclusively to one
worker
 Assignment Model Approach
■ Estimated project repair costs for the Fix-It shop
assignment problem

PROJECT

PERSON 1 2 3

Adams $11 $14 $6

Brown 8 10 11

Cooper 9 12 7

Table 10.26
 Assignment Model Approach
■ Summary of Fix-It Shop assignment alternatives
and costs

PRODUCT ASSIGNMENT
LABOR TOTAL
1 2 3
COSTS ($) COSTS ($)
Adams Brown Cooper 11 + 10 + 7 28
Adams Cooper Brown 11 + 12 + 11 34
Brown Adams Cooper 8 + 14 + 7 29
Brown Cooper Adams 8 + 12 + 6 26
Cooper Adams Brown 9 + 14 + 11 34
Cooper Brown Adams 9 + 10 + 6 25

Table 10.27
 The Hungarian Method
(Flood’s Technique)
■ The Hungarian method is an efficient method of
finding the optimal solution to an assignment
problem without having to make direct
comparisons of every option
■ It operates on the principle of matrix reduction
■ By subtracting and adding appropriate numbers
in the cost table or matrix, we can reduce the
problem to a matrix of opportunity costs
■ Opportunity costs show the relative penalty
associated with assigning any person to a
project as opposed to making the best
assignment
■ We want to make assignment so that the
opportunity cost for each assignment is zero
Three Steps of the Assignment Method

1 Find the opportunity cost table by:

(a) Subtracting the smallest number in each row
of the original cost table or matrix from every
number in that row
(b) Then subtracting the smallest number in
each column of the table obtained in part (a)
from every number in that column
2 Test the table resulting from step 1 to see
whether an optimal assignment can be made by
drawing the minimum number of vertical and
horizontal straight lines necessary to cover all
the zeros in the table. If the number of lines is
less than the number of rows or columns,
proceed to step 3.
Three Steps of the Assignment Method

3 Revise the present opportunity cost table by

subtracting the smallest number not covered by
a line from every other uncovered number. This
same number is also added to any number(s)
lying at the intersection of horizontal and
vertical lines. Return to step 2 and continue the
cycle until an optimal assignment is possible.
 Steps in the Assignment Method

Not
Set up cost table for Revise opportunity cost table
optimal
problem in two steps:
Step (a) Subtract the smallest
number not covered by a line
1
from itself and every other
Find opportunity cost uncovered number
(a) Subtract smallest number (b) add this number at every
in each row from every intersection of any two lines
number in that row, then
(b) subtract smallest number
in each column from every
number in that column Optimal solution at zero
locations. Systematically
make final assignments.
Step
(a) Check each row and
2
column for a unique zero and
Test opportunity cost table to make the first assignment in
see if optimal assignments are that row or column
possible by drawing the
(b) Eliminate that row and
minimum possible lines on
column and search for
columns and/or rows such that Optima
another unique zero. Make
all zeros are covered l that assignment and proceed
in a like manner.
Figure
10.3
 The Hungarian Method
(Flood’s Technique)

■ Step 1: Find the opportunity cost table

■ We can compute row opportunity costs and
column opportunity costs
■ What we need is the total opportunity cost
■ We derive this by taking the row opportunity
costs and subtract the smallest number in
that column from each number in that column
 The Hungarian Method
(Flood’s Technique)
■ Cost of each person- ■ Row opportunity
project assignment cost table

PROJECT PROJECT
PERSON 1 2 3 PERSON 1 2 3

Adams $11 $14 $6 Adams $5 $8 $0

Brown 8 10 11 Brown 0 2 3

Cooper 9 12 7 Cooper 2 5 0

Table 10.28 Table 10.29

■ The opportunity cost of assigning Cooper to

project 2 is $12 – $7 = $5
 The Hungarian Method
(Flood’s Technique)
■ We derive the total opportunity costs by taking
the costs in Table 29 and subtract the smallest
number in each column from each number in
that column
■ Row opportunity ■ Total opportunity
cost table cost table
PROJECT PROJECT
PERSON 1 2 3 PERSON 1 2 3

Adams $5 $8 $0 Adams $5 $6 $0

Brown 0 2 3 Brown 0 0 3

Cooper 2 5 0 Cooper 2 3 0

Table 10.29 Table 10.30

 The Hungarian Method
(Flood’s Technique)
■ Step 2: Test for the optimal assignment
■ We want to assign workers to projects in such
a way that the total labor costs are at a
minimum
■ We would like to have a total assigned
opportunity cost of zero
■ The test to determine if we have reached an
optimal solution is simple
■ We find the minimum number of straight lines
necessary to cover all the zeros in the table
■ If the number of lines equals the number of
rows or columns, an optimal solution has
been reached
 The Hungarian Method
(Flood’s Technique)
■ Test for optimal solution

PROJECT
PERSON 1 2 3

Adams $5 $6 $0

Brown 0 0 3 Covering line

1
Cooper 2 3 0

Table 10.31 Covering line

2

■ This requires only two lines to cover the zeros so

the solution is not optimal
 The Hungarian Method
(Flood’s Technique)
■ Step 3: Revise the opportunity-cost table
■ We subtract the smallest number not covered
by a line from all numbers not covered by a
straight line
■ The same number is added to every number
lying at the intersection of any two lines
■ We then return to step 2 to test this new table
 The Hungarian Method
(Flood’s Technique)
■ Revised opportunity cost table (derived by
subtracting 2 from each cell not covered by a
line and adding 2 to the cell at the intersection of
the lines)
PROJECT
PERSON 1 2 3

Adams $3 $4 $0

Brown 0 0 5

Cooper 0 1 0

Table 10.32
 The Hungarian Method
(Flood’s Technique)
■ Optimality test on the revised opportunity cost
table
PROJECT
PERSON 1 2 3

Adams $3 $4 $0

Brown 0 0 5 Covering line

2
Cooper 0 1 0

Table 10.33 Covering line Covering line

1 3
■ This requires three lines to cover the zeros so the
solution is optimal
 Making the Final Assignment
■ The optimal assignment is Adams to project 3,
Brown to project 2, and Cooper to project 1
■ But this is a simple problem
■ For larger problems one approach to making the
final assignment is to select a row or column that
contains only one zero
■ Make the assignment to that cell and rule out its
row and column
■ Follow this same approach for all the remaining
cells
 Making the Final Assignment
■ Total labor costs of this assignment are

ASSIGNMENT COST ($)

Adams to project 3 6

Brown to project 2 10

Cooper to project 1 9

Total cost 25
 Making the Final Assignment
■ Making the final assignments

(A) FIRST (B) SECOND (C) THIRD

ASSIGNMENT ASSIGNMENT ASSIGNMENT

1 2 3 1 2 3 1 2 3

Adams 3 4 0 Adams 3 4 0 Adams 3 4 0

Brown 0 0 5 Brown 0 0 5 Brown 0 0 5

Cooper 0 1 0 Cooper 0 1 0 Cooper 0 1 0

Table 10.34
Unbalanced Assignment Problems

■ Often the number of people or objects to be

assigned does not equal the number of tasks or
clients or machines listed in the columns, and
the problem is unbalanced
■ When this occurs, and there are more rows than
columns, simply add a dummy column or task
■ If the number of tasks exceeds the number of
people available, we add a dummy row
■ Since the dummy task or person is nonexistent,
we enter zeros in its row or column as the cost
or time estimate
Unbalanced Assignment Problems
■ The Fix-It Shop has another worker available
■ The shop owner still has the same basic problem
of assigning workers to projects
■ But the problem now needs a dummy column to
balance the four workers and three projects

PROJECT
PERSON 1 2 3 DUMMY
Adams $11 $14 $6 $0
Brown 8 10 11 0
Cooper 9 12 7 0
Davis 10 13 8 0

Table 10.35