Linear Programming
Algebra · Linear Programming
Syllabus tag: KCSE | Mathematics | Form 4 | Topic 6 Linear Programming
Lesson objectives
By the end of this topic, you should be able to:
- Form linear inequalities based on real life situations.
- Represent the inequalities on a graph and identify the feasible region.
- Optimise a given objective function by the search line method.
- Interpret the optimum solution in context.
Linear Programming
Linear programming finds the best outcome subject to constraints, using inequalities and a graph.
a) The method
b) Defining the variables
State clearly what each letter represents, including its units.
"Let x be the number of tables and y the number of chairs" is a complete definition. "Let x be tables" is not.
Marks are given for this step.
c) Forming the inequalities
Each constraint becomes one inequality.
"At most 40 hours available" gives ≤ 40. "At least 10 items" gives ≥ 10.
Include the non-negativity constraints x ≥ 0 and y ≥ 0. Quantities of real objects cannot be negative, and omitting these opens the region wrongly.
Check the units match on both sides before writing the inequality down.
d) Drawing the region
Draw each boundary line from the corresponding equation.
Use a solid line for ≤ or ≥, and a dashed line for < or >.
Shade the unwanted side of each line. What remains unshaded after all the lines is the feasible region.
Shading the unwanted side is the usual convention here. With four or five constraints the wanted region then stays clear and readable.
State clearly which convention you have used.
e) The objective function
The objective function is the quantity to maximise or minimise, such as profit P = 3x + 5y.
f) The search line method
Draw the line 3x + 5y = k for a convenient value of k.
Slide a ruler parallel to that line across the feasible region.
For a maximum, the last point touched as the line moves away from the origin is the solution. For a minimum, it is the first point touched.
Keep the ruler exactly parallel. The gradient of the search line decides the answer, so an inaccurate slope gives the wrong corner.
g) The corner point method
The optimum always occurs at a corner of the feasible region.
So the alternative is to list the corners, evaluate the objective at each, and choose the best.
This is more reliable than sliding a ruler. Use it as a check even when the search line method is asked for.
h) Interpreting the answer
Give the answer in the words of the question, not just as coordinates.
Some variables must be whole numbers, such as tables or people. Check the optimum corner has integer coordinates. If not, test the nearest integer points inside the region.
i) Where this is used
Production planning with limited materials and labour. Diet and feed formulation. Transport scheduling. Any allocation of scarce resources.
Words to know
- Constraint -- a condition limiting the possible values, written as an inequality.
- Feasible region -- the set of points satisfying all constraints simultaneously.
- Objective function -- the quantity to be maximised or minimised.
- Vertex -- a corner of the feasible region, where two boundaries meet.
- Search line -- a line drawn with the objective function's gradient, slid across the region.
:::checkpoint Check yourself
- Why must x ≥ 0 and y ≥ 0 be included?
- When do you draw a boundary line dashed rather than solid?
- Where does the optimum of a linear programming problem always occur?
- What is an objective function? :::
Bridge to practice
The exercises begin with forming inequalities and defining variables, move through graphing and the feasible region, and finish with the vertex and search line methods and interpretation. For every problem, write the non-negativity constraints down before anything else.