Graphical Method and the Corner Point Theorem

The Feasible Region

Graph every constraint as a half-plane (the line, plus the side that satisfies the inequality). The feasible region (or solution region) is the region common to all the half-planes, non-negative restrictions included. Points inside or on the boundary are feasible solutions; points outside are infeasible solutions, and the outside itself is the infeasible region.

An optimal (feasible) solution is any feasible point where the objective function attains its optimal (maximum or minimum) value.

The feasible region has infinitely many points — so testing them all is impossible. Two theorems rescue the situation:

Theorem 1: if the objective function $Z = ax + by$ has an optimal value over the feasible region $R$, that optimal value occurs at a corner point (vertex) of $R$.

Theorem 2: if $R$ is bounded, then $Z$ has both a maximum and a minimum on $R$, each at a corner point.

(A corner point is a point of the region where two boundary lines intersect. A region is bounded if it can be enclosed inside some circle; otherwise it is unbounded — it extends indefinitely.)

Key Point: the theorems shrink an infinite search to a finite checklist — only the corners matter. The whole graphical method is bookkeeping around this one fact. For an unbounded region an optimum may not exist at all (the remark after Theorem 2), which is where the extra test below comes in.

The Corner Point Method

1. Draw the feasible region and find every corner point — by inspection or by solving the two intersecting boundary-line equations.
2. Evaluate $Z$ at each corner. Let $M$ be the largest of these values and $m$ the smallest.
3. Bounded region: $M$ is the maximum and $m$ the minimum. Done.
4. Unbounded region — run the half-plane test:

• $M$ is the maximum only if the open half-plane $ax + by > M$ has no point in common with the feasible region. Otherwise $Z$ has no maximum.
• $m$ is the minimum only if the open half-plane $ax + by < m$ has no point in common with the feasible region. Otherwise $Z$ has no minimum.

Two special situations

1. Multiple optimal solutions: if two corner points give the same optimal value, then every point of the segment joining them is also optimal — the objective line is parallel to that edge of the region. Board questions phrase this as "show that the minimum occurs at more than two points."
2. No feasible region: if the constraints contradict each other, no point satisfies them all — the problem has no feasible solution, hence no optimum of any kind.

General features worth quoting in answers

1. The feasible region of an LPP is always a convex region.
2. Optima occur at corners; ties extend along whole edges.

Key Point (board presentation): always tabulate — corner point in one column, $Z$-value in the other, arrow at the optimum. For unbounded regions, write the half-plane test explicitly; skipping it turns a full-marks answer into a partial one, because the smallest table entry is not automatically the minimum.

Solved Examples

Example 1: A bounded maximisation

Maximise $Z = 4x + y$ subject to $x + y \leq 50$, $3x + y \leq 90$, $x, y \geq 0$.

Solution:

1. Region: bounded, with corners $O(0,0)$, $A(30, 0)$, $B(20, 30)$, $C(0, 50)$ — $B$ from solving $x + y = 50$ with $3x + y = 90$.
2. Evaluate:

Answer: maximum $Z = 120$ at $(30, 0)$.

Example 2: A bounded minimisation

Minimise $Z = 200x + 500y$ subject to $x + 2y \geq 10$, $3x + 4y \leq 24$, $x, y \geq 0$.

Solution:

1. Region: bounded triangle with corners $(0, 5)$, $(4, 3)$, $(0, 6)$ — $(4, 3)$ from solving $x + 2y = 10$ with $3x + 4y = 24$.
2. Evaluate: $Z(0,5) = 2500$; $Z(4,3) = 800 + 1500 = 2300$; $Z(0,6) = 3000$.

Answer: minimum $Z = 2300$ at $(4, 3)$ — a mixed-direction constraint pair can still enclose a bounded region.

Example 3: Multiple optimal solutions

Minimise and maximise $Z = 3x + 9y$ subject to $x + 3y \leq 60$, $x + y \geq 10$, $x \leq y$, $x, y \geq 0$.

Solution:

1. Corners: $A(0, 10)$, $B(5, 5)$, $C(15, 15)$, $D(0, 20)$.
2. Evaluate: $Z_A = 90$, $Z_B = 60$ (minimum), $Z_C = 180$, $Z_D = 180$.
3. The tie: the maximum $180$ occurs at both $C$ and $D$ — the objective line $3x + 9y = 180$ is parallel to edge $CD$ (both have slope $-\dfrac{1}{3}$).

Answer: minimum $60$ at $(5, 5)$; maximum $180$ at every point of the segment joining $(15, 15)$ and $(0, 20)$ — infinitely many optimal solutions.

Example 4: Unbounded region, and no minimum

Determine graphically the minimum of $Z = -50x + 20y$ subject to $2x - y \geq -5$, $3x + y \geq 3$, $2x - 3y \leq 12$, $x, y \geq 0$.

Solution:

1. Corners of the (unbounded) region: $(0, 5)$, $(0, 3)$, $(1, 0)$, $(6, 0)$; values $100, 60, -50, -300$ — smallest is $m = -300$.
2. Half-plane test (mandatory here): graph $-50x + 20y < -300$, i.e. $-5x + 2y < -30$. This open half-plane does share points with the feasible region (far out along the $x$-direction).
3. Conclude: $Z$ takes values below $-300$ inside the region.

Answer: $Z$ has no minimum — the table's smallest entry lied, and only the test exposed it. (The same test with $-50x + 20y > 100$ shows there is no maximum either.)

Example 5: No feasible region at all

Minimise $Z = 3x + 2y$ subject to $x + y \geq 8$, $3x + 5y \leq 15$, $x, y \geq 0$.

Solution:

1. Graph both constraints: $x + y \geq 8$ demands points on or above a line through $(8, 0)$ and $(0, 8)$; $3x + 5y \leq 15$ demands points on or below a line through $(5, 0)$ and $(0, 3)$.
2. No overlap: the first region lies entirely beyond the second in the first quadrant.

Answer: there is no feasible region, hence no feasible solution and no minimum — contradictory constraints end the problem before any table is built.