Linear Programming
Linear Programming
This domain tests formulation and graphical solution of two-variable linear programming problems. ASSEB questions usually give constraints, ask for the feasible region, and require the maximum or minimum of a linear objective by the corner-point method.
Core rules
- Decision variables x,y are usually non-negative: x≥0, y≥0.
- Each linear inequality defines a half-plane. The feasible region is the intersection of all half-planes, including non-negativity.
- Corner-point theorem: if an optimum exists on a bounded feasible region, it occurs at a vertex. Evaluate Z=ax+by at every vertex and compare.
- A bounded region has both maximum and minimum; an unbounded region may have no maximum (or no minimum), so check the direction of improvement.
- If the problem requires whole items, integer restrictions must be checked separately; the graphical solution may give a fractional vertex.
Worked example
Maximise Z=3x+2y subject to x+y≤4, x≤2, x≥0, y≥0. The boundary lines are x+y=4 and x=2. Vertices of the feasible region: (0,0), (2,0), (2,2), (0,4). Evaluate: Z(0,0)=0; Z(2,0)=6; Z(2,2)=6+4=10; Z(0,4)=8. The maximum is 10 at (2,2). Check the constraints: 2+2=4 and x=2, so the point is feasible; the value 10 is larger than the other vertex values.
Traps
Shading the wrong side of an inequality is the most common error; test a point such as (0,0) when it is not on the line. Do not ignore x≥0, y≥0. Do not optimise only at the intersection of two constraint lines if that point is outside the feasible region. For an unbounded region, do not assume a corner gives a maximum; state whether the objective is unbounded.