CHAPTER FIVE

Transportation and
Assignment Problems
Mulugeta K. PhD)
Department of Management
5.1. Transportation Problem (TP)

• The major purpose of using an LP model for transportation

problems is to minimize transportation costs taking into
account:
– The origin supplies
– The destination demands, and
– The unit transportation costs.
• Examples of transportation problems include:
Shipments from warehouses to retail stores, shipment from
factories to warehouses, shipments between departments within
a company, and production scheduling
Developing a Transportation Model

• A TP involves:
– a set of sending locations which are referred to as origins,
and
– a set of receiving locations, which are referred to as
destinations.
• Information required to develop a TP model include:
– Supply quantity (capacity) of each origin.
– Demand quantity of each destination.
– Unit transportation cost for each origin-destination route.
Example 1፡ Powerco Formulation

• Powerco has three electric power plants that supply the needs
of four cities. Each power plant can supply the following
numbers of kilowatt-hours (kwh) of electricity: plant 1—35
million; plant 2—50 million; plant 3—40 million. The peak
power demands in these cities, which occur at the same time
(2 P.M.), are as follows (in kwh): city 1—45 million; city 2—20
million; city 3—30 million; city 4—30 million. The costs of
sending 1 million kwh of electricity from plant to city depend
on the distance the electricity must travel. The cost data is
given in the following table.
 Cont…

• Data on the Shipping Costs for Powerco

To
From City 1 City 2 City 3 City 4
Plant 1 $8 $6 $10 $9
Plant 2 $9 $12 $13 $7
Plant 3 $14 $9 $16 $5

• Required
a. Formulate an LP to minimize the cost of meeting each city’s
peak power demand.
 Cont…

• Summarizing the whole information in a single transportation

table
Supply
To
(million kwh)
From City 1 City 2 City 3 City 4
Plant 1 $8 $6 $10 $9 35
Plant 2 $9 $12 $13 $7 50
Plant 3 $14 $9 $16 $5 40
Demand
(million kwh) 45 20 30 30
 Solution

 Let:
xij = number of (million) kwh produced at plant i and sent
to city j
 The total cost of supplying the peak power demands to cities
1–4 may be written as:

8x11 + 6x12 + 10x13 + 9x14 (Cost of shipping power from plant 1)

+ 9x21 + 12x22 + 13x23 + 7x24 (Cost of shipping power from plant 2)
+ 14x31 + 9x32 + 16x33 + 5x34 (Cost of shipping power from plant 3)
 Cont…

• Powerco faces two types of constraints.

1. The total power supplied by each plant cannot exceed the
plant’s capacity

2. Each city will receive sufficient power to meet its peak

demand.
 Cont…

• Combining the OF, supply constraints, demand constraints, and

NNC yields the following LP model of Powerco’s problem:
Min z = 8x11 + 6x12 + 10x13 + 9x14 + 9x21 + 12x22 + 13x23 + 7x24
+ 14x31 + 9x32 + 16x33 + 5x34
s.t.
x11+ x12 + x13 + x14 ≤ 35 (Supply constraints)
x21 + x22 + x23 + x24 ≤ 50
x31 + x32 +x33 + x34 ≤ 40
x11+ x21 + x31 ≥ 45 (Demand constraints)
x12 + x22 + x32 ≥ 20
x13 + x23 + x33 ≥ 30
x14 + x24 + x34 ≥ 30
xij ≥ 0 (i 1, 2, 3; j 1, 2, 3, 4)
General Description of a Transportation Problem

• A transportation problem is specified by the following

information:
1. A set of m supply points from which a good is shipped.
Supply point i can supply at most si units.
• In the Powerco example, m=3, s1= 35, s2 = 50, and s3 = 40.
2. A set of n demand points to which the good is shipped.
Demand point j must receive at least dj units of the
shipped good.
• In the Powerco example, n = 4, d1 = 45, d2 = 20, d3 = 30, and d4
= 30.
3. Each unit produced at supply point i and shipped to
demand point j incurs a variable cost of cij.
• In the Powerco example, c12 = 6.
 Cont…

 Let:
xij = number of units shipped from supply point i to
demand point j, then:
• The general formulation of a transportation problem is

