運(yùn)籌學(xué)課件:第5章 圖與網(wǎng)絡(luò)分析

上傳人:努力****83 文檔編號:48742224 上傳時(shí)間:2022-01-14 格式:DOC 頁數(shù):28 大小:1.88MB
收藏 版權(quán)申訴 舉報(bào) 下載
運(yùn)籌學(xué)課件:第5章 圖與網(wǎng)絡(luò)分析_第1頁
第1頁 / 共28頁
運(yùn)籌學(xué)課件:第5章 圖與網(wǎng)絡(luò)分析_第2頁
第2頁 / 共28頁
運(yùn)籌學(xué)課件:第5章 圖與網(wǎng)絡(luò)分析_第3頁
第3頁 / 共28頁

下載文檔到電腦,查找使用更方便

30 積分

下載資源

還剩頁未讀,繼續(xù)閱讀

資源描述:

《運(yùn)籌學(xué)課件:第5章 圖與網(wǎng)絡(luò)分析》由會員分享,可在線閱讀,更多相關(guān)《運(yùn)籌學(xué)課件:第5章 圖與網(wǎng)絡(luò)分析(28頁珍藏版)》請?jiān)谘b配圖網(wǎng)上搜索。

1、第5章 圖與網(wǎng)絡(luò)分析5.1 圖論的基本概念5.1.1 引言瑞士數(shù)學(xué)歐拉(Euler)在1736年發(fā)表了圖論方面的第一篇論文,題為“依據(jù)幾何位置的解題方法”,解決了著名的哥尼斯堡七橋問題。哥尼斯堡城中有一條河叫普雷格爾河,該河上有兩個(gè)島,河上有七座橋,如圖5-1(a)所示。當(dāng)時(shí)那里的居民熱衷于這樣的問題:一個(gè)散步者能否走過七座橋,且每座橋只走過一次,最后回到出發(fā)點(diǎn)。歐拉用A、B、C、D四點(diǎn)表示河的兩岸和小島,用兩點(diǎn)間的聯(lián)線表示橋,如圖5-1(b),該問題可歸結(jié)為:能否從任一點(diǎn)出發(fā),通過每條邊一次且僅一次,再回到該點(diǎn)?即一筆畫問題。歐拉證明了這是不可能的,因?yàn)閳D中每點(diǎn)都只與奇數(shù)條線相連。這是古典圖

2、論中的一個(gè)著名問題。運(yùn)籌學(xué)中的“中國郵遞員問題”:一個(gè)郵遞員從郵局出發(fā)要走遍他所負(fù)責(zé)的每條街道去送信,問應(yīng)如何選擇適當(dāng)?shù)穆肪€可使所走的總路程最短。這個(gè)總是就與歐拉回路有密切的關(guān)系。圖論的第一本專著是匈牙利數(shù)學(xué)家O.Konig著的“有限圖與無限圖的理論”,發(fā)表于1936年。隨著科學(xué)技術(shù)的發(fā)展及電子計(jì)算機(jī)的出現(xiàn)和廣泛應(yīng)用,圖論得到進(jìn)一步發(fā)展,廣泛應(yīng)用于管理科學(xué)、計(jì)算機(jī)科學(xué)、心理學(xué)及工程技術(shù)管理中,并取得了豐碩的成果。5.1.2 基本概念自然界和人類社會中,大量的事物以及事物之間的關(guān)系,常可以用圖形來表示。如為了反映城市之間有沒有航班,我們可用圖5-2來示意。甲城與乙城,乙城與丙城有飛機(jī)到達(dá),而甲、

3、丙兩城沒有直飛航班。再如工作分配問題,我們可以用點(diǎn)表示每人與需要完成的工作,點(diǎn)間連線表示每個(gè)人可以勝任哪些工作如圖5-3所示。在上面的例子中,我們關(guān)心圖中有多少個(gè)點(diǎn),點(diǎn)與點(diǎn)之間有無連線。這種圖是反映對象之間關(guān)系的一種工具。圖可分為無向圖和有向圖。兩點(diǎn)之間不帶箭頭的聯(lián)線為邊,兩點(diǎn)之間帶箭頭的聯(lián)線為弧。由點(diǎn)、邊構(gòu)成的圖是無向圖,記由點(diǎn)、弧構(gòu)成的圖是有向圖,記圖5-4是一個(gè)無向圖,其中,圖5-5是一個(gè)有向圖,其中,給定一個(gè)圖,一個(gè)點(diǎn)、邊的交錯(cuò)序列,如果滿足,則稱為一條聯(lián)結(jié)和的鏈,記為。對于有向圖,從中去掉所有弧上的箭頭,應(yīng)得到一個(gè)無向圖,稱為的基礎(chǔ)圖,記為。設(shè)是中的一個(gè)點(diǎn)弧交錯(cuò)序列,如果這個(gè)序列在基

