NICEFA Logo
nicefa.
Library
←Module

The Strong Duality Theorem for Linear Programming

Exploring the cinematic intuition of The Strong Duality Theorem for Linear Programming.

Visualizing...

Our institutional research engineers are currently mapping the formal proof for The Strong Duality Theorem for Linear Programming.

Apply for Institutional Early Access →

The Formal Theorem

Consider the primal linear program (P) (P) defined as maximize cTx \text{maximize } c^T x subject to Ax≤b,x≥0 Ax \leq b, x \geq 0 , and its dual (D) (D) defined as minimize bTy \text{minimize } b^T y subject to ATy≥c,y≥0 A^T y \geq c, y \geq 0 . If either the primal or the dual has an optimal solution, then both possess optimal solutions, and their objective values are equal:
max⁡x{cTx∣Ax≤b,x≥0}=min⁡y{bTy∣ATy≥c,y≥0} \max_{x} \{ c^T x \mid Ax \leq b, x \geq 0 \} = \min_{y} \{ b^T y \mid A^T y \geq c, y \geq 0 \}

Analytical Intuition.

Imagine you are an industrial magnate managing a resource-constrained production line. The primal problem represents the maximization of profit by determining the optimal output x x . Simultaneously, the dual problem represents a 'shadow pricing' challenge: an accountant attempts to minimize the total valuation of your resources b b by assigning prices y y such that the cost of resources for any product is at least its market price c c . Strong Duality reveals a profound economic equilibrium: at the peak of your productive efficiency, the maximum profit you extract from your goods is exactly equal to the minimum price at which you would be willing to sell off your raw resource inventory. It is the mathematical bridge between two distinct perspectives—the producer's 'how much to make' and the analyst's 'what is this worth.' When these values converge, the system is in a state of perfect economic optimality, where there is no 'slack' or untapped potential in either the production process or the resource allocation.
CAUTION

Institutional Warning.

Students frequently conflate Strong Duality with Weak Duality. While Weak Duality ensures cTx≤bTy c^T x \leq b^T y for all feasible solutions, Strong Duality requires the existence of an optimal point; it fails if both primal and dual are infeasible or unbounded.

Academic Inquiries.

01

Does Strong Duality hold if the primal is unbounded?

No. If the primal is unbounded, the dual must be infeasible, meaning no equality of values can exist.

02

Why is the dual variable y y often called a 'shadow price'?

Because the optimal dual variable yi∗ y^*_i represents the marginal change in the primal objective function given a one-unit increase in the resource constraint bi b_i .

Standardized References.

  • Definitive Institutional SourceBertsimas, D., & Tsitsiklis, J. N., Introduction to Linear Optimization.

Related Proofs Cluster.

Intermediate

Weierstrass Extreme Value Theorem: Guaranteeing Existence of Optima

Exploring the cinematic intuition of Weierstrass Extreme Value Theorem: Guaranteeing Existence of Optima.

Intermediate

Local Optima are Global Optima for Convex Functions

Exploring the cinematic intuition of Local Optima are Global Optima for Convex Functions.

Intermediate

Hessian Matrix and Second-Order Optimality Conditions

Exploring the cinematic intuition of Hessian Matrix and Second-Order Optimality Conditions.

Intermediate

Jensen's Inequality for Convex Functions

Exploring the cinematic intuition of Jensen's Inequality for Convex Functions.

Institutional Citation

Reference this proof in your academic research or publications.

NICEFA Visual Mathematics. (2026). The Strong Duality Theorem for Linear Programming: Visual Proof & Intuition. Retrieved from https://nicefa.org/library/fundamentals-of-optimization/the-strong-duality-theorem-for-linear-programming

Dominate the Logic.

"Abstract theory is just a movement we haven't seen yet."

Subscribe for Full ProofsEarly Access