Chapter three

Transportation and Assignment Models

Transportation Models
A transportation problem typically involves a set of sending locations, which are referred to as origins,
and a set of receiving locations, which are referred to as destinations. In order to develop a model of a
transportation problem, it is necessary to have the following information:
a. Supply quantity (capacity) of each origin.
b. Demand quantity of each destination.
c. Unit transportation cost for each origin-destination route.
Assumptions
The transportation algorithm requires the assumption that:
 All goods be homogeneous, so that any origin is capable of supplying any destination, and
 Transportation costs are a direct linear function of the quantity shipped over any route.
 Though it will be modified later in our discussion, we shall add one additional requirement that
the total quantity available is equal to the total demand.
Example
Let’s consider an example. Harley’s Sand and Gravel Pit has contracted to provide topsoil for three
residential housing developments. Topsoil can be supplied from three different “farms” as follows:
Farm Weekly capacity (cubic yards)
A 100
B 200
C 200
Demand for the topsoil generated by the construction projects is:
Project Weekly demand(cubic yards)
1 50
2 150
3 300
The manager of the sand and gravel pit has estimated the cost per cubic yard to ship over each of the
possible routes:
Cost per cubic yard to
From Project #1 Project #2 Project #3
Farm A Birr4 Birr 2 Birr 8
Farm B 5 1 9
Farm C 7 6 3

1
This constitutes the information needed to solve the problem.
The next step is to arrange the information into a transportation table. This is shown in the following
table.
Transportation table for Harley’s sand and gravel
To:
From: Projec Project Projec Supply
4 2 8
Farm A 100
5 1 9
Farm B 200
7 6 3
Farm C 200
Demand 50 150 300

FINDING AND INITIAL FEASIBLE SOLUTION

The starting point of the transportation method is a feasible solution. For an assignment to be feasible,
two conditions must be fulfilled:
 A feasible solution is one in which assignments are made in such a way that all supply and
demand requirements are satisfied.
 The number of nonzero (occupied) cells should equal one less than the sum of the number
of rows and the number of columns in a transportation table. In the case of a table with 3
rows and 3 columns, the number of occupied cells should be 3 + 3 -1 = 5 in order to be able
to use the transportation algorithm. Sometimes, fewer occupied or completed cells appear
in a solution. When that happens, the solution is referred to as a degenerated solution;
such a solution requires modification in order to be able to determine if it is optimal. This
topic will be covered later on.
A number of different approaches can be used to find an initial feasible solution. Three of these are
described here:
The northwest-corner method.
An intuitive approach/Least cost method
Vogel’s / Penalty Method

The Northwest-Corner Method

2
The northwest corner method is a systematic approach for developing an initial feasible solution. Its chief
advantages are that it is simple to use and easy to understand. Its chief drawback is that it does not take
transportation costs into account. Consequently, such a solution may require much additional effort to
obtain the optimal solution.

The northwest corner method gets its name because the starting point for the allocation process is the
upper left-hand (Northwest) corner of the transportation table. For the Harley problem, this would be the
cell that represents the route from Farm A to Project #1. The following set of principles guides the
allocation:
i. Begin with the upper left-hand cell, and allocate as many units as possible to that cell.
This will be the smaller of the row supply and the column demand. Adjust the row and
column quantities to reflect the allocation.
ii. Remain in a row or column until its supply or demand is completely exhausted or
satisfied, allocating the maximum number of units to each cell in turn, until all supply has
been allocated (and all demand has been satisfied because we assume total supply and
demand are equal).
Initial Feasible Solution for Harley using Northwest-corner method
To:
Project Project Project Supply
From: #1 #2 #3
4 2 8
Farm A 50 50 100
(first) (second)
5 1 9
Farm B 100 100 200
(third) (fourth)
7 6 3
Farm C 200 200
(last)

Deman 50 150 300 500

d

