# Linear Programming and Simplex

Optimising a linear objective over linear constraints.

**Rests on:** Linear Transformations

*Mathematical Foundations · Optimization*


## Why learn this

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.


## The intuition

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


## An analogy

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.


## Definition

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


## How it connects

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.


## The mathematics

This concept rests on a branch of mathematics called linear algebra, because everything is built from straight lines: a linear objective is a flat plane, and linear constraints are flat planes that cut the space. The first operation you need is the dot product, which is just a way to combine two lists of numbers into a single number. Suppose you have a list of quantities (how many of each product) and a list of prices (profit per unit). The dot product multiplies each quantity by its price and adds them all up. For example, if you make 2 units of product A at ₹100 profit each, and 3 units of product B at ₹200 profit each, the total profit is (2 × 100) + (3 × 200) = 200 + 600 = 800. That's a dot product. The constraints are also dot products: you multiply the quantity of each product by how much of a resource it uses, and add them up, and that total must be less than or equal to what you have. The feasible region is the set of all quantity combinations that satisfy every constraint. Geometrically, each constraint is a line (or a flat plane in higher dimensions) that divides the space into allowed and not-allowed. The feasible region is the intersection of all allowed halves. The key theorem is that the objective function, being linear, is a flat plane itself. If you imagine tilting that plane upward in the direction of increasing profit, the highest point on the feasible region will always be at a corner, because the plane is flat and the region is a polyhedron. So instead of checking all infinite points, you only need to check the vertices. The simplex method is an algorithm that walks from vertex to vertex along the edges, always moving to a neighboring vertex that improves the objective, until no improvement is possible—that vertex is the global optimum.

Maximise (or minimise) c₁x₁ + c₂x₂ + … + cₙxₙ, subject to aᵢ₁x₁ + aᵢ₂x₂ + … + aᵢₙxₙ ≤ bᵢ for each constraint i (i = 1..m), and xⱼ ≥ 0 for each variable j (j = 1..n).


## A worked example

```
A small workshop makes two types of chairs: Wooden (W) and Metal (M). Profit on W is ₹300 each. Profit on M is ₹500 each. Two resources are needed: wood and labour. A W chair uses 2 units of wood and 2 hours of labour. An M chair uses 4 units of wood and 1 hour of labour. The workshop has 12 units of wood and 6 hours of labour available. How many W and M chairs should be made to maximise profit? We represent the decision variables as W (number of wooden chairs) and M (number of metal chairs).

Step 1: Maximise Profit = 300*W + 500*M   # This is the objective: total profit from all chairs, a dot product of quantities and per-unit profits.
Step 2: Constraint 1 (wood): 2*W + 4*M ≤ 12   # Each wooden chair uses 2 units of wood, each metal chair uses 4. Total wood used cannot exceed 12.
Step 3: Constraint 2 (labour): 2*W + 1*M ≤ 6   # Each wooden chair takes 2 hours, each metal chair 1 hour. Total labour cannot exceed 6 hours.
Step 4: W ≥ 0, M ≥ 0   # You cannot make a negative number of chairs.
Step 5: Find the corners of the feasible region: (0,0), (3,0), (0,1.5), and the intersection of the two constraint lines.   # The optimum will be at one of these vertices. We need to find the intersection point.
Step 6: Solve 2W+4M=12 and 2W+1M=6. Subtract: (2W+4M) - (2W+1M) = 12-6 => 3M = 6 => M = 2. Then 2W + 2 = 6 => 2W = 4 => W = 2.   # Solving the two equations simultaneously gives the corner (2,2).
Step 7: Profit at (0,0) = 0; at (3,0) = 900; at (0,1.5) = 750; at (2,2) = 1600.   # Evaluate the objective at each corner. The corner (0,1.5) is fractional, which is allowed in the model even if it is not a whole chair.
Step 8: Maximum profit is ₹1600, achieved at W=2, M=2.   # The optimum is at the intersection corner (2,2). This is the best we can do given the constraints.

Result: The optimal production plan is to make 2 wooden chairs and 2 metal chairs, yielding a maximum profit of ₹1600.
```


## From scratch, in Python

