【正文】 管 理 運(yùn) 籌 學(xué) 35 167。 把所有弧的權(quán)數(shù)計(jì)算如下表： v1 v2 v3 v4 v5 v6 1 2 3 4 5 6 1 16 22 30 41 59 2 16 22 30 41 3 17 23 31 4 17 23 5 18 6 管 理 運(yùn) 籌 學(xué) ?????ijkkiji cbvvF1)( 若每年購(gòu)置一臺(tái)新設(shè)備，則購(gòu)置費(fèi)為：11+11+12+12+13=59，每年的維修費(fèi)為 5元， 共 59+5*5=84. 若在 1， 2， 3年購(gòu)置一臺(tái)新設(shè)備，則購(gòu)置費(fèi)為：11+12+13=36，每年的維修費(fèi)為（ 5+6） +（ 5+6） +5=27，共 36+27=63. 設(shè)備使用一年后就更新則不劃算。 管 理 運(yùn) 籌 學(xué) 這樣上述設(shè)備更新問(wèn)題就變?yōu)椋涸谟邢蛸x權(quán)圖 G = (V, E, F )(圖解如下 )中求 v1到 v6的最短路問(wèn)題 . 31)865(13)(30)865(11)(,59)1811865(11)(635261?????????????????vvvvvv???管 理 運(yùn) 籌 學(xué) 由實(shí)際問(wèn)題可知 ,設(shè)備使用三年后應(yīng)當(dāng)更新 ,因此刪除該圖中 v1到 v5 ,v1到 v6 ,v2到 v6的連線；又設(shè)備使用一年后就更新則不劃算 ,因此再刪除該圖中 v1v2 ,v2v3 ,v3v4 ,v4v5 ,v5v6 五條連線后得到 從上圖中容易得到 v1到 v6只有兩條路： v1v3v6（費(fèi)用 22+31） 和 v1v4v6 （費(fèi)用 22+31） . 而這兩條路都是 v1到 v6的最短路 . 管 理 運(yùn) 籌 學(xué) 39 167。 圖中， (a)就是一個(gè)樹，而 (b)因?yàn)閳D中有圈所以就不是樹， (c)因?yàn)椴贿B通所以也不是樹。 3 最小生成樹問(wèn)題 給了一個(gè)無(wú)向圖 G=(V,E)，我們保留 G的所有點(diǎn)，而刪掉部分 G的邊或者說(shuō)保留一部分 G的邊，所獲得的圖 G，稱之為 G的生成子圖。 如果圖 G的一個(gè)生成子圖還是一個(gè)樹，則稱這個(gè)生成子圖為生成樹，在圖中， (c)就是 (a)的生成樹。 (a) (b) (c) 管 理 運(yùn) 籌 學(xué) 41 167。 在所找的圈中去掉一個(gè)權(quán)數(shù)最大的邊（如果有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其中一條）。 管 理 運(yùn) 籌 學(xué) 42 167。 3 最小生成樹問(wèn)題 例、某大學(xué)準(zhǔn)備對(duì)其所屬的 7個(gè)學(xué)院辦公室計(jì)算機(jī)聯(lián)網(wǎng)，這個(gè)網(wǎng)絡(luò)的可能聯(lián)通的途徑如下圖，圖中 v1,…,v 7 表示 7個(gè)學(xué)院辦公室，請(qǐng)?jiān)O(shè)計(jì)一個(gè)網(wǎng)絡(luò)能聯(lián)通 7個(gè)學(xué)院辦公室，并使總的線路長(zhǎng)度為最短。 “管理運(yùn)籌學(xué)軟件”有專門的子程序可以解決最小生成樹問(wèn)題。 4 最大流問(wèn)題 ? 最大流問(wèn)題：給一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容量，在不超過(guò)每條弧的容量的前提下，求出從發(fā)點(diǎn)到收點(diǎn)的最大流量。由于管道的直徑的變化，它的各段管道（ vi,vj）的流量 cij（容量）也是不一樣的。如果使用這個(gè)網(wǎng)絡(luò)系統(tǒng)從采地 v1向銷地 v7運(yùn)送石油，問(wèn)每小時(shí)能運(yùn)送多少加侖石油？ v5 6 3 5 2 2 2 4 1 2 6 3 v1 v2 v7 v4 v3 v6 管 理 運(yùn) 籌 學(xué) 45 167。 1 , 2 , 70 , 1 , 2 , , 6 。 4 最大流問(wèn)題 在這個(gè)線性規(guī)劃模型中，其約束條件中的前 6個(gè)方程表示了網(wǎng)絡(luò)中的流量必須滿足守恒條件，發(fā)點(diǎn)的流出量必須等于收點(diǎn)的總流入量；其余的點(diǎn)稱之為中間點(diǎn)，它的總流入量必須等于總流出量。我們把滿足守恒條件及流量可行條件的一組網(wǎng)絡(luò)流 {fij}稱之為可行流，（即線性規(guī)劃的可行解），可行流中一組流量最大（也即發(fā)出點(diǎn)總流出量最大）的稱之為最大流（即線性規(guī)劃的最優(yōu)解）。最優(yōu)值（最大流量） =10。 5 車間作業(yè)計(jì)劃模型 一、一臺(tái)機(jī)器、 n個(gè)零件的排序問(wèn)題 例 ，常常出現(xiàn)很多零件同時(shí)要求這臺(tái) 磨床加工的情況，現(xiàn)有六個(gè)零件同時(shí)要求加工，這六個(gè)零件加工所需時(shí)間 如下表所示。 5 車間作業(yè)計(jì)劃模型 ??ji iP1??ji iP1623456 654321 pppppP ????? 例 1解：如果我們用 Pi表示安排在第 i位加工的零件所需的時(shí)間，用 Tj表示安排在第 j位加工的零件在車間里總的停留時(shí)間，則有 Tj = P1 + P2 +…+ Pj1 + Pj = 不同的加工順序得到不同的各零件的平均停留時(shí)間，如何得到一個(gè)使得各零件的平均停留時(shí)間最少的排序呢？這就是我們最后要解決的優(yōu)化問(wèn)題，而且我們要設(shè)法找到一種簡(jiǎn)便的算法。 管 理 運(yùn) 籌 學(xué) 49 167。 表 1 應(yīng)該如何安排這五個(gè)零件的先后順序才能使完成這五個(gè)零件的總的加工時(shí)間為最少？ 解：由于每個(gè)零件必須先進(jìn)行車床加工，再進(jìn)行磨床加工，所以在車床上加 工零件的順序與在磨床上加工零件的順序是一樣的。我們用圖 121 中的線條圖來(lái)表示各零件加工的開始時(shí)間與完成時(shí)間，這種圖是由一根時(shí)間軸和 車床、磨床在每個(gè)時(shí)間段的狀況的圖形所構(gòu)成。 5 車間作業(yè)計(jì)劃模型 圖 1 從上圖中我們可以看出，加工時(shí)間的延長(zhǎng)主要是由于磨床的停工待料 造成的，只要減少磨床的停工待料的時(shí)間就能減少整個(gè)加工任務(wù)的總時(shí)間。 1 2 3 4 5 1 車床 磨床 2 3 4 5 0 10 管 理 運(yùn) 籌 學(xué) 51 167。如表 126中紅色線條所示。如表 126中黃色線條所示。如表 126中藍(lán)色線條所 示。如表 126中黑色線條 所示。一共只需 7個(gè)小時(shí)就能 完成全部加工。 在加工所需時(shí)間表上選出最短加工時(shí)間 tij，這是第 i工序加工 j零件所需時(shí)間，當(dāng) i=1時(shí)，將零件 j的順序盡量靠前，若 i=2時(shí)，將零件 j的順序盡量 靠后。 167。 6 統(tǒng)籌方法 管 理 運(yùn) 籌 學(xué) 網(wǎng)絡(luò)規(guī)則 ? 避免循環(huán)、不留缺口 ? 一一對(duì)應(yīng)：一道工序用兩個(gè)事項(xiàng)表示 ? 3 、從左向右依次展開 例： 工 序 A B C D E F G H I 緊前工序 A B B C、 D C、 D E、 F G 工序時(shí)間 4 6 6 7 5 9 7 4 8 ? ? ? ? ? ? A,4 B,6 D,7 E,5 F,9 H,4 I,8 C,6 G,7 管 理 運(yùn) 籌 學(xué) 關(guān)鍵路線法－－ CPM 時(shí)間參數(shù)運(yùn)算 什么是關(guān)鍵路線？ 作業(yè)時(shí)間 t（ i， j），經(jīng)驗(yàn)數(shù)據(jù)、統(tǒng)計(jì)數(shù)據(jù) 事項(xiàng)最早時(shí)間 TE(j)＝ max{TE(i)+ t（ i， j） } 到齊上課，最后到者決定最早開課時(shí)間 事項(xiàng)最遲時(shí)間 TL(i)＝ min{TL(j) t（ i， j） } 保證 12點(diǎn)吃飯，路最遠(yuǎn)者決定最遲下課時(shí)間 工序最早可能開工時(shí)間 TES(i,j)＝ TE(i) = max{TES(h,i)+ t（ h,i ） } 工序最早可能完工時(shí)間 TEF(i,j)＝ TES(i,j)+ t（ i， j） 管 理 運(yùn) 籌 學(xué) 工序最遲必須開工時(shí)間 TLS（ i,j)＝ TL(j)－ t（ i,j)＝ min{TLs(j,k) t（ i， j） } 工序最遲必須完工時(shí)間 TLF（ i,j)＝ TL(j)＝ TLS（ i,j)+ t（ i,j) 工序總時(shí)差：在不影響其緊后工序 最遲必須 開工時(shí)間的前提下，本工序可以推遲的時(shí)間 R（ i,j）＝ TLS(i,j)－ TES(i,j) ＝ TLF(i,j)－ TEF(i,j) ＝ min{TLS(j,k) } – TEF（ i,j） 工序單時(shí)差：在不影響其緊后工序 最早可能 開工時(shí)間的前提下，本工序可以推遲的時(shí)間 r （ i,j）＝ min{TES(j,k) } – TEF（ i,j） 管 理 運(yùn) 籌 學(xué) 計(jì)算關(guān)系式 ? 這些時(shí)間參數(shù)的關(guān)系可以用下圖表示工作的關(guān)系狀態(tài)。 6 統(tǒng)籌方法 統(tǒng)籌方法包括繪制計(jì)劃網(wǎng)絡(luò)圖、進(jìn)度安排、網(wǎng)絡(luò)優(yōu)化等環(huán)節(jié)，下面進(jìn) 行分別討論： 一、計(jì)劃網(wǎng)絡(luò)圖 統(tǒng)籌方法的第一步工作就是繪制計(jì)劃網(wǎng)絡(luò)圖，也就是將工序（或稱為 活動(dòng)）進(jìn)度表轉(zhuǎn)換為統(tǒng)籌方法的網(wǎng)絡(luò)圖。 表 3 工序代號(hào) 工序內(nèi)容 所需時(shí)間（天 ) 緊前工序 a b c d e 產(chǎn)品設(shè)計(jì)與工藝設(shè)計(jì) 外購(gòu)配套零件 外購(gòu)生產(chǎn)原料 自制主件 主配可靠性試驗(yàn) 60 15 13 38 8 a a c b,d 管 理 運(yùn) 籌 學(xué) 61 167?；? 表示一個(gè)工序（或活動(dòng)），弧的方向是從工序開始指向工序的結(jié)束，弧上 是各工序的代號(hào)，下面標(biāo)以完成此工序所需的時(shí)間（或資源）等數(shù)據(jù)，即 為對(duì)此弧所賦的權(quán)數(shù)． １ ２ ４ ５ ３ a b c d e 60 13 8 38 15 圖 4 管 理 運(yùn) 籌 學(xué) 62 167。 表 5 工序代號(hào) 所需時(shí)間（天） 緊前工序 工序代號(hào) 所需時(shí)間（天） 緊前工序 a b c d 60 15 13 38 － a a c e f g h 8 10 16 5 b，ｄ d d e，ｆ，ｇ 管 理 運(yùn) 籌 學(xué) 63 167。 為此我們?cè)O(shè)立虛工序。 1 5 2 6 4 3 a 60 b 15 8 e 10 13 d c 38 f 圖 5 管 理 運(yùn) 籌 學(xué) 64 167。 在統(tǒng)籌方法的網(wǎng)絡(luò)圖中不允許兩個(gè)點(diǎn)之間多于一條弧，因此增加了一個(gè)點(diǎn)和虛工序如圖 7。 6 統(tǒng)籌方法 在繪制統(tǒng)籌方法的網(wǎng)絡(luò)圖時(shí)，要注意圖中不能有缺口和回路 。 6 統(tǒng)籌方法 二、網(wǎng)絡(luò)時(shí)間與關(guān)鍵路線 在繪制出網(wǎng)絡(luò)圖之后，我們可以由網(wǎng)絡(luò)圖求出： 完成此工程項(xiàng)目所需的最少時(shí)間。 關(guān)鍵路線及其應(yīng)用的關(guān)鍵工序。 例 某公司裝配一條新的生產(chǎn)線，具體過(guò)程如表 10,求：完成此 工程的最少時(shí)間，關(guān)鍵路線及相應(yīng)的關(guān)鍵工序，各工序的最早開始時(shí)間和 非關(guān)鍵工序在不影響工程完成時(shí)間的前提下，其開始時(shí)間與結(jié)束時(shí)間可以 推遲多久。 6 統(tǒng)籌方法 表 10 工序代號(hào) 工序內(nèi)容 所需時(shí)間（天） 緊前工序 a b c d e f g h i j 生產(chǎn)線設(shè)計(jì) 外購(gòu)零配件 下料、鍛件 工裝制造 1 木模、鑄件 機(jī)械加工 1 工裝制造 2 機(jī)械加工 2 機(jī)械加工 3 裝配調(diào)試 60 45 10 20 40 18 30 15 25 35 / a a a a c d d,e g b,i,f,h 管 理 運(yùn) 籌 學(xué) 68 16