(4.4), p. 10 — g_i ≤ f_i ≤ e_i for every node of a PERT network with bundle-independent arc lengths
ProvedFulkersonPERT.Bounds.expected_critical_path_boundsLet be a PERT network with events : origin , terminal , every arc with , and every event on a path from origin to terminal. For every event let the lengths of the arcs entering (the bundle ) have a finite joint distribution on a finite set of bundle vectors, the distributions of distinct bundles being independent. Let
- be the expected length of a critical path to , where and is the longest-path length from the origin to under the arc lengths (3.7);
- be the critical path length to when every arc has its expected length (3.13);
- and for (4.2).
Then for every event ,
The mean-length estimate , the classical PERT figure, is thus a lower bound for the expected project duration, and Fulkerson's numbers , computable bundle by bundle, are a lower bound that is at least as good.
Formalization Note Fulkerson's node is event , so his ranges over all events. The maximum over missing arcs is ignored (Finset.sup' over the arcs that exist). There is one arc per ordered pair of events. Arc lengths may be negative: the page assumes nonnegativity but its footnote on p. 4 says this is not essential in §3–§4, so the statement is the more general one. The referenced project network requires origin and terminal to be distinct ().
import Mathlib import Definitions.Def_CriticalPath_Events_ProjectNetwork import Definitions.Def_CriticalPath_Events_EventTimes import Definitions.Def_FulkersonPERT_Bounds_Model
namespace FulkersonPERT.Bounds
open CriticalPath.Events
theorem expected_critical_path_bounds {n : ℕ} (N : ProjectNetwork n) (D : BundleDist n)
(hD : D.IsProb) :
∀ i : Fin (n + 1), meanCPL N D i ≤ fNum N D i ∧ fNum N D i ≤ expectedLength N D i := by sorry
end FulkersonPERT.Bounds
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.