Chapter 12 · Linear Programming

Example 2: Minimise $Z = 200x + 500y$ graphically

ExamplesCorner Point Method, a “≥” constraint · Section 12.2.2

The question

Solve the following linear programming problem graphically:

Minimise $Z = 200x + 500y$ … (1)

subject to the constraints:

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

Exam answer

Draw the lines (graph):

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

$3x + 4y = 24$ through $(8, 0)$ and $(0, 6)$ ⁠.

At $(0, 0)$ ⁠: $0 \ge 10$ is false, so for $x + 2y \ge 10$ shade the side away from the origin; $0 \le 24$ is true, so for $3x + 4y \le 24$ shade the side containing the origin. With $x, y \ge 0$ ⁠, the feasible region is the triangle ABC (shaded). It is bounded.

At B, from $x + 2y = 10$ ⁠, $x = 10 - 2y$ ⁠. Then $3(10 - 2y) + 4y = 24$ gives $y = 3$ ⁠, $x = 4$ ⁠.

\begin{array}{c|c} \text{Corner} & Z = 200x + 500y \\ \hline A(0, 5) & 2500 \\ B(4, 3) & 2300 \leftarrow \text{min} \\ C(0, 6) & 3000 \end{array}

The region is bounded, so the smallest value in the table is the minimum of $Z$ ⁠.

$\therefore$ Minimum $Z = 2300$ at $(4, 3)$ ⁠.

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

The one idea this problem is built on

A " $\ge$ " constraint keeps the side of its line away from the origin, and a " $\le$ " constraint the side towards it. Here the two kept sides overlap only in a thin triangle between the two lines, next to the $y$ -axis. It is bounded, so the minimum of the linear function $Z$ exists and sits at one of the three corners.

Given, to find, and the plan

Given: $Z = 200x + 500y$ and the constraints $x + 2y \ge 10$ ⁠, $3x + 4y \le 24$ ⁠, $x \ge 0$ ⁠, $y \ge 0$ ⁠.
To find: The minimum value of $Z$ and where it occurs.
Plan: (1) and (2) Draw each line and choose its side with the test point $(0, 0)$ ⁠. (3) Shade the triangle ABC. (4) Find its corners, solving for B. (5) Tabulate $Z$ ⁠. (6) Take the smallest value.

Basics you need

1Drawing a line from its axis points

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

2The test point decides the side

If $(0, 0)$ makes the inequality false, the kept side is the one without the origin. Basics: one side of a line

3The feasible region

The overlap of all the kept sides, including $x \ge 0$ and $y \ge 0$ ⁠. Basics: where the shadings overlap

4Corner points

Solve the equations of the two lines that meet there; check the point in every constraint. Basics: a corner solves two equations

5Bounded region: Theorem 2

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

Solution

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

Put $y = 0$ ⁠: $x = 10$ ⁠. Put $x = 0$ ⁠: $2y = 10$ ⁠, so $y = 5$ ⁠. The line joins $(10, 0)$ and $(0, 5)$ ⁠.

Test $(0, 0)$ in (2): $0 + 0 \ge 10$ is false. So (2) keeps the side of the line that does not contain the origin.

The origin gives $x + 2y = 0$ ⁠, which is too small for "at least 10". Every point on the origin's side gives a value below 10, and every point on the far side a value above 10, so the far side (with the line itself) is kept.

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

Put $y = 0$ ⁠: $3x = 24$ ⁠, so $x = 8$ ⁠. Put $x = 0$ ⁠: $4y = 24$ ⁠, so $y = 6$ ⁠. The line joins $(8, 0)$ and $(0, 6)$ ⁠.

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

Same test, opposite result: " $\le$ " with a positive number on the right always keeps the origin.

Basics: one side of a line
Shade the feasible region

We need points above $x + 2y = 10$ ⁠, below $3x + 4y = 24$ ⁠, and in the first quadrant. On the $y$ -axis this is $5 \le y \le 6$ ⁠; moving right, the two lines close in and meet at B. The region is the small triangle ABC:

The feasible region of Example 2 is the thin triangle ABC (shaded), drawn with equal scales. A(0, 5) and C(0, 6) are on the $y$ -axis, and B(4, 3) is where the two lines cross. Beyond B the line $3x + 4y = 24$ is below $x + 2y = 10$ ⁠, so no point there obeys both constraints.

The triangle is bounded: all three corners lie within a circle about O of radius 6.

To the right of B, every point on or below $3x + 4y = 24$ is below $x + 2y = 10$ ⁠, so the two kept sides do not overlap there. That is why the region stops at B. The distances from O are 5, 5 and 6, so a circle of radius 6 about O contains the whole triangle.

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

