International Baccalaureate · MYP 5 Extended

Inequalities and Linear Programming

⌚ ~162 min ▢ 18 blocks ✓ 74 exercises ➣ Prerequisites : Linear Equations, Inequalities and Formulae, Coordinate Geometry, Simultaneous Equations, Quadratic Equations, Functions, Linear Equations, Inequalities and Formulae

I Non-Linear Inequalities

I.1 Quadratic Inequalities

A quadratic inequality is an inequality that can be written in the form $ax^2+bx+c > 0$ (or $<, \leq, \geq$), with $a \neq 0$. Solving such an inequality involves finding the set of all $x$-values for which the statement is true. The key is to first find the roots of the corresponding equation, as these are the boundary points where the expression can change its sign.

Report an error

Proposition — Sign of an Affine Expression

Let $a$ and $b$ be real numbers with $a \neq 0$. The expression $ax + b$ vanishes at $x_0 = -\dfrac{b}{a}$; it has the sign of $a$ for $x \gt -\dfrac{b}{a}$, and the opposite sign for $x \lt -\dfrac{b}{a}$.

Proof

We solve $ax + b \gt 0$, that is $ax \gt -b$.

If $a \gt 0$, dividing by $a$ keeps the direction: $x \gt -\dfrac{b}{a}$. So $ax+b$ is strictly positive exactly for $x \gt -\dfrac{b}{a}$ — the sign of $a$.
If $a \lt 0$, dividing by $a$ reverses the direction: $x \lt -\dfrac{b}{a}$. So $ax+b$ is strictly positive exactly for $x \lt -\dfrac{b}{a}$ — again on one side of $x_0$, with the sign of $a$ on the other side.

In both cases $ax + b = 0$ exactly when $x = -\dfrac{b}{a}$.

Method — Constructing a Sign Table

To create a sign table for a factored expression:

Find the critical values: Find the values of $x$ that make each factor equal to zero. These are the points where the expression can change sign.
Create the table: Write the critical values in increasing order in the top row of the table. List each factor in a separate row on the left, with the full expression in the last row.
Determine the sign of each factor in the intervals created by the critical values. A linear factor $(x-a)$ is negative for $xa$, and equal to $0$ when $x=a$. For a general affine factor $ax+b$, use the proposition above: it has the sign of $a$ after its zero $-\frac{b}{a}$, the opposite sign before.
Determine the sign of the full expression in each interval by multiplying the signs of the factors in that column.

Proposition — Sign of a Quadratic Trinomial

Let $f(x) = ax^2 + bx + c$ with $a \neq 0$ and $\Delta = b^2 - 4ac$.

If $\Delta > 0$, with roots $x_1 < x_2$: $f(x)$ has the sign of $a$ outside the roots (for $x < x_1$ or $x > x_2$) and the opposite sign between the roots (for $x_1 < x < x_2$); $f(x_1) = f(x_2) = 0$.
If $\Delta = 0$, with double root $x_0$: $f(x)$ has the sign of $a$ for all $x \neq x_0$, and $f(x_0) = 0$.
If $\Delta < 0$: $f(x)$ has the sign of $a$ for all real $x$.

Proof

If $\Delta > 0$, the factored form gives $f(x) = a(x - x_1)(x - x_2)$. The factor $x - x_1$ is negative for $x < x_1$ and positive for $x > x_1$; likewise for $x - x_2$. A sign table of the product shows that $(x - x_1)(x - x_2)$ is positive outside $[x_1, x_2]$ and negative inside $(x_1, x_2)$; multiplying by $a$ gives the sign of $f(x)$.
If $\Delta = 0$, $f(x) = a(x - x_0)^2$ and $(x - x_0)^2 > 0$ for $x \neq x_0$.
If $\Delta < 0$, the vertex form $f(x) = a\left[\left(x + \dfrac{b}{2a}\right)^2 - \dfrac{\Delta}{4a^2}\right]$ has a strictly positive bracket for every $x$, so $f(x)$ has the sign of $a$.

