Skip to content
Probability, Statistics & Linear Programming

Linear Programming

Feasible regions, the simplex method and duality — the part of Unit 4 that is not statistics, and the one most often left out of a preparation plan.

5 previous-year questions →every option and the correct answer, freePractice this topic →one question at a time, no clock, check as you go

See where the marks are across every paper →

1. Linear programming, simplex and duality

Read this as a chapter →

Linear programming, simplex and duality free

In plain words

Optimise a linear quantity over a shape with flat faces. Since there is no peak in the middle, the best value sits at a corner, and the dual problem bounds it.

A linear programme optimises a linear objective over a polyhedron, so if an optimum exists it is attained at a vertex — and the dual programme tells you whether one exists at all.

Exam focus: Part C sets these as multi-statement questions about a single programme: whether it is feasible, whether the optimum is attained, whether it is unbounded, and what the dual says. The arithmetic is light; the marks turn on reading the constraints exactly.

Practice

Part B2025 Juneshow ▾
Solve the following linear programming problem: maximize z = x + y subject to 5x + 3y ≤ 30, 2x + 6y ≤ 25, 2x − y ≤ 8, x ≥ 0, y ≥ 0. Then the optimal value of the objective function is
  1. A.45/11
  2. B.74/11
  3. C.85/12✓ Correct
  4. D.25/6

The worked solution and the per-option analysis are in Trap Analysis.

Part B2025 Decembershow ▾
Consider the following linear programming problem: Maximize 3x1+4x23x_{1} + 4x_{2} subject to 3x1+2x2≤12,3x1+5x2≤15,2x1−x2≥0,x2≤23x_{1} + 2x_{2} \le 12, 3x_{1} + 5x_{2} \le 15, 2x_{1} - x_{2} \ge 0, x_{2} \le 2, and x1,x2≥0x_{1}, x_{2} \ge 0. Which of the following values is the optimum value of the objective function in the feasible region?
  1. A.11
  2. B.13
  3. C.14✓ Correct
  4. D.15

The worked solution and the per-option analysis are in Trap Analysis.

Part C2024 Decembershow ▾
Consider maximizing the objective function P=x1+x2P = x_{1} + x_{2} subject to x1+x2+2x3≤5,2x1−3x3≥1,x2+x3≤0,x1≥0,x2≥0,x3≥0x_{1} + x_{2} + 2x_{3} \le 5, 2x_{1} - 3x_{3} \ge 1, x_{2} + x_{3} \le 0, x_{1} \ge 0, x_{2} \ge 0, x_{3} \ge 0. Then, which of the following statements are true?
  1. A.The optimal solution is 4.
  2. B.An optimal point is (4, 1, 0).
  3. C.The optimal solution is 6.
  4. D.(1/2, 0, 0) is a corner point.✓ Correct

The worked solution and the per-option analysis are in Trap Analysis.

Part C2024 Juneshow ▾
Consider the linear programming problem: max{x1+x2+x3x_{1} + x_{2} + x_{3}} subject to constraints x1+x2−x3≤1,x1+x3≤2,0≤x1≤1/2,x2≥0x_{1} + x_{2} - x_{3} \le 1, x_{1} + x_{3} \le 2, 0 \le x_{1} \le 1/2, x_{2} \ge 0, and 0≤x3≤10 \le x_{3} \le 1. Which of the following statements are true?
  1. A.The optimum value is 3✓ Correct
  2. B.The optimum value is 3/2
  3. C.(0, 2, 1) is an extreme point of the feasible region✓ Correct
  4. D.(1/2, 0, 1) is the optimal solution

The worked solution and the per-option analysis are in Trap Analysis.

Part C2024 Decembershow ▾
Consider maximizing the objective function P=x1+2x2+3x3P = x_{1} + 2x_{2} + 3x_{3} subject to x1+x2≤5,x2+x3≤2,x1+x2+x3≤6,x1≥0,x2≥0,x3≥0x_{1} + x_{2} \le 5, x_{2} + x_{3} \le 2, x_{1} + x_{2} + x_{3} \le 6, x_{1} \ge 0, x_{2} \ge 0, x_{3} \ge 0. Then, which of the following statements are true?
  1. A.(5, 0, 1) is a corner point.✓ Correct
  2. B.(4, 1, 1) is an optimal point.
  3. C.The optimal solution is 9.
  4. D.The optimal solution is 10.✓ Correct

The worked solution and the per-option analysis are in Trap Analysis.

Part Cshow ▾
Consider the LP: maximize 3x + 2y subject to x + y ≤ 4, x + 3y ≤ 6, x, y ≥ 0. Which of the following are true?
  1. A.The optimal solution is x = 4, y = 0, with optimal value 12.✓ Correct
  2. B.The feasible region has exactly 4 vertices: (0,0), (4,0), (3,1), (0,2).✓ Correct
  3. C.The constraint x + 3y ≤ 6 is not binding at the optimal solution.✓ Correct
  4. D.Increasing the coefficient of y in the objective from 2 to 5 would keep (4, 0) as the optimal solution.

Solution

Evaluating 3x+2y at every vertex — (0,0)→0, (4,0)→12, (3,1)→11, (0,2)→4 — the maximum is 12 at (4,0), where x+3y = 4 < 6 is slack, giving (1)–(3). (4) is false: with objective 3x+5y the same vertices give 0, 12, 14, 10 — now (3,1) wins with value 14, so (4,0) is no longer optimal. An LP's optimal vertex depends on the objective, not just the feasible region.

Save for spaced revision (free account)
Part Cshow ▾
Consider a standard-form LP: minimize cᵀx subject to Ax = b, x ≥ 0. Which of the following are true?
  1. A.If the LP is feasible and bounded, it has an optimal solution at a vertex (basic feasible solution).✓ Correct
  2. B.The dual of this LP is a maximization LP with dual variables unrestricted in sign, since the primal constraints are equalities.✓ Correct
  3. C.By strong duality, if both primal and dual are feasible, their optimal objective values are equal.✓ Correct
  4. D.If the primal LP is infeasible, then the dual LP must be unbounded.

Solution

(1) is the fundamental theorem of linear programming. (2) is the standard duality correspondence — equality constraints give unrestricted dual variables. (3) is strong duality. (4) is false: primal infeasibility only forces the dual to be either infeasible or unbounded, not necessarily unbounded — both primal and dual can be infeasible simultaneously.

Save for spaced revision (free account)