運(yùn)籌學(xué)（第2版）課件 第四章 圖論與網(wǎng)絡(luò)計劃

南京航空航天大學(xué)經(jīng)濟(jì)與管理學(xué)院運(yùn)籌學(xué)第四章圖論與網(wǎng)絡(luò)計劃圖論是目前運(yùn)用十分廣泛的運(yùn)籌學(xué)分支之一。一個龐大而復(fù)雜的工程系統(tǒng)和管理問題用圖來描述，可以解決許多工程設(shè)計和管理決策的最優(yōu)化問題。所謂網(wǎng)絡(luò)計劃技術(shù),是以工序所需工時為時間因素，用工序之間相互聯(lián)系的網(wǎng)絡(luò)和一些簡單的算法，來反映整個工程或任務(wù)的全貌，并且在既定的條件下，全面籌劃，統(tǒng)一安排，來尋求達(dá)到預(yù)定目標(biāo)的最優(yōu)實施方案。圖論與網(wǎng)絡(luò)計劃問題應(yīng)用廣泛，涉及計算機(jī)、物理學(xué)、化學(xué)、控制論、信息論、管理經(jīng)濟(jì)科學(xué)等多學(xué)科多領(lǐng)域，在日常生活中，有助于解決各種各樣的決策問題。4.1圖與網(wǎng)絡(luò)自然界和人類社會中許多事物以及事物之間的關(guān)系，都可以用點(diǎn)和線連接起來的圖形來描述。例如用點(diǎn)表示城市，點(diǎn)間聯(lián)線表示城市間的道路，就可描述城市間的交通，如果聯(lián)線旁標(biāo)注城市間的距離——網(wǎng)絡(luò)圖中稱為權(quán)，形成加權(quán)圖，就稱為網(wǎng)絡(luò)圖，就可進(jìn)一步研究從一個城市到另一個城市的最短路徑；或者標(biāo)上單位運(yùn)價，就可分析運(yùn)費(fèi)最小的運(yùn)輸方案。本節(jié)將介紹有關(guān)圖與網(wǎng)絡(luò)的基本概念。4.1.1圖的基本概念一、無向圖二、有向圖4.1.2網(wǎng)絡(luò)的基本概念實際問題中，往往只用圖來描述所研究對象之間的關(guān)系還不夠，如果在圖中賦予邊一定的數(shù)量指標(biāo)，我們常稱之為“權(quán)”。依據(jù)研究問題的需要，權(quán)可以代表距離，也可以代表時間、費(fèi)用、容量、可靠性等。通常把這種賦權(quán)圖稱為網(wǎng)絡(luò)。與無向圖和有向圖相對應(yīng)，網(wǎng)絡(luò)又分為無向網(wǎng)絡(luò)和有向網(wǎng)絡(luò)。我們除了用圖形來表示圖外，為便于數(shù)據(jù)處理和計算機(jī)存儲，還可以用矩陣來表示一個圖。4.2最小生成樹問題4.2.1最小生成樹一、樹的基本概念先看一個具體的實例：例4－1已知有5個城市，要在它們之間架設(shè)電話線網(wǎng)，要求任何兩個城市都可以彼此通話（允許通過其他城市），并且電話線的條數(shù)最少。用點(diǎn)分別表示5個城市。設(shè)想一下，如果在與，與，與之間各架一條電話線，這個方案可用圖4－5（a）表示出來。這個方案顯然是不滿足要求的，因為在這樣的電話線網(wǎng)中，與之間就不能通話。因此，根據(jù)要求，設(shè)計出來的電話網(wǎng)方案必須是連通的。如果按照圖4－5（b）來設(shè)計電話網(wǎng)，雖然方案能滿足不同城市之間通話的要求，但卻不能保證電話線的條數(shù)最少。原因是構(gòu)成一個圈，如果從這個圈上，任意去掉一條，并不影響電話網(wǎng)的連通性，同時又可節(jié)省一條線。所以圖4－5（b）對應(yīng)的方案不是線數(shù)最少的。因此，滿足要求的電話網(wǎng)必須是：①連通的；②不含圈的。滿足這兩點(diǎn)要求的圖稱為“樹”。a)b)圖4－5不連通和連通圖定義4－6連通且不含圈的無向圖稱為樹。樹中次為1的頂點(diǎn)稱為樹葉(懸掛點(diǎn))，次大于1的頂點(diǎn)稱為分枝點(diǎn)。樹是一種重要的簡單圖，在許多領(lǐng)域都有廣泛的應(yīng)用，如行政機(jī)構(gòu)和軍隊建制中的隸屬關(guān)系、圖書分類、會計科目、決策過程等等都可以用樹表示。下面研究樹的性質(zhì)。樹的性質(zhì)可用下面定理給出。4.2.2最小生成樹算法尋找最小生成樹首先考慮構(gòu)建生成樹，但要在舍邊和增邊時，增加一些邊的權(quán)數(shù)的限制。一、破圈法破圈法步驟：從圖中任取一圈，去掉這個圈中權(quán)數(shù)最大的一條邊，得一支撐子圖。在中再任取一圈，再去掉圈中權(quán)數(shù)最大的一條邊，得。如此繼續(xù)下去，一直到剩下的子圖中不再含圈為止。該子圖就是的最小生成樹。二、Kruskal算法（避圈法）Kruskal算法是Kruskal于1956年提出的一個產(chǎn)生最小樹的算法，算法的基本思想是：每次將一條權(quán)最小的弧加入子圖T中，并保證不形成圈。即按照邊長由小到大排序，如果當(dāng)前弧加入后不形成圈，則加入這條弧。當(dāng)弧有條時，即為最小生成樹。例4-2用Kruskal算法求解下圖4-6(a)所示網(wǎng)絡(luò)的最小生成樹，每條邊上的數(shù)表示該邊的權(quán)值。解：通過對邊由小到大排序，按照避圈法的原則，初步增加到T中。最小生成樹如下：4.2.3最小生成樹Excel軟件求解樹是一種重要的簡單圖，在許多領(lǐng)域都有廣泛的應(yīng)用。我們稱連通且不含圈的無向圖為為樹。若圖的生成子圖是一棵樹，則該樹稱為的生成樹。樹的各條邊稱為樹枝，一般圖包含有多個生成樹，最小生成樹是其中樹枝總長最小的生成樹。圖的最小生成樹一般不唯一。最小生成樹是網(wǎng)絡(luò)優(yōu)化中一個重要的概念，它在交通網(wǎng)、電話網(wǎng)、管道網(wǎng)、電力網(wǎng)等設(shè)計中均有廣泛的應(yīng)用。在城市間高速公路的建設(shè)、城市間通信網(wǎng)絡(luò)線路的鋪設(shè)、輸油管線的架設(shè)、礦井通風(fēng)設(shè)施的優(yōu)化設(shè)計與改造等方面，可以應(yīng)用最小生成樹的原理使得建設(shè)的成本最小。盡管我們已經(jīng)介紹了破圈法、Kruskal算法求最小生成樹，但是這幾種方法對于復(fù)雜案例計算量太大，無法直接用來解決實際問題，因此，方便快捷地產(chǎn)生最小生成樹的系統(tǒng)軟件引起了人們的關(guān)注。EXCEL規(guī)劃求解的功能十分強(qiáng)大，利用EXCEL的規(guī)劃求解功能產(chǎn)生最小生成樹樹將具有較大的意義。下面我們通過前面介紹過的例4-2作為具體案例，用Excel軟件求解最小生成樹。例4－3用Excel軟件求解網(wǎng)絡(luò)圖4-6(a)中的最小生成樹。解：使用Excel軟件求解最小生成樹的基本步驟如下：（1）輸入網(wǎng)絡(luò)圖4-6(a)到Excel工作表中，如下列表4-1所示。表中左上角是一個5×5的對稱權(quán)矩陣。例如（1,2）位置的“1”代表從v1O點(diǎn)到v2點(diǎn)的距離；同樣，（2,1）位置的“1”代表的是從v2點(diǎn)到點(diǎn)v1的距離。矩陣中“10000”代表距離是無窮大，意味著相應(yīng)兩點(diǎn)間沒有路。（2）輸入5×5的變量矩陣（可以輸入任意數(shù)）在Excel工作表的A8：E12的單元格矩陣中。矩陣中的元素只能取“0”和“1”，“0”代表沒有選中，“1”代表被選中。例如結(jié)果中如果顯示B8=1，意味著最優(yōu)路徑中包括了從點(diǎn)v1到點(diǎn)v2的路。（3）輸入約束條件：1）變量矩陣的每行的行和大于等于1（見下表中的F8：F13單元格,它取該行元素的和）。這意味著一個節(jié)點(diǎn)至少與其它一個節(jié)點(diǎn)相連。2）變量矩陣的每列的列和（A13：E13）等于相應(yīng)的行和（對稱矩陣）。3）總邊數(shù)（B16）等于頂點(diǎn)數(shù)減一(此例為4)，這是樹的定義。總邊數(shù)就是A8：E12的所有元素和除以“2”（因為每條邊有兩個節(jié)點(diǎn)重復(fù)計算了一次，所有要除以“2”）。見下表中B16單元格。（4）輸入目標(biāo)函數(shù)：總建設(shè)費(fèi)用最小?？偨ㄔO(shè)費(fèi)用等于選中路徑的權(quán)重之和，即SUMPRODUCT(A1:E5，A8:E12)/2（見表中B15單元格）。表4－1最小生成樹的Excel計算過程（5）求解：目標(biāo)函數(shù)：Min（總建設(shè)費(fèi)用最小）約束條件：變量矩陣=bin總邊數(shù)=頂點(diǎn)個數(shù)-1=3行和大于等于1行和等于列和應(yīng)用Excel的規(guī)劃求解模塊求解如圖4-7所示：圖4－7Excel求解的輸入界面（6）結(jié)果顯示如圖4-8所示：圖4－8Excel求解的最小生成樹輸出結(jié)果從上圖看出最小生成樹為(v1,v2)、(v2,v3)、(v3,v4)、(v3,v5)、構(gòu)建成的，最小費(fèi)用為三邊的權(quán)重之和為14與例4-2的結(jié)果一致。4.3最短路與最大流問題最短路問題是網(wǎng)絡(luò)理論中應(yīng)用最廣泛的問題之一。許多優(yōu)化問題可以使用這個模型，如設(shè)備更新、管道鋪設(shè)、線路安排、廠區(qū)布局等。圖論方法是求最短路問題的有效方法。最大流問題是一類應(yīng)用極為廣泛的問題，例如在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車流、貨物流，供水網(wǎng)絡(luò)中有水流，金融系統(tǒng)中有現(xiàn)金流，通信系統(tǒng)中有信息流，等等。20世紀(jì)50年代,福特（Ford）、富克遜（Fulkerson）建立的“網(wǎng)絡(luò)流理論”是網(wǎng)絡(luò)應(yīng)用的重要組成部分。所謂的最大流量問題就是：給一個帶收發(fā)點(diǎn)的網(wǎng)絡(luò)（一般收點(diǎn)用表示，發(fā)點(diǎn)用表示，其余為中間點(diǎn)），其每條弧的權(quán)值稱之為容量，在不超過每條弧的容量的前提下，要求確定每條弧的流量，使得從發(fā)點(diǎn)到收點(diǎn)的流量最大。

