Advertisements
Advertisements
प्रश्न
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 |
Advertisements
उत्तर
| 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 |
Step 1 : Since it is a maximization problem subtract each of the element in the table from the largest element.
| Branch Manager | Monthly Business ( Rs. lakh) | |||
| A | B | C | D | |
| P | 6 | 6 | 8 | 8 |
| Q | 4 | 1 | 6 | 7 |
| R | 5 | 0 | 4 | 9 |
| S | 1 | 3 | 1 | 5 |
Step 2 : Minimum element of each row is subtracted from every element in that row.
| Branch Manager | Monthly Business ( Rs. lakh) | |||
| A | B | C | D | |
| P | 0 | 0 | 2 | 2 |
| Q | 3 | 0 | 5 | 6 |
| R | 5 | 0 | 4 | 9 |
| S | 0 | 2 | 0 | 4 |
Step 3 : Minimum element of each column is subtracted from every element in that column.
| Branch Manager | Monthly Business ( Rs. lakh) | |||
| A | B | C | D | |
| P | 0 | 0 | 2 | 0 |
| Q | 3 | 0 | 5 | 4 |
| R | 5 | 0 | 4 | 7 |
| S | 0 | 2 | 0 | 2 |
Step 4 : Zero elements are covered With minimum number of straight lines.
Step 5 : Selecting the smallest element not covered by the lines and subtracting it from each uncovered element and add it to the intersection of the lines.
Step 6 : Covering all zeros by minimum number of straight lines.
Minimum number of lines = order of matrix. so optimal solution has reached.
Step 7 : Making assignment at single zero of the row and then at single zero of the column.
The optimal assignment is
P → D
Q → A
R → B
S → C
Maximum Profit = 9 + 13 + 17 + 16 = 55 lakhs.
APPEARS IN
संबंधित प्रश्न
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 is given in the following table:
|
Jobs
|
Machines |
|||
|
P |
Q |
R |
S |
|
|
Processing Cost (Rs.)
|
||||
|
A |
31 |
25 |
33 |
29 |
|
B |
25 |
24 |
23 |
21 |
|
C |
19 |
21 |
23 |
24 |
|
D |
38 |
36 |
34 |
40 |
How should the jobs be assigned to the four machines so that the total processing cost is minimum?
Solve the following minimal assignment problem :
| Machines | A | B | C | D | E |
| M1 | 27 | 18 | ∞ | 20 | 21 |
| M2 | 31 | 24 | 21 | 12 | 17 |
| M3 | 20 | 17 | 20 | ∞ | 16 |
| M4 | 21 | 28 | 20 | 16 | 27 |
Determine `l_92 and l_93, "given that" l_91 = 97, d_91 = 38 and q_92 = 27/59`
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 | J1 | J2 | J3 | J4 | J5 | J6 |
| Machine A | 1 | 3 | 8 | 5 | 6 | 3 |
| MAchine B | 5 | 6 | 3 | 2 | 2 | 10 |
The assignment problem is said to be unbalance if ______
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:
Assignment Problem is special case of ______
Choose the correct alternative:
When an assignment problem has more than one solution, then it is ______
In an assignment problem if number of rows is greater than number of columns, then dummy ______ is added
What is the difference between Assignment Problem and Transportation Problem?
Three jobs A, B and C one to be assigned to three machines U, V and W. The processing cost for each job machine combination is shown in the matrix given below. Determine the allocation that minimizes the overall processing cost.
| Machine | ||||
| U | V | W | ||
| Jobs | A | 17 | 25 | 31 |
| B | 10 | 25 | 16 | |
| C | 12 | 14 | 11 | |
(cost is in ₹ per unit)
Assign four trucks 1, 2, 3 and 4 to vacant spaces A, B, C, D, E and F so that distance travelled is minimized. The matrix below shows the distance.
| 1 | 2 | 3 | 4 | |
| A | 4 | 7 | 3 | 7 |
| B | 8 | 2 | 5 | 5 |
| C | 4 | 9 | 6 | 9 |
| D | 7 | 5 | 4 | 8 |
| E | 6 | 3 | 5 | 4 |
| F | 6 | 8 | 7 | 3 |
Choose the correct alternative:
North – West Corner refers to ______
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 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.
