Chapter 12 · Linear Programming

Example 1: Maximise $Z = 4x + y$ on a bounded feasible region

ExamplesCorner Point Method, bounded region · Section 12.2.2

The question

Solve the following linear programming problem graphically:

Maximise $Z = 4x + y$ … (1)

subject to the constraints:

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

Exam answer

Draw the lines (graph):

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

$3x + y = 90$ through $(30, 0)$ and $(0, 90)$ ⁠.

At $(0, 0)$ ⁠: $0 \le 50$ and $0 \le 90$ are true, so shade the side of each line that contains the origin. With $x, y \ge 0$ ⁠, the feasible region is OABC (shaded). It is bounded.

At B, subtracting $x + y = 50$ from $3x + y = 90$ gives $2x = 40$ ⁠, so $x = 20$ ⁠, $y = 30$ ⁠.

\begin{array}{c|c} \text{Corner} & Z = 4x + y \\ \hline O(0, 0) & 0 \\ A(30, 0) & 120 \leftarrow \text{max} \\ B(20, 30) & 110 \\ C(0, 50) & 50 \end{array}

The region is bounded, so the largest value in the table is the maximum of $Z$ ⁠.

$\therefore$ Maximum $Z = 120$ at $(30, 0)$ ⁠.

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

The one idea this problem is built on

Each constraint keeps one side of a straight line, and the four kept sides overlap in a closed quadrilateral, the feasible region. Because the region is bounded and $Z = 4x + y$ is linear, the maximum of $Z$ exists and is at a corner. So the whole problem comes down to four corners and a table of four values.

Given, to find, and the plan

Given: $Z = 4x + y$ and the constraints $x + y \le 50$ ⁠, $3x + y \le 90$ ⁠, $x \ge 0$ ⁠, $y \ge 0$ ⁠.
To find: The maximum value of $Z$ on the feasible region, and where it occurs.
Plan: (1) and (2) Draw each line from its axis points and choose its side. (3) Shade the feasible region and see that it is bounded. (4) Find the corners. (5) Make the table of $Z$ ⁠. (6) Read off the maximum.

Basics you need

1Drawing a line from its axis points

For $ax + by = c$ ⁠, put $y = 0$ ⁠, then $x = 0$ ⁠, and join the two points. Basics: where a line meets the axes

2Which side of the line

Put $(0, 0)$ into the inequality: true means shade the origin's side, false means the other side. Basics: one side of a line

3The feasible region

The points obeying all the constraints: the overlap of all the kept sides. Basics: where the shadings overlap

4Corner points

Where two boundary lines meet; solve their two equations together, then check the point in every constraint. Basics: a corner solves two equations

5Bounded region: Theorem 2

If the region can be enclosed in a circle, $Z$ has a maximum and a minimum on it, and each occurs at a corner point (Section 12.2.2). Basics: bounded or not

Solution

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

Put $y = 0$ ⁠: $x = 50$ ⁠. Put $x = 0$ ⁠: $y = 50$ ⁠. So the line joins $(50, 0)$ and $(0, 50)$ ⁠.

Test $(0, 0)$ in (2): $0 + 0 \le 50$ is true, so constraint (2) keeps the side of the line that contains the origin.

The boundary of $x + y \le 50$ is the line $x + y = 50$ ⁠, and two points fix a line; the axis points are the quickest to find. The inequality holds on one whole side, and one test point tells us which.

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

Put $y = 0$ ⁠: $3x = 90$ ⁠, so $x = 30$ ⁠. Put $x = 0$ ⁠: $y = 90$ ⁠. So the line joins $(30, 0)$ and $(0, 90)$ ⁠.

Test $(0, 0)$ in (3): $0 \le 90$ is true, so again the origin's side is kept.

Same method. This line is steeper (it falls 3 units for each unit across), so it meets the $x$ -axis sooner, at 30 instead of 50.

Basics: one side of a line
Shade the feasible region

Constraint (4) keeps the first quadrant. The part of it on the origin's side of both lines is the quadrilateral OABC:

The feasible region OABC of Example 1 (shaded). One unit along the $x$ -axis is drawn 1.75 times as long as one unit along the $y$ -axis. The corners are O(0, 0), A(30, 0), B(20, 30) and C(0, 50); the points $(50, 0)$ and $(0, 90)$ are outside the region.

OABC is bounded: every corner is within 50 of O (B is $\sqrt{20^2 + 30^2} = \sqrt{1300}$ ⁠, about 36, from O), so a circle about O of radius 51 encloses it.

The feasible region is where all four kept sides overlap. Whether it is bounded decides how we read the table at the end: for a bounded region the largest corner value is certainly the maximum.

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

O $(0, 0)$ ⁠, where the axes meet.