4、礎(chǔ)圖中所對應(yīng)的點(diǎn)邊序列是一條鏈,則稱這個(gè)點(diǎn)弧交錯(cuò)序列是的一條鏈。在實(shí)際問題中,往往只用圖來描述的所研究對象之間的關(guān)系還是不夠的,與圖聯(lián)系在一起的,通常還有與點(diǎn)或邊有關(guān)的某些數(shù)量指標(biāo),稱為“權(quán)”,權(quán)可以代表如距離、費(fèi)用、通過能力(容量)等等。這種點(diǎn)或邊帶有某種數(shù)量指標(biāo)的圖稱為網(wǎng)絡(luò)(即賦權(quán)圖)。5.1.3 圖的矩陣表示用矩陣表示圖對研究圖的性質(zhì)及應(yīng)用常是比較方便的,圖的矩陣表示方法有權(quán)矩陣、鄰接矩陣、關(guān)聯(lián)矩陣、回路矩陣等,這里只介紹其中兩種常用矩陣。定義1網(wǎng)絡(luò),其邊是有權(quán),構(gòu)造矩陣其中,稱矩陣為網(wǎng)絡(luò)的權(quán)矩陣。圖5-6表示圖的權(quán)矩陣為定義2對于圖,構(gòu)造一個(gè)矩陣,其中,則稱矩陣為圖的鄰接矩陣。圖5-7

5、所示圖的鄰接矩陣為當(dāng)為無向圖時(shí),鄰接矩陣為對稱矩陣。5.2 最短路問題最短路問題是網(wǎng)絡(luò)理論中應(yīng)用最廣泛的問題之一。許多優(yōu)化問題可以使用這個(gè)模型,如設(shè)備更新、管道鋪設(shè)、線路安排、廠區(qū)布局等。問題表述:給定一個(gè)賦權(quán)有向圖,對每一弧,相應(yīng)地有權(quán),又有兩點(diǎn),設(shè)是中到的一條路,路的權(quán)是中所有弧的權(quán)之和,記為。最短路問題就是求從到的路中一條權(quán)最小的路,。5.2.1 Dijkstra算法該算法是由Dijkstra于1959年提出來,用于求解指定兩點(diǎn)、之間的最短路,或從指定點(diǎn)到其余各點(diǎn)的最短路,目前被認(rèn)為是求情形下最短路問題的最好方法。算法的基本思路基于以下原理:若是從到的最短路,是中的一個(gè)點(diǎn),那么從沿到的路

6、是從到的最短路。采用標(biāo)號法:標(biāo)號與標(biāo)號。標(biāo)號為試探性標(biāo)號,為永久性標(biāo)號。給點(diǎn)一個(gè)標(biāo)號時(shí),表示從到點(diǎn)的最短路權(quán),點(diǎn)的標(biāo)號不再改變。給點(diǎn)一個(gè)標(biāo)號時(shí),表示從到點(diǎn)的估計(jì)最短路權(quán)的上界,是一種臨時(shí)標(biāo)號。凡沒有得到標(biāo)號的點(diǎn)都有標(biāo)號。算法每一步都把某一點(diǎn)的標(biāo)號改為標(biāo)號,當(dāng)終點(diǎn)得到標(biāo)號時(shí),全部計(jì)算結(jié)束。Dijkstra算法基本步驟:給以標(biāo)號,其余各點(diǎn)均給標(biāo)號,。若點(diǎn)為剛得到標(biāo)號的點(diǎn),考慮,且為標(biāo)號。對的標(biāo)號進(jìn)行如下的更改: 比較所有具有標(biāo)號的點(diǎn),把最小者改為標(biāo)號,即當(dāng)存在兩個(gè)以上最小者時(shí),可同時(shí)改為標(biāo)號。若全部點(diǎn)均為標(biāo)號則停止。否則用代替轉(zhuǎn)回。例5.1 用Dijkstra算法求圖5-8中從的最短路解:首先給以

7、標(biāo)號,給其余所有點(diǎn)標(biāo)號,由于,且是標(biāo)號點(diǎn),所以修改標(biāo)號為:在所有標(biāo)號中,最小,于是令。是剛得到標(biāo)號的點(diǎn),故考察。因?yàn)?,且是?biāo)號,故新的標(biāo)號為:在所有標(biāo)號中,最小,故令。考察,因,在所有標(biāo)號中,最小,令??疾欤谒袠?biāo)號中,最小,令??疾欤谒袠?biāo)號中,最小,故令??疾?,令,所有點(diǎn)都標(biāo)上標(biāo)號,計(jì)算結(jié)束。從之最短路是:,路長13,同時(shí)得到到其余各點(diǎn)的最短路。5.2.2 逐次逼近算法Dijkstra算法只適用于所有的情形,當(dāng)賦權(quán)有向圖中存在負(fù)權(quán)時(shí),則算法失效。例如在圖5-9所示的賦權(quán)有向圖中,用Dijkstra算法得到到最短路的權(quán)是5,但這里顯然不對;因?yàn)榈降淖疃搪肥?,?quán)為3。在存在負(fù)權(quán)時(shí),我們采取

8、逐次逼近算法來求解最短路。為方便起見,不妨設(shè)從任一點(diǎn)到任一點(diǎn)都有一條弧,如果在中,則添加弧,令。顯然,從到的最短路總是從出發(fā),沿著一條路到某點(diǎn),再沿到的,所以,從到的這條路必定是從到的最短路。故有,的距離必滿足如下方程:為了求解這個(gè)方程的解,為的點(diǎn)數(shù),令,為迭代步數(shù)。若第步,對所有,有則為到任一點(diǎn)的最短路權(quán)。例5-2 求圖5-10所示賦權(quán)有向圖中從到各點(diǎn)的最短路。解:迭代初始條件為:有,。用表5-1表示全部計(jì)算過程。表5-1 (表中空格為)ji wijD(t)(v1,vj)V1V2V3V4V5V6V7V8V10-1-230000V2602-1-5-5-5V3-30-51-2-2-2-2V480