```python
def solve_simplex(c, A, b):
    # c: list of objective coefficients, e.g. [300, 500]
    # A: list of lists, each inner list is a constraint row, e.g. [[2,4],[2,1]]
    # b: list of right-hand side values, e.g. [12,6]

    m = len(A)      # number of constraints
    n = len(c)      # number of decision variables

    # Build the simplex tableau
    # Each row: constraint coefficients + slack variables + RHS
    tableau = []
    for i in range(m):
        # slack variables: a 1 in column i (own slack), 0 elsewhere
        slack = [1 if j == i else 0 for j in range(m)]
        tableau.append(A[i] + slack + [b[i]])
    # Objective row: negative c, then zeros for slacks, then 0 for RHS
    objective_row = [-val for val in c] + [0]*m + [0]
    tableau.append(objective_row)

    while True:
        # Find the entering variable: column with most negative entry in objective row
        pivot_col = min(range(n+m), key=lambda j: tableau[-1][j])
        if tableau[-1][pivot_col] >= 0:
            break  # optimal reached

        # Find the leaving variable: minimum ratio test (RHS / coefficient)
        ratios = []
        for i in range(m):
            if tableau[i][pivot_col] > 1e-6:
                ratios.append((tableau[i][-1] / tableau[i][pivot_col], i))
        if not ratios:
            return "unbounded"
        pivot_row = min(ratios)[1]

        # Pivot: divide the pivot row by the pivot element
        pivot_val = tableau[pivot_row][pivot_col]
        tableau[pivot_row] = [x / pivot_val for x in tableau[pivot_row]]

        # Eliminate the pivot column in all other rows
        for i in range(m+1):
            if i != pivot_row:
                factor = tableau[i][pivot_col]
                tableau[i] = [a - factor*b for a, b in zip(tableau[i], tableau[pivot_row])]

    # Extract solution: find columns with a single 1 and rest 0, read RHS
    solution = [0]*n
    for j in range(n):
        col = [tableau[i][j] for i in range(m)]
        if sum(1 for x in col if abs(x - 1) < 1e-6) == 1 and sum(1 for x in col if abs(x) > 1e-6) == 1:
            idx = next(i for i, x in enumerate(col) if abs(x - 1) < 1e-6)
            solution[j] = tableau[idx][-1]
    optimum = tableau[-1][-1]
    return solution, optimum

# Example from the worked problem
# Maximise 300*W + 500*M
# Subject to 2*W + 4*M <= 12, 2*W + 1*M <= 6
c = [300, 500]
A = [[2, 4], [2, 1]]
b = [12, 6]

solution, optimum = solve_simplex(c, A, b)
print("Solution:", solution)  # [2.0, 2.0]
print("Optimum:", optimum)    # 1600.0
```


## The same thing, with a framework

```python
import numpy as np
from scipy.optimize import linprog

# c is the objective coefficients. linprog MINIMISES, so negate to maximise
c = np.array([-300, -500])
# A_ub is the constraint matrix (each row is a constraint)
A_ub = np.array([[2, 4], [2, 1]])
# b_ub is the right-hand side values
b_ub = np.array([12, 6])

result = linprog(c, A_ub=A_ub, b_ub=b_ub, method='highs')

print("Solution:", result.x)   # [2. 2.]
print("Optimum:", -result.fun) # 1600.0
```


## What the code does

The `solve_simplex` function implements the simplex algorithm from scratch. First, it builds a 'tableau', which is just a grid of numbers (a list of lists in Python). The first `m` rows come from the constraints, with added 'slack variables' to turn ≤ into an equation. The last row is the objective, with negated coefficients because the algorithm works with a maximisation standard form. The main loop repeats: it finds the column with the most negative entry in the objective row—that variable is the one that can improve the profit the most. Then it applies the ratio test: for each constraint row, it divides the right-hand side by the coefficient in that column, and picks the smallest positive ratio to find which constraint is the tightest—that determines the row to pivot on. Pivoting is just row arithmetic: dividing the pivot row by the pivot element, and then subtracting multiples of that row from all others to make the pivot column zero everywhere except in the pivot row. When the objective row has no negative entries, the optimum is reached and the solution is read from the tableau. The Python code uses lists and loops: a list is an ordered collection of values, e.g., `[300, 500]`. A nested list, like `A = [[2,4],[2,1]]`, is a table of numbers. The `range()` function is used to loop a fixed number of times, and `min` with a key finds the smallest value according to a rule. The framework version, `scipy.optimize.linprog`, does exactly the same thing underneath, but it is pre-built, tested, and much faster for large problems.


## Common misconceptions

**The optimal solution is always a whole number** — The answer from a linear program will be a clean integer, like 2 wooden chairs and 3 metal chairs, so I can just round any fractional result.