4.3.1最短路算法

Dijkstra算法（雙標(biāo)號法）是公認(rèn)的好算法。在圖論中，所謂“好算法”，即在任何圖上施行這個算法所需要的計算步數(shù)都能以該圖頂點(diǎn)數(shù)和弧數(shù)的一個多項式（如）為其上界。若一個算法的施行需要指數(shù)步數(shù)（如），則對某些大的圖而言，它將是無效的。最后再強(qiáng)調(diào)一下,Dijkstra算法只適用于權(quán)值為正實數(shù)的情況，如果權(quán)值有負(fù)的，算法失效。Dijkstra算法都是求點(diǎn)到點(diǎn)之間的最短路。4.3.2最短路問題EXCEL軟件求解最短路問題是網(wǎng)絡(luò)計劃問題中應(yīng)用最廣泛的問題之一。在前面的學(xué)習(xí)中，求解最短路問題的方法主要介紹了Dijkstra算法。不同于傳統(tǒng)的Dijkstra算法，用excel求解最短路問題，利用了excel的“規(guī)劃求解”在確定最優(yōu)方案的計算方面有獨(dú)到之處的優(yōu)點(diǎn)，通過直接或間接地把電子表格中與公式相聯(lián)系的一組單元格中的數(shù)值進(jìn)行調(diào)整，使某個與公式相關(guān)聯(lián)的單元格達(dá)到期望的結(jié)果，由此來為電子表格中滿足一定要求的單元格找到一個優(yōu)化值。這是一個典型的圖論中的最短路問題，下面我們介紹使用EXCEL建模求解的具體思路。在用EXCEL解決最短路問題時，起點(diǎn)相當(dāng)于供應(yīng)量為1的供應(yīng)點(diǎn)，終點(diǎn)相當(dāng)于需求量為1需求點(diǎn)，所有其余的節(jié)點(diǎn)都是轉(zhuǎn)運(yùn)點(diǎn)，所以每一個所產(chǎn)生的凈流量為0；弧的長度可以看作是網(wǎng)絡(luò)中流的單位成本；如果我們選擇的路經(jīng)過某一特定的弧，則認(rèn)為該弧的流量為1，否則流量為0.這樣一來，使某條路的總長度最短就等價于網(wǎng)絡(luò)流的總費(fèi)用最小。這就是EXCEL規(guī)劃求解建模的基本原則。Excel求解具體過程：（1）將網(wǎng)絡(luò)圖輸入到excel表格中，在每一行記錄每一條弧的起點(diǎn)、終點(diǎn)以及弧的權(quán)值，留空一列（假設(shè)C列）代表是否選擇此路徑可以使路程最短，“1”代表選擇此路徑，而“0”代表不選擇此路徑。（2）確定目標(biāo)函數(shù)。通過C列與距離（即權(quán)值）分別相乘再相加后，就可求得最短路的總距離，而C列的數(shù)值就代表了為使得路徑最短而需走過的路線。（3）確定約束條件。在網(wǎng)絡(luò)圖中，起點(diǎn)只有流出沒有流入，終點(diǎn)只有流入沒有流出，而中間各點(diǎn)的流入流出量均相等，根據(jù)這些條件，可以對圖中每一個頂點(diǎn)做一個約束。指向一個頂點(diǎn)的弧對應(yīng)C列的值之和即為該頂點(diǎn)的流入量，同理，從一頂點(diǎn)指出的弧對應(yīng)C列的值之和即為該頂點(diǎn)的流出量，對于中間各點(diǎn)這兩者應(yīng)相等。另外，為了方便約束條件的書寫，特將起點(diǎn)的流入量和終點(diǎn)的流出量設(shè)定為1。（4）設(shè)定規(guī)劃求解參數(shù)。a.設(shè)置目標(biāo)函數(shù)為最小值。b.設(shè)定可變單元格（即自變量）為C列的值。c.設(shè)定約束條件：C列自變量只能取二進(jìn)制0-1的形式，流出量與流入量相等。d.選擇求解方法為單純線性規(guī)劃。（5）計算得出規(guī)劃求解結(jié)果。經(jīng)過規(guī)劃求解后，可以得到最短路徑的最小總距離，也可以通過表格觀察得到具體的路徑，C列中取1的即表示該弧被選入路徑中。倘若需要計算從起點(diǎn)到非終點(diǎn)的最短距離最短路，則相應(yīng)的改變約束條件即可。在此，我們利用Excel軟件對例4－11進(jìn)行求解，為讀者展示如何用Excel求解最短路問題。例4－5一個網(wǎng)絡(luò)圖G見圖4－11。其中v1是起點(diǎn)，v8為終點(diǎn)，其余各節(jié)點(diǎn)為中間點(diǎn)，各有向邊上的數(shù)字權(quán)重即為路程長度。用EXCEL軟件求起點(diǎn)v1到終點(diǎn)v8的最短路徑。圖4－11有8個節(jié)點(diǎn)的有向網(wǎng)絡(luò)圖解：下面是按照上述解釋給出最短路問題的電子表格模型及其求解過程。圖4－12求最短路的EXCEL輸入過程建立模型如圖4－12。A列與B列分別代表某條有向弧的起始節(jié)點(diǎn)和終止節(jié)點(diǎn)，D列代表這條弧的權(quán)重系數(shù)。C列是一組0-1變量，用來表示是否經(jīng)過某條弧。F列分別代表圖中的八個節(jié)點(diǎn)，由以上分析知，起始點(diǎn)v1的凈流量（即出度-入度）為1，終止點(diǎn)v8的凈流量為-1，其余中間點(diǎn)為0，I列即為設(shè)定好的凈流量數(shù)值列，G列為檢驗列，需要和F列相應(yīng)行保持一致。其中，G列設(shè)置如下：圖4－13檢驗列的輸入過程約束條件和目標(biāo)函數(shù)設(shè)置。約束條件總共有兩個，第一個需要將C列設(shè)為0-1變量；第二個約束需要使G列與I列數(shù)值一致保證圖形邏輯。目標(biāo)函數(shù)變量即C21，為C列與D列點(diǎn)乘之積。具體規(guī)劃求解方案如圖4－14:圖4－14EXCEL求解的輸入界面規(guī)劃求解結(jié)果如圖4－15：圖4－15EXCEL求解最短路的輸出結(jié)果其中，C列中1代表該弧被選中構(gòu)成最短路，0為未構(gòu)成最短路徑，最短路即為v1-v3-v6-v5-v8,最短路長度即為12。4.3.3最大流算法一、最大流的基本概念現(xiàn)在考慮這樣一個問題，要把一批貨物從起點(diǎn)通過鐵路網(wǎng)絡(luò)運(yùn)到終點(diǎn)去，把鐵路網(wǎng)上的車站看作頂點(diǎn)，兩個車站間的鐵路線看作弧，而每條鐵路線上運(yùn)送的貨物總量（容量）總是有限的，我們把某線路上的最大可能運(yùn)送量稱為它的容量，即每條弧上通過的貨物總量不能超過這條弧的容量。考慮：如何安排運(yùn)輸方案，使得從起點(diǎn)運(yùn)到終點(diǎn)的總運(yùn)量達(dá)到最大？圖4－16鐵路容量網(wǎng)絡(luò)圖上面這個問題就是要在鐵路網(wǎng)絡(luò)上，求最大流的問題。這里的“流”，是指鐵路線（弧）上的實際運(yùn)輸量。圖4－16所示網(wǎng)絡(luò)中，每條弧旁的數(shù)字即為該弧的容量，弧的方向就是允許流的方向。顯然，在研究該問題時，可以把網(wǎng)絡(luò)中指向起點(diǎn)的弧以及從終點(diǎn)出發(fā)的弧都去掉，而不會影響問題的解。下面以圖4－17為例來介紹最大流問題的基本概念與模型。圖4－17網(wǎng)絡(luò)圖中的容量和可行流（1）容量網(wǎng)絡(luò)與流在研究網(wǎng)絡(luò)流問題時，首先應(yīng)給出各弧的通過能力，如圖4－16所示各弧的權(quán)數(shù)，它們表示弧的容量，記為，我們把標(biāo)有弧容量的網(wǎng)絡(luò)稱為容量網(wǎng)絡(luò)，記為。2)節(jié)點(diǎn)流量平衡條件：網(wǎng)絡(luò)中的流量必須滿足守恒條件，對收發(fā)點(diǎn)來說，發(fā)點(diǎn)的總流出量=收點(diǎn)的總流入量；對中間點(diǎn)來說，中間點(diǎn)的總流入量=總流出量。例如，對一個給定的容量網(wǎng)絡(luò)，凡是滿足以上兩個條件的網(wǎng)絡(luò)流都稱為可行流。顯然，上圖4－17網(wǎng)絡(luò)流為可行流。尋求網(wǎng)絡(luò)最大流就是找到一個可行流，使得網(wǎng)絡(luò)發(fā)點(diǎn)到收點(diǎn)的總流量達(dá)到最大。網(wǎng)絡(luò)最大流問題的線性規(guī)劃表達(dá)式是顯然，網(wǎng)絡(luò)最大流問題是一個典型而又特殊的線性規(guī)劃問題，一個可行流相當(dāng)于線性規(guī)劃中的一個可行解，而尋求最大流就相當(dāng)于求網(wǎng)絡(luò)容量的最優(yōu)解，自然可用介紹過的單純形法進(jìn)行求解。但利用單純形方法得到網(wǎng)絡(luò)最大流問題的解，計算量過大。由于這一問題的特殊性，用網(wǎng)絡(luò)模型方法求解，更直觀、簡便。下面介紹由Ford和Fulkerson于1956年提出的算法。為此，先介紹與求解方法有關(guān)的概念和原理。第四步：再標(biāo)號同上述第二步標(biāo)號，易見，當(dāng)給標(biāo)號后，無法再進(jìn)行下去，此時，，，。因此，目前所得到的可行流就是最大流，最大流量為。4.3.4最大流算法的Excel軟件求解最大流問題也具有極為廣泛的運(yùn)用，通過前面的學(xué)習(xí)，我們了解到求解此問題的方法為最大流最小截集定理以及Ford-Fulkerson標(biāo)號算法。由于最大流最小截集定理較為繁瑣，在運(yùn)用時也易出錯，所以更為常用的方法是Ford-Fulkerson標(biāo)號算法。在本節(jié)，通過使用Excel對教材中例4－7進(jìn)行求解，為讀者展示如何用Excel求解最大流問題。這是一個典型的最大流問題，在用EXCEL規(guī)劃求解時，其思路不同于傳統(tǒng)算法。在用EXCEL求解時，最大流問題與最短路問題模型的構(gòu)建是類似的，但有幾個條件需要改變。首先是可行流量為小于或等于容量的關(guān)系；其次是起始與終止點(diǎn)的邏輯判斷值不再是1和-1而變?yōu)闊o限制；再者是目標(biāo)函數(shù)應(yīng)該求最大值。例4－8用Excel軟件求圖4－19所示的網(wǎng)絡(luò)最大流，括號中第一個數(shù)字是容量，第二個數(shù)字是容量。

