Assignment Problems Questions and Answers

Q: Consider the following assignment problemJobs / MachinesABCDI10251520II1530515III35201224IV17252420The solution to this problem is given by :

The optimal assignment is I → A, II → C, III → B, IV → D.Its total cost is the lowest possible:\[ 10 + 5 + 20 + 20 = 55 \]The Hungarian method (or checking all 24 assignments) confirms that no other assignment costs less; the next best cost 62. The other options cost more: I → A, II → B, III → C, IV → D costs 10 + 30 + 12 + 20 = 72; I → B, II → A, III → C, IV → D costs 25 + 15 + 12 + 20 = 72; and I → B, II → C, III → A, IV → D costs 25 + 5 + 35 + 20 = 85.

Q: Consider the following assignment cost matrix :Machines / JobsJ1J2J3J4M110978M25877M35465M42345The optimal cost of assignment is :

The optimal cost is 20.Hungarian method. Subtract each row's minimum (7, 5, 4, 2), then each column's minimum (0, 0, 0, 1). That removes 19 in total, so no assignment can cost less than 19.In the reduced matrix, M2 and M4 both have their only zero in column J1, so a complete assignment of zeros is impossible. Covering the zeros and adjusting by the smallest uncovered value adds one more unit, giving 20, and then a full set of independent zeros exists:\[ \begin{aligned} & M_{1} \to J_{3} = 7,\ M_{2} \to J_{1} = 5 \\ & M_{3} \to J_{4} = 5,\ M_{4} \to J_{2} = 3 \\ & \text{Total} = 7 + 5 + 5 + 3 = 20 \end{aligned} \]Checking every one of the 24 assignments confirms that none costs less than 20, so 18 is impossible, and 24 and 26 are feasible but not optimal.

Q: The assignment cost of assigning any one operator to any one machine is given in the following table :MachinesOperatorsIIIIIIIVU1051315V39183W10732X51197The optimal assignment is :

The optimal assignment is U \(\to\) II, V \(\to\) IV, W \(\to\) III, X \(\to\) I, at a total cost of 16.Hungarian method. Subtract each row minimum (5, 3, 2, 5):U: 5, 0, 8, 10; V: 0, 6, 15, 0; W: 8, 5, 1, 0; X: 0, 6, 4, 2.Column minima are 0, 0, 1, 0; subtracting 1 from column III gives U: 5, 0, 7, 10; V: 0, 6, 14, 0; W: 8, 5, 0, 0; X: 0, 6, 3, 2. A full set of independent zeros is U-II, V-IV, W-III, X-I, so this assignment is optimal, with cost \(5 + 3 + 3 + 5 = 16\) (the total reduction \(15 + 1\)).The other options cost far more: U-II, V-III, W-I, X-IV costs \(5 + 18 + 10 + 7 = 40\); U-III, V-IV, W-II, X-I costs \(13 + 3 + 7 + 5 = 28\); U-IV, V-II, W-III, X-I costs \(15 + 9 + 3 + 5 = 32\).

Q: The Hungarian method for the assignment problem is based on the fact that :

The Hungarian method rests on the fact that the optimal assignment is not affected by adding or subtracting a constant from any row or column.Adding or subtracting a constant from every entry of a row (or column) changes the cost of every complete assignment by exactly that constant, because every assignment uses exactly one cell in each row and column. The ranking of assignments, and so the optimum, stays the same. The method uses this to reduce rows and columns until enough zeros appear.Option A states only the subtraction half of the theorem. Option B is wrong because the objective value does change, by the constant. Option D misdescribes the procedure: entries are reduced row by row and column by column, not one at a time.

Q: Assign the programmers U, V, W to the programmes I, II, III in such way that the total computer time is minimum. The estimated computer time required by the programmers to execute the programmes is given in the table.Programmes / ProgrammersUVWI12010080II8090110III110140120The optimal assignment is :

The optimal assignment is I → W, II → V, III → U, with total time 280.With three programmers there are only six assignments, so they can be compared directly:Assignment (I, II, III)TotalU, V, W120 + 90 + 120 = 330U, W, V120 + 110 + 140 = 370V, U, W100 + 80 + 120 = 300V, W, U100 + 110 + 110 = 320W, U, V80 + 80 + 140 = 300W, V, U80 + 90 + 110 = 280The Hungarian method gives the same result. Option B costs 300 and option C 370, and an optimal assignment always exists for a square cost table, so D is wrong.

Consider the following assignment problem

Jobs / Machines	A	B	C	D
I	10	25	15	20
II	15	30	5	15
III	35	20	12	24
IV	17	25	24	20

The solution to this problem is given by :

A.I → A, II → C, III → B, IV → D
B.I → A, II → B, III → C, IV → D
C.I → B, II → A, III → C, IV → D
D.I → B, II → C, III → A, IV → D

Exam Year(s)

MH SET - 2018, SET Exam - 2018,

Answer: A

The optimal assignment is I → A, II → C, III → B, IV → D.

Its total cost is the lowest possible:

\[ 10 + 5 + 20 + 20 = 55 \]

The Hungarian method (or checking all 24 assignments) confirms that no other assignment costs less; the next best cost 62. The other options cost more: I → A, II → B, III → C, IV → D costs 10 + 30 + 12 + 20 = 72; I → B, II → A, III → C, IV → D costs 25 + 15 + 12 + 20 = 72; and I → B, II → C, III → A, IV → D costs 25 + 5 + 35 + 20 = 85.

Discuss in Forum

Consider the following assignment cost matrix :

Machines / Jobs	J1	J2	J3	J4
M1	10	9	7	8
M2	5	8	7	7
M3	5	4	6	5
M4	2	3	4	5

