Assignment Problems

Problem 1.
Let us consider an example where 4 jobs have to be
assigned to four persons. The cost of assigning job j to
resource i is given in following table .
Persons 
1 2 3 4
Jobs 
J1 5 9 3 6
J2 8 7 8 2
J3 6 10 12 7
J4 3 10 8 6

• A feasible solution to the assignment is x11=x22=x33=x44=1

where the first person gets job 1 and so on.
• The cost of the assignments is 5 + 7 + 12 + 6 = 30
 Problem 1. (Solution)
• Optimum solution is obtained as:
• x13=3, x24=2, x32=10 and x41=3
• Z=3+2+10+3
• Z= Rs. 18 /-
 Problem 2.
Let us consider an example where 5 jobs have to be
assigned to five persons. The cost of assigning job j to
resource i is given in following table .

Persons 
1 2 3 4 5
Jobs 

J1 11 7 10 17 10
J2 13 21 7 11 13
J3 13 13 15 13 14
J4 18 10 13 16 14
J5 12 8 16 19 10
 We define procedure that helps us verify whether we have
reached the maximum number of assignments possible
for the given non negative cost matrix with at least one
zero in every row and column having assignments

Determining the maximum number of assignments possible

Step 1 : Tick all unassigned rows.
Step 2 : If a row is ticked and has a zero, then tick the
corresponding column (if the column is not yet ticked)
Step 3 : If a column is ticked and has an assignment, then tick
the corresponding row (if the row is not yet ticked)
Step 4 : Repeat Steps 2 and 3 till no more ticking is
possible.
Step 5: Draw lines through unticked rows and ticked
columns. The number of lines represent the maximum
number of assignments possible.
Procedure (creating a new assignment matrix)

– Indentify the minimum number (say ) that have no

lines passing through them

– Update the Cij matrix using the following changes:

Cij = Cij -  if the number has no lines passing through it.
Cij = Cij if the number has one lines passing through it (No change).
Cij = Cij +  if the number has two lines passing through it.
 Problem 2. (Solution)
• Optimum solution is obtained as:
• x11=11, x23=7, x34=13, x42=10 and x55=10
• Z=11+7+13+10+10
• Z= Rs. 51 /-
 Problem 3.
Let us consider an example where 4 jobs have to be
assigned to four persons. The cost of assigning job j to
resource i is given in following table .

Persons 
1 2 3 4
Jobs 
J1 3 1 1 4
J2 4 2 2 5
J3 5 3 4 8
J4 4 2 5 9
 Problem 3. (Solution)
Optimum assignment Alternate Optimum assignment
1 J4 4 1 J3 1
2 J3 2 2 J4 5
3 J2 3 3 J1 5
4 J1 4 4 J2 2
Optimum (Minimum) cost Alternate Optimum (Minimum) cost
= 4 + 2 + 3 + 4 = Rs. 13/- = 1 + 5 + 5 + 2 = Rs. 13/-
 Problem 4.
A car hire company has one car at each of five depots a,
b, c, d and e. A customer requires a car in each town,
namely A, B, C, D and E. Distance (in kms) between
depots(origins) and towns (destinations) are given in the
following distance matrix:
a b c d e
A 160 130 175 190 200
B 135 120 130 160 175
C 140 110 155 170 185
D 50 50 80 80 110
E 55 35 70 80 105
How should car be assigned to customers so as to
minimize the distance travelled?
 Problem 4. (Solution)
• Optimum solution is obtained as:
• From original matrix table the minimum
distance assignment is given by
Total
Route A-e B-c C-b D-a E-d Distance
Travelled
Distance
200 130 110 50 80 570 Kms.
(Kms.)
Unbalanced Assignment
Problems
 Problem 5.
A city corporation has decided to carry out road repairs on main four arteries of the
city. The government has agreed to make a special grant of Rs. 50 lakhs towards the
cost with a condition that the repairs must be done at the lowest cost and quickest
time. If conditions warrant, then a supplementary token grant will also be
considered favourably. The corporation has floated tenders and 5 contractors have
sent in their bids. In order to expedite work, one road will be awarded to only one
contractor
COST OF REPAIRS (RS. LAKHS)
R1 R2 R3 R4
C1 9 14 19 15
C2 7 17 20 19
Contractors / Road C3 9 18 21 18
C4 10 12 18 19
C5 10 15 21 16

(i) Find the best way of assignment the repair work to the contractors and the costs.
(ii) If it is necessary to seek supplementary grants, then what should be amount
sought?
(iii) Which of the five contractors will be unsuccessful in his bid?
 Problem 5. (Solution)
(i)

Contractors / Total
R1C2 R2C4 R3C1 R4C5 R5C3
Road cost

COST OF REPAIRS
7 12 19 16 0 54
(RS. LAKHS)

(ii) Since the costs exceeds 50 lakhs, the excess

amount of Rs. 4 lakhs (54 lakhs – 50 lakhs) is to be
sought as supplementary grant
(iii) Contractor C3 who has been assigned the
dummy column (Road R5) loses out in the bid.
 Problem 6.
