§4, p. 11 with (3.6) — the earliest-time recursion is the length of a longest path from the origin
ProvedFulkersonPERT.Bounds.earliest_isGreatest_pathLengthcritical-pathlongest-pathp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pert
Let be a project network with events and let be arbitrary arc lengths. For an event , let be given by the recursion and
Then is the greatest length of a path from the origin to : it is the length of some path from to , and every path from to has length at most .
Fulkerson defines in (3.6) as "the length of a longest or critical path from node 1 to node i", and uses the recursion in the proof of (4.4) on p. 11. This statement identifies the two.
Formalization Note Fulkerson's node is event . Paths are lists of events starting at and ending at , consecutive events joined by arcs; the path consisting of the origin alone has length . Arc lengths may be negative.
Preamble
import Mathlib import Definitions.Def_CriticalPath_Events_ProjectNetwork import Definitions.Def_CriticalPath_Events_EventTimes import Definitions.Def_FulkersonPERT_Bounds_Model
Formal statement
namespace FulkersonPERT.Bounds
open CriticalPath.Events
theorem earliest_isGreatest_pathLength {n : ℕ} (N : ProjectNetwork n)
(y : Fin (n + 1) → Fin (n + 1) → ℝ) (i : Fin (n + 1)) :
IsGreatest {L : ℝ | ∃ p : List (Fin (n + 1)), IsPathTo N p i ∧ L = pathLength y p}
(earliest N y i) := by sorry
end FulkersonPERT.Bounds
Source
Fulkerson, Expected Critical Path Lengths in PERT Networks, RAND Memorandum RM-3075-PR (1962), p. 5, (3.6); p. 11, §4, proof of (4.4), display before (4.11)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.