English

Solve the Following Minimal Assignment Problem and Hence Find the Minimum Value :

Advertisements
Advertisements

Question

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

 

Advertisements

Solution

  I II III IV
A 2 10 9 7
B 13 2 12 2
C 3 4 6 1
D 4 15 4 9

Subtracting minimum element from each row,
we have 

  I II III IV
A 0 8 7 5
B 11 0 10 0
C 2 3 5 0
D 0 11 0 5

Subtracting minimum element from each
Column, we have 

  I II III IV
A 0 8 7 5
B 11 0 10 0
C 2 3 5 0
D 0 11 0 5

Hence A → I, B → II, C → IV, D → III
Minimum value is 2 + 2 + 1 + 4 = 9  

shaalaa.com
  Is there an error in this question or solution?
2017-2018 (March)

APPEARS IN

Video TutorialsVIEW ALL [1]

RELATED QUESTIONS

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

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.


Fill in the blank :

An _______ is a special type of linear programming problem.


In an assignment problem, if number of column is greater than number of rows, then a dummy column is added.


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 said to be balanced if ______


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


What is the Assignment problem?


What is the difference between Assignment Problem and Transportation Problem?


A departmental head has four subordinates and four tasks to be performed. The subordinates differ in efficiency and the tasks differ in their intrinsic difficulty. His estimates of the time each man would take to perform each task is given below:

    Tasks
    1 2 3 4
Subordinates P 8 26 17 11
  Q 13 28 4 26
  R 38 19 18 15
  S 9 26 24 10

How should the tasks be allocated to subordinates so as to minimize the total manhours?


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 ______


Choose the correct alternative:

If number of sources is not equal to number of destinations, the assignment problem is called ______


Choose the correct alternative:

The purpose of a dummy row or column in an assignment problem is to


Choose the correct alternative:

In an assignment problem involving four workers and three jobs, total number of assignments possible are


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.


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`


Share
Notifications

Englishहिंदीमराठी


      Forgot password?
Use app×