Reading the sign on the parabola

The sign table matches the shape of the curve: a parabola with $a > 0$ is above the $x$-axis except between its two $x$-intercepts (if any), and a parabola with $a < 0$ is below the $x$-axis except between them. When $\Delta = 0$ the parabola only touches the $x$-axis at its vertex, and when $\Delta < 0$ it never meets the $x$-axis and stays entirely on one side.

Report an error

Example

Give the sign table of $f(x) = 2x^2 - 3x - 5$ and of $g(x) = -x^2 + 4x - 5$.

Answer

$f$: $a = 2 > 0$, $\Delta = 9 + 40 = 49 > 0$, $\sqrt{\Delta} = 7$, roots $x_1 = \dfrac{3 - 7}{4} = -1$ and $x_2 = \dfrac{3 + 7}{4} = \dfrac52$. $f(x)$ is positive outside the roots and negative between them.
$g$: $a = -1 < 0$, $\Delta = 16 - 20 = -4 < 0$: no root, $g(x)$ has the sign of $a$, so $g(x) < 0$ for every real $x$.

Method — Solving a Quadratic Inequality

To solve a quadratic inequality such as $ax^2+bx+c \ge 0$ when $\Delta> 0$:

Find the roots of the corresponding equation $ax^2+bx+c = 0$. Let the roots be $x_1$ and $x_2$. These are the “critical values” where the expression changes sign.
Construct a sign table with the roots placed in increasing order on the number line.
Determine the sign pattern. Instead of testing each factor, we can use the properties of the parabola $y=ax^2+bx+c$:
- If $a>0$, the parabola opens upwards , so the expression is positive outside the roots and negative between them.
- If $a<0$, the parabola opens downwards , so the expression is negative outside the roots and positive between them.
State the solution set by choosing the interval(s) that satisfy the inequality.

If $\Delta = 0$ or $\Delta < 0$, there are no two roots to split the number line: $ax^2+bx+c$ keeps the sign of $a$ for every $x$ (except at the double root, where it is $0$), and the solution set is read directly.

Example

Solve the inequality $x^2 - x - 6 < 0$.

Answer

Find the roots: First, we solve the corresponding equation $x^2 - x - 6 = 0$. By factorising, we get $(x-3)(x+2) = 0$. The roots are $x=3$ and $x=-2$.
Construct the sign table: The critical values are $-2$ and $3$. The quadratic expression is $x^2 - x - 6$. Since the leading coefficient is $a=1$ (positive), the parabola opens upwards. This means the expression is positive outside the roots and negative between them.
State the solution: The inequality is $x^2 - x - 6 < 0$, so we are looking for the interval where the expression is negative. According to the sign table, this is the interval between $-2$ and $3$. Since the inequality is strict ($<$), the endpoints are not included.

The solution is $-2 < x < 3$.

Method — Solving Graphically

On the given lines:

Locate their intersection point (when the two lines intersect): its $x$-coordinate is the boundary.
Read for which $x$ the line of the left side is below the other one (for $<$ or $\leq$) or above it (for $>$ or $\geq$); for the non-strict signs $\leq$ and $\geq$, the boundary itself is also a solution.
Conclude, and check one value by calculation.

Example

For which values of $k$ does the parabola $y = x^2 + kx + 4$ never meet the $x$-axis?

Answer

The parabola never meets the $x$-axis exactly when the equation $x^2 + kx + 4 = 0$ has no real root, that is when its discriminant is negative (Proposition “Nature of Roots”). Here $a = 1$, $b = k$ and $c = 4$: $$\begin{aligned}[t] \Delta &= k^2 - 4 \times 1 \times 4 = k^2 - 16 \\ &= (k - 4)(k + 4). && \text{(difference of two squares)} \end{aligned}$$ The condition is $(k - 4)(k + 4) < 0$, an inequality whose unknown is $k$. The sign table of the product:

