Chapter 12 · Linear Programming

Exercise 12.1 · Q2: Minimise $Z = -3x + 4y$ on a bounded region

Exercise 12.1Corner Point Method, a negative coefficient · Section 12.2.2

The question

Solve the following Linear Programming Problems graphically:

Minimise $Z = -3x + 4y$

subject to $x + 2y \le 8$ ⁠, $3x + 2y \le 12$ ⁠, $x \ge 0$ ⁠, $y \ge 0$ ⁠.

Exam answer

Draw the lines (graph):

$x + 2y = 8$ through $(8, 0)$ and $(0, 4)$ ⁠;

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

At $(0, 0)$ ⁠: $0 \le 8$ and $0 \le 12$ 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 + 2y = 8$ from $3x + 2y = 12$ gives $2x = 4$ ⁠, so $x = 2$ ⁠, $y = 3$ ⁠.

\begin{array}{c|c} \text{Corner} & Z = -3x + 4y \\ \hline O(0, 0) & 0 \\ A(4, 0) & -12 \leftarrow \text{min} \\ B(2, 3) & 6 \\ C(0, 4) & 16 \end{array}

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

$\therefore$ Minimum $Z = -12$ at $(4, 0)$ ⁠.

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

The one idea this problem is built on

Two " $\le$ " constraints and $x, y \ge 0$ give a closed quadrilateral. On a bounded region a linear $Z$ has a minimum, at a corner. The only new point is the minus sign in $Z$ ⁠: a negative value such as $-12$ is smaller than $0$ ⁠, so the minimum here is a negative number.

Given, to find, and the plan

Given: $Z = -3x + 4y$ and the constraints $x + 2y \le 8$ ⁠, $3x + 2y \le 12$ ⁠, $x \ge 0$ ⁠, $y \ge 0$ ⁠.
To find: The minimum 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 minimum.

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

5Comparing negative numbers

On the number line $-12$ lies to the left of $0$ ⁠, so $-12 < 0 < 6 < 16$ ⁠: the "smallest" value is the most negative one.

Solution

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

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

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

The boundary of $x + 2y \le 8$ is the line $x + 2y = 8$ ⁠, and its two axis points are the quickest points to find. One test point tells us which whole side satisfies the inequality.

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

Put $y = 0$ ⁠: $3x = 12$ ⁠, so $x = 4$ ⁠. Put $x = 0$ ⁠: $2y = 12$ ⁠, so $y = 6$ ⁠. So the line joins $(4, 0)$ and $(0, 6)$ ⁠.

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

Same method. This line is steeper than the first, so it meets the $x$ -axis sooner (at 4 instead of 8) but the $y$ -axis higher (at 6 instead of 4). The two lines therefore 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 Q2 (shaded), drawn with equal scales. Its corners are O(0, 0), A(4, 0), B(2, 3) and C(0, 4); the points $(8, 0)$ and $(0, 6)$ are outside the region.

OABC is bounded: every corner is at most 4 from O (B is $\sqrt{2^2 + 3^2} = \sqrt{13}$ ⁠, about 3.6, from O), so a circle about O of radius 5 encloses it.

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

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

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

A $(4, 0)$ ⁠, where $3x + 2y = 12$ meets the $x$ -axis. The other line meets the $x$ -axis at $(8, 0)$ ⁠, but there $3(8) + 0 = 24 > 12$ ⁠, so $(8, 0)$ breaks $3x + 2y \le 12$ and is not a corner.

C $(0, 4)$ ⁠, where $x + 2y = 8$ meets the $y$ -axis. The point $(0, 6)$ breaks $x + 2y \le 8$ ⁠: $0 + 12 = 12 > 8$ ⁠.

B, where the two lines cross:
$\begin{aligned} (3x + 2y) - (x + 2y) &= 12 - 8 \\ 2x &= 4 \\ x &= 2, \end{aligned}$
and then $2y = 8 - 2 = 6$ ⁠, so $y = 3$ ⁠. So B is $(2, 3)$ ⁠, and it obeys every constraint: $2 + 6 = 8$ ⁠, $6 + 6 = 12$ ⁠, $2, 3 \ge 0$ ⁠.

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

Basics: a corner solves two equations

Work out $Z$ at each corner

Corner point	$Z = -3x + 4y$
O $(0, 0)$	$0$
A $(4, 0)$	$-12 + 0 = -12$ ← smallest
B $(2, 3)$	$-6 + 12 = 6$
C $(0, 4)$	$0 + 16 = 16$

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

m = -12

(and the largest, not asked for, is

M = 16

at C).

Lesson: the corner point method

Conclude

The region is bounded, so by Theorem 2 the smallest value in the table is the minimum of $Z$ ⁠: minimum $Z = -12$ at $(4, 0)$ .

To make $Z = -3x + 4y$ small we want $x$ large (it is subtracted) and $y$ small (it is added). The largest $x$ in the region is 4, and it is reached with $y = 0$ ⁠: exactly the corner A.

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

Result

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

\text{Minimum } Z = -12 \text{ at } (4, 0).

(Textbook answer: Minimum $Z = -12$ at $(4, 0)$ ⁠.)

Check it with numbers

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

Two other feasible points: $(3, 1)$ gives $Z = -9 + 4 = -5$ ⁠, and $(1, 1)$ gives $Z = -3 + 4 = 1$ ⁠; both are above $-12$ ✓.

A computer check of all 16 whole-number points of the region found the smallest value $-12$ ⁠, at $(4, 0)$ only ✓.

Common mistakes

Dropping the minus sign. At A, $Z = -3(4) + 0 = -12$ ⁠, not 12.
Calling 0 the minimum. O gives 0, but A gives $-12$ ⁠, and $-12 < 0$ ⁠. With a minus sign in $Z$ ⁠, the origin is often not the minimum.
Using $(8, 0)$ as a corner. It lies on $x + 2y = 8$ but breaks $3x + 2y \le 12$ ⁠.
Assuming the crossing point B is the answer. It gives 6; the table decides.

What to take away

A negative coefficient in $Z$ is handled the same way; just compare the values with their signs.
For a minimum, the answer is the smallest (most negative) value in the table when the region is bounded.
Compare Exercise 12.1 Q1 (one line) and Example 2 (a minimum with a " $\ge$ " constraint).

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 Q2
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 · Q2: Minimise Z=−3x+4yZ = -3x + 4yZ=−3x+4y on a bounded region

Basics you need

Solution

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

Draw the line 3x+2y=123x + 2y = 123x+2y=12 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 · Q2: Minimise $Z = -3x + 4y$ on a bounded region

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

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

Work out $Z$ at each corner