Assignment Problem Examples: Step-by-Step Solutions

Last updated: β€’ Sources β€’ Methodology

Assignment Problem Examples (Solved Set)

This is a lecture-style set of assignment problem examples with verified final assignments and step-by-step Hungarian method reasoning (row reduction, column reduction, and selecting independent zeros). It also includes unbalanced assignment (dummy rows/columns) and common modeling variations.

If you want the full algorithm explained with the cover/adjust loop, start with Hungarian algorithm explained. For model selection, see assignment vs transportation problem.

How to practice: Try each example yourself first, then expand to compare each reduction step and the final assignment. If you find a different assignment with the same total, that indicates multiple optima.
On this page

Quick takeaway: Hungarian method solves balanced one-to-one assignment efficiently. Rectangular matrices must be balanced with dummy rows/columns. Maximization problems can be solved via a safe conversion to minimization.

Checklist before solving

  1. Minimize or maximize? For maximize, convert to minimization (shown in Example 3).
  2. Square matrix? If not, add dummy row/column (Example 4).
  3. Any forbidden pairs? Decide penalty vs ILP/MILP (Example 5).
  4. Interpretation: ensure each row/column must be used exactly once (true assignment).

If you have extra constraints (skills, fairness, multi-period schedules), you often need a broader ILP/MILP model. Start with how to model ILP.

Worked examples

Worked example
Example 1 (3Γ—3 minimization): Hungarian steps + final assignment

Cost matrix:

      J1  J2  J3
W1     9   2   7
W2     6   4   3
W3     5   8   1

Step 1 β€” Row reduction

Row minima: W1=2, W2=3, W3=1. Subtract from each row:

      J1  J2  J3
W1     7   0   5
W2     3   1   0
W3     4   7   0

Step 2 β€” Column reduction

Column minima: J1=min(7,3,4)=3, J2=min(0,1,7)=0, J3=min(5,0,0)=0.

Subtract column minima:

      J1  J2  J3
W1     4   0   5
W2     0   1   0
W3     1   7   0

Step 3 β€” Select independent zeros (one per row/column)

  • W1 has a single zero at J2 β†’ choose W1β†’J2
  • W3 has a zero at J3 β†’ choose W3β†’J3
  • W2 then must use J1 (zero) β†’ choose W2β†’J1

Final assignment (original costs)

  • W1 β†’ J2 cost 2
  • W2 β†’ J1 cost 6
  • W3 β†’ J3 cost 1

Total cost = 2 + 6 + 1 = 9.

This example finishes after reductions because a full set of independent zeros exists immediately. For an example that needs cover/adjust iterations, see the loop demonstration in Hungarian algorithm explained.
Worked example
Example 2 (4Γ—4 minimization): Hungarian steps + verified optimal total

Cost matrix:

      J1  J2  J3  J4
W1     9   2   7   8
W2     6   4   3   7
W3     5   8   1   8
W4     7   6   9   4

Step 1 β€” Row reduction

Row minima: W1=2, W2=3, W3=1, W4=4.

      J1  J2  J3  J4
W1     7   0   5   6
W2     3   1   0   4
W3     4   7   0   7
W4     3   2   5   0

Step 2 β€” Column reduction

Column minima: J1=min(7,3,4,3)=3, J2=min(0,1,7,2)=0, J3=min(5,0,0,5)=0, J4=min(6,4,7,0)=0.

      J1  J2  J3  J4
W1     4   0   5   6
W2     0   1   0   4
W3     1   7   0   7
W4     0   2   5   0

Step 3 β€” Select independent zeros

Work systematically:

  • W1 has only one zero at J2 β†’ choose W1β†’J2
  • W3 has only one zero at J3 β†’ choose W3β†’J3
  • W2 has zeros at J1 and J3 (but J3 already used) β†’ choose W2β†’J1
  • W4 has zeros at J1 and J4 (but J1 already used) β†’ choose W4β†’J4

Final assignment (original costs)

  • W1 β†’ J2 cost 2
  • W2 β†’ J1 cost 6
  • W3 β†’ J3 cost 1
  • W4 β†’ J4 cost 4

Total cost = 2 + 6 + 1 + 4 = 13.

This correct total (13) is a good reminder: always compute the final objective back in the original matrix, not the reduced matrix.
Worked example
Example 3 (maximization): convert profit β†’ cost, solve, convert back

Profit matrix (maximize):

      J1  J2  J3
W1    10   5   9
W2     8   7   4
W3     6   9   8

Step 1 β€” Convert to minimization

Let Pmax = 10. Define cost = Pmax - profit:

      J1  J2  J3
W1     0   5   1
W2     2   3   6
W3     4   1   2

Step 2 β€” Hungarian reductions on the cost matrix

Row reduction (row minima: 0, 2, 1):

      J1  J2  J3
W1     0   5   1
W2     0   1   4
W3     3   0   1

Column reduction (column minima: J1=0, J2=0, J3=min(1,4,1)=1):

      J1  J2  J3
W1     0   5   0
W2     0   1   3
W3     3   0   0

Step 3 β€” Select independent zeros

  • W2 has only one zero at J1 β†’ choose W2β†’J1
  • W1 then must use J3 (zero) β†’ choose W1β†’J3
  • W3 then uses J2 (zero) β†’ choose W3β†’J2

Convert back to profits

  • W2 β†’ J1 profit 8
  • W1 β†’ J3 profit 9
  • W3 β†’ J2 profit 9

Maximum total profit = 8 + 9 + 9 = 26.

