Unit IV:- Assignment problem: Definition, unbalanced assignment problem, Theorems related to the solution

of an assignment problem, solution method, maximization in an assignment problem, restriction on

assignment.
Game Theory: Definition, two-person zero-sum game, pay-off matrix, minimax and maximin principle, pure-
strategy, the value of a game, saddle point, solution of a game with a saddle point.

Assignment problem

The assignment problem is a special case of a transportation problem in which the

objective function is to assign a number of origins to an equal number of destinations at a
minimum cost ( or the total value is maximized when payoffs are given in terms of, say, profits).
An assignment is a problem because people possess varying abilities for performing different
jobs and therefore, the costs of performing those jobs by different people are different.
Obviously, if all persons could do a job at the same time or the same cost then it would not
matter who among them is assigned the job.

The assignment problem is a completely degenerate form of transportation problem. The

units available at each origin and units demanded at each destination are equal to one. That
means exactly one occupied cell in each row and each column of the transportation table i.e. only
n occupied cells in place of the required n + n – 1 = 2n - 1.

Mathematical formulation of the Assignment Problem

Consider a problem of assignment of n jobs to n machines. To minimize the overall cost

or time in such a way that each job can associate with one and only one machine. The cost
Matrix Cij is given as under

j Number of Destinations
Availability
i 1 2 3 …….. j …….. n
1 C11 C12 C13 …….. C1j …….. C1n 1
2 C21 C22 C23 …….. C2j …….. C2n 1
3 C31 C32 C33 …….. C3j …….. C3n 1
. . . . . . . .
Number 1
. . . . . . . .
of
i Ci1 Ci2 Ci3 …….. Cij …….. Cin 1
Origins
.
. . . …….. . . .
. 1
. . . …….. . . .
n Cn1 Cn2 Cn3 …….. Cnj …….. Cnn 1
Requirement 1 1 1 1 1 1 1
 This cost Matrix is the same as that of the transportation problem except that availability
at each of the resources and the requirement at each destination is unity (due to the fact that
assignments are made on a one to one basis)

Let xij denote the assignment of ith job to jth machine such that

xij = 1 if is ith job is assigned to jth machine

= 0 Otherwise.

Since only one job is to be assigned to each machine we must have

∑ ∑

Then the mathematical formulation of the assignment problem is

∑∑

s.t

Where xij = 0 or 1 i= 1,2, …..,n j= 1,2, …..,n

Theorem 1:- (Reduction Theorem) In an assignment problem if we add or subtract a constant

to every element of any row or column of the cost Matrix Cij then an assignment that minimizes
the total cost on one matrix also minimizes the total cost on the other matrix. In other words
if xij = xij* Minimizes ∑ ∑ ∑ ∑ xij = 0 or 1 then
xij = xij* also Minimizes ∑ ∑ where Cij* = Cij ± Ui ± Vj for all i and j and
Ui and Vj are some real numbers
Proof:- Given xij = xij* Minimizes total cost ∑ ∑

overall xij such that

∑ ∑ ; xij = 0 or 1

To show that :- xij = xij* also minimizes new total ∑ ∑

Consider ∑ ∑ =∑ ∑ ( )

∑∑ ∑ ∑ ∑ ∑ ∑ ∑

Since ∑ ∑

∑ and ∑ are fixed numbers that are independent of xij. Therefore the minimum value
of Z* is obtained when the minimum of Z is obtained and vice versa. Thus Min Z* is obtained
when xij = xij*. Hence the theorem.

Theorem 2:- If Cij ≥ 0 such that Min ∑ ∑ then xij = xij* provides an optimum
solution.

Proof:- Given that Cij ≥ 0 for all i, j

Also xij = 0 or 1 ∑ ∑

If we have xij = xij* in such a way that

Then we have ∑ ∑

which is the minimum possible value of the cost of assignment hence the solution given in
equation (1) is the optimum solution giving ∑ ∑

Note:- The above two theorems form the basis of the assignment algorithm. By selecting a
suitable constant to be added or to be subtracted from the elements of the cost matrix, we can
ensure that each Cij* ≥ 0 and can produce at least one Cij* = 0 in each row and each column and
try to make an assignment from among these 0 positions. The assignment is optimal if there
exists exactly one assignment i.e exactly one assigned zero in each row and each column.

The assignment method

An efficient method for solving an assignment problem is as follows. (The method is

known as the Hungarian assignment method)

1) Determine the cost table from the given table.

2) If the number of resources and destinations are equal i.e. if the assignment problem is
balanced then go to step number 4.
3) If the assignment problem is unbalanced then add the dummy source or dummy
destination so that the cost table becomes a square matrix. The cost entries of dummy
source or destination are always zero.
4) Locate the smallest element in each row of the given cost matrix and then subtract the
same from each element of the row.
5) In the reduced matrix obtained in step number four locate the smallest element of each
column and then subtract the same from each element of that column. Each column and
row now have at least one zero.
6) In the modified matrix obtained in step number 5, search for an optimal solution as
follows.
A) Examine the rows successively until a row with a single 0 is located. Enrectangle
this zero and cross off all other zeros in its column. Continue in this manner until all the
rows have been taken care of.

