Skip to content

Strategic Cost Management · Assignment

Assignment Problem: Formulation, Assumptions and Types

Updated 11 October 2026 · Fact-checked

The assignment problem matches n workers to n jobs, one each, so that total cost is the lowest (or total profit the highest). It is a special case of the transportation problem. To solve it, build the n × n cost matrix, check it is balanced, add dummy rows or columns if not, then apply the Hungarian method.

Understand Assignment Problem Formulation and Basics

An assignment problem asks: you have some persons (or machines, vehicles, salesmen) and an equal number of jobs (or territories, routes). Each person does exactly one job and each job is done by exactly one person. The cost of each person-job pair is known. You must choose the pairing with the least total cost.

It is a special case of the transportation problem. Think of persons as sources and jobs as destinations. Every supply is 1 and every demand is 1. So the number of sources equals the number of destinations, and each allocation is either 0 or 1.

Because supply and demand are all 1, a general transportation method is wasteful. The solution has only n allocations in an n × n matrix, so many basic variables would be degenerate. That is why we use a dedicated method, the Hungarian method, covered in its own topic.

A problem is balanced when the number of persons equals the number of jobs (a square matrix). It is unbalanced when they differ. You balance it by adding dummy rows or columns with zero cost, so the matrix becomes square. A job given to a dummy person is left undone. A person given a dummy job stays idle.

The objective can be minimisation (cost, time, distance) or maximisation (profit, sales, efficiency). The formulation is the same; only the objective changes.

Key rules to remember

Decision variable
xij = 1 if person i is assigned to job j; xij = 0 otherwise
Each xij can only be 0 or 1.
Objective function
Minimise Z = Σi Σj cij · xij (i, j = 1 to n)
cij is the cost of assigning person i to job j. Use Maximise for profit matrices.
Row constraints
Σj xij = 1 for every person i
Each person gets exactly one job.
Column constraints
Σi xij = 1 for every job j
Each job is done by exactly one person.
Balanced condition
Number of rows = number of columns
If not equal, add dummy rows or columns with zero cost/profit.
Number of allocations
Optimal assignment has n allocations in an n × n matrix
Use this to check that your final answer is complete.

How to solve Assignment Problem Formulation and Basics questions

Use this order for any formulation or basics question on the assignment problem.

  1. 1Identify what are the persons (rows) and what are the jobs (columns). Note whether the data is cost or profit.
  2. 2Write the n × n matrix. Count rows and columns.
  3. 3If rows and columns differ, add dummy rows or columns with zero entries to make it square. Dummy count = difference.
  4. 4Define xij as 1 if person i is assigned to job j, else 0.
  5. 5Write the objective: minimise Σ cij xij for cost, or maximise for profit.
  6. 6Write the constraints: each row sums to 1 and each column sums to 1, with xij = 0 or 1.
  7. 7State the assumptions that apply, such as one job per person and a fixed known cost for each pair.
  8. 8If asked to solve, apply the Hungarian method and verify there are exactly n allocations.

Quickest way: Balance first, then write the model

When to use it: Use in 2-mark MCQs and short formulation questions where time is tight.

  1. Count rows and columns. If equal, it is balanced.
  2. If unequal, the dummy needed equals the difference, added on the smaller side.
  3. Dummy cost is zero, so the dummy row or column does not change the optimal real assignment.
  4. For formulation, write only three lines: objective, row constraints, column constraints, plus xij ∈ {0,1}.
  5. For transportation versus assignment, remember: all supplies and demands are 1, and the matrix is square.

