Continuous-review lost-sales inventory system: demand environments, admissible policies, costs, and the family
DefinitionLostSalesRQ_modelPrimitive data: demand rate (unit Poisson demand), deterministic lead time , holding cost rate , lost-sales penalty , fixed ordering cost .
Demand environments. A demand environment is a probability space with a filtration and a cumulative demand count , the number of unit demands in ( for ). is adapted, nondecreasing and right-continuous, and for the increment is Poisson with mean and independent of . The information carries everything a policy may use: the demand history and independent private randomization.
Admissible policies. A policy on consists of a free initial supply, the number of units available by each time (on hand at , then deliveries of an initial pipeline with no bound by on residual delivery times), which is finite and -measurable, and a cumulative order process , the number of units ordered in . is adapted to (so an order at a demand epoch may follow that demand), nondecreasing, integer-valued and right-continuous, hence it has finitely many order epochs on bounded intervals.
Dynamics. Units ordered at arrive at . Demand epochs are processed in increasing order; at each epoch the arriving demands are served from the units delivered strictly before the epoch, net of demands already served, and the rest are lost. is on-hand stock, and the served and lost demands, and the number of order epochs in . The cost and the unrestricted optimum are
the infimum ranging over all demand environments of rate and all admissible policies on them. is at , , , .
Policy families. The no-order policy starts empty and never orders. A policy follows the rule if it starts with units on hand and an empty pipeline and a served demand that lowers the inventory position from to triggers an immediate order of units; equivalently . collects these policies (, ) and the no-order policy; collects base stock (the rule) and the no-order policy. The selection rule of Corollary 1 takes the rule if and , and the no-order policy otherwise. Expected holding, order count and served demand on are also defined, for Lemma J.1.
Formalization Note Expected costs, their upper limits and the infima are in . Infinite expected cost stays infinite, and a zero cost coefficient times an infinite expectation is zero, which matches the paper's convention that finite expected cost is required only when the coefficient is positive. Simultaneous demands (a null event under the Poisson law) are served up to the available stock. The rule is a predicate on policies; its existence on every demand environment is a milestone.
import Definitions.Def_LostSalesRQ_poisson_functions
import Mathlib.Probability.Independence.Basic
import Mathlib.Probability.Process.Filtration
import Mathlib.MeasureTheory.Measure.Lebesgue.Basic
import Mathlib.Order.LiminfLimsup
import Mathlib.Data.Finset.Sort
/-!
# The continuous-review lost-sales inventory system
Operational model of M. Hu, "A 1.932 Guarantee for (r,Q) Policies in Continuous-Review
Lost-Sales Inventory Systems", Section 3: unit Poisson demand of rate `lam`, deterministic lead
time `L`, holding cost rate `h`, lost-sales penalty `p`, fixed ordering cost `K`.
A demand environment is a probability space with a filtration carrying the cumulative demand
count `N`, whose increments after any time `s ≥ 0` are Poisson and independent of the
information at `s`. The information carries everything a policy may use: the demand history and
independent private randomization. A policy is a free, finite initial supply (on hand at time
`0` or pending with arbitrary residual delivery times, chosen from the information at time `0`)
together with an adapted, nondecreasing, right-continuous cumulative order process. Orders arrive
`L` time units after they are placed. Demand is served from on-hand stock when it is positive and
is lost otherwise; units arriving at an epoch serve only later demand. Stock cannot be discarded
and orders cannot be cancelled.
-/
noncomputable section
open MeasureTheory ProbabilityTheory Filter
open scoped ENNReal
namespace LostSalesRQ
/-- A demand environment for demand rate `lam` (Section 3.1). `N t` is the number of demands in
`(0, t]` (zero for `t ≤ 0`); it is adapted, nondecreasing and right-continuous, every increment
`N t - N s` with `0 ≤ s ≤ t` is Poisson with mean `lam (t - s)`, and is independent of the
information `𝓕 s` available at time `s`. -/
structure DemandSpace (lam : ℝ) where
Ω : Type
[mΩ : MeasurableSpace Ω]
ν : Measure Ω
[prob : IsProbabilityMeasure ν]
𝓕 : Filtration ℝ mΩ
N : ℝ → Ω → ℕ
N_adapted : ∀ t, Measurable[𝓕 t] (N t)
N_nonpos : ∀ ω t, t ≤ 0 → N t ω = 0
N_mono : ∀ ω, Monotone (fun t => N t ω)
N_rcont : ∀ ω t, ∃ δ > 0, ∀ s, t ≤ s → s < t + δ → N s ω = N t ω
N_law : ∀ s t, 0 ≤ s → s ≤ t → ∀ k : ℕ,
ν {ω | N t ω - N s ω = k} = ENNReal.ofReal (poisMass (lam * (t - s)) k)
N_indep : ∀ s t, 0 ≤ s → s ≤ t →
Indep (MeasurableSpace.comap (fun ω => N t ω - N s ω) inferInstance) (𝓕 s) ν
attribute [instance] DemandSpace.mΩ DemandSpace.prob
/-- An admissible replenishment policy on the demand environment `S` (Section 3.1).
`init t ω` is the number of free initial units available by time `t` (on hand at `t = 0`, then
deliveries of the initial pipeline, with no bound on their residual delivery times); it is
finite and determined by the information at time `0`. `U t ω` is the cumulative number of units
ordered in `[0, t]`; it is adapted (an order at time `t` may use the demand at `t`),
nondecreasing and right-continuous, hence has finitely many order epochs on bounded intervals. -/
structure Policy {lam : ℝ} (S : DemandSpace lam) where
init : ℝ → S.Ω → ℕ
U : ℝ → S.Ω → ℕ
init_meas : ∀ t, Measurable[S.𝓕 0] (init t)
init_nonpos : ∀ ω t, t < 0 → init t ω = 0
init_mono : ∀ ω, Monotone (fun t => init t ω)
init_rcont : ∀ ω t, ∃ δ > 0, ∀ s, t ≤ s → s < t + δ → init s ω = init t ω
init_bdd : ∀ ω, ∃ n : ℕ, ∀ t, init t ω ≤ n
U_adapted : ∀ t, Measurable[S.𝓕 t] (U t)
U_nonpos : ∀ ω t, t < 0 → U t ω = 0
U_mono : ∀ ω, Monotone (fun t => U t ω)
U_rcont : ∀ ω t, ∃ δ > 0, ∀ s, t ≤ s → s < t + δ → U s ω = U t ω
/-- The left limit `f(t-) = sup_{s < t} f(s)` of a nondecreasing path. -/
def leftLim (f : ℝ → ℕ) (t : ℝ) : ℕ :=
sSup (f '' Set.Iio t)
/-- Units delivered by time `t`: initial supply plus units ordered by time `t - L`. -/
def delivered (L : ℝ) (init U : ℝ → ℕ) (t : ℝ) : ℕ :=
init t + U (t - L)
open Classical in
/-- Number of demands served in `(0, t]`. Demand epochs (jumps of `N`) are processed in
increasing order; at an epoch `τ` with `N(τ) - N(τ-)` arrivals, as many are served as the
on-hand stock just before `τ` allows, namely the units delivered strictly before `τ` minus the
demands already served. The remaining arrivals are lost. -/
def servedPath (L : ℝ) (init U N : ℝ → ℕ) (t : ℝ) : ℕ :=
let E : Set ℝ := {τ | τ ∈ Set.Ioc 0 t ∧ leftLim N τ < N τ}
if hE : E.Finite then
(hE.toFinset.sort (· ≤ ·)).foldl
(fun acc τ => acc + min (N τ - leftLim N τ) (leftLim init τ + leftLim U (τ - L) - acc)) 0
else 0
/-- Number of positive orders placed in `[0, T]` (jump epochs of the cumulative order path). -/
def orderCount (U : ℝ → ℕ) (T : ℝ) : ℕ :=
Set.ncard {t | t ∈ Set.Icc 0 T ∧ leftLim U t < U t}
variable {lam : ℝ} {S : DemandSpace lam}
/-- Demands served in `(0, t]` under `π`. -/
def Policy.served (L : ℝ) (π : Policy S) (t : ℝ) (ω : S.Ω) : ℕ :=
servedPath L (fun s => π.init s ω) (fun s => π.U s ω) (fun s => S.N s ω) t
/-- On-hand inventory `X(t)`: units delivered by `t` minus demands served by `t`. -/
def Policy.onHand (L : ℝ) (π : Policy S) (t : ℝ) (ω : S.Ω) : ℕ :=
delivered L (fun s => π.init s ω) (fun s => π.U s ω) t - π.served L t ω
/-- Demands lost in `(0, t]`: `𝒰(t) = N(t) - 𝒜(t)`. -/
def Policy.lost (L : ℝ) (π : Policy S) (t : ℝ) (ω : S.Ω) : ℕ :=
S.N t ω - π.served L t ω
/-- Number `O(T)` of positive orders placed in `[0, T]`. -/
def Policy.orders (π : Policy S) (T : ℝ) (ω : S.Ω) : ℕ :=
orderCount (fun s => π.U s ω) T
/-- Realized cost on `[0, T]`: `h ∫_0^T X(t) dt + p 𝒰(T) + K O(T)`. -/
def Policy.horizonCost (L h p K : ℝ) (π : Policy S) (T : ℝ) (ω : S.Ω) : ℝ≥0∞ :=
ENNReal.ofReal h * (∫⁻ t in Set.Icc 0 T, (π.onHand L t ω : ℝ≥0∞))
+ ENNReal.ofReal p * (π.lost L T ω : ℝ≥0∞)
+ ENNReal.ofReal K * (π.orders T ω : ℝ≥0∞)
/-- Long-run average cost `C(π) = limsup_{T → ∞} T⁻¹ E[h ∫_0^T X dt + p 𝒰(T) + K O(T)]`
(eq. (3)). -/
def Policy.avgCost (L h p K : ℝ) (π : Policy S) : ℝ≥0∞ :=
limsup (fun T : ℝ => (∫⁻ ω, π.horizonCost L h p K T ω ∂S.ν) / ENNReal.ofReal T) atTop
/-- Expected holding `E ∫_0^T X(t) dt`. -/
def Policy.expectedHolding (L : ℝ) (π : Policy S) (T : ℝ) : ℝ≥0∞ :=
∫⁻ ω, (∫⁻ t in Set.Icc 0 T, (π.onHand L t ω : ℝ≥0∞)) ∂S.ν
/-- Expected number of positive orders `E O(T)`. -/
def Policy.expectedOrders (π : Policy S) (T : ℝ) : ℝ≥0∞ :=
∫⁻ ω, (π.orders T ω : ℝ≥0∞) ∂S.ν
/-- Expected number of served demands `E 𝒜(T)`. -/
def Policy.expectedServed (L : ℝ) (π : Policy S) (T : ℝ) : ℝ≥0∞ :=
∫⁻ ω, (π.served L T ω : ℝ≥0∞) ∂S.ν
/-- The policy starts physically empty: no initial supply. -/
def Policy.EmptyStart (π : Policy S) : Prop :=
∀ ω t, π.init t ω = 0
end LostSalesRQ
namespace LostSalesRQ
/-- The unrestricted optimum `OPT` (eq. (3)): the infimum of the long-run average cost over all
admissible policies on every demand environment of rate `lam`. -/
def OPT (lam L h p K : ℝ) : ℝ≥0∞ :=
⨅ (S : DemandSpace lam) (π : Policy S), π.avgCost L h p K
/-- Normalized optimum `OPT_k(μ, a)`: unit demand rate, unit holding cost, lead time `μ`,
lost-sales penalty `a`, setup cost `k` (Section 3.2). -/
def OPTk (μ a k : ℝ) : ℝ≥0∞ :=
OPT 1 μ 1 a k
variable {lam : ℝ}
/-- The empty-start policy that never orders. -/
def noOrderPolicy (S : DemandSpace lam) : Policy S where
init := fun _ _ => 0
U := fun _ _ => 0
init_meas := fun _ => measurable_const
init_nonpos := fun _ _ _ => rfl
init_mono := fun _ => monotone_const
init_rcont := fun _ _ => ⟨1, one_pos, fun _ _ _ => rfl⟩
init_bdd := fun _ => ⟨0, fun _ => le_rfl⟩
U_adapted := fun _ => measurable_const
U_nonpos := fun _ _ _ => rfl
U_mono := fun _ => monotone_const
U_rcont := fun _ _ => ⟨1, one_pos, fun _ _ _ => rfl⟩
/-- `π` follows the classical `(r, Q)` rule (Section 3.3): it starts with `r + Q` units on hand
and an empty pipeline, and a served demand that lowers the inventory position from `r + 1` to `r`
triggers an immediate order of `Q` units. Equivalently, the cumulative order quantity is
`Q ⌊𝒜(t)/Q⌋`, where `𝒜(t)` is the number of demands served in `(0, t]`. -/
def IsRQPolicy {S : DemandSpace lam} (L : ℝ) (r Q : ℕ) (π : Policy S) : Prop :=
(∀ ω t, π.init t ω = if 0 ≤ t then r + Q else 0) ∧
∀ ω t, π.U t ω = Q * (π.served L t ω / Q)
/-- The classical family `Π_rQ`: every `(r, Q)` policy with integers `r ≥ 0`, `Q ≥ 1`, together
with the empty-start no-order policy. -/
def rQFamily (S : DemandSpace lam) (L : ℝ) : Set (Policy S) :=
{π | ∃ r Q : ℕ, 1 ≤ Q ∧ IsRQPolicy L r Q π} ∪ {noOrderPolicy S}
/-- The integer base-stock family `Π_S`: base stock `j ≥ 1` is the `(j - 1, 1)` rule, and level
`0` is the no-order policy. -/
def baseStockFamily (S : DemandSpace lam) (L : ℝ) : Set (Policy S) :=
{π | ∃ j : ℕ, 1 ≤ j ∧ IsRQPolicy L (j - 1) 1 π} ∪ {noOrderPolicy S}
/-- `inf_{π ∈ Π_rQ} C(π)` on the demand environment `S`. -/
def rQFamilyCost (S : DemandSpace lam) (L h p K : ℝ) : ℝ≥0∞ :=
⨅ π ∈ rQFamily S L, π.avgCost L h p K
/-- `inf_{π ∈ Π_S} C(π)` at zero setup cost on the demand environment `S`. -/
def baseStockFamilyCost (S : DemandSpace lam) (L h p : ℝ) : ℝ≥0∞ :=
⨅ π ∈ baseStockFamily S L, π.avgCost L h p 0
open Classical in
/-- `π` is a policy returned by the selection rule of Corollary 1 for normalized data
`(μ, a, k)` and base-stock level `Sstar`: if `Sstar ≥ 1` and `U_μ(a) + b_k < a`, it follows the
`(Sstar - 1, Q_k)` rule; otherwise it is the no-order policy. -/
def IsSelectedPolicy {S : DemandSpace lam} (L μ a k : ℝ) (Sstar : ℕ) (π : Policy S) : Prop :=
if 1 ≤ Sstar ∧ minBaseStockCost μ a + batchSurcharge k < a then
IsRQPolicy L (Sstar - 1) (lotSize k) π
else π = noOrderPolicy S
end LostSalesRQ