Chapter Three

Transportation and Assignment Problems

3.1. Introduction
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.
Transportation Problems
Transportation problem deals with the distribution of goods from several points of supplies
(sources) to a number of points of demands (destinations). It is usually applied to distribution
type problems in which supplies of goods that are held at various locations are to be distributed
to other receiving locations.

Objective of the model: is to identify a distribution plan that would minimize the cost of
transporting the goods from the supply areas to the demand areas taking into account supply
capacities and demand requirements as well as transportation costs.

Application areas: we can use transportation model for various types of problems. For example:

• Shipments from factories to warehouses

• Shipments between departments within a company
• To compare location alternative
• Production scheduling etc.
Necessary conditions for the model:
A transportation problem typically involves a set of sending locations which are referred to as
origins(supply areas ) and a set of receiving locations which are referred to as destinations
( demand areas). In order to develop a model of a transportation problem it is necessary to have
the following information:
• Supply quantity (capacity) of each origin
• Demand quantity of each destination
• Unit transportation cost for each origin- destination route
Assumptions:

• All goods be homogeneous

• Transportation costs are a direct linear function of the quantity shipped over any route
• The total quantity available for shipment is equal to the total quantity demanded

1
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.
3.2. Steps to solve transportation problems
The solution algorithm to a transportation problem is summarized into the following steps:
Step 1: Formulate the transportation table: set up a transportation table with M- rows
representing the number of supply areas and N- columns representing the number of demand
areas.
The formulation of the problem is similar to the linear programming. Here the objective function
is to minimize the total transportation cost and the constraints are the supply and demand
available at each source and destination respectively. The origins are listed down the left side of
the table, and the respective supply quantities are listed down the right side of the table.
Step 2: Obtain an initial basic feasible solution: For this there are 3 methods to find the initial
feasible solution.
• North-West Corner Method (NWCM)
• Least Cost Method (LCM)
• Vogel’s Approximation Method (VAM)
The initial solution obtained by any of the above three methods must satisfy the following
condition:

2
The solution must be feasible: i.e. it must satisfy all the supply and demand constraints
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). If the number of occupied cells < m+n-1==> degenerate solution you
will see it in special issue of a transportation problem.
Step 3: Test the initial solution for optimality: If the current solution is optimal, then stop.
Otherwise, determine the new improved solution.
For this there two method to find the optimal solution
• Stepping stone methods
•Modified distribution method( MODI)
Step 4: Repeat step 3 until an optimal solution is reached
Now based on the above logic lets solve the problem.
Transportation Table
Summarize all the given information in the tabular form as follows.
Destinations (dd) =j

Origin W1 W2 W3 W4 Factory
(Supply) Capacity =i
F1 3 2 7 6 5000

F2 7 5 2 3 6000

F3 2 5 4 5 2500

Requirements of the 6000 4000 2000 1500 13500

Warehouses
( Units of demand)
Note that we can solve the problem using LPPM, because transportation problem is a special
type of LPPM. So we can change the above problem into LPPM as follows:

3
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:
Min Z = 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
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.
To conceptualize the problem easily let’s represent of the problem using a Net work flow
diagram.
This LPP has 12 shipping routes. The objective is to identify the minimum cost route (Least cost
route). From these routes which rout results the minimum total transportation cost. Using Try
and error is very tiresome and inefficient. But by using the transportation problem models you
can identify the routes easily.
3.3. Methods for Finding Initial 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.

4
 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.
2. Subtract from the row supply & from the column demand the amount allocated
3. If the column demand is 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:

T Store 1 Store 2 Store 3 Store 4 Supply

F
Plant 1 19 30 50 10 7

Plant 2 70 30 40 60 9
Plant 3 40 8 70 20 18

Demand 5 8 7 14 34

Consider the following transportation problem:

Required:

a. Develop an initial feasible solution using the NWCM

b. Compute the total cost for this solution.

5
Solution:
a. Table: Initial feasible solution
To Store 1 Store 2 Store 3 Store 4 Supply

From
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
From To Shipped 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.
Example 2
1. Determine an initial basic feasible solution to the following transportation problem using
NWCM and 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 34

6
Answer: X11=5, X21=2, X22=6, X32=3, X33=4, X43=4, and Total cost =$10
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:
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)

