Skip to content
Question 16 of 32
Q.

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:

JobMachines (Processing cost in ₹)
IIIIIIIV
P31253329
Q25242321
R19212324
S38363440
Find the optimal assignment to minimize the total processing cost.
Maharashtra MsbshseMaharashtra HSC (MSBSHSE) Board 2022Subjective· 3mImportance★★★★★
50% · 16/32 Questions
🔒 Locked · start free trial →

You're viewing a preview — the full solution, concept, methods & PYQ mapping are locked.

Start your 14-day free trial to unlock the full solution →

Applying the Hungarian method, the optimal assignment P→II,  Q→IV,  R→I,  S→IIIP\to II,\;Q\to IV,\;R\to I,\;S\to III minimises the cost at ₹99\text{₹}99.

Step 1 — Row reduction (subtract the smallest entry of each row):

Row PP (−25-25): 6,  0,  8,  46,\;0,\;8,\;4

Row QQ (−21-21): 4,  3,  2,  04,\;3,\;2,\;0

Row RR (−19-19): 0,  2,  4,  50,\;2,\;4,\;5

Row SS (−34-34): 4,  2,  0,  64,\;2,\;0,\;6

Step 2 — Column reduction: each column already contains a 00 (column minima are all 00), so the matrix is unchanged:

IIIIIIIVP6084Q4320R0245S4206\begin{array}{c|cccc} & I & II & III & IV\\ \hline P & 6 & 0 & 8 & 4\\ Q & 4 & 3 & 2 & 0\\ R & 0 & 2 & 4 & 5\\ S & 4 & 2 & 0 & 6\end{array}

Step 3 — Assign the zeros. Exactly one independent zero can be chosen in every row and column:

R→IR\to I (zero), P→IIP\to II (zero), S→IIIS\to III (zero), Q→IVQ\to IV (zero).

…

Unlock everything free for 14 days

  • Full step-by-step solutions
  • Concept-first explanations
  • Methods, shortcuts & mistakes
  • PYQ mapping + timed mock tests

Full access for 14 days. No credit card required.