整數(shù)規(guī)劃的含義(編輯修改稿)
2025-01-19 10:24 本頁面
【文章內(nèi)容簡介】 點集、弧集 OR3 23 圖的基本概念 (續(xù) ) ?以點 u為端點的邊的條數(shù)，叫做點 u的 次 次為 1的點叫做 懸掛點 ；次為 0的點叫做孤立點 ；次為奇數(shù)則稱 奇點 ；次為偶數(shù)則稱 偶點。 ?點弧交替序列稱為 鏈 ；閉合的鏈稱為 圈 ?首尾相接的鏈稱為 路 ；閉合的路稱 回路 ?任意兩點之間都有邊相連，稱為 連通圖 OR3 24 樹 ?無圈的連通圖稱之為 樹 ?賦權(quán)無向圖 G=（ V， E）的最小基干稱為最小支撐樹 ?賦權(quán)有向圖 D=（ V， A）， 從始點到終點的權(quán)值最小的路稱為 最短路 OR3 25 最短路問題 ?例 6 某交通網(wǎng)絡(luò)如下圖，求 v1到 v8的最短路線 ?解：用雙標號法 v1 v2 v4 v3 v5 v6 v7 v8 6 3 1 2 2 1 6 10 4 3 10 4 4 6 v1 V2(v3,5) V3(v1,3) V4(v1,1) V5(v2,6) V6(v5,10) V7(v5,9) V8(v5,12) 6 3 1 2 2 1 6 10 4 10 4 3 6 4 V2(v1,6） OR3 26 最大流問題 ?引例：如下輸水網(wǎng)絡(luò)，南水北調(diào)工程，從 vs到 vt送水，弧旁數(shù)字前者為管道容量，后者為現(xiàn)行流量，如何調(diào)整輸水最多？ vs vt v2 v1 v4 v3 (3,3) (5,1) (1,1) (4,3) (1,1) (2,2) (3,0) (2,1) (5,3) OR3 27 最大流問題的相關(guān)概念 ? 網(wǎng)絡(luò)：給定了弧的容量 C（ vi,vj）的有向圖 D=（ V， A， C）叫做一個 網(wǎng)絡(luò) 。 ? 可行流：各點流入量 =流出量，且 vs的流出量=vt的流入量，這樣的流稱之為 可行流 ? 截集：分離始點 vs和終點 vt的弧的集合，叫做截集 ? 截量：截集的容量叫做 截量 ? 增廣鏈：一條從到的鏈，前向弧上可增加，后向弧上可減少，則稱此鏈為 增廣鏈 OR3 28 求最大流的方法 ?方法很簡單：首先找到一條增廣鏈，沿此進行最大可能調(diào)整，再找增廣鏈，再調(diào)整，直到?jīng)]有增廣鏈。 ?尋找增廣鏈的標號法：先給 vs標號（ 0，+∞） ,而后依次審查各條?。?vi,vj）：對前向弧，飽和否？不飽和，給 vj點標號（ vi， l(vj))。對后向弧，可否減少？可，給vj標號（ vi, l(vj) ） ,直到給 vt標上號，就得到了增廣鏈。 OR3 29 解水網(wǎng)最大流問題 . vs V2 (0, +∞) V1 (3,3) (5,1) (1,1) (4,3) (1,1) (2,2) (3,0) (5,3) (2,1) V4 V3 Vt (vs,4) (v1,1) (v2,1) (v3,1) (v2,1) OR3 30 此題最大流圖 ?沿增廣鏈進行調(diào)整，前向弧增加 l(vj)，后向弧減少 l(vj) vs V2 V1 V3 V4 Vt (3,3) (5,2) (4,3) (1,0) (1,0) (2,2) (3,0) (5,3) (2,2) (0,+∞) (vs,3) OR3 31 習題： p312－ ，求最大流 ?給出任意可行流 ?找到一條增廣鏈 ?調(diào)整可行流 注 ：’＝ 1， ＝ 1， $＝ 2，*=1 vs v1 v2 v3 v4 v5 vt （ 4,3）’ （ 10,4） $* （ 3,2） （ 1,1） （ 3,2）’ （ 3,2） * （ 4,2） $ （ 5,3） * （ 4,3）’ （2,2） （ 7,6）’ （ 8,3） $* (0,+∞) (vs,3) OR3 32 第九章 網(wǎng)絡(luò)計劃 ?～是用網(wǎng)絡(luò)分析的方法編制的計劃 ?杜邦公司 —關(guān)鍵路線法 CPM 確定型 ?美國海軍武器局 —計劃評審技術(shù) PERT ?網(wǎng)絡(luò)圖（有向賦權(quán)圖）的構(gòu)成 ?結(jié)點，也稱事項，一道工序的開始或結(jié)束 ?工序（?。?，相對獨立的活動，消耗資源 ?虛工序，只表示銜接關(guān)系，不消耗資源 ?工序時間（權(quán)），完成工序的時間消耗 OR3 33 ? 避免循環(huán)、不留缺口 ? 一一對應(yīng)：一道工序用兩個事項表示 ? 3 、從左向右依次展開 例： 工 序 A B C D E F G H I 緊前工序 A B B C、 D C、 D E、 F G 工序時間 4 6 6 7 5 9 7 4 8 ? ? ? ? ? ? ? A,4 B,6 C,6 D,7 E,5 G,7 F,9 H,4 I,8 OR3 34 關(guān)鍵路線法－－ CPM 什么是關(guān)鍵路線？ 作業(yè)時間 t（ i， j），經(jīng)驗數(shù)據(jù)、統(tǒng)計數(shù)據(jù) 事項最早時間 TE(j)＝ max{TE(i)+ t（ i， j） } 到齊上課，最后到者決定最早開課時間 事項最遲時間 TL(i)＝ min{TL(j) t（ i， j） } 保證 12點吃飯，路最遠者決定最遲下課時間 工序最早可能開工時間 TES(i,j)＝ TE(i) = max{TES(h,i)+ t（ h,i ） } 工序最早可能完工時間 TEF(i,j)＝ TES(i,j)+ t（ i， j） h i j OR3 35 . 工序最遲必須開工時間 TLS（ i,j)＝ TL(j)－ t（ i,j)＝ min{TLs(j,k) t（ i， j） } 工序最遲必須完工時間 TLF（ i,j)＝ TL(j)＝ TLS（ i,j)+ t（ i,j) 工序總時差：
教學課件相關(guān)推薦
鄂ICP備17016276號-1