A $(30, 0)$ ⁠, where $3x + y = 90$ meets the $x$ -axis. The other line meets the $x$ -axis at $(50, 0)$ ⁠, but there $3(50) + 0 = 150 > 90$ ⁠, so $(50, 0)$ breaks (3) and is not a corner.

C $(0, 50)$ ⁠, where $x + y = 50$ meets the $y$ -axis. The point $(0, 90)$ breaks (2): $0 + 90 > 50$ ⁠.

B, where the two lines cross:
$\begin{aligned} (3x + y) - (x + y) &= 90 - 50 \\ 2x &= 40 \\ x &= 20, \end{aligned}$
and $y = 50 - 20 = 30$ ⁠. So B is $(20, 30)$ ⁠, and it obeys every constraint: $20 + 30 = 50$ ⁠, $3(20) + 30 = 90$ ⁠, $20, 30 \ge 0$ ⁠.

The two lines and the two axes cross in six points; only the four that obey every constraint are corners of the region. Subtracting the equations removes $y$ ⁠, because both have $+y$ ⁠.

Basics: a corner solves two equations

Work out $Z$ at each corner

Corner point	$Z = 4x + y$
O $(0, 0)$	$0$
A $(30, 0)$	$120 + 0 = 120$ ← largest
B $(20, 30)$	$80 + 30 = 110$
C $(0, 50)$	$0 + 50 = 50$

By Theorem 1 the maximum, if it exists, is at a corner, so these four values are the only candidates. The largest is

M = 120

and the smallest is

m = 0

⁠.

Lesson: the corner point method

Conclude

The region is bounded, so by Theorem 2 the largest value in the table is the maximum of $Z$ ⁠: maximum $Z = 120$ at $(30, 0)$ .

Notice that the best corner is A, not the crossing point B. $Z = 4x + y$ rewards $x$ four times as much as $y$ ⁠, and A has the largest possible $x$ ⁠. Moving from A to B along $3x + y = 90$ loses $4$ for each unit of $x$ given up but gains only $3$ in $y$ ⁠: a net loss.

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

Result

The feasible region is bounded, with corners $(0, 0)$ ⁠, $(30, 0)$ ⁠, $(20, 30)$ and $(0, 50)$ ⁠, and

\text{Maximum } Z = 120 \text{ at } (30, 0).

(Textbook answer: maximum value of $Z$ is 120 at the point $(30, 0)$ ⁠.)

Check it with numbers

A direct proof that nothing beats 120: on the region $y \ge 0$ ⁠, so (3) gives $3x \le 90$ ⁠, that is $x \le 30$ ⁠. Then $Z = 4x + y = (3x + y) + x \le 90 + 30 = 120$ ⁠, with equality only when $x = 30$ and $3x + y = 90$ ⁠, that is at $(30, 0)$ ✓.

Two other feasible points: $(25, 10)$ gives $Z = 110$ ⁠, and $(10, 40)$ gives $Z = 80$ ⁠; both are below 120 ✓.

A computer check of all 1006 whole-number points of the region found the largest value 120, at $(30, 0)$ only ✓.

Common mistakes

Assuming the crossing point B is always the answer. It gives 110 here; the table decides, not the picture.
Using $(50, 0)$ as a corner. It lies on $x + y = 50$ but breaks $3x + y \le 90$ ⁠.
Shading away from the origin for " $\le$ ". Test $(0, 0)$ ⁠: $0 \le 50$ is true, so the origin's side is kept.
Leaving out O. The origin is a corner too; here it gives the minimum, 0.

What to take away

For " $\le$ " constraints with positive numbers on the right, together with $x, y \ge 0$ ⁠, the region is a closed polygon with a corner at the origin.
Find every corner, check each in every constraint, and let the table decide.
The same steps give the dealer's answer in Section 12.2; Example 2 has a " $\ge$ " constraint and asks for a minimum.

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)
Feasible region: common region of all the constraints	Step 3	Section 12.2.2 (Basics)
Bounded: can be enclosed within a circle	Step 3	Section 12.2.2, footnote to Theorem 2 (Basics)
Corner point: where two boundary lines meet	Step 4	Section 12.2.2, footnote to Theorem 1 (Basics)
Theorem 1 and Theorem 2	Steps 5, 6	Section 12.2.2
Corner Point Method, step 3(i): bounded region	Step 6	Section 12.2.2 (Lesson)
Textbook working and answer	Result	Example 1, 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 1: Maximise Z=4x+yZ = 4x + yZ=4x+y on a bounded feasible region

Basics you need

Solution

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

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

Shade the feasible region

Find the corner points

Work out ZZZ at each corner

Conclude

Every fact used, and where it comes from

Example 1: Maximise $Z = 4x + y$ on a bounded feasible region

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

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

Work out $Z$ at each corner