Linear Programming

2.1 Core concepts

• Problems that seek to maximise (or minimise) profit (or cost) form a general class called optimisation problems; a special, important sub-class is the linear programming problem, illustrated through the furniture-dealer example of maximising profit from tables and chairs (NCERT §12.1, p. 394).
• Only the graphical method of solving LPPs is in scope here, although other methods (e.g. simplex) exist (NCERT §12.1, p. 394).
• Formulation begins by choosing decision variables x and y (e.g. number of tables and chairs), writing the non-negative constraints x ≥ 0, y ≥ 0, the resource constraints (investment 2500x + 500y ≤ 50000 i.e. 5x + y ≤ 100, storage x + y ≤ 60), and the objective function Z = 250x + 75y (NCERT §12.2.1, pp. 395–396).
• A Linear Programming Problem is one concerned with finding the optimal value (maximum or minimum) of a linear function (objective function) of several variables, subject to non-negativity of the variables and a set of linear inequalities (linear constraints); "linear" means all relations are linear, "programming" refers to the method of determining a plan of action (NCERT §12.2.1, p. 396).
• Objective function Z = ax + by (a, b constants) must be maximised or minimised; decision variables are x and y; constraints are the linear inequalities/equations on the variables, and x ≥ 0, y ≥ 0 are non-negative restrictions (NCERT §12.2.1, pp. 396).
• The common region determined by all the constraints (including non-negativity) is the feasible region (solution region); regions outside it are infeasible regions. Every point within and on the boundary of the feasible region is a feasible solution, while a point outside is an infeasible solution (NCERT §12.2.2, pp. 397).
• An optimal (feasible) solution is any point in the feasible region that gives the optimal (max or min) value of the objective function (NCERT §12.2.2, p. 398).
• Theorem 1: if Z = ax + by has an optimal value over a feasible region (convex polygon), this value must occur at a corner point (vertex) of the feasible region (NCERT §12.2.2, p. 398).
• Theorem 2: if the feasible region R is bounded (can be enclosed in a circle), then Z has both a maximum and a minimum on R, each occurring at a corner point (NCERT §12.2.2, p. 398). If R is unbounded, max/min may not exist, but if it exists, it must occur at a corner point.
• Corner Point Method (the procedure): (1) find the feasible region and its corner points by inspection or by solving the intersecting pairs of boundary equations; (2) evaluate Z at each corner — let M and m be the largest and smallest values; (3) if the region is bounded, M and m are the max and min of Z; (4) if the region is unbounded, M is the max only if the open half-plane ax + by > M has no point in common with the feasible region (else no max), and similarly m is the min only if ax + by < m has no point in common (else no min) (NCERT §12.2.2, pp. 399).
• Multiple optimal solutions: if two corner points give the same optimum (e.g. max Z = 180 at C(15,15) and D(0,20) for Z = 3x + 9y), then every point on the line segment joining them is also optimal (NCERT Example 3 + Remark, p. 401).
• Unbounded region — no optimum example: for Z = –50x + 20y over the region defined by 2x – y ≥ –5, 3x + y ≥ 3, 2x – 3y ≤ 12, x,y ≥ 0, the smallest corner value is –300 at (6,0), but the open half-plane –50x + 20y < –300 has points in common with the feasible region, so Z has no minimum (NCERT Example 4, pp. 402–403).
• Infeasible problem: for Z = 3x + 2y with x + y ≥ 8 and 3x + 5y ≤ 15, x,y ≥ 0, no point satisfies all constraints simultaneously — the feasible region is empty and the LPP has no feasible solution (NCERT Example 5, p. 403).
• General features noted: (i) the feasible region of an LPP is always a convex region; (ii) max/min occurs at a vertex; if two vertices give the same optimum, every point on the joining segment also does (NCERT §12.2.2 Remark, p. 403).
• Historical: the first LPP was formulated in 1941 by L. Kantorovich and F. L. Hitchcock (the transportation problem); G. Stigler (1945) formulated the diet problem; G. B. Dantzig (1947) gave the simplex method; Kantorovich and Koopmans got the 1975 Nobel Prize in economics for linear programming (NCERT Historical Note, pp. 404–405).

2.2 Definitions to memorise

2.3 Diagrams / processes to remember

