- Chapter 12
- Linear Programming
- 20 questions
Linear Programming
Terminology, mathematical formulation, graphical solution, feasible regions and optimal solutions.
A factory has a fixed number of machine hours and a fixed amount of raw material, and wants the most profitable production plan. That is a linear programming problem, and it is solved with a graph rather than with calculus.
The key fact is that the optimum of a linear objective function always occurs at a corner of the feasible region, so the whole method reduces to drawing the region, listing its corner points, and evaluating the objective at each. The hardest part in an examination is usually the translation of the word problem into constraints — the graphing that follows is mechanical.
What you should be able to do
- Use the terminology of linear programming correctly: constraints, objective function, feasible region, optimisation.
- Translate a word problem into a linear programming problem with correct constraints.
- Draw the feasible region and identify its corner points.
- Find the optimal solution, and determine whether an unbounded region has one.
Topics
4 topics
- Introduction and Terminology
Constraints, objective function, decision variables and optimisation.
- Mathematical Formulation
Turning a described situation into decision variables, constraints and an objective function.
- Graphical Method and Feasible Region
Drawing the feasible region, distinguishing bounded from unbounded regions, and identifying corner points.
- Optimal Feasible Solutions
Evaluating the objective at corner points, and the extra test required when the region is unbounded.
Formulas
5 items · All formulas
Objective function
Z = ax + byThe quantity to be maximised or minimised.
Non-negativity constraints
x \geq 0, \qquad y \geq 0Almost always present, since the decision variables represent physical quantities.
Corner point theorem
\text{The optimum of } Z \text{ over a feasible region occurs at a corner point.}- Valid when
- The region must be bounded for the optimum to be guaranteed to exist.
Unbounded region — maximum test
M \text{ is the maximum} \iff ax + by > M \text{ has no point in the feasible region}Unbounded region — minimum test
m \text{ is the minimum} \iff ax + by < m \text{ has no point in the feasible region}
Key points
6 items · All key points
The optimum always occurs at a corner point of the feasible region.
For an unbounded region, a corner value is only the optimum if the extra half-plane test passes.
Check whether ax+by > M (for a maximum) meets the region. If it does, no maximum exists.
Never omit the non-negativity constraints x \geq 0, y \geq 0 from the formulation.
Find corner points by solving the boundary lines simultaneously — do not read them off the sketch.
If two adjacent corners give the same optimal value, every point on the segment between them is optimal.
Use the origin to test which side of a line to shade, unless the line passes through the origin.
Common mistakes
5 items · All common mistakes
- Mistake
Reporting the corner point as the answer when the maximum or minimum value was asked for.
InsteadSubstitute the corner coordinates into Z and state the value, along with where it occurs.
- Mistake
Treating an unbounded region exactly like a bounded one.
InsteadApply the open half-plane test. An unbounded region may have no maximum at all.
WhyThe corner point theorem is remembered without the boundedness condition attached to it.
- Mistake
Omitting x \geq 0 and y \geq 0 from the constraints.
InsteadInclude them; they usually form two of the boundaries of the feasible region.
WhyThey are implicit in the physical situation, so they feel too obvious to write.
- Mistake
Shading the wrong side of a constraint line.
InsteadSubstitute (0,0) into the inequality. If it holds, shade the side containing the origin.
- Mistake
Estimating the coordinates of a corner point from the graph.
InsteadSolve the two boundary equations simultaneously for an exact answer.