3
The total cost is found by multiplying the quantities in “completed” (i.e. nonempty) cells by the cell’s unit
cost and, then, summing those amounts. Thus:
Total cost = 50(4) + 50(2) + 100(1) + 100(9) + 200(3) = $1900
As noted earlier, the main drawback of the northwest-corner method is that it does not consider cell
(route) costs in making the allocation. Consequently, if this allocation is optimal, that can be attributed to
chance rather than the method used.
Least cost method
It uses lowest cell cost as the basis for selecting routes. The procedure is as follows:
i. Identify the cell that has the lowest unit cost. If there is a tie, select one arbitrarily. Allocate a
quantity to this cell that is equal to the lower of the available supply for the row and the
demand for the column.
ii. Cross out the cells in the row or column that has been exhausted (or both, if both have been
exhausted), and adjust the remaining row or column total accordingly.
iii. Identify the cell with the lowest cost from the remaining cells. Allocate a quantity to this cell
that is equal to the lower of the available supply of the row and the demand for the column.
iv. Repeat steps (ii) and (iii) until all supply and demand have been exhausted.
The initial feasible solution for the Harley problem completed using the above steps is shown below.
Initial Feasible Solution for the Harley problem using LCM
To:
Project Projec Project Supply
From: #1 t #2 #3
4 2 8
Farm A 50 50 100

5 1 9
Farm B 150 50 200

7 6 3
Farm C 200 200

Deman 50 150 300 500

d

4
We can easily verify that this is a feasible solution by checking to see that the row and column totals of
the assigned cell quantities equal the supply and demand totals for the rows and columns. Now let us
compute the total cost of this solution and compare it to that of the northwest corner solution.
Total cost = 50(4) + 50(8) + 150(1) + 50(9) + 200(3) = $1800
Compared to the plan generated using the Northwest-corner method, this one has a total cost that is $100
less. This is due to the fact that the previous one did not involve the use of cost information in allocating
units.
Vogel’s Approximation Method (VAM)
The third method for determining an initial solution, Vogel’s Approximation Method (also called VAM),
is based on the concept of penalty cost or regret. If a decision maker incorrectly chooses from several
alternative courses of action, a penalty may be suffered (and the decision maker may regret the decision
that was made). In transportation problem, the courses of action are the alternative routes and a wrong
decision is allocating to a cell that does not contain the lowest cost.
This method is preferred over the other two methods because the initial feasible solution obtained with
VAM is either optimal or very close to the optimal. With VAM the basis of allocation is unit cost penalty
i.e. that column or row which has the highest unit cost penalty (difference between the lowest and the
next highest cost) is selected first for allocation and the subsequent allocations in cells are also done
keeping in view the highest unit cost penalty.
Steps in VAM
1. Construct the cost, requirement, and availability matrix i.e. cost matrix with column and row
information.
2. Compute a penalty for each row and column in the transportation table. The penalty is merely the
difference between the smallest cost and the next smallest cost element in that particular row
or column.
3. Identify the row and column with the largest penalty. In this identified row (column), choose the
cell which has the smallest cost and allocate the maximum possible quantity to this cell. Delete
the row (column) in which capacity (demand) is exhausted. When there is a tie for penalty, select
one arbitrarily. After allocation, cross that row or column and disregard it from further
consideration.
4. Repeat steps 1 to 3 for the reduced table until the entire capabilities are used to fill the
requirement at different warehouses.
5. From step 4 we will get initial feasible solution. Now for initial feasible solution find the total
cost.

5
 The solution for our problem is as follows
To: Penalty
From: Project Projec Project Supply
#1 t #2 #3
4 2 8
Farm A 100
4 2 2
5 1 9
Farm B 200
5 1 4
7 6 3
Farm C 200
6 3 3
200 0

Demand 50 150 300

100

4 1 3 selected
Penalty 1 1 5

Table2 Penalty
To:
From: Project Project Project #3 Supply 4 2 2
#1 #2
4 2 8
Farm A 100
5 1 4
5 1 9
Farm B 150 200 50
-- selected

7 6 3
Farm C 200 200
0

Demand 50 150 300 100 Penalty 5 2

9 Second allocation
-4 1 8
1 1 1

6
Table 3
To:
Third From: Project Project Project #3 Supply
#1 #2 allocation
4 2 8
Penalty Farm A 100 50
50
4 selected
5 1 9
Farm B 150 200 50
4
7 6 3
Farm C 200 200 0

Demand 50 150 300 100

Penalty 1 - 1

Table 4
Since there is no penalty for the remaining cells, we allocate for these cells according to their
cost.

To:
From: Project Project Project #3 Supply
#1 #2
4 2 8
Farm A 50 50 100
50 Fourth allocation
5 1 50 9
Farm B 150 200
50
7 6 3
Farm C 200 200

Total Demand 50 150 300 100 50 cost:

1x150 + 3x200+4x50 + 8x50 + 9x50
Total cost = Birr 1800

Evaluating a Solution for Optimality

