Transportation and

Assignment Problems

• The Transportation Model

• Solution of a Transportation Problem
• The Assignment Model
• Solution of the Assignment Model

1
 Transportation Problems
• Transportation Problem
– A distribution-type problem in which supplies of goods
that are held at various locations are to be distributed to
other receiving locations.
– The solution of a transportation problem will indicate to a
manager the quantities and costs of various routes and
the resulting minimum cost.
– Used to compare location alternatives in deciding where
to locate factories and warehouses to achieve the
minimum cost distribution configuration.
– Some of the examples are: Shipment from factories to
warehouses, Shipment between departments within a
company, Shipment from warehouses to retailers
2
 Transportation Model Example
Public Distribution System (PDS)
Problem: How many tons of wheat to transport from each location to each
warehouse on a monthly basis in order to minimize the total cost of transportation ?
Wheat can be supplied from 3 different locations
Location Monthly Supply (in Tons)
A 100
B 200
C 200

Demand for each warehouse is given below

Warehouse Monthly Demand (in Tons)
1 50
2 150
3 300

The estimated cost per ton to ship per ton of wheat to each of the possible routes are
given below. To
From Warehouse 1 Warehouse 2 Warehouse 3
Location A 4 2 8
Location B 5 1 9
Location C 7 6 3 3
Schematic of a Transportation Problem

Assumptions:
• All goods are homogeneous so that any origin is
capable of supplying to any destination.
• Transportation costs are direct linear function of the
quantity shipped over any route.

Problem types:
• Equal supply and demand.
• Unequal supply and demand. 4
 Tableau Format
• Transportation problems are solved manually within a
tableau format.
• Each cell in a transportation tableau is analogous to a
decision variable that indicates the amount allocated
from a source to a destination.
• The supply and demand values along the outside rim of
a tableau are called rim values.

Equal Supply and

Demand

5
 Solution Methods
• Transportation models do not start at the origin where all
decision values are zero; they must instead be given an
initial feasible solution.
• Initial feasible solution determination methods include:
- Northwest Corner method
- Minimum Cell Cost method
- Vogel’s Approximation Method
• Methods for solving the transportation problem itself
include:
- Stepping-stone method and
- Modified Distribution (MODI) method.
6
The Northwest Corner Method

Northwest
Corner
North

West

7
 The Northwest Corner Method
Step 1
Northwest
Corner
North

West

Step 2

Step 3
Step 5

Step 4

8
 The Northwest Corner Method
- In the North-West corner method the largest possible allocation is made to the cell in the
upper left-hand corner of the tableau , followed by allocations to adjacent feasible cells.

The Initial NW
Corner
Solution

- The initial solution is complete when all rim requirements are satisfied.
- Transportation cost is computed by evaluating the objective function:
Z = 4(50) + 2(50) + 1(100) + 9(100) + 3(200)
= 1900

9
 The Northwest Corner Method

Summary of Steps

1. Allocate as much as possible to the cell in the upper left-hand

corner, subject to the supply and demand conditions.
2. Allocate as much as possible to the next adjacent feasible cell.
3. Repeat step 2 until all rim requirements are met.

10
 The Minimum Cell Cost Method
(1 of 3)
- In the minimum cell cost method as much as possible is allocated to the cell with the
minimum cost followed by allocation to the feasible cell with minimum cost.

This method
is also called
as intuitive
approach

The Initial Minimum Cell Cost Allocation

11
The Second Minimum Cell Cost Allocation
 The Minimum Cell Cost Method
(2 of 3)

The Initial Solution

- The computed transportation cost is

Z = 4(50) + 1(150) + 8(50) + 9(50) + 3(200)
= 1800
- The minimum cell cost method will provide a solution with a lower cost than
the northwest corner solution because it considers cost in the allocation process.
12
 The Minimum Cell Cost Method

Summary of Steps
(3 of 3)

1. Allocate as much as possible to the feasible cell with the

minimum transportation cost, and adjust the rim requirements.
2. Repeat step 1 until all rim requirements have been met.

13
 Vogel’s Approximation Method (VAM)
(1 of 3)
- Method is based on the concept of penalty cost
- In VAM the first step is to develop a penalty cost for each source and destination.
- Penalty cost is calculated by subtracting the minimum cell cost from the next higher cell
cost in each row and column.

