🎯 Key Points
- Fundamental theorem of LPP: if an optimal value exists, it ALWAYS occurs at a corner point (vertex) of the feasible region — never strictly inside the region
- Corner point method: shade feasible region → find all corner points (solve boundary equations pairwise) → evaluate Z at each → largest/smallest value is the max/min (for a BOUNDED region)
- For an UNBOUNDED region, a max or min found via corner points must be double-checked — it's only genuinely optimal if the open half-plane beyond that Z-value shares no point with the feasible region
- Three classic problem types: Manufacturing (maximize profit), Diet (minimize cost subject to nutrition minimums), Transportation (minimize shipping cost subject to supply/demand)
The feasible region (shaded) is bounded by the constraint lines; the fundamental theorem of LPP guarantees the optimal value of the objective function occurs at one of the corner points (O, A, B, C), so only these need to be checked, not the entire region.
What is a Linear Programming Problem (LPP)?
A linear programming problem deals with finding the optimal (maximum or minimum) value of a linear function, subject to certain conditions called constraints. It has three key parts:
- Decision variables: the unknown quantities to be determined, usually written as x and y. They are typically restricted to non-negative values (x ≥ 0, y ≥ 0) since they often represent real quantities like units produced.
- Objective function: the linear function Z = ax + by that is to be maximized or minimized, for example profit or cost.
- Constraints: a system of linear inequalities (and sometimes equations) that the decision variables must satisfy, representing limited resources such as time, material, or labour.
The Feasible Region
The set of all points (x, y) that satisfy every constraint simultaneously is called the feasible region. It is the common shaded region obtained by graphing all the constraint inequalities together, and every point inside or on the boundary of this region is called a feasible solution.
- A feasible region is bounded if it can be enclosed within a circle of finite radius, that is, it does not extend infinitely in any direction.
- A feasible region is unbounded if it extends infinitely in at least one direction. A maximum may not exist over an unbounded region even though a minimum does (or vice versa).
- If the feasible region is empty (no point satisfies all constraints at once), the LPP has no feasible solution.
Corner Points and the Optimal Solution
The corners (vertices) of the feasible region are called corner points. A fundamental theorem of linear programming states that if an optimal value of the objective function exists, it must occur at a corner point of the feasible region.
The Corner Point Method
- Graph all the constraints and shade the feasible region.
- Identify all the corner points of the feasible region (these are found by solving pairs of boundary equations simultaneously, or reading off axis intercepts).
- Evaluate the objective function Z = ax + by at every corner point.
- For a bounded region, the largest value of Z among the corner points is the maximum, and the smallest is the minimum.
- For an unbounded region, a maximum or minimum found this way must additionally be checked: if the corresponding open half-plane of Z beyond that value has no point in common with the feasible region, the value is genuinely optimal; otherwise no such optimal value exists.
Types of Linear Programming Problems
- Manufacturing problem: deciding the number of units of different products to manufacture using limited resources (labour hours, machine hours, raw material) so as to maximize profit.
- Diet problem: determining the amount of different foods to include in a diet so that all nutritional requirements (minimum vitamins, proteins, calories) are met while minimizing cost.
- Transportation problem: deciding the quantity of goods to transport from various sources (factories, warehouses) to various destinations (markets) so as to minimize total transportation cost while meeting supply and demand.
Mathematical Formulation of an LPP
Translating a word problem into an LPP follows four steps:
- Identify the decision variables — the quantities to be found, e.g. let x and y be the numbers of two products made.
- Write the objective function Z = ax + by to be maximized or minimized (profit, cost, etc.).
- Write the constraints as linear inequalities from the limited resources (labour, material, budget, nutritional minimums).
- Add the non-negativity restrictions x ≥ 0, y ≥ 0, since the variables usually represent real physical quantities.
Example: a factory makes chairs (x) and tables (y); each chair needs 2 hrs and each table 4 hrs of labour with 100 hrs available, giving 2x + 4y ≤ 100, plus x ≥ 0, y ≥ 0, and objective Z = (profit per chair)x + (profit per table)y.
Graphing Linear Inequalities and the Feasible Region
Each linear constraint corresponds to a half-plane. To graph ax + by ≤ c:
- Draw the boundary line ax + by = c (solid line, since ≤ and ≥ include the boundary).
- Pick a test point not on the line — the origin (0,0) is easiest when the line does not pass through it. Substitute it into the inequality.
- If the test point satisfies the inequality, shade its side of the line; otherwise shade the opposite side.
- The feasible region is the intersection (common overlap) of the half-planes of all the constraints together with x ≥ 0, y ≥ 0 (the first quadrant).
Worked Example: A Minimisation (Diet-type) Problem
Minimise Z = 3x + 5y subject to x + 3y ≥ 3, x + y ≥ 2, x ≥ 0, y ≥ 0.
The two ≥ constraints give an unbounded feasible region. Its corner points are (3,0) [from x + 3y = 3 with y = 0], (0,2) [from x + y = 2 with x = 0], and the intersection of x + 3y = 3 and x + y = 2, which is (1.5, 0.5).
Evaluate Z: (3,0) → 9; (1.5,0.5) → 4.5 + 2.5 = 7; (0,2) → 10. The smallest value is Z = 7 at (1.5, 0.5). Because the region is unbounded, we confirm the minimum by checking that the open half-plane 3x + 5y < 7 has no point in common with the feasible region — it does not, so Z = 7 is genuinely the minimum.
🚀 JEE Advanced Edge
Why checking ALL corner points (not just a few) is essential: Because Z=ax+by is linear, its value changes monotonically along any straight edge of the feasible region — meaning the maximum/minimum along an edge always occurs at one of its two endpoints (corners), never in the middle. This is precisely WHY the corner-point theorem works: optimizing a linear function over a polygon reduces to checking a finite set of points instead of an infinite region.
Degenerate/multiple optimal solutions: If the objective function line Z=ax+by happens to be PARALLEL to one edge of the feasible region, every point along that entire edge (not just the two corners) gives the same optimal Z value — this means the LPP has infinitely many optimal solutions, all corner points on that edge included, a subtlety often tested by asking "does this LPP have a unique optimal solution?"
Worked problem: Maximize Z = 3x+4y subject to x+y≤4, x≥0, y≥0. Approach: The feasible region is a triangle with corners (0,0), (4,0), (0,4) [from x+y=4 intersecting the axes]. Evaluate Z at each: (0,0)→0, (4,0)→12, (0,4)→16. Maximum Z=16 occurs at (0,4).
Worked Example: LP with Two Binding Constraints
Maximize Z = 5x + 4y subject to: 6x + 4y ≤ 24, x + 2y ≤ 6, x ≥ 0, y ≥ 0.
Find corner points: (0,0); (4,0) from 6x+4y=24 with y=0; (0,3) from x+2y=6 with x=0; intersection of both lines: 6x+4y=24 and x+2y=6 → from second: x=6−2y, sub: 6(6−2y)+4y=24 → 36−12y+4y=24 → y=1.5, x=3. Corner (3, 1.5).
Evaluate Z: (0,0)→0; (4,0)→20; (3,1.5)→15+6=21; (0,3)→12. Maximum Z = 21 at (3, 1.5). The maximum (or minimum) always occurs at a corner point — never inside the feasible region.