CHAPTER V

DISTRIBUTION MODELS
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.

5.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

1
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.

 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

5.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

2
 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

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
5.1.2. Linear programming formulation of the
transportation problem
Example
Suppose that a firm has three factories /sources of supply/ & four
warehouses

3
/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
(Supply) W1 W2 W3 W4 Capacity =i
Br.3 7 6
F1 2 5000
7 2 3 6000
F2 5

2 4 5
F3 5 2500
Requirements of
the 400
Warehouses 6000 2000 1500 13500
0
( 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
b. Demand constraints:
x11 + x21 + x31 = 6000 W1 demand constraint
x12 + x22 + x32 = 4000 W2 demand constraint
x13 + x23 +x33 = 2000 W3 demand constraint

4
 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 5000 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).

5.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

5
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.

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 1 Store 2 Store 3 Store 4 Supply
From
Plant 1 19 30 50 10
7
70 30 40 60
Plant 2 9
40 8 70 20
Plant 3 18

5 8 7 14 34
Demand

a. Develop an initial feasible solution using the NWCM

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

5 8 7 14 34
Demand
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
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

7
 S4 1 6 2 14
Deman 7 9 18
d

Answer: X11=5, X21=2, X22=6, X32=3, X33=4, X43=4, 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
Table: Unbalanced transportation table
R S T Supply
A 1 2 3 100
B
4 1 5 110

Deman 80 120 60 210

260
d
Solution:
R S T Supply
1 2 3
A 100
80 20
4 1 5
B 110
100 10
Dumm 0 0 0
50 50
y
Deman
80 120 60 260
d

8
Answer:X11=80, X12=20, X22=100, X23=10, X33=50 Total cost =$270

Assignment
Consider that Harley's Sand & Gravel Pit has 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:
_______________________________________________________________

9
 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
1.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 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:

10
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
Factory
W1 W2 W3 W4 Capacity
F1 3 2 7 6
5000
5000
Factory 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 Shipped Cost =Cost
To X 3 $ 15000
F1 5000 7 7000
W1 1000 5 20000
F2 4000 2 2000
W1 1000 4 4000
F2 1000 5 7500
W2 1500 Total transportation =$55,500
F2 cost
W3
F3
W3
F3
W4
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

11
 Routes Units Unit Total
From Shipped Cost =Cost
To X 3 $ 3000
F1 1000 2 8000
W1 4000 7 17500
F1 2500 2 4000
W2 2000 3 45000
F2 1500 2 5000
W1 2500 Total transportation =$42,000
F2 cost
W3
F2
W4
F3
W1

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)
D E F G Supply
Source
A Destination 1 5 3 4 100
B 4 2 2 5 60
C 3 1 2 4 120
deman
70 50 100 60 280
d
Solution
The 1st allocation be made to the cell with the least-cost. Cells AD & CD
both have the lowest cost f $1. Cell AD is selected 1 st because more units
can be allocated to it (70) than to cell CE (50).

12
Cell CF is filled in 1 st 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

D E F G Supply
Source
A Destinatio 1 5 3 4 100
70
B 4 2 2 5 60
30 30
C 3 1 2 4 120
50 70
deman
70 50 100 60 280
d
Routes Units Unit Total
From Shipped Cost =Cost
To X 1 $ 70
A D 70 2 60
B F 30 5 150
B G 30 1 50
C E 50 2 140
C F 70 Total transportation =$470
cost

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

3. Develop an initial feasible solution using LCM

R S T Suppl
y
A 1 2 3 100
B 4 1 5 110
Deman 80 120 60
d

Solution
R S T Suppl
y
A 1 2 3 100
80 10 10
B 4 1 5 110
110
Dummy 0 0 0 50
13
50
Deman 80 120 60
d
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
Sourc
e S3 0 2 2 4 12
S4 2 7 2 4 19
deman 21 25 17 17
Total d trans
C.
VOGEL'S APPROXIMATION METHOD (VAM)

14
 or
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
Row difference or Row
penalty
or opportunity cost

2 0 - 15- -

2 2 2 2 5
 A B C D Suppl
y
F1 2 2 0 4
Factor 25
5 20
y
F2 5 9 8 3
25
15 5 5
F3 6 4 3 2
10
10
Deman 20 15 20 5 60
d

Column difference 3 2
3 1
or Column penalty
or opportunity cost 3 2 -
1

1 5 -
1

m= 3, n=4 ==> 3+4-1 =6 Occupied

