Maharashtra State Board · Class 12 · Mathematics · Part I Chapter 7

Linear Programming — Formula Sheet

Board Formulas

12 formulas

1.Linear Inequation as a Half-plane
$a x + b y \leq c or a x + b y \geq c$
The line ax + by = c divides the plane into two half-planes; the solution set of the inequation is one of them, including the line.
2.Plotting the Boundary Line by Intercepts
$a x + b y = c passes through (\frac{c}{a}, 0) and (0, \frac{c}{b})$
Valid when a, b, c are all non-zero. If c = 0 the line passes through the origin — use another point such as (1, −a/b).
3.Origin Test
$a (0) + b (0) \leq c ⟺ 0 \leq c$
If the inequality is true at (0, 0), shade the side containing the origin; otherwise shade the other side. If the line passes through the origin, test a point like (1, 0).
4.Translating Word Conditions
$at most k : \leq k, at least k : \geq k, does not exceed k : \leq k$
Availability of a resource (hours, money, storage) gives '≤'. A minimum requirement (nutrients, demand) gives '≥'.
5.Mathematical Form of an LPP★
$Maximise / Minimise Z = c_{1} x + c_{2} y subject to a_{i 1} x + a_{i 2} y \leq b_{i} (or \geq b_{i}), x \geq 0, y \geq 0$
$x, y$ : Decision variables (quantities to be decided) · $Z$ : Objective function (profit, cost, …) · $c_{1}, c_{2}$ : Profit or cost per unit of x and y
Three parts: decision variables x, y; the linear objective function Z; and the linear constraints, including non-negativity.
6.Non-negativity Constraints
$x \geq 0, y \geq 0$
Quantities produced or bought cannot be negative, so the feasible region always lies in the first quadrant.
7.Feasible Region
$R = {(x, y) : all constraints and x \geq 0, y \geq 0 hold}$
The common region of all the half-planes. It is a convex set — bounded (a polygon) or unbounded. Each point of R is a feasible solution.
8.Corner Point from Two Boundary Lines
$a_{1} x + b_{1} y = c_{1}, a_{2} x + b_{2} y = c_{2} \Rightarrow x = \frac{c _{1} b _{2} - c _{2} b _{1}}{a _{1} b _{2} - a _{2} b _{1}}, y = \frac{a _{1} c _{2} - a _{2} c _{1}}{a _{1} b _{2} - a _{2} b _{1}}$
Cramer's rule for the intersection of two lines. Elimination is equally good — just do not estimate from the graph.
9.Corner Point Theorem★
$Z_{m a x} and Z_{m i n} (when they exist) occur at corner points of R$
For a bounded feasible region both the maximum and the minimum exist. Evaluate Z at every corner point and compare.
10.Multiple Optimal Solutions★
$Z (P) = Z (Q) = Z_{opt} \Rightarrow Z = Z_{opt} at tP + (1 - t) Q, 0 \leq t \leq 1$
Happens when the objective line is parallel to a boundary edge PQ of the region. Infinitely many optimal solutions.
11.Unbounded Feasible Region
$M = largest corner value; {(x, y) : c_{1} x + c_{2} y > M} \cap R = \emptyset \Rightarrow Z_{m a x} = M$
Otherwise Z has no maximum. For a minimum, take m = smallest corner value and check that c₁x + c₂y < m has no point in R.
12.Infeasible Problem
$R = \emptyset \Rightarrow no feasible solution$
If the constraints contradict each other (e.g. x + y ≤ 2 and x + y ≥ 5), there is no region to shade and no optimal solution.