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

14 PYQs, none HARD. Of the seven set from 2021 to 2025, two were formulation stems (a machine-time problem and a minimum-cost alloy), and five asked 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

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.

Practise this conceptself-check · 4 quick reps

The same idea in a real exam question:

MHT-CET · 2025 · 26 April Shift II · Q146Moderate

Example 1 · Linear Programming · Formulation and Special Cases — Word Problems and Infinitely Many Optima

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

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

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.

Practise this conceptself-check · 4 quick reps

The same idea in a real exam question:

MHT-CET · 2023 · 9th May Shift 1 · Q126Moderate

Example 2 · Linear Programming · Formulation and Special Cases — Word Problems and Infinitely Many Optima

The maximum value of

z=x+y

, subjected to

x+y\leq10

5x+3y\geq15

x\leq6

x,y\geq0

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

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 14 questions