Skip to content

CMA Final · Strategic Cost Management

Assignment Problem for CMA Final Strategic Cost Management

An assignment problem matches n jobs to n workers or machines, one each, so that total cost is minimum or total profit is maximum. You solve it with the Hungarian method: reduce rows and columns, cover zeros with minimum lines, adjust, and repeat until an optimal assignment of zeros exists.

What this chapter covers

The Assignment chapter in Strategic Cost Management deals with one-to-one allocation. You have a set of jobs, a set of people or machines, and a cost, time or profit for each pairing. You must choose the pairing that gives the best total. It is a special case of the transportation problem in which every supply and demand equals 1.

The chapter has a clear ladder. You first learn to read the problem and build the cost matrix. Then you learn the Hungarian method for minimization. After that you adapt it for maximization and for unbalanced matrices, where the number of jobs and workers differs. Last come restricted assignments, where some pairings are not allowed, and the travelling salesman problem, where you need one closed route through all cities.

This chapter sits with the other operations research and quantitative decision tools in the paper, such as transportation and linear programming. The skill is the same: turn a business situation into a model, solve it step by step, and give a clear recommendation with the total cost or profit. The method is mechanical, so careful working earns marks reliably.

Assignment problems are procedural, so a student who knows the steps can score full marks on a numerical. The same method can also appear as a Section A MCQ on a concept such as dummy rows or the condition for optimality, or as a descriptive question on allocating jobs, staff or machines. Since there is no negative marking, MCQs are worth attempting either way. The method is the same every time, so you can build speed and accuracy by practising many matrices.

Assignment: topics in the order to study them

  1. 1Assignment Problem Formulation and BasicsYou need the matrix layout, the one-to-one rule and the link to transportation before any method makes sense.
  2. 2Hungarian Method for MinimizationThis is the core algorithm; every other topic is a small change to it.
  3. 3Maximization and Unbalanced Assignment ProblemsBoth reduce to the minimization method, by converting profits to opportunity losses or by adding dummy rows or columns.
  4. 4Restricted Assignments and Travelling Salesman ProblemIt builds on the basic method by adding prohibited cells and the extra condition of a single closed route, so it comes last.

How to prepare Assignment

Practise this chapter by repetition. The method is the same every time, so speed and accuracy come from solving many matrices by hand.

  1. Read the formulation topic and write the definition, assumptions and balanced condition in your own words.
  2. Learn the Hungarian steps in order: row reduction, column reduction, cover all zeros with the minimum number of lines, adjust, repeat until lines equal the matrix order.
  3. Solve at least five minimization problems from scratch, then make the final assignment by choosing zeros that cover each row and column once.
  4. Add the variants one by one: for maximization, subtract every entry from the largest entry; for unbalanced problems, add a dummy row or column of zeros.
  5. Practise restricted cases by putting a very large cost in prohibited cells, and solve a travelling salesman problem by checking that the assignment forms one complete tour.
  6. Always compute the total cost or profit from the original matrix, not the reduced one, and write a one-line recommendation.
  7. In the last week, redo past numericals under time limits and attempt MCQs on concepts such as dummy entries and multiple optimal solutions.

Common mistakes in Assignment

  • Doing column reduction before row reduction, or skipping a step.

    Fix: Follow the same order every time and check that each row and column has at least one zero before drawing lines.

  • Drawing more lines than needed to cover the zeros.

    Fix: Start with the row or column holding the most zeros, and recount the lines before deciding whether the solution is optimal.

  • Reporting the total from the reduced matrix.

    Fix: Map each chosen zero back to the original matrix and add those original values.

  • In a maximization problem, simply picking the largest values or forgetting the conversion.

    Fix: Subtract all entries from the largest, solve as minimization, then total the original profits.

  • Not balancing an unbalanced matrix, or treating dummy assignments as real.

    Fix: Add a zero-cost dummy first, and state in the answer which job stays unassigned or which person stays idle.

  • Accepting a travelling salesman answer with sub-tours.

    Fix: Trace the route city by city. If it closes early, take the next-best assignment: use the smallest uncovered element to create a new zero so the sub-tours join, and repeat until you get one full tour. Also check that the diagonal cells carry a very large cost.

Last-day revision: Assignment

  • An assignment problem is a one-to-one allocation. The Hungarian method needs a square matrix; if the problem is unbalanced, make it square by adding dummy rows or columns.
  • Each row and each column gets exactly one assignment.
  • Minimization: subtract the row minimum from each row, then the column minimum from each column.
  • Cover all zeros with the minimum number of horizontal and vertical lines.
  • If the number of lines equals the order of the matrix, an optimal assignment exists.
  • If lines are fewer, subtract the smallest uncovered element from uncovered cells and add it to cells at line intersections.
  • Maximization: convert to a minimization problem by subtracting every element from the largest element, then apply the usual steps.
  • Unbalanced problem: add dummy rows or columns with zero cost to make the matrix square.
  • Prohibited assignment: put a very large cost in that cell so it is never chosen.
  • Travelling salesman: treat it as an assignment problem with a very large cost on the diagonal (a city to itself), and the assignment must form one closed tour. If the optimal assignment has sub-tours, bring in the next-best assignment: use the smallest uncovered element to open a new zero, so the sub-tours join into one tour.
  • Calculate the final total from the original cost or profit matrix.
  • More than one optimal assignment can exist; the total stays the same.

Assignment practice questions

Assignment in other exams

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

Assignment: frequently asked questions

Is the assignment problem the same as the transportation problem?

It is a special case of the transportation problem in which each source has supply of 1 and each destination has demand of 1. Because of this, a simpler method, the Hungarian method, is used.

What do I do if the number of jobs and workers is not equal?

Add a dummy row or column with zero costs to make the matrix square. The job or worker matched to the dummy is left unassigned.

How do I handle a prohibited assignment?

Put a very large cost in that cell for minimization, so it is never selected. Then solve in the normal way and check that the final answer avoids that cell.

Can an assignment problem have more than one optimal solution?

Yes. When more than one set of zeros gives a valid assignment, there are alternative optimal solutions with the same total cost or profit. You can show any one of them unless the question asks for all.

How do I remove sub-tours in a travelling salesman problem?

Solve it as an assignment problem with a very large cost on the diagonal, so no city is assigned to itself. If the optimal assignment splits into sub-tours, move to the next-best assignment by using the smallest uncovered element, so the sub-tours combine into one closed tour.