Systems of linear inequalities and feasible regions

A system of linear inequalities is a collection of inequalities that must all be satisfied simultaneously. The solution set is the intersection of the individual solution regions , a polygon (possibly unbounded) in the plane called the feasible region.

How to solve a system

Graph each inequality as a half-plane.
The feasible region is the intersection , the set of points satisfying every inequality.
The corners (vertices) of the feasible region are intersections of pairs of boundary lines.
Check whether the region is bounded or unbounded.

Vertices and the bounded case

If the feasible region is bounded, it is a convex polygon. Its vertices are critical for linear programming: the maximum and minimum of any linear function $f(x, y) = px + qy$ over the region are attained at a vertex. (You will prove this in Class XII.)

Worked examples

Example 1. Solve graphically: $\{x + y \le 4, x - y \ge 0, x \ge 0, y \ge 0\}$ .

Each inequality is a half-plane:

$x + y \le 4$ : below the line through $(4, 0), (0, 4)$ .
$x - y \ge 0$ : i.e. $y \le x$ , below the line $y = x$ .
$x \ge 0$ : right of $y$ -axis.
$y \ge 0$ : above $x$ -axis.

Intersection: a triangle with vertices $(0, 0), (4, 0), (2, 2)$ .

Example 2. Solve graphically: $\{2x + y \ge 4, x + y \le 3, 2x + 5y \le 10, x \ge 0, y \ge 0\}$ .

Boundaries:

$2x + y = 4$ : through $(2, 0)$ and $(0, 4)$ .
$x + y = 3$ : through $(3, 0)$ and $(0, 3)$ .
$2x + 5y = 10$ : through $(5, 0)$ and $(0, 2)$ .

The feasible region is bounded by the upper sides of the first inequality and the lower sides of the second and third, with $x, y \ge 0$ .

Compute vertices by pairwise intersection:

$2x + y = 4$ and $x + y = 3$ : subtract, $x = 1$ , $y = 2$ , point $(1, 2)$ .
$2x + y = 4$ and $y = 0$ : $x = 2$ , point $(2, 0)$ .
$x + y = 3$ and $y = 0$ : point $(3, 0)$ (check $2x + 5y \le 10 \Rightarrow 6 \le 10$ ✓).
$x + y = 3$ and $2x + 5y = 10$ : subtract twice first from second: $3y = 4$ , $y = 4/3$ , $x = 5/3$ . Check $2x + y = 10/3 + 4/3 = 14/3 \ge 4$ ✓.
$2x + 5y = 10$ and $y = 0$ : $x = 5$ . But check $x + y \le 3$ : fails. So $(5, 0)$ is not a vertex.

Feasible vertices: $(2, 0), (3, 0), (5/3, 4/3), (1, 2)$ . The region is a quadrilateral.

Example 3. A manufacturer makes two products with profit $\\₹40$ on each $A$ and $\\₹50$ on each $B$ . Each $A$ takes $3$ machine-hours, each $B$ takes $2$ , and the factory has $120$ machine-hours per day. Labour: each $A$ takes $1$ hour, each $B$ takes $2$ , and there are $80$ labour hours. How many of each maximise profit?

Constraints (with $x, y$ units of $A, B$ ):

$3x + 2y \le 120$ (machine)
$x + 2y \le 80$ (labour)
$x, y \ge 0$

Find vertices:

$(0, 0)$ .
$(40, 0)$ from $3x = 120$ with $y = 0$ (check $x + 2y = 40 \le 80$ ✓).
$(0, 40)$ from $2y = 80$ with $x = 0$ (check $3x + 2y = 80 \le 120$ ✓).
Intersection of $3x + 2y = 120$ and $x + 2y = 80$ : subtract, $2x = 40$ , $x = 20$ , $y = 30$ . Point $(20, 30)$ .

Profit $f = 40x + 50y$ :

At $(0, 0)$ : $0$ .
At $(40, 0)$ : $1600$ .
At $(0, 40)$ : $2000$ .
At $(20, 30)$ : $800 + 1500 = 2300$ .

Max profit $\\₹2300$ at $(20, 30)$ .

Example 4. Sketch the feasible region of $\{x + y \le 10, x + y \ge 4, x \le 8, y \le 6, x, y \ge 0\}$ .

The region is bounded by the strips $4 \le x + y \le 10$ and $0 \le x \le 8$ , $0 \le y \le 6$ .

Vertices: $(4, 0), (8, 0), (8, 2), (4, 6), (0, 6), (0, 4)$ .

Example 5 (harder). Find the feasible region of $\{x + y \ge 5, x \le 4, y \le 6, x, y \ge 0\}$ . Is it bounded?

$x + y \ge 5$ : above the line $x + y = 5$ .
$x \le 4$ : left of $x = 4$ .
$y \le 6$ : below $y = 6$ .
$x, y \ge 0$ .

Vertices:

$(4, 1)$ : $x + y = 5$ and $x = 4$ ( $y = 1$ ).
$(4, 6)$ : $x = 4$ and $y = 6$ .
$(0, 6)$ : $x = 0$ and $y = 6$ .
$(0, 5)$ : $x = 0$ and $x + y = 5$ ( $y = 5$ ).

Closed polygon: quadrilateral. Bounded.

Try it yourself

Graph $\{x + y \le 6, x - y \ge -2, x \ge 0, y \ge 0\}$ .
Find the feasible region of $\{2x + y \le 6, x + 3y \le 9, x, y \ge 0\}$ and its vertices.
Graph $\{|x| \le 2, |y| \le 3\}$ .
Find the maximum of $z = 3x + 4y$ subject to $\{x + y \le 4, x \ge 0, y \ge 0\}$ .
Find the minimum of $z = 2x + y$ subject to $\{x + y \ge 6, 2x + y \ge 8, x, y \ge 0\}$ .
A diet must contain at least $40$ units of vitamin A and $50$ units of vitamin B. Food $X$ has $4A + 2B$ per gram; food $Y$ has $2A + 5B$ . Cost: $\\₹5/g$ for $X$ , $\\₹4/g$ for $Y$ . Set up the inequalities.
Graph $\{x + y \ge 3, x - y \le 1\}$ and decide if bounded.
Find all vertices of $\{x + 2y \le 10, 3x + y \le 9, x, y \ge 0\}$ .
A shopkeeper sells two types of sweets. He has at most $\\₹2400$ to invest. The first costs $\\₹30$ /kg and the second $\\₹40$ /kg. He has storage for at most $80$ kg. Set up the inequalities.
Graph $\{x + y \le 10, x \ge 0, y \ge 2\}$ .
Find feasible region of $\{2x + y \ge 4, x + y \ge 3, x \ge 0, y \ge 0\}$ . Is it bounded?
A farmer plants two crops. Crop $A$ needs $1$ hectare and $5$ man-days; crop $B$ needs $1$ hectare and $3$ man-days. He has $10$ hectares and $30$ man-days. Profit per hectare: $\\₹40000$ for $A$ , $\\₹30000$ for $B$ . Maximise profit.

Pitfalls / Tricks

Always check the corner points. The optimum of a linear function on a polygon is at a vertex.
Decide bounded vs unbounded before searching for extrema. Unbounded regions may give "no max" or "no min".
A single inequality gives a half-plane (unbounded). Multiple inequalities can carve a bounded region.
Insight. Linear programming is just "find the best corner". The whole subject in Class XII reduces to (a) graph the feasible region, (b) evaluate the objective at each vertex, (c) pick the best.