MHT-CET Maths · Linear Programming

Formulation and Special Cases — Word Problems and Infinitely Many Optima

Turn a word problem into variables, an objective and inequalities in consistent units; and recognise the tie — when two adjacent corners give the same optimum, every point of the edge between them is optimal.

All Linear Programming notes MHT-CET Maths strategy

Why this matters

7 PYQs, none HARD. Two are formulation stems (a machine-time problem and a minimum-cost alloy), and five ask what the solution set of an optimisation LOOKS like — and the answer, every time, has been 'infinitely many points', because the objective was parallel to an edge of the region. That pattern has been set in 2023 (twice) and 2025 (three times); it is the one thing on this page worth memorising.

Concept 1 of 2

Formulating an LPP: Variables, Objective, Constraints in One Unit

Intuition

Name the decision variables (how many of each item), write profit or cost as the objective, and turn each resource limit into an inequality — after converting every quantity to the same unit. 'At most' is

\le

, 'at least' is

\ge

, and

x, y \ge 0

is always there.

Definition

Machine I: $10$ h $40$ min $= 640$ min; item A takes $20$ , B takes $15$ : $20x + 15y \le 640$ . Machine II: $8$ h $20$ min $= 500$ min; $5x + 8y \le 500$ . Profit $25x + 18y$ , maximise.
The option with $5x + 8y \ge 500$ reverses a capacity limit; the option with $20x + 5y \le 8$ mixed hours and minutes. Both are built from the two standard slips.
Minimum cost: copper $x$ g at ₹8, brass $y$ g at ₹5; chip weight at least $5$ g ( $x + y \ge 5$ ), brass at most $4$ ( $y \le 4$ ), copper at least $2$ ( $x \ge 2$ ). Minimise $8x + 5y$ : corners $(2,3)$ , $(2,4)$ , $(5,0)$ give $31, 36, 40$ ; minimum ₹31.
Formulation stems stop at the model; the optimisation stems continue into the corner-point method.

Standard form

\text{Maximise/Minimise } Z = px + qy \quad \text{subject to } a_ix + b_iy \le c_i \ (\text{or } \ge),\ x, y \ge 0

Worked example

A factory makes chairs (

x

) and tables (

y

). A chair needs

2

h of carpentry and

1

h of finishing; a table needs

3

h and

2

h. Carpentry is limited to

36

h a week and finishing to

20

h. Profits are ₹500 and ₹800. Formulate.

Practice this conceptself-check · 4 quick reps

From the bank · past-year question

Example 1Linear ProgrammingMODERATE

A manufacturing company produces two items, A and B. Each toy should be processed by two machines, I and II. Machine I can be operated for maximum 10 hours 40 minutes. It takes 20 minutes for an item of A and 15 minutes for B. Machine II can be operated for a total time at 8 hours 20 minutes. It takes 5 minutes for an item A and 8 minutes for B . The profit per item of

A

is ₹ 25 and per item of

B

is ₹ 18 . The formulation of an L.P.P. to maximize the profit (where

x

is number of items A and

y

is the number of item

B

) is

[Q146 · 26 April Shift II · 2025]

Mixing hours and minutes

20x + 15y \le 10\frac23

is the same constraint in hours and would be fine — but

20x + 5y \le 8

pairs minute coefficients with an hour limit. Convert everything to one unit before writing the inequality.

Drill 1 more on formulating an lpp: variables, objective, constraints in one unit

Concept 2 of 2

Infinitely Many Optima: The Objective Parallel to an Edge

Intuition

If the objective line

Z = ax + by

has the same slope as an edge of the region, the sliding line touches that whole edge last. Two adjacent corners then give the same optimal value, and every point between them is optimal.

Definition

$Z = x + y$ , $x + y \le 10$ , $5x + 3y \ge 15$ , $x \le 6$ : corners $(0,10)$ and $(6,4)$ both give $Z = 10$ because the edge $x + y = 10$ is parallel to the objective. Maximum at infinitely many points.
Minimise $Z = 30x + 20y$ , $x + y \le 8$ , $x + 2y \ge 4$ , $6x + 4y \ge 12$ : $(0,3)$ and $\left(1, \frac32\right)$ both give $60$ — the edge $6x + 4y = 12$ has slope $-\frac32$ , the same as $30x + 20y$ .
Minimise $Z = x + y$ , $x + y \ge 2$ , $x + 2y \le 8$ , $y \le 3$ : $(2,0)$ and $(0,2)$ tie at $2$ ; the region is bounded, so 'infinitely many points, bounded set'.
Test: compare the ratio $a : b$ of the objective with the ratio of the coefficients of each binding constraint; a match means a tie. $x + y$ vs $x + y \le 10$ : match.
'Unique', 'two distinct points' and 'does not exist' are the distractors; a tie is never at exactly two points.

Tie condition

Z = ax + by \ \parallel\ \text{edge } ax + by = c \ \Rightarrow\ \text{optimum on the whole edge}

Worked example

Maximise

Z = 2x + 4y

subject to

x + 2y \le 8

x \le 6

x, y \ge 0

. Describe the solution set.

Practice this conceptself-check · 4 quick reps

From the bank · past-year question

Example 2Linear ProgrammingMODERATE

The maximum value of

z=x+y

, subjected to

x+y\leq10

5x+3y\geq15

x\leq6

x,y\geq0

[Q126 · 9th May Shift 1 · 2023]

Answering 'two distinct points'

Two corners tie only because the whole edge between them ties. The optimum is the segment, so the honest count is infinite, never two.

Drill 4 more on infinitely many optima: the objective parallel to an edge

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 (2)

Formulating an LPP: Variables, Objective, Constraints in One Unit
Standard form
$\text{Maximise/Minimise } Z = px + qy \quad \text{subject to } a_ix + b_iy \le c_i \ (\text{or } \ge),\ x, y \ge 0$
Infinitely Many Optima: The Objective Parallel to an Edge
Tie condition
$Z = ax + by \ \parallel\ \text{edge } ax + by = c \ \Rightarrow\ \text{optimum on the whole edge}$

Watch out for (2)

Mixing hours and minutes
→ Formulating an LPP: Variables, Objective, Constraints in One Unit
Answering 'two distinct points'
→ Infinitely Many Optima: The Objective Parallel to an Edge

Drill every past-year question on this subtopic

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

Drill the 7 questions

Related notes

Corner-Point Method — the table the tie is read from →