Maximisation Assignment Problems

The Hungarian method is built to minimise. Many real problems instead ask us to maximise — assign salesmen to territories to make total profit (or sales, output, efficiency) as large as possible. We do not need a new algorithm; we simply convert the maximisation problem into an equivalent minimisation problem and then run the ordinary Hungarian method.

Two equivalent conversions (use either):

1. Subtract-from-largest (the "regret" or loss matrix). Find the single largest entry $M$ in the whole profit matrix and replace every entry $p_{ij}$ by $M - p_{ij}$. Each new entry is a loss of opportunity — how much profit we forgo at that cell compared with the best cell anywhere. Minimising total opportunity loss is exactly the same as maximising total profit.

2. Negate the matrix. Replace each $p_{ij}$ by $-p_{ij}$ and minimise; but since the Hungarian method assumes non-negative entries, method (1) is the one used in practice.

After the conversion, apply Steps 1–5 of the Hungarian method exactly as before. Crucially, the final answer — the total profit — is read from the original profit matrix, not from the converted one.