LCM is the method that uses a minimum cost in the allocation.

7
It begins a solution by sequentially assigning to the cells with the minimum cost as many units
as possible. The first allocation be made to the cell with the lowest cost.
The Least- Cost Method yields not only an initial feasible solution but also one that is close to
optimal in small problems.

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
W1 W2 W3 W4 Factory 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:
a. Initial feasible solution using NWCM
W1 W2 W3 W4 Factory Capacity
F1 3 2 7 6 5000
5000
F2 7 5 2 3 6000
1000 4000 1000
F3 2 5 4 5 2500
1000 1500
Demand 6000 4000 2000 1500 13,500
m= 3, n =4 ==> 3+4 -1 =6 occupied cells (Feasible)

From To Units Shipped Unit Cost Total Cost

F1 W1 5000 3 $ 15000
F2 W1 1000 7 7000
F2 W2 4000 5 20000

8
F2 W3 1000 2 2000
F3 W3 1000 4 4000
F3 W4 1500 5 7500
Total transportation cost =$55,500

b. Initial feasible solution using LCM

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

F3 2 5 4 5 2500
2500
Demand 6000 4000 2000 1500 13500

Routes Units Unit Total

From To Shipped X Cost =Cost
F1 W1 1000 3 $ 3000
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)

D E F G Supply

9
A 1 5 3 4 100
B 4 2 2 5 60
C 3 1 2 4 120
DD 70 50 100 60 280
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 1st because more units can be allocated to it (70) than to cell CE
(50).
The initial solution by the least -cost method
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

demand 70 50 100 60 280

Routes Units Unit Total
From To Shipped X Cost =Cost
A D 70 1 $ 70
B F 30 2 60
B G 30 5 150
C E 50 1 50
C F 70 2 140
Total transportation cost =$470

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
B 4 1 5 110
Demand 80 120 60
Solution:

R S T Supply

10
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
C. Vogel's Approximation Method (VAM) 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 it 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:

11
• Determine an initial basic feasible solution to the following transportation problem using
VAM.
Warehouse
A B C D Supply
F1 2 2 0 4 25
5 20
F2 5 9 8 3 25
15 5 5
F3 6 4 3 2 10
10
Demand 20 15 20 5 60
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 dollar.
Distribution Center
D1 D2 D3 D4
P1 2 3 11 7
P2 1 0 6 1
P3 5 8 15 9
Find the initial basic feasible solution by:

12
 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
D1 D2 D3 D4 Supply Row Penalty
P1 2 3 11 7 6 1 1 5 -
1 5
P2 1 0 6 1 1 1 - - -
1
P3 5 8 15 9 10 3 3 4 4
6 3 1
Demand 7 5 3 2 17

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
3.4. Test for Optimality
Once an initial solution is available, the next step is to check it for 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.

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

• Stepping stone Method

• Modified Distribution method (MODI Method)
1. Stepping-stone method
Stepping-stone method: involves tracing a series of closed paths in the transportation table,
using one such path for each empty cell. The path represents a shift of a given quantity for an
empty cell. We will use the stepping-stone method to evaluate the economics of shipping via
transportation routes that are not currently part of the transportation solution. If we can find cost
reducing routes, the current solution will be revised by making shipments via these new routes.
By continuing to evaluate the costs associated with routes that are not in the current solution, we
will know that we have reached the optimal solution when all routes not in the current solution
would increase costs if they were brought in to the solution.
Rules for Tracing Stepping-Stone Paths
• All unoccupied cells must be evaluated. Evaluate cells one at a time.
• Except for the cell being evaluated, only add or subtract in occupied cells. (It is permissible to
skip over occupied cells to find an occupied cell from which the path can continue).
• A path will consist of only horizontal and vertical moves, starting and ending with empty cell
that is being evaluated.
• Begin with a plus (+) sign in the cell being evaluated (unused cell) and alternate “+” and “-”
signs. 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.
• 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.
• An even no of at least four cells must participate in a loop and the occupied cells can be visited
once and only once.

