Linear Programming and Simplex

This is the foundation of optimization: finding the best outcome (maximum profit, minimum cost, fastest route) when you have limited resources. It appears everywhere in the real world—logistics, scheduling, finance—and understanding it gives you the mental model for how machines make optimal decisions under constraints. It directly unlocks the study of Convex Optimization, Gradient Descent, and the KKT Conditions in your library. When you later see how neural networks are trained, you'll recognize the same idea: an objective to minimize, constrained by the model's structure. This topic teaches you the language of 'objective', 'constraints', and 'feasible region' that all of optimization speaks.

Every decision you make is a trade-off. You want to maximize something good (profit, happiness) or minimize something bad (cost, time), but you are always limited by constraints: time, money, materials, space. Linear programming is a precise way to answer: given these limits, what is the absolute best I can do? The 'linear' part means everything scales evenly. If one box of product A makes ₹100 profit, two boxes make ₹200, ten make ₹1000. There is no discount for bulk, no penalty for overproduction—just a straight line. The constraints work the same way: if it takes 1 hour to pack one box, it takes 2 for two, and with 8 hours you can pack at most 8. This is a simple sum. The power is that you can write down your goal and your limits as just multiplications and additions, and then a method like the simplex algorithm can find the single best answer from all the infinite possibilities. It does this by checking only the corners of your allowed region, not every point inside it. This is the key insight: the optimum always lies at a corner.

Imagine you are a farmer with a plot of land that has 10 acres. You can plant wheat or barley, or a mix. You have a budget of ₹20,000. Wheat costs ₹1,000 per acre to plant and needs 5 hours of labour per acre. Barley costs ₹2,000 per acre but needs only 2 hours of labour. You have 50 hours of labour available. Your goal is to maximize profit: wheat gives ₹3,000 profit per acre, barley gives ₹4,000. How much of each should you plant? Each combination of wheat and barley is a point on a graph: x-axis is wheat acres, y-axis is barley acres. The constraints—land, budget, and labour—each cut down your options, forming a shape on the graph. Land: W + B ≤ 10. Budget: 1000W + 2000B ≤ 20000. Labour: 5W + 2B ≤ 50. The set of all combinations that satisfy all three is a polygon with straight edges and sharp corners. The magic insight is that the best combination is always at one of these corners. It is never in the middle of the field. The simplex method starts at one corner (say, all wheat, W=10, B=0), checks the profit, then looks at the adjacent corner. If moving there increases profit, it moves. It keeps hopping from corner to corner along the edges until it reaches a corner where no move to an adjacent corner improves the profit. That is your optimum. The analogy starts to break down when you have more than three constraints because the graph becomes a multi-dimensional shape (a polytope), and 'corners' become harder to visualize, but the logic is the same—the algorithm still navigates along the edges of this higher-dimensional shape. It also stops working if your profit is not linear; if profit per acre started to fall after a certain number of acres, the objective would have curved sides, and the corners would not necessarily hold the answer.

Linear programming is the problem of optimizing (maximizing or minimizing) a linear objective function, subject to a set of linear equality and inequality constraints, where the optimal solution always lies at a vertex of the feasible region, known as a polytope.

You have no prior topics mastered yet, so this is your first step into the Optimization parent concept. This is the simplest and most foundational case: the objective and constraints are linear, and the problem is convex (meaning there is exactly one best answer, no local traps). This is why the simplex method is so effective here. When you later study Gradient Descent, you will see it is a different method for a different situation: the objective (like a neural network's loss) is not linear and not convex, so you cannot just walk along edges of a nice shape—you have to take steps in the direction that most reduces the loss. The idea of constraints from here will also connect to Lagrange Multipliers and KKT Conditions, which are advanced ways to handle constraints when they are non-linear. For now, know that this topic is the purest, most solvable form of optimization, and your library's source "Optimization: A Bootcamp for Machine Learning" will extend this to more complex algorithms.