lOMoARcPSD|23226106

Chapter three lecture note operation research

Operation Research (Addis Ababa University)

Studocu is not sponsored or endorsed by any college or university

Downloaded by Amanuel Markos ([email protected])
 lOMoARcPSD|23226106

CHAPTER THREE

3.1. Transportation and Assignment Models

In the previous chapters we have discussed about linear programming, which is more general.
In this chapter we will discuss about special types of linear programming models called
Transportation and Assignment Models. The purpose of using an LP model for transportation
problems is to minimize transportation costs, taking into account the origin supplies, the
destination demands, and the transportation costs.
Examples of transportation problems include shipments from warehouses to retail stores,
shipment from factories to warehouses, shipments between departments within a company,
and production scheduling.

3.1.1. Formulating the Transportation Model

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.
.
Example
Let‟s consider an example. Harley‟s Sand and Gravel Pit have 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 Projects #3
Farm A Birr4 Birr 2 Birr 8
Farm B 5 1 9
Farm C 7 6 3
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.

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

Transportation table for Harley‟s sand and gravel

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

5 1 9
Farm B 200

7 6 3
Farm C 200

Demand 50 150 300

 Note: It is possible to write this transportation problem in the form of LPM.

Nine (3x3) decision variables are there and the objective function is minimization.
LPM for this problem is:
Zmin: 4x11 + 2x12 +8x13 + 5x21 + x22 + 9x23 + 7x31 + 6x32 + 3x33
Subject to:
x11 + x12 +x13  100
x21 + x22 + x23  200 Capacity/ Source constraint
x31 + x32 + x33  200

x11 + x21 + x3 1  50
x12 + x22 +x32  150 Demand/Destination constraint
x13 + x23 + x33  300

This can be rewritten as:

Zmin: 4x11 + 2x12 +8x13 + 5x21 + x22 + 9x23 + 7x31 + 6x32 + 3x33
Subject to:
x11 + x12 + x13  100
x21 + x22 + x23  200
x31 + x32 + x33  200
x11 + x21 + x31  50
x12 + x22 + x32  150
x13 + x23 + x33  300
x11 , x12, x13 ,x21, x22 , x23 , x31, x32 , x33  0

3.1.2. Finding the 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

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

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
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 #2 Project #3 Supply
From: #1
4 2 8
Farm A 50(first) 50(second) 100
5 1 9
Farm B 100 100(fourth) 200
(third)
7 6 3
Farm C 200(last) 200

Demand 50 150 300 500

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

This approach, also known as the minimum-cost method, uses lowest cell cost as the basis for
selecting routes. The procedure is as follows:

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

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 the Intuitive approach
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 200 200

Demand 50 150 300 500

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

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

