One of the major applications of the assignment models is in the travelling salesman problem. Let us say that a salesman has to visit n destinations. He starts from a particular city, visits destination once and then comes back to the city from where he started. Here the objective would minimise the time this salesman takes to visit all the destinations. The problem is to select that sequence which all the destinations are visited in such a manner that the time taken is minimised. This problem similar to the assignment problems already seen except that there is an additional restriction that salesman starting from a particular city, visits each destinations only once and returns to his city from he started.
FORMULATION OF TRAVELLING SALESMAN PROBLEM
Let us define the variables X_{jj} k as (notice constraint k has been added in addition to i and j already there)
where d_{ij }is the distance from city i to city j.
Example 6.3. A salesman has to visit five cities A, B, C, D and E. The intercity distances are tabulated below:
To From 
A 
B 
C 
D 
E 
A 
– 
12 
25 
26 
16 
B 
7 
– 
17 
19 
8 
C 
10 
11 
– 
19 
12 
D 
15 
18 
23 
– 
17 
E 
12 
14 
24 
26 
– 
‘The above distances in KM between two cities need not be same both ways.
Which route would you advise the salesman to take so that the total distance travelled by him is minimum, if the salesman starts from city A and has to come back to city ‘A’?
Sol. Step 1. Select the smallest element in each row and subtract it from every element of that row. Row reduction results in the following matrix.
To From 
A 
B 
C 
D 
E 
A 
– 
0 
13 
14 
4 
B 
0 
– 
10 
12 
1 
C 
0 
1 
– 
9 
2 
D 
0 
3 
8 
– 
2 
E 
0 
2 
12 
14 
– 
Step II. Select the minimum element in each column and subtract this element from every element in that column, we get
To From 
A 
B 
C 
D 
E 
A 
– 
0 
5 
5 
3 
B 
0 
– 
2 
3 
0 
C 
0 
1 
– 
0 
1 
D 
0 
3 
0 
– 
1 
E 
0 
2 
4 
5 
– 
Step III. Draw minimum number of lines to cover all the zeros.
To From 
A 
B 
C 
D 
E 
A 
– 
0 
5 
5 
3 
B 
0 
– 
2 
3 
0 
C 
0 
1 
– 
0 
1 
D 
0 
3 
0 
– 
1 
E 
0 
2 
4 
5 
– 
Since the number of lines = order of matrix (5), this gives the optimal solution.
Step IV. Making assignment in zero positions does not satisfy the constraints of the problem. He the following assignment are made by hit and trial.
To From 
A 
B 
C 
D 
E 
A 
– 
0 
5 
5 
3 
B 
0 
– 
2 
3 
0 
C 
0 
1 
– 
0 
1 
D 
0 
3 
0 
– 
1 
E 
0 
2 
4 
5 
– 
Optimal schedule is A → B,
B →C,
C → D,
D → E,
E → A
involving distance 12 + 17 + 19 + 17 + 12 = 77 km.
This route satisfies the travelling salesman problem.
Unbalanced Problems
Example 6.4. A transport corporation has three vehicles in three cities. Each of vehicles can be assigned to any of the four other cities. The distance differs from one city to the other as under.
1 
2 
3 
4 

A 
33 
40 
43 
32 
B 
42 
30 
31 
24 
C 
40 
31 
37 
31 
you are required
a) To assign a vehicle to a city in such a way that the total distance travelled is minimised.
b) Formulate a mathematical model of the problem.
Sol. Step I. Introduce a dummy vehicle in city D as the problem is not balanced and take 0 distances as follows.
1 
2 
3 
4 

A 
33 
40 
43 
32 
B 
42 
30 
31 
24 
C 
40 
31 
37 
31 
D 
0 
0 
0 
0 
Step II. Subtract the minimum element of each row from all the elements of that row. There is no need to subtract 0 from each column. The matrix is
1 
8 
11 
0 
18 
6 
7 
0 
9 
0 
6 
0 
0 
0 
0 
0 
Step III. Draw minimum number of lines to cover all zero. It can be seen that number of lines = 3, order of matrix = 4. Hence this is not an optimal solution and we have to take steps to increase number of zeros.
1 
8 
11 
6 
18 
6 
7 
0 
9 
0 
6 
0 
0 
0 
0 
0 
Step IV. Subtract the minimum uncovered element (1) from all the uncovered elements and adding it elements at the intersection point. Draw minimum number of lines to cover all the zeros we get
0 
7 
10 
0 
17 
5 
6 
0 
9 
0 
6 
1 
0 
0 
0 
1 
Now, number of lines = 4, and is equal to the order of the matrix hence, this matrix will provide an optimal solution.
Step V. Assignments can be made as shown below.
0 
7 
10 
0 
17 
5 
6 
0 
9 
0 
6 
1 
0 
0 
0 
1 
Step VI. Minimum distance can be worked out as follows.
City 
Vehicle 
Distance 
A 
1 
33 
B 
4 
24 
C 
2 
31 
D 
3 
0 
Total 
88 
(b) Formulation of LPP
x_{11} 33 
X_{12} 40 
x_{13} 43 
X_{14} 32 
X_{21} 42 
X_{22} 30 
X_{23} 31 
X_{24} 24 
X_{31} 40 
X_{32} 31 
X_{33} 37 
X_{34} 31 
X_{41} 0 
X_{42} 0 
X_{43} 0 
X_{44} 0 
Minimise Z = 33 x_{11} + 40 x_{12} + 43 x_{13} + 32 x_{14} + 42 x_{21} + 30 x_{22} + 31 x_{23} + 24 x_{24} + 40 x_{31} + 31 x_{32} + 37 x_{33} + 31 x_{34} + 0 x_{41} + 0 x_{42} + 0 x_{43} + 0 x_{44}
Subject to x_{11} + x_{12} + x_{13} + x_{14} = 1
x_{21} + x_{22} + x_{23}+ x_{24} = 1
x_{31} + x_{32} + x_{33} + x_{34} = 1
x_{41} + x_{42} + x_{43} + x_{44}= 1
x_{ij} ≥ 0.
Example 6.5Solve the following unbalanced assignment problem of minimising total time for doing all the jobs.
Operator 
Jobs 

1 
2 
3 
4 
5 

A 
8 
3 
6 
3 
7 
B 
3 
6 
9 
8 
8 
C 
9 
9 
7 
9 
8 
D 
7 
2 
3 
5 
6 
E 
10 
3 
8 
9 
7 
F 
5 
7 
4 
7 
8 
Sol. StepI. Introducing dummy job 6 to make the problem balanced allotting 0 timing.
Operator 

Jobs 

1 
2 
3 
4 
5 
6 

