Linear Programming notes: CBSE Class 12 Mathematics

1. What is a linear programming problem?

A linear programming problem (LPP) asks for the maximum or minimum of a linear objective function $Z = ax + by$ when the variables must satisfy linear constraints (inequalities) and the non-negativity constraints $x \ge 0$ , $y \ge 0$ .

The variables $x$ and $y$ are the decision variables: the quantities we choose (numbers of items, hours, kilograms).

The vocabulary of a linear programming problem.
Term	Meaning	Bakery example
Decision variables	Quantities we choose	$x$ sponge, $y$ fruit cakes
Objective function	Linear quantity to optimise	$Z = 60x + 80y$ (profit, ₹)
Constraints	Linear limits on resources	$2x + y \le 40$ , $2x + 3y \le 72$
Non-negativity	Variables cannot be negative	$x \ge 0$ , $y \ge 0$

Formulas

General form (two variables)
$\text{Optimise } Z = ax + by \text{ subject to } a_ix + b_iy \le c_i \text{ (or } \ge c_i\text{)},\ x \ge 0,\ y \ge 0$

Key terms

Decision variables: The unknown quantities to be chosen.
Objective function: The linear function $Z = ax + by$ to be maximised or minimised.
Constraints: Linear inequalities that every plan must satisfy.
Non-negativity constraints: $x \ge 0$ , $y \ge 0$ .

2. Formulating a problem

Steps: (1) define the decision variables with units; (2) write the objective function; (3) write one constraint for each limited resource or requirement; (4) add non-negativity.

Translations: "at most", "cannot exceed", "available" give $\le$ ; "at least", "must meet" give $\ge$ . Simplify each constraint by dividing by a common factor, and keep units the same on both sides.

Example (Kanpur bakery): $x$ sponge, $y$ fruit cakes; maximise $Z = 60x + 80y$ subject to $2x + y \le 40$ (flour), $2x + 3y \le 72$ (oven), $x, y \ge 0$ .

Turn each row of the table into one line of the problem.
Resource	Sponge cake	Fruit cake	Available
Flour (g)	$300$	$150$	$6000$
Oven time (min)	$20$	$30$	$720$
Profit (₹)	$60$	$80$	—

Formulas

Simplifying a constraint
$300x + 150y \le 6000 \iff 2x + y \le 40$

Key terms

Formulation: Writing a situation as an objective and constraints.

3. Graphing linear inequalities

The line $ax + by = c$ divides the plane into two half-planes. To decide which side satisfies $ax + by \le c$ , substitute a test point not on the line (the origin if possible): if the inequality is true there, that side is the solution set.

Draw the line using its intercepts. Points on the line belong to the region for $\le$ and $\ge$ .

$2x + 3y = 12$

Test the origin: $0 \le 12$ is true, so shade the origin side.

Formulas

Drawing the line
$\text{intercepts of } ax + by = c:\ \left(\dfrac ca, 0\right),\ \left(0, \dfrac cb\right)$

Key terms

Half-plane: One of the two parts into which a line divides the plane.
Test point: A point not on the line, substituted to choose the side.

4. Feasible region and corner points

The feasible region is the common part of all the half-planes (including $x, y \ge 0$ ). Its points are feasible solutions; points outside are infeasible. An optimal solution is a feasible point giving the best value of $Z$ .

A corner point is a vertex of the region: the meeting point of two boundary lines (or a line and an axis) that satisfies every constraint. Example: $x + y \le 8$ , $x + 2y \le 10$ has corners $(0, 0)$ , $(8, 0)$ , $(6, 2)$ , $(0, 5)$ .

A region is bounded if it can be enclosed in a circle, otherwise unbounded. It may also be empty.

$x + y = 8$
$x + 2y = 10$

Corners of the region: $(0, 0)$, $(8, 0)$, $(6, 2)$, $(0, 5)$.

Key terms

Feasible region: Set of points satisfying all constraints.
Corner point: Vertex of the feasible region.
Bounded region: A region that can be enclosed in a circle.

5. The corner-point method (bounded regions)

Corner Point Theorem. If the feasible region is bounded and non-empty, $Z = ax + by$ has a maximum and a minimum, both at corner points.

