Decision variables, constraints (including non-negativity) and the objective function

Formulating a problem from context, including “at least”, “at most”, ratio and percentage conditions

Drawing constraint lines and identifying the feasible region

The objective line (ruler) method for maximising and minimising

The vertex method: testing every corner of the feasible region

Unbounded regions and problems with more than one optimal solution

Integer solutions when the optimal vertex does not have integer coordinates

1. Linear programming finds the values of two decision variables that make a linear objective as large or as small as possible, subject to linear inequality constraints, by drawing the feasible region and finding its best corner.

2. Decision variables: say exactly what x and y count, with the time period (“the number of vases made each week”).

3. Constraints: one linear inequality per restriction, plus x ≥0, y ≥0. Simplify by dividing through by common factors.

4. Feasible region: draw each boundary line from two points, decide the side with a test point, and label the region R that satisfies every constraint.

5. Optimum: slide an objective line parallel to itself (the last point of R it touches), or evaluate the objective at every vertex.

6. Integers: if the best vertex is not a whole-number point, test the integer points near it against every constraint and pick the best one.

A business has limited clay, limited machine hours or a limited budget, and wants the plan that makes the most profit or costs the least. When every restriction and the goal can be written as linear expressions in two unknowns, the problem can be solved on a graph. That is linear programming.

Decision variables (x, y): the quantities you choose, such as how many of each product, how many hours or how many vehicles.

Constraints: linear inequalities such as 3x + 2y ≤60 that come from limited resources, minimum requirements or ratios.

Non-negativity constraints: x ≥0 and y ≥0. You cannot make a negative number of anything, so always include them.

Objective function: the quantity to optimise, for example profit P = 15x + 12y (maximise) or cost C = 400x + 250y (minimise).

A feasible solution satisfies every constraint; the feasible region is the set of all feasible solutions; an optimal solution is a feasible solution with the best value of the objective. Because every boundary is a straight line, the feasible region is a convex polygon (or an unbounded convex region), and its corners are called vertices.

The standard layout of a formulation

a, b = profit (or cost) per unit of each variable; each constraint is “(amount used per unit) × variable … ≤ (amount available)”. Not in the formulae list: learn the layout.

Formulating is where most of the thinking happens. Work through the text in a fixed order:

1. Define the variables in words, with units and the time period.

2. Go through the text sentence by sentence; every limit, requirement or comparison becomes one inequality.

3. Write the objective and say whether it is maximised or minimised.

4. Add x ≥0, y ≥0 and simplify each constraint (divide by common factors, clear fractions).

The table translates the phrases that come up most often. Ratio and percentage conditions are the ones to slow down on: write them first exactly as the words say, then rearrange.

WORKED EXAMPLE · QUESTION

A pottery makes vases and bowls. Each vase uses 3 kg of clay and 1 hour of glazing; each bowl uses 2 kg of clay and 2 hours of glazing. Each week 60 kg of clay and 32 hours of glazing time are available. At least 3 bowls must be made each week. The profit is £15 on a vase and £12 on a bowl. Formulate this as a linear programming problem, stating your decision variables clearly.

SOLUTION

Variables. Let x = the number of vases and y = the number of bowls made each week.

Constraints, one sentence at a time: clay 3x + 2y ≤60; glazing x + 2y ≤32; bowls y ≥3; x ≥0.

Objective. Maximise P = 15x + 12y subject to 3x + 2y ≤60, x + 2y ≤32, y ≥3, x ≥0.

y ≥0 is already implied by y ≥3, so it does not need to be written separately (writing it is not wrong).

WORKED EXAMPLE · QUESTION

A school buys laptops at £400 each and tablets at £250 each. It needs at least 60 devices, at least 20 of which are tablets, and at least a quarter of all the devices must be laptops. The school wants to keep the cost as low as possible. Formulate this as a linear programming problem, simplifying each constraint.

SOLUTION

Variables. x = number of laptops, y = number of tablets bought.

Constraints. x + y ≥60; y ≥20; x ≥¼(x + y) ⇒4x ≥x + y ⇒y ≤3x; x ≥0.

Minimise C = 400x + 250y subject to x + y ≥60, y ≥20, y ≤3x, x ≥0.

For each constraint draw the boundary line (replace the inequality sign by =), using two easy points, usually the intercepts.

Decide which side is allowed with a test point not on the line. O is easiest unless the line passes through it; then try (1, 0) or (0, 1).

Lines of the form y = mx, from ratio constraints, pass through the origin: plot a second point such as (10, 10m).

The feasible region R is where every constraint holds. Either shade the parts you do not want, leaving R clear, or shade R itself. Say which you have done, and label R.