A 
8 
3 
6 
3 
7 
0 
B 
3 
6 
9 
8 
8 
0 
C 
9 
9 
7 
9 
9 
0 
D 
7 
2 
3 
5 
6 
0 
E 
10 
3 
8 
9 
7 
0 
F 
5 
7 
4 
7 
8 
0 
Step II. Since 0 is in each row, there is no need of row deduction, column deduction is done by subtracting the minimum element of each column from all the elements of that column, we have
Operator 

Jobs 

1 
2 
3 
4 
5 
6 

A 
5 
1 
3 
0 
1 
6 
B 
0 
4 
6 
5 
2 
0 
C 
6 
7 
4 
6 
3 
0 
D 
4 
0 
0 
2 
0 
0 
E 
7 
1 
5 
6 
1 
0 
F 
2 
5 
1 
4 
2 
0 
Draw minimum number of lines to cover all the zeros, since lines = 4 is less than the order of the matrix (6) this is not an optimal solution.
Step III. Subtracting the minimum uncovered element (1) from all uncovered elements and adding it to the elements of intersection points of the lines, we have
Operator 

Jobs 

1 
2 
3 
4 
5 
6 

A 
5 
1 
3 
0 
1 
1 
B 
0 
4 
6 
5 
2 
1 
C 
5 
6 
3 
5 
2 
0 
D 
4 
0 
0 
2 
0 
1 
E 
6 
0 
4 
5 
0 
0 
F 
1 
4 
0 
3 
1 
0 
Since number of linesdrawn (6) = order of matrix, this is the optimal solution,
Step IV. Assignments are made as shown below.
Operator 

Jobs 

1 
2 
3 
4 
5 
6 

A 
5 
1 
3 
0 
1 
1 
B 
0 
4 
6 
5 
2 
1 
C 
5 
6 
3 
5 
2 
0 
D 
4 
0 
0 
2 
0 
1 
E 
6 
0 
4 
5 
0 
0 
F 
1 
4 
0 
3 
1 
0 
Step V. Computing the minimum time.
Operator 
Job 
Time 
A 
4 
3 
B 
1 
3 
C 
6 
0 
D 
5 
6 
E 
2 
3 
F 
3 
4 
Total = 19 
Example 6.6. Four operators A, B, C and D are available to a manager who has to get four jobs J – I, J – 2, J – 3 and J – 4, done by assigning one job to each operator. Given the time needed by different operators for different jobs as per the following matrix.
J1 
J2 
J3 
J4 

A 
10 
8 
10 
9 
B 
12 
10 
14 
10 
C 
6 
8 
16 
6 
D 
8 
9 
7 
7 
How should the manager assign the jobs so that the total time needed for all four jobs is minimum?
Sol. Subtract the minimum element of each row from all the elements of that row, we have
Step I
J1 
J2 
J3 
J4 

A 
2 
0 
2 
1 
B 
2 
0 
4 
0 
C 
0 
2 
10 
0 
D 
1 
2 
0 
0 
Step II. Subtract the minimum element of each column from all elements of that column. Since all columns have zero, there will be no change in the matrix.
Step III. Draw minimum number oflines to cover all the zeros, the matrix is as follows.
J1 
J2 
J3 
J4 

A 
2 
0 
2 
1 
B 
2 
0 
4 
0 
C 
0 
2 
10 
0 
D 
1 
2 
0 
0 
As the number of lines (4) is equal to the order of matrix, this is the optimal solution.
Step IV. Making the assignments
J1 
J2 
J3 
J4 

A 
2 
0 
2 
1 
B 
2 
0 
4 
0 
C 
0 
2 
10 
0 
D 
1 
2 
0 
0 
Step V. Computing the minimum time
Operator 
Job 
Time 
A 
J2 
8 
B 
J4 
10 
C 
J1 
6 
D 
J3 
7 
Total = 31 
Example 6.7. A manufacturing company has four zones Z – 1, Z 2, Z – 1 and Z – 4 and four sales engineers A, B, C and D respectively for assignments. The zones are not equally rich in sales potential and it is estimated that a particular engineer operating in a particular zone will yield the following sales.
Z1 : 4,50,000
Z2 : 3,40,000
Z3 : 3,00,000
Z4 : 4,60,000
The engineers have different sales ability. Working under the same conditions their yearly sales are proportional to 15, 10, 12, 8 respectively. The criteria of maximum expected total sales is to be met by assigning the best engineer to the richest zone, the next best to the second richest zone and 5.0 on.
Find the optimal assignment and the maximum sales.
Sol. Step I. The revenue matrix is as shown below.
The matrix, after multiplications is reduced to
Z1 
Z2 
Z3 
Z4 

A 
150 
114 
100 
154 
B 
100 
75.5 (76) 
67 
102 
C 
120 
90.5 (91) 
80 
123 
D 
80 
60.5 (61) 
53.5 (54) 
82 
Step II. Now the problem can be reduced to minimisation i.e. loss matrix can be formulated by acting all elements from the largest value i.e., 154.
Z1 
Z2 
Z3 
Z4 

A 
4 
40 
54 
0 
B 
54 
78 
87 
52 
C 
34 
63 
74 
31 
D 
74 
93 
100 
72 
Subtract the minimum elements of each row from all elements of that row, we have
Z1 
Z2 
Z3 
Z4 

A 
4 
40 
54 
0 
B 
2 
26 
35 
0 
C 
3 
32 
43 
0 
D 
2 
21 
28 
0 
Step IV. Subtract the minimum element of each column from all elements of that column and draw minimum number of lines to cover all zeros, we get
Z1 
Z2 
Z3 
Z4 

A 
2 
19 
26 
0 
B 
0 
5 
7 
0 
C 
1 
11 
15 
0 
D 
0 
0 
0 
0 
Since there are 3 lines and order of matrix is four, this matrix does not provide .the optimal solution.
Step V. Subtract the minimum uncovered element (1) from all uncovered elements and add the elements at the intersection points of the lines and again draw minimum number of lines to cover all zeros.
Z1 
Z2 
Z3 
Z4 

A 
1 
18 
25 
0 
B 
0 
5 
7 
1 
C 
0 
10 
14 
0 
D 
0 
0 
0 
0 
Again there are 3 lines hence it is not optimal solution, so subtract the minimum uncovered element from all elements which are uncovered and add to the elements at the intersection points, we get
Z1 
Z2 
Z3 
Z4 

A 
1 
13 
20 
0 
B 
0 
0 
2 
1 
C 
0 
5 
9 
0 
D 
5 
0 
0 
6 
Now number of lines = order of matrix, so this will give us the optimal solution.
Step VI. Making the assignments in the usual manner, we have
Z1 
Z2 
Z3 
Z4 

