Scribd
Upload
489 views5 pages

Assignment Nptel

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.

Uploaded by

Vishal Kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
489 views5 pages

Assignment Nptel

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.

Uploaded by

Vishal Kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 5

MODULE-7 ASSIGNMENT

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

MOOC-NPTEL: Introduction to Operations Research


Jan-Feb 2015

You might also like