The idea, step by step
Match the objective
A minimum-cost assignment chooses a feasible pairing with the smallest total. A maximum-profit assignment chooses the largest total. These are different questions even when the same table shape is used. State the direction before performing reductions.
To use the minimum-assignment algorithm on profits, choose a constant K at least as large as every profit and replace each entry p by K−p. A complete n-person assignment then has transformed total nK−P, where P is its original profit. Minimising the transformed total therefore maximises P.
| Team | Contract 1 | Contract 2 | Contract 3 |
|---|---|---|---|
| P | 18 | 14 | 13 |
| Q | 15 | 17 | 12 |
| R | 16 | 11 | 19 |
Read the original result
For the team table, choose K=19. The opportunity losses are [1,5,6], [4,2,7], [3,8,0]. Row reductions immediately produce independent diagonal zeros, giving P→1, Q→2 and R→3. The original profit is 18+17+19=54 hundred-dollar units, or $5,400.
A nonzero transformed total does not represent an actual business expense. It is a comparison device. Profit models also assume the contributions of the selected contracts add independently and the same team is not needed for two contracts at the same time.
A common trap
Minimising the profit entries directly or reporting the transformed loss total as the actual profit.
Instead: Transform profits for the algorithm, then evaluate the selected pairing in the original profit table and original units.
See the thinking
A cost minimum
For rows [8,5,7], [6,9,4], [3,7,6], find a minimum-cost assignment.
- Row minima occur at columns 2,3 and 1, which are distinct.
- They form a feasible complete assignment and attain the sum of all row minima.
- Original total is 5+4+3=12.
A profit maximum
Use the three-team profit table to identify a maximum-profit assignment and express the answer in dollars.
| Team | Contract 1 | Contract 2 | Contract 3 |
|---|---|---|---|
| P | 18 | 14 | 13 |
| Q | 15 | 17 | 12 |
| R | 16 | 11 | 19 |
- With K=19, transform profits to opportunity losses.
- Independent diagonal zeros after row reduction give P→1, Q→2, R→3.
- Add original profits: 18+17+19=54.
- Each table unit is $100, so multiply by 100.
Check your understanding
For three assignments with K=20, a transformed total is 11. What is the original total profit?
Show answer
49 profit units.
11=3×20−P, so P=60−11=49.
Your turn
6 questions · 14 marks · Work at your own pace.
Read the questions online
- Form the opportunity-loss matrix for the supplied profits using K=19.3 marks
Profit ($100 units) from assigning each team to one distinct contract. Team Contract 1 Contract 2 Contract 3 P 18 14 13 Q 15 17 12 R 16 11 19 - For a four-person problem with K=30, the minimum transformed total is 17. Find the maximum profit.2 marks
- Two workers have profits A:[12,8] and B:[10,11]. Find the best complete assignment.2 marks
- For costs A:[12,8] and B:[10,11], find the minimum assignment and compare it with the previous profit objective.2 marks
- If 5 is added to every profit in a three-person square table, does the optimal pairing change? What happens to its total?2 marks
- An assignment gives predicted profits $700, $900 and $600, but the last two contracts compete for the same machine. Explain why adding them may overstate the achievable profit.3 marks
Read the worked solutions
Equivalent correct methods earn the corresponding marks. Include units where asked.
- Form the opportunity-loss matrix for the supplied profits using K=19.3 marks
Profit ($100 units) from assigning each team to one distinct contract. Team Contract 1 Contract 2 Contract 3 P 18 14 13 Q 15 17 12 R 16 11 19 Subtract each original profit from 19.
[1,5,6], [4,2,7], [3,8,0]. - For a four-person problem with K=30, the minimum transformed total is 17. Find the maximum profit.2 marks
The complete transformed total is 4×30−P.
P=120−17=103.
103 profit units. - Two workers have profits A:[12,8] and B:[10,11]. Find the best complete assignment.2 marks
The two feasible totals are 12+11=23 and 8+10=18.
Choose the larger.
A→1, B→2; total profit 23. - For costs A:[12,8] and B:[10,11], find the minimum assignment and compare it with the previous profit objective.2 marks
The same numbers give a different optimum when lower is better.
18<23.
A→2, B→1; total cost 18. - If 5 is added to every profit in a three-person square table, does the optimal pairing change? What happens to its total?2 marks
Each complete assignment selects exactly three entries.
The same constant shift preserves the ranking.
The optimal pairing does not change; every complete total rises by 15. - An assignment gives predicted profits $700, $900 and $600, but the last two contracts compete for the same machine. Explain why adding them may overstate the achievable profit.3 marks
The nominal sum is $2,200.
The machine conflict may prevent both contracts being completed as modelled; costs or scheduling need revision.
The independent-addition/resource assumption is violated.
Curriculum reference & lesson scope
SACE Board of South Australia
Stage 2 General Mathematics: discrete models, project scheduling and assignment. Activity-on-arrow conventions are used for project networks; technology may verify calculations but does not replace interpreting the model.
Official curriculum source ↗