The Vocabulary of a Linear Programming Problem

A linear programming problem (LPP) optimises a linear function subject to linear constraints:

1. Objective function $Z = ax + by$ — the linear function to be maximised or minimised.
2. Constraints — the linear inequalities the variables must satisfy, including the non-negativity constraints $x \geq 0$, $y \geq 0$.
3. Feasible region — the common region satisfying all constraints; each of its points is a feasible solution, and points outside are infeasible solutions.
4. Optimal solution — a feasible solution where $Z$ attains its maximum or minimum.

The feasible region of an LPP is always a convex polygon region (possibly unbounded, possibly empty) because it is an intersection of half-planes.

The Corner Point Method

Corner Point Theorem: if an optimal value of $Z$ exists, it occurs at a corner point (vertex) of the feasible region — so the whole graphical method is:

1. Draw every constraint line and shade the feasible region.
2. Find all corner points (intersections of boundary lines that satisfy every constraint).
3. Evaluate $Z$ at each corner point in a small table.
4. Read off the largest and smallest values.

Bounded region: both a maximum and a minimum of $Z$ always exist, and step 4 finishes the problem.

Two corners tie: if $Z$ takes the same optimal value at two corner points, then every point of the segment joining them is optimal — the LPP has infinitely many optimal solutions, and the answer must say so.

The Unbounded Region Protocol

When the feasible region is unbounded, the corner table alone is not a proof. After finding the candidate value $M$ at a corner:

1. For a minimum: draw the open half-plane $ax + by < M$. If it shares no point with the feasible region, $M$ is the true minimum; if it does, no minimum exists.
2. For a maximum: same test with $ax + by > M$. On an unbounded region a maximum very often fails to exist — state it explicitly.

Empty feasible region: if the constraints have no common point, the LPP is infeasible and has no solution — writing any number is wrong; the answer is the sentence.

Every mark scheme rewards the same skeleton: correct region, corner table, and (when unbounded) the half-plane sentence. Practise writing all three every single time.

Worked Examples — Bounded Regions

Example 1 — Naming the parts

For the LPP: maximise $Z = 3x + 2y$ subject to $x + 2y \leq 10$, $3x + y \leq 15$, $x, y \geq 0$ — identify the objective function, the constraints and the nature of the region.

Step 1 — read the statement: the objective function is $Z = 3x + 2y$; the structural constraints are $x + 2y \leq 10$ and $3x + y \leq 15$; and $x, y \geq 0$ are the non-negativity constraints.

Answer: four constraints in all, and their intersection is a bounded quadrilateral region — so both a maximum and a minimum of $Z$ are guaranteed to exist.

Example 2 — A complete maximisation

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

Step 1 — corner points: the boundary lines meet the axes and each other at $(0,0)$, $(30, 0)$, $(20, 30)$ and $(0, 50)$ — the lines $x + y = 50$ and $3x + y = 90$ intersect where $2x = 40$, giving $(20, 30)$.

Step 2 — the corner table: $Z(0,0) = 0$, $Z(30,0) = 120$, $Z(20,30) = 110$, $Z(0,50) = 50$.

Answer: maximum $Z = 120$ at $(30, 0)$ — note the optimum is not at the intersection of the two structural constraints; the table decides, not intuition.

Example 3 — Finishing Example 1

Maximise $Z = 3x + 2y$ subject to $x + 2y \leq 10$, $3x + y \leq 15$, $x, y \geq 0$.

Step 1 — corner points: $(0,0)$, $(5, 0)$, $(4, 3)$ and $(0, 5)$ — the structural lines meet where $x + 2y = 10$ and $3x + y = 15$: solving gives $x = 4$, $y = 3$.

Step 2 — corner table: $Z = 0, 15, 18, 10$ respectively.

Answer: maximum $Z = 18$ at $(4, 3)$.

Example 4 — A minimisation

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

Step 1 — feasible region: bounded, with corners $(0, 5)$, $(4, 3)$ and $(0, 6)$ — the lines $x + 2y = 10$ and $3x + 4y = 24$ meet at $(4, 3)$.

