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

28 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

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

Practise this conceptself-check · 4 quick reps

The same idea in a real exam question:

MHT-CET · 2024 · 11th May Shift 2 · Q105Easy

Example 1 · Linear Programming · Corner-Point Method — Maximum and Minimum of the Objective Function

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

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 5 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

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

Practise this conceptself-check · 4 quick reps

The same idea in a real exam question:

MHT-CET · 2025 · 25 April Shift II · Q118Moderate

Example 2 · Linear Programming · Corner-Point Method — Maximum and Minimum of the Objective Function

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

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

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

Practise this conceptself-check · 4 quick reps

The same idea in a real exam question:

MHT-CET · 2025 · 22 April Shift I · Q148Moderate

Example 3 · Linear Programming · Corner-Point Method — Maximum and Minimum of the Objective Function

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

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

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

Practise this conceptself-check

The same idea in a real exam question:

MHT-CET · 2023 · 16th May Shift 2 · Q103Moderate

Example 4 · Linear Programming · Corner-Point Method — Maximum and Minimum of the Objective Function

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

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 3 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

Test yourself on Linear Programming

15 past MHT-CET questions from this chapter, timed at 27 minutes and marked the way the exam marks it. You see your score and every answer the moment you finish. Free to start.

Take the Linear Programming chapter test Drill all 28 questions

Related notes

Feasible Region — finding the vertices this page evaluates →