9、23-7-7-7V5-101-3-3V61017-1-1-1V7-105-5-5V8-3-5066 當(dāng)時(shí),發(fā)現(xiàn),表明已得到到各點(diǎn)的最短路的權(quán),即表中最后一列數(shù)。如果需要知道點(diǎn)到各點(diǎn)的最短路徑,可以采用“反向追蹤”的辦法。如已知,因故記下。因,記下,從而從到的最短路徑是。遞推公式中實(shí)際意義為從到點(diǎn),至多含有個(gè)中間點(diǎn)的最短路權(quán)。所以在含有個(gè)點(diǎn)的圖中,如果不含有總權(quán)小于零的回路,求從到任一點(diǎn)的最短路權(quán),用上述算法最多經(jīng)過-1次迭代必定收斂。顯然,如果圖中含有總權(quán)小于零的回路,最短路權(quán)沒有下界。應(yīng)用舉例例5-3設(shè)備更新問題。某企業(yè)使用一臺設(shè)備,在每年年初,都要決定是否更新。若購置新設(shè)備,要付購買費(fèi);若

10、繼續(xù)使用舊設(shè)備,則支付維修費(fèi)用。試制定一個(gè)5年更新計(jì)劃,使總支出最少。若已知設(shè)備在各年的購買費(fèi)及不同機(jī)器役齡時(shí)的殘值和維修費(fèi),如表5-2所示。表5-2第1年第2年第3年第4年第5年購買費(fèi)1112131414機(jī)器役齡0-11-22-33-44-5維修費(fèi)5681118殘值43210解:把這個(gè)問題化為最短路問題用表示第年初購進(jìn)一臺新設(shè)備,虛設(shè)一個(gè)點(diǎn),表示第5年底;用弧表示第初購的設(shè)備一直使用到第年年底;弧上的數(shù)字表示第年初購進(jìn)設(shè)備,一直使用到第年底所需支付的購買、維修的全部費(fèi)用。例如,弧上的28是第1年初購買費(fèi)11加上3年的維修費(fèi)5,6,8,減去了3年役齡機(jī)器的殘值2;弧上的20是第2年初購買費(fèi)12

11、減去機(jī)器殘值3與使用2年維修費(fèi)5,6之和,見圖5-11。這樣設(shè)備更新問題就變?yōu)椋呵髲牡降淖疃搪?,?jì)算結(jié)果表明為最短路,路長為49。即在第1年、第3年初各購買一臺新設(shè)備為最優(yōu)決策,這時(shí)5年的總費(fèi)用為49。5.3最大流問題最大流問題是一類應(yīng)用極為廣泛的問題。例如在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車流、貨物流;供水網(wǎng)絡(luò)中有水流;金融系統(tǒng)中有現(xiàn)金流;通訊系統(tǒng)中有信息流;等等。20世紀(jì)50年代Ford ,F(xiàn)ulkerson建立的“網(wǎng)絡(luò)流理論”是網(wǎng)絡(luò)應(yīng)用的重要組成部分。圖5-12是輸油管道網(wǎng),為起點(diǎn),是終點(diǎn),為中轉(zhuǎn)站,弧上的數(shù)表示該管道的最大輸油能力,問應(yīng)如何安排各管道輸油量,才能使從到的總輸油量最大?5.3.1

12、基本概念與基本定理網(wǎng)絡(luò)與流定義給一個(gè)有向圖,在中指定一點(diǎn)為發(fā)點(diǎn),另一點(diǎn)為收點(diǎn),其余的點(diǎn)叫中間點(diǎn)。對于每一個(gè)弧,對應(yīng)有一個(gè)(簡寫為),稱為弧的容量。這樣的叫做網(wǎng)絡(luò),記作。所謂網(wǎng)絡(luò)上的流,是指定義在弧集合上的一個(gè)函數(shù),并稱為弧上的流量,簡記作??尚辛髋c最大流容量限制條件:每一弧平衡條件:對于中間點(diǎn),有對于發(fā)點(diǎn),收點(diǎn),有稱為這個(gè)可行流的流量。可行流總是存在的,如零流,。所謂最大流問題,就是求一個(gè)流,使其流量達(dá)到最大,并且滿足以上容量限制條件和平衡條件。其實(shí)最大流問題是一個(gè)特殊的線性規(guī)劃問題,但是利用它與圖的緊密關(guān)系求解,更為直觀簡便。增廣鏈若是網(wǎng)絡(luò)中聯(lián)結(jié)發(fā)點(diǎn)和收點(diǎn)的一條鏈,且鏈的方向是從到,則與鏈的