B) Repeat the procedure for each column of the reduced matrix.

C) If a row or column has two or more zeros and one cannot be chosen by inspection
then assign arbitrarily any one of these zeros and cross off all other zeros of that row or
column.

D) Repeat steps (A) through (C) above successively until the chain of assigning ends.

7) If the number of assignments (Enrectangle zeros) is equal to n then an optimum solution

is reached.
 8) If the number of assignments (Enrectangle zeros) is less than n then go to the next step.

9) Draw the minimum number of horizontal and vertical lines to cover all the zeros of the
reduced Matrix using the following procedure.

A) Mark (√) the row that does not have any assigned zero.

B) Mark (√) the column that has zeros in the mark rows.

C) Mark (√) rows that have assigned zero in the marked column.

D) Repeat steps (B) and (C) above until the chain of marking is complete.

E) Draw lines through all the unmarked rows and marked columns.

10) Develop the new revised matrix as follows.

A) Find the smallest element of the reduced matrix not covered by any of the lines.

B) Subtract this element from all the uncovered elements and add the same to all the
elements lying at the intersection of any two lines.

11) Go to step number (6) and repeat the procedure until an Optimum solution is attained

Example 1: A production supervisor is considering how he should assign the four jobs that are to
be performed, to four of the workers. He wants to assign the jobs to the workers such that the
cost of the assignment is the least. The cost matrix is given in the table:

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 smallest element in each row of the given cost matrix is subtracted from each element of the
row. The resultant reduced cost table is
 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

The smallest element in each column of the reduced matrix is subtracted from each element of
the column. The resultant reduced cost table is

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

Examine the rows successively until a row with a single 0 is located. Enrectangle this zero and
cross off all other zeros in its column. Continue in this manner until all the rows have been taken
care of.

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

Also, the number of assignments (Enrectangle zeros = 4) is equal to n = 4. Thus an optimum

solution is reached and is given by

The final pattern of assignments is 1-B, 2-D, 3-C and 4-A

The optimum total cost of the assignment is 40+55+48+41=184 ( as taken from the original
table).
Example 2: The cost of the assignment is given in the table. Find the optimum cost of the
assignment.

Job
Worker A B C D E
1 160 130 175 190 200
2 135 120 130 160 175
3 140 110 155 170 185
4 50 50 80 80 110
5 55 35 70 80 105

The smallest element in each row of the given cost matrix is subtracted from each element of the
row. The resultant reduced cost table is

Job
Worker A B C D E
1 30 0 45 60 70
2 15 0 10 40 55
3 30 0 45 60 75
4 0 0 30 30 60
5 20 0 35 45 70

The smallest element in each column of the reduced matrix is subtracted from each element of
the column. The resultant reduced cost table is

Job
Worker A B C D E
1 30 0 35 30 15
2 15 0 0 10 0
3 30 0 35 30 20
4 0 0 20 0 5
5 20 0 25 15 15
Examine the rows successively until a row with a single 0 is located. Enrectangle this zero and
cross off all other zeros in its column. Continue in this manner until all the rows have been taken
care of
 Job
Worker A B C D E
1 30 0 35 30 15
2 15 10 0

3 30 35 30 20

4 0 20 0 5

5 20 25 15 15
Repeat the procedure for each column of the reduced matrix.

Job
Worker A B C D E
1 30 0 35 30 15
2 15 0 10
3 30 35 30 20

4 0 20 5

5 20 25 15 15

Here the number of assignments (Enrectangle zeros = 3) is less than n = 5. Hence given
solution is not optimum.

For the revised matrix, Draw the minimum number of horizontal and vertical lines to
cover all the zeros of the reduced Matrix using the following procedure.

A) Mark (√) the row that does not have any assigned zero.

B) Mark (√) the column that has zeros in the mark rows.

C) Mark (√) rows that have assigned zero in the marked column.

D) Repeat steps (B) and (C) above until the chain of marking is complete.

E) Draw lines through all the unmarked rows and marked columns.
 Job
Worker A B C D E
1 30 0 35 30 15 √
2 15 0 10
3 30 35 30 20 √

4 0 20 5
5 20 25 15 15 √
√

Develop the new revised matrix as follows.

A) The smallest element of the reduced matrix not covered by any of the lines is 15.

B) Subtract this element from all the uncovered elements and add the same to all the
elements lying at the intersection of any two lines.

Job
Worker A B C D E
1 15 0 20 15 0
2 15 15 0 10 0
3 15 0 20 15 5
4 0 15 20 0 5
5 5 0 10 0 0
Examine the rows successively until a row with a single 0 is located. Enrectangle this zero and
cross off all other zeros in its column. Continue in this manner until all the rows have been taken
care of

