Linear programming · Linear programming & operations research

A linear programming problem asks for the greatest (or least) value of an expression like $P = ax + by$ when $x$ and $y$ must satisfy several linear inequalities.

The feasible region

Draw each boundary line, then keep the side that satisfies the inequality (see inequalities). Test a point that is not on the line, such as the origin. The region that satisfies all of them at once is the feasible region.

The corner-point method

The greatest and least values of $ax + by$ over the region always occur at a corner. So:

find the corners, by solving the equations of the lines that meet there;
work out $ax + by$ at each corner;
pick the largest (or smallest).

The best point is a cornerSlide the line ax + by = k out: it leaves the region at a corner

The corner-point methodSet the coefficients of P = ax + by

20greatest P(4, 4)at

a = 2b = 3

P = 2x + 3y at the corners: (0, 0) → 0; (6, 0) → 12; (5, 3) → 19; (4, 4) → 20; (0, 6) → 18. The greatest is 20, at (4, 4).

Worked example · NECO 2023

NECO 2023 · Paper 1 · Q49

The corner points of the feasible region of a problem are $A(0, 3)$ , $B(2, 3)$ , $C(4, 3)$ , $D(3, 4)$ and $E(0, 0)$ . If $P = 35x + 40y$ , what is the maximum value of $P$ ?

P at each corner
- ${A(0, 3)}$ : ${120}$ . ${B(2, 3)}$ : ${70 + 120 = 190}$ .
- ${C(4, 3)}$ : ${140 + 120 = 260}$ . ${D(3, 4)}$ : ${105 + 160 = 265}$ . ${E(0, 0)}$ : ${0}$ .
Think first. Put each corner into 35x + 40y.
The greatest
- The maximum is ${265}$ , at $D$ : option E.

Worked example · WAEC 2020

WAEC 2020 · Paper 2 · Q4

Shade the region, $P$ , in the $x$ – $y$ plane which satisfies simultaneously the inequalities:

$x + y \ge 5, \qquad 2y - x \ge 0, \qquad x + 5y \le 21$

Use the diagram in 4(a) to find, on the region $P$ , the minimum value of $x$ ;

the maximum value of $(3x + 2y)$ .

The region
- ${3 + 3 = 6 \ge 5}$ , ${6 - 3 = 3 \ge 0}$ and ${3 + 15 = 18 \le 21}$ : $(3, 3)$ is in $P$ , a triangle.
Think first. Test (3, 3) in all three inequalities.
The corners
- ${x + y = 5}$ and ${x + 5y = 21}$ : ${4y = 16}$ , so ${(1, 4)}$ .
- ${y = \frac{x}{2}}$ and ${x + y = 5}$ : ${\frac{3x}{2} = 5}$ , so ${\left(\frac{10}{3}, \frac53\right)}$ .
- ${y = \frac{x}{2}}$ and ${x + 5y = 21}$ : ${\frac{7x}{2} = 21}$ , so ${(6, 3)}$ .
Think first. Solve each pair of boundary lines.
Least x, greatest 3x + 2y
- The least $x$ on the region is at ${(1, 4)}$ : ${x = 1}$ .
- ${3x + 2y}$ : ${11}$ , ${13\frac13}$ and ${24}$ . The greatest is ${24}$ , at ${(6, 3)}$ .

More: regions

WAEC 2023 · Paper 2 · Q11Using a scale of 2 cm to 2 units on both axes, indicate on a graph sheet the area bounded by the inequalities $4y - x \le 4$ , …

Your turn

WAEC 2012 · Paper 2 · Q4

Linear programming & operations research

(a)
Indicate by shading graphically the set of all points $P(x, y)$ in the $Oxy$ plane that satisfy simultaneously the inequalities $2x - y \ge -4$ , $x + y \le 10$ , $y - x > 0$ , $y \ge 2$ and $x \ge 0$ .
Model answer
Draw each boundary line, then shade the side that satisfies every inequality. The region $R$ has corners $(5, 5)$ , $(2, 8)$ , $(0, 4)$ , $(0, 2)$ , $(2, 2)$ . The line $y = x$ is dashed because $y - x > 0$ is strict (points on it are not included). WAEC accepts either shading the wanted region or shading the unwanted side, as long as you label the region clearly.

For (b): check $10x + 5y$ at each corner; the largest value, 75, is at $(5, 5)$ .
(b)
Using the graph, find the values of $x$ and $y$ for which $10x + 5y$ is maximum.
Separate values with commas, e.g. 3, −2

Try it on a graph

The feasible region; test the corners in 10x + 5y.

Worked solution (try it first)

(a)

Draw $2x - y = -4$ , $x + y = 10$ , $y = x$ (dashed, since $y - x > 0$ ), $y = 2$ and $x = 0$ , and shade the region that satisfies all five.
Its corners: $(0, 2)$ .
$y = 2$ and $y = x$ give $(2, 2)$ .
$y = x$ and $x + y = 10$ give $(5, 5)$ .
$x + y = 10$ and $2x - y = -4$ give $3x = 6$ , so $(2, 8)$ .
$2x - y = -4$ and $x = 0$ give $(0, 4)$ .

(b)

$10x + 5y$ at the corners: $10$ , $30$ , $75$ , $60$ and $20$ .
The maximum is $75$ , at $x = 5$ , $y = 5$ .

Report a problem with this question