Library › Further Decision Mathematics 1 WDM11 › Graphical Solution of LP problems

AS Level · Further Decision Mathematics 1 WDM11

Graphical Solution of LP problems

Revise Graphical Solution of LP problems for Further Decision Mathematics 1 WDM11 (AS Level) — revision notes and instant AI marking. Free to start.

📖 Revision notes · preview

Edexcel A Level Further Maths · Decision 1

Graphical Solution of LP Problems

The Big Idea: When you draw all the constraints of a linear programming problem on a graph, they trap a region of "allowed" points — and the best possible answer always sits at one of the corners of that region, never in the middle.

Summary — What This Chapter Covers

Feasible region: the area on a graph that satisfies every constraint at once — found by shading OUT the parts that don't work, leaving the answer unshaded and labelled R.
Objective line method: draw a trial line for the objective function, then slide a ruler parallel to it across the region — the last vertex it touches is the optimal solution.
Vertex method: find the coordinates of every corner of the feasible region (by solving simultaneous equations), plug each into the objective function, and pick the best value.
Integer solutions: when decision variables must be whole numbers (you can't make 3.65 chairs), check the four integer points surrounding the true optimal solution.

1. What Even Is a Linear Programming Problem?

Imagine you run a small furniture workshop. You make chairs (x per day) and tables (y per day). You want to make as much profit as possible — but you're limited by how much wood you have, how many hours your staff can work, and how much storage space exists.

Each of those limits is a constraint — an inequality like 3x + 2y ≤ 24. Your profit is the objective function — something like P = 30x + 40y, which you want to maximise (or in other problems, minimise, e.g. minimising cost).

A linear programming (LP) problem always has this same skeleton:

Structure of an LP Problem

Maximise/Minimise P = ax + by subject to several inequalities in x and y

In plain English: "find the best combination of x and y, without breaking any of the rules."

For problems with just two decision variables (x and y), we can literally see the answer by drawing a graph — that's what this whole chapter is about.

What about 3 variables? Sometimes a third variable z sneaks in — e.g. "the number of desks made is twice the number of tables," so z = 2y. You substitute this relationship into every constraint so that everything is written in terms of just two variables again. Then it's business as usual.

2. The Feasible Region

What is it?

The feasible region is the set of every point (x, y) that satisfies all the constraints simultaneously — including the "hidden" constraint that you usually can't have negative amounts of anything (x ≥ 0, y ≥ 0).

Think of it like a Venn diagram of allowed zones, except instead of circles you're overlapping half-planes cut off by straight lines. Wherever all the allowed zones overlap — that's your feasible region.

How to actually draw it — step by step

Plot each inequality as a straight line. Either rearrange to y = mx + c, or (often easier) find two points that satisfy the equation (e.g. set x = 0, then set y = 0) and join them with a ruler.

Decide solid or dashed: solid line for ≤ or ≥ (the boundary is included), dashed line for < or > (boundary excluded). In LP problems, strict inequalities are rare — almost everything is ≤ or ≥.

Shade the side of the line that is NOT allowed (the side that fails the inequality). Yes — you shade the wrong side, not the right side!

After shading every constraint, whatever's left unshaded is your feasible region. Label it with a capital R.

Why shade the "wrong" side? With several constraints overlapping, shading the failing regions means the feasible region is the one clean blank patch — much easier to spot than trying to identify overlapping cross-hatched shading for the "correct" side. If you're using graphing software, it often shades the side that DOES satisfy the inequality — a neat workaround is to type in the reversed inequality sign so the software shades the same way as you would by hand.

Worked Example

Maximise P = 30x + 40y subject to:

x + y ≤ 10 3x + 2y ≤ 24 x + 2y ≤ 18 x, y ≥ 0

Line 1: x + y = 10 → passes through (0,10) and (10,0). Gradient −1.
Line 2: 3x + 2y = 24 → passes through (0,12) and (8,0).
Line 3: x + 2y = 18 → passes through (0,9) and (18,0).

Plot all three solid lines (all are ≤), plus the axes for x ≥ 0 and y ≥ 0. Shade the unwanted side of each. The blank patch left near the origin — bounded by parts of all these lines — is the feasible region R. Its corners (reading from the graph) turn out to be (0,0), (8,0), (6,3), (2,8), and (0,9).

Practice Question 1

A constraint is given as 2x + 5y ≤ 20. Find two points that lie exactly on the boundary line, and state whether the line should be drawn solid or dashed.

Practice Question 2

Explain, in your own words, why the point (0,0) usually satisfies most "less than or equal to" constraints in an LP problem — and why this is a handy quick check.

3. The Objective Line Method

What is the objective line?

The objective function P = ax + by can be rearranged into the familiar form y = mx + c. That means for any fixed value of P, this is just the equation of a straight line — the objective line. Different values of P give a whole family of parallel lines, all with the same gradient, just shifted up or down.

Key Insight

Increasing P → line moves AWAY from the origin (for maximising)

Decreasing P → line moves TOWARDS the origin (for minimising). Every line in the family is parallel — only its position shifts.

y | ← lines all PARALLEL, sliding | ___ away from origin as P grows | / \___ | / R \___ objective lines |/____________\___ +------------------- x (0,0)

Because the objective line always moves in one direction as P changes, the very last point of the feasible region it touches (as you push it as far as possible while still touching R) must be a vertex (corner) — never an edge or the middle. That vertex is your optimal solution.

Method — step by step

Pick a "nice" trial value of P — ideally a common multiple of the coefficients a and b, so the line crosses the axes at whole numbers.

Plot this trial objective line the same way as any straight line (find where it crosses each axis).

Using a ruler kept exactly parallel to this line, slide it across the feasible region — away from the origin if maximising, towards the origin if minimising.

The last vertex your ruler touches before leaving the feasible region is the optimal solution. Substitute its coordinates back into P to find the optimal value.

Exam tip from the notes: To show clear working (and pick up method marks), draw a new objective line every time your ruler passes through a vertex of the feasible region on its way across — this visually demonstrates you understand which vertex is "last."

Worked Example

Feasible region R has vertices (0,0), (8,0), (4,6), (2,8), (0,9). Maximise P = 30x + 40y.

Trial line: choose P = 120 (multiple of both 30 and 40) → 30x + 40y = 120, which passes through (0,3) and (4,0). Plot it.

Slide the ruler up and away from the origin, drawing a new parallel line each time it crosses a vertex: at (8,0), then (4,6), then (2,8) — where it finally leaves the region.

Optimal solution: (2, 8) → P = 30(2) + 40(8) = 60 + 320 = 380.

Practice Question

A feasible region has vertices (0,0), (6,0), (5,3), (0,7). The objective is to minimise P = 4x + 3y. Which direction should you slide the ruler, and which vertex is most likely to give the minimum?

4. The Vertex Method

Rather than physically sliding a ruler, the vertex method finds the coordinates of every corner of the feasible region algebraically, then just tests each one in the objective function like a shortlist.

Why This Works

Optimal solution ALWAYS occurs at a vertex of R

So instead of guessing, just check every vertex — the best one wins. It's a guaranteed method, no ruler required.

Method — step by step

Find the coordinates of every vertex of R. Some are obvious (the origin, or points on an axis). Others need solving simultaneous equations — pick the two lines that cross at that corner and solve them together.

Substitute each vertex's (x, y) into the objective function P = ax + by and evaluate it. A table is the cleanest way to organise this.

Read off whichever vertex gives the maximum (or minimum, depending what's asked) value of P — that's your optimal solution.

Don't skip the origin! Even in maximising problems where it's "obviously" not going to win, the origin is still a genuine vertex of the feasible region and should be listed in your table — leaving it out can lose you a method mark, even though it never turns out to be optimal.

Worked Example

Maximise P = 2x + 5y, feasible region bounded by x ≥ 0, y ≥ 0, y − 2x ≤ 2, x + 4y ≤ 17, x + y ≤ 8.

Obvious vertices: (0,0); intersection of x=0 with y−2x=2 gives (0,2); intersection of x+y=8 with y=0 gives (8,0).

Solving for the "hidden" corners:

y − 2x = 2 and x + 4y = 17:
From the first, y = 2 + 2x. Substitute: x + 4(2+2x) = 17 → 9x = 9 → x = 1, y = 4. Vertex: (1, 4).

x + 4y = 17 and x + y = 8:
Subtract: 3y = 9 → y = 3, x = 5. Vertex: (5, 3).

x	y	P = 2x + 5y
0	0	0
0	2	10
8	0	16
1	4	22
5	3	25 ✓ MAX

Optimal solution: x = 5, y = 3, giving a maximum value of P = 25.

Practice Question

Two constraint lines are 2x + y = 14 and x + 3y = 22. Find their point of intersection (a candidate vertex of a feasible region).

5. Integer Solutions

Sometimes the "mathematically perfect" optimal solution lands on a decimal, like x = 3.2, y = 4.7 — but the real world doesn't always allow that. You can't bake 4.7 cakes or hire 3.2 employees. When the context demands whole numbers, you need the integer solution closest to (and still inside) the feasible region.

Method

Check the 4 integer points surrounding the true optimal solution

For an optimal solution like (3.2, 4.7), the four surrounding integer points are (3,4), (3,5), (4,4), (4,5) — round down and up in both directions.

(3,5) ×───────× (4,5) \ R / \ / (3.2, 4.7) ← true optimal (not integer!) / \ (3,4) ×───────× (4,4)

Method — step by step

Find the true (possibly decimal) optimal solution using the objective line or vertex method as normal.

Identify the four surrounding integer-coordinate points (round x and y up and down).

Check each of the four points against every single constraint — a point that fails even one constraint is thrown out immediately (you don't need to check the rest for that point).

For the points that survive all checks, evaluate P at each, and pick whichever gives the best (max/min) result.

Careful — this is NOT always the true optimum! The objective line moves away from the boundary once you land on a valid integer point, meaning there could technically be another integer point elsewhere in the feasible region that's even better. You are not expected to search for it — just know that "the integer solution nearest the optimal point" is a good, sensible answer, not necessarily a perfect one.

Worked Example

Optimal (non-integer) solution: x = 3.2, y = 4.7, giving P = 5x + 10y = 63.

The four surrounding integer points: (3,4), (3,5), (4,5), (4,4).

(x, y)	Satisfies all constraints?	P = 5x + 10y
(3, 4)	✔ Yes	55
(3, 5)	✘ No	—
(4, 5)	✘ No	—
(4, 4)	✔ Yes	60 ✓ BEST

Integer solution closest to optimal: x = 4, y = 4, giving P = 60.

Practice Question

The true optimal solution to an LP problem is x = 6.4, y = 2.1. List the four integer coordinate points you would need to check.

What to Memorise

Feasible Region

The unshaded area satisfying ALL constraints (including x, y ≥ 0). Labelled R.

Objective Line

P = ax + by rearranged to y = mx + c. Slide parallel copies — away from origin to maximise, towards origin to minimise.

Vertex Method

Solve pairs of boundary equations simultaneously to find every corner, then test each in P = ax + by.

Integer Solutions

Check the 4 integer points surrounding the true optimum; discard any that fail a constraint; pick the best surviving one.

Line Style

Solid line for ≤ / ≥ (boundary included). Dashed line for < / > (boundary excluded, rare in LP).

Shading Rule

Always shade the side that does NOT satisfy the inequality — the blank space left over is R.

Concepts Checklist

I can explain what an LP problem's objective function and constraints represent.

I can accurately plot a constraint as a straight line by finding two points on it.

I know when to draw a solid line versus a dashed line.

I can correctly shade the unwanted side of each inequality to reveal the feasible region R.

I understand why the optimal solution must lie at a vertex, not inside the region.

I can use the objective line method, choosing a sensible trial value of P and sliding a ruler.

I can use the vertex method by solving simultaneous equations for each corner.

I remember to always include the origin (or axis points) as vertices, even when unlikely to be optimal.

I can find and test the four integer points surrounding a non-integer optimal solution.

I understand that the "nearest integer solution" found this way isn't guaranteed to be the true best integer answer.

Exam Tips & Common Mistakes

Mistake: Shading the wrong side A huge number of marks are lost simply by shading the side that DOES satisfy the inequality instead of the side that doesn't. Always double-check with a test point like (0,0) — if it satisfies the inequality, shade away from it (since that's the unwanted side).

Mistake: Forgetting non-negativity constraints Even if a question doesn't explicitly restate x ≥ 0, y ≥ 0, in real LP contexts (numbers of chairs, hours, litres) they're basically always implied and usually ARE stated — don't forget to plot and shade them like any other constraint.

Mistake: Picking an awkward trial value of P If P = 30x + 40y and you choose P = 17, you'll get ugly fractional axis crossings that are hard to plot accurately. Always pick a common multiple of the coefficients (here, 120) so your trial line hits nice whole-number points.

Mistake: Assuming the origin is always the answer to minimise It often is, but only check this once you've confirmed (0,0) is actually a vertex of the feasible region for that specific problem — some constraints push the region away from the origin entirely.

What examiners actually want to see: Clear labelling of every line and inequality directly on the graph, the feasible region clearly marked with R, and (for the objective line method) evidence of at least one extra parallel line being drawn as your ruler "travels" — this shows understanding, not just a lucky guess at the final vertex.

Common question pattern to expect: "Show graphically the feasible region R" → "Use the objective line/vertex method to find the optimal solution" → "The decision variables must be integers — find the nearest integer solution." Practise all three stages together, since they're almost always asked as one connected question.

Also in the full note

Exam Tips & Common Mistakes

What's inside

📖 Revision notes ✦ AI flashcards ✓ Instant AI marking

Read the full Graphical Solution of LP problems notes free

That's the preview — create a free account to read the rest, plus flashcards and practice questions with instant AI marking. No credit card.

Unlock the full notes free →

Graphical Solution of LP problems

Graphical Solution of LP Problems

Summary — What This Chapter Covers

1. What Even Is a Linear Programming Problem?

2. The Feasible Region

What is it?

How to actually draw it — step by step

Worked Example

3. The Objective Line Method

What is the objective line?

Method — step by step

Worked Example

4. The Vertex Method

Method — step by step

Worked Example

5. Integer Solutions

Method — step by step

Worked Example

What to Memorise

Feasible Region

Objective Line

Vertex Method

Integer Solutions

Line Style

Shading Rule

Concepts Checklist

Exam Tips & Common Mistakes

More Further Decision Mathematics 1 topics