A 
1 
13 
20 
0 
B 
0 
0 
2 
1 
C 
0 
5 
9 
0 
D 
5 
0 
0 
6 
Step VII. Computing the maximum sides
It can be seen from above assignments that the best engineer A has been assigned the richest zone Z – 4, the nextbest engineer C has been assigned the next richest zone Z – 1, and so on.
Example 6.8. MIS Steadfast Enterprise has four plants each of which can manufacture anyone of the four products. Product costs differ from one plant to another as follows:
Product
Plant 
P 
Q 
R 
S 
1 
33 
40 
43 
32 
2 
45 
28 
30 
23 
3 
42 
29 
35 
29 
4 
27 
42 
45 
38 
Find out which product each plant should produce to minimise cost. Also, formulate a LPP.
Sol. Step I. Subtracting the minimum element of each row from all the elements of that row.
1 
8 
11 
0 
12 
5 
7 
0 
13 
0 
6 
0 
0 
15 
18 
11 
Step II. Subtracting the minimum elements of each column of the above matrix from all the elements of that column.
1 
8 
5 
0 
12 
5 
1 
0 
13 
0 
0 
0 
0 
15 
12 
11 
Step III. Draw minimum number of lines (horizontal/vertical) to cover all the zero.
1 
8 
5 
0 
12 
5 
1 
0 
13 
0 
0 
0 
0 
15 
12 
11 
Since the number of lines, drawn is (3) less than the order of the matrix (4), we have to take steps to increase zeros and present solution is not optimal solution.
Step IV. Subtract the minimum uncovered element (1) from all the uncovered elements and add it to the elements at intersection point, we get the matrix.
0 
7 
4 
0 
11 
4 
0 
0 
13 
0 
0 
1 
0 
15 
12 
12 
Step V. Draw the minimum number of lines to cover all the zeros, we get
0 
7 
4 
0 
11 
4 
0 
0 
13 
0 
0 
1 
0 
15 
12 
12 
Since the number of lines drawn (4) is equal to the order of the matrix (4),the above matrix gives optimal solution.
Step VI. Select a row containing exactly one unmarked zero and put a ⎕ around it and draw a vertical line through the column containing this zero. Repeat this till no such row is left. Then select column containing exactly one unmarked zero and put a ⎕ around it and draw a horizontal line through the row containing this zero. Repeat this process till no such column is left.
P 
Q 
R 
S 

1 
0 
7 
4 
0 
2 
11 
4 
0 
0 
3 
13 
0 
0 
0 
4 
0 
5 
12 
12 
Step VII. Optimal assignment is
1 → S =32
2 → R=30
3 → Q=29
4 → P = 27
Minimum cost = 118
Formulation of LPP
x_{11} 33 
x_{12} 40 
x_{13} 43 
x_{14} 32 
x_{21} 45 
x_{22} 28 
x_{23} 30 
x_{24} 23 
x_{31} 42 
x_{32} 29 
x_{33} 35 
x_{34} 29 
x_{41} 27 
x_{42} 42 
x_{43} 45 
x_{44} 38 
Maximise Z = 33 x_{11} + 40 x_{12} + 43 x_{13} + 32 x_{14} +
45 x_{21} + 28 x_{22} + 30 x_{23} + 23 x_{24} +
42 x_{31} + 29 x_{32} + 35 x_{33} + 29 x_{34} +
27 x_{41} + 42 x_{42} + 45 x_{43} + 38 x_{44}
X_{11} + x_{12} + x_{13} + x_{14} = 1
x_{21} + x_{22}+ x_{23} + x_{24} = 1
x_{31} + x_{32} + x_{33} + x_{34} = 1
x_{41} + x_{42} + x_{43} + x_{44}= 1
x_{ij}≥ 0.
Example 6.9. A Company is faced with assigning 5 jobs to 5 operators. Each job must be performed by one operator. The cost of processing of each job by each operator is given below in Rs.
Operators
P 
Q 
R 
S 
T 

A 
7 
5 
9 
8 
11 

Jobs 
B 
9 
12 
6 
11 
10 
C 
8 
5 
4 
6 
8 

D 
7 
3 
6 
8 
5 

E 
5 
6 
7 
5 
11 
Determine the assignment of jobs to the operators so that it will result in minimum cost.
Sol. Step I. Select the minimum element in each row and subtract the is element from every other element in that row.
P 
Q 
R 
S 
T 

A B C D E 
2 3 4 4 0 
0 6 1 0 1 
4 0 0 3 2 
3 5 2 5 0 
6 4 4 2 6 
Step II. Now select the minimum element in each column and subtract this element from every other element in tat row element of that column, we get the following matrix.
P 
Q 
R 
S 
T 

A B C D E 
2 3 4 4 0 
0 6 1 0 1 
4 0 0 3 2 
3 5 2 5 0 
4 2 2 0 4 
Step III. In row A, there is a single zero so assignment is made in cell AQ. In row B, there is a single zero, so assignment is made in cell BR. While making assignment in row AQ, the other zero appearing in the column Q i.e., in element DQ is crossed out. Similarly when assignment is made in row B in cell BR, the other zero in column R i.e., in cell CR is crossed out.
While inspecting rows, row D has a single zero, assignment can be made in cell DT. No assignment can be made in row E, since it has two zeros.
Now inspect columns, column P has single zero, so assignment can be made in cell EP and other zero in row E i.e., in cell ES can be crossed out.
Since it is possible only to make 4 assignments against 5, so optimum solution is not reached. Number of lines drawn is equal to the number of assignments made.
Step IV. Examine the elements not covered by the lines and select the smallest element, in this ease 2 and subtract this from all the uncovered elements and add this to the elements lying at the intersection of the two lines. This gives us the following matrix.
Step V. Make assignment in row C where there is a single zero. Hence assignment in cell CS is made. Step VI. Optimum solution
A → Q=5
B → R=6
C → S=6
D → T=5
E → P=5
Minimum Total cost = Rs 27.
Example 6.10. The following is the cost matrix of assigning 4 professors to 4 key courses. Class preparation time in hours for different topics varies from professor to professor and is given in the table below. Each professor is assigned only one course so as to minimise the total preparation time for all courses.
Professor 
Courses 

C_{1} 
C_{2} 
C_{3} 
C_{4} 

A B C D 
2 15 13 4 
10 4 14 15 
9 14 16 13 
7 8 11 9 
Sol. Step I. Select minimum element’ from each row and subtract it from other elements of that row, we get
Courses
C_{1} 
C_{2} 
C_{3} 
C_{4} 

Professors 
A B C D 
0 11 2 0 
8 0 3 11 
7 10 5 9 
5 4 0 5 
Step II. Select minimum element from each column and subtract it from other elements of that column.
Courses
C_{1} 
C_{2} 
C_{3} 
C_{4} 