原理同求解最短路問題相同，將上述的網(wǎng)絡(luò)圖鍵入，如圖4-20所示。圖4－20網(wǎng)絡(luò)圖以及容量的輸入界面其中，關(guān)于目標(biāo)單元格的設(shè)置需要根據(jù)具體問題具體設(shè)置。在最大流問題中，最大流等于起點(diǎn)的流出量或終點(diǎn)的流入量之和，可變單元格即為流量，而約束條件有以下3條：（1）各節(jié)點(diǎn)流量值小于等于各節(jié)點(diǎn)的容量值；（2）起點(diǎn)只有流出無流入，終點(diǎn)只有流入無流出。起點(diǎn)的流出量與終點(diǎn)的流入量相等；（3）各節(jié)點(diǎn)的流量和為0，即流入量等于流出量。如圖4－21示。圖4－21最大流的約束條件輸入通過規(guī)劃求解，可得最大流為5，求解結(jié)果如圖4－22所示。這與例4－7用Ford-Fulkerson標(biāo)號算法獲得的結(jié)果是一致的。

圖4－22最大流的結(jié)果輸出界面例4－9某公司要運(yùn)輸一批物資。構(gòu)建一個網(wǎng)絡(luò)圖G如圖4－23。其中v1是起點(diǎn)，v8為終點(diǎn)，其余各節(jié)點(diǎn)為中間點(diǎn)，各有向邊上的數(shù)字權(quán)重即為容量，括號中數(shù)字代表初始可行流。求從起點(diǎn)到終點(diǎn)的運(yùn)輸方案，使得運(yùn)輸量最大。

圖4－23運(yùn)輸容量網(wǎng)絡(luò)圖這是一個典型的最大流問題。把圖4－23鍵入建立模型，如圖4－24所示。A列與B列的含義與最短路一致；C列代表路徑流量，不再設(shè)限制；弧上的容量體現(xiàn)在E列中，E列大于等于C列；H列為各點(diǎn)的出量減去入量，因而起點(diǎn)v1與終點(diǎn)v8不設(shè)限制而中間點(diǎn)應(yīng)為0，但起點(diǎn)與終點(diǎn)在數(shù)值上應(yīng)為相反數(shù)關(guān)系。J列即為邏輯判斷值限制列。

圖4－24EXCEL最大流條件輸入界面H列的設(shè)置與最短路問題十分相似，具體設(shè)置如圖4－25：約束條件和目標(biāo)函數(shù)。約束條件共兩個，即流量小于等于容量和凈流量等于供應(yīng)-需求。目標(biāo)函數(shù)即凈流量起點(diǎn)v1值最大。規(guī)劃求解方案如圖4－26：

圖4－26最大流的求解輸入界面圖4－25最大流每個節(jié)點(diǎn)的凈流量輸入規(guī)劃求解結(jié)果如圖4－27：圖4－27最大流的求解結(jié)果輸出界面凈流量不為0的弧所對應(yīng)的凈流量值即為最大流經(jīng)過的流量值（如從v1到v2的弧流量為9）；最大流為19。

4.4網(wǎng)絡(luò)計劃技術(shù)用網(wǎng)絡(luò)分析的方法編制的生產(chǎn)計劃稱為網(wǎng)絡(luò)計劃。它是20世紀(jì)50年代發(fā)展起來的一種編制大型工程進(jìn)度計劃的有效方法。1956年，美國杜邦公司在制定企業(yè)不同業(yè)務(wù)部門的系統(tǒng)規(guī)劃時，制定了第一套網(wǎng)絡(luò)計劃。這種計劃借助于網(wǎng)絡(luò)表示各項工作與所需要的時間，以及各項工作的相互關(guān)系。通過網(wǎng)絡(luò)分析研究工程費(fèi)用與工期的相互關(guān)系。并找出在編制計劃時及計劃執(zhí)行過程中的關(guān)鍵路線。這種方法稱為關(guān)鍵路線法（CriticalPathMethod）簡稱CPM。1958年，美國海軍武器部，在制定研制“北極星”導(dǎo)彈計劃時，同樣地應(yīng)用了網(wǎng)絡(luò)分析方法與網(wǎng)絡(luò)計劃。但它注重于對各項工作安排的評價和審查。這種計劃稱為計劃評審方法（ProgramEvaluationandReviewTechnique）簡稱為PERT。鑒于這兩種方法的差別，所以，CPM主要應(yīng)用于以往在類似工程中已取得一定經(jīng)驗的承包工程；PERT更多地應(yīng)用于研究與開發(fā)項目。在這兩種方法得到應(yīng)用推廣之后，又陸續(xù)出現(xiàn)了類似的最低成本和估算計劃法、產(chǎn)品分析控制法、人員分配法、物資分配和多種項目計劃制定法等等。雖然方法很多，各自側(cè)重的目標(biāo)有所不同。但它們都應(yīng)用的是CPM和PERT的基本原理和基本方法。20世紀(jì)60年代該方法引入我國并開始進(jìn)行推廣應(yīng)用。目前，這些方法被世界各國廣泛應(yīng)用于工業(yè)、農(nóng)業(yè)、國防、科研等管理計劃中，對縮短工期，節(jié)約人力、物力和財力，提高經(jīng)濟(jì)效益發(fā)揮了重要的作用。網(wǎng)絡(luò)計劃的基本原理是：從需要管理的任務(wù)的總進(jìn)度著眼，以任務(wù)中各工作所需要的工時為時間因素，按照工作的先后順序和相互關(guān)系作出網(wǎng)絡(luò)圖，以反映任務(wù)的全貌，實現(xiàn)管理過程的模型化。然后進(jìn)行時間參數(shù)計算，找出計劃中的關(guān)鍵工序和關(guān)鍵路線，對任務(wù)的各項工作所需的人力、物力和財力通過改善網(wǎng)絡(luò)計劃作出合理安排，得到最優(yōu)方案并付諸實施。國內(nèi)外應(yīng)用網(wǎng)絡(luò)計劃的實踐表明，它具有一系列優(yōu)點(diǎn)，特別適用于生產(chǎn)技術(shù)復(fù)雜，工作項目繁多、且聯(lián)系緊密的一些跨部門的工作計劃。例如新產(chǎn)品研制開發(fā)、大型工程項目、生產(chǎn)技術(shù)準(zhǔn)備、設(shè)備大修等計劃。網(wǎng)絡(luò)計劃內(nèi)容包括繪制網(wǎng)絡(luò)圖，計算時間參數(shù)，確定關(guān)鍵路線及網(wǎng)絡(luò)優(yōu)化等環(huán)節(jié)。下面分別討論這些內(nèi)容。4.4.1網(wǎng)絡(luò)圖的繪制為了編制網(wǎng)絡(luò)計劃，首先需繪制網(wǎng)絡(luò)圖。網(wǎng)絡(luò)圖是由節(jié)點(diǎn)(點(diǎn))、弧及權(quán)所構(gòu)成的有向圖。即有向的賦權(quán)圖。 節(jié)點(diǎn)表示一個事項（或事件），它是一個或若干個工序的開始或結(jié)束，是相鄰工序在時間上的分界點(diǎn)。節(jié)點(diǎn)用圓圈和里面的數(shù)字表示，數(shù)字表示節(jié)點(diǎn)的編號，如①，②，…等。它不需要占用時間和資源，只代表某項工序的開始或結(jié)束。 弧表示一個工序（或作業(yè)、工作），工序是指為了完成工程項目，在工藝技術(shù)和組織管理上相對獨(dú)立的具體的工作或活動。一項工程由若干個工序組成。工序需要一定的人力、物力等資源和時間。弧用箭線“→”表示。在網(wǎng)絡(luò)圖上，一項工序用一條箭線來表示，箭尾表示工序的開始，箭頭表示工序的結(jié)束。權(quán)表示為完成某個工序所需要的時間或資源等數(shù)據(jù)。通常標(biāo)注在箭線下面或其它合適的位置上。虛工序用虛箭線“┄→”表示。它不是一項具體的工作，它不需要人力、物力等資源和時間，即不消耗任何資源的虛構(gòu)工作。在網(wǎng)絡(luò)圖中僅表明一項工序與另一項工序間的前行后繼關(guān)系，或表示某工序必須在另外一個工序結(jié)束后才能開始。例4－10某項研制新產(chǎn)品工程的各個工序與所需時間以及它們之間的相互關(guān)系如表4－2所示。要求編制該項工程的網(wǎng)絡(luò)計劃。表4－2新產(chǎn)品工程項目的任務(wù)分解和分析工

