Chapter 12 · Linear Programming

Exercise 12.1 · Q5: Maximise $Z = 3x + 2y$ ⁠: the maximum 18 at $(4, 3)$

Exercise 12.1Corner Point Method, bounded region · Section 12.2.2

The question

Solve the following Linear Programming Problems graphically:

Maximise $Z = 3x + 2y$

subject to $x + 2y \le 10$ ⁠, $3x + y \le 15$ ⁠, $x, y \ge 0$ ⁠.

Exam answer

Draw the lines (graph):

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

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

At $(0, 0)$ ⁠: $0 \le 10$ and $0 \le 15$ 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, multiplying $3x + y = 15$ by 2 gives $6x + 2y = 30$ ⁠. Subtracting $x + 2y = 10$ gives $5x = 20$ ⁠, so $x = 4$ ⁠, $y = 3$ ⁠.

\begin{array}{c|c} \text{Corner} & Z = 3x + 2y \\ \hline O(0, 0) & 0 \\ A(5, 0) & 15 \\ B(4, 3) & 18 \leftarrow \text{max} \\ C(0, 5) & 10 \end{array}

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

$\therefore$ Maximum $Z = 18$ at $(4, 3)$ ⁠.

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

The one idea this problem is built on

Two " $\le$ " lines that cross in the first quadrant, together with $x, y \ge 0$ ⁠, cut out a closed quadrilateral. A linear $Z$ on a bounded region has its maximum at a corner, and here the best corner is the crossing point of the two lines, where both resources are used up.

Given, to find, and the plan

Given: $Z = 3x + 2y$ and the constraints $x + 2y \le 10$ ⁠, $3x + y \le 15$ ⁠, $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 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

3Corner points

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

4Bounded 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 + 2y = 10$ and choose its side

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

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

The boundary of the inequality is the line with " $=$ " in place of " $\le$ ", and its axis points are the quickest to find. One test point picks the whole side.

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

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

Test $(0, 0)$ in $3x + y \le 15$ ⁠: $0 \le 15$ is true, so again the origin's side is kept.

This line is much steeper: it meets the $x$ -axis at 5 (before 10) but the $y$ -axis at 15 (above 5). So the two lines cross inside the first quadrant.

Basics: one side of a line
Shade the feasible region

The constraints $x \ge 0$ ⁠, $y \ge 0$ keep the first quadrant. The part of it on the origin's side of both lines is the quadrilateral OABC:

The feasible region OABC of Exercise 12.1 Q5 (shaded). One unit along the $x$ -axis is drawn 1.8 times as long as one unit along the $y$ -axis. The corners are O(0, 0), A(5, 0), B(4, 3) and C(0, 5); the points $(10, 0)$ and $(0, 15)$ are outside the region.

OABC is bounded: each of A, B and C is exactly 5 from O (for B, $\sqrt{4^2 + 3^2} = 5$ ⁠), so a circle about O of radius 6 encloses it.

The feasible region is where all four kept sides overlap. Because it is bounded, the largest corner value will certainly be the maximum.

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

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

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

C $(0, 5)$ ⁠, where $x + 2y = 10$ meets the $y$ -axis. The point $(0, 15)$ breaks $x + 2y \le 10$ ⁠: $0 + 30 = 30 > 10$ ⁠.

B, where the two lines cross. Multiply $3x + y = 15$ by 2, so that $y$ has the coefficient 2 in both, and subtract $x + 2y = 10$ ⁠:
$\begin{aligned} 6x + 2y &= 30 \\ x + 2y &= 10 \\ 5x &= 20, \quad x = 4, \end{aligned}$
and $y = 15 - 3(4) = 3$ ⁠. So B is $(4, 3)$ ⁠, and it obeys every constraint: $4 + 6 = 10$ ⁠, $12 + 3 = 15$ ⁠, $4, 3 \ge 0$ ⁠.

The two lines and the two axes cross in six points; only the four that obey every constraint are corners. Multiplying first makes the $y$ -terms match, so subtracting removes $y$ ⁠.

Basics: a corner solves two equations

Work out $Z$ at each corner

Corner point	$Z = 3x + 2y$
O $(0, 0)$	$0$
A $(5, 0)$	$15 + 0 = 15$
B $(4, 3)$	$12 + 6 = 18$ ← largest
C $(0, 5)$	$0 + 10 = 10$

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

M = 18

⁠.

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 = 18$ at $(4, 3)$ .

Moving from A along the edge $3x + y = 15$ towards B, $x$ falls by 1 for every 3 that $y$ rises, so $Z$ changes by $-3 + 6 = +3$ ⁠: it improves up to B. Moving on from B along $x + 2y = 10$ towards C, $x$ falls by 2 for every 1 that $y$ rises, so $Z$ changes by $-6 + 2 = -4$ ⁠: it gets worse. So B is the top.

Lesson: Exercise 12.1, step by step · Basics: lines of equal Z

Result

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

\text{Maximum } Z = 18 \text{ at } (4, 3).

(Textbook answer: Maximum $Z = 18$ at $(4, 3)$ ⁠.)

Check it with numbers

A direct proof that nothing beats 18: $Z = 3x + 2y = \frac35(x + 2y) + \frac45(3x + y)$ ⁠, since $\frac35 + \frac{12}{5} = 3$ and $\frac65 + \frac45 = 2$ ⁠. On the region the brackets are at most 10 and 15, so $Z \le 6 + 12 = 18$ ⁠, with equality only where both lines meet, at $(4, 3)$ ✓.

Two other feasible points: $(3, 3)$ gives $Z = 9 + 6 = 15$ ⁠, and $(4, 2)$ gives $Z = 12 + 4 = 16$ ⁠; both are below 18 ✓.

A computer check of all 25 whole-number points of the region found the largest value 18, at $(4, 3)$ only ✓.

Common mistakes

Using $(10, 0)$ as a corner. It lies on $x + 2y = 10$ but breaks $3x + y \le 15$ ( $30 > 15$ ⁠); it would give the wrong "maximum" 30.
Using $(0, 15)$ as a corner. It breaks $x + 2y \le 10$ ⁠.
An elimination slip at B. Check B in both equations: $4 + 2(3) = 10$ and $3(4) + 3 = 15$ ⁠.
Leaving out O. The origin is a corner too; here it gives the minimum, 0.

What to take away

An axis point of one line is a corner only if it obeys the other constraints; reject it otherwise.
When the optimum is at the crossing point, both constraints are used in full.
Compare Exercise 12.1 Q3, where the crossing point has fractional coordinates.

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)
Answer	Result	NCERT answer key, Exercise 12.1 Q5
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 →

Exercise 12.1 · Q5: Maximise Z=3x+2yZ = 3x + 2yZ=3x+2y⁠: the maximum 18 at (4,3)(4, 3)(4,3)

Basics you need

Solution

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

Draw the line 3x+y=153x + y = 153x+y=15 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

Exercise 12.1 · Q5: Maximise $Z = 3x + 2y$ ⁠: the maximum 18 at $(4, 3)$

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

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

Work out $Z$ at each corner