Lesson 9 of 9 · 10 min
Chapter review
Watch a class
The whole chapter on YouTube
Loading the full lesson
Must-know facts
12 facts
- 01A linear programming problem optimises a linear objective Z = ax + by subject to linear constraints and x, y ≥ 0.
- 02Decision variables are the unknowns x and y; constraints are the linear inequalities on them.
- 03"At most" gives ≤ and "at least" gives ≥; always add x ≥ 0, y ≥ 0.
- 04The feasible region is the common part of all the constraints' half planes; its points are feasible solutions.
- 05The feasible region is convex.
- 06Bounded region: can be enclosed in a circle. Unbounded: cannot.
- 07Theorem 1: an optimal value, when it exists, occurs at a corner point.
- 08Theorem 2: on a bounded region, Z has both a maximum and a minimum, each at a corner.
- 09Corner 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
Where marks are lost
Formulas
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.
Key terms
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.