5 cells9 (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 dollar.
Distribution Center

D1 D2 D3 D4
P1 2 3 11 7
P2 1 0 6 1
P3 5 8 15 9

16
 Plant

Find the initial basic feasible solution by:

a. North-west corners method
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 0 6 1 1 1 - -
P2
-
5 8 15 9 10 3 3 4
P3
4
Demand 7 5 3 2

Column
Penalty
7 5 3 2
1 3 5 6
3 5 4 2
3 - 4 2
5 - 15 9

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

The total transportation cost=$(1x2+5x3+1x1+6x5+3x15+1x9) x100 = $
10,200

Assignment
1. Determine an initial basic feasible solution to the following
transportation problem by VAM

17
 Destination
D1 D2 D3 D4 Suppl
y

Sourc
S1 21 16 15 3 11
e S2 17 18 14 13 13
S3 32 27 18 41 19
Deman 6 10 12 15
d

2. Determine an initial feasible solution to the following transportation

problem using
a. NWCM
b. LCM, &
c. VAM
Destination
D1 D2 D3 D4 Suppl
y
A 11 13 17 14 250
Sourc
e B 16 18 14 10 300
C 21 24 13 10 400
Dema 200 225 275 250
nd

5.3. OPTIMALITY TESTS

18
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 - Non degenerate solution.

Rules for drawing each closed loop:

19
1. Select an unused square (cell) to be evaluates.
2.Beginning 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:

20
 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:

: 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:

21
1. Use NWCM to find initial feasible solution and test the solution for
optimality.
Proje Proje Proje ss
ct ct ct
A B C
F1 4 2 8 10
0
F2 5 1 9 20
Farm

0
F3 7 6 3 20
0
d 50 150 300 50
d
0

Solution
Initial feasible solution

Project Project Project ss

A B C
F1 4 2 8 100
50 50
F2 5 1 9 200
100 100
Project Project Project ss
F3 A 7 B 6 C 3 200
F1 4 2 2008 100
dd 50
50 50
150 +
300 500
-
F2 5 1 9 200 m=3, n=3==> 3+3-1=5(Non-
100 + 100- degenerate solution)
F3 7 6 3 200 Total transportation cost =
200
Dd 50 150 300 500
$[50x4+50x2+100x1+100x9+200x3] = $1900

Evaluation path for the unoccupied cells

22
 Table: Test of optimality
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
200
dd 50 150 300 500
Table: Test of optimality

23
 Unoccupied cells Cell evaluators
(F1 ,B) +2 -8+9-1 =+2

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

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

(F3 ,A) +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
a. Obtain the basic feasible solution using VAM
b. Obtain the optimal solution
c. What is the optimal shipping cost?
Solution:
a. Initial feasible solution
To
R S T ss
Opportunity
1 2 3 100 cost
A
80 10 10
1 1 1 1
4 1 5 110
From

B
110 3 3 - -
Dumm 0 0 0 50
0 - - -
y
dd 80 120 60 260
Opportunity 1 1 3
3 1 2
cost 1 2
3
1 2 -
Note: Include the dummy cells to select the opportunity cost under VAM
problems.

b. Test of optimality.
Table: Test of optimality

24
 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
B Supplies 10 units to warehouse S
C Supplies 10 units to warehouse T
B Supplies 110 units to warehouse S

c. The total optimal shipping cost is = $240

Exercise:
Consider the following transportation problem

Store Store Store

Supply
1 2 3

A 12 20 15 50
warehouses

B 9 11 4 15
C 20 14 8 55
Deman 25 50 45 120
d

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)

It is another logarithm for finding the optimal solution to a transportation
problem.

