Linear Programming

💡 Why It Matters

Linear programming (LP) is the foundation of mathematical optimization. It powers resource allocation in supply chains, portfolio construction in finance, scheduling in operations research, and constraint satisfaction in AI planning. Any problem expressible as minimizing a linear objective subject to linear constraints is an LP — and solving LPs efficiently is one of the most impactful achievements in computational mathematics.

ℹ️ Historical Context

George Dantzig invented the simplex method in 1947. LP was used for logistics planning in WWII and later became central to industrial optimization. Today, LP solvers handle problems with millions of variables in seconds.

Linear Programming Standard Form

DfLinear Program

A linear program is an optimization problem of the form: minimize a linear objective function subject to linear inequality and equality constraints, with non-negative decision variables. The feasible region — the set of all $x$ satisfying all constraints — is a convex polytope.

LP Standard Form (Minimization)

\min \; c^T x \quad \text{subject to} \quad Ax \leq b, \quad x \geq 0

Here,

$c$ =Cost (objective) vector in ℝⁿ
$x$ =Decision variable vector in ℝⁿ
$A$ =m × n constraint coefficient matrix
$b$ =Right-hand side vector in ℝᵐ (b ≥ 0)

LP Standard Form (Maximization)

\max \; c^T x \quad \text{subject to} \quad Ax \leq b, \quad x \geq 0

Here,

$c$ =Profit (objective) vector
$A$ =Constraint matrix
$b$ =Resource availability vector

⚠️ Conversion to Standard Form

To convert any LP to standard minimization form:

Maximize → Minimize: Replace $\max c^Tx$ with $\min (-c)^Tx$ .
Equality constraints: Replace $a_i^Tx = b_i$ with $a_i^Tx \leq b_i$ and $a_i^Tx \geq b_i$ .
Unrestricted variables: Replace $x_j$ (free) with $x_j = x_j^+ - x_j^-$ where $x_j^+, x_j^- \geq 0$ .
≥ constraints: Multiply by $-1$ to convert to ≤ form.

ThFundamental Theorem of Linear Programming

If an LP has an optimal solution, it has one at a vertex (extreme point) of the feasible polytope. If the feasible region is unbounded and the objective is unbounded below, the LP is infeasible in the bounded direction. If the feasible region is empty, the LP is infeasible.

Geometry of Linear Programs

DfFeasible Region

The feasible region of an LP is the intersection of half-spaces defined by the constraints. It is a convex polytope (possibly unbounded). Since both the objective and constraints are linear, the optimum is always attained at a vertex or along a face of the polytope.

DfVertex (Extreme Point)

A point $x$ in a convex set $S$ is an extreme point (vertex) if it cannot be expressed as a convex combination of two distinct points in $S$ , i.e., there do not exist $y, z \in S$ with $y \neq z$ and $x = \lambda y + (1 - \lambda)z$ for $\lambda \in (0,1)$ .

📝Problem: Identifying Feasible Region

Find the feasible region and corner points for: maximize $3x_1 + 2x_2$ subject to $x_1 + x_2 \leq 4$ , $x_1 \leq 2$ , $x_2 \leq 3$ , $x_1, x_2 \geq 0$ .

💡Solution

The constraints define a polygon with vertices: $(0,0)$ , $(2,0)$ , $(2,2)$ , $(1,3)$ , $(0,3)$ . Evaluate the objective: $3(0)+2(0)=0$ , $3(2)+2(0)=6$ , $3(2)+2(2)=10$ , $3(1)+2(3)=9$ , $3(0)+2(3)=6$ . Maximum is $10$ at $(2,2)$ .

Simplex Method

DfSimplex Method

The simplex method is an iterative algorithm that moves along edges of the feasible polytope from one vertex to an adjacent vertex, improving the objective at each step. It terminates when no adjacent vertex improves the objective (optimality) or detects an unbounded direction.

DfBasic Feasible Solution (BFS)

