Linear inequalities and linear programming

NUST NET (Engineering) · Maths · Analytic geometry. A short explanation of the idea, the rules to remember, the mistake to avoid, a worked example and practice questions with answers.

Test this topic free All NUST NET (Engineering) topics

The idea

A linear inequality in x and y describes a half-plane: all the points on one side of a straight line. To graph it, draw the boundary line, then test one point (the origin is easiest) to see which side to keep.

Several inequalities together give the feasible region, the set of points that satisfy every constraint at once. The conditions x ≥ 0 and y ≥ 0 keep it in the first quadrant.

In linear programming you maximise or minimise an objective function z = ax + by over this region. You do not search the whole region: the best value always occurs at a corner point, so find the corners and test each one.

Rules to remember

Boundary line: solid for ≤ or ≥ (points on the line included), broken for < or > (points on the line excluded)
Test (0, 0) in the inequality: if it is true, the solution is the side containing the origin; if false, the other side. Use another point if the line passes through the origin
Feasible region = the part of the plane common to all the constraints
Corner points are where two boundary lines meet; solve the pair of equations, then check the point satisfies every other constraint
The maximum and minimum of z = ax + by over a closed and bounded feasible region occur at corner points: evaluate z at each corner and compare
If two neighbouring corners give the same best value, every point on the edge joining them is also optimal

Common mistake

Counting every intersection of two boundary lines as a corner point. An intersection is a corner only if it satisfies all the constraints, so check each one before using it.

Worked example

Maximise z = 5x + 3y subject to x + y ≤ 6, x ≤ 4, x ≥ 0, y ≥ 0.

Corner points: (0, 0), (4, 0), (0, 6), and x = 4 with x + y = 6 gives (4, 2).
z at each: (0, 0) → 0; (4, 0) → 20; (4, 2) → 20 + 6 = 26; (0, 6) → 18.
The largest value is 26.

Answer: Maximum z = 26 at (4, 2)

Practice questions

Try each one, then open the answer.

1. Subject to x + y ≥ 3, 0 ≤ x ≤ 4 and 0 ≤ y ≤ 4, the minimum value of z = 2x + 5y is

A
6
B
0
C
8
D
15

Show answer

Answer: A. The corners (3, 0), (4, 0), (4, 4), (0, 4) and (0, 3) give z = 6, 8, 28, 20 and 15, so the minimum is 6 at (3, 0). The origin gives 0 but is not feasible, since 0 + 0 < 3.

2. Subject to 2x + y ≤ 10, x + 2y ≤ 8, x ≥ 0, y ≥ 0, the maximum value of z = x + y is

Show answer

Answer: C. 2x + y = 10 and x + 2y = 8 meet at (4, 2). The corners (0, 0), (5, 0), (4, 2) and (0, 4) give z = 0, 5, 6 and 4, so the maximum is 6. The point (5, 4) that gives 9 is not feasible.

3. Which point lies in the solution region of 2x + 3y ≤ 12, x ≥ 0, y ≥ 0?

A
(5, 1)
B
(2, 3)
C
(3, 2)
D
(0, 5)

Show answer

Answer: C. (3, 2) gives 6 + 6 = 12 ≤ 12, which is true (points on the boundary line count). The others give 13, 13 and 15, all greater than 12.

Keep going

← Circles and conic sections Vectors in space →All rules on one page Stuck? Ask a question