Lemma 5.6.1 — a pivot step leads to a feasible basis, or detects unboundedness
ProvedMatousekLP.Simplex.pivot_stepLet be a real matrix of rank with , , , and let be a feasible basis with complement and simplex tableau , . Let , , be a nonbasic variable with (an admissible entering variable).
- If , , satisfies the leaving criterion
then is again a feasible basis. 2. If no satisfies it, i.e. for all , then the linear program is unbounded. More precisely, there is a family , , of solutions of with and all other nonbasic variables ; is feasible for every , and as .
The lemma shows that the simplex method moves from feasible basis to feasible basis, and that it stops only at an optimal tableau or with a certificate of unboundedness.
Formalization Note Indices are 0-based; , , are the explicit parameters of Lemma 5.5.1. "No satisfies the criterion" is expressed as for all , which is equivalent because a minimum over a nonempty finite set is attained. The standing assumption of §4.2 is a hypothesis.
import Mathlib import Definitions.Def_MatousekLP_Simplex_Tableau open Matrix Filter
namespace MatousekLP.Simplex
/-- Lemma 5.6.1 (p. 68). Let `B` be a feasible basis and let the entering variable `x_v`,
`v = ℓ_β`, have a positive coefficient `r_β` in the last row of `T(B)`.
(1) If the leaving variable `x_u`, `u = k_α`, satisfies (5.3), then `B′ = (B \ {u}) ∪ {v}` is
again a feasible basis.
(2) If no `x_u` satisfies the criterion (no row has `q_{iβ} < 0`), then the linear program is
unbounded: substituting `t` for `x_v` and `0` for the other nonbasic variables gives, for
every `t ≥ 0`, a feasible solution, and its objective value tends to `+∞` as `t → ∞`.
Standing assumption of §4.2 (p. 44): `n ≥ m` and `A` has rank `m`. -/
theorem pivot_step {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(c : Fin n → ℝ) (hmn : m ≤ n) (hrank : A.rank = m) (B : Finset (Fin n)) (hB : B.card = m)
(hfeas : IsFeasibleBasisOf A b B hB) (β : Fin (n - m)) (hr : 0 < tableauR A c B hB β) :
(∀ α : Fin m, IsEnteringLeaving A b c B hB β α →
IsFeasibleBasis A b (pivotBasis B hB β α)) ∧
((∀ i : Fin m, 0 ≤ tableauQ A B hB i β) →
IsUnbounded A b c ∧
∃ x : ℝ → Fin n → ℝ,
(∀ t, A *ᵥ x t = b ∧ x t (lIdx B hB β) = t ∧
∀ j, j ≠ β → x t (lIdx B hB j) = 0) ∧
(∀ t, 0 ≤ t → MatousekLP.BFS.IsFeasible A b (x t)) ∧
Tendsto (fun t => c ⬝ᵥ x t) atTop atTop) := by sorry
end MatousekLP.Simplex
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.