There are four jobs to be assigned to five machines. Only one
job can be assigned to one machine. The amount of time in
hours required for the jobs per machine are given in the
following matrix.
Machines
Jobs
A B C D E
1 4 3 6 2 7
2 10 12 11 14 16
3 4 3 2 1 5
4 8 7 6 9 6
Find an optimum assignment of jobs to the machines to
minimize the total processing time and also find out for which
machine no job is assigned. What is the total processing time
to complete all the jobs?
 Problem 6. (Solution)
Optimum assignment Alternate Optimum assignment
1 B 3 1 B 3
2 A 10 2 A 10
3 D 1 3 D 1
4 C 6 4 E 6
5 E 0 5 C 0
For machine D, no job is assigned For machine C, no job is assigned

Optimum (Minimum) cost Alternate Optimum (Minimum) cost

= 3 + 10 + 1 + 6 + 0 = Rs. 20/- = 3 + 10 + 1 + 6 + 0 = Rs. 20/-
Maximization in Assignment
Problems
 Problem 7.
A company has 5 jobs to be done. The following matrix
shows the return in rupees on assigning ith (i=1,2,3,4,5)
machine to the jth job (j=A,B,C,D,E). Assign the five jobs to
the five machines so as to maximize the total expected
profit.
Jobs
Machines
A B C D E
1 5 11 10 12 4
2 2 4 6 3 5
3 3 12 5 14 6
4 6 14 4 11 7
5 7 9 8 12 5
 Problem 7. (Solution)
Optimum assignment
1 C 10
2 E 5
3 D 14
4 B 14
5 A 7
Optimum (Maximum) Profit = 10 + 5 + 14 + 14 + 7 = Rs. 50/-
 Problem 8.
A company has four territories open, and four salesmen available for assignment. The
territories are not equally rich in their sales potential; it is estimated that a typical
salesman operating in each territory would bring in the following annual sales:

Territory I II III IV
Annual sales (Rs.) 60,000 50,000 40,000 30,000

Four salesmen are also considered to differ in their ability : it is estimated that,
working under the same conditions, their yearly-sales would be proportionately as
follows

Salesman A B C D
Proportion 7 5 5 4

If the criterion is maximum expected total sales, then intuitive answer is to assign
the best salesman to the richest territory, the next best salesman to the second
richest, and so on. Verify this answer by the assignment technique.
 Problem 8. (Solution)
Sales matrix for maximization is obtained as follows:
Sales in 10 thousand of rupees
6 5 4 3
Sales proportion  I II III IV
7 A 42 35 28 21
5 B 30 25 20 15
5 C 30 25 20 15
4 D 24 20 16 12

Optimum assignment Alternate Optimum assignment

A I A I
B II B III
C III C II
D IV D IV
Both the solution show that the best salesman A is assigned to the richest territory
I, the worst salesman D to the poorest territory IV. Salesman B and C being
equally good, so they may be assigned to either II or III. This verifies the answer
Travelling-salesman (Routing)
problems
 Problem 9.
A salesman wants to visit A, B, C, D and E. He does not
want to visit any city twice before completing his tour of
all the cities and wishes to return to the point of starting
journey. Cost of going from one city to another in Rs is
shown in the table. Find the least cost route.

A B C D E
A ∞ 2 15 7 4
B 4 ∞ 3 8 2
C 6 7 ∞ 4 9
D 8 9 8 ∞ 6
E 4 3 2 8 ∞
 Problem 9. (Solution)
Optimum assignment
A B 2
B E 2
E C 2
C D 4
D A 8
Optimum cost = 2 + 2 + 2 + 4 + 8 = Rs 18/-
 Problem 10.
Solve the following travelling salesman problem given the
following data: c12=20, c13=4, c14=10, c23=5, c24=6, c25=10,
c35=6 and c45=20 where cij=cji and there is no route
between cities i and j if a value of cij is not given
 1 2 3 4 5
1 ∞ 20 4 10 ∞
2 20 ∞ 5 6 10
3 4 5 ∞ ∞ 6
4 10 6 ∞ ∞ 20
5 ∞ 10 6 20 ∞
 Problem 10. (Solution)
Optimum assignment Alternate Optimum assignment
1 3 4 1 4 10
3 5 6 4 2 6
5 2 10 2 5 10
2 4 6 5 3 6
4 1 10 3 1 4
Optimum (Minimum) cost Alternate Optimum (Minimum) cost
= 4 + 6 + 10 + 6 + 10 = Rs. 36/- = 10 + 6 + 10 + 6 + 4 = Rs. 36/-
 Problem 11.
A machine operator processes 5 jobs each week and
must choose a sequence for them. The table gives the
changeover cost. Suggest the best sequence which
minimizes the total change over cost.

A B C D E
A ∞ 2 5 7 1
B 6 ∞ 3 8 2
C 8 7 ∞ 4 7
D 12 4 6 ∞ 5
E 1 3 2 5 ∞
 Problem 11. (Solution)
Optimum assignment
A B 2
B C 3
C D 4
D E 5
E A 1
Optimum cost = 2 + 3 + 4 + 5 + 1 = Rs 15/-