| Term | Meaning |
|---|---|
| Decision variables | The unknowns we want to find (x and y) |
| Objective function | What we want to maximise or minimise (e.g. profit P = 3x+2y) |
| Constraints | The limiting conditions (inequalities) |
| Feasible region | The shaded area satisfying all constraints |
| Optimal solution | The best point in the feasible region |
A factory makes tables (x) and chairs (y). Each table needs 3 hrs carpentry and 2 hrs finishing. Each chair needs 1 hr carpentry and 2 hrs finishing. Available: 12 hrs carpentry and 16 hrs finishing. Profit: Ksh 400 per table, Ksh 250 per chair. Maximise profit.
Variables: x = tables, y = chairs
Objective: Maximise P = 400x + 250y
Constraints:
When x=0: y=12 → point (0,12)
When y=0: x=4 → point (4,0)
Test (0,0): 0 ≤ 12 ✓ → shade side containing origin
Points: (0,8) and (8,0)
Test (0,0): 0 ≤ 8 ✓ → shade side containing origin
The maximum or minimum of the objective function always occurs at a vertex (corner point) of the feasible region.
Vertices of feasible region (read from graph or solve simultaneous equations):
O(0,0), A(4,0), B(2,6), C(0,8)
Test P = 400x + 250y at each:
| Vertex | P = 400x+250y |
|---|---|
| O(0,0) | 0 |
| A(4,0) | 1600 |
| B(2,6) | 800+1500=2300 |
| C(0,8) | 2000 |
Maximum profit = Ksh 2,300 at B(2,6): Make 2 tables and 6 chairs.
A diet must contain at least 30g protein and 20g fat. Food A costs Ksh 5/g protein and Ksh 8/g fat. Food B costs Ksh 7/g protein and Ksh 4/g fat.
Minimise: C = 5x + 7y (cost of protein) subject to constraints.
The minimum occurs at a vertex of the feasible region — test all vertices and take the smallest value.
Alternative to vertex method:
In many real problems, you can't make 2.5 tables — solutions must be integers.
Optimal solution is x=2.5, y=3.5. Test nearby integers in feasible region:
(2,3), (2,4), (3,3) — calculate P for each and pick maximum.
A farmer has 10 acres and Ksh 20,000 to plant maize (x) and beans (y). Maize: 2 acres, Ksh 3000/acre. Beans: 1 acre, Ksh 1500/acre. Expected profit: Ksh 4000/acre maize, Ksh 2500/acre beans.
Constraints: 2x+y≤10, 3000x+1500y≤20000, x≥0, y≥0
Maximise: P = 4000x + 2500y
A truck can carry max 5 tonnes. Small boxes weigh 0.5T, large boxes 1T. Profit: Ksh 200/small box, Ksh 350/large box. At least 2 of each type must be carried.
Maximise: P = 200x + 350y subject to 0.5x+y≤5, x≥2, y≥2
Maximise P = 3x+2y subject to: x+y≤4, x+2y≤6, x≥0, y≥0.
Vertices: O(0,0), A(4,0), B(2,2), C(0,3)
P values: 0, 12, 10, 6
Maximum P = 12 at (4,0)
Minimise C = 2x+3y subject to: x+y≥6, 2x+y≥8, x≥0, y≥0.
Vertices: A(8,0), B(2,4), C(0,8)
C values: 16, 16, 24
Minimum C = 16 at (8,0) or (2,4)
1. The expression to be maximised or minimised is called the .
2. The limiting inequalities in a linear programming problem are called .
3. The shaded area satisfying all constraints is called the .
4. The optimal solution always occurs at one of the of the feasible region.
5. In a profit problem, we want to the objective function.
6. (4 marks) A baker makes bread (x) and cakes (y). Bread needs 2kg flour and 1 egg. Cakes need 1kg flour and 2 eggs. Available: 10kg flour and 14 eggs. Profit: Ksh 50/bread, Ksh 80/cake. Write all constraints and the objective function.
7. (3 marks) For the LP: Maximise P=5x+4y subject to x+y≤5, 2x+y≤8, x≥0, y≥0. Find the vertices and maximum P.
8. (3 marks) A company makes two products X and Y. Product X takes 3 hours machine time and 1 hour labour. Product Y takes 1 hour machine time and 2 hours labour. Available: 12 machine hours and 8 labour hours. If profit is Ksh 300 for X and Ksh 200 for Y, find the production plan that maximises profit.