• If the total supply equals total demand, and the problem is said
to be a balanced transportation problem.
 Cont…

• Network Representation of Powerco Problem and Its Optimal

Solution
Transportation Tableau

• The relevant data in a transportation problem is summarized

in a transportation tableau.
Transportation Tableau for Powerco’s problem
To
From City 1 City 2 City 3 City 4 Supply
Plant 1 8 6 10 9 35

Plant 2 9 12 13 7 50

Plant 3 14 9 16 5 40

Demand 45 20 30 30
Assumptions of a Transportation Model

• The transportation algorithm requires the assumption that:

– All goods be homogeneous, so that any origin is capable of
supplying any destination, and
– Transportation costs are a direct linear function of the
quantity shipped over any route.
– The total quantity available is equal to the total demand
(though we will modify it when we discuss about special
issues).
• The Powerco’s problem is a balanced problem
Quantity Demand = Quantity Supply (125=125)
Solving Transportation Problems

• The transportation problem is solved in two phases:

I. Phase I: Obtaining an initial feasible solution
• Methods like the NWC, LCM and VAM can be used to
establish an initial basic feasible solution easily.
II. Phase II: Moving toward optimality
• Stepping stone and the MODI Methods can be used for
evaluating the reduced costs to move from the initial
feasible solution to the optimal one.
• Whereas, the stepping-stone method is used to reach the optimal
solution, MODI helps to evaluate reduced costs.
I. Obtaining an Initial Basic Feasible Solution

• For the transportation assignment to be feasible, two

conditions must be fulfilled:
1. A feasible solution is one in which assignments are made in
such a way that all supply and demand requirements are
satisfied.
2. The number of nonzero (occupied) cells should equal one
less than the sum of the number of rows and the number
of columns in a transportation table.
• In trying to find a bfs to the remaining m + n -1 constraints, you
might think that any collection of m + n -1 variables would yield
a basic solution.
 Cont…

• A number of different approaches can be used to find an

initial feasible solution.
• Three of these are described here:
1. The northwest-corner method (NCM)
2. An intuitive approach/Least cost method/ (LCM)
3. Vogel’s Approximation / Penalty/ Method (VAM)
• NB:
– When a fewer occupied cells appear in a solution, the
solution is referred to as a degenerated solution.
1. The Northwest-Corner Method (NCM)

• While using the NWC method, the allocation process starts

from the upper left-hand (Northwest) corner of the table.
– Begin with the upper left-hand cell, and allocate as many
units as possible to that cell.
• This will be the smaller of the row supply and the
column demand.
• Adjust the row and column quantities to reflect the
allocation.
– Remain in a row or column until its supply or demand is
completely exhausted or satisfied
Example

• Initial feasible solution (BFS) of the Powerco’s problem using

the NWC method
To
From City 1 City 2 City 3 City 4 Supply
Plant 1 * 8 6 10 9 35
35
Plant 2 * 9 * 12 * 13 7 50
10 20 20
Plant 3 14 9 * 16 * 5 40
10 30
Demand 45 20 30 30

NB: * indicates the occupied cells

 Cont…

• In the above solution we can see that:

# of occupied cells = n+m-1
• Minimum Cost = 35(8)+10(7)+20(12)+20(13)+10(16)+30(5)
=$1160
NB:
• The chief advantages of NWC method are that it is simple to
use and easy to understand.
• Its chief drawback is that it does not take transportation costs
into account, so it can yield an initial bfs that has a very high
shipping cost.
2. The Least Method (LCM)

• The minimum-cost method uses lowest cell cost as the basis

for selecting routes.
• The procedure is as follows:
– Identify the cell that has the lowest unit cost, and allocate
a quantity to this cell
– Cross out the cells in the row or column that has been
exhausted.
– Identify the cell with the lowest cost from the remaining
cells, and allocate a quantity to this cell
– Repeat the above steps until all SS and DD are exhausted.
Example

• Initial basic feasible solution (IBFS) of the Powerco’s problem

