The Assignment Problem — Maximization Case

The Assignment Problem — Maximization Case

The Hungarian Method is built to minimise a cost matrix. When the table instead gives profits (or output, or any measure to be maximised), convert it first:

where $p_{ij}$ is the original profit in cell $(i,j)$ and $M$ is the largest single entry in the whole profit matrix. This converted table $c'=[c'_{ij}]$ is now a genuine minimisation problem, and applying the Hungarian Method to it gives the assignment that maximises the original profit.

Worked example

A firm can put any of three salesmen $W_1,W_2,W_3$ on any of three territories $J_1,J_2,J_3$; expected profit (₹ '000) is:

Largest entry $M=30$. Converted (loss) matrix, $c'_{ij}=30-p_{ij}$:

Row reduction (row minimums: $W_1\to0$, $W_2\to5$, $W_3\to0$):

Column reduction (column minimums: $J_1\to0$, $J_2\to0$, $J_3\to0$ — already the smallest in each column): matrix unchanged.

Cover the zeros: zeros sit at $W_1J_1$, $W_2J_3$, $W_3J_2$ — three zeros, no two sharing a row or column, so they are already independent; covering them needs exactly 3 lines $=n$ → optimal immediately, no adjustment step required. …