25
The MODI method allows us to compute improvement indices quickly foe
each unused cell with out drawing all of the closed paths. Because of
this, it can often provide considerable time savings over the stepping-
stone method for solving transportation problems.
[

MODI provides a new means of finding the unused route with the largest
negative improvement index. Once the largest index is identified, we are
required to trace only one closed path. Just as with the stepping-stone
approach, this path helps to determine the maximum N o of units that can
be shipped via the best unused route.

Steps in the MODI Method

The steps to evaluate unoccupied calls are as follows:
1. For an initial basic feasible solution, calculate Ui and Vj ;for rows
and columns and set

C ij = Ui + Vj for all occupied calls

(i , j)
i.e: Cell cost= Raw Index +Column
2. For unoccupied cells, calculate opportunity cost by using
the relation:

Kij = Cij– (Ui + Vj); for all j and j.

Where Kij is the cell evaluator or
opportunity cost
3. Examine the sign of each Kij
For minimization case:
i. If Kij > 0, then current basic feasible solution is optimal.
ii. If Kij = 0, then the current basic feasible solution will remain
be unaffected but an alternative solution exists.
iii. If one or more Kij < 0, then an improved solution be
obtained entering unoccupied cell (i, j), in the basis. An
unoccupied cell having the largest negative value of Kij is
chosen for entering into the solution mix (new
transportation schedule)
4. Solve the problem as you did using the stepping-stone method.
i.e. construct a closed path (or loop) for the unoccupied cell with
largest negative opportunity cost. Start the close path with the
selected unoccupied cell and mark a plus sign (+) and in this cell,
trace a path along the rows (or columns) to an occupied cell,
mark the corner with minus sign (-) and continue down the
column (or row) to an occupied cell and mark the corner with

26
 plus sign (+) and minus sign (-) alternatively. Close the path
back to the selected unoccupied call.
Locate the smallest quantity allocated to a cell marked with a
minus sign. 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.

5. Obtain a new improved solution by allocating units to the

unoccupied call and calculate the new transportation cost.

6. Test the revised solution for optimality.

Note:
Any initial feasible solution will do: NWCM, VAM Solution, or any arbitrary
assignment.
The stepping- stone method is efficient for small sized transportation
problems. For larger problems, however, the MODI method is
recommended.

Example:
1. Obtain an optimal solution to the transportation problem by MODI
method given below:

Project Project Project

Supply
No 1 No 2 No 3

Farm 1 4 2 8 100
Farm 2 5 1 9 200
Farm 3 7 6 3 200
Deman 50 150 300 500
d
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.

27
Consider the initial feasible solution of the given example by NWCM as
shown below:

Initial solution, NWCM

Proje Projec Projec

ct t t Supply Ui
N 1
o
N 2
o
N 3
o

4 2 8 100
Farm 1 U1=0
50
5 1 9 200
Farm 2 U2=1
100 100
7 6 3 200
Farm 3 U3=-7
200
Deman 500
50 150 300
d

Vj V1=4 V2=2 V3=10

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==> V1=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

28
 Unoccupied cells Cell evaluators
Kij = 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:

Proje Projec Projec

ct t t 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
Deman 500
50 150 300
d

The distribution plan after reallocation of 50 units is:

Proje Projec Projec

ct t t Supply Ui
N 1
o
N 2
o
N 3o

4 2 8 100
Farm 1 U1=0
50 50
5 1 9 200
Farm 2 U2=1
- 100
+ 100+ -
7 6 3 200
Farm 3 U3=-5
200
Deman 500
50 150 300
d

Vj V1=4 V2=0 V3=8

Cij= Ui + Vj
==>C11= U1 +V1==>4=0+ V1==> V1=4 , U1=0 by convention
==>C13= U1 +V3==>8=0 +V3==> V3=8
==>C23= U2 +V3==>1= U2+ 0==> U2=1
==>C22= U2 +V2==>1= 1+V2==> V2= 0

29
 ==>C33= U3 +V3==>3= U3+8 ==> U3= -5
Table: Test of optimality

Unoccupied cells Cell evaluators

Kij = Cij– (Ui + Vj)
(1,2) C12– (U1 +V2)=2-(0+0)= 2
(2,1) C21 – (U2 +V1)=5-(1+4)=0
(3,1) C31– (U3 +V1)=7-(-5+4)=8
(3,2) C32– (U3 +V2)=6-(-5+0)=+11

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

solution.
Thus, the total cost for the distribution plan = $1800

30
Assignment
1. Obtain an optimal solution to the transportation problem by MODI
method given below.

D1 D2 D3 Suppl
D3
y
19 30 50 10 7
Farm 1

70 30 40 60 9
Farm 2

40 8 70 20 18
Farm 3

Deman 34
5 8 7 14
d

2.A company has four ware houses a, b, c and d. It is required to deliver a

product from these warehouses to three customers A, B and C. The
warehouses have the following amounts in stock:

Ware a b c d
house:
No of units: 15 16 12 13

And the customer’s requirements are:

Customer: A B C
No of units: 18 20 18

The table below shows the costs of transporting one unit from
warehouse to customer.

A b c d

8 9 6 3
A

6 11 5 10 31
B

3 8 7 9
C
 Find the optimal transportation routes.

3.A manufacturer has distribution centers at X, Y and Z. These centers

have availability 40, 20, and 40 units of his product. His retail outlets at
A, B, C, D and E require 25,10,20,30 and 15 units respectively. The
transportation cost (in $) per unit between each centre outlet is given
below:

Distributio
Retail outlets
n center

A B C D
E
X
55 30 40 50 40

35 30 100 45 60
Y

40 60 95 35 30
Z

Determine the optimal distribution to minimize the cost of

transportation.

4.A company has factories A, B and C which warehouses t D, E, F and G.

Monthly factory capacities are 160,150 and 190 units respectively.
Monthly warehouses requirements are 80, 90,110 & 160 units
respectively. Unit shipping costs (in $) are as follows:
To
D E F G

A 42 48 38 37

40 49 52 51
B

39 38 40 43
C

32
 Determine the optima distribution for this company to minimize
shipping costs.

5.4. SPECIAL CASES

5.4.1. Degeneracy
A condition that occurs when the N o of occupied cells in any solutions less
than the No 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 to
wards 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 some what
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 No of completed cells and m+n-1.Howerver; you will only be exposed
to the most common case in which one more completed cell is needed.

33
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 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 Suppl
y
1 3 3
50
2 4 6 30
Deman
50 30 80
d Solution:
Using NWCM and MODI, the initial solution is:

Suppl Ui
1 2
y
3 3 U 1=
1 50
50  0
4 6 U 2=
2 30
30 3
Deman
50 30 80
d

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)
(2,1) C21 – (U2 +V1)=4-(3+3) =-2

