Linear programming

Question

Consider a standard LP:

maximize : z = c^Tx (1)

subject to : Ax = b (2)

and x ≥ 0 component-wise (3)

Suppose in addition that the LP has an optimal solution. Prove that this LP must have an optimal BFS. Below are the steps you take to prove this fact.

1. Use the representation theorem to represent an optimal solution x.

2. Use optimality to show that c^Td = 0, where d is the direction of unboundedness.

3. Compare c^Tx with c^Tb, where b is the BFS with the largest objective function value.

4. Conclude that x = b due to optimality.

Answer 1

Hi Sarah,

Here is Proof That an Optimal LP Has an Optimal BFS

Step 1: Representation Theorem Application

By the Representation Theorem, any feasible solution *x* can be written as:

x = Σλᵢvᵢ + Σμⱼdⱼ

where:

1. vᵢ are extreme points (BFSs)
2. dⱼ are extreme directions
3. λᵢ ≥ 0, *Σλᵢ = 1*
4. μⱼ ≥ 0

Step 2: Optimality Implies cᵀd = 0

If any cᵀdⱼ > 0, the objective could be made arbitrarily large by taking μⱼ → ∞, contradicting optimality. Thus:

cᵀdⱼ ≤ 0 for all *j*

But if cᵀdⱼ < 0, then *x* wouldn't be optimal (set *μⱼ = 0*). Therefore:

*cᵀdⱼ = 0* for all *j*

Step 3: Compare Objective Values

The objective decomposes as:

cᵀx = Σλᵢ(cᵀvᵢ) + Σμⱼ(cᵀdⱼ) = Σλᵢ(cᵀvᵢ)

Let *v* be the BFS with maximum cᵀvᵢ. Then:

cᵀx = Σλᵢ(cᵀvᵢ) ≤ cᵀv (since *Σλᵢ = 1*)

Step 4: Conclude x = v

By optimality of *x*, we must have cᵀx = cᵀv, which occurs iff:

1. *λᵢ = 1* for the maximizing vᵢ
2. *λᵢ = 0* for all others
3. Thus x = v (a BFS). ∎

Why This Matters for Your Learning:

This proof reveals key insights about LPs:

1. BFS Dominance: Only need to check BFSs for optimality
2. Degeneracy Implications: Ties in cᵀvᵢ lead to multiple optima
3. Algorithm Design: Justifies why simplex works

Common Student Pitfalls I Address:

1. Misapplying the Representation Theorem
2. Overlooking *cᵀdⱼ = 0* implications
3. Confusing BFSs with interior points

Ready to Master LP Proofs?

In our sessions, you'll:

✓ Animate this proof using Python/MATLAB

✓ Solve variants (e.g., minimization, unbounded cases)

✓ Apply to your HW problems with my step-check system

Limited Availability: Book by Friday for a free LP Proof Cheat Sheet

Best Regards,

Aaron