Graphical Method & the Feasible Region

MATThe Graphical Method

The graphical method solves a two-variable LPP by drawing all constraint lines, identifying the feasible region (the common shaded area satisfying every inequality), and then optimising the objective over it. The feasible region is the convex set of all points meeting the constraints; the optimum lies at one of its corner points.

ISC requires a neat, labelled graph with the region shaded, corners found exactly, and the objective evaluated at each.

Feasible region as an intersection

S = \{(x,y) : a_i x + b_i y \le c_i \text{ or } \ge c_i\ \forall i,\ \ x \ge 0,\ y \ge 0\}

S

is the set of all points satisfying every constraint simultaneously; being an intersection of half-planes it is convex.

Constraint line by intercepts

a x + b y = c \;\Rightarrow\; \left(\tfrac{c}{a},\,0\right),\ \left(0,\,\tfrac{c}{b}\right)

Plot the boundary line through its

x

- and

y

-intercepts (assuming

a,b\ne 0

), then shade the correct half-plane.

Origin test for a half-plane

a(0)+b(0) \le c \;\Rightarrow\; \text{shade the origin side}

Substitute

(0,0)

; if the inequality holds, the feasible side contains the origin (valid only when the line does not pass through the origin).

Corner Point Theorem

Z^{*} = \text{optimum of } \{ax_i + by_i : (x_i,y_i) \in \text{corners of } S\}

The optimum of a linear

Z

over a bounded convex region occurs at a corner point of

S

Convert each inequality to its boundary equation, plot the line, and use a test point (usually the origin) to decide the shaded side.
The feasible region is the overlap of all shaded half-planes intersected with the first quadrant ( $x,y\ge0$ ).
It is always convex; its corner points are where boundary lines (or the axes) intersect.
Find corners exactly by solving the relevant pairs of boundary equations simultaneously, not by eye.
For a bounded region, evaluate $Z$ at every corner and pick the optimum directly.
For an unbounded region, after finding the best corner apply the open half-plane test ( $ax+by>M$ for max, $ax+by<m$ for min) to confirm existence.
Label axes, lines, the shaded feasible region, and each corner point clearly — ISC awards marks for a correct, labelled graph.
If the feasible region is empty (no common overlap), the LPP has no feasible solution and hence no optimum.

Where the marks go

Shading the wrong half-plane because the line passes through the origin (then a different test point must be chosen).
Estimating corner coordinates from the graph instead of solving the boundary lines algebraically.
Forgetting to restrict the region to the first quadrant with $x\ge0,\ y\ge0$ .
Leaving the feasible region or corner points unlabelled, or not stating whether the optimum is a maximum or minimum.

How the board asks it

Diagram / graphfeasible region as the intersection of half-planes
Draw the feasible region determined by the constraints $2x + y \le 10$ , $x + 3y \le 15$ , $x \ge 0$ , $y \ge 0$ . Use a test point to decide the correct side of each line, then shade and clearly label the feasible region, marking all its corner points.
Numericalcorner points by simultaneous boundary equations
For the feasible region given by $x + 2y \le 8$ , $3x + 2y \le 12$ , $x \ge 0$ , $y \ge 0$ , find the coordinates of all corner points by solving the relevant pairs of boundary lines simultaneously.
Numericalcorner point theorem
Maximise $Z = 4x + 3y$ subject to $x + y \le 4$ , $x + 2y \le 6$ , $x \ge 0$ , $y \ge 0$ , by drawing the feasible region and evaluating $Z$ at each corner point.
Give reasonsunbounded region open half-plane test
Minimise $Z = 3x + 5y$ subject to $x + 3y \ge 3$ , $x + y \ge 2$ , $x \ge 0$ , $y \ge 0$ . State whether the feasible region is bounded or unbounded, and using the open half-plane test justify whether the minimum value of $Z$ actually exists.
Applicationfeasible region from a worded constraint set
A factory makes two products $A$ and $B$ , using $x$ units of $A$ and $y$ units of $B$ . Machine time gives $3x + 2y \le 12$ and labour gives $x + 2y \le 6$ , with $x, y \ge 0$ . Draw the feasible region and mark all its corner points.

Practise this topic

PreviousFormulation of a Linear Programming Problem NextCorner-Point Method — Maximisation

Written for Sublevo. Question text quoted anywhere in these notes is the Council’s and carries its year and paper; the board’s own diagrams are not reproduced.