Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Meaning of the theorem, p. 869 — with S₀ = Sₙ = 0 and Tᵢ > 0, D has exactly 2ⁿ⁻¹ vertices, the all-or-nothing modes

Proved
SimpsonInv.Vertex.vertices_model

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

all-or-nothingextreme-pointinventoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polyhedron

Consider Simpson's model with S0=Sn=0S_0 = S_n = 0S0​=Sn​=0 and positive processing times T1,…,Tn>0T_1, \dots, T_n > 0T1​,…,Tn​>0, with n=m+1n = m + 1n=m+1 operations, and let

D={(S1,…,Sn−1):Si≥0, Si−1−Si+Ti≥0}.D = \{ (S_1, \dots, S_{n-1}) : S_i \ge 0,\ S_{i-1} - S_i + T_i \ge 0 \}.D={(S1​,…,Sn−1​):Si​≥0, Si−1​−Si​+Ti​≥0}.

Then the vertices (extreme points) of DDD are exactly the points of DDD at which every service time is either 000 or Si−1+TiS_{i-1} + T_iSi−1​+Ti​:

ext⁡D={S∈D:∀i∈{1,…,n−1}, Si=0 or Si=Si−1+Ti},\operatorname{ext} D = \{ S \in D : \forall i \in \{1, \dots, n-1\},\ S_i = 0 \ \text{or}\ S_i = S_{i-1} + T_i \},extD={S∈D:∀i∈{1,…,n−1}, Si​=0 or Si​=Si−1​+Ti​},

and there are exactly 2n−12^{n-1}2n−1 of them.

This is why a manager "has to examine only 2n−12^{n-1}2n−1 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 2m≠02^m \ne 02m=0. The hypothesis Ti>0T_i > 0Ti​>0 is the paper's "the processing times TiT_iTi​ are always positive" (p. 868), and S0=Sn=0S_0 = S_n = 0S0​=Sn​=0 its standing choices on p. 865. Lean index jjj is the paper's Sj+1S_{j+1}Sj+1​.

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
  • 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