The product is negative exactly for $-4 < k < 4$: the parabola never meets the $x$-axis when $\boldsymbol{-4 < k < 4}$, that is for $k$ in $(-4, 4)$.
Check: for $k = 0$, $y = x^2 + 4 \geq 4 > 0$; for $k = 4$, $y = x^2 + 4x + 4 = (x + 2)^2$ touches the $x$-axis at $x = -2$, so $4$ is excluded.

Skills to practice

Determining the Sign of a Quadratic Trinomial
Solving Quadratic Inequalities
Solving Inequalities by Graphing
Solving Parameter Problems with the Discriminant

I.2 The Sign of a Quotient

For signs, a quotient behaves exactly like a product: $\frac{A}{B}$ is positive when $A$ and $B$ have the same sign, negative when they have opposite signs. There is one new feature: the values that make the denominator zero are forbidden values — the quotient is not defined there, so they can never be solutions, whatever the inequality symbol.

Report an error

Method — Sign Table for a Quotient

Build the table as for a product, with two extra rules:

In the last row, mark each zero of the denominator with a double bar: the quotient is undefined there.
When concluding, a double-bar value is excluded from the solution set even for $\le$ or $\ge$; a zero of the numerator is included for $\le$ or $\ge$ (provided the denominator is not zero there), excluded for $<$ or $>$.

Example

Solve the inequality $\dfrac{x+1}{x-2} \ge 0$.

Critical values: $x + 1 = 0$ gives $x = -1$ (zero of the numerator); $x - 2 = 0$ gives $x = 2$ (forbidden value).
Sign table:
Conclusion: the quotient is positive or zero for $x \le -1$ or $x > 2$. The value $-1$ is included ($\ge$, zero of the numerator); the value $2$ is excluded (forbidden value), despite the $\ge$. In interval notation: $x \in (-\infty,-1] \cup (2,+\infty)$.

Skills to practice

Solving Quotient Inequalities

I.3 The Squared Factor

Proposition — A Square Never Changes Sign

For every number $a$, the factor $(x-a)^2$ is positive or zero: it is zero at $x = a$ and positive everywhere else. In a sign table its row reads $+, 0, +$ — so the full expression does not change sign at $x = a$ (provided no other factor vanishes there): it only touches zero there.

Example

Solve $(x-3)^2(x+1) \ge 0$, then $(x-3)^2(x+1) > 0$.

For $\ge 0$: the product is positive or zero from $-1$ onward, so $x \in [-1,+\infty)$. For $> 0$: the two zeros must now be removed — $x \in (-1,3) \cup (3,+\infty)$. The value $3$ is the trap: the expression touches zero there without changing sign, so a strict inequality excludes it from the middle of an otherwise solid interval.

Skills to practice

Choosing the Solution Set
Solving Inequalities with a Squared Factor

II Regions in the Plane

II.1 Inequalities in Two Variables

Discover

At a stall, a sandwich costs $\dollar 3$ and a bottle of juice costs $\dollar 2$. Lina has $\dollar 12$ to spend. She buys $x$ sandwiches and $y$ bottles of juice.

Can she buy $2$ sandwiches and $3$ bottles? $4$ sandwiches and $1$ bottle?
Write the condition on $x$ and $y$ as an inequality.
Place on a grid every pair of whole numbers $(x, y)$ that she can pay for. Where are these points compared with the line with equation $3x + 2y = 12$?

Answer

