Linear programming
Objective. Use geometry, duality and simplex reasoning.
- 1. Learn
- 2. Worked example
- 3. Practice
- 4. Feedback
- 5. Continue
Learn: the key idea
Linear programming optimises a linear objective subject to linear inequality constraints, with feasible regions forming polyhedra whose optimum lies at a vertex. Each constraint ax+by≤c defines a half-plane; the intersection of all such half-planes is the feasible region, and because the objective is linear, its maximum or minimum occurs at a corner point, found by evaluating the objective at each vertex. Example: maximise 3x+2y subject to x+y≤4, x,y≥0 gives vertices (0,0),(4,0),(0,4), and the best value 12 occurs at (4,0). Duality links this to a related minimisation problem with the same optimal value.
Worked example
A linear programming problem maximises P = 2x + 3y subject to x + y ≤ 5, x ≥ 0, y ≥ 0. Find the maximum value of P.
- 1Identify vertices of the feasible region: (0,0), (5,0), (0,5)
- 2Evaluate P at (0,0): P = 0
- 3Evaluate P at (5,0): P = 10, and at (0,5): P = 15
- 4Compare values: the maximum is at (0,5)
Answer: 15
Concept mastery
Based on your past attempts at this lesson — the question types to practise again come first.
Complete a practice set to see your concept breakdown here.
Practice
Practice happens on its own screen, one question at a time. Answers stay hidden until you submit yours, and you can stop and pick up at the same question later.
Start practisingCommon mistake. Students search for the optimum by checking interior points or midpoints of edges; because the objective is linear, only vertices of the feasible polygon need to be tested.
Your progress
Tick each step as you finish it. Your exact reading position is saved automatically, so Continue drops you back on the same line.
0 of 5 steps complete
Your place saves automatically as you read.