Professors 
A B C D 
0 11 2 0 
8 0 3 11 
2 5 0 4 
5 4 0 5 
Step III. In first row, as there is a single zero, assignment can be made in cell AC_{1} and crossing out other zeros in column C_{1}. In second row assignment can be made in cell 8C_{2}, as there is a single zero. Similarly, assignment can be made in cell CC_{3} as follows.
Courses
C_{1} 
C_{2} 
C_{3} 
C_{4} 

Professors 
A B C D 
0 11 2 8 
8 0 3 11 
2 5 0 4 
5 4 0 5 
As the number of assignment is less than the order of matrix, we have to proceed further as it is not the optimum solution. Also, draw minimum lines to cover all the zeros, we have
Courses
C_{1} 
C_{2} 
C_{3} 
C_{4} 

Professors 
A B C D 
0 11 2 0 
8 0 3 11 
2 5 0 4 
5 4 0 5 
Step IV. Select the minimum numberout of the uncovered elements (2) subtract it from the uncovered elements and add to the elements at the intersection of lines, we get
Courses
C_{1} 
C_{2} 
C_{3} 
C_{4} 

Professors 
A B C D 
0 13 4 0 
6 0 3 9 
0 5 0 2 
3 4 0 3 
Step V. Make fresh assignments
Now the number of assignments is equal to the order of the matrix hence, this is the optimal solution.
Professor 
Course 
Time 
A 
C_{3} 
9 
B 
C_{2} 
4 
C 
C_{4} 
11 
D 
C_{1} 
4 
Total minimum course duration = 28 minutes
Ex. 6.11. In a modification of plant layout of a factory four new machines are to be installed in a machine shop. There are five vacant sheds A, B, C, D & E available. Because of limited space machine 2 cannot be placed at C and M_{3} cannot be placed at A. The cost is shown below. Find optimum assignment schedule.
A 
B 
C 
D 
E 

M_{1} M_{2} M_{3} M_{4} 
9 12 – 14 
11 9 11 8 
15 – 14 12 
10 10 11 7 
11 9 7 8 
Cost.
M_{1} is given A = 9
M_{2} is given B = 9
M_{3} is given E = 7
M_{4} is given D = 7
M_{5} is given C = 0
Total = 32
As the no of lines equals the assigned zero, optimal solution has been obtained.
Example 6.12. Consider a problem of assigning four clerks to four tasks. The time required is give below.
A 
B 
C 
D 

Clerks 
1 2 3 4 
4 – 3 6 
7 8 – 6 
5 7 5 4 
6 4 3 3 
Clerk 2 cannot be assigned to task A and clerk 3 cannot be assigned to task B. Find all the optimum assigned schedules.
Sol. The procedure is same as of earlier example.
Subtracting the minimum element of each row from all its elements we get
1 – B
2 – D
3 – A
4 – C
7 + 4 + 3 + 4 = 18.
Example 6.13. A national car rental service has a surplus of one car in each of the cities 1, 2, 3, 4, 5 and 6 and a deficit of one car in each of the cities 7, 8, 9, 10, 11, 12. The distance in miles between cities with a surplus and cities with a deficit are displayed in the table below. How’ should the. cars be dispatched so as to minimise total mileage travelling?
7 
8 
9 
10 
11 
12 

1 2 3 4 5 6 
41 22 27 45 29 82 
72 29 39 50 40 40 
39 49 60 48 39 40 
52 65 51 52 26 60 
25 81 32 37 30 51 
51 50 32 43 33 70 
Sol. Row Reduction
7 
8 
9 
10 
11 
12 

1 2 3 4 5 6 
16 0 0 8 3 42 
47 7 12 13 14 0 
14 27 33 11 13 0 
27 43 24 15 0 20 
0 59 5 0 4 11 
26 28 5 6 7 30 
Column Reduction &making assignments
The number of lines is less than the number of assignment.
Further Reduction will take place.
The smallest element will be subtracted from all the values from that particular element and added where two lines intersect and elements on line will remain same.
Still the no. of lines is 5 as against required 6.
Second Reduction will take place;
Row Reduction
7 
8 
9 
10 
11 
12 

1 2 3 4 5 6 
16 0 0 8 3 49 
47 7 12 13 14 0 
14 27 33 11 13 0 
27 43 24 15 0 20 
0 59 5 0 4 11 
26 28 5 6 7 30 
Column Reduction & making assignments
Now mark the unmarked row which is Row IVth. See the marked zero in that column. Draw lines on rest of the rows.
1 11 = 25
28= 2
37=27
412=43
5 – 10 = 26
69 = 40
Total = 190
Ex. 6.14. Five lathes are to be allotted to five operators, the following table gives weekly output figures.
L_{1} 
L_{2} 
L_{3} 
L_{4} 
L_{5} 

Operator 
P Q R S T 
20 19 23 21 24 
22 23 28 24 28 
27 29 35 31 31 
32 34 39 37 36 
36 40 34 42 41 
Profit per piece is 25%. Find the maximum profit per week.
Sol. As the given problem is a maximisation problem, we convert it into an opportunity loss matrix by subtracting all the elements of the given table from the highest element of table i.e., 42. Opportunity loss matrix is as follows :
L_{1} 
L_{2} 
L_{3} 
L_{4} 
L_{5} 

Operator 
P Q R S T 
22 23 19 21 18 
20 19 14 18 14 
15 13 7 1 11 
10 8 3 5 6 
6 2 8 0 1 
Row Reduction
L_{1} 
L_{2} 
L_{3} 
L_{4} 
L_{5} 

Operator 
P Q R S T 
16 21 16 21 17 
14 17 11 18 13 
9 11 4 11 10 
4 6 0 5 5 
0 0 5 0 0 
Column Reduction
L_{1} 
L_{2} 
L_{3} 
L_{4} 
L_{5} 

Operator 
P Q R S T 
0 5 0 5 1 
3 6 0 7 2 
5 7 0 7 6 
4 6 0 5 5 
0 0 5 0 0 
Therefore, the minimum number of lines to cover all zeros is 3 which is less than 5, the above matrix will not give optimal solution,
Therefore, subtract the least uncovered element which is 1 from all uncovered elements and add it to all elements lying at the intersection of two lines, we get the following matrix.
L_{1} 
L_{2} 
L_{3} 
L_{4} 
L_{5} 

Operator 
P Q R S T 
0 4 0 4 0 
3 5 0 6 1 
5 6 0 6 5 
4 5 0 4 4

1 0 6 0 0 
Therefore, the minimum lines drawn to cover all zero is 3. Repeating the above procedure, the matrix is
L_{1} 
L_{2} 
L_{3} 
L_{4} 
L_{5} 

Operator 
P Q R S T 
0 4 1 4 0 
2 4 0 5 0 
4 5 0 5 4 
3 4 0 3 3 
1 0 7 0 0 
The minimum number of Lines to cover all zero is 4 which is less than 5 the resultant matrix is
L_{1} 
L_{2} 
L_{3} 
L_{4} 
L_{5} 

