離散數(shù)學ch04圖論最短路徑與關鍵路徑-閱讀頁
2025-02-02 02:22本頁面
【正文】 度 為 ， 稱 此 頂 點 為 終 點 ；記 邊 帶 的 ， 它 一 般權(quán) 為 表 示 時 間 ；P ER TD則 稱 為 圖 . 最短路徑及關鍵路徑 關鍵路徑問題 —— PERT圖（計劃評審技術圖） 在 PERT圖中求關鍵路徑，就是從始點到終點的一條最長路徑，通過求各頂點的最早完成時間來 求關鍵路徑。a（ 7 ） 最短路徑及關鍵路徑 PERT圖 —— 最晚完成時間 ( ) ( )n n iTL v TE v i nv??由 定 義 可 知 ， ； 的 最 晚 完 成 時 間由 下時 ，面 公 式 計 算 ：()( ) m a x { ( ) }, 1 , 2 , 3 , . . . , 1 .j D ii i i jvvTL v TL v w i n???? ? ? ?1( ) .ni i ivvv v T L v在 保 證 終 點 的 最 早 完 成 時 間 不 增 加 的 條 件 下 ， 自最 遲 到 達 的 時 間 稱 為 的 最 晚 完 成 時 間 ， 記 作b（ 7 ） 最短路徑及關鍵路徑 PERT圖 —— 緩沖時間 0, ( ) ( )( ) ( )iii i iT L v T E vL T E vvTv ? ??。 最短路徑及關鍵路徑 解 ： 各 點 最 早 完 成時 間 用 公 式 (7a) 計 算 ：3412( ) 0 。( ) m a x{ 0 2 , 1 0 } 2 。T E vT E vT E vT E v?? ? ?? ? ? ?? ? ? ?5678( ) m a x{ 1 3 , 4 4 } 8 。( ) m a x{ 1 4 , 2 4 } 6 。( ) m i n{ 12 6 } 6 。( ) m i n{ 11 1 } 10 。( ) m i n{ 6 2 , 11 4 , 6 4 } 2 。( ) m i n{ 2 1 , 2 2 , 6 3 } 0.T L vT L vT L vT L v? ? ?? ? ? ? ?? ? ? ? ?? ? ? ? ? 最短路徑及關鍵路徑 計 算 各 點 緩 沖 時 間 ：1 3 7 82456( ) ( ) ( ) ( ) 0 。( ) 6 4 2 。( ) 1 1 9 2 .T S v T S v T S v T S vT S vT S vT S vT S v? ? ? ?? ? ?? ? ?? ? ?? ? ?1 3 7 8 .vv vv關 鍵 路 徑 為 最短路徑及關鍵路徑
法律信息相關推薦
鄂ICP備17016276號-1