The Travelling Salesman Problem
To solve the travelling salesman problems, the assignment models find its application. Suppose a salesman has to visit ‘n’ different locations in which he has to start from a particular city and cover all the destinations. The objective is to minimize the time required by the salesman in his whole journey.
In this context, it is important that the sequence of the locations should give the least time taken to visit them all. The solving technique is similar to the assignment problems, but the only difference is that salesman should visit a particular city only once.
This is quite simple, but there is an additional point to consider that he should reach the starting point at the end of his journey.
Formulation of Travelling Salesman Problem:
Let us consider ijk asthe variable. Here, k has been included in addition to ‘i’ and ‘j’.
ijk =
Where,
i, j, k are integers and vary between 1 to ‘n’. The following constraints can be put in mathematical form as follows
1.ijk– 1, k =1, 2, 3, ……..n and i≠j
- Only one city can be reached from a particular city, say i;
ijk– 1, where i = 1, 2, 3, ……..n
- Only from one city, the salesman can go to another specific city, say j;
ijk– 1, where j = 1, 2, 3, ……..n
- Given that kth visit ends at some specific city i.e., i (k + 1)th. The visit must start at the same city ‘j’. Hence, we get;
ijk–jk(k + 1) for all values of ‘j’ and ‘k’.
Now, to get the objective function, minimize ‘Z’ is given by;
Z = ijkdij i ≠ j
Where,
dij= Distance from city ‘i’ to city ‘j’
Example 6.3:
The intercity distances of a travelling salesman has been given in a tabular form. He has to vist five different cities, viz., A, B, C, D and E.
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 between two cities are measured in km. It should be the same both ways. Suggest the salesman to take a route that can minimize the total distance travelled by him. Suppose he starts from city A and should come back to city A.
Solution:
Step 1: Select the smallest value of each row to subtract it from all the elements in the same row. The following matrix will be formed:
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 2:
Select the smallest value of each column to subtract it from all the elements in the same column. The following matrix will be formed:
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 3:
Draw minimum number of straight lines to cover all the zeroes.
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 –
Hence,
Number of lines (5) = Order of matrix (5). This suggests that it is the optimal solution.
Step 4:
Making an assignment in zero position does not satisfy the constraints. Thus, following assignment has been made by hit and trial method.
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 will be:
A → B, B → C, C → D, D → E and E → A
This means, 12 + 17 + 19 + 17 + 12 = 77 km. it satisfies the travelling salesman problem.
Unbalanced Problems
Example 6.4:
A transport company has 3 vehicles for 3 different cities. For a new project, it has to assign these three vehicles to four different cities. The distance are measured and presented in a tabular form below:
1 2 3 4
A 33 40 43 32
B 42 30 31 24
C 40 31 37 31
You have to,
- Assign a vehicle to the cities to minimize the total distance covered
- Formulate mathematical model of this problem
Solution:
- Step 1:
As this problem is not balanced one, a dummy city D is introduced. Take 0 (zero) as its distance, thisfollowing matrix can be followed:
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 2:
Subtract the smallest element of each row from all other elements of the same row. The following matrix has been formed:
1 2 3 4
A 1 8 11 0
B 18 6 7 0
C 9 0 6 0
D 0 0 0 0
Step 3:
There is no need to subtract 0 from each column
Step 4:
Draw the minimum number of lines to cover all the zeroes. It has found that number of lines (3) is less than order of matrix (4).This means it is not the optimal solution. We have to increase the number of zeroes. Thus, the following matrix is made:
1 2 3 4
A 1 8 11 6
B 18 6 7 0
C 9 0 6 0
D 0 0 0 0
Step 5:
Subtract minimum uncovered element from all uncovered elements. Add this to the elements at the intersection point. Then, draw the minimum numbers of lines to cover all zeroes. we get;
1 2 3 4
A 0 7 10 0
B 17 5 6 0
C 9 0 6 1
D 0 0 0 1
Hence, numbers of lines = 4 = order of the matrix. This is the optimal solution.
Step 6:
Thus, assignments can be made;
1 2 3 4
A 0 7 10 0
B 17 5 6 0
C 9 0 6 1
D 0 0 0 1
Step 7:
Minimum distance covered by the salesman should be:
City Vehicle Distance
A 1 33
B 4 24
C 2 31
D 3 0
Total 88
- Formulation of LPP
11 12 13 14
33 40 43 32
21 22 23 24
42 30 31 24
31 32 33 34
40 31 37 31
41 42 43 44
0 0 0 0
Minimize ‘Z’ will be:
= 3311+ 4012+ 43 13+ 3214+ 42 21+ 30 22+ 3123+ 24 24+ 4031+ 31 32+ 37 33+ 31 34+ 0 41+ 0 42 + 0 43+ 0 44
Subject to;
11+12+ 13+ 14= 1
21+22+ 23+ 24= 1
31+32+ 33+ 34= 1
41+42+ 43+ 44= 1
ij 0.
Example 6.5:
To find the minimization of time for doing all jobs, you need to solve the unbalanced assignment problem below:
Operators 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
Solution:
Step 1:
Add a dummy job 6 to balance this problem and allot 0 (zero) as its timing.
Operators 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 8 0
D 7 2 3 5 6 0
E 10 3 8 9 7 0
F 5 7 4 7 8 0
Step 2:
There is zero in each row so no need to do row deduction. Here, column deduction will be done by subtracting the minimum element value of each column to the rest of the elements of the same column. We get the following matrix;
Operators 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
Since the number of lines (4) is less than the order of matrix (6). It is not an optimal solution. Now, draw minimum numbers of lines and cover all the zeroes.
Step 3:
Subtract the minimum uncovered element from all the uncovered elements. Then, add it to the elements that are present in the intersection of two lines. We get,
Operators 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 0
E 6 0 4 5 0 0
F 1 4 0 3 1 0
Thus, we get the assignment s number of lines (6) = order of the matrix (6). It is optimal solution.
Step 4:
The assignment will be;
Operators 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 0
E 6 0 4 5 0 0
F 1 4 0 3 1 0
Step 5:
The minimum time required will be:
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:
A, B, C and D are four operators available to perform four jobs i.e. J-1, J-2, J-3 and J-4. It would be done by assigning a particular job to each operator. The following detail is given to get the time taken by different operators for doing different jobs.
J-1 J-2 J-3 J-4
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 these jobs to get the minimum time taken for the completion of the task?
Solution:
Step 1:
Subtract the minimum value present in each row from all the other elements of the same row. The following matrix will be formed;
J-1 J-2 J-3 J-4
A 2 0 2 1
B 2 0 4 0
C 0 2 10 0
D 1 2 0 0
Step 2:
There is zero in each column as minimum value, so no need to subtract this in each column.
Step 3:
Draw the minimum numbers of lines to cover all zeros. The following matrix will be formed;
J-1 J-2 J-3 J-4
A 2 0 2 1
B 2 0 4 0
C 0 2 10 0
D 1 2 0 0
Here, Number of lines (4) = Order of matrix. Hence, it is the optimal solution.
Step 4:
Making the final assignment:
J-1 J-2 J-3 J-4
A 2 0 2 1
B 2 0 4 0
C 0 2 10 0
D 1 2 0 0
Step 5:
Compute the minimum time required by each operator:
Operator Job Time
A J-2 8
B J-4 10
C J-1 6
D J-3 7
Total 31
Example 6.7:
A manufacturing company has four sales engineers as A, B, C and D for different assignments in different zones as Z-1, Z-2, Z-3 and Z-4 respectively. Each zone is different in its potential to yield profit. It is estimated that engineers at each zone can produce following sales.
Z-1 : 4,50,000
Z-2 : 3,40,000
Z-3 : 3,00,000
Z-4 : 4,60,000
Each engineer has different sales ability. The criteria of maximum expected sales are to assign the best engineer to the richest zone and the yearly sales shows 15, 10, 12 and 8 respectively when working under similar conditions. Determine the optimal assignment solution to get the maximum sales.
Solution:
Step 1:
The revenue matrix is given below:
Territory Zones (Sales in thousands of Rs)
Engineers Z-1 Z-2 Z-3 Z-4
A 450 x 15/ 45 340 x 15/ 45 300 x 15/ 45 460 x 15/ 45
B 450 x 10/ 45 340 x 10/ 45 300 x 10/ 45 460 x 10/ 45
C 450 x 12/ 45 340 x 12/ 45 300 x 12/ 45 460 x 12/ 45
D 450 x 8/ 45 340 x 8/ 45 300 x 8/ 45 460 x 8/ 45
This matrix gets reduced to:
Z-1 Z-2 Z-3 Z-4
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 2:
Reduce the problem to do minimization. The loss matrix will be formulated by subtracting all elements from largest element value i.e. 154:
Z-1 Z-2 Z-3 Z-4
A 4 40 54 0
B 54 78 87 52
C 34 63 74 31
D 74 93 100 72
Step 3:
Now, subtract the minimum value of each row from all the elements of the same row, we get:
Z-1 Z-2 Z-3 Z-4
A 4 40 54 0
B 2 26 35 0
C 3 32 43 0
D 2 21 28 0
Step 4:
Subtract the minimum value of each column from all the elements of the same column, we get:
Z-1 Z-2 Z-3 Z-4
A 2 19 26 0
B 0 5 7 0
C 1 11 15 0
D 0 0 0 0
Therefore,
Number of lines (3) is not equal to order of matrix (4). Thus, it is not the optimal solution.
Step 5:
Subtract minimum uncovered element from all the uncovered elements. Add the same element to all intersection points of the lines and draw the minimum numbers of lines to cover all the zeros.
Z-1 Z-2 Z-3 Z-4
A 1 18 25 0
B 0 5 7 1
C 0 10 14 0
D 0 0 0 0
Again, there are three lines. It is also not an optimal solution. Repeat Step 5 and obtain another assignment, we get:
Z-1 Z-2 Z-3 Z-4
A 1 13 20 0
B 0 0 2 1
C 0 5 9 0
D 5 0 0 6
Thus, number of lines (4) = order of matrix (4). This is the optimal solution.
Step 6:
Making the assignment in usual manner, we get:
Z-1 Z-2 Z-3 Z-4
A 1 13 20 0
B 0 0 2 1
C 0 5 9 0
D 5 0 0 6
Step 7:
Compute the above table for maximum sales:
Engineer Zone Sales (Rs)
A Z-4 4,60,000 x 15/ 5 = 4,60,000
B Z-2 3,40,000 x10/ 15 = 2,26,666
C Z-1 4,50,000 x 12/ 15= 3,60,000
D Z-3 4,00,000 x 8/ 15 = 1,60,000
Total = 12,06,000
Therefore, it has been found that engineer A is the best performer. Thus, the zone Z-4 will be assigned to him and the next-best is engineer C to assign next richest zone as Z-1.
Example 6.8:
MIS Steadfast Enterprise has four different plants and each of these plants manufacture any of the four products. The cost of the products differs for each plant 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
To minimize the cost, find out which product should each plant produce and formulate a LPP.
Solution:
Step 1:
Subtracting the minimum value of each row with the other elements of the same row-
P Q R S
1 1 8 11 0
2 12 5 7 0
3 13 0 6 0
4 0 15 18 11
Step 2:
Subtracting the minimum value of each column with the other elements of the same column-
P Q R S
1 1 8 5 0
2 12 5 1 0
3 13 0 0 0
4 0 15 12 11
Step 3:
Draw minimum number of lines to (horizontally or vertically) to cover all the zeros-
P Q R S
1 1 8 5 0
2 12 5 1 0
3 13 0 0 0
4 0 15 12 11
It can be seen that number of lines drawn (3) is less than order of matrix (4). Thus, it is not an optimal solution. We have to increase the number of zeros in the matrix.
Step 4:
Subtract the minimum uncovered value (1) from all uncovered elements. Then, add the same number to the elements that are present in the intersection of two lines. We get the following matrix-
P Q R S
1 0 7 4 0
2 11 4 0 0
3 13 0 0 1
4 0 15 12 12
Step 5:
Again, draw minimum numbers of lines to cover all zeros, we get-
P Q R S
1 0 7 4 0
2 11 4 0 0
3 13 0 0 1
4 0 15 12 12
Hence, number of lines drawn = order of the matrix = 4
Thus, the above matrix is the optimal solution.
Step 6:
Select a row that contains exactly one unmarked zero. Put around it and draw vertical line containing this zero. Repeat it till there is no such row left. Then, select a column that contains exactly one unmarked zero. Put around it and draw horizontal line containing this zero. Repeat it till there is no such column 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 7:
Optimal assignment is given by-
1 →S = 32
2 →R = 30
3 →Q = 29
4 →P = 27
Thus, the minimum cost is 118
Formulation of LPP:
11 12 13 14
33 40 43 32
21 22 23 24
45 28 30 23
31 32 33 34
42 29 35 29
41 42 43 44
27 42 45 38
Maximize ‘Z’ will be:
= 3311+ 4012+ 43 13+ 3214+ 4521+ 2822+ 3023+ 2324+ 4231+ 2932+ 3533+ 2934+ 2741+ 4242+ 4543+ 3844
Subject to;
11+12+ 13+ 14= 1
21+22+ 23+ 24= 1
31+32+ 33+ 34= 1
41+42+ 43+ 44= 1
ij 0.
Example 6.9:
A company assigns five jobs to five operators. Each job is performed by exactly one operator. The processing cost of each job is given below (Rs.)
Jobs Operators
P Q R S T
A 7 5 9 8 11
B 9 12 6 11 10
C 8 5 4 6 8
D 7 3 6 8 5
E 5 6 7 5 11
Find out the minimum cost of operation for each job assigned to a particular operator.
Solution:
Step 1:
Pick the minimum value of the element of each row and subtract the same with the other elements of the same row.
P Q R S T
A 2 0 4 3 6
B 3 6 0 5 4
C 4 1 0 2 4
D 4 0 3 5 2
E 0 1 2 0 6
Step 2:
Pick the minimum value of the element of each column and subtract the same with the other elements of the same column.
P Q R S T
A 2 0 4 3 4
B 3 6 0 5 2
C 4 1 0 2 2
D 4 0 3 5 0
E 0 1 2 0 4
Step 3:
Now, we can find that there is a single zero in cell AQ and cell BR that is row A and row B respectively. When assignments are making in these two cells, other zeros are appearing in the column Q and R respectively. Thus, these zeros are crossed out. Hence,
P Q R S T
A 2 0 4 3 4
B 3 6 0 5 2
C 4 1 0 2 2
D 4 0 3 5 0
E 0 1 2 0 4
Here, we can find only a single zero in row D i.e. the cell DT. And in row E, there will be no assignment as it has two zeros.
Looking at the columns, we find that column P has only one zero. This means assignment can be made in the cell EP. Then other zero in the row E will be crossed out at ES.
Thus, it has been observed that only 4 assignments can be made against 5 vacant places, means it is not an optimal solution.
Step 4:
Select the smallest uncovered element (2) and subtract from the uncovered elements. Then add the same value (2) with the elements that are present in the intersection of two lines. We get,
P Q R S T
A 0 0 4 1 4
B 1 6 0 3 2
C 2 1 0 0 2
D 2 0 3 3 0
E 0 3 4 0 6
Step 5:
We can make assignment in cell CS as there is a single zero in row C. Thus, the optimal solution is obtained.
A →Q = 5
B → R = 6
C →S = 6
D →T = 5
E →P = 5
Minimum Total Cost is Rs. 27
Example 6.10
A cost matrix has been made for assigning four key courses to four professors. Class preparation time for different topics is different from professor to professor is given in a table below. To minimize the total preparation time, one course has been assigned to each professor.
Professor Courses
C1 C2 C3 C4
A 2 10 9 7
B 15 4 14 8
C 13 14 16 11
D 4 15 13 9
Solution:
Step 1:
Subtract the minimum element of each row with the other elements of the same row, we get-
C1 C2 C3 C4
A 0 8 7 5
B 11 0 10 4
C 2 3 5 0
D 0 11 9 5
Step 2:
Subtract the minimum element of each column with the other elements of the same column, we get-
C1 C2 C3 C4
A 0 8 2 5
B 11 0 5 4
C 2 3 0 0
D 0 11 4 5
Step 3:
As there is a single zero in the cell AC1, an assignment can be made by crossing the other zeros in column C1. Similarly, assignments can be made in cell BC2 and CC3. We get-
C1 C2 C3 C4
A 0 8 2 5
B 11 0 5 4
C 2 3 0 0
D 0 11 4 5
Here, number of assignments is less than order of matrix. This is not an optimal solution. Now, draw minimum lines to cover all the zeros and we get-
C1 C2 C3 C4
A 0 8 2 5
B 11 0 5 4
C 2 3 0 0
D 0 11 4 5
Step 4:
Select the minimum uncovered element and subtract with the other uncovered elements. Add the same number with the elements that are present in the intersection of two lines. We get-
C1 C2 C3 C4
A 0 6 0 3
B 13 0 5 4
C 4 3 0 0
D 0 9 2 3
Step 5:
Making fresh assignments-
C1 C2 C3 C4
A 0 6 0 3
B 13 0 5 4
C 4 3 0 0
D 0 9 2 3
Hence, the number of assignments = the order of matrix. This is the optimal solution.
Therefore,
Professor Course Time
A C3 9
B C2 4
C C4 11
D C1 4
Total Minimum Course Duration is 28 minutes.
Example 6.11:
A plant layout is modified with four new machines at its machine shop. Five vacant sheds are there, each at A, B, C, D and E. Due to the limited space at C and A, machine M2 and M3 cannot be placed at C and A respectively. Below table shows the cost. Find the optimum assignment schedule.
A B C D E
M1 9 11 15 10 11
M2 12 9 – 10 9
M3 – 11 14 11 7
M4 14 8 12 7 8
Solution:
Here, four rows and five columns are present. To balance the matrix, we will assign 0 to a dummy row M5. We get-
A B C D E
M1 9 11 15 10 11
M2 12 9 – 10 9
M3 – 11 14 11 7
M4 14 8 12 7 8
M5 0 0 0 0 0
Step 1:
Subtract the least element of each row with the other elements in the same row. We get-
A B C D E
M1 0 2 6 1 2
M2 3 0 ∞ 1 0
M3 ∞ 4 7 4 0
M4 7 1 5 0 1
M5 0 0 0 0 0
Step 2:
As there is zero in every column, there is no need to go with column reduction. Thus, we get the following matrix-
A B C D E
M1 0 2 6 1 2
M2 3 0 ∞ 1 0
M3 ∞ 4 7 4 0
M4 7 1 5 0 1
M5 0 0 0 0 0
As the number of lines is equal to the assigned zero, this is the optimal solution.
Hence, cost will be-
M1 →A = 9
M2 →B = 9
M3 →E = 7
M4 →D = 7
M5 →C = 0
Total = 32
Example 6.12:
In the table given below, time taken to complete different tasks has been shown. Determine the optimal solution how to assign four clerks with four tasks.
Clerks A B C D
1 4 7 5 6
2 – 8 7 4
3 3 – 5 3
4 6 6 4 3
Consider that Clerk 2 and Clerk 3 cannot be assigned to task A and B respectively.
Solution:
Step 1:
Subtract minimum value of the element of each row with the other elements of the same row, we get-
A B C D
1 0 3 1 2
2 ∞ 4 3 0
3 0 ∞ 2 0
4 3 3 1 0
Step 2:
Subtract minimum value of the element of each column with the other elements of the same column, we get-
A B C D
1 0 0 0 2
2 ∞ 1 2 0
3 0 ∞ 1 0
4 3 0 0 0
Here, we can find that the number of straight lines is equal to the number of tasks. Hence, this is the optimal solution.
1→B = 7
2→D = 4
3→A = 3
4→C = 4
Total = 18
Example 6.13:
A national car rental service’s company has surplus of car at six different cities from 1 to 6 (one at each city). From the city 7 to 12, there is a deficit of car one at each city. The distances are in miles between each city whether it is surplus or deficits are presented in a tabular form. Find out the way to dispatch the cars to minimize total mileage travelling.
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 70
Solution:
Step 1:
Subtract the minimum element of each row with the other elements of the same row-
7 8 9 10 11 12
1 16 47 14 27 0 26
2 0 7 27 43 59 28
3 0 12 33 24 5 5
4 8 13 11 15 0 6
5 3 14 13 0 4 7
6 42 0 0 20 11 30
Step 2:
Subtract the minimum element of each column with the other elements of the same column-
7 8 9 10 11 12
1 16 47 14 27 0 21 √
2 0 7 27 43 59 23
3 0 12 33 24 5 0
4 8 13 11 15 0 1
5 3 14 13 0 4 2 √
6 42 0 0 20 11 25
√
Here, number of lines = number of assignments
Thus, further reduction will take place.
Step 3:
Subtract the smallest uncovered element with the other uncovered elements. Add the same value with the elements that are present in the intersection of two lines.
7 8 9 10 11 12
1 15 46 13 26 0 20
2 0 7 27 43 60 23
3 0 12 33 24 6 0
4 7 12 10 14 0 0
5 2 14 13 0 5 2
6 42 0 0 20 11 25
Still the number of lines (5) is not equal to the value 6.
Step 4:
Repeating the previous step, we get-
7 8 9 10 11 12
1 15 39 6 26 0 20
2 0 0 20 23 60 23
3 0 5 26 24 6 0
4 7 5 3 14 0 0
5 3 7 6 0 5 2
6 49 0 0 27 19 32
As the minimum number of lines is 6, we have achieved the optimal solution. Hence, the matrix can be written as-
7 8 9 10 11 12
1 15 39 6 26 0 20
2 0 0 20 23 60 23
3 0 5 26 24 6 0
4 7 5 3 14 0 0
5 3 7 6 0 5 2
6 49 0 0 27 19 32
Row Reduction:
7 8 9 10 11 12
1 16 47 14 27 0 26
2 0 7 27 43 59 28
3 0 12 33 24 5 5
4 8 13 11 15 0 6
5 3 14 13 0 4 7
6 49 0 0 20 11 30
Column Reduction and Making Assignments:
7 8 9 10 11 12
1 16 47 14 27 0 21 √
2 0 7 27 43 59 23
3 0 12 33 24 5 0
4 8 13 11 15 0 1
5 3 14 13 0 4 2 √
6 49 0 0 20 11 25
√
Mark the unmarked row (row 4th) and look for marked zero in that column. Draw straight lines on rest of the rows.
1 →11 = 25
2 →8 = 2
3 →7 = 27
4 →12 = 43
5 →10 = 26
6 →9 = 40
Total = 190
Example 6.14:
The following table shows the weekly output of five lathes belong to five different operators:
Operator L1 L2 L3 L4 L5
P 20 22 27 32 36
Q 19 23 29 34 40
R 23 28 35 39 34
S 21 24 31 37 42
T 24 28 31 36 41
Find the maximum profit per week if the profit per piece is 25%
Solution:
The given problem is a maximization problem. We have to convert it into opportunity loss matrix. For this, subtract the maximum value with other elements of the matrix (42), we get-
Operator L1 L2 L3 L4 L5
P 22 20 15 10 6
Q 23 19 13 8 2
R 19 14 7 3 8
S 21 18 1 5 0
T 18 14 11 6 1
Step 1:
Subtract the least element of each row with the other elements of the same row, we get-
Operator L1 L2 L3 L4 L5
P 16 14 9 4 0
Q 21 17 11 6 0
R 16 11 4 0 5
S 21 18 11 5 0
T 17 13 10 5 0
Step 2:
Subtract the least element of each column with the other elements of the same column, we get-
Operator L1 L2 L3 L4 L5
P 0 3 5 4 0
Q 5 6 7 6 0
R 0 0 0 0 5
S 5 7 7 5 0
T 1 2 6 5 0
Here, minimum number of lines to cross all the zeros is 3 and it is less than 5. It is not an optimal solution.
Step 3:
Subtract the minimum uncovered element with the other uncovered elements. Add the same value to the elements at the intersection of two lines.
Operator L1 L2 L3 L4 L5
P 0 3 5 4 1
Q 4 5 6 5 0
R 0 0 0 0 6
S 4 6 6 4 0
T 0 1 5 4 0
Minimum number of lines is again less than 5.
Step 4:
Repeat the same step to get a new matrix-
Operator L1 L2 L3 L4 L5
P 0 2 4 3 1
Q 4 4 5 4 0
R 1 0 0 0 7
S 4 5 5 3 0
T 0 0 4 3 0
Here, the minimum number of lines to cross all the zeros is 4. This is again less than the required value, 5.
Step 5:
Repeat the previous step to get a new matrix-
Operator L1 L2 L3 L4 L5
P 0 2 4 3 4
Q 1 1 2 1 0
R 1 0 0 0 10
S 1 2 2 0 0
T 0 0 4 3 3
This is the optimal solution as the minimum number of lines is equal to 5.
Step 6:
Making the assignments-
Operator L1 L2 L3 L4 L5
P 0 2 4 3 4
Q 1 1 2 1 0
R 1 0 0 0 10
S 1 2 2 0 0
T 0 0 4 3 3
Therefore, it can be written as-
P →L1 = 20
Q →L2 = 40
R →L3 = 35
S →L4 = 37
L →L5 = 28
Total = 160
Hence, the maximum profit per week will be-
25 x 160 = 4,000
Example 6.15
To allot five batsmen at the five middle batting positions, the average runs scored is given in the table below (for each batsman).
Batsmen Batting Position
I II III IV V
P 40 40 35 25 50
Q 42 30 16 25 27
R 50 48 40 60 50
S 20 19 20 18 25
T 58 60 59 55 53
- Find the assignment of each batsman to get maximum number of runs
- If another batsman, U has been added in these batting positions, then find which batsman will be replaced by him? The following is his average runs-
Batting Positions I II III IV V
Average Runs 45 52 38 50 49
Solution:
- Making the assignment:
First convert the profit matrix to get opportunity cost matrix. We subtract all elements of the matrix with the highest element i.e. 60
I II III IV V
P 20 20 25 35 10
Q 18 30 44 35 33
R 10 12 20 0 10
S 40 41 40 42 35
T 2 0 1 5 7
Step 1:
Row Reduction will be given by-
I II III IV V
P 10 10 15 25 0
Q 0 12 26 17 15
R 10 12 20 0 10
S 5 6 5 7 0
T 2 0 1 5 7
Step 2:
Column Reduction to make the assignment will be given by-
I II III IV V
P 10 10 14 25 0 √
Q 0 12 25 17 15
R 10 12 19 0 10
S 5 6 4 7 0
T 2 0 0 5 7 √
√
Step 3:
Subtract the minimum uncovered element (4) from all the uncovered elements. Add the same value to the elements that are present in the intersection of two lines. We get-
I II III IV V
P 6 6 10 21 0
Q 0 12 25 17 19
R 10 12 19 0 14
S 1 2 0 3 0
T 2 0 0 5 11
Here, the number of assignment is equal to the minimum number of lines i.e. 5
P →V = 50
Q →I = 42
R →IV = 60
S →III = 20
L →II = 60
Total = 232
- A new batsmen U is introduced in the team. So a dummy position is created. We get-
Batsmen Batting Position
I II III IV V VI
P 40 40 35 25 50 0
Q 42 30 16 25 27 0
R 50 48 40 60 50 0
S 20 19 20 18 25 0
T 58 60 59 55 53 0
U 45 52 38 50 49 0
First convert this profit matrix into opportunity cost matrix. For this, subtract each element with the highest element (60).
I II III IV V VI
P 20 20 25 35 10 60
Q 18 30 44 35 33 60
R 10 12 20 0 10 60
S 40 41 40 42 35 60
T 2 0 1 5 7 60
U 7 0 14 2 3 52
Do column reduction and making the assignment-
I II III IV V VI
P 10 10 14 25 0 25
Q 0 12 25 17 15 17
R 10 12 19 0 10 35
S 5 6 4 7 0 0
T 2 0 0 5 7 35
U 7 0 13 2 3 27
P →V = 50
Q →I = 42
R →IV = 60
S →Dummy
T →III = 59
U →II = 52
Total = 263
Example 6.16:
Five teachers teach five different subjects in a small school. All the teachers are capable to teach any of these five subjects. The output of a teacher (per day) and the course coverage for each subject (in %) are given below-
Teachers 1 2 3 4 5
A 7 9 4 8 6
B 4 9 5 7 8
C 8 5 7 9 8
D 6 5 8 10 10
E 7 8 10 9 9
Course
Coverage 2 3 2 3 4
Also, if teacher D is not available, make the assignment.
Solution:
Multiply the output of teachers with coverage of course to get the resultant matrix-
Teachers 1 2 3 4 5
A 14 27 8 24 24
B 8 27 10 21 32
C 16 15 14 27 32
D 12 15 16 30 40
E 14 24 20 27 36
This tells that this problem is a maximization problem.
Subtract the largest element (40) with all the other elements to get the following matrix-
Teachers 1 2 3 4 5
A 36 13 32 16 16
B 32 13 30 19 8
C 24 25 26 13 8
D 28 25 24 10 0
E 26 16 20 13 4
Step 1:
Subtract the minimum element of each row with the other elements of the same row, we get-
Teachers 1 2 3 4 5
A 13 0 19 3 3
B 24 5 22 11 0
C 16 17 18 5 0
D 28 25 24 10 0
E 22 12 16 9 0
Step 2:
Subtract the minimum element of each column with the other elements of the same column, we get-
Teachers 1 2 3 4 5
A 0 0 3 0 3
B 11 5 6 8 0
C 3 17 2 2 0
D 15 25 8 7 0
E 9 12 0 6 0
Here, only three lines can be drawn. This is not an optimal solution.
By deduction method, we get the following matrix-
Teachers 1 2 3 4 5
A 0 0 3 0 5
B 9 3 4 6 0
C 1 15 0 0 0
D 13 23 6 5 0
E 9 12 0 6 2
Still number of lines is than the required 5. Again we follow the same procedure, we get-
Teachers 1 2 3 4 5
A 0 0 3 0 8
B 6 0 1 3 0
C 1 15 0 0 3
D 10 20 3 2 0
E 9 12 0 6 5
This is the optimal solution. Hence, making the assignment:
Teachers 1 2 3 4 5
A 0 0 3 0 8
B 6 0 1 3 0
C 1 15 0 0 3
D 10 20 3 2 0
E 9 12 0 6 5
A →1 = 14
B →2 = 27
C →4 = 27
D →5 = 40
E →3 = 20
Total = 128
Review:
- Show that the given assignment model is the special case of transportation model.
- The below table shows that five assignments are given to five operators for five different machines-
Machines Operators
I II III IV V
A 10 5 13 15 16
B 3 9 18 3 6
C 10 7 2 2 2
D 5 11 7 7 12
E 7 9 4 4 12
Assign the operators in such a manner so that the total cost will be minimized.
- Add a constant to every element whether it is in row or column to prove that the assignment with total minimization in the previous matrix form will also be the total minimization after adding the constant.
- A national car rental services owner has six extra cars (one for each city) for cities 1 to 6. The deficit of one car is in each of the cities from 7 – 12. The distance is measured in miles for the cities that are in surplus and deficits are shown in the following table. To minimize the total mileage travelled, find the solution how to dispatch each of these cars.
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
- Distinguish between assignment model and transportation model
- Four machines are allotted to four different jobs. Its setup and production times are too high for change over. The following table shows the cost of producing job on the machines in rupees.
Jobs Machines
1 2 3 4
1 5 7 11 6
2 8 5 9 6
3 4 7 10 7
4 10 4 8 3
Assign different jobs to different machines to minimize the total cost.
Six machines are located in six different places. The cost of locating these machines are given in the following table-
P1 P2 P3 P4 P5 P6
M1 20 23 18 10 16 20
M2 50 20 17 16 15 11
M3 60 30 40 55 8 7
M4 6 7 10 20 25 9
M5 18 19 28 17 60 70
M6 9 10 20 30 40 55
To determine the optimal solution, formulate the assignment as an LP model. Write in detail about the objective function, constraints and symbols that will be used. Using linear programming, find the optimal layout.
- Discuss the assignment model and indicate a method to solve the below problem.
- There are six different machines for five different jobs. Considering this problem faced by a company, following table has been given with estimated cost (hundreds of rupees).
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
Find the minimization of the total cost.
In a company, five new machines are brought to locate them in five different places. Calculate the cost of placing machines in the machine shop using the data from the below table-
Machines Jobs
1 2 3 4 5
1 15 10 25 25 10
2 1 8 10 20 2
3 8 9 17 20 10
4 14 10 25 27 15
5 10 8 25 27 12
To find how to place the machine-
- Formulate the LP model to achieve the optimal solution
- Solve this problem using the assignment technique of LP.
Solve the below 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
A team of five riders with their five horses has entered in an event (contest). The numbers of penalty points that made by each rider with his horse is mentioned in the table below-
Horses Riders
R1 R2 R3 R4 R5
H1 5 3 4 7 2
H2 2 3 7 6 5
H3 4 1 5 2 4
H4 6 8 1 2 3
H5 4 2 5 7 1
To minimize the expected loss of each team, how to allot the horses to each rider.
To determine minimum cost solution, an assignment problem has been given below with cost coefficients-
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
Three jobs have to be assigned to four machines but only one machine can get only one job. Cost of production of job on each machine is given below.
Jobs Machines
W X Y Z
A 18 24 28 32
B 8 13 17 19
C 10 15 19 22
To minimize the cost of production, find how should the jobs be assigned?
To minimize the distance traveled, you have to assign four trucks to six vacant spaces. The following has shown 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
To maximize the total expected profit, a company has to assign five jobs to five machines. The following matrix has been given-
Machines Jobs
1 2 3 4 5
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
Five jobs have to be assigned to four machinists. The expected profit for each machinist on each job is given in the table below. To get the maximum return, how the owner of this machine shop should assign the jobs. Determine which job should be declined.
Machines Jobs
1 2 3 4 5
1 6.20 7.80 5.00 10.00 8.20
2 7.10 8.40 6.10 7.30 5.90
3 8.70 9.20 11.10 7.10 8.10
4 4.80 6.40 8.70 7.70 8.00
The timetable of an airline has shown in a matrix form. Determine the pairing of flight so that minimum layover time should be at least 5 hours when away from home.
Delhi – Jaipur Jaipur – Delhi
Flight No. Depart Arrive Flight No. Depart Arrive
1 7.00 AM 8.00 AM 101 8.00 AM 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
Also, mention the town for each pair where the crew should be based.
A company operated in four different territories with its four salesmen available for the assignment. Every territory has its own potential to bring the annual sales. The below table shows the annual sales of each territory-
Territory Annual Sales (Rs)
I 60,000
II 50,000
III 40,000
IV 30,000
Each salesman has his own personal ability to sale. It has been estimated that the yearly sales proportion of the four salesman under similar condition as follows-
Salesmen Proportion
A 7
B 5
C 5
D 4
Assign the best salesman to richest territory and the next best to second richest territory and so on. Using assignment technique, also verify the answer.
- State the mathematical model of the assignment problem
- A company has five defined tasks (1, 2, 3, 4, 5) and three employees (A, B, C). It has decided to hire two employees D and E. Looking at the specialization of D and E, the personnel manager has decided to offer task 3 to its new employee D and the remaining task to employee E to maximize the total effectiveness.
The following table shows the effectiveness of the employees for different tasks.
Employees Tasks
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
Examine the decision of the personnel manager to assign task 3 to the employee D by maximizing the total effectiveness.
Which are the various steps of Hungarian method to solve assignment problems?
What do you understand by the Hungarian Assignment Method?
Explain any method of solving assignment problems. Give an example
A departmental head has to assign four tasks to four different subordinates. Considering the difficulty of each task, the efficiency of the subordinates differs. The estimate of time taken by each man is given in the below matrix-
Tasks Subordinates
I II III IV
A 8 26 17 11
B 13 28 4 26
C 38 19 18 15
D 19 26 24 10
To minimize the total man-hours, determine how to locate the tasks to each subordinate.
A car hire companyhas five cars at its five different depots a, b, c, d and e. A customer requires five cars for five different cities A, B, C, D and E. The distance between these depots and cities are given in a tabular form-
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
To minimize the distance traveled, you have to assign the cars to the customer.
By solving the following matrix, assign the jobs to the men to minimize the total time-
Men Jobs
J1 J2 J3 J4
M1 8 26 17 11
M2 13 28 4 26
M3 38 19 18 15
M4 19 26 24 10
Three customers have requested for technical assistance. Only three technicians are available at present. Below table highlights the distance between customers’ place and technicians. Assign the customers to each technician to determine the minimum cost of travel (Rs. 2 per km) by using assignment problem techniques.
Technicians Customers
I II III
A 37 58 41
B 38 92 74
C 88 55 43
The cost matrix (in ‘000 Rs) contract is given in the below matrix
Bidder Diff Weapon Subsystems
I II III IV
A 17 20 13 21
B 15 21 14 18
C 17 18 17 21
D 14 22 12 22
To minimize the cost, how should assign the four diff weapon subsystems to each bidder.
How to minimize the total cost by assigning four different contractors to four different jobs?
A B C D
X 17 20 13 21
Y 15 21 14 18
Z 17 18 17 21
L 14 22 12 22
Cost of three jobs for three machines has been given in the below matrix. To minimize the total cost, you have to assign jobs to each machine.
Jobs Machines
X Y Z
A 25 31 35
B 15 20 24
C 22 19 17
Determine the optimal solution of this maximization assignment problem.
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
Solve the following assignment problem to find the optimal solution-
Operators Jobs
1 2 3 4 5
1 6 2 5 2 6
2 2 5 8 7 7
3 7 8 6 9 8
4 6 2 3 4 5
5 9 3 8 9 7
6 4 7 4 6 8
To minimize the cost, how to assign each operator to each machine
Operators Machines
I II III IV V
A 5 5 – 2 6
B 7 4 2 3 4
C 9 3 5 – 3
D 7 2 6 7 2
E 6 5 7 9 1
Solve the following matric to get an optimal solution-
I II III IV V
A 11 17 8 16 20
B 9 7 12 6 15
C 13 16 15 12 16
D 21 24 17 28 26
E 14 10 12 11 15
Find the optimal solution for below profit matrix-
Jobs Machines
1 2 3 4 5
A 11 17 8 16 20
B 9 7 12 6 15
C 13 16 15 12 16
D 21 24 17 28 26
E 14 10 12 11 15
Five operators should be assigned in such a way to minimize the total cost by using the data from the following matrix-
Operators Machines
I II III IV V
A 5 5 – 2 6
B 7 4 2 3 4
C 9 3 5 – 3
D 7 2 6 7 –
E 6 5 7 9 1
Find the optimal solution-
A B C D E
A – 7 6 8 4
B 7 – 8 5 6
C 6 8 – 9 7
D 8 5 9 – 8
E 4 6 7 8 –
Define Unbalance Assignment Problem. Give an example to solve an assignment using HAM (Hungarian Assignment Method).
Find the optimal solution to assign four salesmen to five different territories-
Salesmen Territories
I II III IV V
A 10 15 17 14 14
B 6 18 10 12 16
C 12 5 13 13 6
D 8 11 16 10 12
Let salesman B not assign to territory II. Tell whether there will be a change in the optimal solution or not? If yes, then find the new assignment schedule.
What is the Unbalanced Assignment Problem?
What is the difference between Assignment and Transportation Problem?
Write down the different steps of Hungarian Method.
Define any assignment problem technique. Explain in brief with an example.
To minimize the total time, how to assign each man to each job. Find the optimal solution using the following matrix.
Men Jobs
J1 J2 J3 J4
M1 8 26 17 11
M2 13 18 4 26
M3 38 19 18 15
M4 19 26 24 10
Three customers need technical assistance for certain reasons. Only three technicians are available right now. The distance between customers’ place and technicians are given in the following table. Assign the customers to each technician to determine the minimum cost of travel (Rs. 2 per km) by using assignment problem techniques.
Technicians Customers
I II III
A 37 58 41
B 38 92 74
C 88 55 43
The cost matrix (in ‘000 Rs) contract is given in the below matrix
Bidder Diff Weapon Subsystems
I II III IV
A 17 20 13 21
B 15 21 14 18
C 17 18 17 21
D 14 22 12 22
To minimize the cost, how should assign the four diff weapon subsystems to each bidder.
To minimize the total cost, assign four different contractors to four different jobs. Using assignment problem method, find the optimal solution.
A B C D
X 17 20 13 21
Y 15 21 14 18
Z 17 18 17 21
L 14 22 22 22
Costs havebeen given in the below matrix. To minimize the total cost, you have to assign three jobs for three machines using assignment problem technique.
Jobs Machines
X Y Z
A 25 31 35
B 15 20 24
C 22 19 17
Any one of the operator can carried out a process on any of the four machines.It is expected to get a replacement of one existing machine by a new one. The average time required by the operator on specific machines has been shown below and the estimated time is also included for the new machine. Find out whether it is feasible to use new machine or not.
Operators Machines
I II III IV New
A 12 14 8 12 11
B 11 12 12 9 10
C 10 9 9 8 7
D 14 15 8 7 6
Find the optimal solution of the following matrix-
Persons Jobs
1 2 3 4 5
A 8 4 2 6 1
B 0 9 5 5 4
C 3 8 9 2 6
D 4 3 1 0 3
E 9 5 8 9 5
Solve the following to get an optimal solution (maximizing profits)-
Jobs Machines
A B C D E
I 32 38 40 28 40
II 40 24 28 21 36
III 41 27 33 30 37
IV 22 38 41 36 36
V 39 33 40 35 39
Assign the given jobs to each machine from the below data of cost (in Rs.)
Machines Jobs
1 2 3 4 5
1 2.5 5 1 6 1
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
A company is looking forward to purchase three different types of equipment. Several manufacturers have come forward to offer their products. The price of the equipment (in lacs of Rs.) quoted by these manufacturers have been given in a matrix form. Moreover, the company’s policy suggests purchasing only one machine from a single manufacturer.
Manufacturer s Machines
1 4 5
A 2.99 3.11 2.68
B 2.78 2.87 2.57
C 2.92 3.05 2.80
D 2.82 3.10 2.74
E 3.11 2.90 2.62
If machines of every manufacturer have the same capacity, determine the optimal solution how to purchase the best one.
A departmental head is expected to assign four tasks to four subordinates. Considering the difficulty of the tasks, the efficiency of the subordinates differs. The estimate of time required by the subordinateis givenbelow-
Tasks Subordinates
I II III IV
A 8 26 17 11
B 13 28 4 26
C 38 19 18 15
D 19 26 24 10
Determine how to locate the tasks to each subordinate to minimize the total man-hours.
A car hire company has five cars at five different depots a, b, c, d and e. A customer hires five cars for five different cities A, B, C, D and E. The distance between these depots and cities are given in a tabular form-
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
Assign the cars to the customers in such a way to minimize the distance traveled.
Find the optimal solution using the data given below-
J1 J2 J3 J4 J5
P1 27 18 X 20 21
P2 31 24 21 12 21
P3 20 17 20 X 16
P4 20 28 20 16 27
Solve the given minimization problem to find an optimal solution-
Jobs Machines
A B C D
1 12 7 9 10
2 12 5 10 11
3 8 4 9 7
4 8 6 7 5
5 10 11 9 7
Find the optimal solution by solving the below matrix-
Territory Salesmen
S1 S2 S3 S4
A 50 48 47 45
B 70 72 70 60
C 90 80 85 82
D 60 48 52 55
District-wise, the sales of five salesmen, are tabulated below. Find the optimal solution of this assignment problem.
Salesmen Districts
1 2 3 4 5
A 38 44 47 35 50
B 49 33 37 30 42
C 50 36 40 39 46
D 28 44 48 45 43
E 39 40 48 45 46
A company works with a team of four salesmen for four districts. As per the capabilities of the salesmen and nature of the districts, the company has estimated a minimum amount of profit per day (in rupees) is stated below-
Salesman Districts
1 2 3 4
A 16 10 14 11
B 14 11 15 15
C 15 15 13 12
D 13 12 14 15
Find the optimal solution to maximize the total production-
Operators Lathe Weekly Output
L1 L2 L3 L4 L5
P 20 22 27 32 36
Q 19 23 29 34 40
R 23 28 35 39 34
S 21 24 31 37 42
T 24 28 31 36 41
- Discuss assignment problems are the special case of transportation problems
- To minimize total cost, assign different jobs to different machines-
Jobs Machines
1 2 3 4
A 10 12 19 11
B 5 10 7 8
C 12 14 13 11
D 8 15 11 9
A company has to assign four machines to six different jobs. In this case, one machine should be assigned to one job only. The estimated profit is given in a tabular form-
Jobs Machines
A B C D
1 3 6 2 6
2 7 1 4 4
3 3 8 5 8
4 6 4 3 7
5 5 2 4 3
6 5 7 6 4
Find the optimal solution to get the maximize profit.