The constraints are lines, and their intersection points are not always on integer grid marks. You often get solutions like 2.5 and 1.75. Rounding can give a solution that violates a constraint or is suboptimal. In fact: The mathematical solution can be fractional. If you need whole units, you must use a different, harder method called integer programming. In many real applications, fractional solutions are acceptable (e.g., litres of paint), but not for discrete items like chairs.

**The optimum is always at a single corner, not along an edge** — If I have two constraints, the best answer is always at a unique corner where the two lines cross.

If the objective line is parallel to one of the constraint edges, then any point on that edge gives the same objective value. The whole edge is optimal. In fact: A corner is still an optimal solution in that case, but it is not the only one. The simplex algorithm will stop at one of the two corners of that edge, which is fine, but you should be aware that another equally good answer exists somewhere along the edge.

**More constraints make the problem harder to solve** — Adding more limits means the simplex method has more work to do and the problem will take longer to solve.

Adding constraints shrinks the feasible region. Fewer corners means the simplex algorithm has fewer places to hop to, so it can converge faster. In fact: More constraints generally make the problem *easier* to solve because the search space shrinks. The difficulty comes from having many decision variables, which increases the number of possible corners exponentially.

**The simplex method is slow, so it is not used for large real-world problems** — I heard that simplex is exponential in the worst case, so real companies use other methods for anything big.

The exponential worst case is a mathematical curiosity. In practice, the simplex method is extremely fast on almost every real-world problem, and it has been the workhorse for decades. In fact: Simplex is excellent in practice. Its theoretical worst case is bad, but real problems do not look like that worst case. Moreover, modern solvers combine simplex with interior-point methods, which give polynomial worst-case guarantees, so you get both speed and reliability.


## In short

Linear programming solves the problem of allocating scarce resources to maximise a linear objective. The entire problem is built from simple arithmetic: multiplying variables by coefficients and adding them. The constraints define a feasible region, which is a polygon (in 2D) or a polytope (in higher dimensions). The central theorem is that the best answer is always at a *corner* of this region. The simplex method is a clever algorithm that walks from corner to corner along the edges, always moving to a neighbouring corner that improves the objective, until no improvement is possible. This concept is the foundation of optimisation, and its ideas of objectives, constraints, and corners echo through machine learning, even in the non-linear world of neural networks.


## Where this is used

Linear programming is a workhorse behind the scenes of many AI and data-driven systems. In **large language models**, it appears in fine-tuning, where you want to adjust the model's weights to maximise its performance on a new task while keeping it close to the original model to avoid 'catastrophic forgetting'. This is often cast as a constrained optimisation problem: maximise the new task's accuracy subject to the constraint that the weights do not drift too far from the original (measured by, e.g., a maximum L2 distance). Linear programming gives a simple version of this. In **small language models on devices**, the model is not retrained, but the scheduling of batch jobs, power management, and memory allocation across limited RAM and battery are all solved by linear programming. The goal is to swap in the right layers at the right time to keep response time low while staying within a power budget. In **retrieval-augmented generation**, linear programming is not used in the retrieval itself, but in the 're-ranking' stage. After fetching a pool of candidate documents, a linear model scores each one based on features (relevance to query, recency, authority of source). The optimisation is often to pick the top-k documents while maximising a total linear score, under the constraint of a maximum token budget for the context window—this is exactly a knapsack-style linear program. In **agentic systems** that plan and call tools, the agent often has to choose which tools to call in what order, given a budget of time and API calls. This can be formulated as a linear program: maximise the expected progress towards the goal, subject to constraints such as API call limits, time limits, and the precedence of certain actions. In **everyday applied machine learning**, linear programming is used in portfolio optimisation in finance (allocate capital to maximise expected return under risk limits), in supply chain logistics to decide how much to ship from each warehouse to each store to minimise cost, and in **forecasting** to allocate production to meet predicted demand under capacity constraints. For **fraud detection**, a scoring system may use a linear objective to decide whether to block a transaction, weighing the cost of a false alarm against the cost of a missed fraud. A developer writing this would not hand-code the algorithm; they would use a library like SciPy's `linprog` or commercial solvers like Gurobi or CPLEX. They would write a specification: a list of variables, an objective function as a vector of coefficients, and a matrix of constraint coefficients with their limits. When it goes wrong, it usually goes wrong because the model is too simple—an important constraint was left out, or the real-world relationship is not truly linear, so the answer is mathematically optimal but practically unusable. Debugging is not about the algorithm but about refining the equations.


---

Read this on the web: https://basavapurushottam.com/learn-ai/linear-programming-and-simplex