The optimal solution is:

34
 Suppl Ui
1 2
y Cij= Ui + Vj
3 3
U 1= ==>C11=U1+V1==>3=0+V1==>V1=3,
1 50 30 50
0 U1=0 by convention
4 6 U 2= ==>C21= U2+V1==>4= U2+3==>
2 30
30 1
U2=3
Deman
d
50 30 80 ==>C12= U1 +V2==>3= 0+ V2==>
Vj V1=3 V2=3
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

5.4.1. Alternative Optimal solutions
The esist6ane of alternative optimal solution can be determined by an
inspection of the opportunity costs, Kij 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
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

35
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 tone (in hundred dollars) have been
determined:

Warehous L p Q
e 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.

5.4.3. Prohibited Transportation Routes.

The situation may arise such as road hazards (snow, foods, etc), traffic
regulation etc, when it is not possible to transport goods from certain
sources to certain destinations. In this case, the appropriate cell may either
be completely crossed out or a very large per unit transportation cost assign
to it (M)

5.5. ASSIGNMENT PROBLEMS

The Assignment Problem(AP) refers to the class of LPPs that involves
determining the most efficient assignment of people to projects,
salespeople to territories, contracts to bidders ,jobs to machines,
and so on. The objective is to assign a number of resources to an equal

36
number of activities so as to minimize total costs or total time or maximize
total profit of allocation.

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
Zone table
Z1 Z2 Z3 Zone
Servic Z1 Z2 Z3 Suppl
e Servi y
S1
Team 20 15 31 ce
====> S1
Team 20 15 31 1
S2 17 16 33
S2 17 16 33 1
S3 18 19 27
S3 18 19 27 1
Dema
1 1 1
nd

37
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
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.

5.5.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

5.5.1.1. 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.

38
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.
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.Test for an optimal assignment
i.e. Test the table resulting from step 2 to see whether an optimal
assignment can be made. The procedure is:
a. Draw the minimum number of Horizontal and /or Vertical lines
necessary to cover all zeros costs.
Draw the lines by trial and error but always try to cover two or
more zeros with one line.
b. Count the number of the lines
If the number of lines equals either the number of rows or
columns in the table, an optimal assignment can be made. If
the number of lines is less than the number of rows or
columns, an improvement is possible (we proceed to step 4).

39
Step 4.Improve the present opportunity cost table (matrix)
This is done by the following operations:
a. Find the smallest entry in the uncovered cells (cells with no lines
through them) and subtract it from all entries in the uncovered cells.
b. Add the same smallest entry to those cells in which the lines intersect
(cells with two lines them)
c. Cells with one line through them are transferred (i.e. unchanged to the
improved table).

In those problems where the first improvement does not yield an

optimal solution, we keep on improving the solution by repeating step 4
until an optimal solution is achieved.

Step 5: Make an optimal assignment

An optimal assignment should be made to cells with a zero entery,
maintaining the one-to-one requirement

If more than one optimal solution exists, a trial-and –error approach can be
used to find all possible combination assignments in the zero cells.

Note that multiple optimal solutions are possible.

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
minute)
A B
1 120 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:

40
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 there respective
row. The reduced time matrix is:
Table: After row reduction

A B
-80 1 40 20 0
-80 2 0 10 30
-110 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
1 40 10 0
2 0 0 30
3 0 20 10
Step 3: Test for an optimal assignment
a. Draw the minimum number of horizontal and /or vertical lines necessary
to cover all zero times (costs).
Table: Test of optimal assignment