7
The test for optimality for a feasible solution involves a cost evaluation of empty cells (i.e., routes to
which no units have been allocated) to see if an improved solution is possible. We shall consider two
methods for cell evaluation:
The Stepping-stone method
The MODI method
The Stepping-stone method
The 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 one unit into an empty cell, and it enables the
manager or analyst to answer a “what-if” question: What impact on total cost would there be if one unit
were shifted into an unused route? The result is a cost change per unit shifted into a cell. If the shift would
result in a cost savings, the stepping-stone path also can be used to determine the maximum number of
units that can be shifted into the empty cell, as well as modifications to other completed cells needed to
compensate for the shift into the previously unused cell.
Rules for tracing Stepping-stone paths:
i. All unoccupied cells must be evaluated. Evaluate cells one at a time.
ii. Except for the cell being evaluated, only add or subtract in occupied cells. (It is permissible to
skip over unoccupied cells to find an occupied cell from which the path can continue.)
iii. A path will consist of only horizontal and vertical moves, starting and ending with the empty cell
that is being evaluated.
iv. Alter + and – signs, beginning with a + sign in the cell being evaluated.

To:
Projec Project Projec Supply
From: t #1 #2 t #3
4 2 8
Farm A 50 50 100
–- +
5 1 9
Farm B 100 100 200
– +
7 6 3
Farm C + – 200 200

Demand 50 150 300 500

The MODI method

8
The MODI (Modified Distribution) method of evaluating a transportation solution for optimality involves
the use of index numbers that are established for the rows and columns. These are based on the unit costs
of the occupied cells. The index numbers can be used to obtain the cell evaluations for empty cells
without the use of stepping-stone paths.
There is one index number for each column and one for each row. These can be conveniently displayed
along the left and upper edges of a matrix. The index numbers are determined in such a way that for any
occupied cell, the sum of the row index and the column index equal the cell’s unit transportation cost:

Row index + Column index = Cell cost

ri + kj = cij

The index numbers are determined sequentially in a manner dictated by the position of occupied cells.
The process always begins by assigning a value of zero as the index number of row 1
The method will be illustrated by developing index numbers for the initial feasible solution for the Harley
problem generated by the northwest-corner method. We begin assigning a value of zero for row 1. Once a
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. The complete set of row and column
index numbers is shown in the following table.
Cell evaluations for Northwest Corner solution for the Harley Problem using the MODI method
k1 k2 k3
+4 +2 +10
To:
Project Project Project Supply
From: #1 #2 #3
4 2 8
r1 0 Farm A 50 50 100

5 1 9
r2 -1 Farm B 100 100 200

7 6 3
r3 -7 Farm C 200 200

Demand 50 150 300 500

The cell evaluations (improvement potentials) for each of the unoccupied cells are determined using the
relationship:

9
 Cell evaluation = Cell cost – Row index – Column index
eij = cij – ri – kj

For example, the cell evaluations for A-3 is 8 – 0 – 10 = -2. Similarly, the evaluation for B-1 is +2, for C-
1, +10, and for C-2, it is +11. Note that they agree with the values we computed earlier using the
stepping-stone method.

When cell evaluations are positive or zero, an optimal solution has been found. If one or more is negative,
the cell with the largest negative should be brought into solution because that route has the largest
potential for improvement per unit. In this case, we found that cell A-3 had an evaluation of –2, which
represented an improvement potential of $2 per unit. Hence, an improved solution is possible.
Generally
Developing an improved solution to a transportation problem requires focusing on the unoccupied cell
that has the largest negative cell evaluation. Improving the solution involves reallocating quantities in the
transportation table. More specifically, we want to take advantage of the improvement potential of cell A-
3 by transferring as many units as possible into that cell. The stepping-stone path for that cell is necessary
for determining how many units can be reallocated while retaining the balance of supply and demand for
the table. The stepping-stone path also reveals which cells must have quantity changes and both the
magnitude and direction of changes. 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. With each iteration (new solution), it is necessary to evaluate the empty cells to see if
further improvement is possible. This requires use of either the MODI or the Stepping-stone method.
Both will yield the same values.
SPECIAL ISSUES
There are a number of special issues in relation to the transportation model. They are:
i. Determining if there are alternate optimal solutions.
ii. Defining and handling degeneracy (too few occupied cells to permit evaluation of a solution).
iii. Avoiding unacceptable or prohibited route assignments.
iv. Dealing with problems in which supply and demand are not equal.
v. Solving maximization problems.

