Linear Programming

Why LP exists (motivation)

Many decision problems are about choosing amounts: how much to produce, ship, invest, schedule, or mix. These decisions interact through resource limits (labor hours, budgets, capacities) and requirements (demand, minimum levels). When those interactions are well-approximated by linear relationships, you get a model that is both expressive and mathematically tractable.

LP is foundational in optimization because it sits at the intersection of:

• •Modeling clarity: constraints are readable inequalities.
• •Geometry: feasible solutions form a polyhedron, so the optimum lives at a “corner”.
• •Algorithms: the simplex method and interior-point methods exploit that structure.

The formal definition

An LP in common “inequality form” is:

Maximize (or minimize)

• •objective: cᵀx

Subject to

• •Ax ≤ b
• •x ≥ 0

where:

• •x ∈ ℝⁿ is the decision vector (variables).
• •A ∈ ℝ^{m×n} is the constraint matrix.
• •b ∈ ℝᵐ is the right-hand side.
• •c ∈ ℝⁿ are the objective coefficients.

You might also see equalities, ≥ inequalities, or variables not restricted to be nonnegative. These are equivalent up to standard transformations (we’ll do those carefully soon).

Intuition: linear objective + linear constraints

• •A linear constraint like a₁ᵀx ≤ b₁ defines a half-space.
• •The intersection of half-spaces (and possibly equalities) is a convex polyhedron.
• •A linear objective cᵀx has level sets that are parallel hyperplanes. As you “slide” the hyperplane in the direction of improvement, it last touches the feasible polyhedron at an extreme point (a vertex), unless the optimum is unbounded or the feasible region is empty.

That is the key geometric promise of LP:

If the feasible region is nonempty and bounded and the objective is linear, then an optimal solution exists at a vertex of the feasible polyhedron.

A compact vocabulary

Here are the basic terms you will keep using:

We’ll now build the mechanics that connect this geometry to the simplex algorithm.

Why geometry matters before algorithms

The simplex method works because it only needs to look at a small subset of points: the vertices. To understand why, you need a clear picture of the feasible region and what linear objectives do on convex sets.

Feasible region as an intersection of half-spaces

Each inequality constraint is a half-space:

• •aᵢᵀx ≤ bᵢ is all points on one side of the hyperplane aᵢᵀx = bᵢ.

The feasible region is:

• •P = { x ∈ ℝⁿ : Ax ≤ b, x ≥ 0 }

This set P is convex because it is an intersection of convex sets (half-spaces and the nonnegative orthant).

Convexity (quick but important)

If x₁ and x₂ are feasible, then for any λ ∈ [0, 1],

• •x(λ) = λx₁ + (1 − λ)x₂

is also feasible because:

• •Ax(λ) = A(λx₁ + (1 − λ)x₂)

= λAx₁ + (1 − λ)Ax₂

≤ λb + (1 − λ)b

= b

and x(λ) ≥ 0 if x₁, x₂ ≥ 0.

Convexity is the reason there are no “local maxima” different from the global max for LP; but more importantly, it supports the vertex optimality claim.

Extreme points / vertices and active constraints

A vertex is a point that cannot be expressed as a nontrivial convex combination of two other feasible points. Operationally in LP, a vertex occurs where enough constraints are tight (active) to pin down a unique point.

In ℝ², a vertex is where two non-parallel lines meet (and all constraints hold). In ℝⁿ, you typically need n linearly independent active constraints.

Why the optimum is at a vertex (intuition)

Consider maximizing cᵀx. The sets {x : cᵀx = α} are hyperplanes. Increasing α slides the hyperplane in direction c.

• •If the feasible region is bounded, the last contact between those hyperplanes and the feasible set occurs on the boundary.
• •Because the objective is linear, if the last contact happened strictly inside a face (not at a vertex), then every point on that face would share the same objective value. In that case, at least one vertex of that face is also optimal.

So you can search among vertices.

Degeneracy and multiple optima (important nuance)

Two subtle but common phenomena:

1) Multiple optimal solutions

If the objective hyperplane is parallel to a face of the polyhedron, then the last-contact set is a whole edge/face. There are infinitely many optimal solutions, but still at least one optimal vertex.

2) Degeneracy

A vertex is degenerate if more than n constraints are active there, causing some basic variables to be zero in simplex form. Degeneracy can make simplex “stall” (no objective improvement on a pivot) and is the source of cycling (rare in practice, but real in theory).

