Linear Programming

Definition

Linear programming (LP) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships.

Why It Matters

Optimization is the goal of every organization. Linear programming provides the mathematical rigor needed to find the “best possible” outcome (max profit, min cost) within the constraints of a budget or physical system, turning guessing into calculation.

Core Concepts

Objective Function: The linear function to be maximized or minimized ( $z = c^T x$ ).
- How to read: “The objective value z equals c transpose x.”
- Meaning: Weighted sum of decision variables—what you optimize (profit, cost, etc.).
Constraints: Linear inequalities or equations that define the feasible region ( $Ax \leq b$ and $x \geq 0$ ).
- How to read: “The matrix inequality A x is less than or equal to b, and x is greater than or equal to zero.”
- Meaning: Feasible solutions lie in the intersection of half-spaces (and often the first quadrant for non-negative variables).
Corner Point Principle: The optimal solution always occurs at one of the vertices (corner points) of the feasible region.
Simplex Method: An algorithm that moves from corner to corner along edges of the feasible region to find the optimum.
Duality: Every maximization problem (Primal) has a corresponding minimization problem (Dual).
- Primal: Maximize $c^T x$ subject to $Ax \leq b$ .
- Dual: Minimize $b^T y$ $b^{T} y$ subject to $A^T y \geq c$ $A^{T} y \geq c$ .
  - How to read: “Maximize c transpose x subject to A x being at most b, and minimize b transpose y subject to A transpose y being at least c.”
  - Meaning: Two views of the same problem—primal picks activities $x$ , dual prices constraints $y$ .
- Strong Duality: Max Primal = Min Dual.

from scipy.optimize import linprog

# Minimize: z = -1*x0 + -4*x1 (Equivalent to Maximize: 1*x0 + 4*x1)
c = [-1, -4]
# Constraints:
# 1*x0 + 1*x1 <= 7
# 1*x0 + 2*x1 <= 10
A = 1, 1], [1, 2
b = [7, 10]
x_bounds = (0, None)

res = linprog(c, A_ub=A, b_ub=b, bounds=[x_bounds, x_bounds])
print(f"Optimal value: {res.fun * -1}, at x: {res.x}")

Definition

Why It Matters

Core Concepts

Connected Concepts

Connected notes