Linear Programming — MHT-CET Maths Formulas and Traps

Feasible Region — Half-Plane Tests, Bounded, Unbounded and Empty

The Half-Plane Test: Draw the Line, Test a Point, Keep One Side

Half-plane test

ax + by \le c \text{ keeps the side where the test point satisfies it; the origin unless the line passes through it}

Bounded, Unbounded or Empty: Classify Before You Optimise

Empty-region proof

x + y \ge 10 \Rightarrow 2x + 3y \ge 2(x + y) \ge 20 > 18 \ \Rightarrow\ \text{no feasible point}

Vertices of the Region: Intersect Pairs of Boundaries, Then Check the Rest

Vertex test

\text{corner} = (\text{line}_i \cap \text{line}_j) \text{ that satisfies every other constraint}

Common traps

Testing the origin on a line through it

0 \le 0

is true for

y \le x

and tells you nothing. Use

(1, 0)

or

(0, 1)

, and remember that the distractor figures differ from the right one by exactly this side.

Calling every first-quadrant region bounded

x, y \ge 0

only closes two sides. Unless some constraint caps

x

AND some constraint caps

y

(or one caps

x + y

), the region runs to infinity.

Keeping an intersection that a third constraint kills

Two boundary lines meet at a point that lies OUTSIDE the region because another constraint excludes it. Every candidate corner is tested against all the constraints before it counts.

Reading Constraints Off a Shaded Region

Learn this subtopic in the notes

The Boundary Line From Its Intercepts: x/a + y/b = 1

Intercept form

\frac{x}{a} + \frac{y}{b} = 1 \iff bx + ay = ab

Fix ≥ or ≤ With One Point Inside the Shading

Direction test

P \text{ inside the shading:}\quad aP_x + bP_y < c \Rightarrow ax + by \le c,\qquad > c \Rightarrow ax + by \ge c

Four or Five Lines: Eliminate Options One Line at a Time

Elimination

\text{for each line: decide the side} \to \text{strike every option with the other sign} \to \text{stop when one option is left}

Common traps

Swapping the intercepts

3x + 4y = 12

has

x

-intercept

4

, not

3

. The coefficient of

x

is the

y

-intercept's number and vice versa; the option built on the swap is always offered.

Testing a point on the boundary

(10, 40)

is a good test point precisely because it is nowhere near a line. A point on a boundary gives equality and decides nothing.

'Above the line' read as ≥ when a coefficient is negative

Above

x - 3y = 3

is

x - 3y \le 3

. Evaluate the expression at a point; never convert above/below to a sign by reflex.

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

Learn this subtopic in the notes

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}

Common traps

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.

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.

Treating the largest coordinates as the maximum

With

Z = 7x - 8y

, the corner

(0, 20)

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

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.

Formulation and Special Cases — Word Problems and Infinitely Many Optima

Learn this subtopic in the notes

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}

Common traps

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.

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.

Linear Programming formulas

Feasible Region — Half-Plane Tests, Bounded, Unbounded and Empty

The Half-Plane Test: Draw the Line, Test a Point, Keep One Side

Bounded, Unbounded or Empty: Classify Before You Optimise

Vertices of the Region: Intersect Pairs of Boundaries, Then Check the Rest

Common traps

Reading Constraints Off a Shaded Region

The Boundary Line From Its Intercepts: x/a + y/b = 1

Fix ≥ or ≤ With One Point Inside the Shading

Four or Five Lines: Eliminate Options One Line at a Time

Common traps

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

The Corner-Point Theorem: Evaluate Z at Every Vertex

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

Minimising, Negative Coefficients, and Max Minus Min

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

Common traps

Formulation and Special Cases — Word Problems and Infinitely Many Optima

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

Infinitely Many Optima: The Objective Parallel to an Edge

Common traps

More MHT-CET Maths formula sheets