CHAPTER THREE

TRANSPORTATION AND ASSIGNMENT PROBLEMS

One important application of linear programming has been in the area of the physical distribution
(transportation) of resources, from one place to another, to meet a specific set of requirement.
This chapter describes two special –purpose algorithms: the transportation model and the
assignment model. Model formulation and manual solution are covered for each of these classes
of problems. Both transportation and assignment problems are members of a category of linear
programming techniques called network flow problems.
3.1. TRANSPORTATION PROBLEMS
Transportation problem deals with the distribution of goods from several points of supplies
(sources) to a number of points of demands (destinations).
Consider a corporation engaged in the manufacture of products. Most of such big corporations
are of “multiple-product” and “multi-unit” organizations having production units situated at
different places. Items are produced for sales. Sales take place at different markets which are,
again located at different places. It is not feasible to co-locate production and market. Markets
are located away from the manufacturing places. Hence products are sent to factory warehouses
set up near market outlets. Cost of product consists of production cost and distribution cost.

Cost of product = production cost + distribution cost

Distribution cost consists of mainly the transportation cost of items from its production
(manufacturing) center to the warehouses. Transportation techniques are designed to minimize
the distribution costs. In order to identify products, it is necessary to work out per unit
distribution cost of each product. We also know the production capacity of each product in each
factory is not fixed. The holding capacity of a warehouse or potential sales in each marketing
center is again a fixed quality which cannot be exceeded.
The characteristics of transportation problem are as follows:
1. A limited supply of one commodity is available at certain sources or origins.
2. There is a demand for the commodity at several destinations
3. The quantities of supply at each source and the demand at each destination are constant.
4. The shipping or transportation costs per unit from each source to each destination are
assumed to be constant.
5. No shipments are allowed between sources or between destinations. All supply and demand
quantities are given in whole number or integers.
6. The problem is to determine how many units shipped from each source to each destination so
that all demands are satisfied at the minimum total shipping costs.

Operational Research Page 1

  Uses of transportation techniques:
1. Reduce distribution or transportation cost
2. Improve competitiveness of product
3. Assist proper location of warehouses
3. Assist proper location of new factories or plants being planned.
4. Close down warehouses which are found costly and uneconomical.

 The objective of transportation problem is:

1. To identify the optimal shipping routes-minimum cost route
2. To identify the maximum amount that can be shipped over the optimum route
3. To determine the total transformation cost or the profit of transportation
3.1.1. The Transportation Method
The solution algorithm to a transportation problem may be summarized into the following steps:
Step 1:
Formulate the problem and set up in the matrix form
The formulation of the problem is similar to the linear programming. Here the objective function
is the total transportation cost and the constraints are the supply and demand available at each
source and destination respectively.
Step 2:
Obtain an initial basic feasible solution
There are 3 methods to find the initial feasible solution.

1. North-West Corner Method (NWCM)

2. Least Cost Method (LCM)
3. Vogel’s Approximation Method (VAM)
The initial solution obtained by any of the three methods must satisfy the following condition:
i. The solution must be feasible
i.e.: It must satisfy all the supply and demand constraints
ii. The number of positive allocations must equal to m+n-1, where m=the number of rows (or
origins or supply centers) and n= the number of columns(or destination centers or demand
centers)
Example:
m=3 origins and n=4 destinations ==>m+n-1=3+4 -1=6 (i.e. the transportation model should
have 6 occupied cells).
Note:
The number of occupied cells < m+n-1==> degenerate solution

Operational Research Page 2

Step 3:
Test the initial solution for optimality
If the current solution is optimal, then stop. Otherwise, determine the new improved solution.
Step 4:
Repeat step 3 until an optimal solution is reached
3.1.2. Linear programming formulation of the transportation problem
Example
Suppose that a firm has three factories /sources of supply/ & four warehouses /point of demand/.
The firm's production capacity at the three factories, the demand for the four distribution
centers located at various regions & the cost of shipping each unit from the factories to the
warehouses through each route is given as follows:
Destinations (DD) =j
Origin Factory
W1 W2 W3 W4
(Supply) Capacity =i
Br.3 2 7 6
F1 5000
7 5 2 3 6000
F2
2 5 4 5
F3 2500
Requirements of the
Warehouses 6000 4000 2000 1500 13500
( Units of demand)

Using all the above information

i. Express the following transportation problem as an LPP
Solution
Let xij =The amount of commodity to be transported form source i (i =1,2,3 ) to destination j( j=
1,2,3,4).
Then the objective function of the problem (minimization of the total transportation cost) can be
formulated as:
MinZ = 3x11 +2x12 + 7x13 +6 x14 +
7x21 +5x22 +2x23 + 3x24 +
2x31+5x32 +4x33+5x34
Subject to the constraints
a. Supply constraints:
x11 +x12 +x13 +x 14 =5000 F1 supply constraint
x21 + x22 + x23 +x24 =6000 F2 supply constraint
x31 +x32 +x33+x34 = 2500 F3 supply constraint

Operational Research Page 3

 b. Demand constraints:
x11 + x21 + x31 = 6000 W1 demand constraint
x12 + x22 + x32 = 4000 W2 demand constraint
x13 + x23 +x33 = 2000 W3 demand constraint
x14 +x24 + x34 = 1500 W4 demand constraint
xij > 0 for all i& j
In the above LPP, there are m x n = 3x4 =12 decision variables & m + n = 3+4 =7 constraints.
Thus, if this problem is solved by the simplex method, then it may take considerable
computational time.
ii. The network representation of the transportation LPP is called Net work flow
Origin Destination centers
(Sources of Supply) (Point of demand centers)
F1 50000 3 W1 6000
2
6 7
7
F2 6000 5 W2 4000
2
3
W3 2000
2 5
4
F3 2500 5 W4 1500
This LPP has 12 shipping routes. The objective is to identify the minimum cost route (Least cost
route).
3.2. METHODS OF FINDING INITIAL FEASIBLE SOLUTION
There are several methods available to obtain an initial feasible solution. Here we shall discuss
only three different methods to obtain the initial feasible solution:
A. NORTH- WEST CORNER METHOD (NWCM)
This method does not take into account the cost of transportation on any route of transportation.
The NWCM gets its name because the starting point for the allocation process is the Upper Left-
hand (Northwest) corner of the transportation table. Therefore, allocate to the Northwest corner
as many units as possible.
Northwest corner rule
The following set of principles guides the allocation:
1. Begin with the upper left hand cell (Left, upper most in the table), & allocate as many units
as possible to that cell. This will be the smaller amount of either the row supply or the
column demand. Adjust the row & column quantities to reflect the allocation.

Operational Research Page 4

 2. Subtract from the row supply & from the column demand the amount allocated
3. If the column demand is now zero, move to the cell next to the right, if the row supply is zero,
move down to the cell in the next row.
If both are zero, move first to the next cell on the right then down one cell.
4. Once a cell is identified as per step (3), it becomes a northwest cell. Allocate to it an amount as
per step (1)
5. Repeat, the above steps (1) - (4) until all the remaining supply and demand is gone.
Example:
1) Consider the following transportation problem:
To
Store Store Store Store
Supply
From 1 2 3 4
Plant 1 19 30 50 10
7