A $(0, 5)$ ⁠: $x + 2y = 10$ meets the $y$ -axis. C $(0, 6)$ ⁠: $3x + 4y = 24$ meets the $y$ -axis.

B: from $x + 2y = 10$ ⁠, $x = 10 - 2y$ ⁠. Substitute in $3x + 4y = 24$ ⁠:
$\begin{aligned} 3(10 - 2y) + 4y &= 24 \\ 30 - 2y &= 24 \\ y &= 3, \end{aligned}$
and $x = 10 - 2(3) = 4$ ⁠. So B is $(4, 3)$ ⁠, and it obeys every constraint: $4 + 6 = 10 \ge 10$ ⁠, $12 + 12 = 24 \le 24$ ⁠, $4, 3 \ge 0$ ⁠.

The other crossing points are not in the region: $(10, 0)$ breaks (3), since $30 > 24$ ⁠; $(8, 0)$ breaks (2), since $8 < 10$ ⁠; and O breaks (2).

Substitution works well here because $x$ is easy to isolate from the first equation. Checking the rejected points shows why the region has only three corners.

Basics: a corner solves two equations

Work out $Z$ at each corner

Corner point	$Z = 200x + 500y$
A $(0, 5)$	$0 + 2500 = 2500$
B $(4, 3)$	$800 + 1500 = 2300$ ← smallest
C $(0, 6)$	$0 + 3000 = 3000$

By Theorem 1 the minimum, if it exists, is at a corner, so these three values are the candidates:

m = 2300

and

M = 3000

⁠.

Lesson: the corner point method

Conclude

The region is bounded, so by Theorem 2 the smallest value in the table is the minimum: minimum $Z = 2300$ at $(4, 3)$ .

The question asks only for the minimum. (The same table also gives the maximum, 3000 at $(0, 6)$ ⁠, because the region is bounded.) B wins because $y$ is the expensive variable in $Z$ (500 per unit against 200 for $x$ ⁠), and B has the smallest $y$ in the region.

Lesson: Examples 1 to 3, step by step

Result

The feasible region is the bounded triangle with corners $(0, 5)$ ⁠, $(4, 3)$ ⁠, $(0, 6)$ ⁠, and

\text{Minimum } Z = 2300 \text{ at } (4, 3).

(Textbook answer: minimum value of $Z$ is 2300 attained at the point $(4, 3)$ ⁠.)

Check it with numbers

An exact proof that nothing is below 2300: $200x + 500y = 350(x + 2y) - 50(3x + 4y)$ ⁠. On the region $x + 2y \ge 10$ and $3x + 4y \le 24$ ⁠, so $Z \ge 350(10) - 50(24) = 3500 - 1200 = 2300$ ⁠, with equality only where both lines meet, at $(4, 3)$ ✓.

The centre of the triangle, $\left(\frac43, \frac{14}{3}\right)$ ⁠, gives $Z = \frac{800}{3} + \frac{7000}{3} = 2600$ ⁠, between 2300 and 3000 ✓.

The region has just five whole-number points: $(0, 5)$ ⁠, $(0, 6)$ ⁠, $(1, 5)$ ⁠, $(2, 4)$ ⁠, $(4, 3)$ ⁠, with $Z = 2500, 3000, 2700, 2400, 2300$ ⁠; the smallest is at $(4, 3)$ ✓.

Common mistakes

Shading towards the origin for $x + 2y \ge 10$ ⁠. The test $0 \ge 10$ is false, so the origin's side is not kept.
Including O, $(8, 0)$ or $(10, 0)$ as corners. Each breaks one of the constraints.
Arithmetic at B. $3(10 - 2y) = 30 - 6y$ ⁠, not $30 - 2y$ ⁠. Then $30 - 6y + 4y = 24$ gives $y = 3$ ⁠; forgetting to multiply $2y$ by 3 gives the impossible $y = -3$ ⁠.
Giving the largest value. The question says minimise: the answer is 2300, not 3000.

What to take away

" $\ge$ " with a positive number on the right keeps the side away from the origin; " $\le$ " keeps the origin's side.
A bounded region gives both a maximum and a minimum from the same corner table.
Next, Example 3 asks for both, and two corners tie for the maximum.

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 2, 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 2: Minimise Z=200x+500yZ = 200x + 500yZ=200x+500y graphically

Basics you need

Solution

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

Draw the line 3x+4y=243x + 4y = 243x+4y=24 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 2: Minimise $Z = 200x + 500y$ graphically

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

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

Work out $Z$ at each corner