Step 2 — corner table: $Z(0,5) = 2500$, $Z(4,3) = 2300$, $Z(0,6) = 3000$.

Answer: minimum $Z = 2300$ at $(4, 3)$ — a mixed system ($\geq$ and $\leq$) still gives a bounded region here; always plot before assuming.

Example 5 — Maximum and minimum together, with a tie

Find the maximum and minimum of $Z = 5x + 10y$ subject to $x + 2y \leq 120$, $x + y \geq 60$, $x - 2y \geq 0$, $x, y \geq 0$.

Step 1 — corner points: $(60, 0)$, $(120, 0)$, $(60, 30)$ and $(40, 20)$.

Step 2 — corner table: $Z = 300$, $600$, $600$ and $400$ respectively.

Answer: minimum $Z = 300$ at $(60, 0)$; maximum $Z = 600$ at every point of the segment joining $(120, 0)$ and $(60, 30)$ — when two corners tie, the whole edge is optimal and the answer must say so.

Example 6 — Feasible is not the same as optimal

For the LPP of Example 2, is $(10, 20)$ a feasible solution? Is it optimal?

Step 1 — test the constraints: $10 + 20 = 30 \leq 50$ and $30 + 20 = 50 \leq 90$, with both coordinates non-negative — feasible.

Step 2 — compare with the optimum: $Z(10, 20) = 60 < 120$.

Answer: feasible, but not optimal — every point of the region is feasible; only the best corner value is optimal.

Worked Examples — Unbounded and Degenerate Cases

Example 7 — Minimum on an unbounded region

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

Step 1 — corner points: the region is unbounded, with corners $(3, 0)$, $\left(\dfrac{3}{2}, \dfrac{1}{2}\right)$ and $(0, 2)$ — the lines meet where $x + 3y = 3$ and $x + y = 2$: subtracting, $2y = 1$.

Step 2 — corner table: $Z = 9$, $7$ and $10$ respectively, so the candidate minimum is $7$.

Step 3 — the half-plane test (compulsory for unbounded regions): the open half-plane $3x + 5y < 7$ has no point in common with the feasible region.

Answer: minimum $Z = 7$ at $\left(\dfrac{3}{2}, \dfrac{1}{2}\right)$ — without Step 3 the answer is incomplete on an unbounded region.

Example 8 — A whole edge of minima, unbounded region

Minimise $Z = x + 2y$ subject to $2x + y \geq 3$, $x + 2y \geq 6$, $x, y \geq 0$.

Step 1 — corner points: $(0, 3)$ and $(6, 0)$, both lying on the line $x + 2y = 6$.

Step 2 — corner table: $Z(0,3) = 6$ and $Z(6,0) = 6$ — a tie.

Step 3 — half-plane test: $x + 2y < 6$ shares no point with the region.

Answer: minimum $Z = 6$ at every point of the segment joining $(0, 3)$ and $(6, 0)$ — the objective line is parallel to a boundary edge, so the whole edge is optimal.

Example 9 — When the maximum does not exist

Maximise $Z = x + y$ subject to $x + y \geq 2$, $x, y \geq 0$.

Step 1 — the region: everything on or above the line $x + y = 2$ in the first quadrant — unbounded.

Step 2 — candidate from corners: $Z = 2$ at both $(2, 0)$ and $(0, 2)$.

Step 3 — half-plane test for a maximum: the open half-plane $x + y > 2$ overlaps the feasible region heavily — points like $(10, 10)$ are feasible with $Z = 20$.

Answer: $Z$ has no maximum — it grows without bound. On unbounded regions, always suspect the maximum.

Example 10 — The infeasible LPP

Maximise $Z = x + y$ subject to $x - y \leq -1$, $-x + y \leq 0$, $x, y \geq 0$.

Step 1 — read the two constraints together: the first says $y \geq x + 1$; the second says $y \leq x$.

Step 2 — look for a common point: no point can satisfy both — the feasible region is empty.

Answer: the LPP is infeasible and has no solution — the full sentence is the answer; producing a number here loses every mark.