- VAM allocates as much as possible to the minimum cost cell in the row or column with
the largest penalty cost.

The VAM Penalty Costs

14
 Vogel’s Approximation Method (VAM)
(2 of 3)
- After each VAM cell allocation, all row and column penalty costs are recomputed.
VAM allocates as much as possible to the minimum cost cell in the row or column with the
largest penalty cost.

- The initial VAM solution; total cost = 1800

- VAM and minimum cell cost methods both provide better initial solutions than does the
northwest corner method. 15
 Vogel’s Approximation Method (VAM)
Summary of Steps

1. Determine the penalty cost for each row and column.

2. Select the row or column with the highest penalty cost.
3. Allocate as much as possible to the feasible cell with the
lowest transportation cost in the row or column with the
highest penalty cost.
4. Repeat steps 1, 2, and 3 until all rim requirements have been
met.

16
 The Stepping-Stone Solution Method
(1 of 8)

- Once an initial solution is derived, the problem must be solved using either the stepping-
stone method or the Modified Distribution method (MODI).

The Initial
Feasible Solution
Using Northwest-
Corner method

17
 The Stepping-Stone Solution Method
(2 of 8)
- The stepping-stone method determines if there is a cell with no allocation that would
reduce cost if used.
- An empty cell that will reduce cost is a potential entering variable.
- To evaluate the cost reduction potential of an empty cell, a closed path connecting used
cells to the empty cells is identified.

The Allocation of One Ton to Cell B1

This means that for each unit shifted into cell B1 in this way
(which is the only way the shift could be made), the total cost
would increase by 2. Consequently, such a shift would not be
desirable 18
The Stepping-Stone Solution Method
(3 of 8)

19
The Stepping-Stone Solution Method
(4 of 8)

20
 The Stepping-Stone Solution Method
(5 of 8)

- After all empty cells are evaluated, the one with the greatest cost reduction potential is the
entering variable.
- A tie can be broken arbitrarily.

21
 The Stepping-Stone Solution Method
(6 of 8)
- When reallocating units to the entering variable (cell), the amount is the minimum amount
subtracted on the stepping-stone path.
- At each iteration one variable enters and one leaves (just as in the simplex method).

Total cost Z = 4(50) + 8(50) + 1(150) + 9(50) + 3(200)

= 1800
22
 To 1 2 3 Supply Cell B1
From + cells - cells
The Stepping- A 50(-)
4 2
50(+)
8
100
5
8
4
9
5 1 9

Stone Solution B

C
(+)
7
150
6
50(-)

200
3
200

200
+13 -13

Method Demand 50 150 300 500 = +13 - 13 = 0

To 1 2 3 Supply Cell C1

(7 of 8) From

A 50(-)
4 2
50(+)
8
100
+ cells
7
8
- cells
4
3
5 1 9
B 150 50 200
Check to see if the solution is 7 6 3 +15 -7
C (+) 200(-) 200
optimal. Demand 50 150 300 500 = +15 - 7 = 8

To 1 2 3 Supply Cell C2
From + cells - cells
4 2 8 6 1
A 50 50 100 9 3
5 1 9
B 150(-) 50(+) 200
7 6 3 +15 -4
C (+) 200(-) 200
Cell B1 has cost reduction Demand 50 150 300 500 11
= +15 - 4 = - 11

potential of 0. To 1 2 3 Supply Cell A2

From + cells - cells
What it means? 4 2 8 2 8
A 50 (+) 50(-) 100 9 1
5 1 9
B 150(-) 50(+) 200
7 6 3 +11 -9
C 200 200
Demand 50 150 300 500 = +11 - 9 = 2
23
 The Stepping-Stone Solution Method
(8 of 8)

Summary of Steps
1. Determine the stepping-stone paths and cost changes for
each empty cell in the tableau.
2. Allocate as much as possible to the empty cell with the
greatest net decrease in cost.
3. Repeat steps 1 and 2 until all empty cells have positive cost
changes that indicate an optimal solution.

24
 The Modified Distribution Method (MODI)