$2$ sandwiches and $3$ bottles cost $3 \times 2 + 2 \times 3 = 12$ dollars: exactly her money, so yes. $4$ sandwiches and $1$ bottle cost $3 \times 4 + 2 \times 1 = 14$ dollars, more than $12$: no.
The cost $3x + 2y$ must be at most $12$: $$3x + 2y \leq 12,$$ with $x$ and $y$ whole numbers, $x \geq 0$ and $y \geq 0$.
There are $19$ such pairs. All the points lie on the line $3x + 2y = 12$ (where she spends exactly $\dollar 12$) or below it, between the line and the axes. Lina can only buy whole numbers of items, so her purchases are these $19$ points; the inequality $3x + 2y \leq 12$ itself is also satisfied by pairs that are not whole numbers, such as $(1.5, 2)$. Every point below the line satisfies the inequality, and every point above it breaks it: the next Proposition proves it.

Definition — Linear Inequality in Two Variables

A linear inequality in two variables $x$ and $y$ is an inequality that can be written in one of the forms $$ax + by < c, \qquad ax + by > c, \qquad ax + by \leq c, \qquad ax + by \geq c,$$ where $a$, $b$ and $c$ are numbers, and $a$ and $b$ are not both zero.
A solution of the inequality is a pair of numbers $(x, y)$ that makes it true. In a coordinate plane, a solution is shown by the point with coordinates $(x, y)$, and the set of these points is the region of the inequality.
For example, $(1, 2)$ is a solution of $3x + 2y \leq 12$, since $3 \times 1 + 2 \times 2 = 7 \leq 12$, but $(4, 1)$ is not, since $3 \times 4 + 2 \times 1 = 14$.

Proposition — Half-Planes

Let $a$, $b$ and $c$ be numbers, with $a$ and $b$ not both zero. The line $d$ with equation $ax + by = c$ splits the plane into two half-planes:

the points of one half-plane all satisfy $ax + by < c$;
the points of the other half-plane all satisfy $ax + by > c$;
the points of $d$ itself satisfy $ax + by = c$.

More precisely, when $b > 0$ the points with $ax + by < c$ are the points below $d$ and the points with $ax + by > c$ are the points above $d$; when $b < 0$ it is the reverse; when $b = 0$ the line $d$ is vertical and the two half-planes lie to its left and to its right.
So the region of $ax + by \leq c$ is a half-plane with its boundary line $d$, and the region of $ax + by < c$ is the same half-plane without $d$.

Proof

Let $M(x, y)$ be a point of the plane.

Case $b > 0$. Subtracting $ax$ from both sides, then dividing both sides by the positive number $b$, keeps the symbol (Method “Rules for Solving Inequalities”): $$ax + by < c \iff by < c - ax \iff y < \frac{c - ax}{b}.$$ The point $N$ of $d$ with the same $x$-coordinate as $M$ has the $y$-coordinate $\dfrac{c - ax}{b}$, since it satisfies $ax + by = c$. So $M$ satisfies $ax + by < c$ exactly when it lies below $N$, that is below $d$. In the same way, $ax + by > c \iff y > \dfrac{c - ax}{b}$: $M$ lies above $d$.
Case $b < 0$. Dividing by the negative number $b$ reverses the symbol: $$ax + by < c \iff by < c - ax \iff y > \frac{c - ax}{b},$$ so the points with $ax + by < c$ lie above $d$, and those with $ax + by > c$ below $d$.
Case $b = 0$. Then $a \neq 0$ and $d$ is the vertical line $x = \dfrac{c}{a}$. If $a > 0$, then $ax < c \iff x < \dfrac{c}{a}$: the points lie to the left of $d$; if $a < 0$, then $ax < c \iff x > \dfrac{c}{a}$: they lie to its right.

In every case, the points with $ax + by < c$ fill one side of $d$ and the points with $ax + by > c$ fill the other side.

Method — Graphing a Linear Inequality

To graph the region of a linear inequality in two variables:

Draw the boundary line $ax + by = c$, for instance through its axis intercepts (when the line passes through the origin, through the origin and one other point of the line; a horizontal line $y = k$ or a vertical line $x = k$ is drawn directly): a solid line when the inequality is non-strict ($\leq$ or $\geq$), since its points are solutions; a dashed line when it is strict ($<$ or $>$), since its points are not.
Choose a test point that is not on the line — the origin $O(0, 0)$ whenever the line does not pass through it — and substitute its coordinates into the inequality.
If the test point satisfies the inequality, the region is the half-plane that contains it; otherwise it is the other half-plane (Proposition “Half-Planes”).
Shade the region of the solutions.

In this chapter, the shaded part of a figure is always the region of the solutions.

Shading Conventions

Some books shade the half-plane that is rejected and leave the solutions clear: with several inequalities, the points that satisfy all of them then form the only part left clear. Both conventions are correct, but they are opposite: a figure must say which one it follows, in a legend or in a sentence.

Report an error

Example

Graph the region of the inequality $y \leq 2x + 1$.

Answer

The boundary is the line $y = 2x + 1$, with gradient $2$ and $y$-intercept $1$. It is drawn solid, because the symbol $\leq$ is non-strict.
The line does not pass through $O$, so we test $O(0, 0)$: $$0 \leq 2 \times 0 + 1, \quad \text{that is} \quad 0 \leq 1: \text{ true.}$$ The region is the half-plane that contains $O$ — below the line — together with the line itself.

Example

Graph the region of the inequality $3x + 2y > 6$.

Answer

The boundary line $3x + 2y = 6$ meets the $x$-axis where $y = 0$, so $3x = 6$ and $x = 2$, and the $y$-axis where $x = 0$, so $2y = 6$ and $y = 3$: it passes through $(2, 0)$ and $(0, 3)$. It is drawn dashed, because the symbol $>$ is strict.
Test point $O(0, 0)$: $$3 \times 0 + 2 \times 0 = 0, \quad \text{and} \quad 0 > 6 \text{ is false.}$$ The region is the half-plane that does not contain $O$ — above the line — and the line is excluded.

Example

Graph the region of each inequality.

$x \geq -1$
$y < 2$

Answer

The boundary is the vertical line $x = -1$, solid ($\geq$ is non-strict). Test point $O(0, 0)$: $0 \geq -1$ is true, so the region is the half-plane to the right of the line, the line included.
The boundary is the horizontal line $y = 2$, dashed ($<$ is strict). Test point $O(0, 0)$: $0 < 2$ is true, so the region is the half-plane below the line, the line excluded.

In an inequality where one variable is missing, that variable can take any value: the region of $x \geq -1$ contains the points $(0, 5)$, $(0, -100)$ and every point $(x, y)$ with $x \geq -1$, whatever $y$.

Skills to practice

Recognising Solutions and Regions
Testing Points
Graphing an Inequality

II.2 The Feasible Region

Definition — Feasible Region

A system of linear inequalities is a list of linear inequalities in the same variables that must be true at the same time; in a problem, these inequalities are called the constraints.
A pair $(x, y)$ is a solution of the system when it satisfies every inequality of the system. The region of these solutions is the feasible region: it is the part of the plane that the regions of all the inequalities have in common.
A vertex of the feasible region is a corner of its boundary, where two boundary lines meet. When the constraints are non-strict ($\leq$, $\geq$), as in the linear programming problems of this chapter, the region contains its boundary, and so its vertices.

Example

Graph the feasible region of the system $$\begin{cases} x \geq 0 \\ y \geq 0 \\ x + y \leq 6 \\ x + 2y \leq 8 \end{cases}$$ and give the coordinates of its vertices.

Answer

$x \geq 0$ and $y \geq 0$: the region lies to the right of the $y$-axis and above the $x$-axis, axes included.
$x + y \leq 6$: solid boundary through $(6, 0)$ and $(0, 6)$; test point $O$: $0 \leq 6$ is true, so the side of $O$.
$x + 2y \leq 8$: solid boundary through $(8, 0)$ and $(0, 4)$; test point $O$: $0 \leq 8$ is true, so the side of $O$.