Find each vertex by solving the equations of the two lines that cross there; do not rely on reading a graph if exact values are needed.

WORKED EXAMPLE · QUESTION

Continue worked example 1. Draw the feasible region R and find the coordinates of its vertices.

SOLUTION

Boundary lines from their intercepts: 3x + 2y = 60 through (20, 0) and (0, 30); x + 2y = 32 through (32, 0) and (0, 16); y = 3.

Sides. O satisfies the two ≤ constraints; R is above y = 3 and to the right of the y-axis.

The vertex where clay and glazing both run out: (3x + 2y) - (x + 2y) = 60 - 32 ⇒2x = 28 ⇒x = 14, y = 9.

The other vertices: 3x + 2(3) = 60 ⇒(18, 3); and (0, 16), (0, 3). Vertices (0, 3), (18, 3), (14, 9), (0, 16).

For a fixed value of P, the equation ax + by = P is a straight line. Changing P moves the line but does not change its gradient, -a/b. So the objective lines form a family of parallel lines, and larger values of P (with a, b >0) lie further from O.

Draw one objective line accurately (pick a convenient value of P, such as a multiple of a and b) and place a ruler along it.

To maximise, slide the ruler parallel to itself away from O; the last point of R it touches is optimal.

To minimise, slide it towards O; the last point of R it touches is optimal.

The optimal point is at a vertex. Find it exactly by solving the two boundary equations that meet there.

If the objective line is parallel to an edge of R that it finishes on, every point on that edge is optimal.

Which vertex is optimal?

For P = ax + by, the vertex is optimal when the gradient of the objective line, -a/b, lies between the gradients of the two edges that meet at that vertex. Not in the formulae list: derive it from the gradient of ax + by = c.

WORKED EXAMPLE · QUESTION

Continue worked example 3. Use the objective line method to find the number of vases and bowls the pottery should make to maximise its weekly profit, and state the maximum profit.

SOLUTION

Gradient of the objective line: 15x + 12y = c has gradient -(15/12) = -(5/4).

Compare with the edges: clay -(3/2), glazing -½. Since -(3/2) <-(5/4) <-½, the last point touched is where clay and glazing meet.

14 vases and 9 bowls per week; P = 15(14) + 12(9) = 318, a profit of £318.

At this point all the clay (3 ×14 + 2 ×9 = 60 kg) and all the glazing time (14 + 2 ×9 = 32 h) are used.

The vertex method avoids drawing an objective line: find the exact coordinates of every vertex of R, evaluate the objective at each, and choose the largest (maximising) or smallest (minimising). It works because a linear objective on a convex region always takes its best value at a vertex. Set the work out as a table (vertex, value of the objective), then state the answer in context.

Minimising problems often have an unbounded region, because constraints like x + y ≥60 do not cap anything. A minimum can still exist, but there is no maximum.

Checking only the listed vertices is enough, because the objective increases as you move away into R.

WORKED EXAMPLE · QUESTION

Continue worked example 2. Find the vertices of the feasible region and hence the number of laptops and tablets that minimises the cost. State the minimum cost.

SOLUTION

Vertices. x + y = 60 and y = 3x: 4x = 60 ⇒(15, 45). x + y = 60 and y = 20 ⇒(40, 20).

15 laptops and 45 tablets, minimum cost £17 250.

The region is unbounded, but moving further into it only raises the cost (for example (100, 20) costs £45 000), so the minimum is at a vertex.

When the variables count objects (vases, buses, batches) the solution must be an integer point of R. If the optimal vertex is not an integer point, the best integer solution is usually near it, but not always the point you get by rounding.

List the integer points close to the vertex, check each one against every constraint and evaluate the objective at the feasible ones.

Alternatively, slide the objective line back from the vertex until it meets the first integer point in R.

Rounding both coordinates down keeps you feasible for ≤ constraints but is often not optimal; rounding up can break a constraint.

WORKED EXAMPLE · QUESTION

A caterer prepares x batches of hot meals and y batches of cold meals each day, where 5x + 3y ≤45 (kitchen hours), 2x + 5y ≤40 (fridge space) and x, y ≥0. The profit is £40 per batch of hot meals and £30 per batch of cold meals. Only whole batches can be made. Find the number of batches of each type that maximises the profit.

SOLUTION

Optimal vertex. The objective gradient -(4/3) lies between -(5/3) and -(2/5), so the optimum is where the two constraints meet:

25x + 15y = 225 and 6x + 15y = 120 ⇒19x = 105 ⇒V((105/19), (110/19)) ≈(5.53, 5.79), P ≈394.7.

Test integer points near V against both constraints:

6 batches of hot and 5 batches of cold meals, profit £390.