A basic feasible solution corresponds to a vertex of the feasible region. It is obtained by setting $n - m$ variables (non-basic) to zero and solving the remaining $m$ equations for the $m$ basic variables. The BFS is feasible if all basic variables are non-negative.

ThSimplex Optimality Criterion

In a simplex tableau, the current BFS is optimal if all reduced costs $\bar{c}_j \geq 0$ (for minimization). If any $\bar{c}_j < 0$ , the corresponding non-basic variable can enter the basis to improve the objective.

ℹ️ Simplex Steps

Initialize: Find an initial BFS (possibly via artificial variables / Big-M / two-phase method).
Pricing: Select a non-basic variable with negative reduced cost to enter the basis.
Ratio Test: Determine the leaving variable by the minimum ratio $\theta = \min \{b_i / a_{ik} : a_{ik} > 0\}$ .
Pivot: Perform a pivot operation to update the tableau.
Terminate: When no entering variable exists (optimal) or no leaving variable exists (unbounded).

Simplex Ratio Test

\theta^* = \min_{i: a_{ik} > 0} \frac{b_i}{a_{ik}}

Here,

$a_{ik}$ =Pivot column entry for row i
$b_i$ =Current RHS value for row i
$\theta^*$ =Maximum step size before a basic variable hits zero

import numpy as np

def simplex(c, A, b):
    """Simplex method for: min c^T x, s.t. Ax <= b, x >= 0."""
    m, n = A.shape
    # Add slack variables
    M = np.hstack([A, np.eye(m)])
    c_aug = np.concatenate([c, np.zeros(m)])
    
    # Initial BFS: slack variables are basic
    basis = list(range(n, n + m))
    non_basis = list(range(n))
    
    while True:
        # Compute reduced costs
        B = M[:, basis]
        N = M[:, non_basis]
        c_B = c_aug[basis]
        c_N = c_aug[non_basis]
        
        y = np.linalg.solve(B.T, c_B)
        reduced_costs = c_N - N.T @ y
        
        if np.all(reduced_costs >= -1e-10):
            break  # Optimal
        
        # Enter: most negative reduced cost
        enter_idx = np.argmin(reduced_costs)
        enter_var = non_basis[enter_idx]
        
        # Direction vector
        d = np.linalg.solve(B, M[:, enter_var])
        
        if np.all(d <= 1e-10):
            raise ValueError("LP is unbounded")
        
        # Leave: minimum ratio test
        x_B = np.linalg.solve(B, b)
        ratios = np.where(d > 1e-10, x_B / d, np.inf)
        leave_idx = np.argmin(ratios)
        leave_var = basis[leave_idx]
        
        # Update basis
        basis[leave_idx] = enter_var
        non_basis[enter_idx] = leave_var
    
    x = np.zeros(n + m)
    x_B = np.linalg.solve(M[:, basis], b)
    for i, v in enumerate(basis):
        x[v] = x_B[i]
    
    return x[:n], c_aug @ x

# Example
c = np.array([-1, -2])
A = np.array([[1, 1], [1, -1], [-1, 1]])
b = np.array([4, 2, 2])
x_opt, obj = simplex(c, A, b)
print(f"Optimal: x={x_opt}, obj={-obj}")

Duality in LP

DfDual Problem

Every LP (the primal) has an associated dual LP. The dual provides bounds on the primal optimal value and has deep theoretical significance. For a primal minimization problem, the dual is a maximization problem.

Primal–Dual Pair

\text{Primal: } \min c^Tx \text{ s.t. } Ax \geq b, x \geq 0 \quad \Leftrightarrow \quad \text{Dual: } \max b^Ty \text{ s.t. } A^Ty \leq c, y \geq 0

Here,

$c^T x$ =Primal objective
$b^T y$ =Dual objective
$A$ =Constraint matrix (primal)
$A^T$ =Transpose (dual constraints)
$y$ =Dual variables (shadow prices)

ThWeak Duality Theorem

