Chapter 12 · Linear Programming

Exercise 12.1 · Q1: Maximise $Z = 3x + 4y$ subject to $x + y \le 4$

Exercise 12.1Corner Point Method, bounded region · Section 12.2.2

The question

Solve the following Linear Programming Problems graphically:

Maximise $Z = 3x + 4y$

subject to the constraints: $x + y \le 4$ ⁠, $x \ge 0$ ⁠, $y \ge 0$ ⁠.

Exam answer

Draw the line (graph):

$x + y = 4$ through $(4, 0)$ and $(0, 4)$ ⁠.

At $(0, 0)$ ⁠: $0 \le 4$ is true, so shade the side of the line that contains the origin. With $x, y \ge 0$ ⁠, the feasible region is the triangle OAB (shaded). It is bounded.

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

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

$\therefore$ Maximum $Z = 16$ at $(0, 4)$ ⁠.

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

The one idea this problem is built on

The single constraint $x + y \le 4$ ⁠, together with $x, y \ge 0$ ⁠, cuts out a closed triangle. A linear $Z$ on a bounded region takes its largest value at a corner, so we only need $Z$ at the three corners of the triangle.

Given, to find, and the plan

Given: $Z = 3x + 4y$ and the constraints $x + y \le 4$ ⁠, $x \ge 0$ ⁠, $y \ge 0$ ⁠.
To find: The maximum value of $Z$ on the feasible region, and where it occurs.
Plan: (1) Draw $x + y = 4$ and choose its side. (2) Shade the feasible region and see that it is bounded. (3) List the corners. (4) Make the table of $Z$ ⁠. (5) 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 and its corners

The feasible region is where all the kept sides overlap; its corners are where two boundary lines meet. Basics: where the shadings overlap

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

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

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

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

Basics: where a line meets the axes · Basics: which side
Shade the feasible region

The constraints $x \ge 0$ and $y \ge 0$ keep the first quadrant. The part of it on the origin's side of $x + y = 4$ is the triangle OAB:

The feasible region OAB of Exercise 12.1 Q1 (shaded), drawn with equal scales. Its corners are O(0, 0), A(4, 0) and B(0, 4).

OAB is bounded: every corner is at most 4 from O, so a circle about O of radius 5 encloses it.

The feasible region is where all three kept sides overlap. It matters that it is bounded, because then the largest corner value is certainly the maximum (Theorem 2), with no further test.

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

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

A $(4, 0)$ ⁠, where $x + y = 4$ meets the $x$ -axis.

B $(0, 4)$ ⁠, where $x + y = 4$ meets the $y$ -axis.

Each obeys every constraint: $0 \le 4$ ⁠, $4 \le 4$ ⁠, $4 \le 4$ ⁠, and no coordinate is negative.

There are only three boundary lines ( $x + y = 4$ and the two axes), and each pair of them meets once, so there are exactly three crossing points, and all three are in the region.

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$

B $(0, 4)$ $0 + 16 = 16$ ← largest

By Theorem 1 the maximum, if it exists, is at a corner, so these three values are the only candidates. The largest is $M = 16$ ⁠.

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

This fits common sense. The constraint only limits the total $x + y$ to 4, and each unit of $y$ earns 4 while each unit of $x$ earns only 3. So the best plan is to put the whole total of 4 into $y$ ⁠, which is the corner B.

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

Corner point	$Z = 3x + 4y$
O $(0, 0)$	$0$
A $(4, 0)$	$12 + 0 = 12$
B $(0, 4)$	$0 + 16 = 16$ ← largest

Result

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

\text{Maximum } Z = 16 \text{ at } (0, 4).

(Textbook answer: Maximum $Z = 16$ at $(0, 4)$ ⁠.)

Check it with numbers

A direct proof that nothing beats 16: $Z = 3x + 4y = 4(x + y) - x$ ⁠. On the region $x + y \le 4$ and $x \ge 0$ ⁠, so $Z \le 16 - 0 = 16$ ⁠, with equality only when $x = 0$ and $x + y = 4$ ⁠, that is at $(0, 4)$ ✓.

Two other feasible points: $(1, 2)$ gives $Z = 3 + 8 = 11$ ⁠, and $(2, 2)$ gives $Z = 6 + 8 = 14$ ⁠; both are below 16 ✓.

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

Common mistakes

Shading away from the origin. Test $(0, 0)$ ⁠: $0 \le 4$ is true, so the origin's side is kept.
Forgetting $x, y \ge 0$ ⁠. Without them the side $x + y \le 4$ is a whole half-plane, which is unbounded; the two axes close it into a triangle.
Choosing A because 3 comes first. Only the table decides: A gives 12, B gives 16.
Leaving out O. The origin is a corner too; here it gives the smallest value, 0.

What to take away

One " $\le$ " constraint with a positive right side, together with $x, y \ge 0$ ⁠, gives a triangle with a corner at the origin.
With a constraint on the total $x + y$ ⁠, the maximum goes to the variable with the larger coefficient in $Z$ ⁠.
The same steps, with two lines and a crossing point, appear in 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	Step 1	Class XI, Linear Inequalities (Basics, Basics)
Feasible region: common region of all the constraints	Step 2	Section 12.2.2 (Basics)
Bounded: can be enclosed within a circle	Step 2	Section 12.2.2, footnote to Theorem 2 (Basics)
Corner point: where two boundary lines meet	Step 3	Section 12.2.2, footnote to Theorem 1 (Basics)
Theorem 1 and Theorem 2	Steps 4, 5	Section 12.2.2
Corner Point Method, step 3(i): bounded region	Step 5	Section 12.2.2 (Lesson)
Answer	Result	NCERT answer key, Exercise 12.1 Q1
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 · Q1: Maximise Z=3x+4yZ = 3x + 4yZ=3x+4y subject to x+y≤4x + y \le 4x+y≤4

Basics you need

Solution

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

Shade the feasible region

List the corner points

Work out ZZZ at each corner

Conclude

Every fact used, and where it comes from

Exercise 12.1 · Q1: Maximise $Z = 3x + 4y$ subject to $x + y \le 4$

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

Work out $Z$ at each corner