Alternate Optimal Solutions

10
Sometimes, transportation problems have multiple optimal solutions. In such instances, it can be useful
for a manager to be aware of alternate solutions, because this gives the manager an option of bringing
non-quantitative considerations into the decision. In the case of the transportation problem, the existence
of an alternate solution is signaled by an empty cell’s evaluation equal to zero.
Degeneracy
A solution is degenerate if the number of occupied cells is less than the number of rows plus the number
of columns minus one. i.e., there are too few occupied cells to enable all the empty cells to be evaluated.
In the case of the stepping-stone method, this means that there will be at least one empty cell for which an
evaluation path cannot be constructed. For the MODI method, it means that it will be impossible to
determine all of the row and column index numbers. Obviously, some modification has to be made to
determine if such a degenerate solution is optimal. The modification is to treat some of the empty cells as
occupied cells. This is accomplished by placing a delta () in one of the empty cells. The delta represents
an extremely small quantity (e.g., 0.001 unit); it is so small that supply and demand for the row and
column involved will be unaffected even without modifying other quantities in the row or column, and so
small that total cost will not change.
The purpose of the delta is to enable evaluation of the remaining empty cells. The choice of location for
the delta can be somewhat tricky: some empty cells may be unsuitable if they do not enable evaluations of
the remaining empty cells. Moreover, the 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 delta will be the “smallest quantity in 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 delta.
The technique can be demonstrated for the degenerate alternate solution of the Harley problem. Suppose
that after some experimentation, cell A-1 has been selected for the location of delta. The resulting index
numbers generated using MODI and the improvement potential for empty cells based on delta in cell A-1
are shown in the following table. This confirms that the solution is optimal

Harley Alternate Solution Modified for Degeneracy

11
 +4 0 +8
To:
Project Project Project Supply
From: #1 #2 #3
4 2 8
0 Farm A Δ 100 100

5 1 9
+1 Farm B 50 150 200

7 6 3
-5 Farm C 200 200

Demand 50 150 300 500

Unacceptable Routes
In some cases, an origin-destination combination may be unacceptable. This may be due to weather
factors, equipment breakdowns, labor problems, or skill requirements that either prohibit, or make
undesirable, certain combinations (routes).
Suppose that in the Harley problem route A-3 was suddenly unavailable because of recent flooding. In
order to prevent that route from appearing in the final solution (as it originally did), the manager could
assign a unit cost to that cell that was large enough to make that route uneconomical and, hence, prohibit
its occurrence. One rule of thumb would be to assign a cost that is 10 times the largest cost in the table (or
a very big +M). Then, this revised problem could be solved using either of the methods we have
discussed earlier. Note that the prohibited route may appear in a non-optimal solution, but it will be
eliminated by the time the optimal solution is reached.
Unequal Supply and Demand
Up to this point, examples have involved cases in which supply and demand were equal. As you might
guess, there are situations in which the two are not equal. When such a situation is encountered, it is
necessary to modify the original problem so that supply and demand are equal. This is accomplished by
adding either a dummy column or a dummy row; a dummy row is added if supply is less than demand
and a dummy column is added if demand is less than supply. The dummy is assigned unit costs of zero
for each cell, and it is given a supply (if a row) or a demand (if a column) equal to the difference between
supply and demand. Quantities in dummy routes in the optimal solution are not shipped. Rather, they
serve to indicate which supplier will hold the excess supply, and how much, or which destination will not
receive its total demand, and how much it will be short.

12
Let’s consider an example. Suppose that Farm C in the Harley problem has experienced an equipment
breakdown, and it will be able to supply only 120 cubic yards of topsoil for a period of time. Therefore,
total supply will be 80 units less than total demand. This will require adding a dummy origin with a
supply of 80 units. The final solution is shown in the following table. We interpret the solution
indicating that Project #3 will be short by 80 units per week until the equipment is repaired. Note,
though, that this analysis has considered only transportation costs, and that other factors, such are
shortage costs or schedules of the projects, may dictate some other course of action.
If the intuitive approach is used to obtain the initial feasible solution when a dummy is involved, make
assignments to the dummy last. Hence, begin by assigning units to the cell with the lowest nonzero cost,
then the next lowest nonzero cost, and so on. For the Harley problem this would mean that units would
be assigned first to cell B-2 because its cost of $1 is the lowest nonzero cell cost.