This example shows the full β€œconvert β†’ solve β†’ convert back” workflow, which is common in exams and real scoring assignments.
Worked example
Example 4 (unbalanced): 3 workers, 4 jobs (dummy row) with final interpretation

Rectangular cost matrix (jobs > workers):

      J1  J2  J3  J4
W1     8   6   7   9
W2     6   7   5   8
W3     7   8   6   7

Step 1 β€” Add a dummy worker W4*

Add a dummy row to make it 4Γ—4. If leaving a job unfilled has no penalty, dummy costs are 0: 

      J1  J2  J3  J4
W1     8   6   7   9
W2     6   7   5   8
W3     7   8   6   7
W4*    0   0   0   0

One optimal solution (interpretation-ready)

An optimal assignment for the real workers (with one job assigned to dummy) is:

  • W1 β†’ J2 cost 6
  • W2 β†’ J3 cost 5
  • W3 β†’ J1 cost 7
  • W4* β†’ J4 cost 0

Total cost = 6 + 5 + 7 + 0 = 18.

Interpretation

Because the dummy worker took job J4, the model’s meaning is: Job J4 is left unfilled (or outsourced / postponed), depending on your business interpretation.

Dummy penalties matter. If unfilled jobs are costly, set dummy costs to a penalty value. Full modeling guidance: unbalanced assignment problem.

Worked example
Example 5 (forbidden pairs): penalty method and when to switch to ILP

Suppose W2 cannot do J3. A common approach is to assign a large penalty to that cell so it will never be chosen. For example: 

Set c(W2,J3) = BIG, where BIG is much larger than any realistic total cost.

Why this works (and when it fails)

  • It works if a feasible assignment exists without using the forbidden cell and BIG is large enough to avoid selection.
  • It fails conceptually if you actually want β€œno feasible solution” when forbidden constraints make assignment impossible.
  • It can become numerically/interpretively messy when you have many forbidden pairs and many penalties.

If forbidden pairs are central to your modelβ€”or you have additional rulesβ€”use ILP/MILP instead: how to model ILP and ILP/MILP calculator.

Questions people ask

Questions people ask
Why do row and column reductions preserve the optimal assignment?

In a balanced assignment, every feasible solution selects exactly one entry from each row and each column. If you subtract a constant r_i from every entry in row i, then every feasible assignment’s total cost decreases by exactly Ξ£_i r_i, the same amount for all assignments. So the identity of the minimum-cost assignment does not change.

The same logic holds for column reductions. Hungarian uses these reductions to produce zeros (tight reduced costs) while preserving optimality structure.

Questions people ask
Why does Hungarian algorithm focus so much on zeros?

Zeros represent entries that are β€œas cheap as possible” under the current row/column potentials (a dual-feasible view). When Hungarian can find a set of independent zeros (one per row and column), those zeros correspond to a matching that satisfies complementary slackness conditions, which certifies optimality in the LP sense.

That’s why the algorithm alternates between (1) creating more zeros and (2) trying to pick a conflict-free set of zeros. For the full cover/adjust loop, see Hungarian algorithm explained.

Questions people ask
Can there be multiple optimal assignments?

Yes. If the reduced matrix contains multiple different independent-zero patterns, you may have multiple distinct assignments that tie for the same total. In practice this can happen when costs are symmetric, rounded, or when many entries share equal values.

Multiple optimal solutions are not β€œan error”; they’re a property of the model/data. General concept: multiple optimal solutions.

Questions people ask
How do I verify my final answer is correct?

At minimum:

  • Check feasibility: each row used once and each column used once.
  • Compute the total in the original matrix (not the reduced matrix).
  • Sanity-check by comparing against obvious alternatives (e.g., swapping two assignments) if you want extra confidence.

For a computational check, you can also implement the assignment in Python: Hungarian algorithm in Python (SciPy).

Questions people ask
What is the difference between assignment and transportation problems?

Assignment is one-to-one: all supplies and demands are exactly 1, and decisions are binary matchings. Transportation ships quantities with general supplies/demands and continuous flows.

Assignment is a special case of transportation, but the structure is strong enough that Hungarian is usually the preferred method: assignment vs transportation problem.

Questions people ask
When should I stop using Hungarian and switch to ILP/MILP?

Switch when your problem stops being β€œchoose one job per worker and one worker per job.” Examples: workers can do multiple jobs; jobs need precedence; you need shift coverage (k people per shift); fairness rules; overtime; time windows; or decisions interact.

In those cases, the assignment model becomes a building block inside a larger integer program: how to model ILP and ILP vs MILP.

What to do next

  1. Full algorithm lecture: Hungarian algorithm explained.
  2. Rectangular matrices: unbalanced assignment.
  3. Graph view: bipartite matching & assignment.
  4. Python verification: Hungarian algorithm in Python.

Disclaimer

These examples are for educational purposes. Real assignment/scheduling decisions often include additional constraints not captured by the classic assignment model (skills, fairness, coverage requirements, multiple time periods, overtime, precedence, and legal rules). Penalty methods for forbidden pairs must be chosen carefully. Always validate assumptions and results using appropriate domain constraints and tools. Read the full disclaimer.

Related guides

Hungarian Algorithm Explained Full method including the cover/adjust loop. Unbalanced Assignment Dummy rows/columns and penalty interpretation. Hungarian Algorithm in Python (SciPy) Compute/verify assignments programmatically.
Sources
  1. Kuhn (1955) β€” The Hungarian method for the assignment problem
  2. Munkres (1957) β€” Algorithms for the Assignment and Transportation Problems (SIAM)
  3. Burkard, Dell’Amico, Martello β€” Assignment Problems (SIAM book page)
  4. Wikipedia β€” Assignment problem (overview)