using the LCM method
To
From City 1 City 2 City 3 City 4 Supply
Plant 1 * 8 * 6 10 9 35
15 3rd 20 2nd
Plant 2 * 9 12 * 13 7 50
30 4th 20 5th
Plant 3 14 9 * 16 * 5 40
10 6th 30 1st
Demand 45 20 30 30

 Minimum Cost = 15(8)+20(6)+30(9)+20(13)+10(16)+30(5) = $1080

3. Vogel’s Approximation Method (VAM)

• VAM is based on the concept of penalty cost or regret.

• If a decision maker incorrectly chooses from several
alternative courses of action, a penalty may be suffered.
– Begin by computing for each row (and column) a “penalty”
equal to the difference between the two smallest costs in
the row (column).
– Next find the row / column with the largest penalty.
– Go to that raw/column and, choose as the first basic
variable the variable that has the smallest shipping cost.
 Cont…

– Allocate as many quantity as possible to that cell.

– Cross the row (column) in which capacity (demand) is
exhausted.
• When there is a tie for penalty, select one arbitrarily.
– After allocation, cross that row or column and disregard it
from further consideration.
– Repeat the above steps for the reduced table until the
entire capabilities (supplies) are used to fill the
requirement at different destinations.
Example

• IBFS of the Powerco’s problem using the VAM method

To
From City 1 City 2 City 3 City 4 Supply P1 P2 P3 P4
Plant 1 8 * 6 * 10 9 35
10 25 2 2 2 2
3rd 6th
Plant 2 * 9 12 * 13 7 50
45 4th 5 5th 2 3 3 4
Plant 3 14 * 9 16 * 5 40
10 2nd 30 1st 4 5 -- --
Demand 45 20 30 30

P1 1 3 3 2
P2 1 3 3 --
P3 1 6 3 --
P4 1 -- 3 --
 Cont…

• Minimum Cost = 45(9)+10(6)+10(9)+25(10)+5(13)+30(5)

= $1020
• Comparing the outputs of the three methods for the
Powerco’s problem
Approaches of finding the IBFS
Methods NCM LCM VAM
Min Cost $1160 $1080 $1020

• VAM is preferred over the other two methods, and the initial
feasible solution obtained with VAM is either optimal or very close
to the optimal.
II. Moving toward Optimality

 Evaluating the IFS for Optimality

– The test for optimality for an IFS involves a cost
evaluation of empty cells
• i.e., routes to which no units have been allocated to see if
an improved solution is possible.
– We consider two methods for cell evaluation:
1. The Stepping-stone method
2. The MODI method
1. The Stepping-stone method

• This method involves tracing a series of closed path in the

table, using one such path for each empty cell.
• The path represents a shift of one unit into an empty cell
• It enables the analyst to know what impact on total cost
would there be if one unit were shifted into an unused
route.
• The result is a cost change per unit shift into a cell.
• The stepping-stone path also can be used to determine the
maximum amount that can be shifted into empty cell.
 Cont..

 Rules for tracing stepping-stone paths

– All unoccupied cells must be evaluated one at a time
– Except for the cell being evaluated, only add (+) or subtract (-)
in occupied cells.
– It is permissible to skip over unoccupied or occupied cells to
find an occupied cell from which the path can continue.
– A path will consist of only horizontal and vertical moves
starting and ending with the empty cell being evaluated.
– Alternate ‘+’ and ‘–‘signs, beginning with a ‘+’ sign in the cell
being evaluated.
The stepping Stone Path (Loop)

• An ordered sequence of at least four different cells is called a

loop (stepping step path) if:
– Any two consecutive cells lie in either the same row/ column
– No three consecutive cells lie in the same row or column
– The last cell in the sequence has a row or column in common
with the first cell in the sequence
Example

• Consider the Powerco’s problem of an initial feasible solution

found using NCM, and evaluate its optimality.
• The unoccupied cells to be evaluated are: P1-C2, P1-C3, P1-C4 and
P2-C4, P3-C1 and P3-C2. Lets evaluate P1-C2, for instance:
To
From City 1 City 2 City 3 City 4 Supply
Plant 1 * 8 6 10 9 35
-
Plant 2 * 9 * 12 * 13 7 50
+ -
Plant 3 14 9 * 16 * 5 40

Demand 45 20 30 30
 Cont…

• The net impact of such a unit shift can be determined by adding