序工序代號所需時間(天)緊后工序產(chǎn)品設(shè)計與工藝設(shè)計a65b，c，d，e外購配套件b45l下料、鍛件c10f工裝制造1d20g，h木模、鑄件e40h機(jī)械加工1f18l工裝制造2g30k機(jī)械加工2h15l機(jī)械加工3k25l裝配調(diào)試l35—根據(jù)表4－2的已知條件和數(shù)據(jù)，繪制的網(wǎng)絡(luò)如圖4－28所示。在圖4－28中，箭線a、b、…、l分別代表10個工序。箭線下面的數(shù)字表示為完成該個工序所需的時間（天數(shù)）。節(jié)點(diǎn)①、②、…、⑧分別表示某一或某些工序的開始和結(jié)束。例如，節(jié)點(diǎn)②表示a工序的結(jié)束和b、c、d、e等工序的開始，即a工序結(jié)束后，后四個工序才能開始。圖4－28網(wǎng)絡(luò)圖繪制12467835a6045c10d20e40f18g30h15k25l350在繪制網(wǎng)絡(luò)圖中，用一條弧和兩個節(jié)點(diǎn)表示一個確定的工序。例如，②→⑦表示一個確定的工序b。工序開始的節(jié)點(diǎn)稱為箭尾節(jié)點(diǎn)，如b工序的②；工序結(jié)束的節(jié)點(diǎn)稱為箭頭節(jié)點(diǎn)，如b工序的⑦。②稱為箭尾事項，⑦稱為箭頭事項。工序的箭尾事項與箭頭事項稱為該工序的相關(guān)事項。在一張網(wǎng)絡(luò)圖上只能有始點(diǎn)和終點(diǎn)兩個節(jié)點(diǎn)，分別表示工程的開始和結(jié)束，其它節(jié)點(diǎn)既表示上一個（或若干個）工序的結(jié)束，又表示下一個（或若干個）工序的開始。 為正確反映工程中各個工序的相互關(guān)系，在繪制網(wǎng)絡(luò)圖時，應(yīng)遵循以下規(guī)則：(1)方向、時序與節(jié)點(diǎn)編號 網(wǎng)絡(luò)圖是有向圖，按照工藝流程的順序，規(guī)定工序從左向右排列。網(wǎng)絡(luò)圖中的各個節(jié)點(diǎn)都有一個時間(某一個或若干個工序開始或結(jié)束的時間)，一般按各個節(jié)點(diǎn)的時間順序編號。為了便于修改編號及調(diào)整計劃，可以在編號過程中留出一些編號。始點(diǎn)編號可以從1開始，也可以從0開始。網(wǎng)絡(luò)圖應(yīng)從左向右延伸，編號應(yīng)從小到大，且不重復(fù)。箭頭事項編號大于箭尾事項編號。(2)

緊前工序與緊后工序 例如，在圖4－28中，只有在a工序結(jié)束以后，b、c、d、e工序才能開始。a工序是b、c、d、e等工序的緊前工序，而b、c、d、e等工序則是工序a的緊后工序。(3)虛工序 為了用來表達(dá)相鄰工序之間的銜接關(guān)系，而實際上并不存在而虛設(shè)的工序。虛工序不需要人力、物力等資源和時間。只表示某工序必須在另外一個工序結(jié)束后才能開始。如圖4－28中，虛工序④┄→⑤只表示在d工序結(jié)束后，h工序才能開始。(4)相鄰兩個節(jié)點(diǎn)之間只能有一條弧即一個工序用確定的兩個相關(guān)事項表示，某兩個相鄰節(jié)點(diǎn)只能是一個工序的相關(guān)事項。在計算機(jī)上計算各個節(jié)點(diǎn)和各個工序的時間參數(shù)時，相關(guān)事項的兩個節(jié)點(diǎn)只能表示一道工序，否則將造成邏輯上的混亂。如圖4－29的畫法是錯誤的，圖4－30的畫法是正確的。

即一個工序用確定的兩個相關(guān)事項表示，某兩個相鄰節(jié)點(diǎn)只能是一個工序的相關(guān)事項。在計算機(jī)上計算各個節(jié)點(diǎn)和各個工序的時間參數(shù)時，相關(guān)事項的兩個節(jié)點(diǎn)只能表示一道工序，否則將造成邏輯上的混亂。如圖4－29的畫法是錯誤的，圖4－30的畫法是正確的。(5)網(wǎng)絡(luò)圖中不能有缺口和回路在網(wǎng)絡(luò)圖中，除始點(diǎn)和終點(diǎn)外，其它各個節(jié)點(diǎn)的前后都應(yīng)有弧相連接，即圖中不能有缺口，使網(wǎng)絡(luò)圖從始點(diǎn)經(jīng)任何路線都可到達(dá)終點(diǎn)。否則，將使某些工序失去與其緊后（或緊前）工序應(yīng)有的聯(lián)系。在本章討論的網(wǎng)絡(luò)圖中不能有回路，即不可能有循環(huán)現(xiàn)象。否則，將使組成回路的工序永遠(yuǎn)不能結(jié)束，工程永遠(yuǎn)不能完工。在如下網(wǎng)絡(luò)圖4－31中出現(xiàn)的情況，顯然是錯誤的。(6)平行作業(yè)為縮短工程的完工時間，在工藝流程和生產(chǎn)組織條件允許的情況下，某些工序可以同時進(jìn)行，即可采用平行作業(yè)的方式。如在圖4－28中，工序b、c、d、e四個工序即可平行作業(yè)。在有幾個工序平行作業(yè)結(jié)束后轉(zhuǎn)入下一道工序的情況下，考慮到便于計算網(wǎng)絡(luò)時間和確定關(guān)鍵路線，選擇在平行作業(yè)的幾個工序中所需時間最長的一個工序，直接與其緊后工序銜接，而其它工序則通過虛工序與其緊后工序銜接。如在圖4－28中，工序d、e平行作業(yè)，這兩個工序都結(jié)束后，它們的緊后工序h才可能開始。在工序d、e中，工序e所需的時間(40天)比工序d所需時間(20天)長，則工序e直接與工序h連接，而工序d則通過虛工序與工序h連接。(7)交叉作業(yè)對需要較長時間才能完成的一些工序，在工藝流程與生產(chǎn)組織條件允許的情況下，可以不必等待工序全部結(jié)束后再轉(zhuǎn)入其緊后工序，而是分期分批的轉(zhuǎn)入。這種方式稱為交叉作業(yè)。交叉作業(yè)可以縮短工程周期。如在圖4－28中，將工裝制造分為兩批，將一個工序分為兩個工序d、g，分別與緊后工序h、k連接。(8)始點(diǎn)和終點(diǎn)為表示工程的開始和結(jié)束，在網(wǎng)絡(luò)圖中只能有一個始點(diǎn)和一個終點(diǎn)。當(dāng)工程開始時有幾個工序平行作業(yè)，或在幾個工序結(jié)束后完工，用一個始點(diǎn)、一個終點(diǎn)表示。若這些工序不能用一個始點(diǎn)或一個終點(diǎn)表示時，可用虛工序把它們與始點(diǎn)或終點(diǎn)連起來。(9)網(wǎng)絡(luò)圖的分解與綜合根據(jù)網(wǎng)絡(luò)圖的不同需要，一個工序所包括的工作內(nèi)容可以多一些，即工序綜合程度較高。也可以在一個工序中所包括的工作內(nèi)容少一些，即工序綜合程度較低。一般情況下，工程總指揮部制定的網(wǎng)絡(luò)計劃是工序綜合程度較高的網(wǎng)絡(luò)圖（母網(wǎng)絡(luò)圖）而下一級部門，根據(jù)綜合程度高的網(wǎng)絡(luò)圖的要求，制定本部門的工序綜合程度低的網(wǎng)絡(luò)圖（子網(wǎng)絡(luò)圖）。將母網(wǎng)絡(luò)分解為若干個子網(wǎng)絡(luò)，稱為網(wǎng)絡(luò)圖的分解。而將若干個子網(wǎng)絡(luò)綜合為一個母網(wǎng)絡(luò)，則稱為網(wǎng)絡(luò)圖的綜合。若將圖4－28視為一個母網(wǎng)絡(luò)。它可以分解為工序a，工序b、c、d、e、f、g、h、k，及工序l三個子網(wǎng)絡(luò)。工序a和工序l都可以再分解為綜合程度較低的若干個工序。(10)網(wǎng)絡(luò)圖的布局在網(wǎng)絡(luò)圖中，盡可能將關(guān)鍵路線布置在中心位置，并盡量將聯(lián)系緊密的工作布置在相近的位置。為使網(wǎng)絡(luò)圖清楚和便于在圖上填寫有關(guān)的時間數(shù)據(jù)與其它數(shù)據(jù)，弧線盡量用水平線或具有一段水平線的折線。網(wǎng)絡(luò)圖也可以附有時間進(jìn)度；必要時也可以按完成各工序的工作單位布置網(wǎng)絡(luò)圖。4.4.2網(wǎng)絡(luò)圖的編制網(wǎng)絡(luò)圖的繪制一般可以分為三步（1）確定目標(biāo)，做好編制網(wǎng)絡(luò)計劃的準(zhǔn)備工作。確定目標(biāo)就是確定哪一項任務(wù)，明確任務(wù)最后要達(dá)到的目的和目標(biāo)。（2）進(jìn)行任務(wù)分解和分析。（3）繪制網(wǎng)絡(luò)圖。4.4.3路線與關(guān)鍵路線在網(wǎng)絡(luò)圖中，從始點(diǎn)開始，按照各個工序的順序，連續(xù)不斷地到達(dá)終點(diǎn)的一條通路稱為路線。如在圖4－30中，共有五條路線，五條路線的組成及所需要的時間如表4－4所示。表4－4新產(chǎn)品工程項目的路線及其時間在各條路線上，完成各個工序的時間之和是不完全相等的。其中，完成各個工序需要時間最長的路線稱為關(guān)鍵路線，或稱為主要矛盾線，在圖中用粗線表示。在表4－4中，第三條路線就是條關(guān)鍵路線，組成關(guān)鍵路線的工序稱為關(guān)鍵工序。路線路