Method: draw the region, find all corners, evaluate $Z$ at each, and pick the largest (maximum) or smallest (minimum).

Example: maximise $Z = 3x + 5y$ on the region of section 4: values $0$ , $24$ , $28$ , $25$ , so the maximum is $28$ at $(6, 2)$ . Bakery: maximum ₹ $2000$ at $(12, 16)$ .

The corner-point method in six steps.

Formulas

Bounded region
$Z_{\max} = \max_{\text{corners}} (ax + by)$

Key terms

Corner Point Theorem: On a bounded region, the optimum of a linear objective is at a corner.

6. Unbounded regions: the half-plane test

On an unbounded region an optimum may not exist. If an optimum exists, it is at a corner.

Test for a minimum: let $m$ be the smallest corner value. If the open half-plane $ax + by < m$ has no point in common with the region, $m$ is the minimum; otherwise there is no minimum.

Test for a maximum: with $M$ the largest corner value, check $ax + by > M$ in the same way.

Example: on $x + y \ge 6$ , $x + 3y \ge 9$ , $x, y \ge 0$ , $Z = 2x + 3y$ has minimum $13.5$ at $(4.5, 1.5)$ , but $Z = x + y$ has no maximum.

$x + y = 6$
$x + 3y = 9$
$2x + 3y = 13.5$

The half-plane $2x + 3y < 13.5$ misses the region, so the minimum is $13.5$.

Formulas

Minimum on an unbounded region
$\{ax + by < m\} \cap R = \varnothing \Rightarrow Z_{\min} = m$

Key terms

Unbounded region: A region that cannot be enclosed in a circle.
Half-plane test: Check whether $ax + by < m$ (or $> M$ ) meets the region.

7. Special cases

Multiple optimal solutions: if $Z$ has the same best value at two adjacent corners, every point of the edge joining them is optimal (the objective lines are parallel to that edge). Example: $Z = 2x + 4y$ on the region of section 4 is $20$ at $(6, 2)$ and $(0, 5)$ .
Empty region (infeasible problem): constraints such as $x + y \le 3$ and $2x + 3y \ge 12$ (with $x, y \ge 0$ ) have no common point; there is no solution.
No optimum: on an unbounded region the objective may grow (or fall) without limit.

Not in the 2026–27 syllabus: classifying LPPs into named types (manufacturing, diet, transportation problems).

$x + y = 8$
$x + 2y = 10$
$2x + 4y = 20$

Objective parallel to an edge: every point of that edge is optimal.

Four situations every student should recognise.
Region	What can happen	How to tell
Bounded, non-empty	Max and min both exist, at corners	Compare corner values
Unbounded	An optimum may or may not exist	Half-plane test
Two corners tie	Infinitely many optimal points	Equal best values at adjacent corners
Empty	No feasible point, no solution	Constraints contradict

Key terms

Multiple optima: Infinitely many optimal points along an edge.
Infeasible problem: A problem whose feasible region is empty.

Exam tips

How marks are awarded

Formulation (2–3 marks): variables defined with units, objective, each constraint, non-negativity.
Graphical solution (3–5 marks): lines with intercepts, correct region, all corners with coordinates, corner table, conclusion in words.
Unbounded region: one mark is usually for the half-plane check (draw $Z = m$ and state the result).
Objective (1 mark): corner values, best corner, feasibility of a point, number of corners.

Common mistakes

Forgetting the non-negativity constraints, or a corner on an axis.
Shading the wrong side of a line (no test point).
Mixing units in a constraint (grams with kilograms, minutes with hours).
Listing a crossing point that breaks another constraint as a corner.
Accepting the best corner on an unbounded region without the half-plane test.
Naming one optimal point when two adjacent corners tie.
Writing the optimal value but not the plan (or the plan without the value).
Reading corners from a rough sketch instead of solving the equations.

1. What is a linear programming problem?

Formulas

Key terms

2. Formulating a problem

Formulas

Key terms

3. Graphing linear inequalities

Formulas

Key terms

4. Feasible region and corner points

Key terms

5. The corner-point method (bounded regions)

Formulas

Key terms

6. Unbounded regions: the half-plane test

Formulas

Key terms

7. Special cases

Key terms

Exam tips

Cookies