- Foundation
- About 16 min
- 5 practice questions
Formulating and solving: a scheduling problem and a blending problem
Work through two complete problems from words to answer: a two-machine production plan to maximise profit, and a two-food mix to minimise cost, with the corner-point check for each.
If something looks wrong, please tell us.
Learning the parts of a linear programming problem is one thing; carrying one all the way from the words to the answer is the real test. This lesson solves one maximisation problem and one minimisation problem, step by step. All the figures are illustrative.
The routine
- Decide what to find and name the variables (include units).
- Write the objective function.
- Turn each limit into an inequality, one at a time, and add x ≥ 0 and y ≥ 0.
- Find the corner points of the feasible region.
- Evaluate the objective at each corner (check that a minimum exists if the region is unbounded).
- Answer in words, with units.
Worked example 1: a two-machine workshop (maximise)
A workshop makes products P and Q. Each unit of P needs 2 hours on machine M1 and 1 hour on machine M2. Each unit of Q needs 1 hour on M1 and 2 hours on M2. Machine M1 can run for at most 14 hours and M2 for at most 16 hours in a day. The profit is ₹30 per unit of P and ₹40 per unit of Q (illustrative figures). Find the plan with the greatest profit.
Let x be the number of units of P and y the number of units of Q. Maximise Z = 30x + 40y subject to 2x + y ≤ 14, x + 2y ≤ 16, x ≥ 0, y ≥ 0. To find the corner where both machines are fully used, solve 2x + y = 14 and x + 2y = 16: doubling the first gives 4x + 2y = 28; subtracting the second gives 3x = 12, so x = 4, and then y = 14 − 8 = 6. The other corners are (0, 0), (7, 0) from 2x = 14 and (0, 8) from 2y = 16.
| Corner | Z = 30x + 40y |
|---|---|
| (0, 0) | 0 |
| (7, 0) | 210 |
| (4, 6) | 120 + 240 = 360 |
| (0, 8) | 320 |
The greatest value is ₹360, from 4 units of P and 6 units of Q. Both machines are used for their full time, so both constraints are binding. A check: M1 uses 2(4) + 6 = 14 hours and M2 uses 4 + 2(6) = 16 hours.
Worked example 2: mixing two foods (minimise)
A diet needs at least 12 units of vitamin and at least 12 units of mineral each day. One unit of food P gives 3 units of vitamin and 1 of mineral, and costs ₹5. One unit of food Q gives 1 unit of vitamin and 3 of mineral, and costs ₹4 (illustrative). Find the cheapest mix.
Let x units of P and y units of Q be used. Minimise Z = 5x + 4y subject to 3x + y ≥ 12, x + 3y ≥ 12, x ≥ 0, y ≥ 0. The two lines meet where 3x + y = 12 and x + 3y = 12: subtracting gives 2x − 2y = 0, so x = y, and 4x = 12, so (3, 3). The axis crossings are (0, 12) from 3x + y = 12 and (12, 0) from x + 3y = 12. These three points are the corners of the region, which is unbounded (it extends away from the origin).
| Corner | Z = 5x + 4y |
|---|---|
| (0, 12) | 48 |
| (3, 3) | 15 + 12 = 27 |
| (12, 0) | 60 |
The smallest corner value is 27 at (3, 3). Because the region is unbounded, we must confirm that 27 really is the minimum. Multiply 3x + y ≥ 12 by 11/8 and x + 3y ≥ 12 by 7/8 and add: (33/8 + 7/8)x + (11/8 + 21/8)y = 5x + 4y ≥ 12 × (18/8) = 27. So every feasible plan costs at least 27, and the minimum is ₹27, from 3 units of each food. A second way: the half-plane 5x + 4y < 27 has no point in common with the region.
Common slips
- Mixing the direction of the inequalities: resource limits are ≤, minimum needs are ≥.
- Forgetting that a minimum on an unbounded region needs the extra check.
- Reporting only the value of Z, and not the plan (x, y) that gives it.
Key takeaways: follow the six-step routine; solve each pair of binding lines for the corner; tabulate Z; for an unbounded region confirm the minimum with a combination of the constraints; state the answer in words with units.
Check your understanding
-
1. In the workshop problem, which constraint says machine M2 works at most 16 hours?
- x + 2y ≤ 16
- x + 2y ≥ 16
- 2x + y ≤ 16
- x + y ≤ 16
Show answer
Answer: A. A unit of P needs 1 hour and a unit of Q needs 2 hours on M2, and the limit is at most 16: x + 2y ≤ 16.
-
2. What is the profit at the plan (7, 0) in the workshop problem?
- ₹360
- ₹320
- ₹210
- ₹280
Show answer
Answer: C. Z = 30(7) + 40(0) = 210.
-
3. In the workshop problem, which corner gives the greatest profit?
- (7, 0)
- (4, 6)
- (0, 8)
- (0, 0)
Show answer
Answer: B. The values are 0, 210, 360 and 320. The greatest is 360 at (4, 6).
-
4. In the diet problem, the cost of the mix (12, 0) is:
- ₹48
- ₹27
- ₹36
- ₹60
Show answer
Answer: D. Z = 5(12) + 4(0) = 60.
-
5. Why is an extra check needed in the diet problem after comparing corner values?
- the cost has negative coefficients
- the feasible region is unbounded
- the corner (3, 3) is not feasible
- there are three variables
Show answer
Answer: B. On an unbounded region the corner values are only candidates for a minimum. A combination of the constraints shows that no plan costs less than 27.
Sign in to keep track of the lessons you finish.