Integer constraints and interpreting an optimal solution | Year 12

01 / LEARN

Understand the idea.

A fractional decision may be impossible

Integer constraints restrict decisions to whole numbers. Solving the continuous version can provide a useful bound, but its fractional optimum may not be an allowed decision. Rounding can break a resource limit or miss a better integer point.

Check each proposed integer plan in every original constraint. Rounding down may lose needed capacity; rounding up may exceed a limit. The direction of a rounding operation does not by itself establish feasibility or optimality.

Turn a small integer problem into a finite search

For a small problem, use the constraints to make a finite search. Fix one integer variable, determine the allowed range of the other, and choose the endpoint favoured by the objective. Record the feasible choice and its value for every case.

This search justifies the recommendation only when it covers all possible cases or excludes the rest with a valid bound. Report ties if they occur; a practical tie-break needs a stated criterion rather than an invented preference.

02 / WORKED EXAMPLES

See the method in action.

EXAMPLE 01

Rounding can fail

Maximise $P = 3 x + 4 y$ for non-negative integers with $2 x + y \leq 7$ and $x + 2 y \leq 7$ .

x	Largest feasible integer y	P
0	3	12
1	3	15
2	2	14
3	1	13

Worked solution

1
Locate the fractional corner and test rounding.
$\begin{aligned} 2 x + y = 7, x + 2 y = 7 & \Rightarrow x = y = \frac{7}{3} \\ 2 (3) + 3 & = 9 > 7 \end{aligned}$
Rounding both coordinates up to $(3, 3)$ violates both resource limits.
2
Bound the integer search.
$\begin{aligned} x & \in {0, 1, 2, 3} \\ y & \leq min (7 - 2 x, \frac{7 - x}{2}) \end{aligned}$
Non-negative $y$ and the first constraint imply $x \leq 3$ ; both constraints then bound $y$ .
3
Choose the best feasible height for each input.
$\begin{array}{crrrr} x & 0 & 1 & 2 & 3 \\ y_{max} & 3 & 3 & 2 & 1 \\ 3 x + 4 y_{max} & 12 & 15 & 14 & 13 \end{array}$
For fixed $x$ , profit increases with $y$ , so the largest permitted integer $y$ covers the best plan in that column.
4
Verify the integer winner.
$2 (1) + 3 = 5 \leq 7, 1 + 2 (3) = 7, P = 3 + 12 = 15$
All possible $x$ -values were covered, and $(1, 3)$ gives the largest feasible profit.

Answer

Integer maximum 15 at $(1, 3)$ .

EXAMPLE 02

Whole vehicles

At least 46 seats are needed. A small vehicle has 8 seats and costs AUD 70; a large vehicle has 14 seats and costs AUD 110. At most 5 vehicles are allowed. Minimise cost.

Worked solution

1
Write the integer model.
$\begin{array}{c} C = 70 x + 110 y to minimise \\ 8 x + 14 y \geq 46, x + y \leq 5 \\ x, y \in {0, 1, 2, \dots} \end{array}$
Let $x$ count small vehicles and $y$ count large vehicles; seating is a lower bound and fleet size an upper bound.
2
Cover all possible large-vehicle counts.
$y \in {0, 1, 2, 3, 4, 5}$
The vehicle cap makes this a complete finite search. With $y = 0$ , even five small vehicles provide only 40 seats.
3
Find the least feasible small-vehicle count.
$\begin{array}{crrrrr} y & 1 & 2 & 3 & 4 & 5 \\ x_{min} & 4 & 3 & 1 & 0 & 0 \\ C & 390 & 430 & 400 & 440 & 550 \end{array}$
For each $y$ , take the smallest non-negative integer $x$ meeting the seat requirement and check $x + y \leq 5$ . Any extra small vehicle costs more.
4
Verify the least-cost fleet.
$\begin{aligned} 8 (4) + 14 (1) & = 46 seats \\ 4 + 1 & = 5 vehicles \\ 70 (4) + 110 (1) & = 390 \end{aligned}$
Four small and one large vehicle meet both constraints, and AUD 390 is the smallest cost in the complete comparison.

Answer

Four small and one large vehicle; AUD 390, exactly 46 seats.

03 / YOUR TURN

Try it yourself.

Check your understanding

A model gives 4.2 workers. Is 4 automatically acceptable?

Show answer & reasoning

No.

Four workers are not automatically sufficient. If $4.2$ arose from a minimum workload requirement, four may provide too little capacity; check the original inequalities and whole-number restriction.

Keep practising

6 worksheet questions · 12 marks

Open worksheet Worked solutions

Read the questions online

Find the greatest integer $x$ with $3 x \leq 20$ and $x \geq 0$ .
2 marks
At least 25 items are packed in boxes of 6. Find the least number of boxes.
2 marks
Maximise $P = 2 x + 3 y$ for non-negative integers with $x + y \leq 5$ , $y \leq 3$ .
2 marks
Is $(2, 4)$ feasible for $2 x + y \leq 7$ , $x + 2 y \leq 9$ ?
2 marks
Two integer plans share the greatest profit. What should a recommendation explain?
2 marks
For $x = 0, 1, 2, 3$ , the largest feasible integer $y$ -values are 4,3,2,0. Maximise $P = 5 x + 4 y$ .
2 marks

Read the worked solutions

Equivalent correct methods earn the corresponding marks. Include units where asked.

Find the greatest integer $x$ with $3 x \leq 20$ and $x \geq 0$ .
2 marks
$x \leq \frac{20}{3}$ ; choose the largest permitted integer below that bound.
6.
At least 25 items are packed in boxes of 6. Find the least number of boxes.
2 marks
$6 b \geq 25$ , so $b \geq \frac{25}{6}$ ; round up to meet the minimum.
5.
Maximise $P = 2 x + 3 y$ for non-negative integers with $x + y \leq 5$ , $y \leq 3$ .
2 marks
Increasing $y$ in place of $x$ increases profit.
Use $y = 3$ and the remaining capacity for $x = 2$ .
13 at $(2, 3)$ .
Is $(2, 4)$ feasible for $2 x + y \leq 7$ , $x + 2 y \leq 9$ ?
2 marks
The resource totals are 8 and 10, exceeding both limits.
No.
Two integer plans share the greatest profit. What should a recommendation explain?
2 marks
A secondary criterion such as fewer staff hours can break the tie only if it matters in the stated situation.
Report both optima and any explicitly justified practical preference.
For $x = 0, 1, 2, 3$ , the largest feasible integer $y$ -values are 4,3,2,0. Maximise $P = 5 x + 4 y$ .
2 marks
The four objective values are 16,17,18,15.
18 at $(2, 2)$ .

Checking saved progress…

Curriculum reference & lesson scope

SACE Board of South Australia

Stage 2 General Mathematics: Modelling with Linear Relationships, a compulsory school-assessed topic. The external examination scope differs from the full course.

Official curriculum source ↗

In this lesson

Understand the idea.

A fractional decision may be impossible

Turn a small integer problem into a finite search

See the method in action.

Rounding can fail

Locate the fractional corner and test rounding.

Bound the integer search.

Choose the best feasible height for each input.

Verify the integer winner.

Whole vehicles

Write the integer model.

Cover all possible large-vehicle counts.

Find the least feasible small-vehicle count.

Verify the least-cost fleet.

Try it yourself.

Check your understanding

Keep practising