Plant 2 70 30 40 60 9

Plant 3 40 8 70 20 18

8 7 14 34
Demand 5

a. Develop an initial feasible solution using the NWCM

b. Compute the total cost for this solution.
Solution
a. Table: Initial feasible solution
To
Store Store Store Store
From Supply
1 2 3 4
Plant 1 19 30 50 10
7
5 2
Plant 2 70 30 40 60 9
6 3
Plant 3 40 8 70 20 18
4 14
Demand 5 8 7 14 34

Check that the solution is feasible or not:

==>m + n-1; m=3 and n=4  3+4-1= 6 cells occupied (Feasible solution)
The total transportation cost of the initial feasible solution derived by the NWCM is:
Route Unit Per unit Total

Operational Research Page 5

From To Shipped X cost ( $) = Cost ( $)
Plant 1 Store 1 5 19 95
plant 1 Store 2 2 30 60
Plant 2 Store 3 6 30 180
Plant 2 Store 4 3 40 120
Plant 3 Store 4 4 70 280
Plant 3 Store 4 14 20 280
Total Cost= $ 1015

Note: NWCM does not consider the cost factor for allocation.
Exercise:
1. Determine an initial basic feasible solution to the following transportation problem using
NWCM. Compute the total cost for this solution
Destination
A B C Supply
S1 2 7 14 5
S2 3 3 1 8

S3 5 4 7 7
S4 1 6 2 14
Demand 7 9 18
Answer: X11=5, X21=2, X22=6, X32=3, X33=4, X43=14, and Total cost =$102
Note:
1. Total Supply= Total demand ===> Balanced TP
2. Total Supply ≠ total demand ===> Unbalanced TP
3. Convert the unbalanced TP into a balanced TP by using dummy destination/dummy source.
* If total Supply > Total demand, then create a fictitious or artificial destination called
dummy destination
i.e: total Supply > Total demand===> Add dummy column
* Excess demand (Supply < demand)
- Add a dummy source
- Add a dummy row
Note: the cost of “shipments” to the dummy is usually set at zero ==> No real cost

Example
Develop an initial feasible solution using NWCM

Operational Research Page 6

 Table: Unbalanced transportation table
R S T Supply
A 1 2 3 100
B 4 1 5 110

Demand 80 120 60 210

260
Solution:
R S T Supply
1 2 3
A 100
80 20
4 1 5
B 110
100 10
0 0 0
Dummy 50
50
Demand 80 120 60 260
Answer: X11=80, X12=20, X22=100, X23=10, X33=50 Total cost =$270
Exercise
Consider that Harley's Sand & Gravel Pit have contracted to provide topsoil for three residential
housing developments. Topsoil can be supplied form three different “farms" as follows:
_______________________________________________________________
Weekly Capacity
Farm (Cubic Yards)
A 100
B 200
C 200
_________________________________________________________________
Demand for the topsoil generated by the construction projects is:
_____________________________________________________________
Weekly Demand
Project (Cubic Yards)
1 50
2 150
3 300
_______________________________________________________________
The manager of the sand & gravel pit has estimated the cost per cubic yard to ship over each of
the possible routes:

Operational Research Page 7

 _______________________________________________________________
Costs per cubic yard to
From Project # 1 Project #2 Project #3
Farm A $4 $2 $8
Farm B 5 1 9
Farm C 7 6 3

_______________________________________________________________
Required
Develop the initial feasible solution using NWCM & compute the total cost for this solution.
B. THE LEAST- COST METHOD (LCM) or
(LARGEST- PROFIT) METHOD
LCM is the method used a minimum cost in the allocation. It begins a solution by sequentially
assigning to the ratios or cells with the minimum cost as many units as possible. The first
allocation be made to the cell with the lowest cost (the highest profit in a maximization case)
The Least- Cost Method yields not only an initial feasible solution but also one that is close to
optimal in small problems.
Example
[Link] that a firm has three factories / sources of supply /& four warehouses/point of
demand/. The firm's production capacity at the three factories, the demand for the four
destination centers located at various regions & the cost of shipping each unit from the
factories to the warehouses through each route is given as follows:
Destinations
Factory
W1 W2 W3 W4 Capacity
F1 3 2 7 6 5000
F2 7 5 2 3 6000
F3 2 5 4 5 2500
Demand 6000 4000 2000 1500 13500
Required:
a. Develop an initial feasible solution using NWCM & Compute the total cost
b. Develop an initial feasible solution using least-cost method & compute the total cost.

Solution:
Initial feasible solution

Operational Research Page 8

 Factory
W1 W2 W3 W4 Capacity
F1 3 2 7 6
5000
Factory 5000
7 5 2 3
F2 6000
1000 4000 1000
2 5 4 5
F3 2500
1000 1500
Demand 6000 4000 2000 1500 13500

m= 3, n =4 ==> 3+4 -1 =6 occupied cells (Feasible)

Routes Units Unit Total
From To Shipped X Cost =Cost
F1 W1 5000 3 $ 15000
F2 W1 1000 7 7000
F2 W2 4000 5 20000
F2 W3 1000 2 2000
F3 W3 1000 4 4000
F3 W4 1500 5 7500
Total transportation cost =$55,500

b.
Factory
W1 W2 W3 W4 Capacity
3 2 7 6
F1 5000
1000 4000
7 5 2 3
F2 6000
2500 2000 1500
2 5 4 5
F3 2500
2500
Demand 6000 4000 2000 1500 13500
Routes Units Unit Total
From To Shipped X Cost =Cost
F1 W1 1000 3 $ 3000

Operational Research Page 9

 F1 W2 4000 2 8000
F2 W1 2500 7 17500
F2 W3 2000 2 4000
F2 W4 1500 3 45000
F3 W1 2500 2 5000
Total transportation cost =$42,000

m= 3, n=4 ==> 3+4-1 =6 occupied calls (Feasible)

Least- Cost method is better than the NWCM because it considers cost factories
2. Develop the initial feasible solution for the following TP using the least-cost method (LCM)
Destination D E F G Supply
Source
A 1 5 3 4 100
B 4 2 2 5 60
C 3 1 2 4 120
demand 70 50 100 60 280
Solution
The 1st allocation be made to the cell with the least-cost. Cells AD & CE both have the lowest
cost f $1. Cell AD is selected 1st because more units can be allocated to it (70) than to cell CE
(50).
Cell CF is filled in 1st since a larger quantity (120-50-70) can be placed there. Then, the
remaining requirement of 30 for column F is allocated to cell BF & source B's supply is reduced
to 30.
The initial solution by the least -cost method
destinat
Source
D E F G Supply
A 1 5 3 4 100
70 30
B 4 2 2 5 60
30 30
C 3 1 2 4 120
50 70
Deman
70 50 100 60 280
d
m=3, n=4 ==> 3+4-1 = 6 occupied cells (feasible)
3. Develop an initial feasible solution using LCM
R S T Supply
A 1 2 3 100

Operational Research Page 10

 B 4 1 5 110
