Duality theorem (§6.1) — the duality theorem of linear programming
ProvedMatousekLP.Duality.duality_theoremLet be a real matrix with rows and columns, and , and consider the linear programs
Then exactly one of the following four possibilities occurs:
- neither (P) nor (D) has a feasible solution;
- (P) is unbounded and (D) has no feasible solution;
- (P) has no feasible solution and (D) is unbounded (from below);
- both (P) and (D) have a feasible solution; then both have an optimal solution, and for every optimal solution of (P) and every optimal solution of (D)
That is, whenever both programs are feasible, the maximum of (P) is attained and equals the minimum of (D), which is attained as well. This is the central theorem of linear programming duality; weak duality (Proposition 6.1.1) supplies the inequality , and the content of the theorem is that the dual guards the primal perfectly.
Formalization Note The four cases are the predicate DualityCase A b c k of the definition module MatousekLP.Duality.PrimalDual, with the book's case at index ; "exactly one occurs" is ∃! k : Fin 4, DualityCase A b c k. Optimal solutions are feasible points whose objective value is at least (for (P)) or at most (for (D)) that of every feasible point; no supremum or infimum is used.
import Mathlib import Definitions.Def_MatousekLP_Duality_PrimalDual
namespace MatousekLP.Duality
/-- Matoušek & Gärtner, §6.1, p. 83, Duality theorem of linear programming: for
(P) maximize `cᵀx` s.t. `Ax ≤ b`, `x ≥ 0` and (D) minimize `bᵀy` s.t. `Aᵀy ≥ c`, `y ≥ 0`,
exactly one of the four possibilities `DualityCase A b c k` (`k = 0, 1, 2, 3` for the book's
cases 1–4) occurs. -/
theorem duality_theorem {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(c : Fin n → ℝ) :
∃! k : Fin 4, DualityCase A b c k := by sorry
end MatousekLP.Duality
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.