To:
Project Project Project Supply
From: #1 #2 #3
4 2 8
Farm A 50 50 100

5 1 9
Farm B 150 50 200

7 6 3
Farm C 120 120

0 0 0
Dummy 80 80

Demand 50 150 300 500

Maximization
Some transportation type problems concern profits or revenues rather than costs. In such cases, the objective is to
maximize rather than to minimize. Such problems can be handled by adding one additional step at the start: Identify
the cell with the largest profit and subtract all the other cell profits from that value. Then replace the cell profits with
the resulting values. These values reflect the opportunity costs that would be incurred by using routes with unit
profits that are less than the largest unit profit. Replace the original unit profits with these opportunity cost solution.
This will be identical to maximizing the total profit.
The remainder of the steps for developing an initial feasible solution, evaluation of empty cells, and reallocation are
identical to those used for cost minimization. When the optimal distribution plan has been identified, use the original
cell values (i.e., profits) to compute the total profit for that plan.
THE ASSIGNMENT PROBLEM

13
4.2.3. HUNGARIAN ASSIGNEMNT METHOD (HAM)
A method, designed specially to handle the assignment problems in an efficient way, called the
Hungarian Assignment Method, is available, which is based on the concept of opportunity cost.
For a typical balanced assignment problem involving a certain number of persons and an equal
number of jobs, and with an objective function of the minimization type, the method is applied as
listed in the following steps:
Step 1. Locate the smallest cost element in each row of the cost table. Now subtract this smallest
from each element in that row. As a result, there shall be at least one zero in each row
of this new table, called the Reduced Cost Table (Row Reduction).
Step 2. In the reduced cost table obtained, consider each column and locate the smallest element
in it. Subtract the smallest value from every other entry in the column. As a
consequence of this action, there would be at least one zero in each of the rows and
columns of the second reduced cost table (Column Reduction).
Step 3. Draw the minimum number of horizontal and vertical lines (not diagonal ones) that are
required to cover the entire ‘zero’ elements. If the number of lines drawn is equal to n
(the number of rows/columns) the solution is optimal, and proceeds to step 6. If the
number of lines drawn is smallest than n, go to step 4.
Step 4. Select the smallest uncovered (by the lines) cost element. Subtract this element from all
uncovered elements including it and add this element to each value located at the
intersection of any lines. The cost elements through which only one line passes
remain unaltered.
Step 5. Repeat steps 3 and 4 until an optimal solution is obtained.
Step 6. Given the optimal solution, make the job assignments as indicated by the ‘zero’ elements.
This done as follows:
a) Locate a row which only ‘zero’ element. Assign the job corresponding to this element to
its corresponding person. Cross out the zeros, if any, in the column corresponding to the
element, which is indicative of the fact that the particular job and person are no more
available.
b) Repeat (a) for each of such rows which contain only one zero. Similarly, perform the
same operation in respect of each column containing only one ‘zero’ element, crossing
out the zero(s), if any, in the row in which the element lies.

14
 c) If there is no row or column with only a single ’zero’ element left, then select a
row/column arbitrarily and choose one of the jobs (or persons) and make the assignment.
Now cross the remaining zeros in the column and row in respect of which the assignment
is made.
d) Repeat steps (a) through (c) until all assignments are made.
e) Determine the total cost with reference to the original cost table.
Example
Solve the assignment problem given in Illustrative Example 1 for optimal solution using HAM.
The information is reproduced in the following table.
Time Taken (in minutes) by 4 workers
Job
Worker A B C D
1 45 40 51 67
2 57 42 63 55
3 49 52 48 64
4 41 45 60 55

The solution to this problem is given here in a step-wise manner.

Step 1: The minimum value of each row is subtracted from all elements in the row. It is shown in
the reduced cost table, also called opportunity cost table, given as follows.
Reduced Cost Table 1/row reduction
Job
Worker A B C D
1 5 0 11 27
2 15 0 21 13
3 1 4 0 16
4 0 4 19 14

15
Step 2: For each column of this table, the minimum value is subtracted from all the other values.
Obviously, the columns that contain a zero would remain unaffected by this operation. Here only
the fourth column values would change. The table below shows this.
Reduced Cost Table 2/column reduction
Job
Worker A B C D
1 5 0 11 14
2 15 0 21 0
3 1 4 0 3
4 0 4 19 1