14
• Repeat steps 1 to 4 until an improvement index has been calculated for all unused (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.
To see how the stepping-stone method works, let us return to the initial feasible solution for the
generators problem found by minimum – cost method.
Note:
In a non-degenerate problem, there is only one possible way of drawing the loop for each empty
cell.
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:
• 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

• Design an improved solution, by shifting units form cell to cell

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: Use Least Cost Method to find initial feasible solution and test the solution for optimality.

To

15
From Boston Chicago St.Louis Lexington Supply
Cleveland 3 2 7 6 5000
1000 4000
Bedford 7 2 3 6000
5
2500 2000 1500
York 2 5 5 2500
4
2500
Demand 6000 4000 2000 1500 13,500
Finding the stepping-stone path for each possible new cell enables us to identify the cost effect
for each new cell or route. Evaluating this cost effect for all possible new cells leads to the
following tableau. The per-unit cost effect for each possible new cell in circled in the cell.

To
From Boston Chicago St.Louis Lexington Supply
Cleveland 3 2 7 6 5000
1000 4000
Bedford 7 5 2 3 6000
2500 2000 1500
York 2 5 4 5 2500
2500
Demand 6000 4000 2000 1500 13,500
The stepping-stone path also reveals which cells must have quantity changes, both the magnitude
and the direction of the changes. The “+” signs in the path indicate units to be added and the “-”
signs indicate units to be subtracted. The limit on subtraction is the smallest quantity in a
negative position along the cell path. The following tableau shows the new solution.

To
From Boston Chicago St.Louis Lexington Supply
Cleveland 3 2 7 6 5000
3500 1500
Bedford 7 5 2 3 6000
2500 2000 1500
York 2 5 4 5 2500

16
 2500
Demand 6000 4000 2000 1500 13,500

2. Modified Distribution method (MODI Method)

The MODI method provides a simple approach for determining the best unoccupied cell to bring
in to solution. It 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 number
of units that can be shipped via the best unused route.

This method requires that we define an index “ri” for each row of the tableau of initial feasible
solution of transportation problem and an index “kj” for each column of the same tableau. The
values of these indexes are found by requiring that the cost coefficient for each occupied cell
equal ri (row index) + kj (column index) = Cell cost (Cij ). Requiring that ri + kj = Cij for all
occupied cells in the initial tableau of generators company problem leads to a system of six
equations and seven variables.

Steps in the MODI Method

The steps to evaluate unoccupied calls are as follows:
• For an initial basic feasible solution, calculate ri and kj ;for rows and columns and set.
• For unoccupied cells, calculate opportunity cost by using the relation:
• Examine the sign of each CEij :
• If CEij > 0, then current basic feasible solution is optimal.
• If CEij = 0, then the current basic feasible solution will remain be unaffected but an
alternative solution exists.
•If one or more CEij < 0, then an improved solution be obtained entering unoccupied cell (i, j),
in the basis. An unoccupied cell having the largest negative value of CEij is chosen for entering
into the solution mix (new transportation schedule)

• 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

17
sign (-) and continue down the column (or row) to an occupied cell and mark the corner with
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.
• 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 (r1=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
Project 1 Project Project Supply ri
2 3
Farm 1 4 2 8 100 r1= 0
50 50
Farm 2 5 1 9 200 r2 = 1
100 100
Farm 3 7 6 3 200 r3 = 7
200

Deman 150 300 500

d 50

kj k1=4 k2=2 k3=10

18
To determine Cij, use the occupied cells.
For instance, C11=4, C12=2, C22=1, C23=9, and C33=3
Cij= ri + kj
==>C11= r1 +k1==>4=0+ k1==> k1=4 , r1=0 by convention
==>C12= r1 +k2==>2=0 +k2==> k1=2
==>C22= r2 +k2==>1= r2+ 0==> r2=-1
==>C23= r2 +k3==>9= -1+k3==> k3=10
==>C33= r3 +k3==>3= r3+10 ==> r3= -7
Note:
Cij≠ ri + kj (For unoccupied cells)
For instance, from the above information, C32 ≠ r3 + k2==>6≠-7+2
Test of optimality

Cell evaluation = cell cost – Row index – Column index

Cij = Cij – ri - kj
Unoccupied cells from our initial feasible solution s are:
Unoccupied cells Cell evaluators
CEij = Cij– ri - kj
(1,3) CE13 – r1 -k3 = 8-0-10= -2
(2,1) CE21 – r2 -1 = 5+1-4=+2
(3,1) CE31– r3 -k1 = 7+7-4=10
(3,2) CE32– r3 -r2 = 6+7-2=+11
In this case, we found that 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:
Project 1 Project 2 Project 3 Supply
Farm 1 4 2 8 100
50 50
Farm 2 5 1 9 200
100 100
Farm 3 7 6 3 200
200

19
Demand 50 150 300 500

The distribution plan after reallocation of 50 units is:

Project 1 Project 2 Project 3 Supply ri
Farm 1 4 2 8 100 r1=0
50 50
Farm 2 5 1 9 200 r2=1
+ 100 100 -
Farm 3 7 6 3 200 r3=-5
200

Demand 150 300 500

50

kj k1 = 4 k2 = 0 k3 = 8

Cij= ri + kj

==>C11= r1 +k1==>4=0+ k1==> k1=4 , U1=0 by convention

==>C13= r1 +k3==>8=0 +k3==> k3=8

==>C23= r2 +k3==>1= r2+ 0==> r2=1

==>C22= r2 +k2==>1= 1+k2==> k2= 0

==>C33= r3 +k3==>3= r3+8 ==> r3= -5

Table: Test of optimality

Unoccupied cells Cell evaluators

CEij = Cij– ri - kj
(1,2) CE12– r1 -k2=2-0-0= 2
(2,1) CE21 – r2 -k1=5-1-4=0
(3,1) CE31– r3 -k1=7+5-4=8
(3,2) CE32– r3 -k2=6+5-0=+11
Because none of the cell evaluators is negative, this is an optimal solution.

20
Thus, the total cost for the distribution plan =$1800.
3.4. Special Cases in Transportation Problem
3.4.1. Unbalanced supply and demand
To solve a problem with an equal supply and demand total, first,
convert the unbalanced transportation problem into a balanced transportation
problem 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
* But if excess demand (Supply < demand) exists add a dummy source (add a dummy row)
Note: the cost of “shipments” to the dummy is usually set at zero ==> No real cost
Consider the following transportation problem.
Destination
R S T SS
A 1 2 3 100
Origin B 4 1 5 110
210
DD 80 120 60
260
a. Obtain the basic feasible solution using VAM
b. Obtain the optimal solution
c. What is the optimal shipping cost?
Solution:
• Initial feasible solution
To
From R S T ss
1 2 3 100
A
80 10 10
4 1 5 110
B 110

Dummy 0 0 0 50
DD 80 120 60 260

21
 • Test of optimality.
Table: Test of optimality
Unoccupied cells Cell evaluators
(B,R) +4-1+2-1= +4
(B,T) +5-1+2-3= +3
(D,R) +0-1+3-0= +2
(D,S) +0-2+3-0= +1

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
3.4.2. 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
The degeneracy in the transportation problems may occur at two stages:
• When obtaining an initial solution
• 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, it should be allocated to a cell that has the smallest
transportation cost. 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.

22
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
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 Supply

1 3 3 50
2 4 6 30
Demand 50 30 80

Solution:
Using NWCM and MODI, the initial solution is:
1 2 Supply ri

1 3 3 50 r1 = 0
50

2 4 6 30 r2 = 3
30
Demand 50 30 80
kj k1=3 k2=3
Cij= ri + kj
==>C11= r1 +k1==>3=0+ k1==> k1 = 3, r1=0 by convention
==>C12= r1 +k2==>3=0 + k2==> k2 =3
==>C22= r2 +k2==>6= r2+3==> r2= 3
==>C33= r3 +k3==>3= r3+8 ==> r3= -5
Note: m=2 and n=2==>2+2-1=3==>Occupied cells=2< 3 (Degeneracy)
Table: Test of optimality

23
Unoccupied cell Cell evaluator
CEij = Cij– ri - kj
(2,1) CE21 – r2 -k1=4-3-3 =-2
The optimal solution is:
1 2 Supply ri

1 3 3 50 r1=0
50 30

2 4 6 30 r2=1
30
Demand 50 30 80
kj k1=3 k2=3
Cij= ri + kj
==>C11=r1+k1==>3=0+k1==>k1=3, r1=0 by convention
==>C21= r2+k1==>4= r2+3==> r2=3
==>C12= r1 +k2==>3= 0+ k2==> k2= 3
Table: Test of optimality
Unoccupied cells Cell evaluators
CEij = Cij– (ri + kj)
(2,2) CE22– r2 -k2=6-1-3= +2
The total cost= $(20x3+30x3+30x40=$270
3.4.3. Alternate optimal solution
The existence 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.
3.4.4. Prohibited transportation routes
The situation may arise such as road hazards (snow, floods, etc), traffic regulation, equipment
break down, labor problem etc., when it is not possible to transport goods from certain sources to
certain destinations. To solve such kinds of problem, assign a cost 10 times the largest cost in the
table and then it will be uneconomical to transport to that cell. Then do as usual. (Initial feasible
solution by NWCM/LCM/VAM and optimal solution by stepping stone /MODI)
Example:

24
 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
Note that due to uncontrollable reason it is impossible to transport from S 3 to C. So to solve the
problem fist adjust it as follows:
A B C D Supply
S1 1 5 3 3 34
S2 3 3 1 2 15
S3 0 2 70 4 12
S4 2 7 2 4 19
Demand 21 25 17 17
The cell cost of S3C i.e. 2 will be replaced by 70 i.e. 7 * 10, because 7 is the largest cost in the
table.
Then do as usual.
3.5. Maximization Transportation problems
If you are faced with transportation type problem concerned with profit (revenue). First change
the problem to a minimization type. The steps are:
• Select the largest unit profit from the total cells
• Subtract each cell value from the largest
• Do the same procedure as usual
Example:

T A B C SS
F
1 6 8 10 150
2 7 11 11 175
3 4 5 12 275
DD 200 100 300 600
To change the above maximization problem to a minimization type first identify the largest unit
profit from the cell (12) then subtract all the cells values from this largest selected value as
indicated below( 12-6=6, for cell1A, 12- 8=4 etc. ). These yields opportunity cost figures.

25
Then do as usual. For example if you use LCM for initial solution and MODI for optimality test
the solution will be:

T A B C SS
F
1 6 4 2 150
150 r1 = 0
2 5 1 1 175
50 100 25 r2 = -1
3 8 7 0 275
275 R3 = -2
DD 200 100 300 600
k1= 6 k2= 2 k3= 2

Unoccupied cells Cell evaluators

(1,B) 4-0-2=2
(1,C) 2-0-2=0
(3,A) 8+2-6=4
(3,B) 7+2-2=7
All the improvement index are o and +ve, we reached the optimal solution. The optimal solution
is:
Routes Units Unit Total
From To Shipped X Cost =Cost
1 150 6 $ 900
A 50 7 350
2 100 11 1100
A 25 11 275
2 275 12 3300
B
2 C
3
C
Total profit gained =5925

3.6. Assignment Problems

The Assignment Problem (AP) refers to the class of Linear Programming Problems that
involves determining the most efficient assignment of people to projects, salespeople to

26
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.
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:1relationship.
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 jobs 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)

Z1 Z2 Z3
Seri SS

27
S1 20 15 31 1
S2 17 16 33 1
S3 18 19 27 1
DD 1 1 1
Table: The assignment table

Z Z1 Z2 Z3
Se
S1 20 15 31
S2 17 16 33
S3 18 19 27
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 contraints:
x11 + x21 + x31 = 1 Z1 contraint
x12 + x22 + x32 = 1 Z2 contraint
x13 + x23 +x33 = 1 Z3 contraint
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.

Methods of solving assignment problems

An assignment problem can be solved by the following methods:
1. Enumeration method

28
2. Simplex method
3. Transportation method
4. Hungarian method
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.
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
The transformation of the cost matrix that you have learned in TP is termed as a total-
opportunity cost matrix in assignment problem.
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
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 each column
now have at least one zero value.
Step 3: Test for an optimal assignment

29
Test the table resulting from step 2 to see whether an optimal assignment can be made. The
procedure is:
• 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.
• Count the number of 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).
Step 4: Improve the present opportunity cost table (matrix)
This is done by the following operations:
• Find the smallest entry in the uncovered cells (cells with no lines through them) and
subtract it from all entries in the uncovered cells.
• Add the same smallest entry to those cells in which the lines intersect (cells with two lines
them).
• 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 entry, 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:
• 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
(Estimated time in minute)
A B C
Programmers 1 120 100 80

30
 2 80 90 110
3 110 140 120
Assign the programmers to the programs in such a way that the total computer time is the
minimum.
Solution:
Steps 1 and 2:
• Perform row reduction
A B C
Row minimum

-80 1 40 20 0
-80 2 0 10 30
-110 3 0 30 10
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

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: Test for an optimal assignment

31
 a. Draw the minimum number of horizontal and /or vertical lines necessary to cover all zero
times (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 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).

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 entry, 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.
Table: Test of optimal assignment

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

Count the number of lines

32
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 entry, maintaining the one-to-one
requirement.
Table: optimal assignment

A B C
1 40 10
2 30
3 20 10
Note:
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
Cross Check Formula
Optimal solution = summation of row minimum + summation of columin minimum + revised
reduction
i.e., considering the above problem:
280=270 +10+0
280=280
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.

33
 Employees
I II III IV V
A 10 5 13 15 16
B 3 9 18 13 6
C 10 7 2 2 2
Jobs
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

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
-4 E 3 5 6 0 8
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

34
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 13 10 1

C
10 5
2

D 2 2

E 3 3 4 6

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:

35
Job Machine (Cost in ’000s))
A B C
1 20 15 31
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
-15 1 5 0 16
-16 2 1 0 17
-18 3 0 1 9
A B C
1 5 0 7
2 1 0 8
3 0 1 0
Table: After improvement

