Linear programming: formulation and graphical solution

Writing the problem down

Define the variables in words, including their units. Marks are lost for an unexplained x far more often than for the algebra. Then write the objective to be maximised or minimised, and each restriction as an inequality, remembering the non-negativity conditions the context implies.

Inequalities become equations by adding a variable. A slack variable is added to a ≤ constraint to take up the unused amount. A surplus variable is subtracted from a ≥ constraint to record the excess. An artificial variable is then added to that same constraint, because subtracting the surplus leaves no starting solution to work from.

Two ways to find the corner

The vertex method evaluates the objective at every corner and takes the best. It is reliable and needs no judgement, and with four or five corners it is quick enough.

The objective line method draws one line of constant objective value and slides it parallel across the region, and the last corner it touches is the optimum. It is faster, and it shows at once when two corners tie, which happens when the objective runs parallel to a constraint. Whichever method you use, say which, and draw the line if the question asks for it.

When the variables must be whole numbers the optimum may not sit at a corner at all. Find the corner first, then test the integer points around it that lie inside the region, and give the best of those. Rounding the corner coordinates can land you outside the region entirely.

What a change to a coefficient does

A formulation is a model, and its numbers are estimates. So a question may ask what a change to one of them would do, and the objective line answers it without any recalculation. Only the gradient of that line decides which corner it last touches, so the optimal corner survives any change to the objective that leaves the gradient between the gradients of the two constraints meeting there. Move it past either and the optimum slides to the neighbouring corner.

For the problem above, P = 4x + 5y has gradient −4/5, and the two constraints crossing at (6, 4) have gradients −1 and −2/3. Write the objective as ax + 5y and its gradient is −a/5, which sits between those two while 10/3 ≤ a ≤ 5. At a = 5 the objective runs parallel to x + y = 10 and (10, 0) ties with (6, 4); above 5 the corner (10, 0) wins outright. At a = 10/3 the tie is with (0, 8), and below that (0, 8) takes it.

Drawn on the region, the range is a fan of lines through the corner, and the answer is stable over the whole of it, not only at the one gradient the estimate happened to give.

Describe the drawing

The feasible quadrilateral for the worked problem, with its corner at six and four ringed. Three lines are drawn through that corner: the two constraint lines, of gradient minus one and minus two thirds, and between them the objective line of gradient minus four fifths. The wedge each pair of outer lines cuts out, above the corner and below it, is shaded amber: any objective whose gradient lies in that fan leaves six and four as the last corner the line touches. Tilt it past minus one and the corner at ten and nought takes over; tilt it past minus two thirds and nought and eight does.

Changing a constraint instead moves the region rather than the line. Raise the first limit from 10 to 11 and the two constraints now cross at (9, 2), where P = 46, so the extra unit was worth 2. Raise it again to 12 and the crossing is (12, 0), worth 48, the same gain once more. Past 12 the constraint stops binding, the second one alone fixes the corner, and further units are worth nothing. So the value of relaxing a constraint is constant over a range and then stops.

Integer programming and branch and bound

Testing the lattice points near a corner works while there are few of them. Branch and bound is the systematic version, and it is what a question naming the method wants. Solve the problem without the integer condition first; that answer is an upper bound on anything the integer problem can reach. If it happens to be whole, the work is over. If not, pick a variable with a fractional value and branch: one subproblem takes that variable at or below the value rounded down, the other at or above the value rounded up, and between them they hold every integer point of the original.

Each subproblem is then solved the same way, and its relaxed optimum is a bound on that branch. Two things end a branch. An integer answer ends it and becomes the best so far. A relaxed optimum no better than the best integer answer already found ends it as well, since nothing inside can beat what is in hand, and cutting a branch off on that ground is what stops the tree from doubling for ever.

Five nodes are enough to show both endings at work, and the tree below is the one the worked example builds: each box carries the best integer answer in hand when it was reached, and the last branch cuts itself off against that figure.

Describe the drawing

A branch and bound tree of five boxes. The root solves the problem without the integer condition and reaches 21 at three and a half, so y is the variable to split on. Taking y at least two gives a whole answer straight away, (2, 2) worth 18, which becomes the best so far. Taking y at most one reaches 62 over 3, better than 18, so that branch is split again on x. With x at least four the answer is (4, 0) worth 20, whole, and the best so far rises to 20. With x at most three the branch can reach only 19, which cannot beat 20, so it is cut off and the search ends at x = 4, y = 0 with P = 20.