Maximization to Minimization Conversion (Hungarian Method)

Last updated: • Sources • Methodology

Hungarian Method Trick: Convert Maximization (Profit) to Minimization (Cost)

The Hungarian algorithm is naturally written as a minimization method. To solve a maximization assignment (profits/outputs), you convert the profit matrix to an equivalent cost matrix, solve the minimization, then compute the final total on the original profits.

Try it directly in the Assignment Problem Maximization Calculator. For step tables (cover zeros, θ adjustment), see the Hungarian method solver.

On this page

Quick takeaway: For a profit matrix P, choose K = max(P) (maximum entry among allowed cells), then build a cost matrix C by
Cij = K − Pij.
Any assignment that maximizes total profit in P will minimize total cost in C (the chosen pairs are the same).

Why Hungarian uses minimization

Intuition

Hungarian creates zeros and finds a matching among zeros

Hungarian works by subtracting row/column minima to create zeros, then iterating with “cover zeros with minimum lines” and θ adjustments until a perfect matching is extractable. Those operations are naturally framed for minimization.

Learn the steps: Hungarian algorithm explained · cover zeros with minimum lines · θ adjustment step.

Conversion formula (C = max(P) − P)

Formula

Why the selected assignment doesn’t change

Suppose the assignment picks exactly one cell in each row and column. For an n×n problem, the converted total cost is: 

Sum(C chosen) = Σ (K − P chosen) = nK − Σ(P chosen)

Because nK is constant across all complete assignments, minimizing nK − Σ(P) is the same as maximizing Σ(P).

This is why your calculator can safely show “Total optimal profit” using your original matrix, even though it solves an internal minimization form.

Practical steps (what to do first: balance? forbid?)

Workflow

Recommended order for real problems

Step What you do Why it matters
1 If rectangular, add dummy row/column to make it square Hungarian requires a square matching model (perfect matching)
2 Apply forbidden pairs (do not treat them as normal numbers) Forbidden means “edge removed” in the bipartite graph
3 Compute K = max(P) across allowed profit cells Ensures converted costs are nonnegative and consistent
4 Convert: C = K − P for allowed cells Equivalent minimization problem
5 Solve with Hungarian, then report totals on original profits Users care about profit totals, not converted costs

Dummy interpretation: dummy row / dummy column · Forbidden feasibility: feasible vs infeasible assignment.

Common pitfalls (negative profits, forbidden pairs, dummy values)

Pitfalls

What can go wrong (and what the calculator does)

Pitfall Why it’s confusing Correct handling
Profits include negatives People assume the formula breaks It still works: choose K = max(P) even if K is negative
Forbidden pairs Users try to set a huge negative profit or huge cost Best is strict Forbidden (edge removed). For soft restrictions, see Big‑M method.
Rectangular matrices Conversion alone doesn’t fix shape Balance first using dummy rows/columns (see dummy interpretation)
Dummy value choice 0 may not match real business penalties Use penalties if “idle” or “unfilled” has a real cost (modeling choice)

Worked examples (expandable)

Worked examples

Expand only the example you need

These examples are fully computed (3! = 6 assignments) so you can see the equivalence clearly.

Example 1: 3×3 profit → cost conversion

Profit matrix P:

       T1  T2  T3
A      12   8  15
B       7  14   9
C      10  11  13

Step 1 — Maximize profit directly (enumerate)

1) A→T1, B→T2, C→T3: 12 + 14 + 13 = 39
2) A→T1, B→T3, C→T2: 12 +  9 + 11 = 32
3) A→T2, B→T1, C→T3:  8 +  7 + 13 = 28
4) A→T2, B→T3, C→T1:  8 +  9 + 10 = 27
5) A→T3, B→T1, C→T2: 15 +  7 + 11 = 33
6) A→T3, B→T2, C→T1: 15 + 14 + 10 = 39

