Setting up the problem
In linear programming we find the largest or smallest value of an objective function subject to linear constraints. The steps are: define the variables, write the constraints as inequalities (including x ≥ 0, y ≥ 0), draw the feasible region, and test its vertices or move a line of constant value across it.
The iso-profit (or iso-cost) line
Draw the line of the objective function, for example 5x + 4y = 20. All points on it give the same value. Slide the line parallel to itself; the last point it touches in the feasible region gives the maximum, and the first gives the minimum.
Worked exampleMaximising
Maximise P = 3x + 2y subject to x + y ≤ 8, x ≤ 5, y ≤ 6, x, y ≥ 0.
- Vertices: (0, 0), (5, 0), (5, 3), (2, 6), (0, 6).
Answer: The maximum is 21 at (5, 3).
Try itDiet cost
Choose x and y. The model checks the two nutrient constraints and gives the cost.
Key terms
- Objective function
- The quantity to optimise.
- Constraint
- A linear inequality limiting the variables.
- Feasible region
- The set of points satisfying all constraints.
- Iso-profit line
- A line along which the objective function is constant.
Summary
- Write constraints, draw the feasible region, find the vertices.
- Evaluate the objective function at each vertex.
- Maximum or minimum values occur at a vertex.
- Interpret the answer in the context.