Meaning of the theorem, p. 869 — with S₀ = Sₙ = 0 and Tᵢ > 0, D has exactly 2ⁿ⁻¹ vertices, the all-or-nothing modes
ProvedSimpsonInv.Vertex.vertices_modelall-or-nothingextreme-pointinventoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polyhedron
Consider Simpson's model with and positive processing times , with operations, and let
Then the vertices (extreme points) of are exactly the points of at which every service time is either or :
and there are exactly of them.
This is why a manager "has to examine only possible modes": by THEOREM I the cheapest mode is one of these vertices.
Formalization Note Vertex means extreme point (Set.extremePoints ℝ D). The number of extreme points is Set.ncard, which also forces the set to be finite since . The hypothesis is the paper's "the processing times are always positive" (p. 868), and its standing choices on p. 865. Lean index is the paper's .
Preamble
import Mathlib import Definitions.Def_SimpsonInv_Vertex_Setting
Formal statement
namespace SimpsonInv.Vertex
theorem vertices_model {m : ℕ} (T : ℕ → ℝ) (hT : ∀ i ∈ Finset.Icc 1 (m + 1), 0 < T i) :
Set.extremePoints ℝ (dom (m := m) T 0 0) =
{S : Fin m → ℝ | ∀ j : Fin m, S j = 0 ∨ S j = extVec 0 0 S j.val + T (j.val + 1)} ∩
dom (m := m) T 0 0 ∧
(Set.extremePoints ℝ (dom (m := m) T 0 0)).ncard = 2 ^ m := by sorry
end SimpsonInv.Vertex
Source
Simpson, In-Process Inventories, Operations Research 6 (1958), p. 869, Meaning of the theorem; model conventions p. 865 and p. 868
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.