The feasible region is the quadrilateral $OABC$, the common part of the four half-planes.

$O$, $A$ and $C$ lie on the axes. The vertex $B$ is where the lines $x + y = 6$ and $x + 2y = 8$ meet: $$\begin{aligned}[t] (x + 2y) - (x + y) &= 8 - 6 && \text{(subtracting the two equations)}\\ y &= 2, \end{aligned}$$ then $x = 6 - 2 = 4$. The vertices are $O(0, 0)$, $A(6, 0)$, $B(4, 2)$ and $C(0, 4)$.

Method — Finding the Vertices of a Feasible Region

Graph the feasible region.
At each corner, name the two boundary lines that meet there.
Solve the system formed by their two equations (Methods “Solving by Substitution” and “Solving by Elimination”).
Check the other constraints: a point where two boundary lines meet but which breaks another constraint lies outside the region, and it is not a vertex.

Example

Find the vertices of the feasible region of the system $$\begin{cases} x \geq 0 \\ y \geq 0 \\ 2x + y \leq 10 \\ x + 3y \leq 15 \end{cases}$$

Answer

The lines $2x + y = 10$ and $x + 3y = 15$: the first equation gives $y = 10 - 2x$, and substituting, $$\begin{aligned}[t] x + 3(10 - 2x) &= 15\\ x + 30 - 6x &= 15\\ -5x &= -15\\ x &= 3, \end{aligned}$$ then $y = 10 - 2 \times 3 = 4$. The point $(3, 4)$ satisfies $x \geq 0$ and $y \geq 0$: it is a vertex.
On the $x$-axis ($y = 0$): $2x = 10$ gives $(5, 0)$, and $5 + 3 \times 0 = 5 \leq 15$: a vertex.
On the $y$-axis ($x = 0$): $3y = 15$ gives $(0, 5)$, and $2 \times 0 + 5 = 5 \leq 10$: a vertex.
The line $2x + y = 10$ also meets the $y$-axis at $(0, 10)$, but $0 + 3 \times 10 = 30 > 15$: this point breaks the last constraint, so it is not a vertex. In the same way, $(15, 0)$ breaks $2x + y \leq 10$.

The vertices are $O(0, 0)$, $(5, 0)$, $(3, 4)$ and $(0, 5)$.

Method — Writing Constraints from a Situation

Name each unknown with its meaning and its unit: “let $x$ be the number of …”.
Translate each condition of the text into an inequality: “at most” gives $\leq$, “at least” gives $\geq$, “less than” gives $<$, “more than” gives $>$.
Add the conditions the text does not state: a number of objects, a mass, a time or an area cannot be negative ($x \geq 0$, $y \geq 0$), and a number of objects is a whole number.
Check each inequality on a simple case: a pair that clearly meets (or breaks) the condition must satisfy (or break) the inequality.

Example

A craftswoman makes stools and tables. A stool needs $1$ hour of cutting and $2$ hours of assembly; a table needs $3$ hours of cutting and $2$ hours of assembly. Each week she has at most $24$ hours of cutting and at most $20$ hours of assembly, and she has an order for at least $2$ tables.
Write the constraints on the numbers $x$ of stools and $y$ of tables that she makes in a week, and graph the feasible region.

Answer

Let $x$ be the number of stools and $y$ the number of tables made in a week; they are whole numbers.

Cutting: $x$ stools need $x$ hours and $y$ tables $3y$ hours, so $x + 3y \leq 24$.
Assembly: $2x + 2y \leq 20$, that is $x + y \leq 10$ after dividing both sides by $2$.
The order: $y \geq 2$.
Not negative: $x \geq 0$ (the condition $y \geq 0$ is already implied by $y \geq 2$).

Check: $0$ stools and $2$ tables need $6$ hours of cutting and $4$ of assembly, within the limits, and indeed $0 + 3 \times 2 = 6 \leq 24$ and $0 + 2 = 2 \leq 10$. As $x$ and $y$ count objects, only the points of the region with whole-number coordinates are possible production plans.