Why nothing beats 390: P = 10(4x + 3y) and the largest value of 4x + 3y in R is (750/19) ≈39.5.

For integers 4x + 3y is a whole number, so it is at most 39, giving P ≤390. Rounding V down to (5, 5) gives only £350.

A long question usually runs: formulate → draw and label R → find the optimum with an objective line or the vertices → interpret. It sometimes asks how far a profit could change before the optimal plan changes; that is the gradient comparison from the ruler-method section, run backwards.

WORKED EXAMPLE · QUESTION

A workshop makes standard and deluxe garden benches. A standard bench needs 2 hours of cutting and 4 hours of finishing; a deluxe bench needs 3 hours of cutting and 3 hours of finishing. Each week there are 60 hours of cutting and 90 hours of finishing available. Only 16 sets of deluxe fittings arrive each week, and the number of standard benches made must not be more than three times the number of deluxe benches. The profit is £30 on a standard bench and £40 on a deluxe bench.

(a) Formulate this as a linear programming problem. (b) Draw the constraints and label the feasible region R. (c) Use the objective line method to find the optimal number of each bench, and the maximum weekly profit. (d) The profit on a deluxe bench changes to £k, the profit on a standard bench staying at £30. Find the range of values of k for which your answer to (c) remains optimal.

SOLUTION

(a) x = number of standard and y = number of deluxe benches made each week. Maximise P = 30x + 40y subject to 2x + 3y ≤60, 4x + 3y ≤90, y ≤16, x ≤3y, x, y ≥0.

(b) Lines through (30, 0) and (0, 20); (22.5, 0) and (0, 30); y = 16; x = 3y through O and (18, 6). R has vertices (0, 0), (18, 6), (15, 10), (6, 16), (0, 16).

(c) Objective gradient -(30/40) = -¾, between -(4/3) (finishing) and -⅔ (cutting). (4x + 3y) - (2x + 3y) = 90 - 60 ⇒2x = 30 ⇒x = 15, y = 10. 15 standard and 10 deluxe benches, P = 450 + 400 = 850, i.e. £850.

Check by the vertex method: P = 0, 780, 850, 820, 640 at the five vertices, and 850 is the largest ✓.

(d) (15, 10) stays optimal while the gradient -30/k lies between -(4/3) and -⅔: ⅔ ≤30/k ≤(4/3) ⇒ 22.5 ≤k ≤45.

At k = 45 or k = 22.5 the objective line lies along an edge, so (15, 10) is still optimal but no longer the only optimum.

P1 Straight-line graphs and inequalities

Every constraint boundary is a straight line; intercepts, gradients (-a ÷b) and simultaneous equations are the tools for drawing R and finding its vertices. Shading the region that satisfies a linear inequality is the same skill as in P1.

D1.4 Critical path analysis and other D1 topics

Like critical path analysis and minimum spanning trees, linear programming is about finding the best plan under restrictions; here the restrictions are inequalities and the plan is a point on a graph.

Beyond this unit

Real problems with many variables are solved with the simplex algorithm and computer solvers; the two-variable graphical method shows why the optimum always lies at a corner.

1. x red tiles and y blue tiles are used. The number of red tiles must be at most twice the number of blue tiles. Write this as an inequality.

2. Why is the optimal value of a linear objective always found at a vertex of the feasible region?

3. In worked example 7 the profit becomes P = 6x + 9y. What happens to the optimal solution?

4. A feasible region has vertices (0, 0), (10, 0), (4, 8) and (0, 6), as in the first figure. Find the maximum of P = 3x + y.

5. The feasible region for a problem is unbounded. Can you always find a minimum? A maximum?

6. In worked example 1, the profit on a bowl rises to £20 while a vase stays at £15. Does (14, 9) remain optimal?

1. x ≤2y. Check: 20 red and 10 blue is allowed, 20 ≤20 ✓.

2. The objective lines are parallel. Sliding one across R in the improving direction, the last contact with a convex polygon is at a corner, or along a whole edge if the line is parallel to that edge, which still includes the corners at each end.

3. 6x + 9y = 3(2x + 3y) is parallel to the cutting line, so every point on the edge from (6, 16) to (15, 10) gives the maximum P = 180. The integer points on that edge are (6, 16), (9, 14), (12, 12) and (15, 10).

4. P = 0, 30, 20, 6 at the four vertices, so the maximum is 30 at (10, 0).

5. For an objective with positive coefficients and the region away from O, there is no maximum (it increases without limit), but a minimum exists at a vertex. Check the direction in which the objective improves.

6. The objective gradient is now -(15/20) = -¾, which is still between -(3/2) (clay) and -½ (glazing), so yes: (14, 9) remains optimal, with P = 15(14) + 20(9) = 390, i.e. £390.