線

的

組

成

各工序所需的時間之和(天)1①→②→⑦→⑧

60+45+35=1402①→②→③→⑦→⑧

60+10+18+35=1233①→②→④→⑥→⑦→⑧

60+20+30+25+35=1704①→②→④→⑤→⑦→⑧

60+20+15+35=1305①→②→⑤→⑦→⑧

60+40+15+35=150如果能夠縮短關(guān)鍵工序所需的時間，就可以縮短工程的完工時間。而縮短非關(guān)鍵路線上的各個工序所需要的時間，卻不能使工程的完工時間提前。即使在一定范圍內(nèi)適當(dāng)?shù)赝祥L非關(guān)鍵路線上各個工序所需要的時間，也不至于影響整個工程的完工時間。編制網(wǎng)絡(luò)計劃的基本思想就是在一個龐大的網(wǎng)絡(luò)圖中找出關(guān)鍵路線。對各關(guān)鍵工序，優(yōu)先安排資源，挖掘潛力，采取相應(yīng)措施，盡量壓縮需要的時間。而對非關(guān)鍵路線上的各工序，只要在不影響工程完工時間的條件下，抽出適當(dāng)?shù)娜肆Α⑽锪Φ荣Y源，用在關(guān)鍵工序上，以達(dá)到縮短工程工期，合理利用資源等目的。在執(zhí)行計劃過程中，可以明確工作重點(diǎn)，對各關(guān)鍵工序加以有效控制和調(diào)度。關(guān)鍵路線是相對的，也是可以變化的。在采取一定的技術(shù)組織措施之后，關(guān)鍵路線有可能變?yōu)榉顷P(guān)鍵路線。而非關(guān)鍵路線也有可能變?yōu)殛P(guān)鍵路線。 如對網(wǎng)絡(luò)圖4－33，該網(wǎng)絡(luò)圖從始點(diǎn)①到終點(diǎn)⑥共有8條路線，可以分別計算出這8條路線所需的總工時。這8條路線分別為：①→②→④→⑥1＋2＋5＝8天①→②→④→⑤→⑥1＋2＋0＋3＝6天①→②→③→⑤→⑥1＋3＋5＋3＝12天①→②→③→④→⑥1＋3＋6＋5＝15天①→②→③→④→⑤→⑥1＋3＋6＋0＋3＝13天①→③→④→⑤→⑥5＋6＋0＋3＝14天①→③→④→⑥5＋6＋5＝16天①→③→⑤→⑥5＋5＋3＝13天

可以看出①→③→④→⑥所需時間最長，總共需要16天。則該路線就是關(guān)鍵路線，其所對應(yīng)的工序為關(guān)鍵工序。當(dāng)某些工作的時間調(diào)整后，可能引起關(guān)鍵路線的變化和工期的變化。例如將工作E的時間縮短為2天，則工期縮短為12天，關(guān)鍵路線將變?yōu)橐虼岁P(guān)鍵路線是隨著時間、情況的變化在發(fā)生變化。4.4.4網(wǎng)絡(luò)時間參數(shù)的計算為了編制網(wǎng)絡(luò)計劃和找出關(guān)鍵路線，要計算網(wǎng)絡(luò)圖中各個事項及各個工序的有關(guān)時間，稱這些有關(guān)時間為網(wǎng)絡(luò)時間。計算網(wǎng)絡(luò)圖中有關(guān)的時間參數(shù)，其主要目的就是找出關(guān)鍵路線，為網(wǎng)絡(luò)優(yōu)化、調(diào)整和執(zhí)行提供明確的時間概念。下面分別介紹各種網(wǎng)絡(luò)時間參數(shù)。（1）作業(yè)時間作業(yè)時間(Tij)：為完成某一工序（i，j）所需要的時間稱為該工序的作業(yè)時間，用Tij表示。（2)事項時間①事項最早時間TE(j)通常是按箭頭事項計算事項最早時間，用TE(j)表示，它等于從始點(diǎn)事項起到本事項最長路線的時間長度。計算事項最早時間是從始點(diǎn)事項開始，自左向右逐個事件向前計算。假定始點(diǎn)事項的最早時間等于零，即TE(1)=0。箭頭事項的最早時間等于箭尾事項最早時間加上作業(yè)時間。 當(dāng)同時有兩個或若干個箭線指向箭頭事項時，選擇各工序的箭尾事項最早時間與各自工序作業(yè)時間之和的最大值。即：

式中：TE(j)為箭頭事項的最早時間；TE(i)為箭尾事項的最早時間；例如，在網(wǎng)絡(luò)圖4－9中各事項的最早時間為：②事項最遲時間TL(i)通常是按箭頭事項各工序的最遲必須結(jié)束時間，或箭尾事項各工序的最遲必須開始時間,用TL(j)表示。事項最遲時間通常按箭尾事項的最遲時間計算，從右向左反順序進(jìn)行。箭尾事項的最遲時間等于箭頭事項的最遲時間減去該工序的作業(yè)時間。當(dāng)箭尾事項同時引出兩個以上箭線時，該箭尾事項的最遲時間必須同時滿足這些工序的最遲必須開始時間。所以在這些工序的最遲必須開始時間中選一個最早（時間值最?。┑臅r間，即：

將各事項的最遲時間記入該事項的右下角的三角框內(nèi)，見圖4－37所示。工序總時差越大，表明該工序在整個網(wǎng)絡(luò)中的機(jī)動時間越大，可以在一定范圍內(nèi)將該工序的人力、物力資源利用到關(guān)鍵工序上去，以達(dá)到縮短工程結(jié)束時間的目的。⑥工序單時差FF(i,j)在不影響緊后工序最早開始時間的條件下，工序最早結(jié)束時間可以推遲的時間，稱為該工序的單時差。式中，TES(

j,k)為工序(i→j)的緊后工序的最早開始時間。工序總時差、單時差及其緊后工序的最早開始時間、最遲開始時間的關(guān)系如圖4－38所示。從圖4－37中可以看出，工序b與工序c同為工序a的緊后工序。工序a的單時差不影響緊后工序的最早開始時間，而其總時差不僅包含了本工序的單時差，而且包含了工序b,c的時差，使工序c失去了部分時差，而使工序b失去了全部自由機(jī)動時間。占用某一工序的總時差雖然不影響整個任務(wù)的最短工期，卻有可能使其緊后工序失去自由機(jī)動的余地?？倳r差為零的工序，它的開始和結(jié)束的時間沒有一點(diǎn)機(jī)動的余地。由這些工序所組成的路線就是網(wǎng)絡(luò)中的關(guān)鍵路線。這些工序就是關(guān)鍵工序。用計算工序總時差的方法確定網(wǎng)絡(luò)中的關(guān)鍵工序和關(guān)鍵路線是確定關(guān)鍵路線最常用的方法。在圖4－37中，工序a、d、g、k、l的總時差為零，由這些工序組成的路線就是圖4－37中的關(guān)鍵路線。通過上述的網(wǎng)絡(luò)時間參數(shù)計算過程可以看出，計算過程具有一定的規(guī)律和嚴(yán)格的程序，可以在計算機(jī)上進(jìn)行計算，也可以用表格法計算。按表4－5的格式將工序代號、工序時間填入表格前二列，然后按以下順序計算各工序的時間參數(shù)。第一步：計算工序的最早開始時間和最遲結(jié)束時間。由表4－5中事項的最早時間和事項的最遲時間可得各工序的最早開始時間和最早結(jié)束時間。因為TES(i,j)=TE(i)，TLF(i,j)=TL(

j

)可得表4－4中的第3列和第6列。第二步：計算工序的最早結(jié)束時間和最遲開始時間。由表4－5的第3列數(shù)據(jù)加上第2列相應(yīng)數(shù)據(jù)，可得該工序的最早結(jié)束時間，第4列數(shù)據(jù)加上第2列相應(yīng)數(shù)據(jù)，可得該工序的最遲開始時間，并分別列入表4－5中第4列和第5列。第三步：計算各工序的總時差。由表4－5的第6列數(shù)據(jù)減去第4列相應(yīng)數(shù)據(jù)（第5列數(shù)據(jù)減去第3列相應(yīng)數(shù)據(jù)），可得各工序的總時差。

表4－5作業(yè)時間參數(shù)計算

例4－12以圖4－32為例，計算各工序的時間參數(shù)及關(guān)鍵路線如下。具體計算結(jié)果見表4－6

表4－6作業(yè)時間參數(shù)計算由表4－6可得各工序的時間參數(shù)，由總時差為0的工序A、C、G、H為關(guān)鍵工序，由關(guān)鍵工序組成的路線就是所求的關(guān)鍵路線。4.5網(wǎng)絡(luò)優(yōu)化4.6.1工期優(yōu)化問題求解工期優(yōu)化問題時，一般在關(guān)鍵路線上采取相應(yīng)措施：（1）采取技術(shù)措施，縮短關(guān)鍵工序的作業(yè)時間；（2）采取組織措施，將連續(xù)施工的工序調(diào)整為平行施工；（3）充分利用非關(guān)鍵工序的總時差，合理調(diào)配技術(shù)力量及人財物等資源，縮短關(guān)鍵工序的作業(yè)時間。例4－13