Operator 
P Q R S T 
0 1 1 1 0 
2 1 0 2 0 
4 2 0 2 4 
3 1 0 0 3 
4 0 10 0 3 
Therefore, the minimum number of lines to cover all zeros is 5.
Hence the above matrix will give optimal solution.
and the assignment of operator setting lathe time is given by
P → L_{1} = 20
Q → L_{2} = 40
R → L_{3} = 35
S → L_{4} = 37
L → L_{5} = 28
The maximum profit per week 25 × 160= 4000.
Example 6.15. The Captain of a cricket team has to allot five middle batting positions to five batsmen. The average runs scored by each batsman at these positions are as follows.
Batting Positions
I 
II 
III 
IV 
V 

Batsman 
P Q R S T 
40 42 50 20 58 
40 30 48 19 60 
35 16 40 20 59 
25 25 60 18 55 
50 27 50 25 53 
(i) Find the assignment of batsman to positions which would give maximum number of runs.
(ii) If another batsman U with the following average runs in batting positions as given below.
Batting positions  I  II  III  IV  V 
Average Runs  45  52  38  50  49 
is added to the team, should be included to play in the team? If so who will be replaced by whom?
Sol. (i) Convert the profit matrix into opportunity cost matrix by subtracting all the elements from the highest element 60 of given matrix, we obtain the following opportunity loss matrix.
I 
II 
III 
IV 
V 

P Q R S T 
20 18 10 40 2 
20 30 12 41 0 
25 44 20 40 1 
35 35 0 42 5 
10 33 10 35 7 
Row Reduction
I 
II 
III 
IV 
V 

P Q R S T 
10 0 10 5 2 
10 12 12 6 0 
15 26 20 5 1 
25 17 0 7 5 
0 15 10 0 7 
Column Reduction &Making Assignment
Therefore, the no of assignment is 5, the solution is optimum.
P → V → 50
Q → I → 42
R → IV → 60
S → III → 20
L → II → 60
Total : 232
(a) If we introduce a new batsman U then number of batsmen is not equal to number of batting positions. So a dummy batting position is created and the matrix will become.
I 
II 
III 
IV 
V 
Dummy 

P Q R S T U 
40 42 50 20 58 45 
40 30 48 19 60 52 
35 16 40 20 59 38 
25 25 60 18 55 50 
50 27 50 25 53 49 
0 0 0 0 0 0 
Convert the profit matrix into opportunity cost matrix by subtracting all the elements from the highest element i.e. 60 of the given matrix.
I 
II 
III 
IV 
V 
Dummy 

P Q R S T U 
20 18 10 40 2 15 
20 30 12 41 0 8 
25 44 20 40 1 22 
35 35 0 42 5 10 
10 33 10 35 7 11 
60 60 60 60 60 60 
Row Reduction
I 
II 
III 
IV 
V 
Dummy 

P Q R S T U 
10 0 10 5 2 7 
10 12 12 6 0 0 
15 26 20 5 1 14 
25 17 0 7 5 2 
0 15 10 0 7 3 
50 42 60 25 60 52 
Column Reduction & Making Assignment
I 
II 
III 
IV 
V 
Dummy 

P Q R S T U 
10 0 10 5 2 7 
10 12 12 6 × 0 
14 25 19 4 0 13 
25 17 0 7 5 2 
0 15 10 × 7 3 
25 17 35 0 35 27 
P → V → 50
Q → I → 42
R → IV → 60
S → Dummy 0
T → III → 59
U → II →52
Total : 263
Ex 6.16. A small school has five teachers teaching five different subjects. All the five teachers an capable of teaching all the five subjects. The output per day of the teacher and course coverage (%) for each subjects are given below.
Teachers 
1 
2 
3 
4 
5 
A B C D E 
7 4 8 6 7 
9 9 5 5 8 
4 5 7 8 10 
8 7 9 10 9 
6 8 8 10 9 
Course Coverage % 
2 
3 
2 
3 
4 
If teacher D is not available will your answer be different?
Sol. We can multiply the output of teachers for different subjects with coverage of course (%), the resultant matrix is shown as:
Teachers 
1 
2 
3 
4 
5 
A B C D E 
14 8 16 12 14 
27 27 15 15 24 
8 10 14 16 20 
24 21 27 30 27 
24 32 32 40 36 
Therefore, the problem is of maximisation.
Therefore, will deduct the maximum element i.e., 40. The resultant loss matrix will be
Subject
Teachers 
1 
2 
3 
4 
5 
A B C D E 
26 32 24 28 26 
13 13 25 25 16 
32 30 26 24 20 
16 19 13 10 13 
16 8 8 0 4 
Row Reduction
1 
2 
3 
4 
5 

A B C D E 
13 24 16 28 22 
0 5 17 25 12 
19 22 18 24 16 
3 11 5 10 9 
3 0 0 0 0 
Column Reduction
Now subtracting the main elements of each column from all its elements.
Teachers 
1 
2 
3 
4 
5 
A B C D E 
0 11 3 15 9 
0 5 17 25 12 
3 6 2 8 0 
0 8 2 7 6 
3 0 0 0 0 
Therefore, there are 3 lines, this is not the optimal solution.
So, we will follow the deduction method.
Teachers 
1 
2 
3 
4 
5 
A B C D E 
0 9 1 13 9 
0 3 15 23 12 
3 4 0 6 0 
0 6 0 5 6 
5 0 0 0 2 
Still the number of lines is less
Therefore, again the same procedure will be followed.
Teachers 
1 
2 
3 
4 
5 
A B C D E 
0 6 1 10 9 
0 0 15 20 12 
3 1 0 3 0 
0 3 0 2 6 
8 0 3 0 5 
A → 1=14
B → 2 =27
C → 4 =27
D → 5 =40
E → 3 =20
Total : 128
REVIEW
 1. (a) Show that assignment model is a special case of transportation model.
(b) Consider the problem of assigning five operators to five machines.
given below.
Operators 

Machines 
I 
II 
III 
IV 
V 
A B C D E 
10 3 10 5 7 
5 9 7 11 9 
13 18 2 7 4 
15 3 2 7 4 
16 6 2 12 12 
Assign the operators to different machines so that total cost is minimised.
 2. (a) If in an assignment problem we add a constant to every element of a row (or column) in the effectiveness matrix, prove that an assignment that minimises the total effectiveness in one matrix also minimises the total effectiveness in the other matrix.
(b) A national carrental service has a surplus of one car in each of the cities I, 2, 3, 4, 5, 6 and a deficit of one car in each of the cities 7, 8, 9, 10, 11, 12. The distance in miles between cities with a surplus and cities with a deficit are displayed in matrix. How should the cars be despatched so as to minimise the total mileage travelled.
To
7 
8 
9 
10 
11 
12 

