CBSE · Class 12 · Mathematics · Chapter 12

Linear Programming — Formula Sheet

Board Formulas

13 formulas

1.Objective Function
$Z = a x + b y$
$Z$ : Objective function (profit, cost, ...) · $x, y$ : Decision variables (non-negative) · $a, b$ : Constants (for example profit per unit)
The linear function to be maximised or minimised. a and b are constants, and x and y are the decision variables.
2.Constraints
$a_{1} x + b_{1} y \leq c_{1} (or \geq c_{1}), \dots, x \geq 0, y \geq 0$
Linear inequalities that the variables must satisfy. The conditions x ≥ 0 and y ≥ 0 are the non-negativity constraints.
3.Feasible Region
$R = {(x, y) : all constraints, including x \geq 0, y \geq 0, hold}$
The common region of all the half-planes. Each point in it, including points on its boundary, is a feasible solution. Points outside it are infeasible.
4.Plotting a Constraint Line
$a x + b y = c meets the axes at (\frac{c}{a}, 0) and (0, \frac{c}{b})$
Join the two intercepts to draw the boundary line, for a, b, c ≠ 0. For a line through the origin, such as x = y, plot one more point.
5.Choosing the Side to Shade
$Put (0, 0) in a x + b y \leq c : 0 \leq c true \Rightarrow origin side$
If the inequality is true at the origin, shade the side containing the origin. If it is false, shade the other side. If the line passes through the origin, test another point, such as (1, 0).
6.Corner Point (Intersection of Two Lines)
$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}}$
Solution of a₁x + b₁y = c₁ and a₂x + b₂y = c₂. Elimination works just as well. Then check that the point satisfies all the other constraints.
7.Corner Point Theorem
$If Z has an optimal value on R, it occurs at a corner point of R$
This is why only the corner points need to be tested, not the infinitely many points inside the region.
8.Bounded Feasible Region★
$R bounded \Rightarrow Z_{m a x} = M, Z_{m i n} = m$
$M$ : Largest value of Z among the corner points · $m$ : Smallest value of Z among the corner points
M and m are the largest and smallest values of Z at the corner points. A bounded region can be enclosed in a circle, and both optimal values exist.
9.Unbounded Region: Maximum Test★
$M is the maximum \Leftrightarrow the open half-plane a x + b y > M has no point in common with R$
Draw the dotted line ax + by = M. If any part of R lies on the side where ax + by > M, then Z has NO maximum.
10.Unbounded Region: Minimum Test★
$m is the minimum \Leftrightarrow the open half-plane a x + b y < m has no point in common with R$
Draw the dotted line ax + by = m. If any part of R lies on the side where ax + by < m, then Z has NO minimum.
11.Multiple Optimal Solutions
$Z (P) = Z (Q) = Z^{*} \Rightarrow Z = Z^{*} at every point of segment P Q$
Happens when the objective line is parallel to an edge of the region. Report both corners and the whole segment.
12.No Feasible Region
$R = ϕ \Rightarrow no feasible solution, so no optimal value$
If the shaded half-planes have no common part, the problem has no solution. State this rather than forcing a corner table.
13.Corner Point Method (Steps)★
$Sketch R \to find corners \to evaluate Z \to compare (bounded) or test half-plane (unbounded)$
Follow these steps in order and write a one-line conclusion: 'Maximum Z = ... at (x, y)'.