Linear programming in two variables
This linear-programming practice chapter develops translation into inequalities, graphical feasible regions, objective evaluation and elementary sensitivity ideas. These are shared mathematical foundations; no particular regional examination format or required question is claimed.
Core rules
- Decision variables with x ≥ 0, y ≥ 0; each limited resource gives a ≤ inequality, each minimum requirement a ≥ inequality.
- The objective z = ax + by is linear, so its level curves are parallel lines and when a nonconstant linear objective has a finite optimum over a full-dimensional polygon, some boundary point attains it.
- Fundamental theorem: if the feasible region is non-empty and bounded, the optimum is attained at a vertex. If it is unbounded, test whether z grows without limit along an open direction.
- To draw a constraint, plot its boundary as an equation and test a point (usually the origin) to choose the half-plane. A vertex is the intersection of two boundary lines that satisfies every constraint.
- Duality: max c^T x with Ax ≤ b, x ≥ 0 has dual min b^T y with A^T y ≥ c, y ≥ 0. When a feasible primal problem has a finite optimum, strong duality gives a dual optimum of the same value. An optimal dual variable can describe a marginal resource value within the applicable sensitivity range.
Worked example
Maximise z = 3x + 2y subject to x + y ≤ 4, x + 2y ≤ 6, x ≥ 0, y ≥ 0.
Boundaries: x + y = 4 cuts the axes at (4,0) and (0,4); x + 2y = 6 cuts them at (6,0) and (0,3). The lines meet where x + y = 4 and x + 2y = 6, that is y = 2, x = 2. Vertices of the region: (0,0), (4,0), (2,2), (0,3). Objective values: 0, 12, 10, 6. The maximum is z = 12 at (4,0). If the objective were z = x + y, the values would be 0, 4, 4, 3, and every point of the edge joining (4,0) and (2,2) would be optimal. This is the tied-edge case.
Traps that cost marks
- Omitting x, y ≥ 0 and losing two edges of the region.
- Checking only the intersection of the two main lines.
- Multiplying an inequality by a negative number without reversing the sign.
- Giving a fractional vertex as the answer when the variables count whole units.
- Declaring a maximum without checking that the region is bounded in that direction.