Linear Programming

🎯 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)

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.

Feasible and Infeasible Solutions

Understanding which points are allowed is central to solving an LPP correctly.

• A feasible solution is any point (x, y) that satisfies all the constraints, including the non-negativity conditions x greater than or equal to 0 and y greater than or equal to 0.
• A point that violates even one constraint is an infeasible solution and lies outside the feasible region.
• An optimal (feasible) solution is a feasible point that also gives the maximum or minimum value of the objective function.
• If no point satisfies all constraints at once, the feasible region is empty and the LPP has no feasible solution.

Bounded and Unbounded Feasible Regions

Whether the feasible region is bounded decides if a maximum and a minimum are both guaranteed.

• A feasible region is bounded if it can be enclosed inside a circle of finite radius; both a maximum and a minimum of Z then exist and occur at corner points.
• A feasible region is unbounded if it extends infinitely in at least one direction.
• Over an unbounded region a maximum may fail to exist even though a minimum exists (or the other way round).
• For an unbounded region, a candidate optimal value must be verified by checking whether the open half-plane beyond it shares any point with the feasible region.

Multiple Optimal Solutions

An LPP need not have a single optimal point; sometimes an entire edge is optimal.

• If the objective line Z = ax + by is parallel to one of the constraint boundaries, the optimum can be attained at two adjacent corner points.
• In that case every point on the line segment joining those two corners is also optimal, giving infinitely many optimal solutions.
• The optimal value of Z is still unique even though the optimal point is not.
• This is detected when two corner points return the same best value of the objective function.

The Manufacturing (Maximisation) Problem

The manufacturing problem is a standard application where limited resources are shared between products to maximise profit.

• Let the decision variables be the numbers of units of each product to be made, taken as non-negative.
• The objective function is the total profit Z = (profit per unit of first product) times x + (profit per unit of second) times y, to be maximised.
• Constraints come from limited resources such as machine hours, labour hours or raw material available.
• Solving by the corner point method gives the production plan that yields the greatest profit within the resources.