MHT-CET Maths · Linear Programming

Feasible Region — Half-Plane Tests, Bounded, Unbounded and Empty

Each linear inequality keeps one side of its boundary line; the feasible region is the intersection of those half-planes, and it can be a bounded polygon, an unbounded region, or nothing at all.

All Linear Programming notes MHT-CET Maths strategy

Why this matters

13 PYQs, none HARD — the chapter's opening move and its largest page. Half the stems hand you four figures and ask which one is the solution set; the rest ask whether a region is bounded, unbounded or empty, or for its vertices. Every one is settled by a test point per line, and the empty-region stem has a two-line algebraic proof that beats any sketch.

Concept 1 of 3

The Half-Plane Test: Draw the Line, Test a Point, Keep One Side

Intuition

ax + by \le c

is everything on one side of the line

ax + by = c

. Substitute a point NOT on the line — the origin whenever the line misses it — and if the inequality holds, keep the origin's side; otherwise keep the other side.

Definition

Draw $ax + by = c$ from its intercepts $\left(\dfrac{c}{a}, 0\right)$ and $\left(0, \dfrac{c}{b}\right)$ .
Origin test: for $2x + y \le 10$ , $0 \le 10$ is true, so keep the origin side. For $x + 4y \ge 4$ , $0 \ge 4$ is false, so keep the far side.
A line THROUGH the origin ( $y \le x$ , $2x - y \le 0$ ) needs another test point, e.g. $(1, 0)$ : $0 \le 1$ is true, so $y \le x$ is the side containing $(1, 0)$ , below the line.
$x, y \ge 0$ restricts everything to the first quadrant; $x \le 4$ is the region left of the vertical line, $y \le 2$ the region below the horizontal one.
For $2x + y \le 10$ , $y \le x$ , $y \le 2$ , $x, y \ge 0$ : the region is the polygon with vertices $(0,0)$ , $(5,0)$ , $(4,2)$ , $(2,2)$ — the one graph among four that is bounded above by $y = 2$ and cut by $y = x$ on the left.

Half-plane test

ax + by \le c \text{ keeps the side where the test point satisfies it; the origin unless the line passes through it}

Worked example

Which side of

3x + 2y = 12

does

3x + 2y \ge 12

keep, and which side of

x - y = 0

does

x - y \le 0

keep?

Practice this conceptself-check · 4 quick reps

From the bank · past-year question

Example 1Linear ProgrammingMODERATE

The graph with correct feasible region of L.P.P. for the constraints

2x+y\leqslant 10,y\leqslant x,y\leqslant 2,x,y\geqslant 0

is ...

[Q140 · 23 April Shift I · 2025]

Testing the origin on a line through it

0 \le 0

is true for

y \le x

and tells you nothing. Use

(1, 0)

(0, 1)

, and remember that the distractor figures differ from the right one by exactly this side.

Drill 5 more on the half-plane test: draw the line, test a point, keep one side

Concept 2 of 3

Bounded, Unbounded or Empty: Classify Before You Optimise

Intuition

A region is bounded if it fits inside some circle, unbounded if it runs off to infinity in some direction, and empty if two constraints contradict each other. The empty case is proved by adding inequalities, not by drawing.

Definition

$x, y \ge 0$ , $y \le 6$ , $x + y \le 3$ : the constraint $x + y \le 3$ caps both variables, so the region is the bounded triangle $(0,0)$ , $(3,0)$ , $(0,3)$ — $y \le 6$ never binds.
$-x_1 + x_2 \le 1$ , $-x_1 + 3x_2 \le 9$ , $x_1, x_2 \ge 0$ : nothing caps $x_1$ , so the region is unbounded along the $x_1$ -axis.
$|x - y| \le 1$ , $x, y \ge 0$ : the strip between $y = x - 1$ and $y = x + 1$ in the first quadrant — unbounded (not a polygon, not finite).
Empty (null set): $2x + 3y \le 18$ with $x + y \ge 10$ : from the second, $2x + 3y \ge 2(x + y) \ge 20 > 18$ . No point satisfies both.
A bounded region always has both a maximum and a minimum of any linear objective; an unbounded one may lack one of them.

Empty-region proof

x + y \ge 10 \Rightarrow 2x + 3y \ge 2(x + y) \ge 20 > 18 \ \Rightarrow\ \text{no feasible point}

Worked example

