Section 3.4.3, p. 65 — every greedy marginal-analysis solution is optimal for Problem 5 at its own budget
ProvedServiceParts.StockLevels.greedy_fill_rate_optimalConsider item types, item with simple Poisson demand of rate , mean repair time , unit cost and fill rate . Problem 5 (3.41) is
Run the greedy procedure: start from and repeatedly raise by one the stock level of an item maximizing
with ties broken arbitrarily. Let be the stock vector after steps. Then for every , is an optimal solution of Problem 5 with budget
it satisfies the floor constraints, and every integer vector with and has average fill rate at most that of .
The case is the book's displayed solution; the book states that continuing in this manner the greedy algorithm finds the optimal solution for the budgets it generates.
Formalization Note The greedy procedure is a relation on sequences, so the statement covers every tie-breaking rule.
import Mathlib import Definitions.Def_ServiceParts_StockLevels_Basic import Definitions.Def_ServiceParts_StockLevels_CompoundPoissonDemand import Definitions.Def_ServiceParts_StockLevels_Problems
namespace ServiceParts.StockLevels
theorem greedy_fill_rate_optimal {ι : Type*} [Fintype ι] [DecidableEq ι] [Nonempty ι]
(lam tbar c : ι → ℝ) (hlam : ∀ i, 0 < lam i) (htbar : ∀ i, 0 < tbar i)
(hc : ∀ i, 0 < c i) (seq : ℕ → ι → ℕ) (hseq : IsGreedySeq lam tbar c seq) (k : ℕ) :
(∀ i, ⌊lam i * tbar i⌋₊ ≤ seq k i) ∧
∀ s : ι → ℕ, (∀ i, ⌊lam i * tbar i⌋₊ ≤ s i) →
∑ i, c i * (s i : ℝ) ≤ ∑ i, c i * (seq k i : ℝ) →
avgFillRate lam tbar s ≤ avgFillRate lam tbar (seq k) := by sorry
end ServiceParts.StockLevels
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.