(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 highest cost and the next highest 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.
The solution for our problem is as follows:
To: Penalty
From: Project Project Project Supply Hc NHC Hc- NHC
#1 #2 #3
4 2 8
Farm A 100
8 4 4
5 1 9
Farm B 150 200
9 5 4 selected
1
7 6 3 7 6 1
Farm C 200

Demand 50 150 300

HC 7 6 9 First allocation
NHC 5 2 8
Penalty 2 4 1
HC: Highest cost
NHC: Next Highest cost

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

Table2 Penalty
To: Hc NHC Hc- NHC
From: Project Project Project #3 Supply
#1 #2
4 2 8
8 4 Farm A 100
4

9 5 5 1 9 4
Farm B 150 200 50

7 3 7 6 3 4 selected
Farm C 200 200
2

Demand 50 150 300 100

Penalty 2 - 1 Second allocation

Table 3
Third To:
From: Project Project Project #3 Supply Penalty
allocation #1 #2
4 3 4 2 8 selected
Farm A 50 100 50

4 5 1 9
Farm B 150 200 50

7 6 3
Farm C 200 200

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.

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

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

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

Demand 50 150 300 100 50

Fifth allocation
Therefore the final allocation will be:
To:
From: Project Project Project #3 Supply
#1 #2
4 2 8
Farm A 50 50 100

4
5 1 50 9
Farm B 150 200

7 6 3
Farm C 200 200

5
Demand 50 150 300

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

NB. Could you make comparison among costs of the three approaches? Why do you think
cost of North West corner method has the highest cost?

3.3. Evaluating a Solution for Optimality

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 involves a good deal of more effort than the MODI method.
However, it provides an intuitive understanding of the evaluation process. Moreover, when a
solution is not optimal, the distribution plan must be revised by reallocating units into and out
of various cells, and only the stepping-stone method can be used for the reallocation.

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

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

Reconsider the initial feasible solution we found using the northwest-corner method. Only the
unoccupied cells need to be evaluated because the question at this point is not how many
units to allocate to a particular route but only if converting a cell from zero units to nonzero
(a positive integer) would decrease or increase total costs. The unoccupied cells are A-3, B-1,
C-1, and C-2. They must be evaluated one at a time, but no particular order.

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.

 Note that it is not necessary to actually alter the quantities in the various cells to reflect
the one-unit change, the + and – signs suffice.

The general implication of the plus and minus signs is that cells with + signs mean one unit
would be added, cells with a – sign indicate one unit would be subtracted. The net impact of
such a one-unit shift can be determined by adding the cell costs with signs attached and
noting the resulting value. Thus, for cell B-1, we have a net change of +2 (i.e., 5+2-4-1)
which means that for each unit shifted into cell B-1, the total cost would increase by $2.
Computed in similar way, the evaluations of cells C-1, A-3, and C-2 result in +10, -2, and
+11 respectively. The negative value for cell A-3 indicates an improved solution is possible:
For each unit we can shift into that cell, the total cost will decrease by $2. The following table
shows how empty cell C-1 can be evaluated using the Stepping stone method.

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

Evaluation path for cell C-1

To:
Project Project Project Supply
From: #1 #2 #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

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

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

The cell evaluations (improvement potentials) for each of the unoccupied cells are
determined using the relationship:
Cell evaluation = Cell cost – Row index – Column index
eij = cij – ri – kj
k1 k2 k3
+4 +2 +10
To: -2
Project Project Project Supply
From: #1 #2 #3
4 2 8
r1 0 Farm A 50 50 100
+2

5 1 9
r2 -1 Farm B 100 100 200

+10 7 +11 6 3
r3 -7 Farm C 200 200

Demand 50 150 300 500

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.
3.1.3. Developing an Improved Solution
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.

After reallocating the units using the stepping stone method, the empty cells will be A-2, B-1,
C-1 and C-2. Suppose we use the MODI method for evaluation. After assigning all the row
and column indices, we find the cell evaluations to be as follows:

Cell A-2: 2 – 0 – 0 = +2
Cell B-1: 5–1–4= 0
Cell C-1: 7-(-5)- 4 = +8

10

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

Cell C-2: 6-(-5)- 0 = +11

Because none of these numbers is negative, this is an optimal solution. You may recall that
this was the same solution obtained using the intuitive method for the initial feasible solution.
At that point, it was determined that the total cost for the distribution plan was $1800.
Optimal Solution for the Harley problem
+4 0 +8
To:
Project Project Project Supply
From: #1 #2 #3
4 2 8
0 Farm A 50 +2 50 100

5 1 9
+1 Farm B 150 50 200
0

7 6 3
-5 Farm C +11
200 200
+8

Demand 50 150 300 500

3.1.4. 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. Dealing with problems in which supply and demand are not equal.
iv. Solving maximization problems.
o Alternate Optimal Solutions
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. In fact, you may have noted that cell B-1 had an
evaluation equal to zero in the final solution of the Harley problem. We can find out what that
alternate solution is by reallocating the maximum number of units possible around the
stepping-stone path for that cell. After the cell evaluation of, and reallocating units to cell B-
1, we find the following table to be an alternate optimal solution.

11

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

Alternate optimal solution for the Harley problem

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

5 1 9
Farm B 50 150 200

7 6 3
Farm C 200 200

Demand 50 150 300 500

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

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

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.

12

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

Solution using the Dummy Origin

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. For example,
suppose in the Harley problem, the cell values had been unit profits instead of unit costs. Cell
B-3 had the largest dollar value: $9. Hence, each cell‟s dollar amount would be subtracted
from 9. For cell A-1, the resulting opportunity cost would have been 9-4 = 5 and so on. Cell
B-3 would have an opportunity cost of 0 making it the most desirable route.

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.
3.2. ASSIGNMENT PROBLEMS
In the previous section we discussed about the transportation problem. Now we consider
another type of special linear programming problem, called the assignment problem.

There are many situations where the assignment of people or machines and so on, may be
called for. Assignment of workers to machines, clerks to various counters, salesmen to
different sales areas, service crews to different districts, are typical examples of these. The
assignment is a problem because people possess varying abilities for performing different
jobs and, therefore, the costs of performing the jobs by different people are different.
Obviously, if all persons could do a job in the same time or at the same cost then it would not
matter who of them is assigned the job. Thus, in assignment problem, the question is how
should the assignment be made in order that the total cost involved is minimized (or the total
value is maximized when pay-offs are given in terms of, say, profits).

13

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

A typical assignment problem follows:

Example
A production supervisor is considering how he should assign the four jobs that are
performed, to four of the workers working under him. He want to assign the jobs to the
workers such that the aggregate time to perform the job in the least. Based on the
previous experience, he has the information on the time taken by the four workers in
performing these jobs, as given in below
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

Example
A computer center has got four Expert Programmers. Centre needs four application
programmers to be developed. The head of dept., estimate the computer required by the
respective experts to develop the application programs as follows. Make appropriate
selection of experts.

Program A B C D
Expert
1 120 100 80 90
2 80 90 110 70
3 110 140 120 100
4 90 90 80 90

3.2.1. THE ASSIGNMENT PROBLEM (A.P) definition:

1. The Assignment Problem (A.P) is a special case of Transportation Problem (T.P) under
the condition that the number of origins is equal to the number of destinations,
i.e. m=n
Hence assignment is made on the basis of 1:1
Number of jobs equal to 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 production cycle time e.t.c.
2.
A.P
The Assignment Problem (A.P.) is a special case of Transportation
Problem (T.P.) in which the number of sources and destinations are the
same, and the objective is to assign the given job (task) to most appropriate
machine (person) so as to optimize the objective like minimizing cost.

14

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

Cost Vector (Cij)

Cost vector (Cij) is the cost of assigning ith job (Task) to jth machine
(person),
Assignment Vector (Xij) is defined as follows
Xij = 0; If ith job (Task) is not assigned by jth machine (person) or
Xij = 1; If ith job (Task) is assigned to jth machine (person).
Cost Matrix (Cij)
Assignment problem is stated in the form of (n*n) matrix. This is called
cost matrix. This is illustrated as given below.
Cij = cost of assigning ith job to jth machine
(Symbols j = Job (Task) M = Machine (person)

General Assignment Problem Table

.
M 1 2 3 … k … n
J
1 C11 C12 C13 … C1k … C1n
2 C21 C22 C23 … C2k … C2n
3 C31 C32 C33 … C3k … C3k
… … … … … … … …
K Ck1 Ck2 Ck3 … Ckk … Ckn
… … … … … … … …
N Cn1 Cn2 Cn3 … Cnk … Cnn

Effective Matrix
A cost Matrix in A.P. is called an “Effectiveness Matrix” when there is at
least one zero in each row and column. Following is an example of
Effectiveness Matrix.

1 2 3 4
1 0 1 3 4
2 5 0 6 0
3 7 8 0 9
4 0 4 3 8
3. Mathematical Modeling of an A.P.
Let there be „n‟ jobs in a manufacturing plant. Let there be „n‟ machines to process
the product. A job i (i = 1, 2,…, n) when processed in a machine j (j = 1,2,…, n), it is
assumed to incur a cost of Cij.
The assignment is made in such a way that one job is associated with one machine
(see assumption). Hence we have the following:
n n
 i  1Xij  1 =  j  1Xij  1

Where: - xij is the assignment- vector discussed earlier

Cij is the cost vector associated with the assignment vector xij.
Total assignment cost (Z) is, therefore, given by the following:

15

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

 
n n
Z= i 1 j 1
Cij * xij
Thus the mathematical formulation of assignment Problem is given as follows:
Minimize
 
n n
Z= i 1 j 1
Cij * xij
Subject to
n
 i  1Xij  1 i = 1, 2, 3… n

n
 j  1Xij  1 j = 1, 2, 3…, n

This special structure of A.P. makes solution much easy compared to the conventional T.P.

Remark:
1. It may be noted that assignment problem is a variation of transportation problem with two
characteristics (i) the cost matrix is square matrix, and (ii) the optimum solution for the
problem would always be such that there would be only one assignment in a given row or
column of the cost matrix.

2. In assignment problem if a constant is added or subtracted from every element of any row
or column in the given cost matrix then an assignment that minimizes the total cost in one
matrix also minimizes the total cost in the other matrix.

3.2.2. Hungarian Assignment 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. It is shown in figure 6.1 and discussed here. 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 itself and add this element to each value located

16

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

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

17

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

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
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
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
D 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. This is the optimal solution to the
problem-the same as obtained by enumeration and transportation methods.
Example
Using the following cost matrix, determine (a) optimal assignment, and (b) the cost of
assignments.

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

18

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

E 9 10 9 6 10

Iteration 1: Obtain row reductions.

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

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.

19

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

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

3.2.3. Special Issues

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.

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

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

20

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

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
person
P1 27 18 X 20 21
P2 31 24 21 12 17
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.

Job
J1 J2 J3 J4 J5
P1 27 18 M 20 21
person

P2 31 24 21 12 17
P3 20 17 20 M 16
P4 22 28 20 16 27
P5 0 0 0 0 0
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. Since the
number of lines covering all zeros is less than n, we select the lowest uncovered cell,
which equals 4. With this value, we can obtain the revised reduced cost table, shown in
the final table.

Reduced Matrix
Job
J1 J2 J3 J4 J5
P1 9 0 M 2 3
person

P2 19 12 9 0 5
P3 4 1 44 M 0
P4 6 12 4 0 11
P5 0 0 0 0 0
dummy
Reduced Matrix
Job
person

J1 J2 J3 J4 J5
P1 9 0 M 2 3
P2 19 12 9 0 5

21

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

P3 4 1 4 M 0
P4 6 12 4 0 11
P5 0 0 0 0 0
dummy

Assignment of Job
Job
J1 J2 J3 J4 J5
P1 9 0 M 2 3
person

P2 15 8 9 0 1
P3 4 1 4 M 0
P4 2 8 0 0 X 7
P5 0 0X 0X 0 0 X
dummy

The number of lines covering zeros is equal to 5(=n), hence the optimal assignment can
be made. The assignment is: P1-J2, P2-J4, P3-J5, P4-J3, while job J1 would remain
unassigned. This assignment pattern would cost 18+12+16+20=66 in the aggregate.
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 wherein the
various rows and 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.

22

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

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.

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.

23

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

Further, the 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.
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

24

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

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

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

Steps 4, 5, 6: Find improved solution. Test for optimality and make assignments.

25

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

Reduced cost Table 3

District
Salesman D1 D2 D3 D4 D5
S1 12 0 0 X 7 0 X

S2 0 10 8 10 0 X
S3 0 X 8 4 2 0
S4 23 1 0 0 X 5
S5 15 5 0 X 0 1

More than one optimal assignment is possible in this case because of the existence of
multiple zeros in different rows and columns. The possible assignments are:
S1-D2, S2-D5, S3-D1, S4-D3, S5-D4; or
S1-D2, S2-D1, S3-D5, S4-D3, S5-D5; or
S1-D2, S2-D1, S3-D1, S4-D4, S5-D3; or
S1-D2, S2-D1, S3-D5, S4-D4, S5-D
Each of these assignment patterns would lead to expected aggregated sales equal to 231
thousand birr.

26

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

START

Write the problem in

tabular form

Is it a Add dummy
No
balanced row(s)/column(s)
problem?

Yes

Convert it into a maximization

problem, either by changeling
Is it a the signs of the elements of the
Yes
maximum signs of the elements of the
problem? table; or by subtracting all the
values from the largest value.
No
Obtain reduced cost tables.
i.Subtract from all entries in each
row the least value in the row.
ii.From this table, subtract from all
entries column the least value in
the column.

Improve the solution. For this:

i. Select the minimum of the uncovered
Can all zeros (by lines) cell values.
be covered Yes ii. Subtract this value from all uncovered
by less than n cell values.
lines? iii. Add this value to the cells lying on the
intersection of any pair of lines.
iv. Leave the cell values covered by only
No one undisturbed.
Make assignments on
one-to-one match basis
considering zeros in
rows/columns

STOP

Fig. Schematic Presentation of Hungarian Assignment Method.

27

Downloaded by Amanuel Markos ([email protected])

 lOMoARcPSD|23226106

Summary
 The purpose of using an LP model for transportation problems is to minimize
transportation costs, taking into account the origin supplies, the destination
demands, and the transportation costs
 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.
 For allocation 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
 A number of different approaches can be used to find an initial feasible solution.
Which include:
The northwest-corner method.
An intuitive approach/Least cost method
Vogel‟s / Penalty Method
 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. Two methods for cell evaluation:
The Stepping-stone method
The MODI method
 The Assignment Problem (A.P.) is a special case of Transportation Problem (T.P.)
in which the number of sources and destinations are the same, and the objective is to
assign the given job (task) to most appropriate machine (person) so as to optimize
the objective like minimizing cost.

28

Downloaded by Amanuel Markos ([email protected])