Linear Programming

A Linear Programming Problem (LPP) is a mathematical technique for determining the maximum or minimum value of a linear function, subject to linear constraints. An LPP consists of three core structural elements:

• Decision Variables ($x, y$): The unknown quantities whose values are to be determined (e.g., units of product A and product B to manufacture). In real-world physical systems, these must satisfy non-negativity restrictions: $x \ge 0, y \ge 0$, confining the problem strictly to the first quadrant.
• Objective Function ($Z$): A linear function $Z = ax + by$ (where $a, b$ are constants) which is to be maximized (e.g., profit, revenue, efficiency) or minimized (e.g., cost, time, waste).
• Linear Constraints: System of linear inequalities or equations representing practical limitations on raw materials, labor hours, machine availability, or nutritional minimums, typically written as $a_1 x + b_1 y \le c_1$ or $a_2 x + b_2 y \ge c_2$.
• Feasible Solution: Any point $(x, y)$ that satisfies all the given constraints as well as the non-negative restrictions simultaneously.
• Optimal Solution: Any feasible solution that produces the maximum or minimum value of the objective function $Z$.

The graphical method solves two-variable LPPs by translating algebraic constraints into geometric regions on the coordinate plane:

1. Convert Inequalities to Boundary Lines: Replace each inequality symbol ($\le, \ge$) with an equal sign ($=$) to obtain the boundary lines. Find intercepts (set $x=0$ then $y=0$) to plot each line.
2. Determine Half-Planes: Test a representative point not lying on the line (standard test point: origin $(0, 0)$). If $(0, 0)$ satisfies the inequality, shade the half-plane containing the origin; otherwise, shade the opposing side.
3. Feasible Region ($R$): The common intersection of all shaded half-planes and the first quadrant ($x \ge 0, y \ge 0$).

The core mathematical theorem governing LPP is the Corner Point Theorem (Fundamental Theorem of Linear Programming):

In ISC Class 12 board examinations, LPP problems typically fall into three standard categories:

• Manufacturing Problems: A factory produces two items requiring specific hours on different machines with limited operating capacities. The goal is maximizing total profit $Z = c_1 x + c_2 y$ subject to $\le$ machine hour constraints.
• Diet Problems: A nutritionist blends two food types containing different amounts of vitamins/minerals to meet minimum daily health guidelines at the lowest possible cost. The constraints are usually of the form $\ge$ and the objective is minimizing cost.
• Allocation & Transportation Problems: Distributing commodities between sources and destinations to minimize shipping expenditure.

Board Examination Step-by-Step Algorithm: Always tabulate constraints clearly, define $x, y$ explicitly, show intercept calculations, label all corner points with coordinates on your graph, construct the evaluation table ($Z = ax + by$ for every vertex), and state the final answer with proper units.