the cell costs with signs attached and noting the resulting value.
• Evaluation for Cell P1-C2, for instance, can be done as:
6-12+9-8=-5
• Evaluation for all other empty cells is shown below (Iteration 1)
Unoccupied Cell Reduced Cost
P1-C2 6-12+9-8 = -5
P1-C3 10-13+9-8 = -2
P1-C4 9-5+16-13+9-8 = 8
P2-C4 7-5+16-13 = 5
P3-C1 14-9+13-16 = 2
P3-C2 9-12+13-16 = -6 → results in higher cost reduction
 Cont…

• Cells with negative evaluation indicate that a unit shift in them

will result in a cost reduction, so the solution needs further
improvement.
• In our case, cell P3-C2 should be the basic variable that must be
occupied in the next iteration since it results in higher cost
reduction.
– The + signs in the path indicate units to be added, the – signs
indicate units to be subtracted.
– The limit on subtraction is the smallest quantity in a
negative position along the cell path.
 Cont…

• In our example, there are two quantities in negative positions

associated with the P3-C2’s loop: P2-C2 (20) and P3-C3 (10)
• Take the minimum, i.e. 10, and add it in to and subtract it from
all four cells in that particular loop.
To
From City 1 City 2 City 3 City 4 Supply
Plant 1 * 8 6 10 9 35
35
Plant 2 * 9 * 12 * 13 7 50
10 20 20
Plant 3 14 9 * 16 * 5 40
10 30
Demand 45 20 30 30
 Cont…

• Thus for the next table:

P3-C2 = 0 + 10 = 10 (0 is its current allocation)
P2-C2 = 20 - 10 = 10
P2-C3 = 20 + 10 = 30
P3-C3 = 10 - 10 = 0 (blank for the next tableau)
• All amounts in other cells remain unchanged.
• In the next iteration, we will be going through the same
procedure we have done in the first iteration.
• We will evaluate all unoccupied cells and see if further
improvement is possible.
 Cont…

• Improved solution in the first iteration

To
From City 1 City 2 City 3 City 4 Supply
Plant 1 * 8 6 10 9 35
35
Plant 2 * 9 * 12 * 13 7 50
10 10 30
Plant 3 14 * 9 16 * 5 40
10 30
Demand 45 20 30 30

• P3C3 is removed from the basic variables set while P3C2 enters.
 Cont…

• Evaluation of empty cells (Iteration 2)

Unoccupied Cell Reduced Cost
P1-C2 6-12+9-8 = -5→ results in higher cost reduction
P1-C3 10-13+9-8 = -2
P1-C4 9-5+9-12+9-8 = 2
P2-C4 7-5+9-12 = -1
P3-C1 14-9+12-9 = 8
P3-C3 16-9+12-13 = 6

• P1-C2 should be the basic variable that must be occupied in the

next iteration since it results in higher cost reduction.
• Improve the solution following the earlier procedure.
 Cont…

• Adding and subtracting the minimum negative amount in the

P1C2 loop. i.e. 10 at cell P2C2, we develop the improved solution.
• Improved solution in the second iteration
To
From City 1 City 2 City 3 City 4 Supply
Plant 1 * 8 * 6 10 9 35
25 10
Plant 2 * 9 12 * 13 7 50
20 30
Plant 3 14 * 9 16 * 5 40
10 30
Demand 45 20 30 30
 Cont…

• Evaluation of empty cells (Iteration 3)

Unoccupied Cell Reduced Cost
P1-C3 10-13+9-8 = -2→ results in higher cost reduction
P1-C4 9-5+9-6 = 7
P2-C2 12-9+8-6 = 5
P2-C4 7-5+9-6+8-9 = 2
P3-C1 14-8+6-9 = 3
P3-C3 16-9+6-8+9-13= 1

• P1-C3 should be the basic variable that must be occupied in the

next iteration since it results in cost reduction.
• Improve the solution following the earlier procedure.
 Cont…

• Adding and subtracting the minimum negative amount in the

P1C3 loop. i.e. 25 at cell P1C1, we develop the improved solution.
• Improved solution in the third iteration
To
From City 1 City 2 City 3 City 4 Supply
Plant 1 8 * 6 * 10 9 35
10 25
Plant 2 * 9 12 * 13 7 50
45 + 5
Plant 3 14 * 9 16 * 5 40
10 30
Demand 45 20 30 30
 Cont…