Step 3: Draw the minimum number of lines covering all zeros. As a general rule, we should first
cover those rows/columns which contain larger number of zeros. The above table is reproduced
in the next table and the lines are drawn.

Reduced Cost Table3

Job
Worker A B C D
1 5 0 11 14
2 15 0 21 0
3 1 4 0 3
4 0 4 19 1

Step 4: Since the number of lines drawn is equal to 4(=n), the optimal solution is obtained. The
assignments are made after scanning the rows and columns for unit zeros. Assignments made are
shown with squares, as shown in the following table.

Assignment of Jobs

16
 Job
Worker A B C D
1 5 0 11 14
2 15 0 X 21 0
3 1 4 0 3
4 0 4 19 1

Assignments are made in the following order. Rows 1, 3, and 4 contain only one zero each. So
assign 1-B, 3-C and 4-A. Since worker 1 has been assigned job B, only worker 2 and job E are
left for assignment. The final pattern of assignments is 1-B, 2-D, 3-C, and 4-A, involving a total
time of 40+55+48+41=184 minutes.
Example
Using the following cost matrix, determine (a) optimal assignment, and (b) the cost of
assignments.
Reduced Cost Table 1
Job
Machinist 1 2 3 4 5
A 10 3 3 2 8
B 9 7 8 2 7
C 7 5 6 2 4
D 3 5 8 2 4
E 9 10 9 6 10

Iteration 1: Obtain row reductions.

17
 Reduced Cost Table 1
Job
Machinist 1 2 3 4 5
A 8 1 1 0 6
B 7 5 6 0 5
C 5 3 4 0 2
D 1 3 6 0 2
E 3 4 3 0 4

Iteration 2: Obtain column reductions and draw the minimum number of lines to cover all
zeros.
Reduced Cost Table2
Job
Machinist 1 2 3 4 5
A 7 0 0 0 4
B 6 4 5 0 3
C 4 2 3 0 0
D 0 2 5 0 0
E 2 3 2 0 2

Since the number of lines covering all zeros is less than the number of columns/rows, we modify
the Table 6.13. The least of the uncovered cell values is 2. This value would be subtracted from
each of the uncovered values and added to each value lying at the intersection of lines
(corresponding to cells A-4, D-4, A-5 and D-5). Accordingly, the new table would appear as
shown as follows.

Iteration 3

18
 Job
Machinist 1 2 3 4 5
A 7 0 0 X 2 6
B 4 2 3 0 3
C 2 0 X 1 0 X 0
D 0 2 5 2 2
E 0 X 1 0 0 X 2

The optimal assignments can be made as the least number of lines covering all zeros in Table
6.14 equals 5. Considering rows and columns, the assignments can be made in the following
order:
i. Select the second row. Assign machinist B to job 4. Cross out zeros at cells C-4 and E-4.
ii. Consider row 4, Assign machinist D to job 1. Cancel the zero at cell E-1.
iii. Since there is a single zero in the row, put machinist E to job 3 and cross out the zero at
A-3.
iv. There being only a single left in each of the first and third rows, we assign job 2 to
machinist A and job 5 to C.
The total cost associated with the optimal machinist-job assignment pattern A-2, B-4, C-5, D-1
and E-3 is 3+2+4+3+9 = 21
Special Issues in assignment problems
When we solve assignment problems, there are cases which are treated differently from the usual
way.
Unbalanced Assignment Problems
The Hungarian Method of solving an assignment problem requires that the number of columns
should be equal to the number of rows. They are equal, the problem is balanced problem, and
when not, it is called an unbalanced problem. Thus, where there are 5 workers and 4 machines,
or when there are 4 workers and 6 machines, for instance, we have unbalanced situations in
which one-to-one match is not possible. In case the machines are in excess, the excess
machine(s) would remain idle and so is the case when men are in excess- the number of excess
people would get an assignment.

19
In such situations, dummy column(s)/row(s), whichever is smaller in number, are inserted
with zeros as the cost elements. For example, when the given cost matrix is of the dimension
4*5, a dummy row would be included. In each column in respect of this row, a ‘zero’ would
be placed. After this operation of introducing dummy columns/rows, the problem is solved in
the usual manner.
Example:
A company has 4 machines to do 3 jobs. Each job can be assigned to one and only one
machine. The cost of each job on each machine is given below. Determine the job
assignments which will minimize the total cost.
Machine
W X Y Z
A 18 24 28 32
Job
B 8 13 17 18
C 10 15 19 22
Add dummy row and follow similar procedures of HAM at a normal case