(1 of 5)
- MODI is a modified version of the stepping-stone method in which math equations replace
the stepping-stone paths.
- In the table, the extra left-hand column with the ri symbols and the extra top row with the
kj symbols represent values that must be computed.
- Compute ri and kj for all cells having allocations using the formula below:
ri + kj = cij = unit transportation cost for cell ij.

Initial feasible solution

obtained using Northwest-
Corner method

25
 The Modified Distribution Method (MODI)
(2 of 5)

For all occupied cells:

r1 = 0 (arbitrary selection)
r1+k1=4; 0+k1=4; hence k1=4
r1+k2=2; 0+k2=2; hence k2=2
r2+k2=1; r2+2=1; hence r2= -1 (knowledge of k2 helps us to calculate r2)
r2+k3=9; -1+k3=9; hence k3=10 (knowledge of r2 helps us to calculate k3)
r3+k3=3, r3+10=3; hence r3 = -7 26
 The Modified Distribution Method (MODI)
(3 of 5)
We can now readily determine the improvement potentials for each of the unoccupied
cells using the relationship:
Improvement potential (for a unoccupied cell) = Cell cost – Row index – Column index

For all unoccupied cells:

B1 = 5 – (-1) – 4 = 2
A3 = 8 – 0 – 10 = -2
C1 = 7 – (-7) – 4 = 10
C2 = 6 – (-7) – 2 = 11
Note that these values agree with the values we computed earlier using the
stepping stone method 27
 The Modified Distribution Method (MODI)
(4 of 5)
When all the evaluations are positive or zero, an optimal solution has been found.
If one or more is negative, the cell with the largest negative should be brought
into solution because that route has the largest potential for improvement per unit.

Since the cell A3 has -2, improvement potential of 2 per unit is possible.

Developing improved solution:

Reallocate quantities as much as in the cell A3 to take advantage of improvement
potential taking into consideration of rim conditions.

Stepping-stone path is necessary for determining reallocation potential.

28
 The Modified Distribution Method (MODI)
(5 of 5)

Improved transportation cost = 4*50 + 8*50 + 1*150 + 9*50 + 3*200 = 1800

Again check all empty cells to see if further improvement is possible or not . This
requires use of MODI method or stepping stone method. Continue this iteration till
we get solution that has no further improvement

29
The Modified Distribution Method (MODI)
Summary of Steps

1. Develop an initial solution.

2. Compute the ri and kj values for each row and column.
3. Compute the cost change, for each empty cell.
4. Allocate as much as possible to the empty cell that will
result in the greatest net decrease in cost (most negative)
5. Repeat steps 2 through 4 until all values are positive or
zero in all empty cells

30
Special Issues

31
 Alternate Optimal Solutions
Manager should be aware of alternate solutions which gives an option of
bringing non-quantitative considerations into the decision.

The existence of an alternate solution is signaled by an empty cell’s

