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

16 PYQs, none HARD — the chapter's opening move. 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

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?

Practise this conceptself-check · 4 quick reps

The same idea in a real exam question:

MHT-CET · 2025 · 23 April Shift I · Q140Moderate

Example 1 · Linear Programming · Feasible Region — Half-Plane Tests, Bounded, Unbounded and Empty

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 ...

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

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?

Practise this conceptself-check · 4 quick reps

The same idea in a real exam question:

MHT-CET · 2023 · 15th May Shift 1 · Q125Moderate

Example 2 · Linear Programming · Feasible Region — Half-Plane Tests, Bounded, Unbounded and Empty

The region represented by the inequations

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

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

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

Practise this conceptself-check · 4 quick reps

The same idea in a real exam question:

MHT-CET · 2024 · 10th May Shift 1 · Q107Moderate

Example 3 · Linear Programming · Feasible Region — Half-Plane Tests, Bounded, Unbounded and Empty

Vertices of feasible region for

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

are

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

Test yourself on Linear Programming

15 past MHT-CET questions from this chapter, timed at 27 minutes and marked the way the exam marks it. You see your score and every answer the moment you finish. Free to start.

Take the Linear Programming chapter test Drill all 16 questions

Related notes

Corner-Point Method — what the vertices are for →