Machine
W X Y Z
A 18 24 28 32
Job
B 8 13 17 18
C 10 15 19 22
dumm 0 0 0 0
y

Reduced Cost Table 1/row reduction

Machine

20
 W X Y Z
A 14 8 4 0
Job
B 10 5 1 0
C 12 7 3 0
Dumm 0 0 0 0
y

Constrained/Prohibited/ Assignment Problems

It happens sometimes that a worker cannot perform a certain job or is not to be assigned a
particular job. To cope with this situation, the cost of performing that job by such person is taken
to be extremely large (which is written as M). Then the solution to the assignment problem
proceeds in the manner discussed earlier. The effect of assigning prohibitive cost to such person-
job combinations is that they do not figure in the final solution.
Example:
You are given the information about the cost of performing different jobs by different persons.
The job-person marking X indicates that the individual involved cannot perform the particular
job. Using this information, state (i) the optimal assignment of jobs, and (ii) the cost of such
assignment,

Job
J1 J2 J3 J4 J5
P1 27 18 X 20 21
P2 31 24 21 12 17
person

P3 20 17 20 X 16
P4 22 28 20 16 27

Solution: - Balancing the problem not assigning a high cost to the pairings P1-J3 and P3-
J4, we have the cost given in the table below.

21
 Job
J1 J2 J3 J4 J5
P1 27 18 M 20 21
P2 31 24 21 12 17
P3 20 17 20 M 16
P4 22 28 20 16 27
P5 0 0 0 0 0
person

dummy

Now we can derive the reduced cost table as shown in table shown below. Note that the cells
with prohibited assignments continue to be shown with the cost element M, since M is
defined to be extremely large so that subtraction or addition of value does not practically
affect it. To test optimality, lines are drawn to cover all zeros.

Reduced Matrix
Job
J1 J2 J3 J4 J5
P1 9 0 M 2 3
P2 19 12 9 0 5
P3 4 1 4 M 0
P4 6 12 4 0 11
P5 0 0 0 0 0
person

dummy

Since the number of lines covering all zeros is less than n, we select the lowest uncovered cell,
which equals 1. With this value, we can obtain the revised reduced cost table, and follow the
procedure
Unique Vs Multiple Optimal Solutions
In the process of making assignments, it was stated earlier that we select a row/column with only
a single zero to make an assignment. However, a situation may where in the various rows and

22
columns, where assignment are yet to be done, have all multiple zeros. In such cases, we get
multiple optimal solutions to the given problem. In any of the problems discussed so far, we have
not experienced such a situation. Hence, each one of them has had a unique optimal solution.
When a problem has a unique optimal solution, it means that no other solution to the problem
exists which yields the same objective function value (cost, time, profit e.t.c) as the one obtained
from the optimal solution derived. On the other hand in a problem with multiple optimal
solutions, there exists more than one solution which all is optimal and equally attractive.
Consider the following example.
Example:
Solve the following assignment problem and obtain the minimum cost at which all the jobs can
be performed.
Job (cost in ’00 Br.)
Worker 1 2 3 4 5
A 25 18 32 20 21
B 34 25 21 12 17
C 20 17 20 32 16
D 20 28 20 16 27
Solution: This problem is unbalanced since number of jobs is 5 while the number of workers is
4. We first balance it by introducing a dummy worker E, as shown in table below.
Balancing the Assignment Problem
Job (cost in ’00 Br.)
Worker 1 2 3 4 5
A 25 18 32 20 21
B 34 25 21 12 17
C 20 17 20 32 16
D 20 28 20 16 27
E 0 0 0 0 0

Step 1: Obtain reduced cost values by subtracting the minimum value in each row from
every cell in the row. This is given in Table below.

23
Reduced Cost 1
Job (cost in ’00 Br.)
Worker 1 2 3 4 5
A 7 0 14 2 3
B 22 13 9 0 5
C 4 1 4 16 0
D 4 12 4 0 11
E 0 0 0 0 0

Since there is at least one zero in each row and column, we test it for optimality.
Accordingly, lines are drawn. All zeros are covered by 4 lines, which is less than 5 (the order
of the given matrix). Hence, we proceed to improve the solution. The least uncovered value
is 4. Subtracting from every uncovered value and adding it to every value lying at the
intersection of lines, we get the revised values as shown below.

Reduce cost 2 and Assignment