1 
41 
72 
39 
52 
25 
51 
2 
22 
29 
49 
65 
81 
50 
3 
27 
39 
60 
51 
32 
32 
4 
45 
50 
48 
52 
37 
43 
5 
29 
40 
39 
26 
30 
33 
6 
82 
40 
40 
60 
51 
30 
 3. (a) Distinguish between transportation model and assignment model.
(b) Four different jobs are to be done on four different machines. The set up and production times are prohibitively high for change over. Tables indicates the cost of producing job i on machine j in rupees.
Machines
1 
2 
3 
4 

Jobs 
1 
5 
7 
11 
6 
2 
8 
5 
9 
6 

3 
4 
7 
10 
7 

4 
10 
4 
8 
3 
Assign jobs to different machines so that the total cost is minimised.
 4. Six machines M_{1}, M_{2}, M_{3}, M_{4}, M_{5} and M_{6} are to be located in six places P_{1}, P_{2}, P_{3}, P_{4}, P_{5} and P_{6}. C_{ij} the cost of locating machine M_{i} at place P_{j} is given the matrix below.
P_{1} 
P_{2} 
P_{3} 
P_{4} 
P_{5} 
P_{6} 

M_{1} 
20 
23 
18 
10 
16 
20 
M_{2} 
50 
20 
17 
16 
15 
11 
M_{3} 
60 
30 
40 
55 
8 
7 
M_{4} 
6 
7 
10 
20 
25 
9 
M_{5} 
18 
19 
28 
17 
60 
70 
M_{6} 
9 
10 
20 
30 
40 
55 
Formulate an LP model to determine an optimal assignment. Write the objective function and the constraints in detail. Define any symbol used. Find an optimal layout by assignment techniques of linear programming.
 5. (a) Discuss assignment model, Indicate a method of solving an assignment problem.
(b) A Company is faced with the problem of assigning six different machines to five different jobs. The costs estimated in hundreds of rupees are given in the table below.
1 
2 
3 
4 
5 

1 
2.5 
5 
1 
6 
2 
2 
2 
5 
1.5 
7 
3 
3 
3 
6.5 
2 
8 
3 
4 
3.5 
7 
2 
9 
4.5 
5 
4 
7 
3 
9 
6 
6 
6 
9 
5 
10 
6 
Solve the problem assuming that the objective is to minimise the total cost.
 6. Five new machines are to be located in machine shop. There are five possible locations in which machines can be located. C_{ij} the cost of placing machine i in place j is given in the table below.
Jobs 

1 
2 
3 
4 
5 
1 

1 
15 
10 
25 
25 
10 

2 
1 
8 
10 
20 
2 

Machine 
3 
8 
9 
17 
20 
10 
4 
14 
10 
25 
27 
15 

5 
10 
8 
25 
27 
12 
It is requiredto place the machines at suitable places so as to minimise the total cost.
(i) Formulate an LP model to find an optimal assignment.
(ii) Solve the problem by assignment technique of L.P.
 7. Solve the following assignment problem
I 
II 
III 
IV 
V 

1 
11 
17 
8 
16 
20 
2 
9 
7 
12 
6 
15 
3 
13 
16 
15 
12 
16 
4 
21 
24 
17 
28 
26 
5 
14 
10 
12 
11 
15 
 8. A team of 5 horses and 5 riders has entered a jumping show contest. The number of penalty points to be expected when each rider rides anv horse is shown below.
R_{1} 
R_{2} 
R_{3} 
R_{4} 
R_{5} 

Horse 
H_{1} 
5 
3 
4 
7 
2 
H_{2} 
2 
3 
7 
6 
5 

H_{3} 
4 
1 
5 
2 
4 

H_{4} 
6 
8 
1 
2 
3 

H_{5} 
4 
2 
5 
7 
1 
How should the horses be allotted to the riders so as to minimise the expected loss of the team?
 9. Find the minimum cost solution for the 5 × 5 assignment problem whose cost coefficients are A given below.
1 
2 
3 
4 
5 

1 
2 
4 
8 
6 
1 
2 
0 
9 
5 
5 
4 
3 
3 
8 
9 
2 
6 
4 
4 
3 
1 
0 
3 
5 
9 
5 
8 
9 
5 
 10. A company has four machines on which to do three jobs. Each job can be assigned to one and only one machine. The cost of each job on each machine is given in the following table.
Machines
W 
X 
Y 
Z 

Job 
A 
18 
24 
28 
32 
B 
8 
13 
17 
19 

C 
10 
15 
19 
22 
What are the job assignments which will minimise the cost?
 11. Assign four trucks 1, 2, 3 and 4 to vacant spaces 7, 8, 9, 10, 11 and 12 so that the distance travelled is minimised. The matrix below shows the distance.
1 
2 
3 
4 

7 
4 
7 
3 
7 
8 
8 
2 
5 
5 
9 
4 
9 
6 
9 
10 
7 
5 
4 
8 
11 
6 
3 
5 
4 
12 
6 
8 
7 
3 
 12. A Company has five jobs to be done. The following matrix shows the return in rupees of assigning ith machine (i = 1, 2, …. 5) to the job (j = 1, 2, …. 5). Assign the five jobs to the five machines so as to maximise the total expected profit.
Job
1 
2 
3 
4 
5 

Machine 
1 2 3 4 5 
5 2 3 6 7 
11 4 12 14 9 
10 6 5 4 8 
12 3 14 11 12 
4 5 6 7 5 
 13. The owner of a small machine shop has four machinists available to assign to jobs for the day. Five jobs are offered with the expected profit in rupees for each machinist on each job being as follows. Find the assignment of machinists to jobs that will return in a maximum profit. Which job should be declined?
Job
1 
2 
3 
4 
5 

Machine 
1 2 3 4 
6.20 7.10 8.70 4.80 
7.80 8.40 9.20 6.40 
5.00 6.10 11.10 8.70 
10.00 7.30 7.10 7.70 
8.20 5.90 8.10 8.00 
 14. An airline that operates seven days a week has timetable as shown below. Crew must have a minimum layover of 5 hours between flights. Obtain the pairing of flights that minimises layover time away from home. For any given pairing, the crew will be based at the city that results in smaller layover.
DelhiJaipur 
JaipurDelhi 

Flight No. 
Depart 
Arrive 
Flight No 
Depart 
Arrive 
1 
7.00 AM 
8.00 AM 
101 
8.00AM 
9.15 AM 
2 
8.00 AM 
9.00 AM 
102 
8.30 AM 
9.45 AM 
3 
1.30 AM 
2.30 AM 
103 
12.00 Noon 
1.15 PM 
4 
6.30 PM 
7.30 PM 
104 
8.00 PM 
6.45 PM 
For each pair also mention the town where the crew should be based.
 15. A company has four territories open and four salesman 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 