Is the region

x + y \ge 6

x + 2y \le 4

x, y \ge 0

bounded, unbounded or empty?

Practice this conceptself-check · 4 quick reps

From the bank · past-year question

Example 2Linear ProgrammingMODERATE

The region represented by the inequations

2x+3y\leq18, x+y\geq10, x\geq0, y\geq0

[Q125 · 15th May Shift 1 · 2023]

Calling every first-quadrant region bounded

x, y \ge 0

only closes two sides. Unless some constraint caps

x

AND some constraint caps

y

(or one caps

x + y

), the region runs to infinity.

Drill 3 more on bounded, unbounded or empty: classify before you optimise

Concept 3 of 3

Vertices of the Region: Intersect Pairs of Boundaries, Then Check the Rest

Intuition

A corner is where two boundary lines meet — but only if that meeting point satisfies every OTHER constraint. List the candidate intersections, test each, and keep the survivors.

Definition

$x + y \le 4$ , $x \le 2$ , $y \le 1$ , $x + y \ge 1$ , $x, y \ge 0$ : candidates on the axes $(1,0)$ , $(2,0)$ , $(0,1)$ ; $x = 2$ meets $y = 1$ at $(2,1)$ ; $x + y = 4$ never binds (it would need $x + y = 4$ with $x \le 2$ , $y \le 1$ , impossible). Vertices $(1,0)$ , $(2,0)$ , $(2,1)$ , $(0,1)$ .
$y \ge x - 2$ , $y \le x + 1$ , $x \ge 2$ , $y \le 4$ : the strip between two parallel lines, right of $x = 2$ , under $y = 4$ : corners $(2,0)$ , $(2,3)$ , $(3,4)$ , $(6,4)$ .
$4x + 3y \le 60$ , $y \ge 2x$ , $x \ge 3$ : at $x = 3$ , $y$ runs from $6$ to $16$ ; $y = 2x$ meets $4x + 3y = 60$ at $(6, 12)$ . Triangle $(3,6)$ , $(3,16)$ , $(6,12)$ .
An option listing $(0,4)$ or $(4,0)$ for the first example is built from the non-binding constraint; a vertex must satisfy ALL constraints.

Vertex test

\text{corner} = (\text{line}_i \cap \text{line}_j) \text{ that satisfies every other constraint}

Worked example

Find the vertices of

x + 2y \le 8

x \le 4

x, y \ge 0

Practice this conceptself-check · 4 quick reps

From the bank · past-year question

Example 3Linear ProgrammingMODERATE

Vertices of feasible region for

x+y\le4,\;x\le2,\;y\le1,\;x+y\ge1,\;x,y\ge0

are

[Q107 · 10th May Shift 1 · 2024]

Keeping an intersection that a third constraint kills

Two boundary lines meet at a point that lies OUTSIDE the region because another constraint excludes it. Every candidate corner is tested against all the constraints before it counts.

Drill 2 more on vertices of the region: intersect pairs of boundaries, then check the rest

Summary — formulas & gotchas at a glance

A revision cheat-sheet for the formulas and gotchas above. Click any concept name to jump back to its full explanation.

Formulas (3)

The Half-Plane Test: Draw the Line, Test a Point, Keep One Side
Half-plane test
$ax + by \le c \text{ keeps the side where the test point satisfies it; the origin unless the line passes through it}$
Bounded, Unbounded or Empty: Classify Before You Optimise
Empty-region proof
$x + y \ge 10 \Rightarrow 2x + 3y \ge 2(x + y) \ge 20 > 18 \ \Rightarrow\ \text{no feasible point}$
Vertices of the Region: Intersect Pairs of Boundaries, Then Check the Rest
Vertex test
$\text{corner} = (\text{line}_i \cap \text{line}_j) \text{ that satisfies every other constraint}$

Watch out for (3)

Testing the origin on a line through it
→ The Half-Plane Test: Draw the Line, Test a Point, Keep One Side
Calling every first-quadrant region bounded
→ Bounded, Unbounded or Empty: Classify Before You Optimise
Keeping an intersection that a third constraint kills
→ Vertices of the Region: Intersect Pairs of Boundaries, Then Check the Rest

Drill every past-year question on this subtopic

13 questions from the bank — paginated, with cart and Word-export support.

Drill the 13 questions

Drill every past-year question on this subtopic

Related notes