Chapter 12 · Linear Programming

Example 3: Minimise and maximise $Z = 3x + 9y$ ⁠: multiple optimal solutions

ExamplesCorner Point Method, a tie at the maximum · Section 12.2.2

The question

Solve the following problem graphically:

Minimise and Maximise $Z = 3x + 9y$ … (1)

subject to the constraints:

\begin{aligned} x + 3y &\le 60 &&\ldots(2) \\ x + y &\ge 10 &&\ldots(3) \\ x &\le y &&\ldots(4) \\ x \ge 0,\ y &\ge 0 &&\ldots(5) \end{aligned}

Exam answer

Draw the lines (graph):

$x + 3y = 60$ through $(60, 0)$ and $(0, 20)$ ⁠;

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

$x = y$ through $(0, 0)$ and $(20, 20)$ ⁠.

At $(0, 0)$ ⁠: $0 \le 60$ is true, so shade towards the origin for (2); $0 \ge 10$ is false, so shade away from the origin for (3). For $x \le y$ test $(0, 1)$ ⁠: $0 \le 1$ is true, so shade the side of $x = y$ that contains $(0, 1)$ ⁠. With $x, y \ge 0$ ⁠, the feasible region is ABCD (shaded). It is bounded.

B: $x = y$ in $x + y = 10$ gives $B(5, 5)$ ⁠.

C: $x = y$ in $x + 3y = 60$ gives $4x = 60$ ⁠, so $C(15, 15)$ ⁠.

\begin{array}{c|c} \text{Corner} & Z = 3x + 9y \\ \hline A(0, 10) & 90 \\ B(5, 5) & 60 \leftarrow \text{min} \\ C(15, 15) & 180 \leftarrow \text{max} \\ D(0, 20) & 180 \leftarrow \text{max} \end{array}

The region is bounded, so the smallest and largest values in the table are the minimum and maximum of $Z$ ⁠. The maximum occurs at two corners, C and D, so it occurs at every point of the segment CD.

$\therefore$ Minimum $Z = 60$ at $(5, 5)$ ⁠; maximum $Z = 180$ at every point of the segment joining $(15, 15)$ and $(0, 20)$ ⁠.

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

The one idea this problem is built on

The constraint $x \le y$ has a line through the origin, so the origin cannot be the test point for it. Apart from that, the method is the same: shade, find the four corners, tabulate $Z$ ⁠. The new feature is a tie: $Z = 3x + 9y = 3(x + 3y)$ is parallel to the edge $x + 3y = 60$ ⁠, so $Z = 180$ at both ends of that edge, and at every point between them.

Given, to find, and the plan

Given: $Z = 3x + 9y$ and the constraints $x + 3y \le 60$ ⁠, $x + y \ge 10$ ⁠, $x \le y$ ⁠, $x \ge 0$ ⁠, $y \ge 0$ ⁠.
To find: The minimum and the maximum of $Z$ ⁠, and where each occurs.
Plan: (1) to (3) Draw each line and choose its side (a different test point for $x = y$ ⁠). (4) Shade ABCD. (5) Find the corners. (6) Tabulate $Z$ ⁠. (7) Read off both values and explain the tie.

Basics you need

1Drawing a line from its axis points

Put $y = 0$ ⁠, then $x = 0$ ⁠. A line through the origin, like $x = y$ ⁠, needs a second point such as $(20, 20)$ ⁠. Basics: where a line meets the axes

2The test point decides the side

Use $(0, 0)$ unless it lies on the line; then use another point, such as $(0, 1)$ ⁠. Basics: one side of a line

3The feasible region and its corners

The overlap of all the kept sides; each corner is where two boundary lines meet. Basics: where the shadings overlap · Basics: a corner solves two equations

4Lines of equal $Z$

$3x + 9y = k$ is a family of parallel lines. If one of them lies along an edge of the region, $Z$ is the same all along that edge. Basics: lines of equal Z

5Bounded region: Theorem 2

On a bounded region $Z$ has a maximum and a minimum, each at a corner point (Section 12.2.2). Basics: bounded or not

Solution

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

