Linear programming (SACE Stage 2 General Mathematics)

What this dot point is asking

You must translate a worded problem into inequalities and an objective function, graph the feasible region, and find the vertex that optimises the objective.

Setting up the problem

Define decision variables (often $x$ and $y$ for the number of each product). Then write:

• Constraints: linear inequalities from limits on resources (time, material, demand), plus $x \ge 0$ and $y \ge 0$.
• Objective function: the quantity to maximise or minimise, such as $P = 5x + 8y$.

Graphing the feasible region

For each inequality, graph the boundary line (replace the inequality with $=$), then shade the side that satisfies it. The feasible region is where all shadings overlap.

Why the optimum is always at a vertex

The objective function $P = ax + by$ has straight, parallel level lines - one for each value of $P$. Increasing $P$ slides this line across the plane in a fixed direction. As it sweeps over the feasible region, the last point it touches before leaving is always a corner (or, in a tie, an entire edge). This is why you never need to test interior points: the extreme value of a linear objective over a polygon is reached at a vertex. Understanding this corner-point principle, rather than just applying it, is what examiners look for when they ask you to justify your method.

Finding the vertices

Each vertex is the intersection of two boundary lines, found by solving the corresponding pair of equations simultaneously. Some vertices lie on the axes (where $x = 0$ or $y = 0$) and are read off directly; the crucial interior vertex is where two sloping constraints cross, which you must solve for. List every vertex of the feasible region, evaluate the objective at each, and the best value is your answer. Missing the interior intersection is the most common way to get a wrong optimum.

Interpreting the solution

The optimal vertex gives the best combination. Always state the answer in context: how many of each item and the resulting objective value. Check the solution uses whole numbers if the items are indivisible.

Integer solutions

Many linear-programming contexts involve indivisible items - you cannot make $6.4$ tables. When the optimal vertex has non-integer coordinates, the true answer is the best integer point inside the feasible region near that vertex, found by testing the nearby whole-number combinations that still satisfy every constraint. SACE problems are usually designed so the optimum lands on integers, but you should always confirm the solution is feasible and sensible in context, rounding toward the interior of the region rather than blindly to the nearest integer, which might violate a constraint.

Minimisation problems

Not every objective is a profit to maximise; some are costs to minimise. The method is identical - graph the feasible region and test the vertices - but you choose the corner giving the smallest objective value rather than the largest. For minimisation the feasible region is often unbounded above (for example, "use at least this much of each ingredient"), and the optimum sits at the lowest-cost corner of the bounded part. Reading whether the question asks to maximise or minimise, and selecting the corresponding vertex, is essential.