【正文】 運 籌 學 時間參數(shù)圖解 . 解上例： 計算事項 ? ? ? 時間參數(shù) ? ? ? ? 解上例：計算事項時間參數(shù)TES TLS TEF TLF TES TLS TEF TLS r(i,j) R（ i,j） A4 B6 C6 G7 D7 E5 F9 H4 I 8 0 0 4 7 6 13 22 20 28 28 20 24 13 6 關鍵路線：由總時差為零的工序構成 B D G I t（ i,j) t（ j,k) 管 理 運 籌 學 ? 解上例 計算工序時間參數(shù) 工序 i j t(i,j) ES EF LS LF R r A ? ? 4 0 4 3 7 3 0 B ? ? 6 0 6 0 6 0 0 C ? ? 6 4 10 7 13 3 3 D ? ? 7 6 13 6 13 0 0 E ? ? 5 6 11 19 24 13 11 F ? ? 9 13 22 15 24 2 0 G ? ? 7 13 20 13 20 0 0 H ? ? 4 22 26 24 28 2 2 I ? ? 8 20 28 20 28 0 0 管 理 運 籌 學 60 167。 5 車間作業(yè)計劃模型 管 理 運 籌 學 基本概念 ? 杜邦公司 — 關鍵路線法 CPM 確定型 ? 美國海軍武器局 — 計劃評審技術 PERT ? 網(wǎng)絡圖（有向賦權圖）的構成 ? 結點，也稱事項，一道工序的開始或結束 ? 工序（?。?，相對獨立的活動，消耗資源 ? 虛工序，只表示銜接關系，不消耗資源 ? 工序時間（權），完成工序的時間消耗 167。在表上劃去零件 j的所在行，回到步驟 1。 從例 2中我們可以歸納出關于兩臺機器 n個零件的排序問題，使得全部 任務總的時間 最短的排序算法。 這樣就得到了最優(yōu)加工順序： 5， 3， 4， 1， 2。 零件 車床 （第一工序） 磨床 （第二工序） 零件 車床 （第一工序） 磨床 （第二工序） 1 2 3 4 5 表 2 管 理 運 籌 學 52 同樣，下一個最短加工時間為 1，這是車床加工零件 3的所需時間，故 把零件 3排在第二位上，同時把零件 3所在的行劃去。 下一個最短加工時間為 ，這個加工時間是車床（第一工序）加工零件 5的所需時間，故 把零件 5排在加工順序的第一位上，同時把表中的零件 5所在的行劃去。 接著，我們又找到最短加工時間為 ，這一時間與磨床（第二工序）有關，我們把 磨床加 工時間為 1放到除第五外的加工順序的末尾，即第四位加工，同時把 表中的零件 1所在 的行劃去。 5 車間作業(yè)計劃模型 尋找例 2的最優(yōu)解：我們在表 125中找到所列出的最短加工時間是 ,它是第二道工序磨床 加工零件 2的所需時間，由于這個時間與磨床有關，故我們把零件 2放在加工順序的末尾，即第五位，并在表中劃去零件 2 所在行。 為了減少磨床的停工待料，我們應該一方面把在車床上加工時間越短的零 件越早加工，減少磨床等待的時間；另一方面把在磨床上加工時間越長的 零件越晚加工，以便充分利用前面的時間，這樣我們就得到了使完成全部 零件加工任務所需總時間最少的零件排序方法。 零件 車床 磨床 零件 車床 磨床 1 2 3 4 5 管 理 運 籌 學 50 167。 如果這些零件在車床上和磨床上加工順序都為 1， 2， 3， 4， 5。 5 車間作業(yè)計劃模型 二、兩臺機器、 n個零件 例 ，這些零件要求先在車床上車削，然后再在 磨床上加工，每臺機器上各零件加工時間如表 125所示。 對于某種加工順序，我們知道安排在第 j位加工的零件在車間里總的停留時間為Tj ， Tj = 可知這六個零件的停留時間為： T1 + T2 + T3 + T4 + T5 + T6 ＝ P1 + ( P1 + P2 ) + (P1 + P2 + P3 ) + (P1 + P2 + P3 + P4 ) + (P1 + P2 + P3 + P4 + P5) + (P1 + P2 + P3 + P4 + P5 + P6 ) ＝ 6 P1 + 5 P2 + 4P3 + 3P4 + 2P5 + P6. 那么各個零件平均停留時間為 從上式可知，對于一臺機器 n個零件的排序問題，只要系數(shù)越大，配上加工時間越少的，即按照加工時間排出加工順序，加工時間越少的零件排在越前面，加工時間越多的零件排在越后面，可使各個零件的平均停留時間為最少。 應該按照什么樣的加工順序來加工這六個零件，才能使得這六個零 件在車間里停留的平均時間為最少？ 零件 加工時間（小時） 零件 加工時間（小時） 1 2 3 4 5 6 管 理 運 籌 學 48 167。 管 理 運 籌 學 47 167。 我們把例 6的數(shù)據(jù)代入以上線性規(guī)劃模型，用“管理運籌學軟件”，馬上得到以下的結果： f12=5， f14=5， f23=2，f25=3， f43=2， f46=1， f47=2， f35=2， f36=2， f57=5， f67=3。其后面幾個約束條件表示對每一條弧(vi,vj)的流量 fij要滿足流量的可行條件，應小于等于弧 (vi,vj)的容量 cij，并大于等于零，即 0≤ fij≤ cij。 1 , 2 , 712ij ijijm ax F = f ff f ff f f ff f f ff f ff f ff f f f ff c i jf i j???? ? ?? ? ?????? ? ? ?? ? ?? ? ?目 標 函 數(shù) ：約 束 條 件 ：管 理 運 籌 學 46 167。 4 最大流問題 我們可以為此例題建立線性規(guī)劃數(shù)學模型： 設弧 (vi,vj)上流量為 fij，網(wǎng)絡上的總的流量為 F，則有： ? ?? ?1412 23 2514 43 46 4723 43 35 3625 35 5736 46 6757 67 47 12 14, 1 , 2 , , 6 。 cij的單位為萬加侖 /小時。 最大流的數(shù)學模型 例 6 某石油公司擁有一個管道網(wǎng)絡，使用這個網(wǎng)絡可以把石油從采地運送到一些銷售點，這個網(wǎng)絡的一部分如下圖所示。 v1 3 3 1 7 2 8 5 4 10 3 4 v7 v6 v5 v4 v2 v3 管 理 運 籌 學 44 167。 解：此問題實際上是求最小生成樹，這在例中已經(jīng)求得，也即按照圖的 (f)設計，可使此網(wǎng)絡的總的線路長度為最短，為 19百米。 3 最小生成樹問題 例 用破圈算法求圖（ a）中的一個最小生成樹 v1 3 3 1 7 2 8 5 4 10 3 4 v7 v6 v5 v4 v2 v1 3 3 1 7 2 8 5 4 3 4 v7 v6 v5 v4 v2 v1 3 3 7 2 5 4 3 4 v7 v6 v5 v4 v2 v3 v3 v3 1 v1 3 3 7 2 4 3 4 v7 v6 v5 v4 v2 v3 1 v1 3 3 7 2 3 4 v7 v6 v5 v4 v2 v3 1 v1 3 3 7 2 3 v7 v6 v5 v4 v2 v3 1 (a) (b) (c) (d) (e) (f) 管 理 運 籌 學 43 167。 如果所余下的圖已不包含圈，則計算結束，所余下的圖即為最小生成樹，否則返回第 1步。 3 最小生成樹問題 求解最小生成樹的破圈算法 算法的步驟： 在給定的賦權的連通圖上任找一個圈。 最小生成樹問題就是指在一個賦權的連通的無向圖 G中找出一個生成樹，并使得這個生成樹的所有邊的權數(shù)之和為最小。在圖中， (b)和 (c)都是 (a)的生成子圖。 v1 v2 v3 v4 v5 v6 v7 v8 v9 v1 v2 v3 v5 v8 v7 v6 v4 v1 v2 v3 v4 v5 v7 v6 v8 v9 (a) (b) (c) 管 理 運 籌 學 40 167。 3 最小生成樹問題 ? 樹是圖論中的重要概念，所謂樹就是一個無圈的連通圖。 由表知，設備使用三年后應當更新。 2 最短路問題 例的解： 將問題轉化為最短路問題，如下圖： 用 vi表示“第 i年年初購進一臺新設備” ,弧 （ vi,vj）表示第 i年年初購進的設備一直使用到第 j年年初。 設 bi 表示設備在第 i 年年初的購買費 ,ci 表示設備使用 i 年后的維修費 , V={v1, v2, … , v6},點 vi表示第 i 年年初購進一臺新設備 ,虛設一個點 v6表示第 5年年底 . E ={vivj | 1≤i＜ j≤6}. 167。若已知設備在各年的購買費，及不同機器役齡時的殘值與維修費。 2 最短路問題 例 2最終解得： 最短路徑 v1 v3 v5 v6 v7，每點的標號見下圖 （ 0,s） V1 （甲地） 15 17 6 2 4 4 3 10 6 5 (13,3) v2 (22,6) V7 （乙地） V5 (14,3) V6 (16,5) V3 (10,1) V4 (18,5) 管 理 運 籌 學 例 設備更新問題 某工廠使用一臺設備，每年年初工廠要作出決定：繼續(xù)使用，購買新的？如果繼續(xù)使用舊的，要負維修費；若要購買一套新的，要負購買費。只要在算法中把從已標號的點到未標號的點的弧的集合改成已標號的點到未標號的點的邊的集合即可?？梢园褵o向圖的每一邊（ vi,vj）都用方向相反的兩條?。?vi,vj）和（ vj,vi）代替，就化為有向圖，即可用 Dijkstra算法來求解。權數(shù)表示兩地間公路的長度（單位：公里）。 最短路問題 管 理 運 籌 學 32 167。 2 最短路問題 例 1 求下圖中 v1到 v6的最短路 解：采用 Dijkstra算法，可解得最短路徑為 v1 v3 v4 v6 各點的標號圖如下： v2 3 5 2 7 5 3 1 5 1 2 v1 v6 v5 v3 v4 (3,1) v2 3 5 2 7 5 3 1 5 1 2 V1 （ 0,s) v5 (8,4) v6 (2,1) v3 (3,3) v4 管 理 運 籌 學 31 網(wǎng)絡最短路線問題： 尋找網(wǎng)絡中從起點 v1 到終點 vn 的最短路線。利用 vi 到 vj 的一步距離求出 vi 到 vj 的兩步距離再求出 vi 到 vj 的四步距