某工程要求49周內(nèi)完成，否則賠償25萬元，若在41周內(nèi)完成可獲得18萬元額外獎勵，工序時間如表4-7及網(wǎng)絡(luò)圖如圖4-39所示，應(yīng)如何進(jìn)行網(wǎng)絡(luò)優(yōu)化。表4－7工程工序次序以及時間耗費(fèi)表圖4－39我們利用前面求各種網(wǎng)絡(luò)時間參數(shù)及關(guān)鍵路線方法可以求出各種網(wǎng)絡(luò)時間參數(shù)如圖4-40所示?？倳r差為0的工序為關(guān)鍵工序，因此工程項目的關(guān)鍵工序是：A,B,C,E,F,J,L,andN。圖4－40四個時間參數(shù)輸出結(jié)果縮短工期分析：由網(wǎng)絡(luò)計劃圖4－40可知，此工程網(wǎng)絡(luò)計劃的工期TC為44周，符合此工程的原定49周內(nèi)完成的要求。根據(jù)題意可得，為使獲得18萬元的額外獎勵，必須41周前完工，故需要對其工期壓縮至少3周。若要達(dá)到此目標(biāo)，主要有以下兩種思路。（1）A，B，C工序不受非關(guān)鍵路線余量影響，可優(yōu)先考慮優(yōu)化；（2）若非關(guān)鍵路線上工序作業(yè)時間保持現(xiàn)有情況，則E，F(xiàn)，J，L，N總計可調(diào)整余量為3周，其中L只能調(diào)整1周，E和F共可調(diào)整2周。具體過程如下：（1）根據(jù)各項工作的正常持續(xù)時間，原工期為44周，關(guān)鍵線路A---B---C---E---F---J---L---N。（2）計算應(yīng)縮短的時間：目標(biāo)工期Tr41周，TC(網(wǎng)絡(luò)計劃的計算工期)-Tr(目標(biāo)工期)3周。（3）若A，B，C工序可以通過優(yōu)化以達(dá)到目標(biāo)，則選擇思路一；反之，再加上在非關(guān)鍵路線上工序作業(yè)時間保持現(xiàn)有情況的前提下，E，F(xiàn)，J，L，N總計可調(diào)整余量為3周，恰好可以完成目標(biāo)，即選擇思路二。（4）將關(guān)鍵工序L的持續(xù)時間壓縮至4周，E，F(xiàn)的持續(xù)時間分別壓縮至3，4周。此時，關(guān)鍵線路有4條，A---B---C---E---F---J---L---N，A---B---C---E---F---J---K---N，A---B---C---I---J---L---N，A---B---C---I---J---K---N。計算工期為41周，滿足了此工程的目標(biāo)工期要求。4.6.2時間-費(fèi)用優(yōu)化問題在編制網(wǎng)絡(luò)計劃過程中，研究如何使得工程完工費(fèi)用少和求優(yōu)化工期是類似的。所謂的時間-費(fèi)用優(yōu)化是指：或者在保證既定的工程完工時間的條件下，所需要的費(fèi)用最少；或者在限制費(fèi)用的條件下，工程完工時間最短；這就是時間——費(fèi)用優(yōu)化所要研究和解決的問題。任何一項任務(wù)的成本一般包括直接費(fèi)用和間接費(fèi)用兩部分。直接費(fèi)用包括直接生產(chǎn)工人的工資及附加費(fèi)、設(shè)備、能源、工具及材料消耗等直接與完成工序有關(guān)的費(fèi)用。為縮短工序的作業(yè)時間，需要采取一定的技術(shù)組織措施，相應(yīng)地要增加一部分直接費(fèi)用。在一定條件下和一定范圍內(nèi)，工序的作業(yè)時間越短，直接費(fèi)用就越多。間接費(fèi)用包括管理人員的工資、辦公費(fèi)用等。間接費(fèi)用，通常按照施工時間的長短分?jǐn)偅谝欢ㄉa(chǎn)規(guī)模內(nèi)，工序的作業(yè)時間越短，分?jǐn)偟拈g接費(fèi)用就越少。它們之間的關(guān)系如圖4－41所示。圖4－41工期縮短時直接費(fèi)用要增加而間接費(fèi)用將減少，總成本是由直接費(fèi)用和間接費(fèi)用相加而得?？s短工序的作業(yè)時間也有一定的限度，這個限度稱之為工序的最快完成時間（極限時間）。設(shè)完成工序(i,j)的正常時間為Tij；直接費(fèi)用為Cij；完成工序(i,j)的最快完成時間為tij；間接費(fèi)用為cij。這樣可以計算出縮短工序(i,j)的單位工期所增加的費(fèi)用，用Pij表示： 在進(jìn)行時間——費(fèi)用優(yōu)化時，需要計算在采取各種技術(shù)組織措施之后，工程項目的不同的完工時間所對應(yīng)的工序總費(fèi)用和工程項目所需要的總費(fèi)用。使得工程費(fèi)最低的工程完工時間稱為最低成本日程。編制網(wǎng)絡(luò)計劃，無論是以降低費(fèi)用為主要目標(biāo)，還是以盡量縮短工程完工時間為主要目標(biāo)，都要計算最低成本日程，從而提出時間——費(fèi)用的優(yōu)化方案。下面以一實例說明計算最低成本日程的解題步驟：（1）以正常時間進(jìn)行網(wǎng)絡(luò)分析，求得關(guān)鍵路線；（2）在關(guān)鍵路線上，尋找最小費(fèi)率的工作，縮短其時間，使工期最多到次長路線的長度；（3）縮短工期必須對所有關(guān)鍵路線進(jìn)行，此時應(yīng)選擇費(fèi)率總和最小的組合方案。例4－35

已知網(wǎng)絡(luò)計劃各工序的正常完工時間、最快完工時間及相應(yīng)的費(fèi)用，如表4－8，網(wǎng)絡(luò)圖如圖4－42。按正常完工時間從圖4－42中計算出總工期為74天。關(guān)鍵路線為a，c，f，由表4－8可計算出在正常完工時間情況下總直接費(fèi)用為47800元。設(shè)正常完工時間下，任務(wù)總間接費(fèi)用為18000元，工期每縮短一天，間接費(fèi)用可節(jié)省330元。（1）求最低成本日程。表4-8工序完工時間以及費(fèi)用表工序正常完工最快完工直接費(fèi)用變動率時間（天）費(fèi)用（元）時間（天）費(fèi)用（元）a3090001810200100b245000167000250c26100002410300150d224000184800200e248000209000250f185400185400－g18640010680050解（1）：從表4－8看出，關(guān)鍵路線上的三個關(guān)鍵工序a，c，f的直接費(fèi)用變動率中a的直接費(fèi)用變動率最小，因此應(yīng)選擇在工序a上縮短工時，由表4－11可知，工序a最多可縮短12天。而路線b，d，f的總工期為64天，它只比正常完工時間下的總工期為74天少10天，這就意味著工序a沒有必要減少12天，減少10天就可以了。如圖4－43。此次調(diào)整增加直接費(fèi)用為10*100＝1000元。減少間接費(fèi)用10*330＝3300元。從圖4－72可知，該網(wǎng)絡(luò)圖有兩條關(guān)鍵路線a,c,f與b,d,f。在關(guān)鍵路線a,c,f上，工序a的直接費(fèi)用變動率最小，在關(guān)鍵路線b,d,f上，工序d的直接費(fèi)用變動率最小。將a，d同時縮短一天需直接直接費(fèi)用100＋200＝300元，而工序a可縮短2天，工序d可縮短4天，取其中最小者，及工序a、工序d各縮短2天，此次總工期為62天，調(diào)整增加直接費(fèi)用為2*300＝600元。減少間接費(fèi)用2*330＝660元。

從圖4－44可知，該網(wǎng)絡(luò)圖有兩條關(guān)鍵路線仍然是a,c,f與b,d,f。在關(guān)鍵路線a,c,f上，此時工序a不能縮短工時，因此只能考慮工序c的直接費(fèi)用變動率，在關(guān)鍵路線b,d,f上，工序d還可以繼續(xù)縮短，而它的直接費(fèi)用變動率最小。將c，d同時縮短一天需增加直接費(fèi)用150＋200＝350元，而工序f的直接費(fèi)用變動率為300元，并且f是兩條關(guān)鍵路徑共用的工序，因此首先考慮縮短工序f，工序f可縮短2天，總工期減少為60天。從費(fèi)用角度考慮，調(diào)整增加直接費(fèi)用2*300=600元，減少間接費(fèi)用為2*330=660元。目前關(guān)鍵路徑還是a,c,f與b,d,f。a,c,f上只能考慮縮短工序c；b,d,f上，d的直接費(fèi)用變動率最小，如果將c，d同時縮短一天需增加直接費(fèi)用150＋200＝350元，減少間接費(fèi)用為330元。因此從費(fèi)用角度考慮，再縮短工時費(fèi)用會增加。因此最低成本日程為60天。4.6案例分析案例分析1（光纖網(wǎng)絡(luò)鋪設(shè)問題）默登公司的管理層決定鋪設(shè)最先進(jìn)的光纖網(wǎng)絡(luò)，為它的主要中心之間提供高速通信。圖4-45中的節(jié)點(diǎn)顯示了默登公司主要中心的分布圖。虛線是鋪設(shè)光纖的可能位置。虛線旁邊的數(shù)字表示了如果選擇在這個位置鋪設(shè)光纖的需要花費(fèi)的成本。為了節(jié)約成本，不需要每兩個中心都有線直接聯(lián)系起來?，F(xiàn)在的問題是要確定需要鋪設(shè)哪些線路，使得提供給每兩個中心之間的高速通信的總成本最低。解：（1）首先用Excel軟件對此問題求解。這個案例是從網(wǎng)絡(luò)圖4-45中一個尋找最小生成樹的問題。基本步驟如下：第一步：輸入網(wǎng)絡(luò)圖4-45到Excel工作表中，如下列表4-9所示。表中左上角是一個7×7的對稱權(quán)矩陣。矩陣中“10000”代表距離是無窮大，意味著相應(yīng)兩點(diǎn)間沒有路。第二步：輸入7×7的變量矩陣（可以輸入任意數(shù)）。矩陣中的元素只能取“0”和“1”，“0”代表沒有選中，“1”代表被選中。第三步：輸入約束條件：1）變量矩陣的每行的行和大于等于1；2）變量矩陣的每列的列和等于相應(yīng)的行和（對稱矩陣）。3）總邊數(shù)等于頂點(diǎn)數(shù)減一(此例為6)，這是樹的定義。第四步：輸入目標(biāo)函數(shù)：總成本最低?？偝杀镜扔谶x中路徑的權(quán)重之和，即SUMPRODUCT(A1:G7，A9:G15)/2（見表中B19單元格）。表4-9默登公司最低總成本的Excel計算過程第五步：求解：目標(biāo)函數(shù)：Min（總成本最?。┘s束條件：變量矩陣=bin（變量時0或1）總邊數(shù)=頂點(diǎn)個數(shù)-1=6行和大于等于1行和等于列和應(yīng)用Excel的規(guī)劃求解模塊求解如圖4-46所示：圖4－46第六步：結(jié)果顯示如圖4-47所示：圖4－47從圖4-47顯示，網(wǎng)絡(luò)圖中保留AB、BC、CD、CF、EF、以及EG邊不僅可以使得每兩個中心之間保持通訊，而且高速通信的總成本最低。案例分析2（飛行之旅問題）為了為老人們圓夢，旅行社計劃在5月中下旬舉辦一次“飛行之旅”活動，專為想坐飛機(jī)旅行的中老年人設(shè)計旅行線路。本次活動的旅行地點(diǎn)范圍幾乎覆蓋我國所有省、直轄市和特別行政區(qū)。同時，我們將這些地區(qū)分類，分別為本次活動的個區(qū)域，即子活動“走進(jìn)西部”、“北國風(fēng)光”、“南部之旅”等等，顧客可以選擇參與任意一個子活動。每個省、直轄市和特別行政區(qū)之間都有直達(dá)或者轉(zhuǎn)機(jī)的航班，我們將按照以下原則及流程為其設(shè)計路線：（1）路線的起點(diǎn)為南京，即從南京祿口機(jī)場出發(fā)；（2）由旅行者指定終點(diǎn)。若沒有特別想去的地方，可從我們提供的推薦路線中選擇；（3）我們將根據(jù)旅行的起始點(diǎn)，為其設(shè)計“最短”路線。當(dāng)然，這里的最短路線，并不是指路程最短，它是指在合適時間里價格最優(yōu)問題。分析步驟：（1）模型構(gòu)建：