• Evaluation of empty cells [for Next Iteration]

Unoccupied Cell Reduced Cost
P1-C1 8-10+13-9= 2
P1-C4 9-5+9-6 = 7
P2-C2 12-6+10-13 = 3
P2-C4 7-5+9-6+10-13 = 2
P3-C1 14-9+13-10+ 6-9= 5
P3-C3 16-10+6-9= 3

• Since all cell evaluations result in positive (+ve) values further

evaluation can not be done, and the current solution is optimal.
• So, the optimal solution is found
 Cont…

• The optimal solution is summarized in the following table

From To Quantity (million Cost

kwh)
Plant 1 City 2 10 60
Plant 1 City 3 25 250
Plant 2 City 1 45 405
Plant 2 City 3 5 65
Plant 3 City 2 10 90
Plant 3 City 4 30 150
Total minimum transportation cost $1020
2. The MODI method

• The Modified Distribution (MODI) method is an efficient way

of evaluating a solution for optimality.
• It involves the use of index numbers that are established for
the rows and columns.
• These are based on the unit costs of the occupied cells.
• They will be used to obtain the cell evaluations for empty
cells without the use of stepping-stone paths.
• There is one index number for each column and one for each
row.
 Cont…

• Index numbers are determined in such a way that for any

occupied cell, the sum of the row index and the column index
equal the cell‘s unit transportation cost.

Row index + Column index = Cell cost

ui + vj= cij

• The process always begins by assigning a value of zero as the

index number of row 1.
• Once a row/column index has been established, it will enable
us to compute other index numbers.
 Cont…

• The cell evaluations for each of the unoccupied cells are

determined using the relationship:
Cell evaluation = Cell cost – Row index – Column index
eij=cij– ui–kj

• When cell 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.
• It is because that route has the largest potential for
improvement per unit.
Example

• Consider the Powerco’s problem of an initial feasible solution

found using the LCM, and evaluate its optimality Using MODI.
• The unoccupied cells to be evaluated are: P1-C3, P1-C4, P2-C2, P2-
C4, P3-C1 and P3-C2
To
From City 1 City 2 City 3 City 4 Supply
Plant 1 * 8 * 6 10 9 35
u1 =0
Plant 2 * 9 12 * 13 7 50
u2 =1
Plant 3 14 9 * 16 * 5 40
u3 =4
Demand 45 20 30 30
ν1 =8 ν2 =6 ν3 =12 ν4 =1
Finding Index numbers for each row and column

• Let: u1(row 1) = 0, where, U= row, V= Column

C11=u1 + ν1 C23= u2 + ν3
8 =0+ ν1 13 =1+ ν3
ν1 =8 ν3 =12

C12 =u1 + ν2 C33= u3 + ν3

6 =0 + ν2 16 =u3+ 12
ν2 =6 u3 =4

C21 =u2 + ν1 C34= u3 + ν4

9 =u2 + 8 5 =4+ ν4
u2 = 1 ν4 =1
 Cont…

• Evaluation of empty cells using the specified formula

eij=cij– ui–kj

Unoccupied Cells Reduced Cost

P1-C3 10-0-12= -2→ results in highest cost reduction
P1-C4 9-0-1 = 8
P2-C2 12-1-6 = 5
P2-C4 7-1-1 = 5
P3-C1 14-4-8 = 2
P3-C2 9-4-6= -1

Entering variable: Cell P1-C3

 Cont…

• Improving the Solution requires to look at the stepping stone path

of cell P1-C3, the entering variable.

To
From City 1 City 2 City 3 City 4 Supply
Plant 1 * 8 * 6 10 9 35
15 20
Plant 2 * 9 12 * 13 7 50
Min
30 20
Plant 3 14 9 * 16 * 5 40
10 30
Demand 45 20 30 30

Minimum negative amount = 15, Do (+) and (–) for cells in the loop
 Cont…

• Adding and subtracting the minimum negative amount in the P1C3