13、方向一致的弧叫前向弧,表示前向弧的集合;與鏈的方向相反的弧叫后向弧,表示后向弧的集合。定義設(shè)是一個(gè)可行流,是從到的一條鏈,若滿足下列條件,是可行流的一條增廣鏈。 弧上,即中每一弧是非飽和弧。 弧上,即中每一弧是非零流弧。截集與截量設(shè),我們把始點(diǎn)在,終點(diǎn)在中的所有弧構(gòu)成的集合,記為。定義給網(wǎng)絡(luò),若點(diǎn)集被剖分為兩個(gè)非空集合和, ,使,則把弧集稱為分離,的截集。從定義可知截集是從到的必經(jīng)之道。定義給一截集,把截集中所有弧的容量之和稱為這個(gè)截集的容量,記作不難證明,任何一個(gè)可行流的流量都不會超過任一截量的容量,即。顯然,若對于一個(gè)可行流,網(wǎng)絡(luò)中有一個(gè)截集,則必是最大流,而必定是的所有截集中容量最小的一

14、個(gè),即最小截量。最大流量最小截量定理:任一個(gè)網(wǎng)絡(luò)中,從到的最大流的流量等于分離,的最小截集的容量。定理1可行流是最大流,當(dāng)且僅當(dāng)不存在關(guān)于的增廣鏈。證明若是最大流,設(shè)中存在關(guān)于的增廣鏈,令由增廣鏈的定義,可知,令不難驗(yàn)證是一個(gè)可行流,且,這與是最大流假設(shè)矛盾?,F(xiàn)在設(shè)中不存在關(guān)于的增廣鏈,證明是最大流。令,若,且,則令;若,且,則令。因?yàn)椴淮嬖陉P(guān)于的增廣鏈,故。記,于是得到一個(gè)截集,顯然必有所以,。于是必是最大流,定理得證。定理1為我們提供了尋求網(wǎng)絡(luò)最大流的一個(gè)方法。若可行流中存在增廣鏈,說明還有潛力可挖,只須沿增廣鏈調(diào)整流量,得到一個(gè)流量增大的新的可行流;否則是最大流。而判別是否存在增廣鏈,可

15、以根據(jù)是否屬于來進(jìn)行。5.3.2 尋求最大流的標(biāo)號法(Ford,F(xiàn)ulkerson)設(shè)已有一個(gè)可行流,標(biāo)號算法分2步:第1步是標(biāo)號過程,通過標(biāo)號來尋找增廣鏈;第2步是調(diào)整過程,沿增廣鏈調(diào)整以增加流量。標(biāo)號過程每個(gè)標(biāo)號點(diǎn)的標(biāo)號包含兩部分:第1個(gè)標(biāo)號明它的標(biāo)號從哪一點(diǎn)得到,以便找出增廣鏈;第2個(gè)標(biāo)號是為確定增廣鏈的調(diào)整量用的。 給發(fā)點(diǎn)以標(biāo)號; 選擇一個(gè)已標(biāo)號的點(diǎn),對于的所有未標(biāo)號的鄰接點(diǎn),如果,且,令,并給以標(biāo)號;如果,且,令,并給以標(biāo)號。 重復(fù)上述步驟,直到被標(biāo)上號或不再有頂點(diǎn)可標(biāo)號為止。如果得到標(biāo)號,說明存在增廣鏈,轉(zhuǎn)入調(diào)整過程;若未獲得標(biāo)號,標(biāo)號過程已無法進(jìn)行時(shí),說明已是最大流。調(diào)整過程令調(diào)

16、整量,去掉所有標(biāo)號,對新的可行流重新進(jìn)行標(biāo)號過程。例5-4 用標(biāo)號法求圖5-13所示網(wǎng)絡(luò)的最大流?;∨缘臄?shù)是。解:經(jīng)檢查,網(wǎng)絡(luò)中的流是可行流,下面分析是否可以增加流量。(一) 標(biāo)號過程1、 首先給標(biāo)上;2、檢查,在弧上,則的標(biāo)號為,其中。在弧上,不滿足標(biāo)號條件。3、檢查,在弧上,不滿足標(biāo)號條件。在弧上,則的標(biāo)號為,。4、檢查,在弧上,則給標(biāo)號,。在弧上,給標(biāo)號,。5、在中任選一個(gè)進(jìn)行檢查,例如,在弧 上,給標(biāo)號,。因有了標(biāo)號,故轉(zhuǎn)入調(diào)整過程。(二)調(diào)整過程按點(diǎn)的第一個(gè)標(biāo)號找到一條增廣鏈,如圖5-14中雙箭線所示。則見:按,在增廣鏈上調(diào)整。上:上:其余的不變。調(diào)整后得到圖5-15所示的可行流,對

