MathMastery.Beta
Start Quiz
Learning Resources

Linear Programming

Interactive curriculum lessons, worked examples, and geometric problem-solving techniques designed to help Kenyan students master CBC, KPSEA, KCSE, and IGCSE mathematics.

Form 4 Pathway: N/A

First Principles

Objective

Formulate and solve linear programming problems using graphical methods to optimize (maximize or minimize) an objective function under given constraints.

Concrete Scenario: A furniture workshop in Nairobi makes desks (\( x \)) and chairs (\( y \)). Each desk needs 2 units of timber and 1 hour of labor; each chair needs 1 unit of timber and 2 hours of labor. With 8 units of timber and 8 hours of labor available daily, how many of each should be produced to maximize profit \( Z = 3000x + 4000y \)?

Linear Programming Insights:

  • Constraints & Feasible Region: Inequalities form straight line boundaries on a Cartesian plane. The shaded area where all inequalities overlap is the feasible region.
  • Corner Point (Vertex) Theorem: The optimal value (maximum or minimum) of a linear objective function \( Z = ax + by \) always occurs at one of the vertices (corners) of the feasible region.
  • Non-Negativity: Since physical quantities cannot be negative, \( x \ge 0 \) and \( y \ge 0 \) always restrict the region to the first quadrant.

Feasible Region & Optimal Vertex

Optimal Vertex (2.7, 2.7)Desks (x)Chairs (y)

Key Formulas

\[Z = c_1 x + c_2 y\] — Objective Function: Quantity to be maximized (profit/revenue) or minimized (cost).
\[a_1 x + b_1 y \le k_1, \quad a_2 x + b_2 y \le k_2\] — Resource Constraints: Linear inequalities representing limits on materials or time.
\[x \ge 0, \quad y \ge 0\] — Non-Negativity Constraints: Restricts solutions to physical domain (first quadrant).
\[Z_{\text{optimal}} = \max_{(x,y) \in \text{Vertices}} \{c_1 x + c_2 y\}\] — Corner Point Method: Test objective function at every vertex of the feasible polygon.

Worked Examples

Example 1 (Easy) — Testing Corner Points:

Problem: Maximise \( Z = 2x + 3y \) subject to \( x + y \le 4 \), \( x \ge 0 \), \( y \ge 0 \).

  1. Identify vertices of the triangular feasible region: \( (0,0) \), \( (4,0) \), and \( (0,4) \).
  2. Evaluate \( Z \) at each vertex:
    • At \( (0,0) \): \( Z = 2(0) + 3(0) = 0 \)
    • At \( (4,0) \): \( Z = 2(4) + 3(0) = 8 \)
    • At \( (0,4) \): \( Z = 2(0) + 3(4) = 12 \)
  3. Select maximum: \( Z_{\max} = 12 \) at \( (0,4) \).
Example 2 (Medium) — Workshop Optimization:

Problem: Maximise profit \( Z = 3x + 4y \) subject to timber constraint \( 2x + y \le 8 \) and labor constraint \( x + 2y \le 8 \) (where \( x, y \ge 0 \)).

  1. Find line intersections: \( 2x + y = 8 \) and \( x + 2y = 8 \).
  2. Subtracting equations gives \( x = 2.67 \) (or \( \frac{8}{3} \)) and \( y = 2.67 \) (or \( \frac{8}{3} \)).
  3. List vertices: \( (0,0) \), \( (4,0) \), \( (0,4) \), and \( (\frac{8}{3}, \frac{8}{3}) \).
  4. Evaluate \( Z \):
    • \( Z(4,0) = 12 \)
    • \( Z(0,4) = 16 \)
    • \( Z(\frac{8}{3}, \frac{8}{3}) = 3(\frac{8}{3}) + 4(\frac{8}{3}) = 8 + 10.67 = 18.67 \)
  5. Maximum profit is 18.67 (KSh 18,667).
Example 3 (Hard) — Cost Minimization:

Problem: Minimise cost \( C = 12x + 10y \) subject to protein constraint \( 5x + 3y \ge 30 \) and fiber constraint \( 2x + 4y \ge 20 \) (where \( x, y \ge 0 \)).

  1. Find intersection of boundary lines: \( 5x + 3y = 30 \) and \( 2x + 4y = 20 \).
  2. Solve simultaneously: multiply 1st by 2 (\( 10x + 6y = 60 \)) and 2nd by 5 (\( 10x + 20y = 100 \)).
  3. Subtracting gives \( 14y = 40 \implies y = 2.86 \), then \( x = 4.29 \).
  4. Feasible region vertices (unbounded above): \( (0, 10) \), \( (4.29, 2.86) \), \( (10, 0) \).
  5. Evaluate cost \( C \):
    • \( C(0,10) = 12(0) + 10(10) = 100 \)
    • \( C(4.29, 2.86) = 12(4.29) + 10(2.86) = 51.48 + 28.60 = 80.08 \approx 80 \)
    • \( C(10,0) = 12(10) + 10(0) = 120 \)
  6. Minimum cost = Ksh 80.

Common Mistakes

Mistake Testing only axis intercepts \( (x,0) \) and \( (0,y) \) and skipping intersection vertices between constraint lines.
Correction The optimal vertex frequently occurs at the intersection of two slanted constraint lines.
Why it feels right Axis intercepts are easier to calculate than solving simultaneous equations.
Mistake Shading the wrong side of a constraint inequality line.
Correction Always test the origin \( (0,0) \). If \( (0,0) \) satisfies \( ax + by \le k \), shade the region containing \( (0,0) \).
Why it feels right Guessing shading directions based on inequality signs without checking test points.

Real World

Agricultural Feed Mixing: Minimizing ingredient costs while meeting minimum nutritional requirements for livestock feeds.
Transport & Logistics: Allocating fleets of trucks and vans to maximize cargo volume delivered within budget and fuel limits.
Manufacturing Optimization: Maximizing profit from factory assembly lines constrained by labor hours and raw material supplies.

Practice

A farmer needs a feed mixture containing at least 30 g protein and 20 g fiber per kg. Ingredient A provides 5 g protein and 2 g fiber at Ksh 12/kg. Ingredient B provides 3 g protein and 4 g fiber at Ksh 10/kg. What is the minimum cost per kg of the optimal mix? (Type only the number, e.g., 80)
Review the concepts above.
A transport firm uses trucks (Ksh 8/km, 20 ton-km capacity) and vans (Ksh 5/km, 10 ton-km capacity). They must cover at least 500 km total distance and transport at least 8000 ton-km. What is the minimum total daily cost in Ksh? (Type only the number, e.g., 3400)
Review the concepts above.
A cafeteria sells sandwiches (Ksh 150 profit) and salads (Ksh 200 profit). Sandwiches take 5 min prep and 2 units cheese; salads take 8 min prep and 3 units cheese. Limits: max 400 prep min, max 150 units cheese, and at least 20 salads. What is the maximum daily profit in Ksh? (Type only the number, e.g., 10750)
Review the concepts above.
A workshop produces tables (Ksh 150 profit, 3 hrs labor, 4 units material) and chairs (Ksh 100 profit, 2 hrs labor, 3 units material). Available: max 120 labor hrs and max 150 material units. What is the maximum profit achievable? (Type only the number, e.g., 5625)
Review the concepts above.
A bakery makes chocolate cakes (KSh 500 profit, 2 eggs, 3 cups flour) and vanilla cakes (KSh 400 profit, 1 egg, 2 cups flour). Available: 100 eggs and 180 cups flour. What is the maximum profit in KSh? (Type only the number, e.g., 36000)
Review the concepts above.
A cafeteria yields Ksh 2 profit per sandwich (1 unit bread, 0.5 unit lettuce) and Ksh 3 per salad (0.2 unit bread, 1 unit lettuce). Stock: 100 bread, 80 lettuce. At least 10 sandwiches must be made. What is max profit rounded to nearest whole Ksh? (Type only the number, e.g., 287)
Review the concepts above.