(4.13), p. 11 — e_{i+1} ≥ Σ_{t_B} p(t_B) max[e_1 + t_1, …, e_i + t_i]
ProvedFulkersonPERT.Bounds.sum_max_add_le_expectedLengthLet be a project network with events and let bundle distributions be given, each a probability distribution on its finite support, the bundles being independent. Let be the expected critical path lengths (3.7). Then for every event ,
This is the inequality (4.13): the expected critical path length to dominates the expectation, over the bundle of alone, of the maximum of the expected lengths to the predecessors plus the arc lengths. It is the step where independence between bundles is used; the example of Fig. 4.2 shows that it fails for correlated bundles.
Formalization Note Fulkerson's node is the event ; is the length of arc in the bundle vector . Arc lengths may be negative (footnote, p. 4).
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 sum_max_add_le_expectedLength {n : ℕ} (N : ProjectNetwork n) (D : BundleDist n)
(hD : D.IsProb) (j : Fin (n + 1)) (hj : j ≠ 0) :
∑ v ∈ D.supp j, D.p j v *
(N.pred j).sup' (N.pred_nonempty hj) (fun i => expectedLength N D i + v i) ≤
expectedLength N D j := by sorry
end FulkersonPERT.Bounds
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.