Demand 80 120 60
Solution
R S T Supply
A 1 2 3 100
80 10 10
B 4 1 5 110
110
Dummy 0 0 0 50
50
Demand 80 120 60

Total transportation cost=80x1+10x2+10x3+110x1+50x0=$240

Exercise
Three garment plants are available for monthly education of four styles of men's shirts. The
capacities of the three plants are 45,000, 93,000 and 60,000 shirts. The number of shirts required
in style "a" through "d" are 28,000, 65,000, 35,000 & 70,000, respectively. The profits, in $ per
shirt, at each plant for each style are shown below.
Table: The garment plants' profit.
STYLE
a B c d
PLANT
1 8 12 -2 6
2 13 4 3 10
3 0 7 11 8
How many shirts of each type to produce in each plant so that profit is maximized?
Answers: Total profit= $2,119,000 (Hint: Select the largest per unit profit, first & use largest-
profit method)
2. Determine an initial feasible solution to the following transportation problem
Using LCM

A B C D Supply
S1 1 5 3 3 34
S2 3 3 1 2 15
S3 0 2 2 4 12
S4 2 7 2 4 19
demand 21 25 17 17
C. VOGEL'S
APPROXIMATION METHOD (VAM)
Or

Operational Research Page 11

 PENALTY METHOD
VAM is preferred to the other two methods described above. In this method each allocation is
made on the basis of the opportunity (or penalty or extra) cost that would have incurred if
allocation in certain cells with minimum unit transportation cost were missed.
In this method allocation are made so that the penalty cost is minimized. The advantage of this
method is that it gives an initial solution which is nearer to an optimal solution or is the optimal
solution itself.
VAM determines the penalty for not using the minimum cost routes, where the objective is to
avoid large penalties so that the penalty from not using the routes is minimized.
The steps in VAM are as follows:
1. Calculate penalties for each row (column) by taking the smallest & the next smallest unit
transportation cost in the same row (column)
This difference indicates the penalty or extra cost which has to be paid if one fails to
allocate to the cell with the minimum unit transportation cost
2. Select the row or column with the largest penalty & allocate as much unit as possible in the
cell having the least cost in the selected row or column satisfying the conditions.
If there is a tie in the values of penalties, then t can be broken by selecting the cell where
maximum allocation can be made.
3. Adjust the supply & demand & cross out the satisfied row or column
If a row or column is satisfied simultaneously, only one of them is crossed out & the
remaining row (column) is assigned a zero supply (demand) .Any row or column with zero
supply or demand should not be used in computing future penalties.
4. Repeat step 1 to 3 until the entire available supply at various sources & demand at various
destinations are satisfied.
Example:
1. Determine an initial basic feasible solution to the following transportation
problem using VAM.

Warehouse
A B C D Supply Row difference or Row
penalty
or opportunity cost

2 2 - - - -
Operational Research Page 12
2 2 2 2 5 0
 Factor F1 2 2 0 4
25
y
5 20
F2 5 9 8 3
25
15 5 5
F3 6 4 3 2
10
10
Demand 20 15 20 5 60
Column difference 3 2
3 1
or Column penalty
or opportunity cost 3 2 -
1

1 5 -
1

0 0 -
0
m= 3, n=4 ==> 3+4-1 =6 Occupied cells (feasible)
The transportation cost associated with this solution is:
Total cost= 5x2 + 20x0+15x5x9 =+95x3+10x4= $185
2. A dairy firm has three plants located in different regions. The daily milk production at each
plant is as follows:
Plant 1: 6 million liters.
Plant 2: 1 million liters, &
Plant 3: 10 million liters
Each day the firm must fulfill the needs of its four distribution centers. Minimum
requirement at each center is as follows.
Distribution center 1: 7 million liters
" " 2: 5 " "
" " 3: 3 " "
" " 4: 2 " "
Cost of shipping one million liters form each plant to each distribution center is given in the
following table in hundreds of dollars.
Distribution Center
D1 D2 D3 D4
P1 2 3 11 7
Plant P2 1 0 6 1
P3 5 8 15 9

Find the initial basic feasible solution by:

a. North-west corners method

Operational Research Page 13

 b. LCM
c. VAM if the object is to minimize the total transportation cost
Answer:
a. Total cost = $11, 600
b. Total cost= $11,200
c.
D1 D2 D3 D4 Supply Row Penalty
2 3 11 7 6 1 1 5 -
P1
1 5
1 0 6 1 1 1 - - -
P2
1
5 8 15 9 10 3 3 4 4 6
P3
6 3 1
Demand 7 5 3 2
Column
Penalty

1 3 5 6
3 5 4 2
3 - 4 2
0 - 0 0

m+n -1 +3+4-1 =6 ==>the solution is non-degenerate.

Exercise
1. Determine an initial basic feasible solution to the following transportation problem by VAM
Destination
D1 D2 D3 Supply D4
S1 21 16 15 3 11
Source S2 17 18 14 13 13
S3 32 27 18 41 19
Demand 6 10 12 15
2. Determine an initial feasible solution to the following transportation problem using
a. NWCM
b. LCM, &
c. VAM
Destination

Operational Research Page 14

 D1 D2 D3 D4 Supply
A 11 13 17 14 250
Source B 16 18 14 10 300
C 21 24 13 10 400
Demand 200 225 275 250

3.3. OPTIMALITY TESTS

Once an initial solution is available, the next step is to check its optimality. An optimal solution is one in
which there is no opportunity cost. That is, there is no other set of transportation routes
(allocations) that will reduce the total opportunity cost. Thus we have to evaluate each
unoccupied cell (represents unused route) in the transportation table in terms of opportunity cost.
The purpose of the optimality test is to see if the proposed solution just generated can be
improved or not. The solution to be checked for optimality must be non-degenerate i.e the no of
occupied cells must be m+n-1.
The Procedure for testing optimality is analogous to that of the simplex method. A distinction is
made between basic variables, those associated with occupied cells & non-basic variables, those
associated with the empty cells.
For each empty cell, the effect of changing it to an occupied cell is examined. If any of these
changes are favorable, the solution is not optimal & a new solution must be designed. A
favorable change means an increase in the value of the objective function in maximization
problems or a decrease in minimization problems.
Optimum solution to a TP can be obtained by following two methods. These methods are much
simpler compared to simplex method of an LPP.
A. Stepping stone Method
B. Modified Distribution method (MODI Method)
A. Stepping-stone method
The Stepping-stone method is an iterative technique for moving from an initial feasible solution
to an optimal solution in transportation problems.
For the stopping- stone method to be applied to a transportation problem, one rule about the n o
of shipping routes being used must be observed. The rule is:
“The No of occupied routes (or squares) must always be equal to one less than the sum of the
no of rows plus the no of columns."
i.e. Occupied shipping routes (squares) = N o of rows + No of columns -1= Non degenerate
solution.
Rules for drawing each closed loop:

Operational Research Page 15

