Linear Programming Class 12: notes and important questions

Linear Programming — revision notes

1. Terminology and formulation

• Decision variables \(x, y \ge 0\) (non-negativity); objective function \(Z = ax + by\) to be maximised or minimised; constraints are linear inequalities.
• Formulating: (1) define \(x, y\) with units; (2) write \(Z\); (3) one inequality per resource/requirement (“at most” \(\le\), “at least” \(\ge\)); (4) add \(x, y \ge 0\).

2. Feasible region and corner points

• The feasible region is the common region of all constraints; each point is a feasible solution. Boundary points count.
• Test a half-plane with a point not on the line (usually the origin).
• Corner points: intersections of boundary lines that satisfy every constraint — solve the pairs of equations algebraically.
• Empty region: the problem is infeasible (no solution).

3. Corner-point method

• Bounded region: \(Z\) has a maximum and a minimum, each at a corner point. Evaluate \(Z\) at all corners.
• Unbounded region: let \(M\) = largest and \(m\) = smallest corner value. \(M\) is the maximum iff the open half-plane \(ax + by \gt M\) has no point in common with the region; \(m\) is the minimum iff \(ax + by \lt m\) has no common point. Otherwise that optimum does not exist.
• If two adjacent corners give the same optimal value, every point of the edge joining them is optimal (infinitely many solutions).

Worked example 1

Maximise \(Z = 2x + 5y\) with \(x + y \le 5,\ y \le 3,\ x, y \ge 0\): corners \((0, 0), (5, 0), (2, 3), (0, 3)\), \(Z = 0, 10, 19, 15\); maximum \(19\) at \((2, 3)\).

Worked example 2

Minimise \(Z = 3x + y\) with \(x + y \ge 4,\ x, y \ge 0\) (unbounded): corners \((4, 0), (0, 4)\), \(Z = 12, 4\). The half-plane \(3x + y \lt 4\) does not meet the region, so the minimum is \(4\) at \((0, 4)\); there is no maximum.

Worked example 3

If \(Z = px + qy\) has the same maximum at \((1, 4)\) and \((3, 2)\): \(p + 4q = 3p + 2q \Rightarrow p = q\).

Common errors

• Missing a corner (e.g. where a constraint meets an axis) or including an intersection point that violates another constraint.
• Declaring a maximum/minimum on an unbounded region without the half-plane check.
• Shading the wrong side of a line — always test a point.
• Forgetting the non-negativity constraints, or units and the final interpretation in word problems.

Board-exam tips

• The LPP is usually a 5-mark question (or a 3-mark one): a neat, labelled graph with the feasible region shaded, a table of corner points with \(Z\) values, and a concluding sentence each earn marks.
• Only two variables and up to three non-trivial constraints are examined; types of LPP (diet/transportation classification) are not in the syllabus.