Lemma 0, p. 656 — how c(s − 1, S) compares with c(s, S) and G(s)
ProvedZhengFedergruenSS.Algorithm.lemma_0inventoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1s-s-policy
In the model of Zheng and Federgruen, fix and .
- If then .
- If then .
- If then .
- If then .
- If then .
- If then .
Items 1–3 are part (a) of the lemma and items 4–6 part (b). These comparisons drive both loops of the algorithm.
Preamble
import Mathlib import Definitions.Def_VeinottWagnerSS_RenewalCost_Demand import Definitions.Def_ZhengFedergruenSS_Algorithm_Model
Formal statement
namespace ZhengFedergruenSS.Algorithm
/-- Lemma 0, p. 656 (Zheng and Federgruen 1991). For any fixed `S` and `s < S`:
(a) `G(s) < (=, >) c(s − 1, S) ⩽ (=, ⩾) c(s, S)` if `G(s) < (=, >) c(s, S)`;
(b) `c(s − 1, S) ⩽ (=, ⩾) c(s, S)` if `G(s) < (=, >) c(s − 1, S)`.
All six readings are stated; in (a) the first comparison is strict and the second weak, as printed. -/
theorem lemma_0 (D : VeinottWagnerSS.RenewalCost.DemandDist) (hp0 : D.φ 0 < 1)
(K : ℝ) (hK : 0 < K) (G : ℤ → ℝ) (hG : NegUnimodal G) (hgrowth : GrowthCond K G)
(s S : ℤ) (hsS : s < S) :
(G s < c D.φ K G s S → G s < c D.φ K G (s - 1) S ∧ c D.φ K G (s - 1) S ≤ c D.φ K G s S) ∧
(G s = c D.φ K G s S → G s = c D.φ K G (s - 1) S ∧ c D.φ K G (s - 1) S = c D.φ K G s S) ∧
(G s > c D.φ K G s S → G s > c D.φ K G (s - 1) S ∧ c D.φ K G (s - 1) S ≥ c D.φ K G s S) ∧
(G s < c D.φ K G (s - 1) S → c D.φ K G (s - 1) S ≤ c D.φ K G s S) ∧
(G s = c D.φ K G (s - 1) S → c D.φ K G (s - 1) S = c D.φ K G s S) ∧
(G s > c D.φ K G (s - 1) S → c D.φ K G (s - 1) S ≥ c D.φ K G s S) := by sorry
end ZhengFedergruenSS.Algorithm
Source
Zheng and Federgruen, Finding Optimal (s, S) Policies Is About As Simple As Evaluating a Single Policy, Oper. Res. 39(4):654–665 (1991), DOI 10.1287/opre.39.4.654, p. 656, Lemma 0
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.