Lemma 8.4: the DUALOC duality gap is
ProvedSupplyChainTheory.dualoc_gapdualitydualocfacility-locationoperations-research
Lemma 8.4. Let and satisfy PDP1 and PDP2, let be a nearest facility of to each customer , and let be the primal solution (8.52)-(8.53). Then the objective value of (UFLP-P) under and the objective value of the condensed dual (UFLP-CD) under satisfy
The book omits the proof (Problem 8.40). By PDP1 each fixed cost , , is the sum of the dual slacks , and by PDP2 the slack of is exactly ; the remaining slacks are the gap. This is what the dual-adjustment procedure attacks.
Preamble
import Definitions.Def_SupplyChainTheory_location
Formal statement
namespace SupplyChainTheory
theorem dualoc_gap {n m : ℕ} (chat : Fin n → Fin m → ℝ) (f : Fin m → ℝ) (v : Fin n → ℝ)
(Jp : Finset (Fin m)) (a : Fin n → Fin m) (hPDP : PDP chat f v Jp) (ha : NearestIn chat Jp a) :
(∑ j ∈ Jp, f j + ∑ i, chat i (a i)) - ∑ i, v i
= ∑ i, ∑ j ∈ Jp.erase (a i), max 0 (v i - chat i j) := by sorry
end SupplyChainTheory
Source
Lawrence V. Snyder and Zuo-Jun Max Shen, Fundamentals of Supply Chain Theory, 2nd ed., Wiley 2019, DOI 10.1002/9781119584445, p. 284, Sect. 8.2.4.1, Lemma 8.4: 'Proof. Omitted; see Problem 8.40'
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.