Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 4, p. 939 — in program (3), the optimal a = min{d, v₀ − v₁}

Proved
ZipkinLostSales.LNatural.optimal_fill

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

dynamic-programminginventorylost-salesoperations-researchp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider the lost-sales model with lead time L≥1L\ge1L≥1, nonnegative independent demands with common law μ\muμ of finite mean, nonnegative unit costs c,h^,pc,\hat h,pc,h^,p and discount factor 0<γ≤10<\gamma\le10<γ≤1. Let fˉk\bar f_kfˉ​k​ be the optimal cost with kkk periods to go in the transformed state (with fˉ0=0\bar f_0=0fˉ​0​=0).

After demand d≥0d\ge 0d≥0 is observed in a period whose continuation cost is fˉt+1=fˉk\bar f_{t+1}=\bar f_kfˉ​t+1​=fˉ​k​, the paper's program (3) chooses the amount aaa of demand to fill and the remaining inventory www:

κˉt(v,ζ∣d)=min⁡a,w{h^w+p(d−a)+γfˉt+1[(w+v1,v2,…,vL−1,0)−ζe]:a+w=v0−v1, 0≤a≤d, w≥0}.\bar\kappa_t(v,\zeta\mid d)=\min_{a,w}\Big\{\hat h w+p(d-a)+\gamma\bar f_{t+1}\big[(w+v_1,v_2,\dots,v_{L-1},0)-\zeta e\big] : a+w=v_0-v_1,\ 0\le a\le d,\ w\ge0\Big\}.κˉt​(v,ζ∣d)=a,wmin​{h^w+p(d−a)+γfˉ​t+1​[(w+v1​,v2​,…,vL−1​,0)−ζe]:a+w=v0​−v1​, 0≤a≤d, w≥0}.

The claim is that the optimal aaa is min⁡{d,v0−v1}\min\{d,v_0-v_1\}min{d,v0​−v1​}: for every v∈Vv\in Vv∈V, ζ≤0\zeta\le0ζ≤0 and d≥0d\ge 0d≥0,

κˉt(v,ζ∣d)=q^(v0−v1−d)+γ fˉt+1(v+),v+=([v0−v1−d]++v1,v2,…,vL−1,0)−ζe,\bar\kappa_t(v,\zeta\mid d)=\hat q(v_0-v_1-d)+\gamma\,\bar f_{t+1}(v_+),\qquad v_+=\big([v_0-v_1-d]^+ +v_1,v_2,\dots,v_{L-1},0\big)-\zeta e,κˉt​(v,ζ∣d)=q^​(v0​−v1​−d)+γfˉ​t+1​(v+​),v+​=([v0​−v1​−d]++v1​,v2​,…,vL−1​,0)−ζe,

where q^(u)=h^u++pu−\hat q(u)=\hat h u^+ + p u^-q^​(u)=h^u++pu−.

The paper notes this "is not hard, but also not essential" for Theorem 4; it is what makes the two-step program (4)–(5) agree with the recursion (1). It depends on the model: it uses h^,p≥0\hat h,p\ge0h^,p≥0, γ≤1\gamma\le 1γ≤1 and the specific fˉt+1\bar f_{t+1}fˉ​t+1​, and fails for an arbitrary continuation function.

Formalization Note. The program is stated in the form (4), after the substitution v+=w+v1v_+=w+v_1v+​=w+v1​ (so a=min⁡{d,v0−v1}a=\min\{d,v_0-v_1\}a=min{d,v0​−v1​} is v+=max⁡(v0−d,v1)v_+=\max(v_0-d,v_1)v+​=max(v0​−d,v1​)); κˉ\bar\kappaκˉ is the infimum over the interval max⁡(v0−d,v1)≤v+≤v0\max(v_0-d,v_1)\le v_+\le v_0max(v0​−d,v1​)≤v+​≤v0​, and the equality says the infimum equals the value at the left endpoint. Time is the number of periods to go kkk (fbar … k is the paper's fˉt+1\bar f_{t+1}fˉ​t+1​, for every period ttt of every horizon). Vectors are indexed 0,…,L−10,\dots,L-10,…,L−1 with vL=0v_L=0vL​=0. The cost hypotheses (c,h^,p≥0c,\hat h,p\ge0c,h^,p≥0, 0<γ≤10<\gamma\le10<γ≤1) read the paper's "unit cost" and "discount rate"; nonnegative demand is the paper's; finite mean demand is added so that q^0\hat q^0q^​0 is finite.

Preamble
import Mathlib
import Definitions.Def_ZipkinLostSales_LNatural_Model
open MeasureTheory
Formal statement
namespace ZipkinLostSales.LNatural

/-- Proof of Theorem 4 (Zipkin 2008, p. 939): in program (3)/(4) with continuation `f̄_{t+1}`
(here `fbar … k`), filling as much demand as possible (`a = min{d, v₀ − v₁}`, i.e.
`v₊ = max(v₀ − d, v₁)`) is optimal, so `κ̄(v, ζ | d) = q̂(v₀ − v₁ − d) + γ f̄_{t+1}(v₊)` with `v₊`
the transition of p. 938. -/
theorem optimal_fill (L : ℕ) (hL : 0 < L) (μ : Measure ℝ) [IsProbabilityMeasure μ]
    (hμ : μ (Set.Iio 0) = 0) (hμint : Integrable id μ)
    (c hh p γ : ℝ) (hc : 0 ≤ c) (hhh : 0 ≤ hh) (hp : 0 ≤ p) (hγ0 : 0 < γ) (hγ1 : γ ≤ 1)
    (k : ℕ) (v : Fin L → ℝ) (hv : v ∈ V L) (ζ : ℝ) (hζ : ζ ≤ 0) (d : ℝ) (hd : 0 ≤ d) :
    kappa hh p γ (fbar c hh p γ μ k) d v ζ =
      qhat hh p (vext v 0 - vext v 1 - d) + γ * fbar c hh p γ μ k (next v d ζ) := by sorry

end ZipkinLostSales.LNatural
Source
Zipkin, On the Structure of Lost-Sales Inventory Models, Oper. Res. 56 (2008), p. 939 (PDF p. 4), proof of Theorem 4, program (3) and the remark "the optimal a = min{d, v₀ − v₁}", together with the substitution leading to (4)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me