Maximum profit = 39 (assignments #1 and #6).

Step 2 — Convert: K = max(P) = 15; C = 15 − P

       T1  T2  T3
A       3   7   0
B       8   1   6
C       5   4   2

Step 3 — Minimize cost directly (same 6 assignments)

1) 3 + 1 + 2 = 6
2) 3 + 6 + 4 = 13
3) 7 + 8 + 2 = 17
4) 7 + 6 + 5 = 18
5) 0 + 8 + 4 = 12
6) 0 + 1 + 5 = 6

Minimum cost = 6 (assignments #1 and #6), matching the same max-profit assignments. Also nK = 3×15 = 45, so profit = 45 − 6 = 39.

Example 2: Negative profits (conversion still works)

Profit matrix P:

       T1   T2   T3
W1     -2    4    1
W2      0   -1    3
W3      2    1   -3

Step 1 — Maximize profit directly

1) -2 + (-1) + (-3) = -6
2) -2 + 3 + 1 = 2
3) 4 + 0 + (-3) = 1
4) 4 + 3 + 2 = 9   ← best
5) 1 + 0 + 1 = 2
6) 1 + (-1) + 2 = 2

Maximum profit = 9 (assignment #4).

Step 2 — Convert: K = 4; C = 4 − P

       T1  T2  T3
W1      6   0   3
W2      4   5   1
W3      2   3   7

Step 3 — Minimize cost

1) 18
2) 10
3) 11
4) 3   ← best
5) 10
6) 10

Minimum cost = 3 (assignment #4). Since nK = 12, profit = 12 − 3 = 9.

Example 3: Forbidden pairs + conversion

Profit matrix P (X = forbidden):

       T1   T2   T3
W1     10    X    8
W2      7    9    6
W3      5    4   11

Step 1 — Choose K using allowed cells only

Largest allowed profit is 11, so K = 11.

Step 2 — Convert allowed cells: C = 11 − P

       T1   T2   T3
W1      1    X    3
W2      4    2    5
W3      6    7    0

Step 3 — Enumerate feasible assignments only

A) W1→T1, W2→T2, W3→T3: Profit 30 ; Cost 3  ← best
B) W1→T1, W2→T3, W3→T2: Profit 20 ; Cost 13
C) W1→T3, W2→T1, W3→T2: Profit 19 ; Cost 14
D) W1→T3, W2→T2, W3→T1: Profit 22 ; Cost 11

Conclusion: maximizing profit chooses (A), and minimizing converted cost also chooses (A).

If forbidden pairs block every perfect matching, the problem becomes infeasible: feasible vs infeasible assignment.

Check your answer (calculator + next links)

Tools

Use these pages next

Maximization Assignment Calculator Max profit/output version (Hungarian conversion internally). Hungarian Method Solver Step tables + bipartite graph visualization. Unbalanced Assignment Calculator Rectangular matrices + dummy rows/columns. Restricted Assignment Calculator Forbidden pairs + feasibility check.

Questions people ask (max→min conversion)

People ask

Why do we convert maximization to minimization for Hungarian?

Hungarian is built around creating and covering zeros after row/column reductions, which is naturally a minimization procedure. Converting profit to cost lets the same algorithm select the same assignment.

People ask

What is the conversion formula for maximization assignment?

Choose K = max(P) (over allowed cells) and compute Cij = K − Pij.

People ask

Does the final total come from the converted matrix?

No. The converted matrix is only used to find the assignment. The reported total optimal profit should be computed from the original profit matrix.

People ask

Should I convert before or after adding dummy rows/columns?

Balance first (dummy rows/columns), then convert allowed profit cells using K = max(P). Interpretation: dummy row / dummy column.

Glossary

Glossary

  • Profit matrix (P): entries represent benefits; objective is to maximize total.
  • Cost matrix (C): entries represent costs; objective is to minimize total.
  • K = max(P): constant used to flip profit ordering into cost ordering.
  • Forbidden pair: prohibited worker–task pairing (edge removed).
  • Dummy row/column: balancing technique for rectangular matrices.

Disclaimer

This page is for educational and planning purposes only. Real-world maximization may require constraints beyond a basic one-to-one model. Validate results with appropriate business rules and a production optimizer. Read our full disclaimer.

Sources