Common mistakes in Assignment Problem Formulation and Basics

  • Solving an unbalanced matrix without adding a dummy row or column.

    Students start the Hungarian steps straight away.

    Fix: Always count rows and columns first. Add dummies until the matrix is square.

  • Putting the dummy on the wrong side.

    Confusion about which side is short.

    Fix: Add the dummy to the side that has fewer entries. Fewer persons than jobs means a dummy row.

  • Giving dummy cells a non-zero cost.

    Students copy values from other cells.

    Fix: Dummy cost or profit is zero, unless the question gives a penalty.

  • Forgetting xij is 0 or 1 and writing xij ≥ 0 only.

    Carrying over transportation or LPP habits.

    Fix: State xij = 0 or 1 and both row and column sum equal to 1.

  • Saying assignment and transportation differ only in size.

    Memorised answer is incomplete.

    Fix: Mention all supplies and demands equal 1, a square matrix, one-to-one allocation, and a specialised method.

  • Reporting a person as doing a dummy job as real work.

    Dummy results are not interpreted.

    Fix: Say the person assigned to a dummy job is idle, or the job given to a dummy person is not done.

Worked examples

Example 1

Four operators A, B, C, D are to be assigned to four machines M1 to M4, one each. Write the mathematical formulation to minimise total cost, where cij is the cost of operator i on machine j.

Show the solution
  1. Rows are operators and columns are machines. The matrix is 4 × 4, so it is balanced.
  2. Let xij = 1 if operator i is assigned to machine j, otherwise 0.
  3. Objective: Minimise Z = Σ (i = 1 to 4) Σ (j = 1 to 4) cij · xij.
  4. Each operator gets one machine: Σj xij = 1 for i = 1, 2, 3, 4.
  5. Each machine gets one operator: Σi xij = 1 for j = 1, 2, 3, 4.
  6. Non-negativity and integer condition: xij = 0 or 1.

Answer: Minimise Z = Σ Σ cij xij subject to Σj xij = 1 for each operator, Σi xij = 1 for each machine, and xij ∈ {0, 1}.

Example 2

A firm has 3 salesmen and 5 territories. Expected monthly sales (₹ in thousands) of each salesman in each territory are known, and the firm wants maximum sales with one territory per salesman. Is the problem balanced? How will you make it balanced and what does the result mean?

Show the solution
  1. Rows = 3 salesmen, columns = 5 territories. Rows ≠ columns, so the problem is unbalanced.
  2. Difference = 5 − 3 = 2, so add 2 dummy rows (dummy salesmen).
  3. Fill each dummy row with zero sales in all five territories.
  4. The matrix is now 5 × 5, so the Hungarian method can be applied, with the objective set to maximise.
  5. Interpretation: the 3 real salesmen get 3 territories. Two territories are assigned to dummy salesmen, so they stay uncovered.

Answer: The problem is unbalanced. Add two dummy salesmen with zero sales to form a 5 × 5 matrix. After solving, two territories assigned to dummies remain without a salesman.

Exam tips

  • In MCQs, check if the matrix is square first. Many questions test only this.
  • For 'difference between transportation and assignment', write four points: supply and demand of 1, square matrix, one-to-one allocation, and the Hungarian method versus MODI.
  • Write the full formulation neatly: objective, two sets of constraints, and xij ∈ {0,1}. Marks are given for each part.
  • For maximisation, state the objective as Maximise Z, and say the matrix will be converted later when solving.
  • After adding a dummy, always explain what it means in business terms.

Practice questions from Assignment

Assignment Problem Formulation and Basics in other exams

The same ground in other exams, if you are preparing for more than one or want another angle on it.

Assignment Problem Formulation and Basics: frequently asked questions

Why is the assignment problem a special case of the transportation problem?

Because it has the same structure, with sources, destinations and costs. The difference is that every supply and demand equals 1, and the number of sources equals the number of destinations. Each allocation is therefore 0 or 1.

What is a balanced and unbalanced assignment problem?

A balanced problem has equal numbers of persons and jobs, giving a square matrix. An unbalanced problem has unequal numbers. You add dummy rows or columns with zero cost to make it square.

What are the assumptions of the assignment problem?

Each person does exactly one job and each job is done by exactly one person. The cost of every person-job pair is known and fixed. The number of persons equals the number of jobs after balancing, and the objective is to minimise total cost or maximise total profit.

Can I use the transportation method to solve an assignment problem?

Yes, it can be done because the assignment problem is a special case. But it gives many degenerate solutions and takes longer. The Hungarian method is faster and is the expected method in the exam.