Chapter 12 · Linear Programming

Exercise 12.1 · Q10: Maximise $Z = x + y$ ⁠: no feasible region

Exercise 12.1No feasible region · Section 12.2.2

The question

Solve the following Linear Programming Problems graphically:

Maximise $Z = x + y$ ⁠, subject to $x - y \le -1$ ⁠, $-x + y \le 0$ ⁠, $x, y \ge 0$ ⁠.

Exam answer

Draw the lines (graph):

$x - y = -1$ through $(-1, 0)$ and $(0, 1)$ ⁠;

$-x + y = 0$ through $(0, 0)$ and $(5, 5)$ ⁠.

At $(0, 0)$ ⁠: $0 \le -1$ is false, so shade the side of $x - y = -1$ away from the origin. For $-x + y \le 0$ test $(1, 0)$ ⁠: $-1 \le 0$ is true, so shade the side of $-x + y = 0$ that contains $(1, 0)$ ⁠.

The two lines are parallel, and the two shaded parts have no common point (graph). Indeed, adding the two constraints,

\begin{aligned} (x - y) + (-x + y) &\le -1 + 0 \\ \Rightarrow\ 0 &\le -1, \end{aligned}

which is false. So no point satisfies both constraints.

$\therefore$ There is no feasible region, hence no feasible solution: $Z$ has no maximum value.

Want the reason behind every step, the basics and the checks?

The one idea this problem is built on

Before looking for corners, there must be a region. Here the two constraints contradict each other: $x - y \le -1$ says $y \ge x + 1$ ⁠, so $y$ is more than $x$ ⁠, while $-x + y \le 0$ says $y \le x$ ⁠. No point obeys both, so there is nothing to maximise over.

Given, to find, and the plan

Given: $Z = x + y$ and the constraints $x - y \le -1$ ⁠, $-x + y \le 0$ ⁠, $x \ge 0$ ⁠, $y \ge 0$ ⁠.
To find: The maximum of $Z$ ⁠, or show that there is none.
Plan: (1) and (2) Draw each line and choose its side. (3) Show that the two sides have no common point. (4) Conclude.

Basics you need

1Lines and sides

Draw each line from two points and test a point off the line to choose its side. Basics: where a line meets the axes · Basics: which side

2The feasible region is the overlap

A point is feasible only if it obeys every constraint. If the kept sides have no common point, there is no feasible region. Basics: where the shadings overlap

3Adding inequalities

If $a \le b$ and $c \le d$ ⁠, then $a + c \le b + d$ (Class XI, Linear Inequalities).

Solution

Draw the line $x - y = -1$ and choose its side

Put $y = 0$ ⁠: $x = -1$ ⁠. Put $x = 0$ ⁠: $-y = -1$ ⁠, so $y = 1$ ⁠. So the line joins $(-1, 0)$ and $(0, 1)$ ⁠; it is the line $y = x + 1$ ⁠.

Test $(0, 0)$ in $x - y \le -1$ ⁠: $0 \le -1$ is false, so this constraint keeps the side of the line away from the origin, the side above it: $x - y \le -1$ means $y \ge x + 1$ ⁠.

The $x$ -axis point $(-1, 0)$ lies to the left of the origin, but it still fixes the line. Adding $y + 1$ to both sides of $x - y \le -1$ gives $x + 1 \le y$ ⁠, which shows directly that the kept side is above the line.

Basics: where a line meets the axes · Basics: which side
Draw the line $-x + y = 0$ and choose its side

The line $-x + y = 0$ is $y = x$ ⁠: it passes through $(0, 0)$ and $(5, 5)$ ⁠.

The origin lies on it, so test $(1, 0)$ in $-x + y \le 0$ ⁠: $-1 \le 0$ is true. So this constraint keeps the side of the line that contains $(1, 0)$ ⁠, the side below it: $-x + y \le 0$ means $y \le x$ ⁠.

A test point on the line gives " $0 \le 0$ ", which decides nothing; any point off the line works. Both lines have slope 1 ( $y = x + 1$ and $y = x$ ⁠), so they are parallel and never meet.

Basics: one side of a line
No point obeys both constraints

