Linear Programming
Linear Programming
UPMSP tests formulation and graphical solution of two-variable linear programming problems. An LPP has an objective function to maximize or minimize, linear constraints, and usually non-negativity restrictions x≥0, y≥0. The feasible region is the intersection of all constraint half-planes; the corner-point theorem says a linear objective attains its optimum at a vertex of a bounded feasible region.
Core rules
- Convert each inequality to a boundary line, test a point, and shade the feasible side.
- Identify all corner points, including intercepts and intersections of boundary lines.
- Evaluate the objective at every vertex; the largest value is the maximum, the smallest the minimum.
- If the feasible region is unbounded, check whether the objective can improve without limit.
- Include x=0 or y=0 boundaries when non-negativity applies.
Worked example
Maximize Z=3x+2y subject to x+y≤4, x≤2, x≥0, y≥0. The vertices are (0,0), (2,0), (2,2), and (0,4). Values: Z(0,0)=0, Z(2,0)=6, Z(2,2)=10, Z(0,4)=8. The maximum is 10 at (2,2). The point (2,2) is the intersection of x=2 and x+y=4, so it must be included.
Traps
Shading the wrong side of a constraint; missing an intersection vertex; checking only axes intercepts; ignoring non-negativity; assuming a maximum exists when the region is unbounded; mixing the objective coefficients with constraint coefficients.