The document contains 20 multiple choice questions about assignment problems. It covers topics like the number of feasible solutions and variables in assignment problems of different sizes, solving assignment problems using the Hungarian algorithm and duality, and calculating optimal objective function values for various assignment problem examples.
The document contains 20 multiple choice questions about assignment problems. It covers topics like the number of feasible solutions and variables in assignment problems of different sizes, solving assignment problems using the Hungarian algorithm and duality, and calculating optimal objective function values for various assignment problem examples.
The document contains 20 multiple choice questions about assignment problems. It covers topics like the number of feasible solutions and variables in assignment problems of different sizes, solving assignment problems using the Hungarian algorithm and duality, and calculating optimal objective function values for various assignment problem examples.
The document contains 20 multiple choice questions about assignment problems. It covers topics like the number of feasible solutions and variables in assignment problems of different sizes, solving assignment problems using the Hungarian algorithm and duality, and calculating optimal objective function values for various assignment problem examples.
1. How many feasible solutions does a 5 x 5 assignment problem have?
Ans = 5! or 120
2. How many variables does the formulation of 5 x 5 assignment problem have?
Ans = 25 For a n x n assignment problem there are n2 variables
3. How many constraints does a 5 x 5 assignment problem have?
Ans = 10 For a n x n assignment problem there are n supply constraints and n demand constraints. There are 2n constraints.
4. In a 4 x 4 assignment problem where 4 jobs are assigned to 4 machines, job 1 is
assigned to M2, job 2 to M4, Job 3 to M3. What is the fourth assignment? Ans = Job 4 to M1 The unassigned job is J4 and the unassigned machine is M1.
5. How many variables does the dual of 5 x 5 assignment problem have?
Ans = 10 An n x n assignment problem, there are n2 variables and 2n constraints. A 5 x 5 problem has 25 variables and 10 constraints. Its dual will have 25 constraints and 10 variables
6. How many constraints does the dual of the 5 x 5 assignment problem have? Ans = 25 An n x n assignment problem, there are n2 variables and 2n constraints. A 5 x 5 problem has 25 variables and 10 constraints. Its dual will have 25 constraints and 10 variables
7. The minimum cost for the following 3 x 3 assignment problem is
1 1 4 6 7 2 8 4 3 MOOC-NPTEL: Introduction to Operations Research Jan-Feb 2015 Ans = 7 The problem is a minimization problem. We do row minimum and column subtraction. The initial assignments are X23 and X11. There are 2 assignments. Lines are drawn through row 1 and column 3. Minimum θ = 1. The new allocations are X11 = X23 = X32 = 1 with cost = 1 + 2 + 4 = 7
8. Consider the assignment problem with 4 jobs and 3 machines. The job that is not assigned to any machine is 1 1 4 6 7 2 8 4 3 5 6 7 Ans = Job 4 The problem is unbalanced and we add an extra column with zero costs. Initial assignments are X34 = X11 = X23 = 1. We draw lines through rows 1, 2 and column 4. Minimum θ = 1. The assignments are again X34 = X11 = X23 = 1. We draw lines through row 1 and columns 3 and 4. Minimum θ = 2. The assignments are X23 = X44 = X11 = X32 = 1. Job 4 is assigned to the dummy column and does not get a machine.
9. Which of the following is not a step in Hungarian algorithm?
(a)Subtract row minimum from every row (b) Subtract column minimum from every column (c ) Draw lines through ticked rows and unticked columns (a) Tick unassigned rows Ans = C In Hungarian algorithm, we draw lines through unticked rows and ticked columns.
10. Solve the 4 x 4 maximization assignment problem. The maximum profit is
1 1 4 8 6 7 2 7 8 4 3 6 5 6 7 8 Ans = 30 The given problem is converted to minimization by multiplying with -1. The allocations after row and column subtraction are X11 = X22 = X31 = X43 = 1 with profit = 8 + 7 + 8 + 7 = 30
11. Consider the 3 job 4 machine assignment problem:
1 3 5 6 7 6 2 4 3 7 8 9 MOOC-NPTEL: Introduction to Operations Research Jan-Feb 2015 The machine that does not get a job in the optimum assignment is ___. The objective function value at the optimum is _____ Ans = 4, 11 The problem is balanced by adding a dummy column (job) with zero values. We do column minimum subtraction. The initial assignments are X24, X33 and X11. We draw lines through rows 1, 3 and column 4. Minimum θ = 3. The assignments in the new matrix are X33, X44, X11. We draw lines through row 1 and columns 3 and 4. Minimum θ = 1. The assignments in the new matrix are X44, X11, X22 and X33. There is alternate optima but X44 = 1 is in all the alternate solutions. Machine 4 is assigned to the dummy job and does not get a job. The cost = 1 + 7 + 3 + 0 = 11
12. Which of the following statements is not TRUE about the Assignment problem: a) It is a transportation problem b) The LP formulation will give binary solutions c) When solving, the cost matrix is square d) LP can give non integer solution sometimes Ans = d The LP solution to the assignment problem always gives a binary solution
13. Find the minimum cost corresponding to the 4 x 4 assignment problem:
20 17 22 16 32 29 33 26 26 27 29 28 40 30 35 37 Ans = 104 The initial assignments are X14, X42 and X31. We draw lines through rows 3, 4 and column 1. Minimum θ = 1. The assignments in the new matrix are X24, X42, X31. We draw lines through row 3 and columns 2 and 4. Minimum θ = 2. The assignments in the new matrix are X24, X31, X43 and X12. The cost = 17 + 26 + 26 + 35 = 104
14. Consider the following assignment problem. When you solve it by hand, the number of assignments that you get in the first iterations is ____. Ans = 3 20 17 22 16 32 29 33 26 26 27 29 28 40 30 35 37 Ans = 3. The initial assignments are X14, X42 and X31.
MOOC-NPTEL: Introduction to Operations Research
Jan-Feb 2015 15. If ui and vj represent the dual variables in the assignment formulation, the constraint set is given by a) ui + vj = Cij b) ui + vj ≥ Cij c) ui + vj ≤ Cij Ans = c
16. In the dual to the assignment problem, the dual variables are a) ≥ 0 b) ≤ 0 c) Unrestricted Ans = c. The primal constraints are equations. The dual variables are unrestricted in sign.
17. The maximum profit for the following 3 x 3 assignment problem is
1 1 4 6 7 2 8 4 3 Ans = 19 The problem is solved as minimization by multiplying with -1. The assignments are X13 = X22 = X31 = 1 with profit = 4 + 7 + 8 = 19
18. The maximum profit for the following 4x 3 assignment problem is
1 1 4 6 7 2 8 4 3 6 3 7 Ans = 22 The problem is first balanced by adding a fourth column with profit zero in all elements. It is then solved as minimization by multiplying with -1. The assignments are X14 = X22 = X31 = X43 = 1 with profit = 0 + 7 + 8 + 7 = 22
19. The minimum cost for the following 5x 5 assignment problem is
1 1 4 3 2 10 7 8 6 7 8 4 6 3 9 6 6 7 8 9 12 10 11 13 12 Ans = 28 The row minimum and column minimum are subtracted. The assignments are X34, X25, X11, X42 = X52 = 1 with cost = 1 + 7 + 3 + 6 + 11 = 28. There is alternate optima but X34 = X25 = 1 in all the solutions. MOOC-NPTEL: Introduction to Operations Research Jan-Feb 2015 20. The maximum profit for the following 4x 3 assignment problem is 1 1 4 10 7 2 x 4 6 6 3 7 Ans = 21 The problem is first balanced by adding a fourth column with profit zero in all elements. It is then solved as minimization by multiplying with -1. The assignments are X21 = X43 = X14 = X32 = 1 with profit = 10 + 7 + 0 + 4 = 21