Exercise 12.1 Q10, drawn with equal scales. Gold: the part of the first quadrant with $x - y \le -1$ ⁠, above the line $y = x + 1$ ⁠. Violet: the part with $-x + y \le 0$ ⁠, below the line $y = x$ ⁠. The lines are parallel, and the two shaded parts have no common point.

The graph shows a gap between the gold and violet parts. To prove it for every point, add the two constraints:
$\begin{aligned} (x - y) + (-x + y) &\le -1 + 0, \\ \text{that is } 0 &\le -1, \end{aligned}$
which is false. So no point $(x, y)$ satisfies both $x - y \le -1$ and $-x + y \le 0$ ⁠, and therefore none satisfies all the constraints.

In words: the first constraint needs $y \ge x + 1$ and the second $y \le x$ ⁠; together they would give $x + 1 \le y \le x$ ⁠, that is $1 \le 0$ ⁠. The gap between the parallel lines $y = x$ and $y = x + 1$ belongs to neither side. The conditions $x, y \ge 0$ are not even needed for this.

Basics: where the shadings overlap
Conclude

There is no feasible region, and hence no feasible solution. With no feasible point at all, $Z = x + y$ has no maximum value (and no minimum either).

An optimal solution must be a feasible point, and there are none, so the Corner Point Method has nothing to work on: no region, no corners, no table of $Z$ ⁠. This is the situation of the book's Example 5.

Lesson: Exercise 12.1, step by step · Lesson: when the constraints disagree, Example 5

Result

Adding the constraints $x - y \le -1$ and $-x + y \le 0$ gives $0 \le -1$ ⁠, which is false, so no point satisfies them both:

\text{there is no feasible region,}

hence no feasible solution, and $Z = x + y$ has no maximum value. (Textbook answer: No feasible region, hence no maximum value of Z.)

Check it with numbers

Points that obey $x - y \le -1$ break $-x + y \le 0$ ⁠: $(0, 1)$ gives $-0 + 1 = 1 > 0$ ⁠; $(2, 5)$ gives $3 > 0$ ✓.

Points that obey $-x + y \le 0$ break $x - y \le -1$ ⁠: $(1, 0)$ gives $1 > -1$ ⁠; $(3, 3)$ gives $0 > -1$ ✓.

A computer check of all 441 whole-number points with $0 \le x, y \le 20$ found none that obeys both constraints ✓.

Common mistakes

Looking for the crossing point of the two lines. They are parallel (both have slope 1), so there is none.
Shading towards the origin for $x - y \le -1$ ⁠. The test $0 \le -1$ is false.
Testing $(0, 0)$ for $-x + y \le 0$ ⁠. It lies on the line $y = x$ ⁠; test a point off it, such as $(1, 0)$ ⁠.
Writing a maximum anyway. With no feasible point, there is no maximum; say so in words.

What to take away

Always check that the kept sides overlap before looking for corners.
Adding constraints (or combining them) can prove in one line that a region is empty.
Exercise 12.1 has now shown every case: bounded (Q7), unbounded with an optimum (Q6), unbounded without one (Q9), and no region at all.

Every fact used, and where it comes from

Fact	Used in	Source
A line from two points; a test point off the line chooses the side	Steps 1, 2	Class XI, Linear Inequalities (Basics, Basics)
Feasible region: common region of all the constraints	Step 3	Section 12.2.2 (Basics)
Inequalities in the same direction can be added	Step 3	Class XI, Linear Inequalities
No feasible region means no feasible solution	Step 4	Example 5, Section 12.2.2 (Lesson)
Answer	Result	NCERT answer key, Exercise 12.1 Q10

Found an error, or want more?

Tell us if something on this page is wrong or unclear, or if you would like a fuller explanation, another method or a new feature. Send feedback on this problem →

Exercise 12.1 · Q10: Maximise Z=x+yZ = x + yZ=x+y⁠: no feasible region

Basics you need

Solution

Draw the line x−y=−1x - y = -1x−y=−1 and choose its side

Draw the line −x+y=0-x + y = 0−x+y=0 and choose its side

No point obeys both constraints

Conclude

Every fact used, and where it comes from

Exercise 12.1 · Q10: Maximise $Z = x + y$ ⁠: no feasible region

Draw the line $x - y = -1$ and choose its side

Draw the line $-x + y = 0$ and choose its side