Theorem 1: zero-setup and full-cost guarantees, tightness of
ProvedLostSalesRQ.main_theoremThis is Theorem 1 of the paper, in full. Let be the demand rate, lead time, holding cost rate, lost-sales penalty and fixed ordering cost of the continuous-review lost-sales system with unit Poisson demand, let be the long-run average cost of an admissible policy and the infimum over all admissible policies.
- Full-cost guarantee. For every nonnegative and every demand environment of rate ,
- Zero-setup guarantee. When , on every demand environment.
- The algorithm at . For , with and , let be any integer minimizing . On every demand environment a policy selected by the rule of Corollary 1 exists, and every such policy is an integer base-stock policy (possibly level ) whose cost equals .
- Tightness. In normalized parameters,
- The ratio is well defined. For , .
The constant is the root of . The theorem gives the first constant-factor guarantee valid at every finite parameter vector for this model with positive lead time and arbitrary fixed ordering costs.
Formalization Note Policy costs are evaluated on an arbitrary demand environment (a probability space with a filtration carrying the Poisson demand count), while is the infimum over all environments and all admissible policies on them. Costs and are in , so the inequalities are meaningful even when (for instance , or ), where the infima need not be attained. The ratio in item 4 is division in of by .
import Definitions.Def_LostSalesRQ_model import Definitions.Def_LostSalesRQ_lower_curve
namespace LostSalesRQ
theorem main_theorem :
(∀ lam L h p K : ℝ, 0 ≤ lam → 0 ≤ L → 0 ≤ h → 0 ≤ p → 0 ≤ K →
∀ S : DemandSpace lam,
rQFamilyCost S L h p K ≤
ENNReal.ofReal ((Real.sqrt 2 + Real.sqrt 6) / 2) * OPT lam L h p K) ∧
(∀ lam L h p : ℝ, 0 ≤ lam → 0 ≤ L → 0 ≤ h → 0 ≤ p →
∀ S : DemandSpace lam,
baseStockFamilyCost S L h p ≤ ENNReal.ofReal (Real.sqrt 2) * OPT lam L h p 0) ∧
(∀ lam L h p : ℝ, 0 < lam → 0 ≤ L → 0 < h → 0 ≤ p →
∀ S : DemandSpace lam, ∀ Sstar : ℕ,
(∀ j : ℕ, baseStockCost (lam * L) (p * lam / h) Sstar ≤
baseStockCost (lam * L) (p * lam / h) j) →
(∃ π : Policy S, IsSelectedPolicy L (lam * L) (p * lam / h) 0 Sstar π) ∧
∀ π : Policy S, IsSelectedPolicy L (lam * L) (p * lam / h) 0 Sstar π →
π ∈ baseStockFamily S L ∧ π.avgCost L h p 0 = baseStockFamilyCost S L h p) ∧
(⨆ (μ : ℝ) (a : ℝ) (_ : 0 < μ ∧ 0 < a),
ENNReal.ofReal (minBaseStockCost μ a) / OPTk μ a 0) = ENNReal.ofReal (Real.sqrt 2) ∧
(∀ μ a : ℝ, 0 < μ → 0 < a →
ENNReal.ofReal (lowerCurve μ a) ≤ OPTk μ a 0 ∧ min 1 a ≤ lowerCurve μ a ∧
0 < min 1 a) := by sorry
end LostSalesRQConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.