17、這個(gè)可行流進(jìn)行標(biāo)號,尋找增廣鏈。開始給標(biāo)號,檢查,給標(biāo)以,檢查,弧上,弧上,均不符合條件,標(biāo)號過程無法繼續(xù)下去,算法結(jié)束。這時(shí)圖5-15 可行流即最大流。最大流為:。與此同時(shí)可找到最小截集,其中為標(biāo)號點(diǎn)集,即,為未標(biāo)號點(diǎn)集,截集,最小截量為5。由上述可見,用標(biāo)號法找增廣鏈找到最大流的同時(shí),得到一個(gè)最小截集。最小截集的容量大小影響網(wǎng)絡(luò)最大流量。因此為提高總的輸送量,必須首先考慮改善最小截集中各弧的輸送能力。另一方面,一旦最小截集中弧的通過能力被 降低,就會使總的輸送量減少。5.4 網(wǎng)絡(luò)計(jì)劃20世紀(jì)50年代以來,國外陸續(xù)出現(xiàn)一些計(jì)劃管理的新方法,如關(guān)鍵路線法(Critical Path Metho

18、d,縮寫為CPM),計(jì)劃評審方法(Program Evaluation Review Technique,縮寫為PETR)等。這些方法都是建立在網(wǎng)絡(luò)模型基礎(chǔ)之上,稱為網(wǎng)絡(luò)計(jì)劃技術(shù),廣泛應(yīng)用于工業(yè)、農(nóng)業(yè)、國防、科研等計(jì)劃管理中,對縮短工期,節(jié)約人力、物力和財(cái)力,提高經(jīng)濟(jì)效益發(fā)揮了重要作用。我國數(shù)學(xué)家華羅庚先生將這些方法總結(jié)概括為統(tǒng)籌方法,引入中國并推廣應(yīng)用。統(tǒng)籌方法的基本原理是:從需要管理的任務(wù)的總進(jìn)度著眼,以任務(wù)中各工作所需要的工時(shí)為時(shí)間因素,按照工作的先后順序和相互關(guān)系作出網(wǎng)絡(luò)圖,以反映任務(wù)全貌,實(shí)現(xiàn)管理過程的模型化。然后進(jìn)行時(shí)間參數(shù)計(jì)算,找出計(jì)劃中的關(guān)鍵工作和關(guān)鍵路線,對任務(wù)的各項(xiàng)工作所需

19、的人、財(cái)、物通過改善網(wǎng)絡(luò)計(jì)劃作出合理安排,得到最優(yōu)方案并付諸實(shí)施。通過對各種評價(jià)指標(biāo)進(jìn)行定量化分析,在計(jì)劃的實(shí)施過程中,進(jìn)行有效的監(jiān)督與控制,以保證任務(wù)高質(zhì)量地完成。5.4.1 網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖是由節(jié)點(diǎn)、弧及權(quán)所構(gòu)成的有向圖,即有向的賦權(quán)圖。節(jié)點(diǎn)表示事項(xiàng),弧表示工序(活動)。工序是在工藝技術(shù)和組織管理上相對獨(dú)立的工作或活動,需要一定的時(shí)間與資源,而事項(xiàng)則表示一個(gè)或若干工序的開始或結(jié)束,是相繼工序的分界點(diǎn)。權(quán)表示為完成某個(gè)工序所需要的時(shí)間或資源等數(shù)據(jù)。例如某工序可以表示為:,為箭頭節(jié)點(diǎn),表示工序開始,為箭頭尾節(jié)點(diǎn),表示工序結(jié)束,5為完成本工序所需時(shí)間。網(wǎng)絡(luò)圖是有向圖,按照工藝流程的順序,規(guī)定工序從左

20、向右排列,再給節(jié)點(diǎn)統(tǒng)一編號,節(jié)點(diǎn)由小到大編號。對任一工序來講,要求。始點(diǎn)編號可以從1開始。在繪制網(wǎng)絡(luò)圖時(shí),還要注意以下規(guī)則:網(wǎng)絡(luò)圖只能有一個(gè)總起點(diǎn)事項(xiàng),一個(gè)總終點(diǎn)事項(xiàng)。網(wǎng)絡(luò)圖不能有缺口和回路。兩節(jié)點(diǎn)之間只能有一條弧。正確表示工作之間的前行、后繼關(guān)系。如圖5-16表示兩工序結(jié)束后,兩工序才開始。為的緊前工序,為的緊后工序。虛工序的應(yīng)用。如果的工序關(guān)系是:必須在均完成后才能開工,而只要在完成后即可開工。也就是說,是的緊前工序,而只有是的緊前工序。這樣必須用圖5-17來表示,其中是一個(gè)虛工序,只表示、兩節(jié)點(diǎn)的銜接關(guān)系,不需要人力、物力等資源和時(shí)間。虛工序還可以用于正確表示平行與交叉作業(yè)。一道工序分為

21、幾道工序同時(shí)進(jìn)行,稱為平行作業(yè)。如圖5-18(a)中市場調(diào)研需12天,如增加人力分為3組同時(shí)進(jìn)行,可以畫為5-18(b)。兩個(gè)或兩個(gè)以上的工作交叉進(jìn)行,稱為交叉作業(yè)。如工作與工作分別為挖溝和埋管子,那么它們的關(guān)系可以是挖一段,埋一段,不必等溝全部挖好再埋。這樣,我們可用圖5-19來表示交叉作業(yè)。根據(jù)上述規(guī)則繪制網(wǎng)絡(luò)圖,是為了保證網(wǎng)絡(luò)圖的正確性。此外,為了使圖面布局合理,層次分明,條理清楚,還要注意畫圖技巧。避免弧的交叉,盡可能將關(guān)鍵路線布置在中心位置,將聯(lián)系緊密的工序布置在相近的位置。例5-5 某項(xiàng)新產(chǎn)品投產(chǎn)前全部準(zhǔn)備工作(如表5-3)列示各工序與所需時(shí)間以及它們之間的相互關(guān)系。要求編制該項(xiàng)工