Skills to practice

Translating Conditions into Inequalities
Finding the Vertices of a Region
Drawing a Feasible Region

III Linear Programming

III.1 Optimising a Linear Objective

Definition — Objective Function

In a problem with constraints, the quantity to make as large or as small as possible is the objective function. Here it is a linear expression $$P = px + qy$$ of the two unknowns, where $p$ and $q$ are numbers, not both zero.
For a number $k$, the points where $P = k$ form the line with equation $px + qy = k$, called a level line of $P$. All the level lines of $P$ are parallel: when $q \neq 0$, they all have the gradient $-\dfrac{p}{q}$.
A linear programming problem asks for the maximum or the minimum of an objective function on a feasible region.

Proposition — Optimum at a Vertex

Let the feasible region be a polygon that is closed (its boundary is included) and bounded (it does not extend without end). Then the objective function $P = px + qy$ has a maximum and a minimum on the region, and each of them is reached at a vertex of the region; it may also be reached at every point of a whole edge joining two vertices.
If the feasible region is unbounded, a maximum or a minimum may not exist.

Proof

As $k$ increases, the level line $px + qy = k$ moves parallel to itself, always in the same direction, and $P$ takes the value $k$ at a point of the region exactly when this level line meets the region. Here is the region of vertices $O(0, 0)$, $A(6, 0)$, $B(4, 2)$, $C(0, 4)$, with $P = 2x + 3y$: the level line $P = 6$ crosses the region, $P = 12$ still crosses it (it passes through $A$ and $C$), $P = 14$ only touches it at $B$, and $P = 18$ misses it.

As the region is bounded, the level lines that meet it stop at a last position; as the region also contains its boundary, this last position still meets the region: it is the largest value of $k$ for which the level line meets the region. (If an edge were excluded, the level lines could come closer and closer to it without a last position inside the region.) In that position the line touches the region without entering it: the whole region lies on one side of the line. A line that touches a polygon in this way passes through a vertex, or contains a whole edge — and then both ends of that edge are vertices. So the largest value of $P$ is reached at a vertex. The same argument, with the smallest value of $k$, gives the minimum.
On an unbounded region the level lines may meet the region for every value of $k$: there is then no last position, and no maximum.

Method — Solving a Linear Programming Problem

Define the unknowns, write the constraints and the objective function.
Graph the feasible region and check that it is closed and bounded; when it is unbounded, the optimum asked for may not exist, and it must be justified directly (Remark “Unbounded Regions”).
Find the coordinates of its vertices (Method “Finding the Vertices of a Feasible Region”).
Evaluate the objective function at every vertex, in a table, and read the largest or the smallest value — or slide a level line across the region: both give the same best value (at a vertex, or along a whole edge).
When the unknowns must be whole numbers and the best vertex does not have whole-number coordinates, use the value at that vertex as a bound: no point of the region does better. Then look for the points of the region with whole-number coordinates whose value comes closest to that bound — usually near the vertex, but not always, so check the level lines $P = k$ for the best values of $k$ in turn (when $p$ and $q$ are whole numbers, $P$ takes whole values at those points: for a maximum, try the whole values of $k$ below the bound, from the largest down; for a minimum, the whole values above the bound, from the smallest up) — and test each point against every constraint: never round the coordinates of the vertex.
Answer the question with a sentence, in its context and with its units.

Example

A craftswoman makes $x$ stools and $y$ tables a week, under the constraints $$x \geq 0, \qquad y \geq 2, \qquad x + 3y \leq 24, \qquad x + y \leq 10$$ (hours of cutting, hours of assembly and an order for at least $2$ tables). She makes a profit of $\dollar 40$ on a stool and $\dollar 100$ on a table. How many stools and tables should she make to earn the greatest profit?

Answer