Put $y = 0$ ⁠: $x = 60$ ⁠. Put $x = 0$ ⁠: $3y = 60$ ⁠, so $y = 20$ ⁠. The line joins $(60, 0)$ and $(0, 20)$ ⁠.

Test $(0, 0)$ in (2): $0 \le 60$ is true, so (2) keeps the origin's side.

" $\le$ " with a positive number on the right: the origin satisfies it, so its side (with the line) is kept.

Basics: where a line meets the axes
Draw the line $x + y = 10$ and choose its side

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

The origin gives $x + y = 0$ ⁠, which is not at least 10, so the kept side is the one without the origin.

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

The boundary of $x \le y$ is $x - y = 0$ ⁠, the line through $(0, 0)$ and $(20, 20)$ ⁠. The origin lies on it, so test $(0, 1)$ instead: $0 \le 1$ is true. So (4) keeps the side of $x = y$ that contains $(0, 1)$ ⁠, the side towards the $y$ -axis.

A test point on the line itself gives " $0 \le 0$ ", which is true for both sides and decides nothing. Any point off the line works; $(0, 1)$ is the simplest, and it lies above the line, where $y$ is bigger than $x$ ⁠.

Basics: which side
Shade the feasible region

Together with $x \ge 0$ and $y \ge 0$ ⁠, the kept sides overlap in the quadrilateral ABCD:

The feasible region ABCD of Example 3 (shaded). One unit along the $y$ -axis is drawn about 1.5 times as long as one unit along the $x$ -axis, so the line $x = y$ looks steeper than it is. The corners are A(0, 10), B(5, 5), C(15, 15) and D(0, 20); the thick edge CD is where $Z = 180$ ⁠.

ABCD is bounded: every corner is within about 21.2 of O (the farthest is C, at $\sqrt{450}$ ⁠), so a circle about O of radius 22 encloses it.

The region is cut off below by $x + y = 10$ ⁠, on the right by $x = y$ ⁠, above by $x + 3y = 60$ ⁠, and on the left by the $y$ -axis. The constraint $y \ge 0$ is obeyed automatically here, because $y \ge x \ge 0$ ⁠.

Basics: where the shadings overlap · Basics: bounded or not
Find the corner points

A $(0, 10)$ ⁠: $x + y = 10$ meets the $y$ -axis. D $(0, 20)$ ⁠: $x + 3y = 60$ meets the $y$ -axis.

B: put $x = y$ in $x + y = 10$ ⁠: $2x = 10$ ⁠, so B is $(5, 5)$ ⁠.

C: put $x = y$ in $x + 3y = 60$ ⁠: $4x = 60$ ⁠, so C is $(15, 15)$ ⁠.

Each obeys every constraint; for example C: $15 + 45 = 60 \le 60$ ⁠, $30 \ge 10$ ⁠, $15 \le 15$ ⁠. The remaining crossing points are outside the region: $(10, 0)$ ⁠, $(60, 0)$ break $x \le y$ ⁠; O breaks $x + y \ge 10$ ⁠; and $x + 3y = 60$ meets $x + y = 10$ at $(-15, 25)$ ⁠, which breaks $x \ge 0$ ⁠.

Where one line is $x = y$ ⁠, substituting $y = x$ turns the other equation into one with a single unknown. Checking the leftover crossings shows that the region has exactly these four corners.

Basics: a corner solves two equations

Work out $Z$ at each corner

Corner point	$Z = 3x + 9y$
A $(0, 10)$	$0 + 90 = 90$
B $(5, 5)$	$15 + 45 = 60$ ← smallest
C $(15, 15)$	$45 + 135 = 180$ ← largest
D $(0, 20)$	$0 + 180 = 180$ ← largest

The region is bounded, so by Theorem 2 both the minimum and the maximum exist and are among these four values:

m = 60

⁠,

M = 180

⁠.

Lesson: the corner point method

Conclude, and explain the tie

Minimum $Z = 60$ at B $(5, 5)$ ⁠.

Maximum $Z = 180$ , reached at both C $(15, 15)$ and D $(0, 20)$ ⁠. Then it is reached at every point of the segment CD as well: $Z = 3x + 9y = 3(x + 3y)$ ⁠, and every point of CD lies on $x + 3y = 60$ ⁠, so $Z = 3 \times 60 = 180$ there.