evaluation equal to zero (Refer Slide # 22)

We can find the alternate solution is by reallocating the maximum number

of units possible around stepping-stone path (cell B1).
To 1 2 3 Supply Cell B1
From + cells - cells
4 2 8 5 4
A 50(-) 50(+) 100 8 9
5 1 9
B (+) 150 50(-) 200
7 6 3 +13 -13
C 200 200
Demand 50 150 300 500 = +13 - 13 = 0

32
Total cost = 5(50) + 1(150) + 8(100) + 3(200) = 1800
 Degeneracy
(1 of 3)

- In a transportation tableau with m rows and n columns, there must be m + n - 1 cells with
allocations; if not, it is degenerate.
- The tableau in the figure does not meet the condition since 3 + 3 -1 = 5 cells and there are
only 4 cells with allocations.

33
 Degeneracy
(2 of 3)

- In a degenerate tableau, all the stepping-stone paths or MODI equations cannot be

developed.
-To rectify a degenerate tableau, an empty cell must artificially be treated as an occupied
cell with the value Delta (which is a very low value (say 0.001 units) and do the check for
optimality).

34
Degeneracy
(3 of 3)

Optimal solution
35
 The Unbalanced Transportation Model
(1 of 2)

- When demand exceeds supply a dummy row is added to the tableau.

An Unbalanced Model
(Demand > Supply)

NOTE:
If the minimum cell cost method is used to obtain the initial solution,
make assignment to the dummy last. Hence, begin by assigning units
to the cell with the lowest nonzero cost, next lowest nonzero cost and
so on.
36
 The Unbalanced Transportation Model
(2 of 2)

- When supply exceeds demand, a dummy column is added to the tableau.

An Unbalanced Model (Supply > Demand)

37
Prohibited Routes or Unacceptable Routes

- A prohibited route is assigned a large cost such as M.

- When the prohibited cell is evaluated, it will always
contain the cost M, which will keep it from being
selected as an entering variable.

38
 Maximization Problem

• Some transportation problem concern profit rather than cost.

• The objective is to maximize rather than minimize.
Such problems can be handled by adding one additional step at
the start: Identify the cell with the largest profit and subtract all
the other cell profits from that value. Then replace the cell
profits with the resulting values. These values reflect the
opportunity costs that would be incurred by using routes with
unit profits that are less than the largest unit profit. Replace the
original unit profits with these opportunity costs and solve in the
usual way for the minimum opportunity cost solution. This will
be identical to maximizing the total profit.
In this problem assume
unit profits are given.
Maximum profit = 9,
Calculate opportunity cost
by subtracting individual
profit from maximum
profit and treat as
minimization problem
39
The Assignment
Problem

40
 The Assignment Problem
Characteristics
• Special form of linear programming
model similar to the transportation model. It was developed and published
by Harold Kuhn , who gave the
• Supply at each source and demand at name "Hungarian method"
each destination limited to one unit. because the algorithm was
largely based on the earlier works
• In a balanced model supply equals of
two Hungarian mathematicians:
demand. Dénes Kőnig and Jenő Egerváry.
• In an unbalanced model supply does not
equal demand.

The specialized solution method for the assignment

problem called the Hungarian Method
41
 Example
A manager has prepared a table that shows the cost of performing each of four jobs by
each of four employees (see Table below). According to this table, Job 1 will cost $15 if
done by employee A, $20 if it is done by employee B, and so on. The manager has
stated that his goal is to develop a set of job assignments that will minimize the total
cost of getting all four jobs done. It is further required that the jobs be performed
simultaneously, thus requiring one job being assigned to each employee.
Although the manager recognizes that this problem can be solved using the
simplex routine, he also knows that he can solve the problem by hand using the
Hungarian method.

42
 The Hungarian Method

• Provides a simple heuristic that can be used to find

the optimal set of assignments.
• Is easy to use, even for fairly large problems.
• Is based on minimization of opportunity costs that
would result from potential pairings.
– These are additional costs would be incurred if the lowest-
cost assignment is not made, in terms of either jobs (i.e.,
rows) or employees (i.e., columns).

43
Row Reduction

44
Column Reduction of Opportunity
(Row Reduction) Costs

45
Determine the Minimum Number of Lines Needed to Cover the Zeros

If the minimum number of covering lines

equals the number of rows (or columns,
because this is a square table), an optimal
assignment is possible.

Further Revision of the Cost Table

46
Optimal Assignments

Total cost the assignments

47
Transshipment Problems

48
 Transshipment Problems

• Transshipment Problems
– A transportation problem in which some locations
are used as intermediate shipping points, thereby
serving both as origins and as destinations.
– Involve the distribution of goods from
intermediate nodes in addition to multiple sources
and multiple destinations.

49
 Transshipment Model Example
Public Distribution System (PDS)
Problem: Now the PDS has decided to utilize two intermediate nodes as transshipment points
(temporary warehouse) for temporary storage of wheat. How many tons of wheat to transport
from each location to each warehouse on a monthly basis in order to minimize the total cost
of transportation ?
Location Monthly Supply (in Tons)
A 100
Wheat can be supplied from 3
different locations B 200
C 200

Warehouse Monthly Demand (in Tons)

1 50
Demand for each of final
warehouse 2 150
3 300

The estimated cost per ton to ship per ton of wheat to each of the possible routes are
given below.

50
A Network Diagram of a Transshipment Problem

100 A 1 50

200 B 2 150

200 C Intermediate 3 300

warehouses
Wheat Final
Supply warehouses
locations

51
 Exercise
Consider the transportation problem of the Crystal
Refrigerator company:

a) Develop an initial feasible solution and compute the

total cost.
b) Evaluate the solution using the stepping-stone
method. Is the solution optimal? Explain.
52
Backup

53