A B C
1 4 0 6
2 0 0 7
3 0 2 0
Since the number of lines and the number of rows/ columns are equal the solution is optimal

Table: Optimal Assignment

36
 A B C

1 4 6

2 7

3 2

Job Machine Cost(in $)

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

3.7. Special case in Assignment Problems

I. 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.
Example1:
1. Given this final assignment table, identify two optimal solutions.
Job Machine (Estimated time in minute)
1 2 3
A 4 0 0
B 0 3 2
C 1 0 0
Solution

37
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:
Job Machine (Estimated time in minute)
1 2 3
A 4

B 3 2

C 1

Job Machine (Estimated time in minute)

1 2 3
A 4

B 3 2

C 1

Example: 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
Operator 1 70 80 75 64
2 55 52 58 54
3 58 56 64 68

4 62 60 67 70
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.

38
Solution:

Table: After row reduction

A B C D
1 6 16 11 0
2 3 0 6 2
3 2 0 8 12

4 2 0 7 10
Table: After column reduction
A B C D
1 4 16 5 0
2 1 0 0 2
3 0 0 2 12

4 0 0 1 10

Operator Machine Cost(in $)

4 A 62
3 B 56
2 C 58
1 D 64
Total cost =$240
c. Yes!
Alternative optimal assignment
Operator Machine Cost(in $)
1 D 64
2 C 58
3 A 58
4 B 60
Total cost=$240
II. 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:

• Find the largest profit coefficient in the entire.

• Subtract each entry in the original table from the largest profit coefficient.

39
The transformed assignment problem so obtained can be solved by using the Hungarian method.
Example:
• 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.
I II III IV
A 42 35 28 21
B 30 25 20 15
C 30 25 20 15
D 24 20 16 12
Solution:
I II III IV
A 0 3 6 9
B 0 1 2 3
C 0 1 2 3
D 0 0 0 0
Convert maximization problem into minimization problem by subtracting all elements from the
highest element (i.e. 42)
Thus, the equivalent cost table is:
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:

40
 Assignment set II
Assignment set I

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
III. Unbalanced Assignment Problem (unequal number of
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 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)

41
Person
P1 800 1,100 1,200 1,000
P2 500 1,600 1,300 800
P3 500 1,000 2,300 1,500
Dummy 0 0 0 0
Table: after row reduction

C1 C2 C3 C4
P1 0 300 400 200
P2 0 1,100 800 300
P3 0 500 1800 1000
Dummy 0 0 0 0
Table: Optimal Assignment
C1 C2 C3 C4
P1 100 0 100 0
P2 0 700 400 0
P3 0 100 1400 700
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
IV. 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.

42
Example:
• 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 cannot be placed at C and M3 cannot be placed at A. the
cost of placing of machine at place i (in $) is shown below.
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
The total minimum cost ($) and optimal assignments made are as follows:

Machine Location Costs ($)

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

43
44