1. Select an unused square (cell) to be evaluates.
[Link] at this cell, trace a closed loop going clockwise draw an arrow to an
occupied cell in the same row (or column).
3. Move vertically or horizontally (but never diagonally) to another occupied cell “stepping –
over” unoccupied or occupied cells (if necessary) without changing them. Follow the same
procedure to other occupied cells until returning to the original empty cell.
4. Begin with a plus (+) sign at the unused cell, place alternative (-) signs and plus signs on each
corner square of the closed path just traced.
i.e. At each turn of the loop (the loop may cross over itself at times), plus and minus signs are
alternately placed in the cells, starting with a + sign in an empty cell.
5. There must be exactly one cell with a + sign and exactly one cell with a - sign in any row or
column in which the loop turns.
6. An even no of at least four cells must participate in a loop and the occupied cells can be
visited once and only once.
7. Repeat steps 1 to 4 until an improvement index has been calculated for all unused squares
(cells). If all indices computed are greater than or equal to zero, an optimal solution has been
reached. If not, it is possible to improve the current solution and decrease total shipping costs.
Note: In a non-degenerate problem, there is only one possible way of drawing the loop for each
empty cell.
How to find the value of a cell evaluator?
The value of a cell evaluator is the sum of the per unit shipping costs in the gaining cells less the
sum of the per unit shipping costs in the losing cells of the closed loop. This evaluation process
must be extended to all unoccupied cells.
1. The test of optimality for a minimization (cost) problem:
If one or more of the cell evaluators is negative, the existing solution is not optimal.
i.e: For minimization (cost) problems, all the cell evaluators must be positive for
optimality.
 Analysis of test:
Check all the empty cells and select for improvement the one with the largest
improvement potential.
 If the solution is not optimal, the next step in the transportation method is to find a
better solution. The operations in this step are:
a. Identify the “incoming" cell (the empty cell to be occupied)
In a minimization case, the incoming cell is located by identifying the
most negative cell evaluator.
b. Design an improved solution
-By shifting units form cell to cell
2. The test of optimality for a maximization (profit) case:

Operational Research Page 16

 : Is the reversed of minimization case
-If one or more of the cell evaluators is positive, the existing solution is not optimal.
i.e: for a maximization (profit) case, all the cell evaluators must be negative for
optimality. If any cell evaluation is positive, the solution is not optimal.
Note:
 A cell evaluator of 0 indicates the existence of another solution just as good as the current
solution. Thus, in the final solution, if cell evaluators of 0 exist, this indicates the
existence of multiple optimal solutions.
 If two or more cells have the same value, then either may be selected.
 If two or more of the "losing" cells contain the same no of units, both will become empty
simultaneously and a “degenerate" solution will result.
 For the minimization case; when one or more cell evaluators are negatives, the cell with
the largest negative should be brought into solution because that route has the largest
potential for improvement per unit.
 The loop starts and ends at the selected unoccupied cell. Every corner element of the
loop must be an occupied cell.
Example:
1. Use NWCM to find initial feasible solution and test the solution for optimality.
Project Project Projec SS
A B t
C
Farm

F1 4 2 8 100
F2 5 1 9 200
F3 7 6 3 200
DD 50 150 300 500
Solution
Initial feasible solution
Project Project Projec SS
A B t
C
F1 4 2 8 100
50 50
F2 5 1 9 200
100 100
F3 7 6 3 200
200
DD 50 150 300 500
m=3, n=3==> 3+3-1=5(Non-degenerate
solution)

Operational Research Page 17

Total transportation cost = $[50x4+50x2+100x1+100x9+200x3] = $1900
Project Project Projec SS Evaluation path for the unoccupied cells
A B t
C Table: Test of optimality
F1 4 2 8 100
50 50 - +
F2 5 1 9 200
100 + 100-
F3 7 6 3 200
200
DD 50 150 300 500
Unoccupied cells Cell evaluators
(F2 ,A) +5-4+2-1=+2
(F1 ,C) +8-9+1-2=-2
(F3 ,A) +7-4+2-1+9-3=+10
(F3 ,B) +6-1+9-3=+11

The negative value for cell (F1, C) indicates an improved solution is possible. For each unit we
can shift into that cell, the total cost will decrease by $2. The next question is how many units
can be reallocated into that cell while retaining the balance of supply and demand for that table?
The Stepping- stone path for cell (F1, C) is:
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. There are
two quantities in negative positions, 50 and 100. Because 50 is the smaller quantity, that amount
will be shifted in the following manner: Subtract 50 units from each cell on the path with a -
sign and add 50 units to the quantity of each cell with a + sign in it.
With each iteration (new solution), it is necessary to evaluate the empty cells to see if further
improvements is possible.
The distribution plan after reallocation of 50 units is:
A B C SS
F1 4 2 8 100
50 50
F2 5 1 9 200
150 50
F3 7 6 200
3
DD 50 150 200
300 500
Table: Test of optimality
Unoccupied cells Cell evaluators

Operational Research Page 18

 (F1 ,B) +2 -8+9-1 =+2

(F2 ,A) +5 -4+8-9 =0

(F3 ,A) +7-4+8-3 =+8

(F3 ,B) +6-1+9-3= +11

Because none of these no is negative, this is an optimal solution. Therefore, the total cost for the
distribution plan is:
The total transportation cost = $ (50x4 +50x8 150x1+50x9 +200x3) = $1,800
2. Consider the following TP
Destination
R S T Ss
A 1 2 3 100
B 4 1 5 110
Origin

21
dd 80 120 60 0
260
Note: Include the dummy cells to select the opportunity cost under VAM problems.
b. Test of optimality.
Table: Test of optimality
Unoccupied cells Cell evaluators
+4-1+2-1= +4
(B,R)
+5-1+2-3= +3
(B,T)
+0-1+3-0= +2
(D,R)
+0-2+3-0= +1
(D,S)
Since none of the cell evaluators is negative, the above feasible solution is optimal.
Thus, accordingly the distribution is as follows
A Supplies 80 units to warehouse R
A supplies 10 units to warehouse S
A Supplies 10 units to warehouse S
C Supplies 50 units to warehouse T
B Supplies 110 units to warehouse S

Operational Research Page 19

c. The total optimal shipping cost is = $240
Exercise:
Consider the following transportation problem

Stor Stor Store

Supply
e e 3
A 12 20 15 50
Warehouses

B 9 11 4 15
C 20 14 8 55
Dema 25 50 45 120
nd
a. Develop an initial feasible solution using the NWCM. And compute the total cost for this
solution.
b. Evaluate the solution using the stepping-stone method. Is the solution optimal? Explain.
c. What is the total cost for the optimal solution?

B. Modified Distribution Method (MODI Method)

The steps to evaluate unoccupied cells are as follows:
Step 1 for an initial feasible solution with m+n-1 occupied cells, calculate ui and v j for rows
and columns. The initial solution can be obtained by any of the three methods discussed earlier.
To start with, any one ofui ’s and v j ' s is assigned the value zero. It is better to assign zero for a
particular ui or v j where there are maximum number of allocations in a row or column
respectively, as it will reduce arithmetic work considerably. Then complete the calculation of
ui ' s and v j ' s for other rows and columns by using the relation
c ij=ui+ v j for all occupied cells (i,j).
Step 2 for unoccupied cells; calculate opportunity cost by using the relationship
d ij =c ij-(ui+ v j) for all i and j.
Step 3 examine sign of each d ij
I. If d ij >0, then current basic feasible solution is optimal
II. If d ij =0, then current basic feasible solution will remain unaffected but an alternative
solution exists