22、程的網(wǎng)絡(luò)計(jì)劃。表5-3工序工序內(nèi)容緊前工序工時(shí)(周)A市場調(diào)查/4B資金籌措/10C需求分析A3D產(chǎn)品設(shè)計(jì)A6E產(chǎn)品研制D8F制定成本計(jì)劃C,E2G制定生產(chǎn)計(jì)劃F3H籌備設(shè)備B,G2I原材料準(zhǔn)備B,G8J安裝設(shè)備H5K人員準(zhǔn)備G2L準(zhǔn)備開工投產(chǎn)I,J,K1根據(jù)以上規(guī)則,繪制的網(wǎng)絡(luò)圖如5-20所示。5.4.2 時(shí)間參數(shù)計(jì)算計(jì)算網(wǎng)絡(luò)圖中有關(guān)的時(shí)間參數(shù),主要目的是找出關(guān)鍵路線,為網(wǎng)絡(luò)計(jì)劃的優(yōu)化、調(diào)整和執(zhí)行提供明確的時(shí)間概念。通常把網(wǎng)絡(luò)圖中需時(shí)最長的路線叫做關(guān)鍵路線,如圖5-21所示網(wǎng)絡(luò)中雙箭線表示的為關(guān)鍵路線,關(guān)鍵路線上的工序稱為關(guān)鍵工序。要想使任務(wù)按期完或提前完工,就要在關(guān)鍵路線的關(guān)鍵工序上想辦法

23、。網(wǎng)絡(luò)圖的時(shí)間參數(shù)包括工序所需時(shí)間、事項(xiàng)最早、最遲時(shí)間,工序的最早、最遲時(shí)間及時(shí)差等,下面分別敘述。一、 工序時(shí)間的確定工序的所需時(shí)間可記為,有以下兩種情況:完成工序所需時(shí)間確定,只給出一個(gè)時(shí)間值。在具備勞動定額資料的條件下,或者在具有類似工序的作業(yè)時(shí)間消耗的統(tǒng)計(jì)資料時(shí),用對比分析來確定作業(yè)時(shí)間。在影響工序因素較多,作業(yè)時(shí)間難以準(zhǔn)確估計(jì)時(shí),可以采用三點(diǎn)時(shí)間估計(jì)法來確定作業(yè)時(shí)間:最快可能完成時(shí)間最可能完成時(shí)間最慢可能完成時(shí)間一般情況下,可按下列公式近似計(jì)算作業(yè)時(shí)間。概率型網(wǎng)絡(luò)圖與確定型網(wǎng)絡(luò)圖在工時(shí)確定后,對其他時(shí)間參數(shù)的計(jì)算基本相同。二、 事項(xiàng)時(shí)間參數(shù)事項(xiàng)最早時(shí)間事項(xiàng)的最早時(shí)間用表示,它表示以為

24、始點(diǎn)的各工序最早可能開始的時(shí)間,也表示以為終點(diǎn)的各工序的最早可能完成時(shí)間。它等于從始點(diǎn)事項(xiàng)起到本事項(xiàng)最長路線的時(shí)間長度。事項(xiàng)最早時(shí)間可用下列遞推公式,按照事項(xiàng)編號從小到大順序逐個(gè)計(jì)算。式中,為事項(xiàng)相鄰的各緊前事項(xiàng)的最早時(shí)間。事項(xiàng)的最遲時(shí)間事項(xiàng)的最遲時(shí)間用表示,它表明在不影響任務(wù)總工期條件下,以它為始點(diǎn)的工序的最遲必須開始時(shí)間,或以它為終點(diǎn)的各工作的最遲必須完成時(shí)間。在一般情況下,把任務(wù)的最早完工時(shí)間作為任務(wù)的總工期,所示事項(xiàng)最遲時(shí)間的計(jì)算方法如下:為事項(xiàng)相鄰的各緊后事項(xiàng)的最遲時(shí)間,它的計(jì)算從終點(diǎn)事項(xiàng)開始,按編號由大到小的順序逐個(gè)計(jì)算。三、 工序的時(shí)間參數(shù)工序的最早可能開始時(shí)間和最早可能完工時(shí)間

25、一個(gè)工序的最早可能開工時(shí)間用表示,任何一個(gè)工序都必須在其所有緊前工序全部完工后才能開始。工序的最早可能完工時(shí)間用表示,它表示工作按最早開工時(shí)間開始所能達(dá)到的完工時(shí)間,計(jì)算公式如下:工序的最早可能開工時(shí)間等于事項(xiàng)最早時(shí)間。工序的最遲必須開工時(shí)間與最遲必須完工時(shí)間一個(gè)工序的最遲必須開工時(shí)間用表示,它是工序在不影響整個(gè)任務(wù)如期完成的前提下,必須開始的最晚時(shí)間。工序最遲必須完工時(shí)間用表示,它表示工作按最遲時(shí)間開工,所能達(dá)到的完工時(shí)間。工序最遲必須完工時(shí)間等于事項(xiàng)的最遲時(shí)間四、時(shí)差。工序的時(shí)差,又稱為工序的機(jī)動時(shí)間,工序時(shí)差分兩種:工序總時(shí)差在不影響工程最早結(jié)束時(shí)間的條件下,工序最早開始(或結(jié)束)時(shí)間可