loop. i.e. 15 at cell P1C1, we develop the improved solution.
• Improved solution from the first iteration
To
From City 1 City 2 City 3 City 4 Supply
Plant 1 8 * 6 * 10 9 35 u1 =0
20 15
Plant 2 * 9 12 * 13 7 50
u2 =3
45 5
Plant 3 14 9 * 16 * 5 40 u3 =6
10 30
Demand 45 20 30 30
ν1 =6 ν2 =6 ν3 =10 ν4 =-1
 Cont…

• Evaluation of empty cells [Second Iteration]

• The unoccupied cells to be evaluated are: P1-C1, P1-C4, P2-C2,
P2-C4, P3-C1 and P3-C2
Unoccupied Cells Reduced Cost
P1-C1 8-0-6= 2
P1-C4 9-0-1 = 8
P2-C2 12-3-6 = 3
P2-C4 7-3-(-1) = 5
P3-C1 14-6-6 = 2
P3-C2 9-6-6= -3→ results in highest cost reduction
Entering variable: Cell P3-C2
 Cont…

• Looking at the stepping stone path of cell P3-C2, we can see

that the minimum negative amount is 10 at cell P3C3, we
develop the improved solution.

To
From City 1 City 2 City 3 City 4 Supply
Plant 1 8 * 6 * 10 9 35
20 15
Plant 2 * 9 12 * 13 7 50
45 5
Plant 3 14 9 * 16 * 5 40
10 30
Demand 45 20 30 30
 Cont…

• Improved solution from the second iteration

To
From City 1 City 2 City 3 City 4 Supply
Plant 1 8 * 6 * 10 9 35
10 25 u1 =0
Plant 2 * 9 12 * 13 7 50
45 5 u2 =3
Plant 3 14 * 9 16 * 5 40 u3 =3
10 30
Demand 45 20 30 30
ν1 =6 ν2 =6 ν3 =10 ν4 =2
 Cont…

• Evaluation of empty cells [Third Iteration]

• The unoccupied cells to be evaluated are: P1-C1, P1-C4, P2-C2,
P2-C4, P3-C1 and P3-C3
Unoccupied Cells
Unoccupied Cells Reduced Cost
Reduced Cost
P1-C1
P1-C1 8-0-6= 22
8-0-6=
P1-C4
P1-C4 9-0-2 == 77
9-0-2
P2-C2
P2-C2 12-3-6 == 33
12-3-6
P2-C4
P2-C4 7-3-2 == 22
7-3-2
P3-C1
P3-C1 14-3-6 == 55
14-3-6
P3-C3
P3-C3 16-3-10= 33
16-3-10=

Since all evaluations are positive, the optimal solution is found

 Cont…

• The optimal solution is summarized in the following table

From To Quantity (million Cost
kwh)
Plant 1 City 2 10 60
Plant 1 City 3 25 250
Plant 2 City 1 45 405
Plant 2 City 3 5 65
Plant 3 City 2 10 90
Plant 3 City 4 30 150
Total optimal minimum transportation cost $1020
It matches with the stepping-stone solution
Special Issues in Transportation Problem

• There are a number of special issues in relation to the

transportation model. They are:
1. Alternate optimal solutions
2. Unbalance transportation problems
3. Degeneracy (too few occupied cells to permit evaluation
of a solution)
4. Unacceptable or prohibited route assignments
5. Maximization problems
 Cont…

1. Alternate optimal solutions

– The existence of an alternate solution is signaled by an
empty cell’s evaluation in optimal table equal to zero.
– We can find the alternate solution by reallocating the
maximum number of units possible around the stepping-
stone path for that cell.
2. Unbalanced problem
– When there is unequal supply and demand
– Resolved by introducing dummy sources or dummy
destinations as necessary with cost coefficients of zero
 Cont…

• A dummy row is added if supply is less than demand and a

dummy column if demand is less.
• Example To:
Project #1 Project #2 Projec Supply
From: t #3
To: 4 2 8
Project Project Projec Supply Farm A 50 50 100
From: #1 #2 t #3
4 2 8 5 1 9
Farm A 50 50 100 Farm B 150 50 200

5 1 9 7 6 3
Farm B 150 50 200 Farm C 120 120