Operational Research Page 20

III. If one or mored ij <0, then an improved solution can be obtained by entering unoccupied
cell (i,j) in the basis. An unoccupied cell having the largest negative value of d ij is
chosen for entering in to the solution mix( new transportation schedule)

Steps 4 construct a closed path (or loop) for the unoccupied cell with largest negative
opportunity cost. Start the closed path with the selected unoccupied cell and mark a plus sign(+)
in this cell, trace a path along the rows( or columns) to an unoccupied cell, mark the corner with
minus sign(-) and continue down the column ( or row) to an occupied cell and mark the corner
with plus sign(+) and minus(-) alternatively. Close the path back to the selected unoccupied cell.
Step 5 select the smallest quantity amongst the cells marked with minus sign on the corners
of closed loop. Allocate this value to the selected unoccupied cell and add it to other occupied
cells marked with plus signs and subtract it from the occupied cells marked with minus signs.
Step 6 obtain a new improved solution by allocating units to the unoccupied cell according
to step 5 and calculate the new total transportation cost.
Step 7 test the revised solution further for optimality. The procedure terminates when all d ij
≥0, for unoccupied cells.
Remarks: the loop starts and ends at the selected unoccupied cell. It consists of successive
horizontal and vertical (connected) lines whose end points must be occupied cells, except for a
end point associated with entering unoccupied cell. This means that every corner element of the
loop must be an occupied cell. It is immaterial whether the loop is traced in a clockwise or anti
clock wise direction. However, for a given solution only one loop can be constructed for each
unoccupied cell.
Example:
1. Obtain an optimal solution to the transportation problem by MODI method given below:

Project Projec Projec Suppl

No 1 t t y
Farm 4 2 8 100
1
Farm 5 1 9 200
2
Farm 7 6 3 200
3
Dema 50 150 300 500
nd

Operational Research Page 21

Solution
Note:
Both the MODI and the stepping - stone method will yields the same values.

Remark:
Conventionally, we begin by assigning a value of zero as the index for row 1 (U1=0). Once row
index has been established, it will enable us to compute column index numbers for all occupied
cells in that row. Similarly, once a column index number has been determined, index numbers
for all rows corresponding to occupied cells in that column can be determined.
Consider the initial feasible solution of the given example by NWCM as shown below
Initial solution, NWCM

Proj Proje Proje

SS Ui
ect ct ct
4 2 8 100
Farm 1 U1=0
50 50
5 1 9 200
Farm 2 U2=-1
100 100
Farm 3 7 6 3 200 U3=-7
200
DD 50 150 300 500

Vj V1=4 V2=2 V3=1

To determine Cij , use the occupied cells.
For instance, C11=4, C12=2, C22=1, C23=9, and C33=3
Cij= Ui + Vj
==>C11= U1 +V1==>4=0+ V1==> V1=4 , U1=0 by convention
==>C12= U1 +V2==>2=0 +V2==> V2=2
==>C22= U2 +V2==>1= U2+ 0==> U2=-1
==>C23= U2 +V3==>9= -1+V3==> V3=10
==>C33= U3 +V3==>3= U3+10 ==> U3= -7
Note:
Cij≠ Ui + Vj (For unoccupied cells)
For instance, from the above information, C32 ≠ U3 + V2==>6≠-7+2
Table: Test of optimality

Operational Research Page 22

 Unoccupied cells Cell evaluators
Dij = Cij– (Ui + Vj)

(1,3) C13 – (U1 +V3)=8-(0+10)= -2

(2,1) C21 – (U2 +V1)=5-(-1+4)=+2
(3,1) C31– (U3 +V1)=7-(-7+4)=10
(3,2) C32– (U3 +V2)=6-(-7+2)=+11
In this case, we found hat cell (1, 3) had an evaluation of -2, which represented an improvement
potential of and $ 2 per unit. Hence, an improved solution is possible.
The stepping-stone path for call (1, 3) is:

Proj Proj Proj

Supply
No 1 No 2 No 3
4 2 8 100
Farm 1 - +
50 50
5 1 9 200
Farm 2
100 100
7 6 3 200
Farm 3
200
500
Demand 150 300
50
The distribution plan after reallocation of 50 units is:

Proj Proje Proje Suppl

Ui
ect ct ct y
Farm 4 2 8 100
U1=8
1 50 50
Farm 5 1 9 200
U2=9
2 150 50
Farm 7 6 3 200
U3=3
3 200
Dema 500
150 300
nd 50

Vj V1=- V2=-8 V3=0 Table: Test of optimality

4
Unoccupied cells Cell evaluators
Dij = Cij– (Ui + Vj)
(1,2) C12– (U1 +V2)=2-(-8+8)= 2
(2,1) C21 – (U2 +V1)=5-(-4+9)=0

Operational Research Page 23

 (3,1) C31– (U3 +V1)=7-(-4+3)=8
(3,2) C32– (U3 +V2)=6-(-8+3)=+11

Because none of the cell evaluators is negative, this is an optimal solution.

Thus, the total cost for the distribution plan =$1800
3.4. SPECIAL CASES
3.4.1. Degeneracy
A condition that occurs when the No of occupied cells in any solutions less than the N o of rows
plus the No of columns minus 1 in a transportation table.

i.e. No of occupied calls < m+ n -

1 .....................Degeneracy

If the No of occupied cells = m+n-1, then the solution is

The degeneracy in the transportation problems may occur at two stages:

