Linear Programming and Simplex

You often face decisions where you want the best possible result—maximizing profit or minimizing cost—but you are bound by strict limits, such as a budget cap or available hours. Linear programming is the mathematical method for finding that single best option among thousands of possibilities while respecting every rule you have set. It is the engine behind efficient logistics, fair scheduling, and resource allocation in industries from banking to manufacturing. Understanding it gives you the tools to model real-world restrictions precisely and let a computer find the optimal path, rather than guessing or settling for a 'good enough' answer.

Imagine you run a small factory making two products: chairs (C) and tables (T). You have limited wood and labor. Each chair uses 2 units of wood and earns ₹50 profit. Each table uses 4 units of wood and earns ₹100 profit. You have 40 units of wood available. Your goal is to maximize total profit, which you can write as: Profit = 50C + 100T.

The constraint is simple: the wood used by chairs plus the wood used by tables cannot exceed 40. So, 2C + 4T ≤ 40. You also cannot make negative items, so C ≥ 0 and T ≥ 0.

If you plot this on a graph with Chairs on the x-axis and Tables on the y-axis, the line 2C + 4T = 40 divides the world into 'possible' and 'impossible' combinations. The 'feasible region' is the area of all combinations that do not use more than 40 units of wood. This shape is a triangle bounded by the axes and the wood line.

The simplex algorithm finds the best answer by exploiting a key geometric fact: because your profit formula is linear (straight lines), the highest possible profit will always occur at one of the sharp corners (vertices) of this feasible region, not somewhere in the middle of an edge or inside the area. In our example, the corners are:
1. Make 0 chairs, 0 tables (Profit = ₹0)
2. Make 20 chairs, 0 tables (Uses 40 wood; Profit = ₹1,000)
3. Make 0 chairs, 10 tables (Uses 40 wood; Profit = ₹1,000)

Wait, let's add a labor constraint to make it interesting. Suppose you also have only 30 hours of labor. Chairs take 1 hour; tables take 2 hours. Constraint: 1C + 2T ≤ 30.

Now the feasible region is a quadrilateral (a four-sided shape) with four corners:
A. (0,0) -> Profit ₹0
B. (30,0) -> 30 chairs, 0 tables. Wood used: 60 (Violates wood constraint! Not feasible).
*Let's recalculate the vertices properly for both constraints:*
Intersection of C=0 and 2C+4T=40 is T=10. Point (0,10). Profit = ₹1,000.
Intersection of T=0 and C+2T=30 is C=30. Point (30,0). Wood used: 60 (Violates wood constraint).
Intersection of 2C+4T=40 and C+2T=30?
From second eq: C = 30 - 2T. Substitute into first: 2(30-2T) + 4T = 40 -> 60 - 4T + 4T = 40 -> 60=40 (Impossible). The lines are parallel. Let's change wood cost for tables to 5 units to create an intersection.
New Wood Constraint: 2C + 5T ≤ 50.
Labor: C + 2T ≤ 30.
Corner A: (0,0). Profit = 0.
Corner B (Max T): If C=0, 5T≤50 -> T=10. Check labor: 2(10)=20 ≤ 30. OK. Point (0,10). Profit = 50(0)+100(10) = ₹1,000.
Corner C (Max C): If T=0, 2C≤50 -> C=25. Check labor: 1(25)=25 ≤ 30. OK. Point (25,0). Profit = 50(25) = ₹1,250.
Corner D (Intersection): Solve 2C + 5T = 50 and C + 2T = 30.
Multiply second by 2: 2C + 4T = 60. Subtract from first: (2C+5T) - (2C+4T) = 50 - 60 -> T = -10. (Impossible, negative). Let's try different numbers.
Wood: 2C + 3T ≤ 24. Labor: C + T ≤ 10.
Vertices:
1. (0,0): Profit 0.
2. Max T on Wood line: C=0 -> 3T=24 -> T=8. Point (0,8). Labor check: 0+8=8≤10. OK. Profit = 100*8 = ₹800.
3. Max C on Labor line: T=0 -> C=10. Wood check: 2(10)=20≤24. OK. Point (10,0). Profit = 50*10 = ₹500.
4. Intersection of 2C+3T=24 and C+T=10.
From second: C = 10 - T.
Sub into first: 2(10-T) + 3T = 24 -> 20 - 2T + 3T = 24 -> T = 4.
Then C = 6.
Point (6,4). Profit = 50(6) + 100(4) = 300 + 400 = ₹700.

Comparing corners: (0,8) gives ₹800. (10,0) gives ₹500. (6,4) gives ₹700. The best is (0,8), making 8 tables.

The simplex algorithm works by starting at one corner (say, 0,0), calculating profit, then checking the adjacent corners. If an adjacent corner has higher profit, it moves there. It repeats this until it finds a corner where no neighbor is better. In this case, it would hop from (0,0) to (0,8) or (10,0) and eventually settle on (0,8).

Think of a hiker trying to find the highest peak in a mountain range defined by fences. The 'feasible region' is the area inside the fences where you are allowed to walk. This area is a polygon with straight sides and sharp corners. Because the 'height' function (your objective) changes at a constant rate across the landscape, the very highest point cannot be in the middle of a flat plateau or along a sloping hillside; it must be exactly at one of the sharp corners where two fence lines meet. The simplex algorithm is like a hiker who only walks along the fence lines (edges) and stops only when they are at a corner from which no adjacent corner is higher. It ignores all the ground inside the fences because it knows, through linear geometry, that the peak is guaranteed to be at a vertex of the polygon defined by the constraints.

This analogy holds perfectly until your landscape is curved (non-linear) or your fence lines curve, in which case the highest point might indeed be in the middle of an edge or inside the region.

Linear programming is a method for achieving the best outcome in a mathematical model where the requirements are represented by linear relationships. The optimal solution always occurs at a vertex (a sharp corner) of the feasible region (the multi-sided shape formed by the intersection of all constraints).

This topic sits beside Convex Optimization, which is a broader category of problems where the set of allowed solutions forms a 'convex' shape (one that bulges outward like a sphere or square, ensuring any peak you find is the highest one), and Gradient Descent, a different algorithm used when the relationships are curved; instead of hopping between corners, Gradient Descent calculates the steepness at your current point and takes small steps in the direction of the steepest change.