Standard form as preparation for simplex

The simplex method is most naturally described for standard form:

Maximize

• •cᵀx

Subject to

• •Ax = b
• •x ≥ 0

How do we convert Ax ≤ b into equalities? Add slack variables.

Slack variables (mechanics)

If you have:

• •aᵢᵀx ≤ bᵢ

introduce slack sᵢ ≥ 0 such that:

• •aᵢᵀx + sᵢ = bᵢ

Stacking all constraints:

• •Ax + s = b, with s ≥ 0

Now the full variable vector might be z = [x; s] with z ≥ 0.

What a vertex looks like in standard form

In standard form with m equations, a basic solution chooses m variables to solve for (the “basic” variables) and sets the rest to 0 (the “nonbasic” variables). If the resulting basic variables are ≥ 0, the solution is a basic feasible solution (BFS), which corresponds to a vertex (under mild non-degeneracy assumptions).

This is the bridge:

• •Geometry: vertices.
• •Algebra: BFS defined by choosing a basis.

Next we’ll make that bridge explicit with simplex pivoting.

Why simplex works (the big idea)

If an optimum exists at a vertex, we can:

1) Start at some vertex (a BFS).

2) Move along edges to adjacent vertices.

3) Improve the objective each step.

4) Stop when no adjacent vertex improves.

The simplex method implements this using linear algebra on a changing set of basic variables.

Partition variables into basic and nonbasic

Assume standard form:

• •Ax = b, x ≥ 0

with A ∈ ℝ^{m×n} and rank m (constraints independent).

Choose an index set B (|B| = m) for basic variables and N for nonbasic variables. Reorder columns so:

• •A = [A_B A_N]
• •x = [x_B; x_N]

Then constraints become:

• •A_B x_B + A_N x_N = b

If A_B is invertible, solve:

• •x_B = A_B⁻¹(b − A_N x_N)

A basic solution sets x_N = 0, giving:

• •x_B = A_B⁻¹ b

This is feasible iff A_B⁻¹ b ≥ 0.

Objective in terms of nonbasic variables (reduced costs)

Write objective:

• •maximize cᵀx = c_Bᵀx_B + c_Nᵀx_N

Substitute x_B:

cᵀx = c_BᵀA_B⁻¹(b − A_N x_N) + c_Nᵀx_N

Work it step-by-step:

= c_BᵀA_B⁻¹b − c_BᵀA_B⁻¹A_N x_N + c_Nᵀx_N

= (c_BᵀA_B⁻¹b) + (c_Nᵀ − c_BᵀA_B⁻¹A_N) x_N

Define the reduced costs:

• •r_Nᵀ = c_Nᵀ − c_BᵀA_B⁻¹A_N

Then:

• •objective = constant + r_Nᵀ x_N

Optimality condition (for maximization)

At a BFS, x_N = 0. If all reduced costs satisfy:

• •r_N ≤ 0 (componentwise)

then increasing any nonbasic variable from 0 cannot increase the objective (because it would contribute rⱼ xⱼ with rⱼ ≤ 0 and xⱼ ≥ 0). Therefore the BFS is optimal.

If some reduced cost is positive, that variable is a candidate to enter the basis to improve the objective.

Pivoting: moving to an adjacent BFS

Suppose variable x_k (currently nonbasic) has reduced cost r_k > 0 and we try to increase it. From:

• •x_B = A_B⁻¹(b − A_k x_k − …)

the basic variables change linearly with x_k. To maintain feasibility, we require x_B ≥ 0. This yields a maximum step size (the ratio test).

Let d = A_B⁻¹ A_k be the direction in basic-variable space when x_k increases by 1. Then:

• •x_B(new) = x_B(old) − d · θ

where θ is the amount we increase x_k.

Feasibility requires:

• •x_B(old) − d θ ≥ 0

For components where d_i > 0:

• •θ ≤ x_{B,i} / d_i

So choose:

• •θ* = min_{i: d_i > 0} x_{B,i} / d_i

The minimizer index i* tells you which basic variable hits zero first; that variable leaves the basis.

This produces a new basis B′ where x_k enters and x_{B,i*} leaves—an adjacent vertex.

What about unboundedness?

If for an entering variable x_k with r_k > 0 we have d_i ≤ 0 for all i, then increasing x_k never makes any basic variable negative. Then θ can grow without bound and the objective increases without bound.