1. when obtaining an initial solution
2. During improvement (or at any stage while moving towards optimal solution.
To resolve degeneracy, we processed by allocating a very small quantity close to zero to one or
more unoccupied cell so as to get m+n-1 number of occupied cells. This amount is denoted by a
Greek letter  (epsilon) or (delta). This quantity would not affect the total cost as well as
supply and demand values.
 = Almost zero
In a minimization transportation problem, allocate the smallest transportation cost to .
In a maximization transportation problem, it should be allocated to a cell that has a high pay off
value.
Insert  when it is able to create a closed loop for each occupied cell.
The purpose of epsilon/delta is to enable evaluation of the remaining empty cells. The choice of
location for the epsilon/delta can be somewhat tricky: some empty cells may be unsuitable if
they do not enable evaluations of remaining empty cells. Not all choices would be acceptable.
Actually, the No of epsilon/deltas needed will equal the difference between the N o of completed
cells and m+n-1. However; you will only be exposed to the most common case in which one
more completed cell is needed.
The epsilon/delta cannot be placed in a cell which later turns out to be in a negative position of a
cell path involved in reallocation because epsilon/delta will be the “smallest quantity a negative
position “and shifting that minute quantity around the cell path will leave the solution virtually

Operational Research Page 24

unchanged. Consequently, a certain amount of trial and error may be necessary before a
satisfactory location can be identified for epsilon/delta.

Example
1. Solve the following transportation problem.
1 2 Supp
1 3 3 ly
50
2 4 6 30
Dema
50 30 80
nd

Solution:
Using NWCM and MODI, the initial solution is:

1 2 Supply Ui

3 3
1 50 U1=0
50 
4 6
2 30 U2=3
30
Demand 50 30 80
Vj V1=3 V2=3

Cij= Ui + Vj
==>C11= U1 +V1==>3=0+ V1==> V1=3, U1=0 by convention
==>C12= U1 +V2==>3=0 +V2==> V2=3
==>C22= U2 +V2==>6= U2+3==> U2= 3
==>C33= U3 +V3==>3= U3+8 ==> U3= -5
Note: m=2 and n=2==>2+2-1=3==>Occupied cells=2< 3 (Degeneracy)

Table: Test of optimality

Unoccupied cell Cell evaluator
Kij = Cij– (Ui + Vj)

Operational Research Page 25

 (2,1) C21 – (U2 +V1)=4-(3+3) =-2

The optimal solution is:

1 2 Supply Ui

3 3
1 50 U1=0
20 30
4 6
2 30 U2=1
30
Demand 50 30 80
Vj V1=3 V2=3

Cij= Ui + Vj
==>C11=U1+V1==>3=0+V1==>V1=3, U1=0 by convention
==>C21= U2+V1==>4= U2+3==> U2=3
==>C12= U1 +V2==>3= 0+ V2==> V2= 3

Table: Test of optimality

Unoccupied cells Cell evaluators
Kij = Cij– (Ui + Vj)
(2,2) C22– (U2 +V2)=6-(1+3)= +2

The total cost= $(20x3+30x3+30x40=$270

3.4.2. Alternative Optimal solutions
The existence of alternative optimal solution can be determined by an inspection of the
opportunity costs, Dij for the unoccupied cells. If an unoccupied cell in an optimal solution has
opportunity cost of zero, then an alternative optimal solution can be formed with another set of
allocations without increasing the total transportation cost.
Exercise

Operational Research Page 26

XYZ Tobacco Company purchases tobacco and stores in warehouses located in the following
four cities.

warehouse location Capacity (Tones)

City A 90
City B 50
City C 80
city D 60
The warehouses supply tobacco to cigarette companies in three cities that have the following
demand:

Cigarette Company Demand (Tones)

L 120
P 100
Q 110
The following railroad shipping costs per ton (in hundred dollars) have been determined:

Warehouse L p Q
location
A 7 10 5
B 12 9 4
C 7 3 11
D 9 5 7
Because of rail road construction, shipments are temporarily from warehouse at city A to L
Cigarette Company.
A. Find the optimum distribution for XYZ Tobacco Company.
B. Are there multiple optimum solutions? If there are alternative optimum solutions,
identify them.

3.2 ASSIGNMENT PROBLEMS

The Assignment Problem(AP) refers to the class of LPPs that involves determining the most
efficient assignment of people to projects, sales people to territories, contracts to bidders, jobs
to machines, and so on. The objective is to assign a number of resources to an equal number of
activities so as to minimize total costs or total time or maximize total profit of allocation.

Operational Research Page 27

The problem of assignment arises because available resources such as men, machines, etc have
varying degrees of efficiency for performing different activities such as job. Therefore, cost,
profit or time of performing the different activities is different.
Assumptions:
The AP is a special case of TP under the condition that the number of origins is equal to the
number of destinations. Viz. m=n. Hence assignment is made on the basis of 1:1.
Following are the assumptions:
 Number of jobs is equal to the number of machines or persons
 Each man or machine is loaded with one and only one job.
 Each man or machine is independently capable of handling any of the job being presented.
 Loading criteria must be clearly specified such as “minimizing operating time” or “maximizing
profit”, or “minimizing production cost” or “minimizing throughout (production cycle) time” etc.
Remark:
 The AP is considered as a special TP in which the supply at each source and the demand at each
destination are always one unit.
 Since the supply and demand are always equal to one unit in each row and column, there is no need to
write them in the assignment table.
Example:
Service costs of different team assignment ($ in thousands)
Table: The assignment

Service
Team Z1 Z2 Z3
Supply
Servic Z1 Z2 Z3 ====>
e S1 20 15 31 1
S1 20 15 31
S2 17 16 33 1
S2 17 16 33
S3 18 19 27 1
S3 18 19 27
Demand 1 1 1

The above problem can be presented as a LPP as follows:

MinZ = 20x11 +15x12 + 31x13 +17x21 +16x22 +33x23 +18x31+19x32 +27x33
Subject to the constraints
a. Supply constraints:
x11 +x12 +x13 =1 S1 constraint
x21 + x22 + x23 =1 S2 constraint
x31 +x32 +x33 = 1 S3 supply constraint
b. Demand constraints
x11 + x21 + x31 = 1 Z1 constraint
x12 + x22 + x32 = 1 Z2 constraint

Operational Research Page 28

 x13 + x23 +x33 = 1 Z3 constraint
xij either 0 or 1 for all i, j
Since all xij can be either 0 or 1, there will be one assignment in each supply constraint and one
assignment in each demand constraint.
As in the transportation problem, assignment problems can be balanced or not. In a balanced
case, the number of objects to be assigned equals the number of objects to which they are
assigned. Unbalanced problem can be balanced by adding a dummy (dummies) with zero cost
coefficients.
3.2.1. Methods of solving assignment problems
An assignment problem can be solved by the following methods:
1. Enumeration method
2. Simplex method
3. Transportation method
4. Hungarian method
[Link]. Hungarian Method/Flood’s Technique/
The Hungarian Method (developed by Hungarian Mathematician D. Konig) of assignment
provides us with efficient method of finding the optimal solution without having to make a direct
comparison of every solution. It works on the principle of reducing the given cost matrix (the
principle of matrix reduction) to a matrix of opportunity costs, 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.
Opportunity costs show the relative penalties associated with assigning resource to an activity as
opposed to making the best or least-cost assignment. If we can reduce the cost matrix to the
extent of having at least one zero in each row and column, then it will be possible to make
optimal assignments.
Steps in solving assignment problems:
Step.1. Develop the cost table from the given problem
If the number of rows does not equal the number of columns and vice versa, then a dummy row
or dummy column must be added. The assignment costs for dummy cells are always zero.
Step 2. Find the opportunity cost table
i.e. The transformation of the cost matrix to what is termed as a total-opportunity cost matrix.

Operational Research Page 29

It involves two operations:
a. Perform row operation
i.e. Locate the smallest element in each row of the given cost table and then subtract that the
given cost table and then subtract that from each element of that row
b. Perform column operation
I.e. In the reduced matrix obtained from 2(a), locate the smallest element in each column and
then subtract that from each element of that column. Notice that each row and column now have
at least one zero value.
Step 3 make assignment in the opportunity cost matrix
a) Examine rows successively until a row with exactly one unmarked zero is obtained.
Make an assignment to this single zero by making a square around it
b) For each zero value that becomes assigned, eliminate (strike off) all other zeros in the
same row and/or column
c) Repeat steps 3(a) and 3(b) for each column also with exactly single zero value cell that
has not been assigned
d) If a row and/or column has two or more unmarked zeros and one cannot be chosen by
inspection, then chose the assigned zero cell arbitrarily
e) Continue this process until all zeros in rows/columns are either enclosed(assigned) or
strike off (x)

