Machine-translated by Google. Questions are authored in English.
Top

Discussion

The optimal solution to the following assignment problem

\(J_{1}\)\(J_{2}\)\(J_{3}\)\(J_{4}\)
\(M_{1}\)10987
\(M_{2}\)3456
\(M_{3}\)2112
\(M_{4}\)4356

is given by :

  • A.\(M_{1} \rightarrow J_{3}\), \(M_{2} \rightarrow J_{2}\), \(M_{3} \rightarrow J_{1}\), \(M_{4} \rightarrow J_{4}\)
  • B.\(M_{1} \rightarrow J_{4}\), \(M_{2} \rightarrow J_{1}\), \(M_{3} \rightarrow J_{2}\), \(M_{4} - J_{3}\)
  • C.\(M_{1} \rightarrow J_{4}\), \(M_{2} \rightarrow J_{1}\), \(M_{3} - J_{3}\), \(M_{4} - J_{2}\)
  • D.\(M_{1} - J_{3}\), \(M_{2} - J_{4}\), \(M_{3} - J_{2}\), \(M_{4} - J_{1}\)

Answer: C

The optimal assignment is \(M_1 \rightarrow J_4, M_2 \rightarrow J_1, M_3 - J_3, M_4 - J_2\).

Total cost of each option:

  • A: 8 + 4 + 2 + 6 = 20
  • B: 7 + 3 + 1 + 5 = 16
  • C: 7 + 3 + 1 + 3 = 14
  • D: 8 + 6 + 1 + 4 = 19

Option C is also provably optimal. Every machine must take at least its row minimum, and the row minima are 7 (M1), 3 (M2), 1 (M3) and 3 (M4):

\[ 7 + 3 + 1 + 3 = 14 \]

No assignment can cost less than 14, and C achieves it with each machine on a different job, so it is optimal. The Hungarian method reaches the same assignment.

No comment is present. Be the first to comment.
Loading…

Post your comment

Please log in or register to post a comment.

Subject Categories

Examination Categories

About Us

ExamsRepo

Copyright © 2026 ExamsRepo . All Rights Reserved . With