對于該案例，我們首先將所涉及的城市的機(jī)場及路線放在一個無向圖中，圖中頂點(diǎn)為各個機(jī)場，考慮到老年人不適合長時間的飛行，邊的權(quán)值我們將用以飛行時間和機(jī)票價格為變量的公式來計算。以此建立無向圖為該案例的模型。該模型的約束條件為每個頂點(diǎn)的流入和流出相等（都為1或者都為0），而每個頂點(diǎn)的流入為以該頂點(diǎn)為終點(diǎn)的邊的C值之和，每個頂點(diǎn)的流出為以該頂點(diǎn)為起點(diǎn)的邊的C值之和，以上組成該模型的約束條件。3）目標(biāo)函數(shù)對于該模型，目標(biāo)函數(shù)為，即每條邊的權(quán)值與C值的乘積之和，對其進(jìn)行規(guī)劃求解，即可得到最短路徑。（2）數(shù)據(jù)的收集與整理首先，選取中國各地共38個地區(qū)，即38個機(jī)場作為網(wǎng)絡(luò)圖中38個頂點(diǎn)。其次，我們所收集的數(shù)據(jù)包括航班的票價和時間?？紤]到這是老人的圓夢之旅，我們一般只考慮打折票或特價票。各個城市之間航班我們通過網(wǎng)絡(luò)收集?？紤]到老人的身體狀況，我們要避開黃金周，因此我們找了五月中下旬約一周的機(jī)票價格，取均值。航班飛行時間。依舊是五月中下旬約一周的航班，根據(jù)起降時間計算出飛行時間，取均值。（3）Excel計算1）輸入信息（見表4-10和4-11）這里我們將以“走進(jìn)西部”子活動來作為具體實例。假設(shè)一顧客指定目的地為烏魯木齊。我們將需要求解南京—烏魯木齊的最短路徑。 首先，以南京為起點(diǎn)，烏魯木齊為終點(diǎn)，將我們的網(wǎng)絡(luò)圖輸入到excel表格中。同時將向量歸一化，其中t列表示時間參數(shù)，p列表示價格參數(shù)，通過公式計算出的權(quán)重作為弧的權(quán)值同樣輸入到表格中。留空一列F列代表是否選擇此路徑可以使權(quán)重最小，“1”代表選擇此路徑，而“0”代表不選擇此路徑。細(xì)節(jié)見表4－10和4－11。表4－10網(wǎng)絡(luò)圖輸入信息（一）表4－11網(wǎng)絡(luò)圖輸入信息（二）2）輸入目標(biāo)函數(shù)和約束條件（見圖4－48） 通過F列與權(quán)重值分別相乘再相加后，就可求得我們該選擇的最短路徑，而F列的數(shù)值就代表了為使得路徑最短而需走過的路線。額外列出表格顯示節(jié)點(diǎn)和它的流入流出量。約束條件包含：對于各點(diǎn)流入量和流出量應(yīng)相等；另外，將起點(diǎn)的流入量和終點(diǎn)的流出量設(shè)定為1。圖4－48目標(biāo)函數(shù)和約束條件輸入界面3）結(jié)果顯示（見圖4－49）圖4－49最短路輸出結(jié)果由此我們可以得出，從南京到烏魯木齊的最短路徑為：南京—蘭州—烏魯木齊。該路徑即為老年旅客設(shè)計的路線。該路線在飛機(jī)這項交通工具上機(jī)票約花費(fèi)1351元，時間約花費(fèi)310分鐘。案例分析3（SF公司速運(yùn)物流配送問題）華東地區(qū)是SF公司快遞業(yè)務(wù)量較大，發(fā)展勢頭最為迅猛的區(qū)域。在華東地區(qū)擁有3個一級中轉(zhuǎn)場，分別是上海、杭州和無錫。一級中轉(zhuǎn)場為航空樞紐，年吞吐量共達(dá)到16.7萬噸。另外也設(shè)有25個二級中轉(zhuǎn)場，分別有南京、揚(yáng)州、紹興、舟山等。其年吞吐量為42.4萬噸。其劃分標(biāo)準(zhǔn)主要以行政區(qū)域為主。二級中轉(zhuǎn)場之間共有地面干線運(yùn)輸班次274個?，F(xiàn)有一批緊急物資需要從徐州盡快到達(dá)蘇州，在道路情況一樣的情況下，需要尋求一條最短路徑。解：（1）數(shù)據(jù)收集：從網(wǎng)絡(luò)獲得數(shù)據(jù)如圖4－50所示。路線旁邊數(shù)字指各城市間距離（單位：公里)。圖4－50SF公司速運(yùn)網(wǎng)絡(luò)圖（2）輸入數(shù)據(jù)并建立相應(yīng)模型如圖4－51：圖4－51EXCEL最短路輸入界面（3）輸入約束條件與目標(biāo)函數(shù)并規(guī)劃求解，過程如圖4－52所示。圖4－52EXCEL最短路輸入界面（4）求解獲得最短路徑如圖4－53所示。根據(jù)狀態(tài)變量的變化我們可以得到最短路徑，即徐州→宿遷→淮安→泰州→常州→無錫→蘇州。最短距離為612.1公里。圖4－53最短路輸出結(jié)果案例分析4（城市供水問題）某城市有7個供水加壓站，分別用節(jié)點(diǎn)1，節(jié)點(diǎn)2，……，節(jié)點(diǎn)7表示，見圖4-105。其中節(jié)點(diǎn)l為水廠，各泵站間現(xiàn)有的管網(wǎng)用相應(yīng)節(jié)點(diǎn)間的邊表示?，F(xiàn)規(guī)劃在節(jié)點(diǎn)7處建一個開發(fā)區(qū)，經(jīng)對現(xiàn)有管網(wǎng)調(diào)查，各段管網(wǎng)尚可增加的供水能力(萬噸／日)如圖4-54中各邊上的數(shù)值所示。依照現(xiàn)有管網(wǎng)狀況，從水廠(源點(diǎn))到開發(fā)區(qū)(匯點(diǎn))，每日最多可增加多少供水量?圖4－54城市供水網(wǎng)絡(luò)圖解本題為一個網(wǎng)絡(luò)最大流問題。需在網(wǎng)絡(luò)圖中添加一條從節(jié)點(diǎn)7(匯點(diǎn))至節(jié)點(diǎn)1(源點(diǎn))的“虛”邊(因為實際上并不存在從節(jié)點(diǎn)7流向節(jié)點(diǎn)1的管道，所以稱該邊為“虛”的)，增加這條邊的目的是為了使網(wǎng)絡(luò)中各節(jié)點(diǎn)的邊形成回路，各節(jié)點(diǎn)的流出量與流入量的代數(shù)和(即凈流出量)為零。目標(biāo)函數(shù)是開發(fā)區(qū)(節(jié)點(diǎn)7)的總流人量(或虛擬的總流出量)最大化，這時節(jié)點(diǎn)7的總流人量(或虛擬的總流出量)就是網(wǎng)絡(luò)最大流，即最大供水量。下面用Excel求解此最大流問題。（1）輸入已知數(shù)據(jù)（見圖4－55）圖4－55最大流數(shù)據(jù)輸入界面（2）設(shè)定決策變量本問題的決策變量用C6：I12中的單元格表示就如顯示在圖4－56。它們是從各節(jié)點(diǎn)到其他節(jié)點(diǎn)的流量，也是供水流量增量在網(wǎng)絡(luò)中各條邊上的分配量。例如單元格D6表示從節(jié)點(diǎn)1流入節(jié)點(diǎn)2的流量，也是連接節(jié)點(diǎn)1與節(jié)點(diǎn)2的邊上的流量。圖4－56約束條件（3）目標(biāo)函數(shù)本問題的目標(biāo)函數(shù)是流入節(jié)點(diǎn)7的總流入量最大(即開發(fā)區(qū)得到的供水流量增量最大)，即從節(jié)點(diǎn)7流向節(jié)點(diǎn)1的流出量最大。任選一個單元格輸入目標(biāo)函數(shù)＝C12。（4）約束條件本問題的約束條件有兩個：第一個約束是網(wǎng)絡(luò)中邊的容量約束。容量約束是指各節(jié)點(diǎn)間的邊上的流量不得超過該邊的容量。第二個約束是節(jié)點(diǎn)總流人量與總流出量的平衡約束。圖4－57目標(biāo)函數(shù)與約束條件輸入界面在規(guī)劃求解參數(shù)框中輸入目標(biāo)單元格(目標(biāo)函數(shù)地址)、可變單元格(決策變量地址)和兩個約束條件（見圖4－57），然后在規(guī)劃求解選項參數(shù)框中選擇“采用線性模型”和“假定非負(fù)”如圖4－58，最后求解得到本問題的最優(yōu)解。圖4－58LP模型和決策變量設(shè)定（5）最大流結(jié)果顯示在表4－12。上述結(jié)果也可用圖網(wǎng)絡(luò)圖4－59表示。表4－12最優(yōu)供水量圖4－59最大流結(jié)果顯示圖節(jié)點(diǎn)節(jié)點(diǎn)1（水廠）節(jié)點(diǎn)2節(jié)點(diǎn)3節(jié)點(diǎn)4節(jié)點(diǎn)5節(jié)點(diǎn)6節(jié)點(diǎn)7（開發(fā)區(qū)）節(jié)點(diǎn)1