Step 4 optimality criteria

If the number of assigned cells is equal to the number of rows/columns, then it is optimal
solution. The total cost associated with this solution is obtained by adding original cost figures in
the occupied cells.

Steps 5 revise the opportunity cost table

Draw a set of horizontal and vertical lines to cover all the zeros in the revised cost table obtained
from step 3, by using the following procedure
a) For each row in which no assignment was made, mark a tick
b) Examine the marked rows, if any zero cell occurs in those rows, mark a tick to the
respective columns that contain those zeros

Operational Research Page 30

 c) Examine market columns. If any assigned zero occurs in those columns, tick the
respective rows that contain those assigned zeros
d) Repeat this process until no more rows or columns can be marked
e) Draw a straight line through each marked column and each unmarked row

If the number of lines drawn (or total assignment) is equal to the number of rows (or columns),
the current solution is the optimal solution, otherwise go to step 6
Step 6 develop the new revised opportunity cost table
a) From among the cells are not covered by any line, choose the smallest element. Call this
value k
b) Subtract k from every element in the cell not covered by a line
c) Add k to every in the cell covered by the two lines, i.e. intersection of two lines
d) Elements in cells not covered by one line remain unchanged

Step 7 repeat steps

Repeat steps 3 to 6 until optimal is obtained
Example:
1. A computer center has three programmers. The center wants three application programs to be
developed. The head of the computer center, after studying carefully the programs to be
developed, estimate the computer time in minutes required by the experts for the application
programs as follows:
Programs
Programmers

(Estimated time in
1 120 minute)
100 80
2 80 90 110
3 110 140 120

Assign the programmers to the programs in such a way that the total computer time is minimum.
Solution:
Steps 1 and 2:
a. Perform row reduction
The minimum time element in row 1, 2, and 3 is 80, 80 and 110 respectively. Subtract those elements
from all elements in their respective row. The reduced time matrix is:
Table: After row reduction

A B C
-80 1 40 20 0
-80 2 0 10 30
Operational Research Page
-110 31 3 0 30 10
b. Column reduction
Since column B has no one ‘0’, perform also column reduction. The minimum time element in columns
A, B and C is 0, 10 and 0 respectively. Subtract these elements from all elements in their respective
column to get the reduced time matrix.
Table: After column reduction

A B C
1 40 10 0
2 0 0 30
3 0 20 10
Step 3: make assignment in the opportunity cost matrix
a. In l assignment, start with row/column having one zero and cancel the alternative zeros(x)
Table: Test of optimal assignment

A B C
1 40 10 00
2 0 00 30
3 0
0 20 10
b. Count the number of occupied cells
If the number occupied cells are equal to the number of rows/columns, the optimal solution is obtained.

The pattern of assignment among programmers and programs with their respective time (in minute) is
given below:
Programmer Program Time (in minutes)
1 C 80
2 B 90
3 A 110
Total time=280 minutes
3.A
department has five employees with five jobs to be performed. The time (in hours) each man will take to
perform each job is given in the effectiveness matrix.

Employees

I II III IV V
A 10 5 13 15 16
Jobs

B 3 9 18 13 6

Operational Research Page 32

 C 10 7 2 2 2

D 7 11 9 7 12

7 9 10 4 12
E

How should the jobs be allocated, one per employees, so as to minimize the total man-hours?
Solution:
Table: After row reduction

I II III IV V
A 5 0 8 10 11
B 0 6 15 10 3
C 8 5 0 0 0

D 0 4 2 0 5

3 5 6 0 8
E

Since the number of lines less than the number of rows/columns, an improvement is possible.
Step 4. Improve the present opportunity cost table
This is done by the following operations;
a. Select the smallest entry (element) among all uncovered elements by the lines and subtract it from all
entries in the uncovered cells. this cell is 2
b. Add the same smallest entry to those cells in which lines intersect (cells with two lines them).
c. Cells with one line through them are unchanged to the improved table

I II III IV V
A 7 0 8 12 11
0
B 00 4 13 10 1
C 10 5 0 2 00
D 0 2 0 0 3
0
E 3 3 4 0 6

Since the number of assigned cells equals to the number of rows/columns, the solution is optimal.

Operational Research Page 33

 Job Employees Time (in minutes)
A II 5
B I 3
C V 2
D III 9

E IV 4

Total time=23 Hours

3. A manager has prepared the following table, which shows the costs for various
combinations of job-machine assignments:

Machine
(Cost in ’000s))
A B C
1 20 15 31
Job 2 17 16 33
3 18 19 27
a. What is the optimal (minimum-cost) assignment for this problem?
b. What is the total cost for the optimum assignment?
Solution:
Table: After row reduction Table: After column reduction

A B C A B C
-15 1 5 0 16 1 5 00 7
-16 2 1 0 17 2 1 0 8
-18 3 0 1 9 3 0 1 0
0
Table: optimal

A B C
1 4 0 0 6
2 00 0 7
3 0 2 00

Job Machine Cost(in $)

1 B 15000
2 A 17000
3 C 27000
Total optimal assignment=$59000
3.2.3 SPECIAL CASES IN THE ASSIGNMENT PROBLEMS

Operational Research Page 34

Certain situations can arise in which the model deviates slightly from that previously described. Among
those situations are the following:

A. Multiple Optimal Solutions

While making an assignment in the reduced assignment matrix, it is possible to have two or more ways to
strike off a number of zeros. Such situation indicates multiple optimal solutions with the same optimal
value of objective function. In such cases the more suitable solution may be considered by the decision-
maker.
In multiple optimal solutions, no unique 0 will exist at some point, resulting in more than one choice for
assignment and hence, more than one optimal solution. It should be noted that all optimal solutions will
yield the same value of the objective function.
Example:
1. Given this final assignment table, identify two optimal solutions.
Machine
(Estimated time in minute)
1 2 3
A 4 0 0
Job B 0 3 2
C 1 0 0
Solution
The first assignment must be B-1, because B-1 is the only 0 that appears in a single row or column.
Having made that assignment, there are two choices for the remaining two rows, and two choices for the
remaining two columns. This results in two possible solutions, as shown:
Machine Machine
(Estimated time in minute) (Estimated time in minute)
1 2 3 1 2 3
A 4 0 0 A 4 0 0
Job B 0 3 2 Job B 0 3 2
C 1 0 0 1 0
C 0

2. The foreman of a machine shop wants to determine a minimum cost matching for operators and
machines. The foreman has determined hourly cost for of four operators for the four machines, as shown
in the following cost table.
Machine
(Estimated cost in $)
A B C D
1 70 80 75 64
55 52 58 54
Operator

2
3 58 56 64 68
4 62 60 67 70

Required:

Operational Research Page 35