That is the simplex certificate of unboundedness.

Tableau view (operational tool)

In practice simplex is often described via a tableau (a compact way to maintain A_B⁻¹A and A_B⁻¹b). Pivot operations perform the basis change without explicitly inverting matrices each step.

Conceptually:

• •Pivot chooses an entering column (improves objective)
• •Pivot chooses a leaving row (ratio test)
• •Row operations update the tableau to represent the new BFS

Phase I / Phase II (finding a starting BFS)

A hidden requirement so far: we need an initial BFS. If the model is in the form:

• •Ax = b, x ≥ 0

and b ≥ 0 with slack variables forming an identity matrix, we get a trivial BFS by setting original variables to 0 and slacks to b.

But if constraints include:

• •equalities not naturally having slack identity columns,
• •≥ inequalities (need surplus variables),
• •negative b entries,

then a BFS is not obvious.

Phase I introduces artificial variables and minimizes their sum to drive them to 0; if the minimum is > 0, the LP is infeasible. If it reaches 0, the resulting basis gives a feasible start for Phase II, which optimizes the real objective.

We’ll solidify all of this with worked examples where the algebra and geometry line up clearly.

Why LP modeling is a skill (not just a solver call)

The power of LP comes from turning messy language into:

• •decision variables (what you control),
• •an objective (what “better” means),
• •constraints (what must be true).

A good LP model is:

• •complete (captures all real constraints that matter),
• •linear (no products of variables, no max/min inside unless linearized),
• •scaled (coefficients not wildly different in magnitude).

Common modeling patterns

1) Resource allocation / production planning

Variables: xⱼ = quantity of product j.

Constraints: ∑ aᵢⱼ xⱼ ≤ bᵢ (resource i capacity).

Objective: maximize ∑ pⱼ xⱼ.

2) Diet / blending

Variables: xⱼ = amount of ingredient j.

Constraints: nutrition minimums ∑ nᵢⱼ xⱼ ≥ reqᵢ; cost objective.

3) Transportation

Variables: x_{i→j} shipment.

Constraints: supply and demand balance, capacity.

Objective: min cost.

Many of these become special LPs that admit faster algorithms (e.g., network flow), but LP is the unifying language.

Duality (connection you’ll soon rely on)

Even before a full duality theorem, it helps to internalize the dual’s meaning:

• •The primal chooses quantities x.
• •The dual assigns “prices” y to constraints.

For a primal in max form:

Maximize cᵀx

Subject to Ax ≤ b, x ≥ 0

A corresponding dual is:

Minimize bᵀy

Subject to Aᵀy ≥ c, y ≥ 0

Interpretation:

• •yᵢ is the shadow price of resource i.
• •Aᵀy ≥ c means the priced resources cover each product’s profit.
• •bᵀy is the total value of available resources.

Weak duality says:

• •For any feasible x and y: cᵀx ≤ bᵀy

So the dual provides an upper bound on primal profit (for max problems). At optimum, the bounds meet.

This matters because:

• •It explains optimality conditions.
• •It gives certificates of optimality.
• •It connects LP to game theory (minimax) and to flows (min-cut).

Connection to Zero-Sum Games

A finite zero-sum game can be written as an LP:

• •Choose a mixed strategy p (probabilities) maximizing guaranteed payoff v.

Constraints enforce that expected payoff against each opponent action is ≥ v. That is linear in p, and probabilities sum to 1.

Duality aligns with the minimax theorem:

• •max over player A strategies of min payoff = min over player B strategies of max payoff

This is exactly primal-dual equality.

You’ll use LP duality as the algebraic backbone for Zero-Sum Games.

Connection to Network Flow

Max-flow can be expressed as an LP:

• •Variables are flows on edges.
• •Constraints are capacity bounds and flow conservation.
• •Objective is total flow from source to sink.

The dual corresponds to a min-cut-like object. Strong duality yields the max-flow min-cut theorem.

This is why Network Flow feels “LP-shaped” even when solved with specialized algorithms.

When simplex is used in practice

Despite worst-case exponential examples, simplex is extremely fast on many real problems and remains a workhorse in operations research, often enhanced with:

• •presolve and scaling,
• •advanced pivot rules,
• •sparse linear algebra,
• •warm starts (re-optimizing after small model changes).

For very large, sparse LPs, interior-point methods are also common, but simplex is still essential for sensitivity analysis and re-optimization.