Formulating a linear programming problem
A baker has limited oven time and limited helpers, but wants the most profit from cakes and pies. Turning such a story into numbers and inequalities is called formulation.
A linear programming problem has three parts: an objective function Z = ax + by to be maximised or minimised, constraints, which are linear inequalities, and non-negativity conditions x ≥ 0, y ≥ 0. The unknowns x and y are decision variables, such as the number of cakes and pies.
Formula: Maximise or minimise Z = ax + by subject to px + qy ≤ r (or ≥ r), x ≥ 0, y ≥ 0
Rule 1: Variables and objective — Name what to decide, then write the profit or cost.
- Easy: Profit of ₹40 per cake (x) and ₹30 per pie (y) gives Z = 40x + 30y.
- Medium: Each cake needs 2 hours of oven time and each pie 1 hour, with 100 hours available, so 2x + y ≤ 100.
- Exam-type: A diet needs at least 12 units of a vitamin; tablet A gives 3 and tablet B gives 2 units, so 3x + 2y ≥ 12.
Rule 2: Check a point — Put it in every constraint.
- Easy: (10, 10) is feasible for 2x + y ≤ 100 and x + y ≤ 80.
- Medium: (50, 50) is not feasible, because 2(50) + 50 = 150 is more than 100.
- Exam-type: Z = x² + y is not a linear objective function.
In a linear programming problem every expression is of the first degree. Never forget x ≥ 0 and y ≥ 0.
Reversing the sign of an inequality: "at most" is ≤ and "at least" is ≥.
Decide, maximise, limit, and keep it positive.
Practice questions
- 1Name the three parts of a linear programming problem.
- 2A cake gives a profit of ₹40 and a pie gives ₹30. Write the objective function.
- 3Each cake needs 2 oven hours and each pie 1 hour. Only 100 hours are available. Write the constraint.
- 4Is Z = x² + y a linear objective function?
- 5Write the non-negativity conditions for x cakes and y pies.
- 6Is (10, 10) feasible for 2x + y ≤ 100 and x + y ≤ 80?
- 7Is (50, 50) feasible for the same constraints?
- 8A diet needs at least 12 units of a vitamin. Tablet A gives 3 units and B gives 2 units. Write the constraint.
Show answers (try them yourself first)
- 1Objective function, constraints and non-negativity conditions
- 2Z = 40x + 30y
- 32x + y ≤ 100
- 4No, because x² makes it non-linear
- 5x ≥ 0 and y ≥ 0
- 6Yes, since 30 ≤ 100 and 20 ≤ 80
- 7No, since 2(50) + 50 = 150 is more than 100
- 83x + 2y ≥ 12
Graphical (corner point) method
The best spot in a plot of land is always at one of its corners. In the same way, the best value of a linear function over a polygon region is always found at a corner point.
Draw all constraints and shade the common region, which is the feasible region. Find its corner points, evaluate Z at each, and compare. For a bounded region the largest value is the maximum and the smallest is the minimum. For an unbounded region, a minimum exists only if the half-plane Z < m has no point in common with the region.
Formula: Optimal value of Z = the largest or smallest of the values of Z at the corner points
In the figure: The line x + y = 4 cuts the axes at B(4, 0) and C(0, 4). With x ≥ 0 and y ≥ 0, the shaded feasible region of x + y ≤ 4 is the triangle OBC, with corner points O(0, 0), B and C.
Rule 1: Corner point method — List the corners, evaluate Z, compare.
- Easy: Maximise Z = 3x + 2y with x + y ≤ 4, x ≥ 0, y ≥ 0. Corners (0, 0), (4, 0), (0, 4) give Z = 0, 12, 8, so the maximum is 12 at (4, 0).
- Medium: Maximise Z = 40x + 30y with 2x + y ≤ 100, x + y ≤ 80, x, y ≥ 0. Corners (0, 0), (50, 0), (20, 60), (0, 80) give Z = 0, 2000, 2600, 2400, so the maximum is 2600 at (20, 60).
- Exam-type: Minimise Z = 2x + 3y with x + y ≥ 4, x, y ≥ 0. Corners (4, 0) and (0, 4) give 8 and 12. The region is unbounded, but 2x + 3y < 8 has no common point with it, so the minimum is 8 at (4, 0).
Rule 2: Special cases — Equal values at two corners, or no corner.
- Easy: Maximise Z = x + y with x + y ≤ 5. Corners (5, 0) and (0, 5) give the same value 5, so every point on the segment between them is optimal.
- Medium: Maximise Z = 5x + 4y with x + y ≤ 6, x ≤ 4, x, y ≥ 0. Corners (0, 0), (4, 0), (4, 2), (0, 6) give 0, 20, 28, 24, so the maximum is 28 at (4, 2).
- Exam-type: Minimise Z = x + y with x + 2y ≥ 6, 3x + y ≥ 6, x, y ≥ 0. Corners (0, 6), (6/5, 12/5), (6, 0) give 6, 18/5, 6, so the minimum is 18/5.
The optimum is always at a corner point (or along an edge between two corners). Always evaluate Z at all corners.
Evaluating Z only at the corner that looks best, or choosing a point inside the region.
Draw, find corners, test every corner.
Practice questions
- 1Maximise Z = 3x + 2y subject to x + y ≤ 4, x ≥ 0, y ≥ 0.
- 2Minimise Z = 2x + 3y subject to x + y ≥ 4, x ≥ 0, y ≥ 0.
- 3Maximise Z = 40x + 30y subject to 2x + y ≤ 100, x + y ≤ 80, x ≥ 0, y ≥ 0.
- 4Maximise Z = 5x + 4y subject to x + y ≤ 6, x ≤ 4, x ≥ 0, y ≥ 0.
- 5Minimise Z = x + y subject to x + 2y ≥ 6, 3x + y ≥ 6, x ≥ 0, y ≥ 0.
- 6Find the corner points of the region x + y ≤ 4, x ≥ 0, y ≥ 0.
- 7The corner points of a region are (0, 0), (5, 0), (3, 4) and (0, 6). Find the maximum of Z = x + y.
- 8Maximise Z = x + y subject to x + y ≤ 5, x ≥ 0, y ≥ 0. How many points give the maximum?
Show answers (try them yourself first)
- 1Corners (0, 0), (4, 0), (0, 4) give Z = 0, 12, 8; maximum 12 at (4, 0)
- 2Corners (4, 0) and (0, 4) give 8 and 12; minimum 8 at (4, 0)
- 3Maximum 2600 at (20, 60)
- 4Corners (0, 0), (4, 0), (4, 2), (0, 6) give 0, 20, 28, 24; maximum 28 at (4, 2)
- 5Corners (0, 6), (6/5, 12/5), (6, 0) give 6, 18/5, 6; minimum 18/5 at (6/5, 12/5)
- 6(0, 0), (4, 0) and (0, 4)
- 7Z = 0, 5, 7, 6, so the maximum is 7 at (3, 4)
- 8Infinitely many: every point of the segment from (5, 0) to (0, 5) gives Z = 5