26、以推遲的時(shí)間:工序單時(shí)差不影響緊后工序最早開始時(shí)間的條件下,工序最早結(jié)束時(shí)間可以推遲的時(shí)間:式中,為工序的緊后工序的最早開始時(shí)間。總時(shí)差為零的工序,開始和結(jié)束的時(shí)間沒有一點(diǎn)機(jī)動的余地,由這些工序所組成的路線就是網(wǎng)絡(luò)中的關(guān)鍵路線,這些工序就是關(guān)鍵工序。例5-6:確定圖5-20所示網(wǎng)絡(luò)的關(guān)鍵路線。解:先用圖上計(jì)算法求解,再用表上計(jì)算法驗(yàn)證。根據(jù)圖5-20的資料,先計(jì)算各事項(xiàng)的時(shí)間參數(shù)。事項(xiàng)時(shí)間如總開工事項(xiàng),將結(jié)果填入圖中編號上方空格 的左邊。逐個(gè)計(jì)算事項(xiàng)最早時(shí)間,得到總完工事項(xiàng),說明整個(gè)工作需要32周的時(shí)間完成。再從后面開始計(jì)算各事項(xiàng)最遲時(shí)間,如總完工事項(xiàng)的,事項(xiàng)的將結(jié)果填入編號上方空格 右邊。工

27、序時(shí)間工序時(shí)間有4種:,用圖標(biāo) 表示,計(jì)算結(jié)果表示在圖5-22上。時(shí)差根據(jù)圖5-22中的結(jié)果,可以求出各工序的總時(shí)差。由總時(shí)差為0的工序組成關(guān)鍵路線,即:,總工期為32周。表5-4用來計(jì)算網(wǎng)絡(luò)時(shí)間,并標(biāo)示出關(guān)鍵工序。表5-4工序關(guān)鍵工序A404040B10010132313C347151811D64104100E8101810180F2182018200C3202320230虛工序0232323230H2232524261I8233123310J5233026311K2252529316L13132313205.4.3 網(wǎng)絡(luò)優(yōu)化繪制網(wǎng)絡(luò)圖,計(jì)算網(wǎng)絡(luò)時(shí)間和確定關(guān)鍵路線,得到一個(gè)初始的計(jì)劃方案。從

28、工期、成本、資源等方面對初步方案進(jìn)一步的改善和調(diào)整,以求得最佳效果,就是網(wǎng)絡(luò)優(yōu)化。目前尚未有能全面反映工期、成本、資源的綜合數(shù)學(xué)模型,因此,網(wǎng)絡(luò)優(yōu)化問題是根據(jù)實(shí)際情況分為時(shí)間優(yōu)化、時(shí)間-資源優(yōu)化和時(shí)間-費(fèi)用優(yōu)化。1、 時(shí)間優(yōu)化根據(jù)對計(jì)劃進(jìn)度的要求,縮短工程完工時(shí)間。可以采取措施:把串聯(lián)工序改為平行或交叉工序,縮短關(guān)鍵工序的作業(yè)時(shí)間;充分利用非關(guān)鍵工序的時(shí)差,減少這些作業(yè)的人力、資源用于關(guān)鍵工序,縮短關(guān)鍵工序的作業(yè)時(shí)間。2、 時(shí)間-資源優(yōu)化在編制網(wǎng)絡(luò)計(jì)劃安排工程進(jìn)度時(shí),考慮時(shí)間優(yōu)化的同時(shí),盡量合理地利用有限的資源。具體的要求和做法是:優(yōu)先安排關(guān)鍵工序所需要的資源;利用非關(guān)鍵工序的總時(shí)差,錯(cuò)開各工

29、序的開始時(shí)間,拉平資源需要量的高峰;綜合考慮資源和時(shí)間,必要時(shí),可適當(dāng)?shù)赝七t工程完工時(shí)間。在優(yōu)化時(shí),通常將計(jì)劃的各主要資源需要量按日程排出,再按以上方法,使各主要資源的日負(fù)荷相對平衡。但是由于一項(xiàng)工程所包含的工序繁多,涉及到的資源利用情況復(fù)雜,需要多次綜合平衡,才能得到在時(shí)間進(jìn)度和資源利用等方面都比較合理的計(jì)劃方案。3、 時(shí)間-費(fèi)用優(yōu)化時(shí)間-費(fèi)用優(yōu)化要研究和解決的問題是決定合理的工程完工時(shí)間,使費(fèi)用最省,或者以合理的費(fèi)用代價(jià)完成趕工作任務(wù)。工程費(fèi)用包括兩大類:直接費(fèi)用是完成各項(xiàng)工作直接所需人力、資源設(shè)備費(fèi)用;為縮短工序的作業(yè)時(shí)間,需要采取一定的技術(shù)組織措施,相應(yīng)會增加一部分直接費(fèi)用。間接費(fèi)用是

30、指管理費(fèi)、辦工費(fèi)等,常按施工時(shí)間長短分?jǐn)?。完成工程?xiàng)目的直接費(fèi)用、間接費(fèi)用、總費(fèi)用與工程完工時(shí)間的關(guān)系,一般情況下如圖5-23所示。顯然,在網(wǎng)絡(luò)計(jì)劃中,最低成本日程具有重要意義。因此要計(jì)算網(wǎng)絡(luò)計(jì)劃的不同完工期相應(yīng)的總費(fèi)用,以求得成本最低的日程安排,即最低成本日程。下面舉例說明最低成本日程計(jì)劃。例5-7:已知網(wǎng)絡(luò)計(jì)劃各工序的正常工時(shí)、極限工時(shí)及相應(yīng)費(fèi)用如表5-5,網(wǎng)絡(luò)圖如圖5-24。表5-5工序正常工時(shí)極限工時(shí)成本斜率(元/天)時(shí)間(天)費(fèi)用(元)時(shí)間(天)費(fèi)用(元)24500016700025030900018102001002240001848002002610000241030015024