A B
1 40 10 0
2 0 0 30
3 0 20 10

b. Count the number of lines

If the number of lines is equal to the number of rows/columns, the optimal
solution is obtained. Thus proceed directly to step 5.

Step 5.Make an optimal assignment

An optimal assignment should be made to cells with a zero entery,
maintaining the one-to-one requirement.

41
 Table: optimal assignment

A B
1 40 10
2 3 30
3 1 0
0 0
10
0
Note: 0

In optimal assignment, start with row/column having one zero and

cancel the alternative zeros(x)

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

2. 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
B 3 9 18 13 6
Jobs

C 10 7 2 2 2

D 7 11 9 7 12

E
7 9 10 4 12

How should the jobs be allocated, one per employees, so as to minimize

the total man-hours?

Solution:
Table: After row reduction

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

-7 D 0 5 2 0 5

E
3 5 6 0 8
-4

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

Table: After improvement

I II III IV V
A 7 0 8 12 11
B 0 4 13 10 1
C 10 5 0 2 0

D 0 2 0 0 2

E
3 3 4 0 6

Since the number of lines equals to the number of rows/columns, the

solution is optimal.
Table: Optimal assignments

I II III IV V

A 7 8 12 11

B 4
0 13 10 1

C 10 5 2

D 0
0 2 2

43
E 3 3 4 6

0
0
The pattern of assignments among jobs and employees with respective
time (in hours) is given below:

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
-15 1 5 0 16 1 5 0 7
-16 2 1 0 17 2 1 0 8
-18 3 0 1 9 3 0 1 0

Table: After improvement

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

44
 Table: Optimal Assignment

A B C

1 4 6
0

2 7
0 0

3 2

0 0

Job Machine Cost(in $)

1 B 15000
2 A 17000
3 C 27000
Total optimal assignment=$59000

5.6. SPECIAL CASES IN THE ASSIGNMENT

PROBLEMS
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.

45
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
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 (Estimated time in
minute) minute)
1 2 1
A 4 0 0 A 4 02 0
Job B 0 3 2 Job B 0 0 3 2
C 1 0 0 C 1 0 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
$) D
A B
70 80 75 6
1
4
55 52 58 5
Operator

2
4
3 58 56 64 6
62 60 67 7
8
4
0

46
Required:
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 D
A B D 1 4 16 5 0
1 6 16 11 0
Table: 2 1 0 0 2
2 3 0 6 2
3 0 0 2 1
3 2 0 8 1 A B D 1
2
1
2 1 4 16 4 5 0 0 1
4 2 0 7 0
0 2 1 2
0 Optimal
3 0 0
2 1
Assignments
0 0 1
2
4 1
0 0 0

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

47
Alternative optimal assignment

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
A 42 35 28 21
Salesmen

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

48
Thus, after improvement of the table, the optimal assignment is:
I II III IV
A 0 2 4 7

B 0 0 0 1

C 0 0 0 1

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

49
 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 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?
Offic
e 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(Gambe
la)
P1 800 1,100 1,200 1,000

Person P2 500 1,600 1,300 800

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

50
 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. 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).

51
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
Table: Optimal assignment

A B C D E

M1 0 2 6 1 2

3 0 M 1 0
M2

M3 M 4 7 4
0

M4 7 1 5 0 1

M5
0 0 0 0 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

52
Exercise:
1. A car rental company has one car at each of five depots a, b, c, d and
e. A customer in each of the five towns A, B, C, D and E requires a car.
The distance in (in kilometers) between the depots and towns where the
customers are, is given in the following distance matrix:
Depots

a b c d e
A 160 130 175 190 200
B 135 120 130 160 175
Towns

C 140 110 155 170 185

D 50 50 90 80 110
E 55 35 70 80 105

How should the cars be assigned to the customers so as to minimize

the distance traveled?
Answer:
A e
B c
C b
D d

Minimum distance = 570 km

2. An airline company has drawn up a new flight schedule involving five

flights. To assist in allocating five pilots to the flights, it has asked them
to state their preference scores by giving each flight a number out of
10 .The higher the number , the greater is the preference. Certain of
these flights are unsuited to some pilots owing to domestic reasons.
These have been marked with a X
Flight number
a b c d e
A 8 2 X 5 4
B 10 9 2 8 4
Pilot

C 5 4 9 6 X
D 3 6 2 8 7
E 5 6 10 4 3

53
What should be the allocation of the pilots to flights in order to meet as
many performances as possible?
(Hint: The problem is to maximize the total preference score)

Pilot Flight No Preference Score

A 1 8
B 2 9
C 4 6
D 5 7
E 3 10
Total 40

54