Chapter 12 · Linear Programming

Exercise 12.1 · Q3: Maximise $Z = 5x + 3y$ ⁠: the maximum at $\left(\frac{20}{19}, \frac{45}{19}\right)$

Exercise 12.1Corner Point Method, a corner with fractions · Section 12.2.2

The question

Solve the following Linear Programming Problems graphically:

Maximise $Z = 5x + 3y$

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

Exam answer

Draw the lines (graph):

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

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

At $(0, 0)$ ⁠: $0 \le 15$ and $0 \le 10$ 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, multiply $5x + 2y = 10$ by 5 and $3x + 5y = 15$ by 2, then subtract:

\begin{aligned} 25x + 10y &= 50 \\ 6x + 10y &= 30 \\ \Rightarrow\ 19x &= 20 \end{aligned}

So $x = \frac{20}{19}$ ⁠, and $2y = 10 - \frac{100}{19} = \frac{90}{19}$ ⁠, so $y = \frac{45}{19}$ ⁠.

At B, $Z = \frac{100}{19} + \frac{135}{19} = \frac{235}{19}$ ⁠.

\begin{array}{c|c} \text{Corner} & Z = 5x + 3y \\ \hline O(0, 0) & 0 \\ A(2, 0) & 10 \\ B\left(\frac{20}{19}, \frac{45}{19}\right) & \frac{235}{19} \leftarrow \text{max} \\ C(0, 3) & 9 \end{array}

Since $12 \times 19 = 228 < 235$ ⁠, $\frac{235}{19} > 12$ ⁠, so it is the largest value. The region is bounded, so it is the maximum of $Z$ ⁠.

$\therefore$ Maximum $Z = \dfrac{235}{19}$ at $\left(\dfrac{20}{19}, \dfrac{45}{19}\right)$ ⁠.

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

The one idea this problem is built on

The method is the same as always: draw, shade, find the corners, make the table. What is new is that the best corner is the crossing point of two lines whose coordinates are fractions. The variables $x$ and $y$ may take any real values here, so a fractional corner is a perfectly good answer.

Given, to find, and the plan

Given: $Z = 5x + 3y$ and the constraints $3x + 5y \le 15$ ⁠, $5x + 2y \le 10$ ⁠, $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, solving for the crossing point exactly. (5) Make the table of $Z$ ⁠. (6) Compare the values and 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

3Solving two equations by elimination

Multiply the equations so that one unknown has the same coefficient in both, then subtract. 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

5Comparing a fraction with a whole number

$\frac{235}{19} > 12$ because $12 = \frac{228}{19}$ and $235 > 228$ ⁠.

Solution

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

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

Test $(0, 0)$ in $3x + 5y \le 15$ ⁠: $0 \le 15$ 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 the axis points are the quickest points on it. One test point then picks the side.

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

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

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

This line is the steeper of the two: it meets the $x$ -axis sooner (at 2 instead of 5) and the $y$ -axis higher (at 5 instead of 3). So the two lines must 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 Q3 (shaded), drawn with equal scales. Its corners are O(0, 0), A(2, 0), B $\left(\frac{20}{19}, \frac{45}{19}\right)$ and C(0, 3); the points $(5, 0)$ and $(0, 5)$ are outside the region.

OABC is bounded: every corner is at most 3 from O, so a circle about O of radius 4 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 $(2, 0)$ ⁠, where $5x + 2y = 10$ meets the $x$ -axis. The other line meets the $x$ -axis at $(5, 0)$ ⁠, but there $5(5) + 0 = 25 > 10$ ⁠, so $(5, 0)$ breaks $5x + 2y \le 10$ and is not a corner.

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

B, where the two lines cross. Multiply $5x + 2y = 10$ by 5 and $3x + 5y = 15$ by 2, so that $y$ has the coefficient 10 in both, and subtract:
$\begin{aligned} 25x + 10y &= 50 \\ 6x + 10y &= 30 \\ 19x &= 20, \quad x = \frac{20}{19}. \end{aligned}$
Then from $5x + 2y = 10$ ⁠: $2y = 10 - \frac{100}{19} = \frac{190 - 100}{19} = \frac{90}{19}$ ⁠, so $y = \frac{45}{19}$ ⁠.

So B is $\left(\frac{20}{19}, \frac{45}{19}\right)$ ⁠. It lies on the other line too: $3 \cdot \frac{20}{19} + 5 \cdot \frac{45}{19} = \frac{60 + 225}{19} = \frac{285}{19} = 15$ ⁠, and both coordinates are positive.