The objective function is the weekly profit, in dollars: $P = 40x + 100y$.
The feasible region is closed and bounded; its vertices are

$(0, 2)$, where $x = 0$ meets $y = 2$;
$(8, 2)$, where $y = 2$ meets $x + y = 10$: $x = 10 - 2 = 8$, and $8 + 3 \times 2 = 14 \leq 24$;
$(3, 7)$, where $x + 3y = 24$ meets $x + y = 10$: subtracting the equations, $2y = 14$, so $y = 7$ and $x = 10 - 7 = 3$;
$(0, 8)$, where $x = 0$ meets $x + 3y = 24$: $y = 8$, and $0 + 8 = 8 \leq 10$.

Vertex	$(0, 2)$	$(8, 2)$	$(3, 7)$	$(0, 8)$
$P = 40x + 100y$	$200$	$520$	$820$	$800$

The largest value is $820$, at $(3, 7)$, whose coordinates are whole numbers. The level line $P = 820$ touches the region only at this vertex:

She should make $3$ stools and $7$ tables, for a profit of $\dollar 820$ a week.

Example

A florist has $12$ roses and $10$ tulips. A small bouquet uses $2$ roses and $4$ tulips; a large bouquet uses $3$ roses and $1$ tulip. How many bouquets of each size should she make to make as many bouquets as possible?

Answer

Let $x$ be the number of small bouquets and $y$ the number of large ones: whole numbers with $x \geq 0$ and $y \geq 0$. The roses give $2x + 3y \leq 12$ and the tulips $4x + y \leq 10$. The objective function is the number of bouquets $N = x + y$.
The vertices of the feasible region are $O(0, 0)$, $(2.5, 0)$, $(0, 4)$ and the point $B$ where $2x + 3y = 12$ meets $4x + y = 10$: $$\begin{aligned}[t] y &= 10 - 4x && \text{(second equation)}\\ 2x + 3(10 - 4x) &= 12 && \text{(substituting)}\\ -10x &= -18, \end{aligned}$$ so $x = 1.8$ and $y = 10 - 4 \times 1.8 = 2.8$. At the vertices, $N$ is worth $0$, $2.5$, $4$ and $1.8 + 2.8 = 4.6$: the best vertex is $B(1.8, 2.8)$, which is not a pair of whole numbers.

Rounding $B$ gives $(2, 3)$, which needs $2 \times 2 + 3 \times 3 = 13$ roses: it lies outside the region. On the region $N \leq 4.6$, so a whole number of bouquets is at most $4$. The points of the region with whole coordinates and $x + y = 4$ are $(0, 4)$, $(1, 3)$ and $(2, 2)$ (check $(2, 2)$: $4 + 6 = 10 \leq 12$ roses and $8 + 2 = 10 \leq 10$ tulips); $(3, 1)$ needs $13$ tulips.
She can make at most $4$ bouquets: $4$ large ones, or $1$ small and $3$ large, or $2$ small and $2$ large.

Unbounded Regions

The feasible region of the constraints $x \geq 0$, $y \geq 0$, $x + y \geq 4$ is unbounded: it extends without end upwards and to the right.

On it, $P = x + y$ has a minimum, $4$, reached at every point of the edge from $(4, 0)$ to $(0, 4)$. But $P$ has no maximum: for every whole number $n \geq 4$, the point $(n, 0)$ belongs to the region and $P = n$ there, as large as we want. Before stating a maximum, check that the region is bounded.

Report an error

Skills to practice

Evaluating an Objective at the Vertices
Solving a Linear Programming Problem

IV Going further

Skills to practice

Reasoning with Sign Tables
Solving Real-Life Problems
Investigating Patterns in Linear Programming
Quiz

Vertex	\((0, 2)\)	\((8, 2)\)	\((3, 7)\)	\((0, 8)\)
\(P = 40x + 100y\)	\(200\)	\(520\)	\(820\)	\(800\)