Annual Sales (Rs.) 
I 
60,000 
II 
50,000 
III 
40,000 
IV 
30,000 
The four salesmen are also considered to differ in ability, it is estimated that working under the same conditions their yearly sales will be proportionately as follows.
Salesmen 
Proportion 
A 
7 
B 
5 
C 
5 
D 
4 
 16. If the criterion is maximum expected total sales, the 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.
 17. (a) State mathematical model of assignment problem.
(b) The personnel manager of a medium size company decided to recruit two employees D and E in a particular section of the organisation. The section has five fairly defined tasks 1, 2, 3, 4 and 5 and three employees A, B and C are already employed in the section. Looking at the rather specialised nature of task 3 and the special qualifications of the recruit D for task 3, the manager decided to assign task 3 to employee D and then assign the remaining tasks to remaining employees so as to maximise the total effectiveness. The index of effectiveness of each employee for different task is as under.
Tasks
Employee 
1 
2 
3 
4 
5 

A 
25 
55 
60 
45 
30 

B 
45 
65 
55 
35 
40 

C 
10 
35 
45 
55 
65 

D 
40 
30 
70 
40 
60 

E 
55 
45 
40 
55 
10 
Assign the tasks for maximising total effectiveness. Critically examine whether the decision of the manager to assign task 3 to employee D was correct.
 18. Enumerate various steps involved in Hungarian method of solving assignment problem.
 19. Discuss briefly the Hungarian method of solving an assignment problem.
 20. Write a method of solving an assignment problem. Illustrate with an example.
 21. A Departmental head has 4 subordinates and 4 tasks to be performed, the subordinates differ in efficiency and the tasks differ in their intrinsic difficulty. His estimate of the times each man would take to perform each task is given below in the matrix:
Tasks/ Subordinates 
I 
II 
III 
IV 
A B C D 
8 13 38 19 
26 28 19 26 
17 4 18 24 
11 26 15 10 
How should the tasks to be located to subordinates so as to minimize the total
manhours?
 22. . A car hire company has one car at each of 5 depots a, b, c, d and e. A customer each of five cities A, B, C, D and E require a car. The distance (in kms.) he depots and the cities are as follows:
Tasks/ Subordinates 
a 
b 
c 
d 
D 
A B C D E 
160 135 140 50 55 
130 120 110 50 35 
175 130 155 80 70 
190 160 170 80 80 
200 175 185 110 105 
 23. How should the cars be assigned to the customers so as to minimize the distance travelled?
 24. Find the assignment of men to jobs that will minimize the total time:
Jobs
J_{1} 
J_{2} 
J_{3} 
J_{4} 

MEN 
M_{1} M_{2} M_{3} M_{4} 
8 13 38 19 
26 28 19 26 
17 4 18 24 
11 26 15 10 
 25. Three customers in a certain sales territory have requested technical assistance from available 3 technicians. Distance between the technicians and customers is reported below. Using assignment problems techniques assign the technicians to the customers for minimum cost of travel per km is Rs. 2
Customers 

I 
II 
III 

Technicians 
A B C 
37 38 88 
58 92 55 
41 74 43 
 26. Given the following cost matrix (in ‘000 Rs.) contract
Bidder 
Diff 
Weapon 
Subsystems 

I 
II 
III 
IV 

A B C D 
17 15 17 14 
20 21 18 22 
13 14 17 12 
21 18 21 22 
Assign the 4 diff weapon subsystems, one each to bidder so as to minimize cost.
 27. Using following cost matrix, assign the different contractors to different jobs so as to minimize the total cost:
A 
B 
C 
D 

JOBS 
X Y Z L 
17 15 17 14 
20 21 18 22 
13 14 17 12 
21 18 21 22 
 28. Using following cost matrix of cost of three jobs on three machines, assign one job to each machine so that the total cost is minimum.
Machine 

X 
Y 
Z 

Job 
A 
25 
31 
35 
B 
15 
20 
24 

C 
22 
19 
17 
 29. Solve the following Assignment Problem of maximization:
5 
6 
8 
9 
2 
3 
4 
5 
6 
5 
3 
4 
9 
8 
8 
9 
6 
5 
4 
2 
3 
1 
2 
2 
3 
 30. Determine the optimum solution to each of the following problem:
Jobs 

Operator 
1 
2 
3 
4 
5 
1 2 3 4 5 6 
6 2 7 6 9 4 
2 5 8 2 3 7 
5 8 6 3 8 4 
2 7 9 4 9 6 
6 7 8 5 7 8 
 31. Assign the operators to machines to minimize costs for the following:
Machines 

Operator 
I 
II 
III 
IV 
V 
A B C D E 
5 7 9 7 6 
5 4 3 2 5 
– 2 5 6 7 
2 3 – 7 9 
6 4 3 2 1 
 32. Find the optimal solution for the assignment problem:

I 
II 
III 
IV 
V 
A B C D E 
11 9 13 21 14 
17 7 16 24 10 
8 12 15 17 12 
16 6 12 28 11 
20 15 16 26 15 
 33. For a given profit matrix, find the optimal assignments:
Machines 

Job 
1 
2 
3 
4 
5 
A B C D E 
11 9 13 21 14 
17 7 16 24 10 
8 12 15 17 12 
16 6 12 28 11 
20 15 16 26 15 
 34. Assigns five operators to five machines to minimise total cost:
Machines 

Operator 
I 
II 
III 
IV 
V 
A B C D E 
5 7 9 7 6 
5 4 3 2 5 
– 2 5 6 7 
2 3 – 7 9 
6 4 3 – 1 
 35. Solve the assignment problem:
From/To 
A 
B 
C 
D 
E 
A B C D E 
– 7 6 8 4 
7 – 8 5 6 
6 8 – 9 7 
8 5 9 – 8 
4 6 7 8 – 
 36. What is Unbalance Assignment Problem? How it is solved by HAM? (Take any imaginary problem). HAMHungarian Assignment Method.
 37. Suggest optimum assignment to sales territories, where the estimates of sales to be made by each salesman in different territories are given below:
Territories 

Salesman 
I 
II 
III 
IV 
V 
A B C D 
10 6 12 8 
15 18 5 11 
17 10 13 16 
14 12 13 10 
14 16 6 12 
If salesman B cannot be assigned to territory II for certain reasons, will the optimum assignment change? If so, what will be the new assignment schedule and the total sales?
 38. Unbalanced assignment problem’
 39. Distinguish between Assignment and Transportation problem.
 40. Enumerate various steps involved in Hungarian method of solving assignment problem.
 41. Write a method of solving a assignment problem Illustrate with an example.
 42. Find the assignment of men to jobs that will minimize the total time:

Jobs 