a. Determine the minimum-cost assignment for this problem
b. What is the total cost for the optimal assignment?
c. Is there an alternative optimal assignment? What is it? Calculate the total cost for the alternate optimal
assignment.
Solution:
Table: After row reduction Table: After column reduction

A B C D
A B C D 1 4 16 5 0
1 6 16 11 0
2 1 0 0 2
2 3 0 6 2
3 0 0 2 12
3 2 0 8 12
4 0 0 1 10
4 2 0 7 10 Table: Optimal
Assignments
A B C D
1 4 16 5 0
2 1 0 0 2
3 0 0 2 12
4 0 0 1 10

a. Optimal Assignment b.
Operator Machine Cost(in $)
4 A 62
3 B 56
2 C 58
1 D 64
Total cost =$240

c. Yes!
Operator Machine Cost(in $)
1 D 64
2 C 58
3 A 58
4 B 60
Total cost=$240
Alternative optimal assignment

Operational Research Page 36

B. Maximization case in assignment problems
There may arise situations when the assignment problem calls for maximization of profit, revenue, etc as
the objective function. Such problem may be solved by converting the given maximization problem into a
minimization problem by the following procedure:
i. Find the largest profit coefficient in the entire.
ii. Subtract each entry in the original table from the largest profit coefficient.
The transformed assignment problem so obtained can be solved by using the Hungarian method.

Example
1.A company has four territories open, and four salesmen available for an assignment. The territories are
not equally rich in their sales potential. Based on the past performance, the following table shows the
annual sales (in $) that can be generated by each salesman in each territory. Find the optimal
assignment and the maximum expected total sales.
Territory
I II III IV
Salesmen

A 42 35 28 21
B 30 25 20 15
C 30 25 20 15
D 24 20 16 12

Solution:
Convert maximization problem into minimization problem by subtracting all elements from the highest
element (i.e 42)
Thus, the equivalent cost table is:
I II III IV I II III IV
A 0 7 14 21 A 0 3 6 9

B 12 17 22 27 B 0 1 2 3

C 12 17 22 27 C 0 1 2 3

D 18 22 26 30 D 0 0 0 0

Thus, after improvement of the table, the optimal assignment is:

I II III IV
A 0 2 4 7

B 0 0 0 1

Operational
C 0 Research
0 0 1 Page 37
D 2 1 0 0
The pattern of two alternative optimal assignments among territories and salesmen with respective sale is
given below:

Assignment set I Assignment set II

___________________________________ _________________________________

Salesman Territory Sales($) Salesman Territory Sales($)

A I 42 A I 42
B III 20 B II 25
C II 25 C III 20
D IV 12 D IV 12
Total= $ 99 Total= $ 99
___________________________________ _________________________________
Exercise
Five salesmen are to be assigned to five territories. Based on the past performance, the following table
shows the annual sales man in each territory. Find the optional assignment.
T1 T2 T3 T4 T5

S1 26 14 10 12 9
S2 31 27 30 14 16
S3 15 18 16 25 30
S4 17 12 21 30 25
S5 20 19 25 16 10

C. Unbalanced Assignment problem

The Hungarian method of assignment requires that the number of columns and rows in the assignment
matrix be equal. However, when the given cost matrix is not a square matrix, the assignment problem is
called an unbalanced problem. In such cases a dummy row(s) or column(s) are added in the matrix (with
zeros as the cost elements) to make it a square matrix. After making the given cost matrix a square
matrix, the Hungarian method may be used to solve the problem.
Example
MEGA printing press, a publisher headquartered in Addis Ababa, wants to assign three recently hired
college graduates, Marta, Bakcha and Hirut to regional sales districts in Mekelle, Bahir Dare, and
DireDawa. But the firm also has an opening in Gambela and would send one of the three there if it were

Operational Research Page 38

more economical than a move to Mekelle, Bahir Dar and Dire Dawa. It will cost Br. 1,000 to relocate
Marta to Gambela, Br. 800 to relocate Baklcha there, and Br. 1,500 to move Hirut. What is the optimal
assignment of personnel to offices?
Office
Mekelle Bahir Dare Dire Dawa
Hire
Marta Br.800 Br 1,100 Br 1,200
Bekcha Br. 500 Br 1,600 Br 1,300
Hirut Br. 500 Br 1,000 Br 2,300

Solution
To balance the problem, we add a dummy row (person) with a zero relocation cost to each city.
City
C1 C2 C3 C4(Gambela)

P1 800 1,100 1,200 1,000

P2 500 1,600 1,300 800
Person
P3 500 1,000 2,300 1,500
Dummy 0 0 0 0

Table: After row reduction Table: Optimal Assignment

C1 C2 C3 C4
C1 C2 C3 C4
P1 0 300 400 200
P1 100 0 100 0
P2 0 1,100 800 300
P2 0 700 400 0
P3 0 500 1800 1000
P3 0 100 1400 700
Dummy 0 0 0 0
Dummy 400 0 0 100

Thus, an optimal assignment can be made at zero cells (squares).

Person City
Dummy(No person) Dire Dawa
Hirut Mekelle
Bekcha Gambela
Marta Bahir Dare

Cost =Br. (0+500+800+1,100)=Br.2,400

D. Restrictions on Assignments
In certain instances, it may happen that a particular match or pairing may be either undesirable or
otherwise unacceptable. For example, an employee may not have the skills necessary to perform a
particular job or a machine may not be equipped to handle a particular operation. In such cases, the cost
of performing that particular activity by a particular resource is considered to be very large (written as M
or  ) so as to prohibit the entry of this pair of employee-job into the final solution. When such a
restriction is present, a letter (M) is often placed in the table in the position that would represent a paring.

Operational Research Page 39

Analysis is performed as usual except the M is ignored throughout the analysis. That is, M is not used in
any reductions, nor is any value added to it or subtracted from it during the course of the analysis.
Example
1. In the modification of a plant layout of a factory four new machines M1, M2, M3 and M4 are to be
installed in a machine shop. There are five vacant places A, B, C, D and E available. Because of
limited space, machine M2 can not be placed at C and M3 cannot be placed at A. the cost of placing of
machine at place i (in $) is shown below.

Location
A B C D E

M1 9 11 15 10 11

Machine M2 12 9 - 10 9

M3 - 11 14 11 7

M4 14 8 12 7 8

Find the optimal assignment schedule.

Solution:
As the cost matrix is not balanced, add one dummy row (machine) with a zero cost element in that
row. Also assign a high cost, denoted by M, to the pair (M2, C) and (M3, A).

Apply the Hungarian method to solve the problem

A B C D E
M1 9 11 15 10 11

M2 12 9 M 10 9

M3 M 11 14 11 7

M4 14 8 12 7 8

M5 0 0 0 0 0

A B C D E

0
M1 2 6 1 2
Table: Optimal assignment

3 0 M 1 0
M2

M3 M 4 7 4
0
Operational Research Page 40
M4 7 1 5 0 1

M5
0
 The total minimum cost ($) and optimal assignments made are as follows:

Location Costs ($)

Machine
M1 A 9
M2 B 9
M3 E 7
M4 D 7
M5 (Dummy) C 0
Total = $32

Operational Research Page 41