The two lines and the two axes cross in six points; only the four that obey every constraint are corners. Here neither unknown has matching coefficients, so we first multiply to make the $y$ -coefficients equal. Putting B back into the second equation catches any arithmetic slip.

Basics: a corner solves two equations

Work out $Z$ at each corner

Corner point	$Z = 5x + 3y$
O $(0, 0)$	$0$
A $(2, 0)$	$10 + 0 = 10$
B $\left(\frac{20}{19}, \frac{45}{19}\right)$	$\frac{100}{19} + \frac{135}{19} = \frac{235}{19}$ ← largest
C $(0, 3)$	$0 + 9 = 9$

To compare: $12 \times 19 = 228$ ⁠, so $\frac{235}{19} = 12 + \frac{7}{19}$ ⁠, which is more than 12, and so more than 10 and 9.

By Theorem 1 the maximum is at a corner, so these four values are the only candidates. Keeping B's value as an exact fraction avoids rounding, and writing 12 as

\frac{228}{19}

makes the comparison exact.

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 = \frac{235}{19}$ at $\left(\frac{20}{19}, \frac{45}{19}\right)$ .

Moving from A along the edge $5x + 2y = 10$ towards B, $x$ falls by 2 for every 5 that $y$ rises, so $Z$ changes by $-10 + 15 = +5$ ⁠: it improves all the way to B. Moving on from B along $3x + 5y = 15$ towards C, $x$ falls by 5 for every 3 that $y$ rises, so $Z$ changes by $-25 + 9 = -16$ ⁠: 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)$ ⁠, $(2, 0)$ ⁠, $\left(\frac{20}{19}, \frac{45}{19}\right)$ and $(0, 3)$ ⁠, and

\begin{aligned} &\text{Maximum } Z = \frac{235}{19} \\ &\text{at } \left(\frac{20}{19}, \frac{45}{19}\right). \end{aligned}

(Textbook answer: Maximum $Z = \frac{235}{19}$ at $\left(\frac{20}{19}, \frac{45}{19}\right)$ ⁠.)

Check it with numbers

A direct proof that nothing beats $\frac{235}{19}$ ⁠: $Z = 5x + 3y = \frac{5}{19}(3x + 5y) + \frac{16}{19}(5x + 2y)$ ⁠, since $\frac{15 + 80}{19} = 5$ and $\frac{25 + 32}{19} = 3$ ⁠. On the region the brackets are at most 15 and 10, so $Z \le \frac{75}{19} + \frac{160}{19} = \frac{235}{19}$ ⁠, with equality only where both lines meet, at B ✓.

In decimals: B is about $(1.0526, 2.3684)$ and $\frac{235}{19} \approx 12.3684$ ⁠; indeed $5(1.0526) + 3(2.3684) = 5.2630 + 7.1052 = 12.3682$ ⁠, which matches up to the rounding of the coordinates ✓.

A computer check of the 8 whole-number points of the region found the largest value 11, at $(1, 2)$ ⁠, below $\frac{235}{19}$ ⁠: the maximum is at a point with fractional coordinates, which the problem allows ✓.

Common mistakes

Rounding B too early. With B as $(1.05, 2.37)$ you get $Z = 12.36$ ⁠, not the exact $\frac{235}{19}$ ⁠. Keep fractions.
Using $(5, 0)$ or $(0, 5)$ as a corner. Each lies on one line but breaks the other constraint.
An elimination slip. Multiplying to match the $y$ -coefficients gives $19x = 20$ ⁠; check B in both equations.
Thinking the answer must be whole numbers. Nothing in this problem asks for whole numbers; the maximum is at a fractional corner.

What to take away

Solve for the crossing point exactly and substitute it back into both equations.
Compare fractions exactly, for example by writing a whole number with the same denominator.
The same steps with whole-number corners: Exercise 12.1 Q2 and Example 1.

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; elimination	Step 4	Section 12.2.2, footnote to Theorem 1; Class X, Pair of Linear Equations (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 Q3
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 · Q3: Maximise Z=5x+3yZ = 5x + 3yZ=5x+3y⁠: the maximum at (2019,4519)\left(\frac{20}{19}, \frac{45}{19}\right)(1920​,1945​)

Basics you need

Solution

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

Draw the line 5x+2y=105x + 2y = 105x+2y=10 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 · Q3: Maximise $Z = 5x + 3y$ ⁠: the maximum at $\left(\frac{20}{19}, \frac{45}{19}\right)$

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

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

Work out $Z$ at each corner