Men 
J_{1} 
J_{2} 
J_{3} 
J_{4} 
M_{1} M_{2} M_{3} M_{4} 
8 13 38 19 
26 18 19 26 
17 4 18 24 
11 26 15 10 
 43. Three customers in a certain sales territory has requested technical assistance from available 3 technicians. Distance between the technicians and customers is reported below. Using assignment problems techniques assign the technicians to the ‘customers for minimum cost of travel per km. is Rs. 2.
Technicians 
Customers 

I 
II 
III 

A B C 
37 38 38 
58 92 55 
41 74 43 
 44. Given the following cost matrix (in ‘000 Rs.) contract:
Bidder 
Diff. Weapons subsystems 

I 
II 
III 
IV 

A B C D 
17 15 17 14 
20 21 18 22 
13 14 17 12 
21 18 21 22 
Assign the 4 Different weapon subsystems, one each to each bidder so minimize cost.
 45. Using following cost matrix, assign the different contractors to different jobs to minimize the total cost:
Jobs 
Contractors 

A 
B 
C 
D 

X Y Z L 
17 15 17 14 
20 21 18 22 
13 14 17 22 
21 18 21 22 
 46. Using following cost matrix of cost of three jobs on three machines, assign one job to each machine so that total cost is minimum.
Job 
Machine 

X 
Y 
Z 

A B C 
25 15 22 
31 20 19 
35 24 17 
 47. A process can be carried out on any of the 4 machines by one of the operators. The average time taken by any operator on any specific machine is tabulated below. A proposal to replace one of the existing machines by a new machine is under consideration. The estimated timing to carry out the process on the new machine are also included in the table. Is it worthwhile to use new machinery?
Operator 
I 
Machines 

II 
III 
IV 
New 

A B C D 
12 11 10 14 
14 12 9 15 
8 12 9 8 
8 12 9 8 
12 9 8 7 
11 10 7 6 
 48. Consider the problem of assigning the five jobs to five persons. The assignment costs are given as follow:
Jobs 


1 
2 
3 
4 
5 

Persons 
A B C D E 
8 0 3 4 9 
4 9 8 3 5 
2 5 9 1 8 
6 5 2 0 9 
1 4 6 3 5 
 49. Assign the jobs to machines for maximizing profits given in table.
Machines 


A 
B 
C 
D 
E 

Jobs 
I II III IV V 
32 40 41 22 39 
38 24 27 38 33 
40 28 33 41 40 
28 21 30 36 35 
40 36 37 36 39 
 50. Assign machine to give jobs, you are given costs (in Rs.)
Jobs 


1 
2 
3 
4 
5 

Machine 
1 2 3 4 5 6 
2.5 2 3 3.5 4 6 
5 5 6.5 7 7 9 
1 1.5 2 2 3 5 
6 7 8 9 9 10 
1 3 3 4.5 6 6 
 51. A firm wants to purchase three different types of equipment and manufactures have come forward to supply one or all the three machines. However, the firm’s policy is to purchase one machine from one manufacturer only. The data relating to price (in lacs of Rs.) quoted by the different manufactures is given on next page.

Machines 


1 
4 
5 

Manufacture 
A B C D E 
2.99 2.78 2.92 2.82 3.11 
3.11 2.87 3.05 3.10 2.90 
2.68 2.57 2.80 2.74 2.62 
Determine how best the firm can purchase three machines, assuming machines of different manufactures have the same capacity.
 52. A departmental head has 4 subordinates and 4 tasks to be performed, the
subordinates differ in efficiency and the task differ in their intrinsic difficulty. His estimate of the times each man would take to perform each task is given below is the matrix :
I 
II 
III 
IV 

A B C D 
8 13 38 19 
26 28 19 26 
17 4 18 24 
11 26 15 10 
How should the tasks to be allocated to subordinates so as to minimize the total manhours?
 53. A car hire company has one car at each of 5 depots a, b, c, d and .e. A customer in each of five cities, A, B, C, D and E require a car. The distance (in kms.) between depots and the cities are as follows:
a 
b 
c 
d 
e 

A B C D E 
160 135 140 50 55 
130 120 110 50 35 
175 130 155 80 70 
190 160 170 80 80 
200 175 185 110 105 
How should the cars be assigned to the customers so as to minimize the distance travelled?
 54. Solve the foil lowing assignment problem:
J1 
J2 
J3 
J4 
J5 

P1 P2 P3 P4 
27 31 20 20 
18 24 17 28 
X 21 20 20 
20 12 X 16 
21 21 16 27 
 55. Solve the following assignment (minimisation) problem:
Machines 

Jobs 
A 
B 
C 
D 
1 2 3 4 5 
12 12 8 8 10 
7 5 4 6 11 
9 10 9 7 9 
10 11 7 5 7 
 56. Solve the following Assignment problem:
Sales in Rs. 000’S 

Salesman → Territory ↓ 
S_{1} 
S_{2} 
S_{3} 
S_{4} 
A B C D 
50 70 90 60 
48 72 80 48 
47 70 85 52 
45 60 82 55 
 57. Solve the following assignment problem. The district wise sales of ‘5 salesmen is given as under
Districts 
Sales in Rs. 000’s 

Salesman 
1 
2 
3 
4 
5 
A B C D E 
38 49 50 28 39 
44 33 36 44 40 
47 37 40 48 48 
35 30 39 45 45 
50 42 46 43 46 
 58. A company has a team of four salesmen and there are four districts where the
company wants to start its business. After taking into account the capabilities of salesmen and the nature of districts the company estimates that the profit per day in rupees for each salesman in each district is as below:
Districts 

Salesman 
1 
2 
3 
4 
A B C D 
16 14 15 13 
10 11 15 12 
14 15 13 14 
11 15 12 15 
 59. Following table gives the weekly output of five operators working on 5 lathes. Do the assignment of operators on the lathes so as to maximize total production:
Lathe Weekly output 

Operators 
L_{1} 
L_{2} 
L_{3} 
L_{4} 
L_{5} 
P Q R S T 
20 19 23 21 24 
22 23 28 24 28 
27 29 35 31 31 
32 34 39 37 36 
36 40 34 42 41 
 60. (i) Assignment Problem is a special case of Transportation Problem Discuss.
(ii) Using following cost matrix assign jobs to different machines so as to minimise total cost:
Machines 

1 
2 
3 
4 

A B C D 
10 5 12 8 
12 10 14 15 
19 7 13 11 
11 8 11 9 
 61. A company is faced with the problem of assigning 4 machines to 6 different jobs (One machine to one job only). The profits are estimated as follows:
Machine 

Jobs 
A 
B 
C 
D 
1 2 3 4 5 6 
3 7 3 6 5 5 
6 1 8 4 2 7 
2 4 5 3 4 6 
6 4 8 7 3 4 
Solve the problem to maximise the profit.
Recent Comments