7 6 3 0 0 0
Farm C 120 120 Dummy 80 80

Demand 50 150 300 Demand 50 150 300 500

DD≠ SS DD=SS (Balanced)

 Cont…

3. Degeneracy
– A solution is degenerate if the number of occupied cells is
less than the number of rows plus the number of columns
minus one.
– i.e., there are too few occupied cells to enable all the empty
cells to be evaluated.
– To solve the problem, place a zero quantity in one of
unoccupied cells and proceed computing improvement
indices
– Other method is placing a delta () in one of the empty
cells.
 Cont…

• The delta represents an extremely small quantity (e.g. 0.001

unit).
• it is so small that supply and demand for the row and column
involved will be unaffected
• Example:
To Customer Customer Customer Warehouse
From supply
1 2 3
100 $8 $2 $6
Warehouse 1 100

$10 $9 $9
Warehouse 2  100 20 120

$7 $10 $7
Warehouse 3 800 80

Customer 100 100 100 300

demand
 Cont…

4. Unacceptable Routes
• In some cases, an origin-destination combination may be
unacceptable.
• This may be due to weather factors, equipment breakdowns,
labor problems that may make certain routes undesirable.
• One way of overcoming the problem is to assign a cost that
is extremely large in that cell (or a very big +M).
• The prohibited route may appear in a non-optimal solution,
but it will be eliminated by the time the optimal solution is
reached.
 Cont…

5. Maximization Problem
• Some transportation type problems concern maximizing
profits or revenues.
• Such problems can be handled by adding one additional step
at the start.
• i.e., converting the whole table in to opportunity cost table.
• 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, and
use the regular procedure to solve.
The Assignment Problem (AP)

An assignment problem is a special case of a transportation

problem in which all supplies and all demands are equal to 1.
Assignment of workers to machines, clerks to various counters,
salesmen to different sales areas, service crews to different
districts, are typical examples of these.
It seeks to minimize the total cost assignment of m workers to
m jobs, given that the cost of worker i performing job j is cij.
In a balanced model number of jobs is equal to number of
machines or persons (m=n).
In unbalanced problems dummy row/column will be added.
 Cont…

Problem definition
– m workers are to be assigned to m jobs
– Each man/machine is loaded with one and only one job.
– Each man/ machine is independently capable of
handling any of the jobs being presented.
– A unit cost (or profit) Cij is associated with worker i
performing job j.
– Objective is to minimize the total cost (maximize the
total profit) of assigning workers to jobs
The Network Representation of an AP

• The network representation of an assignment problem with

three workers and three jobs is shown below.
c11
1 1
c12
c13
c21
c22
2 2
c23
c31
c32
3 c33 3

WORKERS JOBS
Linear Programming Formulation of AP

• Linear Programming Formulation:

Min cijxij
ij

S.t. xij = 1 for each worker i

j
xij = 1 for each job j
i
xij = 0 or 1 for all i and j.
Hungarian Assignment Method (HAM)

• Step 1: Find the minimum element in each row of the m x m

cost matrix.
– Construct a new matrix by subtracting from each cost the
minimum cost in its row.
– For this new matrix, find the minimum cost in each column.
– Construct a new matrix (called the reduced cost matrix) by
subtracting from each cost the minimum cost in its column.
• Step 2: Draw the minimum number of lines (horizontal, vertical,
or both) that are needed to cover all the zeros in the reduced
cost matrix.
 Cont…

– If m lines are required, then an optimal solution is

available among the covered zeros in the matrix. If fewer
than m lines are needed, then proceed to step 3.
• Step 3 Find the smallest nonzero element (call its value k) in
the reduced cost matrix that is uncovered by the lines drawn
in step 2.
– Now subtract k from each uncovered element of the
reduced cost matrix and add k to each element that is
covered by two lines.
– Return to step 2.
Example

Machineco has four machines and four jobs to be completed.

Each machine must be assigned to complete one job. The time
required to set up each machine for completing each job is
shown below. Machineco wants to minimize the total setup
time needed to complete the four jobs.
Setup Times for Machineco
Time (Hours)
Machine Job 1 Job 2 Job 3 Job 4
1 14 5 8 7
2 2 12 6 5
3 7 8 3 9
4 2 4 6 10
LP Model for the Machineco Problem

