Advertisements
Advertisements
Solve the following problem :
A dairy plant has five milk tankers, I, II, III, IV and V. These milk tankers are to be used on five delivery routes A, B, C, D and E. The distances (in kms) between the dairy plant and the delivery routes are given in the following distance matrix.
I | II | III | IV | V | |
A | 150 | 120 | 175 | 180 | 200 |
B | 125 | 110 | 120 | 150 | 165 |
C | 130 | 100 | 145 | 160 | 175 |
D | 40 | 40 | 70 | 70 | 100 |
E | 45 | 25 | 60 | 70 | 95 |
How should the milk tankers be assigned to the chilling center so as to minimize the distance travelled?
Advertisements
Solution
Step 1: Row minimum
Subtract the smallest element in each row from every element in its row.
The matrix obtained is given below:
I | II | III | IV | V | |
A | 30 | 0 | 55 | 60 | 80 |
B | 15 | 0 | 10 | 40 | 55 |
C | 30 | 0 | 45 | 60 | 75 |
D | 0 | 0 | 30 | 30 | 60 |
E | 20 | 0 | 35 | 45 | 70 |
Step 2: Column minimum
Subtract the smallest element in each column of assignment matrix obtained in step 1 from every element in its column.
I | II | III | IV | V | |
A | 30 | 0 | 45 | 30 | 25 |
B | 15 | 0 | 0 | 10 | 0 |
C | 30 | 0 | 35 | 30 | 20 |
D | 0 | 0 | 20 | 0 | 5 |
E | 20 | 0 | 25 | 15 | 15 |
Step 3:
Draw minimum number of vertical and horizontal lines to cover all zeros.
First cover all rows and columns which have maximum number of zeros.
I | II | III | IV | V | |
A | 30 | 0 | 45 | 30 | 25 |
B | 15 | 0 | 0 | 10 | 0 |
C | 30 | 0 | 35 | 30 | 20 |
D | 0 | 0 | 20 | 0 | 5 |
E | 20 | 0 | 25 | 15 | 15 |
Step 4:
From step 3, minimum number of lines covering all the zeros are 3, which is less than order of matrix, i.e., 5.
∴ Select smallest element from all the uncovered elements, i.e., 15 and subtract it from all the uncovered elements and add it to the elements which lie at the intersection of two lines.
I | II | III | IV | V | |
A | 15 | 0 | 30 | 15 | 10 |
B | 15 | 15 | 0 | 10 | 0 |
C | 15 | 0 | 20 | 15 | 5 |
D | 0 | 15 | 20 | 0 | 5 |
E | 5 | 0 | 10 | 0 | 0 |
Step 5:
Draw minimum number of vertical and horizontal lines to cover all zeros.
I | II | III | IV | V | |
A | 15 | 0 | 30 | 15 | 10 |
B | 15 | 15 | 0 | 10 | 0 |
C | 15 | 0 | 20 | 15 | 5 |
D | 0 | 15 | 20 | 0 | 5 |
E | 5 | 0 | 10 | 0 | 0 |
Step 6:
From step 5, minimum number of lines covering all the zeros are 4, which is less than order of matrix, i.e., 5.
∴ Select smallest element from all the uncovered elements, i.e., 5 and subtract it from all the uncovered elements and add it to the elements which lie at the intersection of two lines.
I | II | III | IV | V | |
A | 10 | 0 | 25 | 10 | 5 |
B | 15 | 20 | 0 | 10 | 0 |
C | 10 | 0 | 15 | 10 | 0 |
D | 0 | 20 | 20 | 0 | 5 |
E | 5 | 5 | 10 | 0 | 0 |
Step 7:
Draw minimum number of vertical and horizontal lines to cover all zeros.
I | II | III | IV | V | |
A | 10 | 0 | 25 | 10 | 5 |
B | 15 | 20 | 0 | 10 | 0 |
C | 10 | 0 | 15 | 10 | 0 |
D | 0 | 20 | 20 | 0 | 5 |
E | 5 | 5 | 10 | 0 | 0 |
Step 8:
From step 7, minimum number of lines covering all the zeros are 5, which is equal to order of the matrix, i.e., 5.
∴ Select a row with exactly one zero, enclose that zero in () and cross out all zeros in its respective column.
Similarly, examine each row and column and mark the assignment ().
∴ The matrix obtained is as follows:
I | II | III | IV | V | |
A | 10 | 0 | 25 | 10 | 5 |
B | 15 | 20 | 0 | 10 | 0 |
C | 10 | 0 | 15 | 10 | 0 |
D | 0 | 20 | 20 | 0 | 5 |
E | 5 | 5 | 10 | 0 | 0 |
Step 9:
The matrix obtained in step 8 contains exactly one assignment for each row and column.
∴ Optimal assignment schedule is as follows:
Routes | Dairy Plant | Distance (kms) |
A | II | 120 |
B | III | 120 |
C | V | 175 |
D | I | 40 |
E | IV | 70 |
525 |
∴ Minimum distance travelled
= 120 + 120 + 175 + 40 + 70
= 525 kms.
APPEARS IN
RELATED QUESTIONS
Solve the following minimal assignment problem and hence find the minimum value :
I | II | III | IV | |
A | 2 | 10 | 9 | 7 |
B | 13 | 2 | 12 | 2 |
C | 3 | 4 | 6 | 1 |
D | 4 | 15 | 4 | 9 |
Suggest optimum solution to the following assignment. Problem, also find the total minimum service time.
Service Time ( in hrs.)
Counters | Salesmen | |||
A | B | C | D | |
W | 41 | 72 | 39 | 52 |
X | 22 | 29 | 49 | 65 |
Y | 27 | 39 | 60 | 51 |
Z | 45 | 50 | 48 | 52 |
Solve the following maximal assignment problem :
Branch Manager | Monthly Business ( Rs. lakh) | |||
A | B | C | D | |
P | 11 | 11 | 9 | 9 |
Q | 13 | 16 | 11 | 10 |
R | 12 | 17 | 13 | 8 |
S | 16 | 14 | 16 | 12 |
A departmental head has three jobs and four subordinates. The subordinates differ in their capabilities and the jobs differ in their work
contents. With the help of the performance matrix given below, find out which of the four subordinates should be assigned which jobs ?
Subordinates | Jobs | ||
I | II | III | |
A | 7 | 3 | 5 |
B | 2 | 7 | 4 |
C | 6 | 5 | 3 |
D | 3 | 4 | 7 |
In a factory there are six jobs to be performed each of which should go through two machines A and B in the order A - B. The processing timing (in hours) for the jobs arc given here. You are required to determine the sequence for performing the jobs that would minimize the total elapsed time T. What is the value of T? Also find the idle time for machines · A and B.
Jobs | J_{1} | J_{2} | J_{3} | J_{4} | J_{5} | J_{6} |
Machine A | 1 | 3 | 8 | 5 | 6 | 3 |
MAchine B | 5 | 6 | 3 | 2 | 2 | 10 |
A job production unit has four jobs A, B, C, D which can be manufactured on each of the four machines P, Q, R and S. The processing cost of each job for each machine is given in the following table:
Jobs | Machines (Processing Cost in ₹) |
|||
P | Q | R | S | |
A | 31 | 25 | 33 | 29 |
B | 25 | 24 | 23 | 21 |
C | 19 | 21 | 23 | 24 |
D | 38 | 36 | 34 | 40 |
Find the optimal assignment to minimize the total processing cost.
Five wagons are available at stations 1, 2, 3, 4, and 5. These are required at 5 stations I, II, III, IV, and V. The mileage between various stations are given in the table below. How should the wagons be transported so as to minimize the mileage covered?
I | II | III | IV | V | |
1 | 10 | 5 | 9 | 18 | 11 |
2 | 13 | 9 | 6 | 12 | 14 |
3 | 3 | 2 | 4 | 4 | 5 |
4 | 18 | 9 | 12 | 17 | 15 |
5 | 11 | 6 | 14 | 19 | 10 |
Five different machines can do any of the five required jobs, with different profits resulting from each assignment as shown below:
Job | Machines (Profit in ₹) | ||||
A | B | C | D | E | |
1 | 30 | 37 | 40 | 28 | 40 |
2 | 40 | 24 | 27 | 21 | 36 |
3 | 40 | 32 | 33 | 30 | 35 |
4 | 25 | 38 | 40 | 36 | 36 |
5 | 29 | 62 | 41 | 34 | 39 |
Find the optimal assignment schedule.
The assignment problem is said to be unbalance if ______
The assignment problem is said to be balanced if ______.
Choose the correct alternative :
The assignment problem is said to be balanced if it is a ______.
Choose the correct alternative :
In an assignment problem if number of rows is greater than number of columns then
Fill in the blank :
When an assignment problem has more than one solution, then it is _______ optimal solution.
Fill in the blank :
An _______ is a special type of linear programming problem.
State whether the following is True or False :
In assignment problem, each facility is capable of performing each task.
Solve the following problem :
A plant manager has four subordinates, and four tasks to be performed. The subordinates differ in efficiency and the tasks differ in their intrinsic difficulty. This estimate of the time each man would take to perform each task is given in the effectiveness matrix below.
I | II | III | IV | |
A | 7 | 25 | 26 | 10 |
B | 12 | 27 | 3 | 25 |
C | 37 | 18 | 17 | 14 |
D | 18 | 25 | 23 | 9 |
How should the tasks be allocated, one to a man, as to minimize the total man hours?
Choose the correct alternative:
The assignment problem is generally defined as a problem of ______
Choose the correct alternative:
Assignment Problem is special case of ______
Choose the correct alternative:
When an assignment problem has more than one solution, then it is ______
Choose the correct alternative:
The assignment problem is said to be balanced if ______
If the given matrix is ______ matrix, the assignment problem is called balanced problem
In an assignment problem if number of rows is greater than number of columns, then dummy ______ is added
State whether the following statement is True or False:
The objective of an assignment problem is to assign number of jobs to equal number of persons at maximum cost
State whether the following statement is True or False:
In assignment problem, if number of columns is greater than number of rows, then a dummy row is added
State whether the following statement is True or False:
In assignment problem each worker or machine is assigned only one job
What is the Assignment problem?
Give mathematical form of Assignment problem
A computer centre has got three expert programmers. The centre needs three application programmes to be developed. The head of the computer centre, after studying carefully the programmes to be developed, estimates the computer time in minitues required by the experts to the application programme as follows.
Programmers | ||||
P | Q | R | ||
Programmers | 1 | 120 | 100 | 80 |
2 | 80 | 90 | 110 | |
3 | 110 | 140 | 120 |
Assign the programmers to the programme in such a way that the total computer time is least.
Find the optimal solution for the assignment problem with the following cost matrix.
Area | |||||
1 | 2 | 3 | 4 | ||
P | 11 | 17 | 8 | 16 | |
Salesman | Q | 9 | 7 | 12 | 6 |
R | 13 | 16 | 15 | 12 | |
S | 14 | 10 | 12 | 11 |
Choose the correct alternative:
Number of basic allocation in any row or column in an assignment problem can be
Choose the correct alternative:
North – West Corner refers to ______
Choose the correct alternative:
The solution for an assignment problem is optimal if
Choose the correct alternative:
In an assignment problem involving four workers and three jobs, total number of assignments possible are
A car hire company has one car at each of five depots a, b, c, d and e. A customer in each of the fine towers A, B, C, D and E requires a car. The distance (in miles) between the depots (origins) and the towers(destinations) where the customers 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 the cars be assigned to the customers so as to minimize the distance travelled?
A natural truck-rental service has a surplus of one truck in each of the cities 1, 2, 3, 4, 5 and 6 and a deficit of one truck in each of the cities 7, 8, 9, 10, 11 and 12. The distance(in kilometers) between the cities with a surplus and the cities with a deficit are displayed below:
To | |||||||
7 | 8 | 9 | 10 | 11 | 12 | ||
From | 1 | 31 | 62 | 29 | 42 | 15 | 41 |
2 | 12 | 19 | 39 | 55 | 71 | 40 | |
3 | 17 | 29 | 50 | 41 | 22 | 22 | |
4 | 35 | 40 | 38 | 42 | 27 | 33 | |
5 | 19 | 30 | 29 | 16 | 20 | 33 | |
6 | 72 | 30 | 30 | 50 | 41 | 20 |
How should the truck be dispersed so as to minimize the total distance travelled?
A dairy plant has five milk tankers, I, II, III, IV and V. Three milk tankers are to be used on five delivery routes A, B, C, D and E. The distances (in kms) between the dairy plant and the delivery routes are given in the following distance matrix.
I | II | III | IV | V | |
A | 150 | 120 | 175 | 180 | 200 |
B | 125 | 110 | 120 | 150 | 165 |
C | 130 | 100 | 145 | 160 | 170 |
D | 40 | 40 | 70 | 70 | 100 |
E | 45 | 25 | 60 | 70 | 95 |
How should the milk tankers be assigned to the chilling center so as to minimize the distance travelled?
A job production unit has four jobs P, Q, R, and S which can be manufactured on each of the four machines I, II, III, and IV. The processing cost of each job for each machine is given in the following table:
Job | Machines (Processing cost in ₹) |
|||
I | II | III | IV | |
P | 31 | 25 | 33 | 29 |
Q | 25 | 24 | 23 | 21 |
R | 19 | 21 | 23 | 24 |
S | 38 | 36 | 34 | 40 |
Find the optimal assignment to minimize the total processing cost.
A department store has four workers to pack goods. The times (in minutes) required for each worker to complete the packings per item sold is given below. How should the manager of the store assign the jobs to the workers, so as to minimize the total time of packing?
Workers | Packing of | |||
Books | Toys | Crockery | Cutlery | |
A | 3 | 11 | 10 | 8 |
B | 13 | 2 | 12 | 12 |
C | 3 | 4 | 6 | 1 |
D | 4 | 15 | 4 | 9 |
Five wagons are available at stations 1, 2, 3, 4 and 5. These are required at 5 stations I, II, III, IV and V. The mileage between various stations are given in the table below. How should the wagons be transported so as to minimize the mileage covered?
I | II | III | IV | V | |
1 | 10 | 5 | 9 | 18 | 11 |
2 | 13 | 9 | 6 | 12 | 14 |
3 | 7 | 2 | 4 | 4 | 5 |
4 | 18 | 9 | 12 | 17 | 15 |
5 | 11 | 6 | 14 | 19 | 10 |
A job production unit has four jobs P, Q, R, S which can be manufactured on each of the four machines I, II, III and IV. The processing cost of each job for each machine is given in the following table :
Job | Machines (Processing cost in ₹) |
|||
I | II | III | IV | |
P | 31 | 25 | 33 | 29 |
Q | 25 | 24 | 23 | 21 |
R | 19 | 21 | 23 | 24 |
S | 38 | 36 | 34 | 40 |
Complete the following activity to find the optimal assignment to minimize the total processing cost.
Solution:
Step 1: Subtract the smallest element in each row from every element of it. New assignment matrix is obtained as follows :
Job | Machines (Processing cost in ₹) |
|||
I | II | III | IV | |
P | 6 | 0 | 8 | 4 |
Q | 4 | 3 | 2 | 0 |
R | 0 | 2 | 4 | 5 |
S | 4 | 2 | 0 | 6 |
Step 2: Subtract the smallest element in each column from every element of it. New assignment matrix is obtained as above, because each column in it contains one zero.
Step 3: Draw minimum number of vertical and horizontal lines to cover all zeros:
Job | Machines (Processing cost in ₹) |
|||
I | II | III | IV | |
P | 6 | 0 | 8 | 4 |
Q | 4 | 3 | 2 | 0 |
R | 0 | 2 | 4 | 5 |
S | 4 | 2 | 0 | 6 |
Step 4: From step 3, as the minimum number of straight lines required to cover all zeros in the assignment matrix equals the number of rows/columns. Optimal solution has reached.
Examine the rows one by one starting with the first row with exactly one zero is found. Mark the zero by enclosing it in (`square`), indicating assignment of the job. Cross all the zeros in the same column. This step is shown in the following table :
Job | Machines (Processing cost in ₹) |
|||
I | II | III | IV | |
P | 6 | 0 | 8 | 4 |
Q | 4 | 3 | 2 | 0 |
R | 0 | 2 | 4 | 5 |
S | 4 | 2 | 0 | 6 |
Step 5: It is observed that all the zeros are assigned and each row and each column contains exactly one assignment. Hence, the optimal (minimum) assignment schedule is :
Job | Machine | Min.cost |
P | II | `square` |
Q | `square` | 21 |
R | I | `square` |
S | III | 34 |
Hence, total (minimum) processing cost = 25 + 21 + 19 + 34 = ₹`square`
A plant manager has four subordinates and four tasks to perform. The subordinates differ in efficiency and task differ in their intrinsic difficulty. Estimates of the time subordinate would take to perform tasks are given in the following table:
I | II | III | IV | |
A | 3 | 11 | 10 | 8 |
B | 13 | 2 | 12 | 2 |
C | 3 | 4 | 6 | 1 |
D | 4 | 15 | 4 | 9 |
Complete the following activity to allocate tasks to subordinates to minimize total time.
Solution:
Step I: Subtract the smallest element of each row from every element of that row:
I | II | III | IV | |
A | 0 | 8 | 7 | 5 |
B | 11 | 0 | 10 | 0 |
C | 2 | 3 | 5 | 0 |
D | 0 | 11 | 0 | 5 |
Step II: Since all column minimums are zero, no need to subtract anything from columns.
Step III: Draw the minimum number of lines to cover all zeros.
I | II | III | IV | |
A | 0 | 8 | 7 | 5 |
B | 11 | 0 | 10 | 0 |
C | 2 | 3 | 5 | 0 |
D | 0 | 11 | 0 | 5 |
Since minimum number of lines = order of matrix, optimal solution has been reached
Optimal assignment is A →`square` B →`square`
C →IV D →`square`
Total minimum time = `square` hours.