For any feasible primal solution $x$ and dual solution $y$ : $b^T y \leq c^T x$ . The dual objective always provides a lower bound on the primal objective (for minimization). Equality holds if and only if both solutions are optimal.

ThStrong Duality Theorem

If the primal has an optimal solution $x^*$ , then the dual has an optimal solution $y^*$ with $c^T x^* = b^T y^*$ . The optimal values are equal. This holds when both problems are feasible and bounded.

ℹ️ Complementary Slackness

At optimality, for each constraint pair:

If $y_i^* > 0$ , then the $i$ -th primal constraint is tight (equality holds): $a_i^T x^* = b_i$ .
If $a_i^T x^* > b_i$ (primal slack), then $y_i^* = 0$ .
If $x_j^* > 0$ , then the $j$ -th dual constraint is tight: $a_j^T y^* = c_j$ .
If $a_j^T y^* < c_j$ (dual slack), then $x_j^* = 0$ .

📝Problem: Construct the Dual

Given primal: minimize $5x_1 + 4x_2$ subject to $6x_1 + 4x_2 \geq 24$ , $x_1 + 2x_2 \geq 6$ , $x_1, x_2 \geq 0$ . Write the dual.

💡Solution

Dual: maximize $24y_1 + 6y_2$ subject to $6y_1 + y_2 \leq 5$ , $4y_1 + 2y_2 \leq 4$ , $y_1, y_2 \geq 0$ . The dual variables $y_1, y_2$ represent shadow prices for the two resource constraints.

Sensitivity Analysis

DfSensitivity Analysis

Sensitivity analysis studies how changes in the LP data (costs $c$ , right-hand side $b$ , or matrix $A$ ) affect the optimal solution. It answers: "How much can a parameter change before the current basis is no longer optimal?"

DfShadow Price

The shadow price (dual variable value) $y_i^*$ measures the rate of change of the optimal objective per unit increase in $b_i$ : $\frac{\partial z^*}{\partial b_i} = y_i^*$ . A shadow price of $5$ means increasing $b_i$ by $1$ improves the objective by $5$ .

DfReduced Cost

The reduced cost $\bar{c}_j$ of a non-basic variable $x_j$ measures the rate of change of the objective per unit increase of $x_j$ from zero: $\bar{c}_j = c_j - a_j^T y^*$ . A large positive reduced cost means forcing $x_j > 0$ is expensive.

⚠️ Range of Optimality

The current basis remains optimal as long as:

Each cost coefficient $c_j$ (for non-basic $x_j$ ) stays within its allowable range: $\bar{c}_j \geq 0$ .
Each RHS value $b_i$ stays within its allowable range so that $x_B = B^{-1}b \geq 0$ . Outside these ranges, a basis change (pivot) is required.

Shadow Price Interpretation

z^*(b + \Delta b) \approx z^*(b) + y^{*T} \Delta b

Here,

$z^*$ =Optimal objective value
$y^*$ =Optimal dual variables (shadow prices)
$\Delta b$ =Perturbation to RHS vector

Transportation Problem

DfTransportation Problem

The transportation problem is a special LP where goods are shipped from $m$ suppliers (with supply $s_i$ ) to $n$ destinations (with demand $d_j$ ) at minimum cost. The constraint matrix has a special network structure.

Transportation Formulation

\min \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij} \quad \text{s.t.} \quad \sum_{j} x_{ij} = s_i, \quad \sum_{i} x_{ij} = d_j, \quad x_{ij} \geq 0

Here,

$c_{ij}$ =Unit cost from supplier i to destination j
$x_{ij}$ =Quantity shipped from i to j
$s_i$ =Supply at supplier i
$d_j$ =Demand at destination j

ℹ️ Northwest Corner Rule

A feasible starting solution is found by the northwest corner rule: start at the top-left cell $(1,1)$ , allocate as much as possible, then move right (if demand unmet) or down (if supply remains). This provides an initial BFS for the transportation simplex method.

ThTransportation Problem Optimality