Job (cost in ’00 Br.)
Worker 1 2 3 4 5
A 7 0 14 6 3
B 18 9 5 0 1
C 4 1 4 20 0
D 0 8 0 0 X 7
E 0 X 0 X 0 4 0 X

The solution given in the reduced cist 2 table is optimal since the number of lines covering
zeros matches with the order of the matrix. We can, therefore, proceed to make assignments.
To begin with, since each of the columns has multiple zeros, we cannot start making
assignments considering columns and have, therefore, to look through rows. The first row
has a single zero. Thus, we make assignment A-2 and cross out zero at E-2. Further, the

24
 second and the third rows have one zero each. We make assignments B-4 and C-5, and cross
out zeros at D-4 and E-5. Now, both the rows left two zeros each and so have both the
columns. This indicates existence of multiple optimal solutions. To obtain the solutions, we
select zeros arbitrarily and proceed as discussed below.

i. Select the zero at D-1, make assignment and cross out zeros at D-3 and E-1 (as both,
worker D and job 1, are not available any more). Next, assign worker E to job 3,
corresponding to the only zero left. Evidently, selecting the zero at E-3 initially would have
the effect of making same assignments.
ii. Select the zero at D-3, make assignment and cross at D-1 and E-3. Next, make assignment
at the only zero left at E-1. Obviously, selecting the zero at E-1 making assignment in the
first place would lead to the same assignments.

To conclude, the problem has two optimal solutions as given below.

Solution 1 (’00 Br.) Solution 2 (’00 Br.) cost

Worker Job cost Worker Job Cost
A 2 18 A 2 18
B 4 12 B 4 12
C 5 16 C 5 16
D 1 20 D 3 20
Job left 3 Job left 1
Total 66 Total 66

Maximization Case in Assignment Problem

In some situations, the assignment problem may call for maximization of profit, revenue, e.t.c.
as the objective. For example, we may be faced with the problem of assignment of salesmen in
different regions in which they can display different qualities in making sales (reflected in
amounts of sales executed by them). Obviously, assignment would be made in such a way that
the total expected revenue is maximized.

25
For dealing with a maximization problem, we first change it into an equivalent minimization
problem. This is achieved by subtraction each of the elements of the given pay-off matrix from a
constant (value) k. Thus, we may simply put a negative sign before each of the pay-off values
(which is equivalent to subtracting each value from zero). Usually, the largest value of all values
in the given matrix is located and then each one of the values is subtract from it (the largest value
is taken so as to avoid the appearance of negative signs). Then the problem is solved the same
way as a minimization problem is
Example:
A company plans to assign 5 salesmen to 5 districts in which it operates. Estimates of sales
revenue in thousands of birr for each salesman in different districts are given in the following
table. In your opinion, what should be the placement of the salesmen if the objective is to
maximize the expected sales revenue?

District
Salesman D1 D2 D3 D4 D5
S1 40 46 48 36 48
S2 48 32 36 29 44
S3 49 35 41 38 45
S4 30 46 49 44 44
S5 37 41 48 43 47
Solution: Since it is a maximization problem, we would first subtract each of the entries in
the table from the largest one, which equals 49 here. The resultant data are given in Table
below.

Opportunity Loss Matrix

26
 District
Salesman D1 D2 D3 D4 D5
S1 9 3 1 13 1
S2 1 17 13 20 5
S3 0 14 8 11 4
S4 19 3 0 5 5
S5 12 8 1 6 2

Now, we will proceed as usual.

Step 1: Subtract value in each row from every value in the row. The resulting values are
given in table below.
Reduced cost Table 1
District
Salesman D1 D2 D3 D4 D5
S1 8 2 0 12 0
S2 0 16 12 19 4
S3 0 14 8 11 4
S4 19 3 0 5 5
S5 11 7 0 5 1

Step 2: Subtract minimum value in each column in reduced cost table 1 from each value in
the column. Test for optimality by drawing lines to cover zeros. These are shown in table
below (in the Reduced cost Table 2)

Reduced cost Table 2

District

27
 Salesman D1 D2 D3 D4 D5
S1 8 0 0 7 0
S2 0 14 12 14 4
S3 0 12 8 6 4
S4 19 1 0 0 5
S5 11 5 0 0 1

Since the number of lines covering all zeros is fewer than n, we select uncovered cell value,
which equals 4. With this, we can modify the table as given in the Reduced Cost Table 3 and
follow the Hungarian procedures.

28