• According to the setup table Machinco’s problem can be

formulated as follows (for i,j=1,2,3,4):
MinZ  14 X 11  5 X 12  8 X 13  7 X 14  2 X 21  12 X 22  6 X 23  5 X 24
 7 X 31  8 X 32  3 X 33  9 X 34  2 X 41  X 42  6 X 43  10 X 44
s.t. X 11  X 12  X 13  X 14  1
X 21  X 22  X 23  X 24  1
X 31  X 32  X 33  X 34  1
X 41  X 42  X 43  X 44  1
X 11  X 21  X 31  X 41  1
X 12  X 22  X 32  X 42  1
X 13  X 23  X 33  X 43  1
X 14  X 24  X 34  X 44  1
Xij  0orX ij  1
Solution (HAM)

• Step 1a: Row reduction

Time (Hours)
Machine Job 1 Job 2 Job 3 Job 4
1 9 0 3 2
2 0 10 4 3
3 4 5 0 6
4 0 2 4 8
• Step 1b: Column reduction
Time (Hours)
Machine Job 1 Job 2 Job 3 Job 4 #CLs ≠ m/n
1 9 0 3 0
2 0 10 4 1
3 4 5 0 4
4 0 2 4 6
Select a minimum uncovered element
Solution

• Step 2: Draw the minimum number of lines

– Since the number of lines is only 3 we need to carry on our iteration
by selecting the minimum uncovered element (number)
• Step 3: Select the minimum uncovered number
– The minimum uncovered element is 1 (circled in the previous slide).
• Revised Solution
Time (Hours)
Machine Job 1 Job 2 Job 3 Job 4
1 10 0 4 0
2 0 9 4 0
3 4 4 0 3
4 0 1 4 5
 Cont…

• Step 4: The minimum number of lines to cover all 0's is four.

– Thus, there is a minimum-cost assignment of 0's with this
tableau. The optimal solution is found.
• The optimal assignment is:

Machines Jobs Cost Total Cost

3 Job 3 3
4 Job 1 2
2 Job 4 5
1 Job 2 5 15 Hours
Special Issues in Assignment Problem

1. Unbalanced Problems
• The problem is said to be unbalanced when the number of
rows is not equal to the number of columns
– OR, the number of jobs is not equal to the number of
workers.
• In such cases, dummy column(s)/row(s), whichever is
smaller in number, are introduced with zeros as the cost
elements.
• After this, the problem is solved in the usual manner.
• Solve the exercise given in the next slide
Exercise

A contractor pays his subcontractors a fixed fee plus mileage for

work performed. On a given day the contractor is faced with
three electrical jobs associated with various projects. Given
below are the distances between the subcontractors and the
projects. How should the contractors be assigned to minimize
total costs?
Cost (in birr)
Subcontractors A B C
Westside 50 36 16
Federated 28 30 18
Goliath 35 32 20
Universal 25 25 14
 Cont…

2. Constrained/Prohibited/ Assignment Problems

– It happens sometimes that a worker cannot perform a
certain job or is not to be assigned a particular job.
– To cope with this situation, the cost of performing that job
by such person is taken to be extremely large (which is
written as M).
3. Multiple Optimal Solutions
– A situation wherein the various rows and columns, where
assignment are yet to be done, have all multiple zeros.
– All solutions are optimal and equally attractive
 Cont…

4. Maximization Problems
• If the objective is to maximize the profit, we can solve it by
converting the entire table in to the opportunity cost table,
and use the usual procedure.
• This is achieved by subtracting each of the elements of the
given pay-off matrix from the largest value.
Example:
A company plans to assign 5 salesmen to 5 districts in which it
operates. Estimates of sales revenue in thousands of birr for each
salesman in different districts are given in the following table. In your
opinion, what should be the placement of the salesmen if the
objective is to maximize the expected sales revenue?
 Cont…

• Data on the estimates of sales revenue (in thousands)

District
Salesman D1 D2 D3 D4 D5
S1 40 46 48 36 48
S2 48 32 36 29 44
S3 49 35 41 38 45
S4 30 46 49 44 44
S5 37 41 48 43 47
79