Linear programming in two variables
Linear programming in two variables is a certain exam question: translate a word problem into inequalities, draw the feasible region, optimise the objective at the vertices, and answer the duality or sensitivity part.
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 the optimum lies on the boundary of the region.
- 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. Primal and dual optimal values coincide, and each dual variable is the shadow price of its constraint.
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 - the tie case the exam likes.
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.