Minimum-cost and maximum-profit assignments | Year 12

01 / LEARN

Understand the idea.

Match the objective

State the objective before reducing a table. A minimum-cost allocation seeks the smallest sum; a maximum-profit allocation seeks the largest. The same one-to-one constraints apply, but directly minimising a profit table would answer the wrong question.

For profits, choose a common constant $K$ at least as large as every entry and replace each profit $p$ by $K - p$ . Every complete allocation selects $n$ entries, giving transformed total $n K - P$ . A smaller transformed total therefore means a larger original profit $P$ .

\begin{aligned} C_{i j} & = K - P_{i j} \\ \sum C_{i j} & = n K - \sum P_{i j} \end{aligned}

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

Read the original result

With $K = 19$ , the team table becomes opportunity-loss rows $[1, 5, 6]$ , $[4, 2, 7]$ and $[3, 8, 0]$ . Row reduction yields independent diagonal zeros, selecting P→1, Q→2 and R→3. Evaluate those choices using the original profits.

The original selected values total $18 + 17 + 19 = 54$ hundred-dollar units, or 5,400 dollars. Transformed losses are a comparison device rather than actual expenses. The model assumes the selected contract profits add independently and the pairings are all available.

02 / WORKED EXAMPLES

See the method in action.

EXAMPLE 01

A cost minimum

For rows [8,5,7], [6,9,4], [3,7,6], find a minimum-cost assignment.

Worked solution

1
Find the lowest cost in each row.
$\begin{aligned} min (8, 5, 7) & = 5 (column 2) \\ min (6, 9, 4) & = 4 (column 3) \\ min (3, 7, 6) & = 3 (column 1) \end{aligned}$
Any complete assignment must pay at least the minimum of each selected row.
2
Check that the minima form a feasible allocation.
$1 \to 2, 2 \to 3, 3 \to 1$
Columns 2, 3 and 1 are distinct, so every job is assigned once.
3
Attain the lower bound.
$C = 5 + 4 + 3 = 12 units$
This feasible assignment reaches the sum of row minima, so no other assignment can cost less.

Answer

Row 1→2, row 2→3, row 3→1; minimum cost 12 units.

EXAMPLE 02

A profit maximum

Use the three-team profit table to identify a maximum-profit assignment and express the answer in dollars.

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

Worked solution

1
Transform profits using K equal to 19.
$C = (\begin{array}{cccccccccc} 1 & 5 & 6 \\ 4 & 2 & 7 \\ 3 & 8 & 0 \end{array})$
Each entry is nineteen minus its original profit; minimising the transformed total maximises the three selected profits.
2
Reduce each opportunity-loss row.
$C \to (\begin{array}{cccccccccc} 0 & 4 & 5 \\ 2 & 0 & 5 \\ 3 & 8 & 0 \end{array})$
Subtract row minima 1, 2 and 0. The independent diagonal zeros certify a minimum transformed assignment.
3
Read the original selected profits.
$\begin{aligned} P & \to 1, Q \to 2, R \to 3 \\ P_{total} & = 18 + 17 + 19 = 54 \end{aligned}$
The original entries are in hundred-dollar units; transformed entries are not the profit.
4
Convert the total to dollars.
$54 \times 100 = 5400 dollars$
Each table unit represents one hundred dollars, so the maximum profit is 5,400 dollars.

Answer

P→1, Q→2, R→3; maximum profit $5,400.

03 / YOUR TURN

Try it yourself.

Check your understanding

For three assignments with K=20, a transformed total is 11. What is the original total profit?

Show answer & reasoning

49 profit units.

There are three selected entries, so $11 = 3 (20) - P$ . Therefore $P = 60 - 11 = 49$ profit units. Subtract the transformed total from $n K$ , rather than from $K$ alone.

Keep practising

6 worksheet questions · 14 marks

Open worksheet Worked solutions

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.
$[\begin{array}{cccccccccc} 1 & 5 & 6 \\ 4 & 2 & 7 \\ 3 & 8 & 0 \end{array}]$ .
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 \times 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.

Checking saved progress…

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 ↗

In this lesson

Understand the idea.

Match the objective

Read the original result

See the method in action.

A cost minimum

Find the lowest cost in each row.

Check that the minima form a feasible allocation.

Attain the lower bound.

A profit maximum

Transform profits using K equal to 19.

Reduce each opportunity-loss row.

Read the original selected profits.

Convert the total to dollars.

Try it yourself.

Check your understanding

Keep practising