Linear Programming
Complete Formula Sheet & Shortcut Bible · BITSAT 2026
CrackIt
Core Terminology & LPP Structure
Objective Function (Z)
Z = ax + by
The linear function to be maximized or minimized. 'a' and 'b' are cost or profit coefficients.
Decision Variables
x, y
The quantities you need to determine. For BITSAT, it's usually two variables.
Constraints
a₁x + b₁y ≤ c₁
a₂x + b₂y ≤ c₂
...
a₂x + b₂y ≤ c₂
...
Linear inequalities representing limitations like resources, time, or demand. Can be ≤, ≥, or =.
Non-Negativity Constraints
x ≥ 0, y ≥ 0
Implicit in most real-world problems. Restricts the solution to the first quadrant.
Graphical Method: Finding the Feasible Region
Step 1: Plot Lines
Treat each inequality as an equation.
e.g., a₁x + b₁y ≤ c₁ → a₁x + b₁y = c₁
e.g., a₁x + b₁y ≤ c₁ → a₁x + b₁y = c₁
Find x and y intercepts to quickly draw the line. For x+y=5, intercepts are (5,0) and (0,5).
Step 2: Identify Region
Test a point, usually (0,0).
If a(0)+b(0) ≤ c is true, shade towards the origin.
If a(0)+b(0) ≤ c is true, shade towards the origin.
If the inequality is false for (0,0), shade the region on the other side of the line.
Feasible Region
The common intersection of all shaded regions.
This polygon contains all possible solutions to the LPP. It can be bounded (closed) or unbounded (open).
Finding the Optimal Solution
Corner Point Theorem
An optimal solution (max or min) to an LPP, if it exists, will occur at a corner point (vertex) of the feasible region.
This is the most fundamental theorem for solving LPPs graphically.
Procedure
1. Find all corner points (vertices).
2. Substitute each point into Z = ax + by.
3. The largest Z value is the maximum, smallest is the minimum.
2. Substitute each point into Z = ax + by.
3. The largest Z value is the maximum, smallest is the minimum.
Corner points are found by solving the system of equations of the intersecting lines that form them.
Multiple Optimal Solutions
Slope of Z = Slope of Constraint
-a/b = -a₁/b₁
-a/b = -a₁/b₁
If the slope of the objective function line is the same as a boundary line of the feasible region, all points on that line segment are optimal solutions.
BITSAT Shortcuts & Special Cases
Infeasible Solution
No Common Region
If the constraints are contradictory, there is no overlapping feasible region, and thus no solution.
Unbounded Solution
Feasible region is not enclosed.
A maximum or minimum may not exist. To check, plot ax+by > M (for max) or ax+by < m (for min). If this region overlaps with the feasible region, no optimal solution exists.
Redundant Constraint
A constraint that does not affect the feasible region.
Identifying and ignoring this can save calculation time, but be careful not to misidentify.
Speed Hacks for BITSAT
Quickly use the origin (0,0) test for shading. If a line passes through the origin, use another simple point like (1,0) or (0,1).
For MCQ, you can test the given options. Plug the (x,y) points from the options into the constraints first. If they are valid, then check which one optimizes Z.
Pay close attention to keywords: 'at least' means ≥, 'at most' means ≤, 'not more than' means ≤.
If all coefficients in Z are positive, the maximum value for a bounded region is usually at the corner point farthest from the origin.
Bounded vs. Unbounded Feasible Regions
| Property | Bounded Region | Unbounded Region |
|---|---|---|
Definition | A closed polygonal area. Can be enclosed in a circle. | An open area that extends infinitely in at least one direction. |
Optimal Solution | Both a maximum and a minimum value of Z are guaranteed to exist. | Either a maximum or a minimum (or both) may not exist. |
Solution Method | Find corner points and evaluate Z. The highest/lowest value is the answer. | Find corner points, find potential max/min. Then, perform an additional check to confirm existence. |
BITSAT Focus | Most common type. The solution is always at a corner point. | Less common, but appears as a trick question. Always check if the solution exists. |