CMA Final · Strategic Cost Management

Assignment: formula sheet

Full chapter guide

Key formulas

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.
Row reduction: New cost = cost − smallest value in that row; Do this for every row. Each row now has at least one zero.
Column reduction: New cost = cost − smallest value in that column; Do this on the row-reduced matrix. Skip a column that already has a zero, because its minimum is 0.
Optimality test: Minimum number of lines covering all zeros = n ⇒ optimal assignment exists; If the lines are fewer than n, the solution is not yet optimal. Revise the matrix.
Matrix revision: k = smallest uncovered element; uncovered cells: subtract k; cells at line intersections: add k; cells covered once: unchanged; Repeat the line-covering test after each revision.
Total minimum cost: Total cost = Σ original cost of the assigned cells; Read the costs from the original matrix. Never add up the reduced values.
Conversion of maximization to minimization: Opportunity loss = (Largest value in the matrix) − (Given value); Apply to every cell. Then use the Hungarian method. Read the final total from the original profit matrix.
Balancing rule: Number of rows = Number of columns; If rows < columns, add (columns − rows) dummy rows. If columns < rows, add (rows − columns) dummy columns.
Dummy entries: All entries of a dummy row or column = 0; In a maximization problem, add the dummy zeros after converting to loss, or use zero profit in the original matrix. Both give the same assignment.
Optimality condition: Minimum number of lines covering all zeros = order of the square matrix; If fewer lines, subtract the smallest uncovered value from uncovered cells and add it to cells at line intersections.
Multiple optima: More than one complete set of independent zeros ⇒ alternative optimal solutions; All such sets give the same optimal total.
Prohibited cell rule: Cost of prohibited assignment = M (M very large, M ± k = M); Use for minimisation. Never choose an M cell in the final answer.
TSP diagonal rule: Cost(i → i) = M for every city i; A city cannot be its own next city.
Optimality test: Minimum number of lines covering all zeros = n; n is the order of the square matrix. If fewer lines, revise the matrix.
Matrix revision: Subtract the smallest uncovered element from uncovered cells and add it to cells at line intersections; Cells covered by one line stay unchanged.
TSP validity check: Assignment is a valid tour only if it forms one closed loop of n cities; Two or more loops are sub-tours and the solution is not yet valid.
Total cost: Total cost = Σ original costs of the chosen cells; Always read the cost from the original matrix, not the reduced one.

Quick revision

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.

Common mistakes

Solving an unbalanced matrix without adding a dummy row or column. Fix: Always count rows and columns first. Add dummies until the matrix is square.
Putting the dummy on the wrong side. Fix: Add the dummy to the side that has fewer entries. Fewer persons than jobs means a dummy row.
Adding up the reduced matrix values to get the total cost. Fix: Go back to the original matrix. Write each pairing with its original cost and add those costs.
Doing column reduction before row reduction, or skipping it altogether. Fix: Do rows first, then columns. Column reduction can create zeros in a column that had none, so it often changes the answer.
Subtracting from the row maximum or column maximum instead of the largest value in the whole matrix. Fix: For conversion, use one number only: the single largest entry in the matrix. Row and column minima come later.
Reporting the total from the loss matrix as the maximum profit. Fix: After choosing the pairs, go back to the original profit matrix and add the actual profits.
Leaving the prohibited cell blank or as 0 Fix: Write M. A zero would make the prohibited cell the most attractive one.
Forgetting the diagonal M in a TSP Fix: Put M on every diagonal cell before reducing. Otherwise a city may be sent to itself.

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.
Show every matrix: after row reduction, after column reduction, and after each revision. Marks are given for method even if the final cost slips.
Always state the number of lines and compare it with n in one sentence. This is the proof that you have tested optimality.
Write the final cost from the original matrix as a sum, such as 10 + 10 + 13 + 9 = 42. Do not leave only the pairings.