243

節(jié)點(diǎn)2

2

節(jié)點(diǎn)3

121

節(jié)點(diǎn)4

4

節(jié)點(diǎn)5

6節(jié)點(diǎn)6

3案例分析5（物質(zhì)調(diào)運(yùn)問題）桃曲坡水庫、玉皇閣水庫和高爾塬水庫都位于渭河的支流上，古城西安的上游。這3座水庫尤其是桃曲坡水庫的防洪對西安的安全有著很大的影響，每逢汛期，都有大量的防汛物資從附近倉庫運(yùn)送到這3座水庫(具體倉庫和水庫分布見圖4－60)。3座水庫最低防洪物資需求量為：桃曲坡，230t；高爾塬，190t；玉皇閣，110t。這3座水庫附近有7個倉庫，每個倉庫的物資儲備量和從某座倉庫運(yùn)輸物資到某座水庫的單位物資運(yùn)輸費(fèi)用如表4－13所示。求滿足各水庫最低物資需求量的運(yùn)輸方案。圖4－60水庫位置圖表4－13物資運(yùn)輸單價解

這是一個最小費(fèi)用最大流問題的求解。求解過程是對單一源點(diǎn)到單一匯點(diǎn)進(jìn)行的，防洪物資運(yùn)輸問題涉及到多個儲存物資的倉庫(源點(diǎn))和多個需求物資的水庫(匯點(diǎn))。這就需要引進(jìn)s點(diǎn)作為單源,引進(jìn)t點(diǎn)作為單匯。規(guī)定從s點(diǎn)到第i個倉庫的道路運(yùn)輸能力為第i個倉庫的物資儲備量，從s點(diǎn)運(yùn)送到第i個倉庫的單位物資運(yùn)輸費(fèi)用為0，規(guī)定從第j個水庫到t點(diǎn)的道路運(yùn)輸能力為無窮大，從第j個水庫運(yùn)送到t點(diǎn)的單位物資運(yùn)輸費(fèi)用為0。這樣一來，運(yùn)輸?shù)目傎M(fèi)用不會變，可以應(yīng)用求解最小費(fèi)用最大流問題的算法對問題進(jìn)行求解。倉庫水庫/元

桃曲坡

高爾塬

玉皇閣倉庫物資儲備量/t馬欄20016023090廟曲130160200110柳林5070130105石門關(guān)1307016095青草坪200200250115石柱5012014095（1）輸入已知信息將表4-18中的信息網(wǎng)絡(luò)化，結(jié)點(diǎn)1—7代表7個倉庫，依次為：馬欄、廟灣、瑤曲、柳林、石門關(guān)、青草坪、石柱，結(jié)點(diǎn)8、9、10分別代表水曲坡、高爾塬、玉皇閣（從水庫到t點(diǎn)的道路運(yùn)輸能力為無窮大,用99999表示）。細(xì)節(jié)見圖4－61。圖4－61最小費(fèi)用最大流信息輸入界面（2）設(shè)定決策變量（見圖4－62）圖4－62決策變量設(shè)定界面

（3）目標(biāo)函數(shù)本例中，總費(fèi)用=SUM(Q29:Q35)=54650（元）。（4）添加約束條件及參數(shù)見圖4－63圖4－63目標(biāo)函數(shù)與約束條件輸入界面（5）求解獲得最優(yōu)解見圖4－64。滿足各水庫最低物資需求量的運(yùn)輸方案被總結(jié)在表4-19中。圖4－64最小費(fèi)用最大流結(jié)果輸出界面

表4－14最優(yōu)運(yùn)輸方案倉庫水庫/元流出量桃曲坡高爾塬玉皇閣馬欄0153090廟灣080080瑤曲30080110柳林10500105石門關(guān)095095青草坪000115石柱950095流入量230190110案例分析6（網(wǎng)絡(luò)優(yōu)化問題）空中空客總裝有限公司裝配飛機(jī)垂尾的生產(chǎn)計劃如圖4－65所示?，F(xiàn)要求編制該工程的網(wǎng)絡(luò)計劃。（1）不發(fā)生意外時施工，能在多少天內(nèi)竣工？給出這時的費(fèi)用。2010年3月2號，海南航空公司現(xiàn)要求其在7月1號前完成（即90天），每天的間接費(fèi)用為800元。為滿足要求總裝廠需費(fèi)用多少？（2）若不計成本，該工程最快能多少天完成？（3）完成該裝配最優(yōu)費(fèi)用需要多少時間？圖4－65飛機(jī)垂尾裝配的費(fèi)用和時間參數(shù)解（1）求解90天完工的費(fèi)用基本步驟如下：1）建立模型并畫出工序流程圖（如圖4－66所示）圖4－66網(wǎng)絡(luò)圖2）計算正常工期下的時間與直接費(fèi)用（如圖4－67所示）2）計算正常工期下的時間與直接費(fèi)用（如圖4－67所示）圖4－67正常工期下的時間和費(fèi)用正常完工時間為103天，獲得總費(fèi)用為：總費(fèi)用=直接費(fèi)用+間接費(fèi)用3）計算90天完工的直接費(fèi)用見圖4－68?？傎M(fèi)用為：總費(fèi)用=直接費(fèi)用+間接費(fèi)用，即138350+800*90=210350.圖4－68趕工條件下的時間和費(fèi)用（2）計算極限工期（使用最短工期的時間作為工序時間），獲得最快完工時間為71天。如圖4－69所示?？傎M(fèi)用為=直接費(fèi)用+間接作用=157600+800*71=214400。圖4－69最快趕工時間以及費(fèi)用（3）最優(yōu)費(fèi)用下的工期1)計算最優(yōu)工期：輸入最短工期和正常工期間時間，及各種情況下的費(fèi)用結(jié)果如圖4－70所示。圖4－70最優(yōu)趕工時間以及費(fèi)用2）計算最優(yōu)費(fèi)用下的工期。輸入最優(yōu)工期，獲得最優(yōu)費(fèi)用下的工期為82天。直接費(fèi)用為143750（見圖4－71）。直接費(fèi)用+間接費(fèi)用=總費(fèi)用，即。圖4－71最優(yōu)趕工時間以及最優(yōu)費(fèi)用（4）結(jié)果比較見表4-15表4－15不同工期下費(fèi)用比較由上表可知，選擇最優(yōu)工期可以節(jié)約3770元 。

正常工期（103）

限定工期（90）

極限工期（71）

最優(yōu)工期（82）直接費(fèi)

130720138350157600143750間接費(fèi)

82400720005680065600總費(fèi)用

213120210250214400209350案例討論1（物資配送問題）（物流最大流問題）兩家工廠x1和x2生產(chǎn)同一種商品。商品通過圖4－72的網(wǎng)絡(luò)送到市場y1,y2,y3（路線旁邊數(shù)字指運(yùn)輸物流最大流量）。求從工廠到市場所能運(yùn)送的最大數(shù)量。

圖4－72物資配送網(wǎng)絡(luò)圖案例討論2（網(wǎng)絡(luò)計劃問題）某航空有限公司裝配車間的生產(chǎn)計劃如下表所示?，F(xiàn)要求編制該工程的網(wǎng)絡(luò)計劃。（1）不發(fā)生意外時施工，能在多少天內(nèi)竣工？給出這時的費(fèi)用。（2）若不計成本，該工程最快能多少天完成以及相應(yīng)費(fèi)用？（3）完成該裝配最優(yōu)費(fèi)用需要多少時間？表4-16裝配車間時間和費(fèi)用表項

目代

號活動名稱緊前活動正常時間極限時間正常費(fèi)用極限費(fèi)用費(fèi)用變化率資源消耗1虛活動

0000

02御間緣肋組件裝配16635003500

73前梁裝配1422600440090054后梁裝配1422600440090055后腹板裝配1543000395095066前梁壓鉚32210001000

47梁間肋裝配33311001100

68后梁壓鉚42210001000

49鉸鏈肋裝配465400050001000610裝配上壁板54220003800900511裝配下壁板54220003800900512翼梁裝配58849004900

413后梁總裝配8,91187500114001300814鉚接上下壁板322900900

315噴漆13217001100400216垂尾總裝6,7,158655007000750417安裝尾部型材144320002700700618安裝前肋175330004000500519架外加工2,166425003400450320虛活動190000

0案例討論3（NJ風(fēng)景區(qū)游覽問題）鐘山風(fēng)景區(qū)是NJ著名的風(fēng)景游覽勝地，首批國家5A級旅游景區(qū)，中國旅游勝地四十佳，全區(qū)包括14個可供觀光游覽的景點(diǎn)，分為明孝陵景區(qū)、中山陵景區(qū)、靈谷景區(qū)、頭陀嶺景區(qū)和其他景點(diǎn)五大部分。雄偉的風(fēng)景和濃厚的人文底蘊(yùn)每年吸引大量游客游覽。但是，由于景區(qū)可供觀光游覽的景點(diǎn)眾多，景區(qū)游覽線路復(fù)雜，