Chapter 12: Linear Programming

A linear programming problem (LPP) asks you to optimise a linear function , the objective , subject to a finite list of linear inequalities, the constraints. Despite the elementary-sounding word linear, this is a powerful framework. Real-world problems ranging from diet planning, factory output, transportation routing, and resource allocation reduce to linear programming. In Class XII you study only two-variable LPPs, which can be solved graphically.

The standard LPP looks like this. Find $x, y \ge 0$ that maximise (or minimise) $Z = ax + by$ subject to $\alpha_i x + \beta_i y \le \gamma_i$ for $i = 1, 2, \ldots, k$. The set of points $(x, y)$ satisfying all constraints is the feasible region , a convex polygon (possibly unbounded). The objective is a linear function on this region.

A central fact: a linear function on a convex polygon attains its maximum and minimum at the corner points (vertices) of the polygon. So the algorithm is mechanical: (i) sketch the feasible region; (ii) find all corners; (iii) evaluate $Z$ at each corner; (iv) pick the best. This is the corner-point method.

The chapter has two halves. The first is formulation: reading a word problem (about food, manufacturing, transportation) and translating it into mathematical constraints. The second is graphical solution: drawing inequalities, identifying corners, evaluating the objective. Practice both halves separately.

For board exams, expect a single big problem with full formulation and solution. For competitive contexts (although not the main JEE focus), linear programming appears in optimisation chapters of operations research and economics. The mental model , constraints carve out a feasible region; the optimum sits on the boundary , is broadly useful.

Prerequisites: graphing lines and inequalities in the $xy$-plane; some comfort with translating words into equations. No calculus required.

A word on terminology. Variables in an LPP are called decision variables. Constraints of the form $x, y \ge 0$ are called non-negativity constraints. The feasible region may be bounded (a closed polygon) or unbounded (extends to infinity in some direction); in the latter case the maximum (or minimum) may not exist.

What's inside

1. Formulation of LPPs , reading word problems and writing the math.
2. Graphical solution: feasible region and corner points , drawing inequalities, finding vertices.
3. The corner-point method , evaluating $Z$ at corners, choosing the optimum.
4. Bounded vs unbounded feasible regions , when an optimum exists.
5. Diet problems , a classic LPP type.
6. Manufacturing problems , another classic type.

Key results / Formula card

How to read this chapter

The procedural part is straightforward. The challenging part , and the part on which most marks are won and lost , is formulation. Read each word problem carefully. Identify the decision variables, the objective, and each constraint. Translate units consistently. Then the graphing and the corner-point evaluation become routine. Aim to formulate cleanly even before drawing anything.