The book's Remark after this example states the general fact: when two corner points give the same optimal value, every point on the segment joining them gives it too, so the problem has multiple optimal solutions. Here the reason is visible: the lines $Z = k$ are parallel to the edge CD, and the line $Z = 180$ lies along it.

Lesson: Examples 1 to 3, step by step · Basics: lines of equal Z

Result

The feasible region is bounded, with corners $(0, 10)$ ⁠, $(5, 5)$ ⁠, $(15, 15)$ ⁠, $(0, 20)$ ⁠, and

\begin{aligned} &\text{Minimum } Z = 60 \text{ at } (5, 5), \\ &\text{Maximum } Z = 180 \\ &\text{on the segment joining} \\ &(15, 15) \text{ and } (0, 20). \end{aligned}

(Textbook answer: minimum 60 at $(5, 5)$ ⁠; maximum 180 at $(15, 15)$ and $(0, 20)$ ⁠, multiple optimal solutions.)

Check it with numbers

Exact bounds on the whole region: $Z = 3(x + 3y) \le 3 \times 60 = 180$ ⁠. Also $x \le y$ and $x + y \ge 10$ give $2y \ge x + y \ge 10$ ⁠, so $y \ge 5$ ⁠, and $Z = 3(x + y) + 6y \ge 30 + 30 = 60$ ⁠, with equality only at $(5, 5)$ ✓.

The midpoint of CD, $\left(\frac{15}{2}, \frac{35}{2}\right)$ ⁠, gives $Z = \frac{45}{2} + \frac{315}{2} = 180$ ✓, and so does $(3, 19)$ ⁠: $9 + 171 = 180$ ✓.

A computer check of all 141 whole-number points of the region found the smallest value 60 at $(5, 5)$ only, and the largest value 180 at exactly six points, $(0, 20)$ ⁠, $(3, 19)$ ⁠, $(6, 18)$ ⁠, $(9, 17)$ ⁠, $(12, 16)$ ⁠, $(15, 15)$ ⁠, all on CD ✓.

Common mistakes

Testing $(0, 0)$ for $x \le y$ ⁠. It lies on the line $x = y$ ⁠; use a point off the line, such as $(0, 1)$ ⁠.
Shading below $x = y$ ⁠. $x \le y$ keeps the side where $y$ is the bigger one, towards the $y$ -axis.
Giving only one point for the maximum. C and D tie, so the maximum is at every point of CD.
Using $(10, 0)$ as a corner. It is on $x + y = 10$ but breaks $x \le y$ ⁠.

What to take away

For a line through the origin, test any other point.
If two corners give the same best value, every point of the segment joining them does too: multiple optimal solutions.
A tie happens when $Z = k$ is parallel to an edge; spot it by comparing coefficients, as in $3x + 9y = 3(x + 3y)$ ⁠. Example 4 moves on to an unbounded region.

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 to 3	Class XI, Linear Inequalities (Basics, Basics)
Feasible region; bounded means it can be enclosed within a circle	Step 4	Section 12.2.2 and the footnote to Theorem 2 (Basics)
Corner point: where two boundary lines meet	Step 5	Section 12.2.2, footnote to Theorem 1 (Basics)
Theorem 2: bounded region, maximum and minimum at corners	Steps 6, 7	Section 12.2.2
Two corners with the same optimal value: the whole segment is optimal	Step 7	Remark after Example 3, Section 12.2.2 (Basics)
Textbook working and answer	Result	Example 3, Section 12.2.2
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 3: Minimise and maximise Z=3x+9yZ = 3x + 9yZ=3x+9y⁠: multiple optimal solutions

Basics you need

Solution

Draw the line x+3y=60x + 3y = 60x+3y=60 and choose its side

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

Draw the line x=yx = yx=y and choose its side

Shade the feasible region

Find the corner points

Work out ZZZ at each corner

Conclude, and explain the tie

Every fact used, and where it comes from

Example 3: Minimise and maximise $Z = 3x + 9y$ ⁠: multiple optimal solutions

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

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

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

Work out $Z$ at each corner