A feasible solution to the transportation problem is optimal if all dual variables $u_i + v_j - c_{ij} \leq 0$ for all cells (where $u_i$ and $v_j$ are the dual variables associated with supply and demand constraints). This is checked via the MODI (Modified Distribution) method.

from scipy.optimize import linprog
import numpy as np

def transportation_problem(costs, supply, demand):
    """Solve transportation problem using LP."""
    m, n = costs.shape
    # Decision variables: x_{ij} flattened as x[i*n + j]
    c = costs.flatten()
    
    # Supply constraints: sum over j for each i
    A_eq_supply = np.zeros((m, m * n))
    for i in range(m):
        A_eq_supply[i, i*n:(i+1)*n] = 1
    
    # Demand constraints: sum over i for each j
    A_eq_demand = np.zeros((n, m * n))
    for j in range(n):
        A_eq_demand[j, j::n] = 1
    
    A_eq = np.vstack([A_eq_supply, A_eq_demand])
    b_eq = np.concatenate([supply, demand])
    
    result = linprog(c, A_eq=A_eq, b_eq=b_eq, bounds=[(0, None)] * (m*n), method='highs')
    
    if result.success:
        return result.x.reshape(m, n), result.fun
    return None, None

costs = np.array([[8, 6, 10, 9], [9, 12, 13, 7], [14, 9, 16, 5]])
supply = np.array([35, 50, 40])
demand = np.array([45, 20, 30, 30])

shipment, total_cost = transportation_problem(costs, supply, demand)
print(f"Optimal shipments:\n{shipment}")
print(f"Total cost: {total_cost}")

Network Flow Problems

DfMinimum Cost Network Flow

The minimum cost network flow problem generalizes the transportation problem to arbitrary directed graphs. Flow is sent along edges with capacity limits and costs, subject to supply/demand at nodes and conservation constraints.

Network Flow Formulation

\min \sum_{(i,j) \in E} c_{ij} x_{ij} \quad \text{s.t.} \quad \sum_{j:(i,j) \in E} x_{ij} - \sum_{k:(k,i) \in E} x_{ki} = b_i, \quad 0 \leq x_{ij} \leq u_{ij}

Here,

$x_{ij}$ =Flow on edge (i,j)
$c_{ij}$ =Cost per unit flow on edge (i,j)
$u_{ij}$ =Capacity of edge (i,j)
$b_i$ =Supply (+) or demand (-) at node i

DfMaximum Flow Problem

The maximum flow problem finds the maximum total flow from a source $s$ to a sink $t$ in a directed graph with edge capacities. It is dual to the minimum cut problem.

ThMax-Flow Min-Cut Theorem

The maximum flow from $s$ to $t$ equals the minimum capacity of an $s$ - $t$ cut (a partition of vertices into two sets, one containing $s$ and one containing $t$ ). This is the foundational result of network optimization.

ℹ️ Applications of Network Flow

Shortest path (set $b_s = 1, b_t = -1$ , others $0$ ): find minimum cost route.
Maximum bipartite matching: model as network flow with unit capacities.
Project selection: choose profitable projects subject to dependency constraints.
Image segmentation: min-cut formulations for computer vision.

Integer Linear Programming

DfInteger Linear Program (ILP)

An integer linear program is an LP with the additional restriction that some or all decision variables must take integer values. When all variables are integer, it is called a pure ILP; when only some are integer, it is a mixed-integer LP (MILP).

Integer Linear Program

\min \; c^T x \quad \text{s.t.} \quad Ax \leq b, \quad x \geq 0, \quad x_j \in \mathbb{Z} \; \forall j \in \mathcal{I}

Here,

$x_j$ =Integer decision variable for j in index set I
$A$ =Constraint matrix (continuous entries allowed)
$\mathcal{I}$ =Index set of integer-constrained variables

⚠️ Complexity

ILP is NP-hard in general (unlike LP which is polynomial). The simplex method cannot be directly applied. Common approaches include:

Branch and bound: systematically enumerate subproblems with LP relaxations.
Cutting planes: add valid inequalities to tighten the LP relaxation.
Branch and cut: combine both strategies (used by modern solvers like Gurobi, CPLEX).

DfLP Relaxation

The LP relaxation of an ILP drops the integrality constraints, yielding a standard LP. The LP relaxation provides a lower bound (for minimization) on the ILP optimal value. The gap between the LP relaxation bound and the best known integer solution is called the integrality gap.

📝Problem: Mixed-Integer LP

A company produces two products. Product A requires 2 hours of machine time and 1 hour of labor per unit. Product B requires 1 hour of machine time and 3 hours of labor per unit. Machine time available: 8 hours. Labor available: 9 hours. Profit: A = $5, B =$ 4. At most 3 units of A can be produced (integer constraint). Maximize profit.

💡Solution

Formulate: maximize $5x_1 + 4x_2$ subject to $2x_1 + x_2 \leq 8$ , $x_1 + 3x_2 \leq 9$ , $x_1 \leq 3$ , $x_1, x_2 \geq 0$ , $x_1 \in \mathbb{Z}$ . Using branch and bound: LP relaxation gives $x_1 = 2.4, x_2 = 2.2$ , profit = $20.8$ . Rounding $x_1 = 3$ : $x_2 \leq 2$ , profit = $23$ . Check feasibility: $2(3)+2=8 \leq 8$ , $3+6=9 \leq 9$ . Optimal: $x_1 = 3, x_2 = 2$ , profit = $23$ .

Python Implementation

Using SciPy

from scipy.optimize import linprog
import numpy as np

# Example: Maximize z = 3x + 2y
# Subject to: x + y <= 4, x <= 2, y <= 3, x,y >= 0
c = [-3, -2]  # Negate for maximization
A_ub = [[1, 1], [1, 0], [0, 1]]
b_ub = [4, 2, 3]

result = linprog(c, A_ub=A_ub, b_ub=b_ub, method='highs')
print(f"Optimal x: {result.x}")
print(f"Maximum z: {-result.fun}")

# Equality constraints example
# min 5x + 4y, s.t. 6x + 4y = 24, x + 2y = 6, x,y >= 0
c2 = [5, 4]
A_eq = [[6, 4], [1, 2]]
b_eq = [24, 6]

result2 = linprog(c2, A_eq=A_eq, b_eq=b_eq, bounds=[(0, None), (0, None)])
print(f"Optimal: x={result2.x}, cost={result2.fun}")

Using PuLP

from pulp import *

# Define the problem
prob = LpProblem("Production_Planning", LpMaximize)

# Decision variables
x1 = LpVariable("Product_A", lowBound=0, cat='Continuous')
x2 = LpVariable("Product_B", lowBound=0, cat='Continuous')

# Objective function
prob += 3 * x1 + 2 * x2, "Total_Profit"

# Constraints
prob += x1 + x2 <= 4, "Resource_1"
prob += x1 <= 2, "Resource_2"
prob += x2 <= 3, "Resource_3"

# Solve
prob.solve(PULP_CBC_CMD(msg=0))

print(f"Status: {LpStatus[prob.status]}")
print(f"Product A = {x1.varValue}")
print(f"Product B = {x2.varValue}")
print(f"Total Profit = {value(prob.objective)}")

# Mixed-Integer example
prob2 = LpProblem("ILP_Example", LpMaximize)
x = LpVariable("x", lowBound=0, cat='Integer')
y = LpVariable("y", lowBound=0, cat='Continuous')

prob2 += 5 * x + 4 * y
prob2 += 2 * x + y <= 8
prob2 += x + 3 * y <= 9
prob2 += x <= 3

prob2.solve(PULP_CBC_CMD(msg=0))
print(f"ILP: x={x.varValue}, y={y.varValue}, obj={value(prob2.objective)}")

Applications in AI/ML

Resource Allocation

ℹ️ LP in Machine Learning

Linear programming appears in many ML contexts:

