Linear Programming — MHT-CET Maths

Formulas (3)

• 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}$$

Watch out for (3)

• Testing the origin on a line through it
  → The Half-Plane Test: Draw the Line, Test a Point, Keep One Side
• Calling every first-quadrant region bounded
  → Bounded, Unbounded or Empty: Classify Before You Optimise
• Keeping an intersection that a third constraint kills
  → Vertices of the Region: Intersect Pairs of Boundaries, Then Check the Rest

Formulas (3)

• 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}$$

Watch out for (3)

• Swapping the intercepts
  → The Boundary Line From Its Intercepts: x/a + y/b = 1
• Testing a point on the boundary
  → Fix ≥ or ≤ With One Point Inside the Shading
• 'Above the line' read as ≥ when a coefficient is negative
  → Four or Five Lines: Eliminate Options One Line at a Time

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

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