Formulating linear programming problems, the feasible region and graphical solution, the vertex (objective line) method, slack variables, and the simplex algorithm for maximisation.

What this dot point is asking

AQA wants you to formulate a linear programming problem with an objective function and constraints, draw the feasible region, solve graphically using the vertex method or an objective line, introduce slack variables to form equations, and carry out the simplex algorithm to maximise an objective.

Formulating and the feasible region

The hardest marks in a linear programming question often come from the formulation, not the solving. Define the decision variables precisely (say what $x$ and $y$ count and in what units), write the objective function to maximise or minimise, and translate each restriction in the wording into a linear inequality. Resource limits give $\leq$ constraints, minimum-requirement conditions give $\geq$ constraints, and the non-negativity conditions $x \geq 0$ and $y \geq 0$ are almost always implied. Reading the constraints carefully and simplifying them (for example dividing $4x + 2y \leq 40$ down to $2x + y \leq 20$) makes the graphical work cleaner.

Graphical solution

The objective-line (or profit-line) method is the alternative to testing every vertex: draw one line $ax + by = c$ for a convenient $c$, then slide it parallel across the region in the direction of increasing objective; the last vertex it touches is the optimum.

Slack variables and the simplex algorithm

When there are more than two variables you cannot draw the region, so you add a slack variable to each $\leq$ constraint to make it an equation, then build the simplex tableau and pivot algebraically. The slack variables measure the unused amount of each resource, and they are non-negative because you cannot use more than is available.

Each simplex iteration chooses a pivot column (the most negative entry in the objective row, the variable that raises $P$ fastest), then a pivot row (the smallest non-negative ratio of constraint value to pivot-column entry, so no constraint is violated). You then divide the pivot row to make the pivot element $1$ and add multiples of it to the other rows to clear the pivot column. The algorithm stops when the objective row has no negative entries, at which point the basic variables read off the optimal solution. The simplex method effectively walks from vertex to vertex of the feasible region, improving the objective each step, which is why it always lands on the optimal corner.

Reading the final tableau

When the simplex algorithm halts, the answer is read directly from the tableau rather than recomputed. A variable is basic (non-zero) if its column is a unit column, that is a single $1$ with zeros elsewhere; its value is the number in the value column of the row holding that $1$. Every other variable is non-basic and equals zero. The objective row's value entry is the optimal value of $P$. The numbers sitting in the objective row above the slack columns also carry meaning: they are the shadow prices, telling you how much $P$ would rise per extra unit of each resource, which is the standard way an exam asks you to interpret the solution.

A practical point that trips students is the ratio test for the pivot row. You only form ratios for strictly positive entries in the pivot column; a zero or negative entry is skipped, because increasing that variable would not bind against the corresponding constraint. If no entry in the pivot column is positive, the problem is unbounded and the objective can grow without limit, which signals a mistake in the formulation for a normal exam question. Keeping the arithmetic in exact fractions until the final step avoids rounding errors that would otherwise accumulate across several pivots.

Minimisation problems

AQA problems are usually phrased as maximisation, but a minimisation can be handled by maximising the negative of the objective, since minimising $C$ is the same as maximising $-C$. Alternatively, for a graphical minimisation you slide the objective line in the direction of decreasing value and take the first vertex it touches. Either way the optimum still sits at a vertex of the feasible region, so the vertex-testing method works unchanged: list the corner points, evaluate the objective at each, and select the smallest. The skill the marks reward is correct formulation followed by systematic vertex evaluation, not clever shortcuts.