Feature selection: L1-regularized linear regression (Lasso) is equivalent to an LP.
Support vector machines: Linear SVMs with separable data reduce to LP.
Reinforcement learning: Linear programming formulations for MDPs.
Fairness constraints: Enforcing demographic parity can be formulated as LP.

import numpy as np
from scipy.optimize import linprog

# Lasso regression as LP: min ||y - Xw||_1
# Reformulated: min sum(t_i), s.t. y - Xw <= t, -(y - Xw) <= t
np.random.seed(42)
X = np.random.randn(50, 5)
true_w = np.array([1, 0, 0, 0, 0], dtype=float)
y = X @ true_w + 0.1 * np.random.randn(50)

n, p = X.shape
# Variables: [w (p), t (n)]
c = np.concatenate([np.zeros(p), np.ones(n)])

# Constraints: y - Xw <= t  =>  -Xw - t <= -y
#             -(y - Xw) <= t  =>  Xw - t <= y
A_ub = np.vstack([
    np.hstack([-X, -np.eye(n)]),
    np.hstack([X, -np.eye(n)])
])
b_ub = np.concatenate([-y, y])

result = linprog(c, A_ub=A_ub, b_ub=b_ub, method='highs')
w_lasso = result.x[:p]
print(f"Lasso coefficients: {w_lasso.round(3)}")

Portfolio Optimization

from scipy.optimize import linprog

# Linear risk model: minimize tracking error
# min sum |x_i - w_i| subject to budget and sector constraints
n_assets = 5
target = np.array([0.2, 0.2, 0.2, 0.2, 0.2])

# Variables: [x (n), s_plus (n), s_minus (n)]
c = np.concatenate([np.zeros(n_assets), np.ones(n_assets), np.ones(n_assets)])

# x - target = s+ - s-
# x - s+ + s- = target  (equality)
A_eq = np.hstack([
    np.eye(n_assets),
    -np.eye(n_assets),
    np.eye(n_assets)
])
b_eq = target

# Budget: sum(x) = 1
A_budget = np.hstack([np.ones((1, n_assets)), np.zeros((1, 2 * n_assets))])
b_budget = [1.0]

A_eq_full = np.vstack([A_eq, A_budget])
b_eq_full = np.concatenate([b_eq, b_budget])

result = linprog(c, A_eq=A_eq_full, b_eq=b_eq_full,
                 bounds=[(0, 1)] * n_assets + [(0, None)] * (2 * n_assets),
                 method='highs')
print(f"Optimal weights: {result.x[:n_assets].round(3)}")

Linear Programming in MDPs

DfLP Formulation of MDPs

