Linear Programming and Feasible Regions (Graphical Method)
This domain tests the formulation and graphical solution of two-variable linear programming problems: objective function, constraints, feasible region, vertices and the fundamental theorem of linear programming, plus the interpretation of the optimum.
Formulating the problem
- Define x and y with units (quantities of two products, hours on two machines, hectares of two crops).
- Convert each restriction into a linear inequality: "at most" → ≤, "at least" → ≥, "exactly" → =.
- Add the non-negativity constraints x ≥ 0, y ≥ 0 unless the statement excludes them.
- Write the objective z = ax + by and identify whether it is to be maximised or minimised.
Solving graphically
- Draw each boundary line from its intercepts with the axes.
- Choose a test point (usually (0,0)) to decide which half-plane satisfies the inequality, and shade the intersection of all valid half-planes.
- Compute the vertices: intersections of pairs of boundary lines, together with the axis intercepts that belong to the region.
- Evaluate z at each vertex. If the region is bounded and non-empty, the optimum occurs at a vertex; compare values and state the maximum or minimum together with the point.
Special cases
- Empty region: the constraints are incompatible, so there is no solution.
- Unbounded region: check whether z can grow without limit; a minimum may still exist at a vertex.
- Objective parallel to a constraint: the optimum is attained on a whole segment, and both endpoints give the same value.
- If the answer must be a whole number of units and the vertex is fractional, check the nearest integer feasible points.
Worked example
Maximise z = 3x + 2y subject to x + y ≤ 4, x + 2y ≤ 6, x ≥ 0, y ≥ 0. The vertices are (0,0) with z = 0, (4,0) with z = 12, (0,3) with z = 6, and the intersection of x + y = 4 and x + 2y = 6, which is (2,2) with z = 10. The region is bounded, so the maximum is z = 12 at (4,0).
Traps that cost marks
- Shading the wrong half-plane because the inequality sign was not tested with a point.
- Forgetting the axis intercept as a vertex, or including an intersection that lies outside the feasible region.
- Evaluating the objective at only some vertices, or at the origin only.
- Giving the optimal value without the point where it is reached, or vice versa.