The optimal cost of assignment is :

A.24
B.26
C.20
D.18

Exam Year(s)

MH SET - 2019, SET Exam - 2019,

Answer: C

The optimal cost is 20.

Hungarian method. Subtract each row's minimum (7, 5, 4, 2), then each column's minimum (0, 0, 0, 1). That removes 19 in total, so no assignment can cost less than 19.

In the reduced matrix, M2 and M4 both have their only zero in column J1, so a complete assignment of zeros is impossible. Covering the zeros and adjusting by the smallest uncovered value adds one more unit, giving 20, and then a full set of independent zeros exists:

\[ \begin{aligned} & M_{1} \to J_{3} = 7,\ M_{2} \to J_{1} = 5 \\ & M_{3} \to J_{4} = 5,\ M_{4} \to J_{2} = 3 \\ & \text{Total} = 7 + 5 + 5 + 3 = 20 \end{aligned} \]

Checking every one of the 24 assignments confirms that none costs less than 20, so 18 is impossible, and 24 and 26 are feasible but not optimal.

Discuss in Forum

The assignment cost of assigning any one operator to any one machine is given in the following table :

Machines	Operators
Machines	I	II	III	IV
U	10	5	13	15
V	3	9	18	3
W	10	7	3	2
X	5	11	9	7

The optimal assignment is :

A.U \(\to\) II, V \(\to\) III, W \(\to\) I, X \(\to\) IV
B.U \(\to\) II, V \(\to\) IV, W \(\to\) III, X \(\to\) I
C.U \(\to\) III, V \(\to\) IV, W \(\to\) II, X \(\to\) I
D.U \(\to\) IV, V \(\to\) II, W \(\to\) III, X \(\to\) I

Exam Year(s)

MH SET - 2019, SET Exam - 2019,

Answer: B

The optimal assignment is U \(\to\) II, V \(\to\) IV, W \(\to\) III, X \(\to\) I, at a total cost of 16.

Hungarian method. Subtract each row minimum (5, 3, 2, 5):

U: 5, 0, 8, 10; V: 0, 6, 15, 0; W: 8, 5, 1, 0; X: 0, 6, 4, 2.

Column minima are 0, 0, 1, 0; subtracting 1 from column III gives U: 5, 0, 7, 10; V: 0, 6, 14, 0; W: 8, 5, 0, 0; X: 0, 6, 3, 2. A full set of independent zeros is U-II, V-IV, W-III, X-I, so this assignment is optimal, with cost \(5 + 3 + 3 + 5 = 16\) (the total reduction \(15 + 1\)).

The other options cost far more: U-II, V-III, W-I, X-IV costs \(5 + 18 + 10 + 7 = 40\); U-III, V-IV, W-II, X-I costs \(13 + 3 + 7 + 5 = 28\); U-IV, V-II, W-III, X-I costs \(15 + 9 + 3 + 5 = 32\).

Discuss in Forum

The Hungarian method for the assignment problem is based on the fact that :

A.The optimal assignment is not affected if a constant is subtracted from any row or column
B.The value of the objective function is not affected by adding or subtracting a constant from any row or column
C.The optimal assignment is not affected by adding or subtracting a constant from any row or column
D.The optimal assignment is not affected if each entry in the cost matrix is treated separately to obtain sufficient number of zeros

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

Answer: C

The Hungarian method rests on the fact that the optimal assignment is not affected by adding or subtracting a constant from any row or column.

Adding or subtracting a constant from every entry of a row (or column) changes the cost of every complete assignment by exactly that constant, because every assignment uses exactly one cell in each row and column. The ranking of assignments, and so the optimum, stays the same. The method uses this to reduce rows and columns until enough zeros appear.

Option A states only the subtraction half of the theorem. Option B is wrong because the objective value does change, by the constant. Option D misdescribes the procedure: entries are reduced row by row and column by column, not one at a time.

Discuss in Forum

Assign the programmers U, V, W to the programmes I, II, III in such way that the total computer time is minimum. The estimated computer time required by the programmers to execute the programmes is given in the table.

Programmes / Programmers	U	V	W
I	120	100	80
II	80	90	110
III	110	140	120

The optimal assignment is :

A.\(I \to W\), \(\mathrm{II} \to V\), \(\mathrm{III} \to U\)
B.\(I \to V\), \(\mathrm{II} \to U\), \(\mathrm{III} \to W\)
C.\(I \to U\), \(\mathrm{II} \to W\), \(\mathrm{III} \to V\)
D.Optimal assignment cannot be done

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

Answer: A

The optimal assignment is I → W, II → V, III → U, with total time 280.

With three programmers there are only six assignments, so they can be compared directly:

Assignment (I, II, III)	Total
U, V, W	120 + 90 + 120 = 330
U, W, V	120 + 110 + 140 = 370
V, U, W	100 + 80 + 120 = 300
V, W, U	100 + 110 + 110 = 320
W, U, V	80 + 80 + 140 = 300
W, V, U	80 + 90 + 110 = 280

The Hungarian method gives the same result. Option B costs 300 and option C 370, and an optimal assignment always exists for a square cost table, so D is wrong.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Assignment Problems Questions and Answers || Assignment Problems MCQ Questions and Answers || Assignment Problems GK Questions and Answers || Assignment Problems GK MCQ Questions || Assignment Problems Multiple Choice Questions and Answers || Assignment Problems GK || GK on Assignment Problems || Operations Research Questions and Answers || Operations Research MCQ Questions and Answers || Operations Research GK Questions and Answers || GK on Operations Research

Assignment Problems Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications