MHT-CET Maths · Linear Programming

Corner-Point Method — Maximum and Minimum of the Objective Function

A linear objective over a polygon takes its maximum and minimum at corners: list the vertices, evaluate Z at each, and read off the largest and smallest.

All Linear Programming notes MHT-CET Maths strategy

Why this matters

16 PYQs and not one HARD — the chapter's largest page and the cheapest two marks in the subject. Half the stems give the constraints, half give the figure with the corners labelled; either way the work is four or five substitutions. One 2024 figure stem carries an official key that its own working contradicts (19.8 marked where the corner gives 19.5); it is kept as printed and taught as a trap, and it is the only irregularity in sixteen questions.

Concept 1 of 4

The Corner-Point Theorem: Evaluate Z at Every Vertex

Intuition

Z = ax + by

is constant along parallel lines; sliding that line across a polygon, the last point it touches is a corner. So the optimum is at a vertex, and a bounded region needs only its vertices checked.

Definition

$Z = 3x + 5y$ with $3x + 2y \le 18$ , $x \le 4$ , $y \le 6$ : vertices $(0,0)$ , $(4,0)$ , $(4,3)$ , $(2,6)$ , $(0,6)$ ; $Z = 0, 12, 27, 36, 30$ . Maximum $36$ at $(2, 6)$ .
$Z = 10x + 6y$ with $x + y \le 12$ , $2x + y \le 20$ : corners $(0,0)$ , $(10,0)$ , $(8,4)$ , $(0,12)$ ; $Z = 0, 100, 104, 72$ : the maximum is at $(8, 4)$ , NOT at the corner with the biggest $x$ .
$Z = 7x + 8y$ , $x + y \le 20$ , $y \ge 5$ , $x \le 10$ : corners $(0,5)$ , $(10,5)$ , $(10,10)$ , $(0,20)$ ; $Z = 40, 110, 150, 160$ ; maximum $160$ .
The minimum is read from the same table: $Z = 4x + 6y$ over $(4,0)$ , $(0,4)$ , $(0,6)$ gives $16, 24, 36$ — maximum $36$ , minimum $16$ .
Always write the vertex beside its value; stems ask sometimes for the value, sometimes for the point.

Corner-point method

\max / \min\ Z = \max / \min_{\text{vertices } V}\ Z(V) \quad (\text{bounded region})

Worked example

Maximise

Z = 2x + 3y

subject to

x + y \le 6

x \le 4

y \le 5

x, y \ge 0

Practice this conceptself-check · 4 quick reps

From the bank · past-year question

Example 1Linear ProgrammingEASY

The maximum value of

Z = 3x+5y

subject to the constraints

3x+2y \leq 18

x \leq 4

y \leq 6

x,y \geq 0

, is

[Q105 · 11th May Shift 2 · 2024]

Stopping at the first good corner

(10, 0)

gives

100

and looks final;

(8, 4)

gives

104

. Every vertex is evaluated before the answer is read.

Drill 6 more on the corner-point theorem: evaluate z at every vertex

Concept 2 of 4

Corners That Are Not on the Axes: Solve the Pair of Lines

Intuition

When the best corner is where two slanted boundaries cross, solve the two equations simultaneously — the answer is often a fraction, and the option list has it as a fraction.

Definition

$Z = 6x + 3y$ , $x + y \le 5$ , $x + 2y \ge 4$ , $4x + y \le 12$ : $4x + y = 12$ with $x + y = 5$ gives $\left(\frac73, \frac83\right)$ , $Z = 22$ ; $4x + y = 12$ with $x + 2y = 4$ gives $\left(\frac{20}{7}, \frac47\right)$ , $Z = \frac{132}{7}$ ; axis corners $(0,2)$ , $(0,5)$ give $6$ , $15$ . Maximum $22$ .
$Z = 5x + 2y$ , $2x - y \ge 2$ , $x + 2y \le 8$ : corners $(1,0)$ , $(8,0)$ , $\left(\frac{12}{5}, \frac{14}{5}\right)$ ; $Z = 5, 40, 17.6$ ; maximum $40$ — the fractional corner is a distractor here, not the answer.
Solve by elimination: multiply to match a coefficient, subtract, back-substitute. Check the corner satisfies the remaining constraints before evaluating.
Keep values as fractions until the comparison; $\frac{132}{7} \approx 18.9 < 22$ is only obvious once both are numbers.

Corner from two boundaries

a_1x + b_1y = c_1,\ a_2x + b_2y = c_2 \ \Rightarrow\ (x, y) \text{ by elimination, then check the other constraints}

Worked example

Maximise

Z = 4x + 5y

subject to

2x + y \le 8

x + 2y \le 7

x, y \ge 0

Practice this conceptself-check · 4 quick reps

From the bank · past-year question

Example 2Linear ProgrammingMODERATE

In L.P.P., the maximum value of objective function

Z = 6x+ 3y

subject to constraints

x+y\leq 5,x+ 2y\geq 4,4x+y\leq 12,x,y\geq 0

[Q118 · 25 April Shift II · 2025]

Assuming the fractional corner is the answer

Option lists offer

\frac{132}{7}

and

\frac{122}{7}

beside

22

. A fraction is a corner value, not automatically the optimum; compare all of them.

Drill 1 more on corners that are not on the axes: solve the pair of lines

Concept 3 of 4

Minimising, Negative Coefficients, and Max Minus Min

Intuition

Nothing changes for a minimum: the same vertex table, read for the smallest value. A negative coefficient (

Z = 7x - 8y

) makes large

y

BAD, so the maximum can sit where

y

is smallest; and a 'difference of max and min' stem is two lookups in one table.

Definition

$Z = 7x - 8y$ , $x + y \le 20$ , $y \ge 5$ : corners $(0,20)$ , $(0,5)$ , $(15,5)$ ; $Z = -160, -40, 65$ . Max $-$ min $= 225 = 5k + 200 \Rightarrow k = 5$ .
Minimum from a figure: region between $y = 3$ and $y = x + 3$ , right of $2x + 3y = 12$ , left of $x = 4$ ; $Z = 3x + 5y$ at $(4,3)$ , $(4,7)$ , $\left(\frac35, \frac{18}{5}\right)$ , $\left(\frac32, 3\right)$ is $27, 47, 19.8, 19.5$ . The corner-point minimum is $19.5$ ; the official key marks $19.8$ even though its own working lists $19.5$ . The bank keeps the official letter with a note — know both numbers.
A minimum over an UNBOUNDED region exists when the objective's coefficients are non-negative (it cannot decrease without bound); a maximum then may not exist.
Cost stems ('minimum cost of the chip') are minimisations with the same method.

Max minus min

\max Z - \min Z = \max_V Z(V) - \min_V Z(V)

Worked example

Find the difference between the maximum and minimum of

Z = 5x - 3y

over

x + y \le 10

y \ge 2

x, y \ge 0

Practice this conceptself-check · 4 quick reps

From the bank · past-year question

Example 3Linear ProgrammingMODERATE

If the difference between the maximum and minimum values of the objective function

z = 7x- 8y

subject to the constraints

x+y\leqslant 20,y\geqslant 5,x,y\geqslant 0

5k + 200

, then the value of k is

[Q148 · 22 April Shift I · 2025]

Treating the largest coordinates as the maximum

With

Z = 7x - 8y

, the corner

(0, 20)

gives the MINIMUM. Substitute; never rank corners by position.

Drill 1 more on minimising, negative coefficients, and max minus min

Concept 4 of 4

When the Figure Labels the Corners: Read Coordinates, Then Substitute

Intuition

Many stems give the shaded region with its vertices marked. There is no plotting to do — read each vertex's coordinates from the axes, evaluate

Z

, compare.

Definition

Region $OCDB$ with $C(10,10)$ , $D(10,20)$ , $B(0,25)$ : $Z = 3x + 4y$ gives $0, 70, 110, 100$ ; maximum $110$ at $D$ .
Corners $O(0,0)$ , $A(6,0)$ , $B(6,4)$ , $C(3,7)$ , $D(0,5)$ with $Z = 4x + 3y$ : $0, 24, 36, 33, 15$ ; maximum $36$ at $B$ — set in two sittings with the same figure.
Corners $(3,0)$ , $(3,2)$ , $(2,3)$ , $(0,3)$ with $Z = 10x + 25y$ : $30, 80, 95, 75$ ; maximum $95$ at $(2, 3)$ .
A vertex not on a grid intersection must be COMPUTED from the two lines through it (previous concept); the figure only tells you which two lines.
Word-dressed figures (a scholarship $z = 550x + 300y$ over a quadrilateral) are the same read-and-substitute.

Figure stems

\text{read } V_i \text{ from the axes} \to Z(V_i) \to \text{compare}

Worked example

A figure shows a feasible region with vertices

O(0,0)

P(8,0)

Q(5,6)

R(0,7)

. Maximise

Z = 6x + 4y

Practice this conceptself-check

From the bank · past-year question

Example 4Linear ProgrammingMODERATE

The shaded area in the given figure is a solution set for some system of inequalities. The maximum value of the function

z = 4x + 3y

subject to linear constraints given by the system is

[Q103 · 16th May Shift 2 · 2023]

Reading a corner one grid unit off

C(3,7)

misread as

(3,8)

gives

36

again, by coincidence — but

(10,20)

misread as

(10,25)

gives

130

, which is on the list. Read each vertex against both axes.

Drill 4 more on when the figure labels the corners: read coordinates, then substitute

Summary — formulas & gotchas at a glance

A revision cheat-sheet for the formulas and gotchas above. Click any concept name to jump back to its full explanation.

Formulas (4)

The Corner-Point Theorem: Evaluate Z at Every Vertex
Corner-point method
$\max / \min\ Z = \max / \min_{\text{vertices } V}\ Z(V) \quad (\text{bounded region})$
Corners That Are Not on the Axes: Solve the Pair of Lines
Corner from two boundaries
$a_1x + b_1y = c_1,\ a_2x + b_2y = c_2 \ \Rightarrow\ (x, y) \text{ by elimination, then check the other constraints}$
Minimising, Negative Coefficients, and Max Minus Min
Max minus min
$\max Z - \min Z = \max_V Z(V) - \min_V Z(V)$
When the Figure Labels the Corners: Read Coordinates, Then Substitute
Figure stems
$\text{read } V_i \text{ from the axes} \to Z(V_i) \to \text{compare}$

Watch out for (4)

Stopping at the first good corner
→ The Corner-Point Theorem: Evaluate Z at Every Vertex
Assuming the fractional corner is the answer
→ Corners That Are Not on the Axes: Solve the Pair of Lines
Treating the largest coordinates as the maximum
→ Minimising, Negative Coefficients, and Max Minus Min
Reading a corner one grid unit off
→ When the Figure Labels the Corners: Read Coordinates, Then Substitute

Drill every past-year question on this subtopic

16 questions from the bank — paginated, with cart and Word-export support.

Drill the 16 questions

Drill every past-year question on this subtopic

Related notes