31、8000209000250185400185400/18640010680050按正常工時(shí)計(jì)算出總工期74天,關(guān)鍵路線,總直接費(fèi)用為47800元。設(shè)正常工時(shí)下任務(wù)總間接費(fèi)用為18000元,工期每縮短一天,間接費(fèi)用可節(jié)省330元,求最低成本日程。解:按下列步驟進(jìn)行計(jì)算。a) 從關(guān)鍵工作中選出縮短工時(shí)所需直接費(fèi)用最少的方案及天數(shù);b) 按照新工時(shí),重新計(jì)算網(wǎng)絡(luò)計(jì)劃的關(guān)鍵路線及關(guān)鍵工作;c) 計(jì)算由于縮短工時(shí)總費(fèi)用的變化。重復(fù)以上三個(gè)步驟,直到工期不能再縮短為止。在圖5-24上,挑選關(guān)鍵路線中成本斜率最小者,最多可縮短12天,即新工時(shí)為18天。重新計(jì)算網(wǎng)絡(luò)時(shí)間參數(shù),如圖5-25(a)所示,關(guān)鍵路線為

32、,工期為64天,實(shí)際只縮短10天,這意味著工序的工時(shí)為20天。重新計(jì)算結(jié)果如圖5-25(b),總工期64天,有兩條關(guān)鍵路線,直接費(fèi)用增10100元,間接費(fèi)用減10330元。重復(fù)上述步驟,將,的工時(shí)縮短為:18,20天,重新計(jì)算網(wǎng)絡(luò)時(shí)間參數(shù),結(jié)果如圖5-26。關(guān)鍵路線不變。增加直接費(fèi)用2(100+200)=600元,減少間接費(fèi)用2330=660元。第三次調(diào)整,在,工序上多縮短2天,重新計(jì)算網(wǎng)絡(luò)時(shí)間參數(shù),結(jié)果如圖5-27,有三條關(guān)鍵路線,總工期60天,直接費(fèi)用增加2350=700元,間接費(fèi)用減少2330=660元。由于一條關(guān)鍵路線上各工序工時(shí)不能縮短,計(jì)算結(jié)束。最低成日程為62天,總成本63440

33、元。習(xí)題:5.1有9個(gè)城市,其公路網(wǎng)如圖5-28所示。弧旁數(shù)字是該段公路的長度,有一批貨物從到,問走哪條路最短?5.2用DijKstra方法求圖5-29中從到各點(diǎn)的最短路。5.3求圖5-30網(wǎng)絡(luò)中各頂點(diǎn)間的最短路。5.4某設(shè)備今后5年的價(jià)格預(yù)測分別是(5,5,6,7,8),若該設(shè)備連續(xù)使用,其第年的維修費(fèi)分別為(1,2,3,5,6)。某單位今年購進(jìn)一臺,問如何確定更新方案可使5年里總支出最?。ú还茉O(shè)備使用了多少年,其殘值為0)。5.5在如圖5-31所示的網(wǎng)絡(luò)中,每弧旁的數(shù)字是。(1) 確定所有的截集;(2) 求最小截集的容量;(3) 證明指出的流是最大流。5.6求如圖5-32所示的網(wǎng)絡(luò)的最大流

34、,弧上數(shù)為。5.7如圖5-33,發(fā)點(diǎn)分別可供應(yīng)10和15個(gè)單位,收點(diǎn)可以接收10和25個(gè)單位,求最大流,弧上數(shù)為。5-8試畫出表5-6所表示項(xiàng)目的網(wǎng)絡(luò)圖。表5-6工作工時(shí)(d)緊前工序工作工時(shí)(d)緊前工序A15-F5D,EB10-G20C,F(xiàn)C10A,BH10D,ED10A,BI15G,HE5B5-9設(shè)有如圖5-34網(wǎng)絡(luò)圖,用圖上計(jì)算法計(jì)算時(shí)間參數(shù),并求出關(guān)鍵路線。5-10繪 制表5-7所示的網(wǎng)絡(luò)圖,并用表上計(jì)算法計(jì)算工作的各項(xiàng)時(shí)間參數(shù),確定關(guān)鍵路線。表5-7工作工時(shí)(d)緊前工序工作工時(shí)(d)緊前工序A5-F4B,CB8A,CG8CC3AH2F,GD6CI4E,HE10B,CJ5F,G5-11已知下列資料表5-8活動作業(yè)時(shí)間(d)緊前活動正常完成進(jìn)度的直接費(fèi)用(百元)趕進(jìn)度1天所需費(fèi)用(百元)A4-205B8-304C6B153D3A52E5A184F7A407G4B,D103H3E,F(xiàn),G156工程的間接費(fèi)5(百元/天),求出該項(xiàng)工程的最低成本日程。28

展開閱讀全文
溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號:ICP2024067431-1 川公網(wǎng)安備51140202000466號


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請立即通知裝配圖網(wǎng),我們立即給予刪除!