Lesson 9 of 9 · 10 min

Chapter review

Watch a class

The whole chapter on YouTube

12 facts

1A linear programming problem optimises a linear objective Z = ax + by subject to linear constraints and x, y ≥ 0.
2Decision variables are the unknowns x and y; constraints are the linear inequalities on them.
3"At most" gives ≤ and "at least" gives ≥; always add x ≥ 0, y ≥ 0.
4The feasible region is the common part of all the constraints' half planes; its points are feasible solutions.
5The feasible region is convex.
6Bounded region: can be enclosed in a circle. Unbounded: cannot.
7Theorem 1: an optimal value, when it exists, occurs at a corner point.
8Theorem 2: on a bounded region, Z has both a maximum and a minimum, each at a corner.
9Corner point method: find corners, evaluate Z at each, pick the largest or smallest.
10Two corners with the same optimal value make every point of the edge between them optimal.
11Unbounded region: M is the maximum only if ax + by > M misses the region; m is the minimum only if ax + by < m misses it.
12Contradictory constraints give an empty region and no solution.

Common traps

Forgetting the non-negative restrictions and taking corners with negative x or y.

x ≥ 0 and y ≥ 0 are constraints too; the region lies in the first quadrant.

Writing "at least 10 trays" as x + y ≤ 10.

"At least" means the total may not fall below 10: x + y ≥ 10.

Missing a corner where a constraint line meets an axis.

Walk round the whole boundary of the region and list every vertex, including those on the axes.

Reading a corner's coordinates off the graph when the lines cross at an awkward point.

Solve the two boundary equations simultaneously.

Declaring the smallest corner value the minimum on an unbounded region.

Test the open half plane ax + by < m; if it meets the region, there is no minimum.

Giving one point as the answer when two corners tie.

Every point of the edge joining the tied corners is optimal.

Shading the wrong side of a line.

Substitute a test point such as (0, 0) into the inequality.

4 to know

Objective function

Z = ax + by

a, b constants; x, y decision variables.

Level line of Z

ax + by = k

Lines for different k are parallel.

Max test (unbounded)

ax + by > M has no feasible point ⇒ max = M

M the largest corner value.

Min test (unbounded)

ax + by < m has no feasible point ⇒ min = m

m the smallest corner value.

7 terms

Objective function: The linear expression Z = ax + by that is to be maximised or minimised.
Decision variables: The unknowns, such as x and y, whose values make up a plan.
Constraints: The linear inequalities or equations that the variables must satisfy.
Feasible region: The set of points satisfying every constraint, non-negativity included.
Corner point: A point of the feasible region where two of its boundary lines meet.
Optimal solution: A feasible point at which the objective function takes its best value.
Bounded region: A region that fits inside some circle.