Chapter 12 · Linear Programming

Example 5: Minimise $Z = 3x + 2y$ ⁠: no feasible region

ExamplesNo feasible region · Section 12.2.2

The question

Minimise $Z = 3x + 2y$

subject to the constraints:

\begin{aligned} x + y &\ge 8 &&\ldots(1) \\ 3x + 5y &\le 15 &&\ldots(2) \\ x \ge 0,\ y &\ge 0 &&\ldots(3) \end{aligned}

Exam answer

Draw the lines (graph):

$x + y = 8$ through $(8, 0)$ and $(0, 8)$ ⁠;

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

At $(0, 0)$ ⁠: $0 \ge 8$ is false, so for (1) shade the side of $x + y = 8$ away from the origin; $0 \le 15$ is true, so for (2) shade the side of $3x + 5y = 15$ containing the origin. With $x, y \ge 0$ ⁠, (2) and (3) give the triangle with corners $(0, 0)$ ⁠, $(5, 0)$ ⁠, $(0, 3)$ ⁠.

The two shaded parts have no common point (graph). Indeed, for any point obeying (2) and (3),

\begin{aligned} 3x + 3y &\le 3x + 5y \le 15 \\ \Rightarrow\ x + y &\le 5 < 8, \end{aligned}

so (1) fails at every such point.

$\therefore$ There is no feasible region, hence no feasible solution: $Z$ has no minimum 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 constraints contradict each other: $3x + 5y \le 15$ with $x, y \ge 0$ keeps only a small triangle near the origin, where $x + y$ is at most 5, while $x + y \ge 8$ demands at least 8. No point obeys all the constraints, so there is nothing to minimise over.

Given, to find, and the plan

Given: $Z = 3x + 2y$ and the constraints $x + y \ge 8$ ⁠, $3x + 5y \le 15$ ⁠, $x \ge 0$ ⁠, $y \ge 0$ ⁠.
To find: The minimum of $Z$ ⁠, or show that there is none. The book's solution also asks: is there any feasible region, and why?
Plan: (1) and (2) Draw each line and choose its side. (3) Find the region kept by (2) and (3) and the largest value of $x + y$ on it. (4) Show that no point obeys (1) as well. (5) Conclude.

Basics you need

1Lines and sides

Draw each line from its axis points and test $(0, 0)$ 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

3A linear expression on a triangle

On a bounded region, a linear expression such as $x + y$ is largest at a corner (Theorem 2, Section 12.2.2). Basics: corners

4Adding inequalities

If $a \le b$ and $b \le c$ ⁠, then $a \le c$ ⁠; and adding the same amount to both sides keeps an inequality true (Class XI, Linear Inequalities).

Solution

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

Its axis points are $(8, 0)$ and $(0, 8)$ ⁠. Test $(0, 0)$ in (1): $0 \ge 8$ is false, so (1) keeps the side of the line away from the origin.

"At least 8" fails at the origin, so the kept side is the far one: points such as $(8, 0)$ ⁠, $(4, 5)$ or $(10, 10)$ ⁠.

Basics: one side of a line
Draw the line $3x + 5y = 15$ and choose its side

Put $y = 0$ ⁠: $x = 5$ ⁠. Put $x = 0$ ⁠: $y = 3$ ⁠. The line joins $(5, 0)$ and $(0, 3)$ ⁠. Test $(0, 0)$ in (2): $0 \le 15$ is true, so (2) keeps the origin's side.

" $\le$ " with a positive number on the right keeps the origin's side.

Basics: where a line meets the axes
The region kept by (2) and (3)

In the first quadrant, (2) keeps the triangle with corners $(0, 0)$ ⁠, $(5, 0)$ and $(0, 3)$ ⁠. The largest value of $x + y$ on it is at a corner:

Corner of the triangle $x + y$

$(0, 0)$ $0$

$(5, 0)$ $5$ ← largest

$(0, 3)$ $3$

So every point of the triangle has $x + y \le 5$ ⁠.

The triangle is bounded and $x + y$ is linear, so its largest value on the triangle is at a corner, just as for $Z$ in earlier examples. This table shows how far short of 8 the triangle falls.

Basics: corners
No point obeys all the constraints

Example 5, drawn with equal scales. Gold: the part of the first quadrant with $x + y \ge 8$ ⁠. Violet: the triangle $3x + 5y \le 15$ ⁠, with corners $(0, 0)$ ⁠, $(5, 0)$ ⁠, $(0, 3)$ ⁠. The two shaded parts have no common point.