• Fig 12.1, p. 397 — feasible region OABC for the furniture dealer with corner points O(0,0), A(20,0), B(10,50), C(0,60); maximum profit Z = 6250 at B(10,50).
• Fig 12.2, p. 400 — bounded feasible region OABC for Maximise Z = 4x + y under x + y ≤ 50, 3x + y ≤ 90; corners (0,0), (30,0), (20,30), (0,50); max Z = 120 at (30,0).
• Fig 12.3, p. 400 — bounded triangular region ABC for Minimise Z = 200x + 500y under x + 2y ≥ 10, 3x + 4y ≤ 24; corners (0,5), (4,3), (0,6); min Z = 2300 at (4,3).
• Fig 12.4, p. 401 — bounded region ABCD for Min/Max Z = 3x + 9y under x + 3y ≤ 60, x + y ≥ 10, x ≤ y; corners (0,10), (5,5), (15,15), (0,20); min 60 at (5,5); max 180 at both C(15,15) and D(0,20) — multiple optimal solutions on segment CD.
• Fig 12.5, p. 402 — unbounded region for Z = –50x + 20y under 2x – y ≥ –5, 3x + y ≥ 3, 2x – 3y ≤ 12; smallest corner value –300 at (6,0) is NOT the minimum because the half-plane –50x + 20y < –300 intersects the feasible region.
• Fig 12.6, p. 403 — illustration of an infeasible problem (Z = 3x + 2y under x + y ≥ 8, 3x + 5y ≤ 15) where no feasible region exists.
• Process — Corner Point Method (p. 399): (1) find feasible region and corner points; (2) evaluate Z at each corner; (3) if bounded, M = max, m = min; (4) if unbounded, verify by checking if open half-plane ax + by > M (or < m) intersects the feasible region.

2.5 Key formulas & theorems

2.6 Solved examples (NCERT-grounded)

Example A (NCERT furniture problem, §12.2, p. 398). Max Z = 250x + 75y subject to 5x + y ≤ 100, x + y ≤ 60, x, y ≥ 0.

Step 1 — find corners: O(0,0), A(20,0), B(10,50), C(0,60). Step 2 — evaluate Z: 0, 5000, 6250, 4500. Step 3 — choose max: Z = 6250 at B(10, 50).

Example B (NCERT Example 1, p. 400). Max Z = 4x + y under x + y ≤ 50, 3x + y ≤ 90, x, y ≥ 0.

Step 1 — corners: (0,0), (30,0), (20,30), (0,50). Step 2 — Z values: 0, 120, 110, 50. Step 3 — max: Z = 120 at (30, 0).

Example C (NCERT Example 2, p. 400). Min Z = 200x + 500y under x + 2y ≥ 10, 3x + 4y ≤ 24, x, y ≥ 0.

Step 1 — corners (triangular): (0,5), (4,3), (0,6). Step 2 — Z values: 2500, 2300, 3000. Step 3 — min: Z = 2300 at (4, 3).

Example D (NCERT Example 3, p. 401). Max Z = 3x + 9y under x + 3y ≤ 60, x + y ≥ 10, x ≤ y, x, y ≥ 0.

Step 1 — corners: A(0,10), B(5,5), C(15,15), D(0,20). Step 2 — Z values: 90, 60, 180, 180 (multiple optima at C and D). Step 3 — conclude: Max Z = 180 on the segment CD.

Example E (NCERT Example 5, p. 403). Min Z = 3x + 2y under x + y ≥ 8, 3x + 5y ≤ 15, x, y ≥ 0.

Step 1 — sketch: x + y ≥ 8 forces above the line y = 8 − x; 3x + 5y ≤ 15 forces below 3x + 5y = 15. Step 2 — check overlap: lines intersect at x = 25/2, y = −9/2 (negative), so no feasible point with x, y ≥ 0. Step 3 — conclude: infeasible LPP — no solution exists.

2.4 Common confusions / NTA trap points

• "Bounded" ≠ "closed". Boundedness means the region fits inside some circle. An unbounded region may still be closed and have corner points — but Theorem 2 does NOT guarantee a max/min there (NCERT §12.2.2, p. 398).
• Smallest corner value ≠ minimum on unbounded regions. NTA likes the trap of asking you to read off the smallest tabulated Z on an unbounded region without checking the half-plane condition (cf. Example 4, p. 402 where –300 is NOT the minimum).
• Feasible region is always convex and the optimum is at a vertex — distractors often suggest "centre" or "any interior point" can be optimal (NCERT Remark (i), p. 403).
• Multiple optimal solutions: if two vertices give equal optimum, the entire segment joining them is optimal — students sometimes pick "only at the midpoint" or "only at the two corners" (NCERT Remark, p. 401).
• Infeasible vs unbounded. An empty feasible region (Example 5) means NO feasible solution; an unbounded region MAY still have an optimum — students conflate the two (NCERT Example 5, p. 403).
• Non-negativity x ≥ 0, y ≥ 0 is a constraint of the LPP itself; distractors sometimes label it as the objective or as a separate "definition" — it is part of the linear constraints (NCERT §12.2.1, p. 395).