Job
Worker A B C D E
1 15 20 15 0

2 15 15 0 10
3 15 0 20 15 5
4 0 15 20 5
5 5 10 0
Here n = 5

Also, the number of assignments (Enrectangle zeros = 5) is equal to n = 5. Thus an optimum

solution is reached and is given by

The final pattern of assignments is 1-E, 2-C, 3-B, 4-A and 5-D

Optimum total cost of assignment is 200 + 130 + 110 + 50 + 80 = 570 ( as taken from the
original table).

Unbalanced Assignment Problem:- If the cost matrix of an assignment problem is not a square
matrix i.e. number of origins is not equal to the number of destinations then the assignment
problem is called an Unbalanced assignment problem. In such a case, a dummy row or column
is added to the matrix to form a square matrix.
If the number of rows is less than the number of columns then the dummy row will be
added to the matrix and if the number of columns is less than the number of rows then the
dummy column will be added to the matrix to make it a balanced assignment problem. The cost
associated with the dummy row or column will be zero. Then the usual assignment algorithm can
be applied to this resulting balanced assignment problem.
e.g.

j
Number of Destinations
i 1 2 3 4
1 19 30 50 7
Number of
Origins 2 70 30 40 9
3 40 8 70 10

Here number of rows (3) < number of columns (4)

Therefore dummy row will be added to the cost matrix with zero cost to make a balanced
assignment problem.
 j
Number of Destinations
i 1 2 3 4
1 19 30 50 7
Number of 2 70 30 40 9
Origins 3 40 8 70 10
4 0 0 0 0
Now the usual assignment algorithm can be applied to this resulting balanced assignment
problem.
Variations of the Assignment Problem
1) The Maximal Assignment problem
The assignment problem can be of Minimization type or Maximization type.
A Minimization assignment problem involves cost or time data. The objective of the solution is
to minimize the total cost.
A Maximization assignment problem involves sales, revenue, or profit data.
The objective of the solution is the maximization of total sales, revenue, or profit. The steps to
solve are as follows.
1) Convert the Maximization problem to the Minimization problem.
2) From the original element values, find out the highest element value.
3) From this highest element, subtract all element values or equivalently by placing minus
sign before each element of the original profit matrix to make it a cost matrix.
4) Solve it as a normal assignment problem.
Note:- But for calculating the final schedule, you must multiply the quantity by the original
profit value and not by cost value.
Example: A manufacturing company has five Machines - 1, 2, 3, 4, and 5. The following
the matrix shows the return in rupees on assigning ith machine to jth job. Assign the five
jobs to the five machines to maximize the returns.
 Jobs
Machines
A B C D E

1 5 11 10 12 4

2 2 4 9 3 6

3 3 12 5 14 6

4 6 14 4 11 7

5 7 9 8 12 5

To Convert the Maximization problem to the Minimization problem: Highest return value is 14.
So subtracting all the elements from 14 the reduced cost matrix is

Jobs
Machines
A B C D E

1 9 3 4 2 10

2 12 10 5 11 9

3 11 2 9 0 8

4 8 0 10 3 7

5 7 5 6 2 9

Solve it as a normal assignment problem.

OR

Equivalently by placing a minus sign before each element of the original profit matrix to make it
a cost matrix. i.e.
 Jobs
Machines
A B C D E

1 - 5 - 11 - 10 - 12 - 4

2 - 2 - 4 - 9 - 3 - 6

3 - 3 - 12 - 5 - 14 - 6

4 - 6 - 14 - 4 - 11 - 7

5 - 7 - 9 - 8 - 12 - 5

Solve it as a normal assignment problem.

2) Restrictions on assignment problem

Sometimes technical, legal, or other restrictions do not allow the assignment of a

particular machine to a particular job. Such a situation can be overcome by assigning a very high
cost (say, infinite cost) to the corresponding cell, so that that the particular assignment will be
automatically excluded from the optimal solution.

e.g. A shop has purchased 5 new machines of different types. There are 5 available locations in
the shop where a machine could be installed. Some of these locations are more desirable than
others for a particular machine due to some technical reasons. The estimated cost of assigning a
particular machine to a particular location is given below. Locations A, B, C, D, and E are not
considered for machines 1, 2, 3, 4, and 5 respectively. Find the optimal solution.

Location
Machines
A B C D E

1 - 10 25 25 10

2 1 - 10 15 2

3 8 9 - 20 10

4 14 10 24 - 15

5 10 8 25 27 -
 Since Locations A, B, C, D, and E are not considered for machines 1, 2, 3, 4, and 5
respectively, we assign a very high cost (say, infinite cost) to the corresponding cell. So that
that the particular assignment will be automatically excluded from the optimal solution. The
resultant cost matrix is

Location
Machines
A B C D E

1 ∞ 10 25 25 10

2 1 ∞ 10 15 2

3 8 9 ∞ 20 10

4 14 10 24 ∞ 15

5 10 8 25 27 ∞

Solve it as a normal assignment problem.