The graph shows a gap between the violet triangle and the gold side. To prove it for every point: if $x \ge 0$ ⁠, $y \ge 0$ and $3x + 5y \le 15$ ⁠, then, because $2y \ge 0$ ⁠,
$\begin{aligned} 3x + 3y &\le 3x + 5y \le 15, \\ \text{so } x + y &\le 5. \end{aligned}$
But (1) needs $x + y \ge 8$ ⁠, and $5 < 8$ ⁠. So no point satisfies (1), (2) and (3) together.

This answers the book's questions "Is there any feasible region? Why is so?": no, because the constraints (2) and (3) force $x + y \le 5$ ⁠, while (1) forces $x + y \ge 8$ ⁠. The two lines do meet, at $\left(\frac{25}{2}, -\frac92\right)$ ⁠, but that point has $y < 0$ ⁠, outside the first quadrant.

Basics: where the shadings overlap
Conclude

There is no feasible region, and hence no feasible solution. With no feasible point at all, $Z = 3x + 2y$ has no minimum value (and no maximum 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$ ⁠. The book closes with a Remark: whenever a feasible region exists it is convex, and the optimum (when there is one) is at a corner.

Lesson: when the constraints disagree, Example 5 · Basics: convex and bounded regions

Corner of the triangle	$x + y$
$(0, 0)$	$0$
$(5, 0)$	$5$ ← largest
$(0, 3)$	$3$

Result

The constraints have no common point: (2) and (3) give $x + y \le 5$ ⁠, while (1) needs $x + y \ge 8$ ⁠. So

\begin{aligned} &\text{there is no feasible region,} \\ &\text{so no feasible solution,} \end{aligned}

and $Z = 3x + 2y$ has no minimum value. (Textbook answer: the problem is having no feasible region and hence no feasible solution.)

Check it with numbers

Points that obey (1) break (2): $(8, 0)$ gives $3(8) + 0 = 24 > 15$ ⁠; $(0, 8)$ gives $40 > 15$ ⁠; $(4, 4)$ gives $32 > 15$ ✓.

Points that obey (2) and (3) break (1): the corner $(5, 0)$ has $x + y = 5 < 8$ ⁠, and $(2, 1)$ has $3 < 8$ ✓.

A computer check of the 13 whole-number points that obey (2) and (3) found the largest $x + y$ to be 5, at $(5, 0)$ ⁠; none reaches 8 ✓.

Common mistakes

Using the crossing point of the two lines as a corner. $\left(\frac{25}{2}, -\frac92\right)$ has $y < 0$ ⁠, so it breaks (3).
Writing a minimum such as $Z = 0$ at $(0, 0)$ ⁠. The origin breaks (1); a minimum must be at a feasible point.
Shading towards the origin for $x + y \ge 8$ ⁠. The test $0 \ge 8$ is false.
Ending without a conclusion. Say it in words: no feasible region, so no feasible solution and no minimum.

What to take away

Always check that the kept sides overlap before looking for corners.
A one-line combination of the constraints, here $3x + 3y \le 3x + 5y \le 15$ ⁠, proves that a region is empty.
So far: a bounded region gives both optima (Examples 1 to 3), an unbounded one needs the half-plane test (Example 4), and an empty one gives no solution.

Every fact used, and where it comes from

Fact	Used in	Source
A line from its axis points; a test point chooses the side	Steps 1, 2	Class XI, Linear Inequalities (Basics, Basics)
A linear expression on a bounded region is largest at a corner	Step 3	Theorem 2, Section 12.2.2 (Basics)
Feasible region: common region of all the constraints	Step 4	Section 12.2.2 (Basics)
Inequalities can be chained and added	Step 4	Class XI, Linear Inequalities
No feasible region means no feasible solution	Step 5	Example 5, Section 12.2.2 (Lesson)
Remarks: the feasible region is convex; optima occur at corners	Step 5	Remarks after Example 5, Section 12.2.2 (Basics)
All values	Steps, Check	Recomputed with exact fractions in the site's verification script

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 →

Example 5: Minimise Z=3x+2yZ = 3x + 2yZ=3x+2y⁠: no feasible region

Basics you need

Solution

Draw the line x+y=8x + y = 8x+y=8 and choose its side

Draw the line 3x+5y=153x + 5y = 153x+5y=15 and choose its side

The region kept by (2) and (3)

No point obeys all the constraints

Conclude

Every fact used, and where it comes from

Example 5: Minimise $Z = 3x + 2y$ ⁠: no feasible region

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

Draw the line $3x + 5y = 15$ and choose its side