A Markov Decision Process can be solved via LP: minimize $v(s_0)$ subject to $v(s) \geq r(s,a) + \gamma \sum_{s'} P(s'|s,a) v(s')$ for all state-action pairs $(s,a)$ . The dual variables correspond to the stationary distribution.

Common Mistakes

Mistake	Problem	Solution
Forgetting to convert max to min	`linprog` always minimizes	Negate objective: $\max c^Tx \to \min (-c)^Tx$
Wrong constraint direction	Feasible region is inverted	Check: $Ax \leq b$ means constraints are ≤
Ignoring non-negativity	Unbounded below	Always specify `bounds=[(0, None)]` for $x \geq 0$
Infeasible constraints	No solution exists	Check for contradictory constraints; use dual to diagnose
Not scaling variables	Numerical instability	Normalize variables to similar magnitudes
Confusing ≤ and ≥ in dual	Wrong dual formulation	Primal min with $Ax \geq b$ → Dual max with $A^Ty \leq c$
Ignoring integer requirements	Fractional solution accepted	Use `cat='Integer'` in PuLP or MILP solver
Wrong reduced cost sign	Misinterpreting optimality	For min: $\bar{c}_j \geq 0$ means optimal; for max: $\bar{c}_j \leq 0$
Not handling degeneracy	Cycling in simplex	Use Bland's rule or perturbation
Assuming global optimum for ILP	Local optima in branch-and-bound	Use global solvers (Gurobi, CPLEX) with tight bounds

Interview Questions

💡 Common Interview Questions

What is the geometric interpretation of an LP? — An LP optimizes a linear function over a convex polytope. The optimum is at a vertex.
What is duality and why does it matter? — Every LP has a dual; strong duality says optimal values are equal. The dual provides shadow prices.
When is the simplex method slow? — Worst-case exponential (Klee-Minty example), but typically polynomial in practice. Interior-point methods are provably polynomial.
What is the difference between LP and ILP? — ILP is NP-hard; LP is polynomial. ILP allows integer variables; LP requires only continuous.
How does sensitivity analysis help? — It tells you how the solution changes with parameter variations without re-solving.
What is complementary slackness? — At optimality, if a dual variable is positive, the corresponding primal constraint is tight, and vice versa.
When would you use interior-point vs simplex? — Interior-point for large-scale; simplex when you need warm-starts or sensitivity analysis.
How is LP used in ML? — Lasso regression, SVMs (linear case), MDP solving, fairness constraints, feature selection.
What is a degenerate LP? — A basic feasible solution where one or more basic variables are zero. Can cause cycling in simplex.
What is the transportation problem special structure? — The constraint matrix is totally unimodular, guaranteeing integer solutions from LP relaxation.

Practice Problems

📝Problem 1: Diet Problem

A dietician must plan meals meeting minimum requirements: 50g protein, 40g carbs, 30g fat. Food A provides 10g protein, 8g carbs, 5g fat per serving at $2. Food B provides 5g protein, 10g carbs, 8g fat per serving at$ 3. Minimize cost.

💡Solution

Let $x_1$ = servings of A, $x_2$ = servings of B. Minimize $2x_1 + 3x_2$ subject to $10x_1 + 5x_2 \geq 50$ , $8x_1 + 10x_2 \geq 40$ , $5x_1 + 8x_2 \geq 30$ , $x_1, x_2 \geq 0$ . Solving: $x_1 = 4, x_2 = 2$ (cost = $14). Verify: protein =$ 40+10=50 $✓, carbs =$ 32+20=52 $✓, fat =$ 20+16=36$ ✓.

📝Problem 2: Manufacturing

A factory produces tables and chairs. Each table requires 2 hours of cutting, 4 hours of assembly, 1 hour of finishing. Each chair requires 3 hours of cutting, 2 hours of assembly, 1 hour of finishing. Available: cutting = 120 hrs, assembly = 160 hrs, finishing = 50 hrs. Profit: table = $70, chair =$ 50. Maximize profit.

💡Solution

Maximize $70x + 50y$ subject to $2x + 3y \leq 120$ , $4x + 2y \leq 160$ , $x + y \leq 50$ , $x,y \geq 0$ . Corner points: $(0,0)=0$ , $(40,0)=2800$ , $(35,20)=3450$ , $(20,30)=2900$ , $(0,40)=2000$ . Maximum = $3450$ at $(35, 20)$ .

📝Problem 3: Dual Interpretation

Given primal: minimize $6x_1 + 3x_2$ subject to $4x_1 + x_2 \geq 12$ , $x_1 + x_2 \geq 6$ , $x_1, x_2 \geq 0$ . What do the dual variables represent? If $y_1^* = 1.5$ and $y_2^* = 0$ , what does this mean?

💡Solution

Dual: maximize $12y_1 + 6y_2$ subject to $4y_1 + y_2 \leq 6$ , $y_1 + y_2 \leq 3$ , $y_1, y_2 \geq 0$ . $y_1^* = 1.5$ means the first constraint is binding: increasing its RHS from 12 to 13 would improve the objective by 1.5. $y_2^* = 0$ means the second constraint is slack — relaxing it doesn't help.

📝Problem 4: Network Flow

Find the maximum flow from node 1 to node 4 in a network: (1→2: cap 10), (1→3: cap 8), (2→3: cap 5), (2→4: cap 7), (3→4: cap 10).

💡Solution

By augmenting path method: Path 1→2→4: flow 7 (capacity bottleneck = 7). Path 1→3→4: flow 8 (capacity bottleneck = 8). Path 1→2→3→4: remaining capacity on 1→2 = 3, 2→3 = 5, 3→4 = 2 (remaining after 8). Flow = 2. Total max flow = 7 + 8 + 2 = 17. Verify min cut: cut {1} vs {2,3,4}: capacity = 10+8 = 18. Cut {1,2} vs {3,4}: 5+7 = 12. Cut {1,3} vs {2,4}: 10+10 = 20. Cut {1,2,3} vs {4}: 7+10 = 17. Min cut = 17 = max flow ✓.

📝Problem 5: Integer Programming

A logistics company must decide which of 5 warehouses to open. Opening warehouse $i$ costs $f_i$ . Each warehouse can serve certain regions at cost $c_{ij}$ . Demand in region $j$ is $d_j$ . Formulate as MILP.

💡Solution

Binary variables $y_i \in \{0,1\}$ : 1 if warehouse $i$ is open. Flow variables $x_{ij} \geq 0$ : amount shipped from $i$ to $j$ . Minimize $\sum_i f_i y_i + \sum_{i,j} c_{ij} x_{ij}$ subject to $\sum_i x_{ij} = d_j$ (demand), $\sum_j x_{ij} \leq M_i y_i$ (capacity link), $y_i \in \{0,1\}$ , $x_{ij} \geq 0$ . The big-M constraint ensures flow only from open warehouses.

Quick Reference

📋Linear Programming Quick Reference

Standard Form: $\min c^T x$ s.t. $Ax \leq b$ , $x \geq 0$ .
Dual Form: Primal $\min c^T x$ , $Ax \geq b$ ↔ Dual $\max b^T y$ , $A^T y \leq c$ , $y \geq 0$ .
Strong Duality: $c^T x^* = b^T y^*$ at optimality.
Complementary Slackness: $y_i^* > 0 \Rightarrow a_i^T x^* = b_i$ and $x_j^* > 0 \Rightarrow a_j^T y^* = c_j$ .
Shadow Price: $y_i^* = \partial z^* / \partial b_i$ — marginal value of resource $i$ .
Simplex: Moves along vertices; polynomial in practice, exponential worst-case.
Interior Point: Polynomial $O(n^{3.5} L)$ ; no vertex information.
ILP: NP-hard; use branch-and-cut (Gurobi, CPLEX).
Transportation: Special LP with totally unimodular matrix; LP relaxation gives integer solutions.
Network Flow: Min-cost flow generalizes transportation; max-flow = min-cut.
Python: scipy.optimize.linprog (simplex/highs), pulp (modeling), Gurobi/CPLEX (large-scale).

📋Complexity Summary

Problem	Complexity	Algorithm
LP (continuous)	Polynomial	Interior point $O(n^{3.5}L)$
LP (simplex)	Exponential worst, fast practical	Simplex
ILP / MILP	NP-hard	Branch-and-cut
Transportation	Polynomial (special structure)	Transportation simplex
Network flow	Polynomial	Simplex on networks
Max flow	Polynomial	Ford-Fulkerson, push-relabel

Cross-References

ℹ️ Related Topics

065 — Constrained Optimization — Lagrange multipliers, KKT conditions — the continuous analog of duality.
067 — Quadratic Programming — Extends LP with quadratic objective; used in SVMs and portfolio optimization.
070 — Applications in Deep Learning — How optimization powers neural network training.
074 — Graphs — Network structures underlying flow problems.
031 — Lagrange Multipliers — Theoretical foundation for LP duality.
064 — Newton's Method: Interior-point methods use Newton steps on the barrier problem.
068 — Metaheuristic Optimization — Genetic algorithms and simulated annealing for problems where LP doesn't apply.
069 — Hyperparameter Optimization — Continuous optimization for tuning ML models.