運(yùn)籌學(xué)（第2版）課件 第3-5章 整數(shù)規(guī)劃；圖論與網(wǎng)絡(luò)計(jì)劃；存儲(chǔ)論

南京航空航天大學(xué)經(jīng)濟(jì)與管理學(xué)院運(yùn)籌學(xué)第三章整數(shù)規(guī)劃

目前世界上大多航空公司的機(jī)隊(duì)都具有多種機(jī)型，不同機(jī)型有著不同的設(shè)計(jì)特點(diǎn)，如座位數(shù)、著陸重量、機(jī)組、飛機(jī)維護(hù)和燃油消耗等等。針對(duì)不同的運(yùn)營航線，每種機(jī)型的運(yùn)營成本也都有所不同，如何安排不同機(jī)型承擔(dān)運(yùn)輸任務(wù)是航空公司生產(chǎn)運(yùn)營過程中一項(xiàng)非常重要的工作。

對(duì)于機(jī)型的分配是一般是通過對(duì)已經(jīng)開航或擬開辟的各航線進(jìn)行客流量預(yù)測，并通過對(duì)機(jī)隊(duì)中各種機(jī)型在不同航線和航班上的運(yùn)營成本進(jìn)行對(duì)比分析，最終的目標(biāo)是為各個(gè)航班匹配合理的機(jī)型。機(jī)型分配的結(jié)果直接影響到航空公司的運(yùn)營成本和飛行安全問題，對(duì)航空公司的正常運(yùn)作和整體效益有著決定性影響。

機(jī)型分配問題主要通過考慮飛機(jī)飛行時(shí)間、旅客數(shù)量、兩地航班次數(shù)等約束條件，建立總成本最小的目標(biāo)函數(shù)，從而得到最優(yōu)的機(jī)型配置方案。在這類問題中，最優(yōu)解是各種類型飛機(jī)班次，所以是一定是整數(shù)。因此航空公司大多采用基于整數(shù)規(guī)劃算法的航班計(jì)劃編制管理系統(tǒng)解決機(jī)型分配問題，該系統(tǒng)能為航空公司提高飛機(jī)利用率、節(jié)省航班計(jì)劃編制時(shí)間，從而提高航空公司整體的經(jīng)濟(jì)效益。

第三章整數(shù)規(guī)劃

從上述情況可以看出，航空公司機(jī)型分配與前面介紹的線性規(guī)劃問題最大的不同在于最優(yōu)解必須是整數(shù)。因此，人們將決策變量必須取整數(shù)的線性規(guī)劃問題稱為整數(shù)線性規(guī)劃問題。在整數(shù)線性規(guī)劃問題中，如果所有決策變量都是整數(shù)，則稱為純整數(shù)規(guī)劃；如果一部分決策變量是整數(shù)，一部分是非整數(shù)，則稱為混合整數(shù)規(guī)劃；而變量取值只能是0或1的問題稱為0-1整數(shù)規(guī)劃。這些分類主要是根據(jù)決策變量的整數(shù)要求和限制來進(jìn)行區(qū)分的。3.1.1整數(shù)規(guī)劃的求解例3.1某廠擬用集裝箱托運(yùn)甲、乙兩種貨物，兩種貨物的體積、質(zhì)量、單件利潤以及集裝箱托運(yùn)限制情況如表3.1所示。問兩種貨物各托運(yùn)多少箱，可使獲得的利潤為最大？表3.1兩種貨物的體積、質(zhì)量、單件利潤以及集裝箱托運(yùn)限制情況解：設(shè)分別為甲、乙兩種貨物的托運(yùn)箱數(shù)，則數(shù)學(xué)模型可以表示為：其中，目標(biāo)函數(shù)代表追求最大利潤，約束條件是對(duì)集裝箱的體積和質(zhì)量限制，決策變量要求集裝箱數(shù)量必須是整數(shù)。3.1.2分支定界算法當(dāng)涉及整數(shù)規(guī)劃問題的求解時(shí)，可以使用單純形算法來求得非整數(shù)約束下的最優(yōu)解，然后通過四舍五入或取整法來獲得最優(yōu)整數(shù)解。然而，這種方法有時(shí)并不能保證得到整數(shù)規(guī)劃的最優(yōu)解。

為更好地理解，以例3.1的求解為例，先不考慮x1,x2為整數(shù)的條件，采用單純形法求解該問題，得到：x1=4.8,x2=0,z=96。若對(duì)x1,x2

采用四舍五入法求解，則有x1=5,x2=0,顯然，此解不是可行解；如果采用取整法，x1=4,x2=0。此時(shí)，目標(biāo)函數(shù)z=80,這個(gè)解也不是最優(yōu)解。由此表明，四舍五入或者取整法得到的解并不是整數(shù)規(guī)劃的最優(yōu)解。

對(duì)于整數(shù)規(guī)劃問題，如果可行域是有界的，那么整數(shù)解的數(shù)量應(yīng)該是有限的。在這種情況下，可以使用枚舉法計(jì)算所有可行整數(shù)解，并比較它們對(duì)應(yīng)的目標(biāo)函數(shù)值，從中選擇最優(yōu)解。當(dāng)決策變量較少且取值范圍不大時(shí)，枚舉法是可行且有效的。然而，對(duì)于具有大量決策變量的整數(shù)規(guī)劃問題，當(dāng)決策變量很多且取值范圍較大時(shí)，采用枚舉法將導(dǎo)致指數(shù)級(jí)增長的計(jì)算量，并不可行。目前，解決整數(shù)規(guī)劃問題的兩種常用方法是分支定界算法和割平面法。分支定界算法是在20世紀(jì)60年代提出的一種靈活且適合計(jì)算機(jī)求解的方法。下面將通過例子說明分支定界算法的思想和步驟。例3.2求解對(duì)如下整數(shù)規(guī)劃：解：先不考慮整數(shù)條件，解相應(yīng)的線性規(guī)劃，得最優(yōu)解：

該解不符合整數(shù)條件。對(duì)其中一個(gè)非整數(shù)變量解，如

，顯然

，若要滿足整數(shù)條件

必定有

于是，對(duì)原問題增加兩個(gè)新約束條件，將原問題分為兩個(gè)子問題，即有（LP1）

和（LP2）

問題（LP1）和（LP2）的可行域中包含了原整數(shù)規(guī)劃問題的所有整數(shù)可行解，而在

中不可能存在整數(shù)可行解的區(qū)域已被切除。分別求解這兩個(gè)線性規(guī)劃問題，得到的解是：

和

。

變量

仍然不滿足整數(shù)的條件，對(duì)問題（LP1），必有

，將（LP1）增加約束條件，得到：（LP12）（LP11）求解（LP11），得到

；求解（LP12），得到

。由于（LP12）的最優(yōu)值小于（LP11）的最優(yōu)值，故，原問題的最優(yōu)值必大于340，盡管（LP12）的解仍然不滿足整數(shù)條件，（LP12）已無必要繼續(xù)分解。對(duì)（LP2），

不滿足整數(shù)條件，必有

，將這兩個(gè)約束條件分別加到（LP2）中，得到（LP21）和（LP22），求解得到：（LP21）的最優(yōu)解為

，（LP22）無可行解。至此，原問題的最優(yōu)解為

。上述求解過程稱為分支定界算法，求解過程用圖3.1表示：

圖3.1例3.2求解過程

將要求解的整數(shù)規(guī)劃問題稱為問題A，將與之相應(yīng)的線性規(guī)劃問題稱為問題B（與問題A相比較，僅不含有變量為整數(shù)的約束條件），問題B稱為原問題A的松弛問題。解問題B，可能得到以下情況之一：B沒有可行解，這時(shí)

A也沒有可行解，則停止。B有最優(yōu)解，并符合問題A的整數(shù)條件，B的最優(yōu)解即為A的最優(yōu)解，則停止。B有最優(yōu)解，并不符合問題A的整數(shù)條件，記它的目標(biāo)函數(shù)值為

。用觀察法找問題A的一個(gè)整數(shù)可行解，一般可取

試探，求得其目標(biāo)函數(shù)值，并記為。以

表示問題A的最優(yōu)目標(biāo)函數(shù)值；這時(shí)

，然后按下述步驟進(jìn)行迭代。分支過程。在

B的最優(yōu)解中任選一個(gè)不符合整數(shù)條件的變量

，若其值為

，以

表示小于

的最大整數(shù)，構(gòu)造兩個(gè)約束條件：

。將這兩個(gè)約束條件，分別加入問題

B，得到后續(xù)規(guī)劃問題

。不考慮整數(shù)條件求解這兩個(gè)后續(xù)問題。定界過程。以每個(gè)后續(xù)問題為一分支，并標(biāo)明求解的結(jié)果，在其他問題解的結(jié)果中，找出最優(yōu)目標(biāo)函數(shù)值最大者作為新的上界

。從已符合整數(shù)條件的各分支中，找出目標(biāo)函數(shù)值最大者作為新的下界

，若無可行解，則

。步驟1：分支界定過程步驟2：比較與剪支。各分支的最優(yōu)目標(biāo)函數(shù)中若有小于

者，則剪掉這支，以后不再考慮這個(gè)分支。若大于

，且不符合整數(shù)條件，則重復(fù)步驟1，直到最后得到

為止，得到最優(yōu)整數(shù)解3.1.3一般整數(shù)規(guī)劃的Excel求解

下面以例3.1為例，介紹如何使用Excel求解整數(shù)規(guī)劃問題。例3.1是一個(gè)集裝箱托運(yùn)貨物問題，最終目標(biāo)是確定貨物甲和貨物乙各需要裝載多少個(gè)集裝箱，以實(shí)現(xiàn)最大利潤，而且同時(shí)滿足集裝箱的托運(yùn)限制條件?；A(chǔ)數(shù)據(jù)的輸入如圖3.2所示，這是一個(gè)整數(shù)規(guī)劃問題。圖3.2裝箱問題電子表格

使用Excel計(jì)算例3.1的步驟與上述線性規(guī)劃求解類似。需要注意的是貨物甲和貨物乙的箱數(shù)必須指明是整數(shù)。如圖3.3所示，在“添加約束”對(duì)話框中指明在“B7”位置上的第一個(gè)變量被限制為整數(shù)“int”。所有約束條件被添加完成后，整個(gè)參數(shù)設(shè)置的結(jié)果顯示在圖3.4中。圖3.3整數(shù)約束對(duì)話框圖3.4整數(shù)規(guī)劃求解參數(shù)設(shè)置

在點(diǎn)擊“求解”按鈕后，得到整數(shù)規(guī)劃最優(yōu)解如圖3.5所示。在可變單元格部分，“初值”欄顯示的是任意輸入的初始變量數(shù)值?！敖K值”欄顯示的是最終的最優(yōu)整數(shù)解，當(dāng)貨物甲裝4箱和貨物乙裝1箱時(shí)可獲得最大利潤9000元。圖3.5裝箱問題的整數(shù)最優(yōu)解3.20-1規(guī)劃例3.1中的整數(shù)規(guī)劃問題，決策變量是甲、乙兩種貨物的箱數(shù)，對(duì)于不同的整數(shù)規(guī)劃問題，決策變量也可能是人數(shù)、機(jī)器臺(tái)數(shù)等作為決策變量。在實(shí)際建模過程中，還會(huì)經(jīng)常遇到要求模型解決“是、否”或者“有、無”等問題，這類問題一般可以借助引入數(shù)值為0或者1的決策變量加以解決，下面舉例說明。例3.3

某公司擬在市東、西、南三區(qū)建立門市部，有7個(gè)位置

（

）可供選擇，考慮到各地區(qū)居民消費(fèi)水平及居民居住密集度，公司制定了如下規(guī)定：在東區(qū)，由

三個(gè)點(diǎn)中至多選兩個(gè)；在西區(qū)，由

兩個(gè)點(diǎn)中至少選一個(gè)；在南區(qū)，由

兩個(gè)點(diǎn)中至少選一個(gè)。

如選用

點(diǎn)，設(shè)備投資預(yù)計(jì)為

元，每年可獲利潤預(yù)計(jì)為

元，由于公司的投資能力及投資策略限制，要求投資總額不能超過B元。問應(yīng)如何選擇可使年利潤為最大？解：設(shè)

表示是否在位置i建立門市部，有

則可以建立如下的數(shù)學(xué)模型：

其中，目標(biāo)函數(shù)表示尋求獲利最大的設(shè)點(diǎn)方案，第一個(gè)約束條件表示投資總額限制，之后的三個(gè)約束條件分別表示在東、西和南區(qū)的設(shè)點(diǎn)數(shù)限制，決策變量取值0或1。3.2.2背包問題例3.4某科學(xué)實(shí)驗(yàn)衛(wèi)星擬從下列儀器裝置中選若干件裝上。已知儀器裝置

(i=1,2,…,7)的體積為

，重量為

，該裝置在實(shí)驗(yàn)中的價(jià)值為

。要求：①裝入衛(wèi)星的儀器裝置總體積不超過V，總重量不超過

W；②A1與A3中最多安裝一件；③A2與A4中至少安裝一件；④A5與A6或者都安裝上，或者都不安裝。

總的目的是裝上去的儀器裝置使該科學(xué)實(shí)驗(yàn)衛(wèi)星發(fā)揮最大的實(shí)驗(yàn)價(jià)值。試建立這個(gè)問題的數(shù)學(xué)模型。解：設(shè)

（i=1，2，…，7）表示是否裝載該儀器設(shè)備，有

。則可以建立如下的數(shù)學(xué)模型：

其中，目標(biāo)函數(shù)表示追求最大的衛(wèi)星實(shí)驗(yàn)價(jià)值；第1,2個(gè)約束條件表示體積和重量的限制；第3-5個(gè)約束條件表示特定的衛(wèi)星裝載要求,該問題的決策變量是0-1整數(shù)變量。3.2.3隱枚舉法

從上面兩個(gè)例子可以看出，此類型問題是整數(shù)規(guī)劃中的特殊情形，其中決策變量

的取值只能為0或1，此時(shí)變量

稱為0-1變量，這類問題被稱為0-1整數(shù)規(guī)劃。對(duì)于

的取值的0-1約束，可以轉(zhuǎn)化成下述整數(shù)約束條件：

這樣就把0-1規(guī)劃問題轉(zhuǎn)變成一般整數(shù)規(guī)劃問題了，利用解決一般整數(shù)規(guī)劃問題的通用方法，如分支定界法、割平面法，就可以對(duì)該問題求解。

除此之外，解0-1規(guī)劃問題的方法最直接的是枚舉法，即考慮變量取值0或1的每一種組合情況。雖然和一般的整數(shù)規(guī)劃問題相比，變量的取值范圍大大縮小，但是對(duì)變量個(gè)數(shù)n比較大的情況，仍需要進(jìn)行大量的計(jì)算，計(jì)算工作也是很難完成的。

因此可以設(shè)計(jì)一些方法，只需要檢查變量組合中的一部分就可以找到最優(yōu)解，隱枚舉法就是一種這樣的方法。

下面舉例說明求解0-1整數(shù)規(guī)劃的隱枚舉法。例3.5有0-1整數(shù)規(guī)劃問題：解：采用試探的方法找到一個(gè)可行解，容易看出

符合約束條件，目標(biāo)函數(shù)值

。

對(duì)于極大化問題，應(yīng)有

，于是增加一個(gè)約束條件：（5）

新增加的約束條件稱為過濾條件。原問題的線性約束條件就變成5個(gè)，3個(gè)變量共有23=8個(gè)解，原來4個(gè)約束條件共需32次運(yùn)算，增加了過濾條件后，將5個(gè)約束條件按(3.1)～(3.5)的順序排好(見表3.2)，對(duì)每個(gè)解，依次代入約束條件左側(cè)，求出數(shù)值，看是否滿足不等式條件，如某一條件不適合，同行以下條件就不必再檢查，這樣可以減少運(yùn)算次數(shù)。于是求得最優(yōu)解，maxZ=8。在計(jì)算過程中，若遇到z值已超過條件（5）右邊的值，應(yīng)改變條件（5），使右邊為迄今為止的最大z，繼續(xù)檢查。例如，當(dāng)檢查點(diǎn)（0，0，1）時(shí)因

Z=5＞3，所以應(yīng)將條件（5）換成表3.2（6）3.2.30-1規(guī)劃的Excel求解

以例3.5為例介紹如何使用Excel求解0-1整數(shù)規(guī)劃求解問題。把基礎(chǔ)數(shù)據(jù)輸入到Excel電子表格中，如圖3.6所示。圖3.6矩陣形式電子表格模型

用Excel進(jìn)行0-1整數(shù)規(guī)劃求解的步驟與一般的整數(shù)規(guī)劃求解類似。不同點(diǎn)是需要指明所有變量是0-1決策變量。例如說明在“B8”位置上的第一個(gè)變量是0-1形式的變量，在選擇按鈕處選擇“bin”就意味著第一個(gè)變量被限制為“0-1”決策變量，如圖3.7所示。

在所有參數(shù)被設(shè)置完后點(diǎn)擊“求解”，最優(yōu)解報(bào)告會(huì)顯示出來。在可變單元格部分，“初值”欄顯示的是任意輸入的初始變量數(shù)值(x1,x2,x3)=(1,0,0)?！敖K值”欄顯示的是最終的最優(yōu)0-1整數(shù)解(x1,x2,x3)=(1,0,1)，最大值被顯示在目標(biāo)單元格部分為8。圖3.7二進(jìn)制形式的約束3.3指派問題3.3.1指派問題模型

在生活中經(jīng)常會(huì)遇到這樣的問題：某單位需完成n項(xiàng)任務(wù)，恰好有n個(gè)人可承擔(dān)這些任務(wù)。由于每人的專長不同，各人完成任務(wù)所需的時(shí)間也不同。問題是，應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成n項(xiàng)任務(wù)的總體所需總時(shí)間最?。窟@類問題稱為指派問題或分配問題（AssignmentProblem）。例3.6

有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作E、J、G、R?，F(xiàn)有甲乙丙丁四人。他們將中文說明書翻譯成不同語種說明書所需時(shí)間如表3.3所示。問，若要求每一翻譯任務(wù)只分配給一人去完成，每一個(gè)人只接受一項(xiàng)任務(wù)，應(yīng)指派何人去完成何工作，使所需時(shí)間最少？表3.3例3.6的效率矩陣表

一般地，稱表3.3為效率矩陣或者系數(shù)矩陣，其元素

表示指派第

i個(gè)人去完成第

j項(xiàng)任務(wù)所需的時(shí)間，或者稱為完成任務(wù)的工作效率（或時(shí)間、成本等）。解：引入0-1變量由此可得到指派問題的數(shù)學(xué)模型：

目標(biāo)函數(shù)表示

n個(gè)人完成任務(wù)所需的時(shí)間最少（或效率最高）；第一個(gè)約束條件說明第

j項(xiàng)任務(wù)只能由1人去完成；第二個(gè)約束條件說明第

i人只能完成1項(xiàng)任務(wù)?？傻?，上述問題可行解可寫成表格或矩陣形式，如例3.6的一個(gè)可行解矩陣是可以看出，解矩陣中各行(各列)只能有一個(gè)元素是1?；仡欉\(yùn)輸問題的數(shù)學(xué)模型，當(dāng)生產(chǎn)量和銷售量分別等于1時(shí)，實(shí)際上所得到的數(shù)學(xué)模型與指派問題完全相同，即指派問題是運(yùn)輸問題的特例，因此可以使用運(yùn)輸問題的表上作業(yè)法來解決指派問題。下面根據(jù)指派問題的特點(diǎn)介紹一種更為簡便的算法。3.3.2匈牙利法

指派問題的最優(yōu)解有這樣的性質(zhì)，若從系數(shù)矩陣

的某一行（列）各元素中分別減去該行（列）的最小元素，得到新矩陣

，那么以

為系數(shù)矩陣求得的最優(yōu)解和用原系數(shù)矩陣求得的最優(yōu)解相同。

以例3.6來理解上述性質(zhì)，對(duì)甲來說，只能完成一項(xiàng)任務(wù)，若其無論完成哪項(xiàng)任務(wù)都減少相同的時(shí)間，這種時(shí)間變動(dòng)并不改變甲在四項(xiàng)任務(wù)中的最佳選擇；若完成某項(xiàng)任務(wù)的四個(gè)人都減少相同的時(shí)間，同樣，這種時(shí)間的節(jié)省并不改變?nèi)蝿?wù)對(duì)完成人的最佳選擇。

3.3.2匈牙利法

利用這個(gè)性質(zhì)，可使原系數(shù)矩陣變換為含有很多0元素的新系數(shù)矩陣，而最優(yōu)解保持不變。在系數(shù)矩陣中，一般稱位于不同行不同列的0元素為獨(dú)立0元素。若能在系數(shù)矩陣中找出n個(gè)獨(dú)立的0元素，令解矩陣中對(duì)應(yīng)著n個(gè)獨(dú)立0元素的元素取值為1，其他元素取值為0，則代入目標(biāo)函數(shù)中得到目標(biāo)函數(shù)等于0，那么這個(gè)解一定是最優(yōu)解。1955年庫恩（W.W.Kuhn）利用匈牙利數(shù)學(xué)家康尼格（D.Konig）一個(gè)關(guān)于矩陣中0元素的定理，提出了指派問題的解法，稱為匈牙利法。該定理證明了以下結(jié)論：

系數(shù)矩陣中，獨(dú)立元素0元素的最大個(gè)數(shù)等于能覆蓋所有0元素的最小直線數(shù)。下面用例3.6來說明該方法的應(yīng)用步驟。第一步：使指派問題的系數(shù)矩陣經(jīng)變換，在各行各列中都出現(xiàn)0元素。（1）從系數(shù)矩陣的每行元素減去該行的最小元素；（2）再從所得系數(shù)矩陣的每列元素中減去該列的最小元素。例3.6的計(jì)算結(jié)果為：第二步：進(jìn)行試指派，以尋求最優(yōu)解。

經(jīng)第一步變換后，系數(shù)矩陣中每行每列都已有了0元素；但需找出n個(gè)獨(dú)立的0元素。若能找出，就以這些獨(dú)立0元素對(duì)應(yīng)解矩陣中的元素為1，其余為0，這就得到最優(yōu)解。

當(dāng)n較小時(shí)，可用觀察法、試探法去找出n個(gè)獨(dú)立0元素。若n較大時(shí)，就必須按一定的步驟去找，常用的步驟為：①從只有一個(gè)0元素的行（列）開始，給這個(gè)0元素加圈，記作◎。這表示對(duì)這行所代表的人，只有一種任務(wù)可指派。然后劃去◎所在列（行）的其他0元素，記作

。這表示這列所代表的任務(wù)已指派完，不必再考慮別人。②反復(fù)進(jìn)行步驟（1），直到所有0元素都被圈出或劃掉為止。③若仍有沒有畫圈的0元素，且同行（列）的0元素至少有兩個(gè)（表示對(duì)這個(gè)可以從兩項(xiàng)任務(wù)中指派其一）。則從剩有0元素最少的行（列）開始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個(gè)0元素加圈（表示選擇性多的要“禮讓”選擇性少的）。然后劃掉同行同列的其他0元素?？煞磸?fù)進(jìn)行，直到所有0元素都已圈出或劃掉為止。④若◎元素的數(shù)目m等于矩陣的階數(shù)n，那么指派問題的最優(yōu)解已得到。若m＜n，則轉(zhuǎn)入后面的第三步。對(duì)于例3.6，按步驟（1），先給b22加圈，然后給b31加圈，劃掉b11,b41；按步驟（2），給b43加圈，劃掉b44,最后給b14加圈，得到由于m=n=4，所以得最優(yōu)解為這表示：指定甲譯出俄文，乙譯出日文，丙譯出英文，丁譯出德文，所需總時(shí)間最少例3.7求表3.7所示效率矩陣的指派問題的最小解。解：按上述第一步，將這系數(shù)矩陣進(jìn)行變換。表3.7例3.7的效率矩陣按第二步，得到：這里◎的個(gè)數(shù)m=4，而

n=5；解題沒有完成，應(yīng)按以下步驟繼續(xù)進(jìn)行。第三步：作最少的直線覆蓋所有0元素，以確定該系數(shù)矩陣中能找到最多的獨(dú)立元素?cái)?shù)。為此按以下步驟進(jìn)行：對(duì)沒有◎的行打√號(hào)；對(duì)已打√號(hào)的行中所有含

元素的列打√號(hào)；再對(duì)打有√號(hào)的列中含◎元素的行打√號(hào)；重復(fù)（2），（3）直到得不出新的打√號(hào)的行、列為止；對(duì)沒有打√號(hào)的行畫一橫線，已打√號(hào)的列畫一縱線，這就得到覆蓋所有0元素的最少直線數(shù)。令這直線數(shù)為l。若l<n，說明必須再變換當(dāng)前的系數(shù)矩陣，才能找到n個(gè)獨(dú)立的0元素，為此轉(zhuǎn)第四步：若l=n，而m<n，應(yīng)回到第二步（4），另行試探。

在例3.7中，對(duì)矩陣按以下次序進(jìn)行：

先在第五行旁打√號(hào)，接著在第一列打√號(hào)，接著在第三列旁打√號(hào)。經(jīng)檢查不能再打√號(hào)了。對(duì)沒有打√行，畫一直線以覆蓋0元素，已打√的列畫一直線以覆蓋0元素。得

√√√由此可見。所以應(yīng)繼續(xù)對(duì)矩陣進(jìn)行變換，轉(zhuǎn)第四步。第四步：該步進(jìn)行矩陣變換的目的是增加0元素。在沒有被直線覆蓋的部分中找出最小元素。然后在打√行各元素中都減去這最小元素，而在打√列的各元素都加上這最小元素，以保證原來0元素不變。若得到n個(gè)獨(dú)立的0元素，則已得最優(yōu)解，否則回到第三步重復(fù)進(jìn)行。在沒有被覆蓋部分（第3、5行）中找出最小元素為2，然后在第3、5行各元素分別減2，給第一列各元素加2，得到新矩陣。按第二步，找出所有獨(dú)立的0元素，得到：它具有5個(gè)獨(dú)立的0元素。這就得到了最優(yōu)解，相應(yīng)的解矩陣為由解矩陣得最優(yōu)指派方案：甲—B，乙—D，丙—E，丁—C，戊—A。本例還可以得到另一最優(yōu)指派方案：甲—B，乙—C，丙—E，丁—D，戊—A。所需總時(shí)間為minz=32。

當(dāng)指派問題的系數(shù)矩陣，經(jīng)過變換得到了同行和同列中都有兩個(gè)或兩個(gè)以上0元素時(shí)，這時(shí)可以任選一行（列）中某一個(gè)0元素，再劃去同行（列）的其他0元素。這時(shí)會(huì)出現(xiàn)多重解。

下面討論幾種特殊的情況，經(jīng)過適當(dāng)變換后，即可以采用匈牙利法求解。（1）目標(biāo)函數(shù)求極大化的問題。對(duì)例3.6，若系數(shù)矩陣中各元素

為翻譯人員從事某種語言翻譯工作后所得到的收益，要求一種指派，使翻譯人員的收益最大，即求

，可令

，其中M是足夠大的常數(shù)（如可選

中最大元素為M），這時(shí)系數(shù)矩陣可變換為

，這時(shí)

，符合匈牙利法的條件。

目標(biāo)函數(shù)經(jīng)變換后，即解

，所得最小解就是原問題最大解，因?yàn)椋?/p>

因?yàn)閚M為常數(shù)，所以取最小時(shí)，即為最大。（2）任務(wù)數(shù)m與工作人員數(shù)n不等

當(dāng)m>n時(shí)，可設(shè)“虛工作人員”，虛工作人員從事各項(xiàng)任務(wù)的效率為0，分配給虛擬人的工作實(shí)際上無法安排；當(dāng)m<n時(shí)，可設(shè)“虛工作”，各工作人員從事虛工作的效率為0，被指派做虛擬工作的人的狀態(tài)，實(shí)際是休息狀態(tài)。此時(shí)，即可將問題得到轉(zhuǎn)化。若例3.6中，只有甲乙丙三個(gè)工作人員，則轉(zhuǎn)化的矩陣為表3.5；若原四個(gè)工作人員只需要完成EJG三項(xiàng)工作，則轉(zhuǎn)化的矩陣為表3.6表3.5轉(zhuǎn)化矩陣表(一)表3.6轉(zhuǎn)化矩陣表(二)人員任務(wù)EJGR甲215134乙1041415丙9141613虛工作人員0000人員任務(wù)EJG虛工作甲215130乙104140丙914160丁78110（3）不平衡指派問題的擴(kuò)展

三個(gè)工人從事四項(xiàng)工作，某一工人從事二項(xiàng)工作，求花費(fèi)時(shí)間最小的指派。先不考慮“某一工人從事二項(xiàng)工作”，則增加虛擬工作人員，得到最優(yōu)指派后，剩余工作必定由三人中完成該項(xiàng)任務(wù)花費(fèi)時(shí)間最少的來從事。與（2）不同的是，該虛工作人員完成任務(wù)的時(shí)間花費(fèi)等于各項(xiàng)任務(wù)中三人的最少花費(fèi)時(shí)間，該問題即得到表3.7。用匈牙利法求解該問題，若虛工作人員從事G工作，表明第四項(xiàng)工作由甲完成；若虛工作人員從事J工作，表明第四項(xiàng)工作由乙完成。表3.7不平衡指派問題擴(kuò)展表人員任務(wù)EJGR甲215134乙1041415丙9141613“虛工作人員”24134在不平衡指派問題中，在工人數(shù)大于工作數(shù)情況下，增加虛工作：某人必須被指派工作。則該人從事虛工作的時(shí)間花費(fèi)為“M”，表示工作花費(fèi)時(shí)間無窮大，其余人從事該虛工作的時(shí)間花費(fèi)為0。工人不能得到指派時(shí)存在一定賠償損失費(fèi)，將各人得到的賠償費(fèi)作為從事該虛工作的時(shí)間花費(fèi)。當(dāng)工作數(shù)大于工人數(shù)時(shí)，則增加虛工作人員：若某項(xiàng)工作必須完成，則該虛工作人員從事必須完成工作的時(shí)間花費(fèi)為“M”，表示該項(xiàng)工作不得由虛工作人員從事，虛工作人員從事其它工作的時(shí)間花費(fèi)為0；若工作不能完成時(shí)存在懲罰損失費(fèi)時(shí)，則直接將懲罰費(fèi)作為虛工作人員從事各項(xiàng)工作的時(shí)間；若某人不能完成某項(xiàng)工作，則在系數(shù)矩陣中，相應(yīng)位置處填入“M”。3.3.4指派問題的Excel求解

首先將例3.6中各人完成不同任務(wù)的基礎(chǔ)數(shù)據(jù)輸入Excel電子表格中，如圖3.8所示.圖3.8指派問題電子表格

在“規(guī)劃求解參數(shù)”對(duì)話框中的參數(shù)設(shè)置如圖3.9所示。

按照?qǐng)D3.9設(shè)置完參數(shù)后，點(diǎn)擊“求解”，則可以得到指派問題的最優(yōu)解，如圖3.10所示。

根據(jù)圖3.10可以看出可變單元格E11、C12、B13和D14的“終值”為1，其余全為0，由此可知任務(wù)分配的結(jié)果是指派甲從事任務(wù)R，乙從事任務(wù)J，丙從事任務(wù)E，丁從事任務(wù)G。目標(biāo)單元格最小值為28。圖3.9指派問題求解參數(shù)設(shè)置圖3.10指派問題的最優(yōu)解3.4案例分析案例分析1（分銷中心選址問題）A公司在D1處經(jīng)營一家年生產(chǎn)量為30萬件產(chǎn)品的工廠，產(chǎn)品被運(yùn)輸?shù)轿挥贛1、M2、M3的分銷中心。由于預(yù)期將有需求增長，該公司計(jì)劃在D2、D3、D4、D5中的一個(gè)或多個(gè)城市建新工廠以增加生產(chǎn)能力。根據(jù)調(diào)查，被提議的四個(gè)城市中建立工廠的固定成本和年生產(chǎn)能力如表3.8所示。該公司對(duì)3個(gè)地區(qū)分銷中心的年需求量做了如下預(yù)測，見表3.9：表3.8各城市建立工廠的固定成本和年生產(chǎn)能力表表3.9各分銷中心的年需求量預(yù)測目標(biāo)工廠固定成本/萬元年生產(chǎn)能力/萬件D217.510D330.020D437.5030D550.040分銷中心年需求量/萬件M130M220M320根據(jù)估計(jì)，每件產(chǎn)品從每個(gè)工廠到各分銷中心的運(yùn)費(fèi)（萬元）見表3.10：請(qǐng)問：公司是否需要在四個(gè)地區(qū)中建廠，若建廠，各工廠到各分銷中心如何配送調(diào)運(yùn)？表3.10每件產(chǎn)品從每個(gè)工廠到各分銷中心的運(yùn)費(fèi)目標(biāo)工廠分銷中心M1M2M3D1523D2434D3975D41042D5843解：

引入0-1變量表示在Di處是否建立工廠,

設(shè)

表示從每個(gè)工廠到分銷中心的運(yùn)輸量(單位：萬件)。年運(yùn)輸成本和經(jīng)營新廠的固定成本之和為：

，

表示從工廠i

到分銷中心j的單位運(yùn)費(fèi)；考慮被提議工廠的生產(chǎn)能力約束條件，以D2為例，有

，其余類似；考慮分銷中心的需求量約束條件，以M1為例，有

，其余類似。因此，有整數(shù)規(guī)劃模型：利用EXCEL求解得到：總費(fèi)用為295萬元。結(jié)果表明，在D2和D4處建立分廠，從D1處運(yùn)輸給M1的數(shù)量為20萬件，D1處運(yùn)輸給M2的數(shù)量為10萬件；從D2處運(yùn)輸給M1的數(shù)量為10萬件；從D4處運(yùn)輸給M2的數(shù)量為10萬件；從D4處運(yùn)輸給M3的數(shù)量為20萬件。實(shí)際上，這一模型可以應(yīng)用于工廠與倉庫之間、工廠與零售店之間的直接運(yùn)輸和產(chǎn)品分配系統(tǒng)。利用0-1變量的性質(zhì)，有多種廠址的配置約束，比如，由于D1和D4兩地距離較近，公司不愿意同時(shí)在這兩地建廠等。案例分析2（航線的優(yōu)化安排問題）總部設(shè)在H市的A航空公司擁有J1型飛機(jī)3架、J2型飛機(jī)8架和J3型飛機(jī)2架，飛往A、B、C、D四個(gè)城市（如圖3.11所示）。如圖3.11飛行路線表通過收集相關(guān)數(shù)據(jù)，得到不同類型飛機(jī)由H市飛往各個(gè)城市的往返費(fèi)用、往返飛行時(shí)間等數(shù)據(jù)如表3.11所示。表3.11飛機(jī)類型、飛行總費(fèi)用及飛行時(shí)間數(shù)據(jù)表飛機(jī)類型飛往城市飛行總費(fèi)用/萬元飛行時(shí)間/小時(shí)J1A62B74C85D1010J2A11B24C48D—20J3A22B3.52C66D1012假定每架飛機(jī)每天的最大飛行時(shí)間為18小時(shí)，城市A為每天8班，城市B為每天11班，城市C為每天10班，城市D為每天6班。管理層希望合理安排飛行，使得總費(fèi)用最低。解：用i=1,2,3分別表示3種類型飛機(jī)，j=1,2,3,4分別代表A、B、C、D四個(gè)城市，引入決策變量表示安排第i種飛機(jī)飛往城市j的次數(shù)（i=1,2,3；j=1,2,3,4），有如下約束：（1）城市飛行班次約束：城市A城市B城市C城市D注意：由于J2型飛機(jī)飛往城市D需要20小時(shí)，超過18小時(shí)的最低要求，所以。（2）每種飛機(jī)飛行時(shí)間約束J1型J2型J3型（3）變量非負(fù)約束目標(biāo)函數(shù)為飛行費(fèi)用最小化因此，該線性規(guī)劃模型為：利用Excel求解得到：，最低的飛行費(fèi)用為130萬。案例分析3（投資項(xiàng)目選擇問題）某投資公司制訂從2015年到2019年間五年的投資計(jì)劃，根據(jù)公司資金的條件，未來五年每年年初可使用的投資額度分別是150萬元、180萬元、200萬元、230萬元和240萬元，合計(jì)1000萬元。公司已經(jīng)對(duì)多個(gè)五年期投資項(xiàng)目進(jìn)行了考察，并確定了10個(gè)備選項(xiàng)目供選擇。這些項(xiàng)目要求公司按照合同規(guī)定在未來五年的每年年初進(jìn)行投資，并在最后一年年末一次性支付投資總額。每個(gè)項(xiàng)目的投資回報(bào)率已在合同中協(xié)商確定。公司備選項(xiàng)目及投資、收益詳情如表3.12所示，問該投資公司應(yīng)如何選擇項(xiàng)目以獲取最大收益。表3.12備選項(xiàng)目投資詳表解：10個(gè)項(xiàng)目均是盈利項(xiàng)目，但由于公司資金額度的限制，不能投資全部項(xiàng)目，所以公司希望能夠充分利用已有的1000萬元資金，正確選擇投資項(xiàng)目，使得投資能夠獲得最大收益，即在第五年年末取得所確定注資項(xiàng)目投資回報(bào)總和的最大值。因此，該問題應(yīng)主要解決如何選擇所投資的項(xiàng)目，而對(duì)于項(xiàng)目的投資決策只能有兩種可能性——是或否，因此該問題的決策變量可以假設(shè)為10個(gè)0-1變量，此時(shí)投資公司的五年投資規(guī)劃可以看作一個(gè)背包問題，投資公司的背包容量即為投資限額1000萬元。在投資過程中，每年的投資總額應(yīng)該不能超過注資總額，所以又把上面的背包問題化為五個(gè)小背包問題，在滿足了每一年的小背包限制后，投資總額的大背包問題也一定不會(huì)超過總?cè)萘?。根?jù)上述分析，引入0-1變量表示投資的第i個(gè)項(xiàng)目，

該投資問題可有整數(shù)規(guī)劃模型：

利用Excel求解可以得到，得到

，

，即該公司應(yīng)當(dāng)投資第2、5、7、10個(gè)項(xiàng)目，實(shí)際總投資為910萬元，五年后回報(bào)總額為170.9萬元。案例分析4（值班人員安排問題）某部門計(jì)劃購買一臺(tái)設(shè)備，并需要人員進(jìn)行設(shè)備的監(jiān)測工作。目前部門有四名工人和兩名工程師可勝任該工作，但由于他們目前已承擔(dān)其他工作，因此只能通過加班來安排他們的監(jiān)測任務(wù)。關(guān)于設(shè)備，計(jì)劃在周一到周五的上午8點(diǎn)至晚上10點(diǎn)期間運(yùn)行，并且只需要一名人員值班。要求每名工人每周值班不少于8小時(shí)，工程師不少于7小時(shí)，每次值班不少于2小時(shí)，每天安排值班的人不超過三人，并且必須有一名工程師，由于工作強(qiáng)度的原因，每人每周值班不能超過三次。每人每天可以安排的值班時(shí)間和加班工資如表3.13所示。

根據(jù)表3.13的數(shù)據(jù)，為該部門安排一張人員值班表，使得總支付的工資最少。表3.13每人每天可以安排的值班時(shí)間和加班工資表解：用i=1,2,3,4分別表示工人甲、乙、丙、丁，i=5,6分別表示工程師甲、乙，j=1,2,3,4,5表示周一至周五，令表示值班人員i在星期j的值班時(shí)間，同時(shí)引入0-1變量根據(jù)要求有如下約束：（1）每次值班時(shí)間不少于2小時(shí)，并不能超過當(dāng)天值班人員的可安排時(shí)間（2）工人每周值班不少于8小時(shí)（4）設(shè)備每天運(yùn)行時(shí)間從上午8點(diǎn)至晚上10點(diǎn)，共14小時(shí)（3）工程師每周值班不少7小時(shí)（5）每人每周值班不超過3次（6）每天值班不超過3人變量非負(fù)約束（7）每天至少有一名工程師值班目標(biāo)函數(shù)為總支付工資最少：因此，該問題的線性規(guī)劃問題為利用Excel求解可以得到值班安排表3.14最低運(yùn)行該設(shè)備所需的工資為1373元。表3.14值班安排表復(fù)習(xí)思考題1、某公司考慮在北京、上海、廣州和武漢四個(gè)城市設(shè)立庫房，這些庫房負(fù)責(zé)向華北、華中和華南三個(gè)地區(qū)供貨，每個(gè)庫房每月可處理貨物1000件。在北京設(shè)立庫房的每月成本為4.5萬元，上海為5萬元，廣州為7萬元，武漢為4萬元。每個(gè)地區(qū)的月平均需求量為華北500件，華中800件，華南700件。發(fā)運(yùn)貨物的費(fèi)用(單位：元/件)如表3.15所示，公司希望在滿足地區(qū)需求條件下使平均月成本最小，且滿足以下條件：若在上海設(shè)立庫房，則必須在武漢設(shè)立庫房；最多設(shè)立兩個(gè)庫房；武漢和廣州不能同時(shí)設(shè)立庫房。試建立一個(gè)滿足上述要求的整數(shù)規(guī)劃模型，并求出最優(yōu)解。表3.15發(fā)運(yùn)貨物的費(fèi)用表

單位：元/件

2、某地準(zhǔn)備投資D元建民用住宅，可以建宅的地點(diǎn)有

處，在

處的造價(jià)為

，最多可建

幢。問應(yīng)當(dāng)在哪幾處建宅，分別建幾幢才能使建造的住宅總數(shù)最多。試建立此問題的數(shù)學(xué)規(guī)劃模型。3、一個(gè)旅行者要在其背包中裝一些最有用的旅行物品，背包的體積為

a，可攜帶的物品重量為b，現(xiàn)有10件物品，第

件物品的體積為

，重量為

，價(jià)值為

。每件物品只能整件裝入，不考慮物品放入背包中相互間隙，問旅行者應(yīng)攜帶哪幾種物品才能使攜帶的物品總價(jià)值最大。4、某公司制造大、中、小三種尺寸的金屬容器，所需資源為金屬板、勞動(dòng)力及機(jī)器設(shè)備，制造一個(gè)容器所需的各種資源如表3.16所示。每種容器售出的利潤分別為4萬元、5萬元和6萬元，可使用的金屬板有500t，勞動(dòng)力有300人/月，設(shè)備100臺(tái)/月。不管每種容器制造的數(shù)量是多少，需要支付一筆固定的費(fèi)用，小號(hào)為100萬元，中號(hào)為150萬元，大號(hào)為200萬元?，F(xiàn)要制定一個(gè)生產(chǎn)計(jì)劃，使獲得的利潤最大。表3.16制造一個(gè)容器所需資源表5、旅行商問題。某商人從某一城市出發(fā)，到其它n個(gè)城市去推銷商品，規(guī)定每個(gè)城市均需達(dá)到且只能到達(dá)一次，然后回到原出發(fā)城市，已知城市之間的距離為，問商人應(yīng)該選擇一條什么樣的路線旅行，使總的行走路程最短，請(qǐng)建立數(shù)學(xué)模型。6、用分支定界法求解下列問題（1）（2）7、用割平面法求解下列整數(shù)規(guī)劃問題。（1）（2）8、用隱枚舉法求解下列0-1整數(shù)規(guī)劃（1）（2）9、用匈牙利法求解系數(shù)矩陣如下的指派問題（1）（2）10、學(xué)生A、B、C、D的各門成績?nèi)绫?.17所示，現(xiàn)將此四名學(xué)生派去參加各門課的單項(xiàng)競賽，競賽同時(shí)進(jìn)行，每人只能參加一項(xiàng)。如果以他們的成績作為選拔的標(biāo)準(zhǔn)，應(yīng)如何分配最為有利？表3.17學(xué)生A、B、C、D的各門成績11.某項(xiàng)目需要完成五項(xiàng)技術(shù)檢查工作(A、B、C、D、E)，由四名技術(shù)人員(甲、乙、丙、丁)完成，其中某一名技術(shù)人員完成兩項(xiàng)工作，其余技術(shù)人員各完成一項(xiàng)工作。已知不同技術(shù)人員完成不同檢查工作所消耗的時(shí)間如表3.18所示。請(qǐng)利用Excel求解該問題的最優(yōu)分配方案，使得所消耗的總時(shí)間最少。表3.18不同技術(shù)人員完成不同檢查工作所消耗的時(shí)間

單位：小時(shí)12.已知0-1整數(shù)規(guī)劃試用Excel求解該0

-1整數(shù)規(guī)劃的最優(yōu)解。13.五名游泳運(yùn)動(dòng)員的百米最好成績?nèi)绫?.19所示，應(yīng)從中選哪四個(gè)人組成一個(gè)4×100m混合泳接力隊(duì)？表3.19五名游泳運(yùn)動(dòng)員的百米最好成績表試用Excel求解該指派問題的最優(yōu)解。

南京航空航天大學(xué)經(jīng)濟(jì)與管理學(xué)院運(yùn)籌學(xué)第四章圖論與網(wǎng)絡(luò)計(jì)劃圖論是目前運(yùn)用十分廣泛的運(yùn)籌學(xué)分支之一。一個(gè)龐大而復(fù)雜的工程系統(tǒng)和管理問題用圖來描述，可以解決許多工程設(shè)計(jì)和管理決策的最優(yōu)化問題。所謂網(wǎng)絡(luò)計(jì)劃技術(shù),是以工序所需工時(shí)為時(shí)間因素，用工序之間相互聯(lián)系的網(wǎng)絡(luò)和一些簡單的算法，來反映整個(gè)工程或任務(wù)的全貌，并且在既定的條件下，全面籌劃，統(tǒng)一安排，來尋求達(dá)到預(yù)定目標(biāo)的最優(yōu)實(shí)施方案。圖論與網(wǎng)絡(luò)計(jì)劃問題應(yīng)用廣泛，涉及計(jì)算機(jī)、物理學(xué)、化學(xué)、控制論、信息論、管理經(jīng)濟(jì)科學(xué)等多學(xué)科多領(lǐng)域，在日常生活中，有助于解決各種各樣的決策問題。4.1圖與網(wǎng)絡(luò)自然界和人類社會(huì)中許多事物以及事物之間的關(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)一步研究從一個(gè)城市到另一個(gè)城市的最短路徑；或者標(biāo)上單位運(yùn)價(jià)，就可分析運(yùn)費(fèi)最小的運(yùn)輸方案。本節(jié)將介紹有關(guān)圖與網(wǎng)絡(luò)的基本概念。4.1.1圖的基本概念一、無向圖二、有向圖4.1.2網(wǎng)絡(luò)的基本概念實(shí)際問題中，往往只用圖來描述所研究對(duì)象之間的關(guān)系還不夠，如果在圖中賦予邊一定的數(shù)量指標(biāo)，我們常稱之為“權(quán)”。依據(jù)研究問題的需要，權(quán)可以代表距離，也可以代表時(shí)間、費(fèi)用、容量、可靠性等。通常把這種賦權(quán)圖稱為網(wǎng)絡(luò)。與無向圖和有向圖相對(duì)應(yīng)，網(wǎng)絡(luò)又分為無向網(wǎng)絡(luò)和有向網(wǎng)絡(luò)。我們除了用圖形來表示圖外，為便于數(shù)據(jù)處理和計(jì)算機(jī)存儲(chǔ)，還可以用矩陣來表示一個(gè)圖。4.2最小生成樹問題4.2.1最小生成樹一、樹的基本概念先看一個(gè)具體的實(shí)例：例4－1已知有5個(gè)城市，要在它們之間架設(shè)電話線網(wǎng)，要求任何兩個(gè)城市都可以彼此通話（允許通過其他城市），并且電話線的條數(shù)最少。用點(diǎn)分別表示5個(gè)城市。設(shè)想一下，如果在與，與，與之間各架一條電話線，這個(gè)方案可用圖4－5（a）表示出來。這個(gè)方案顯然是不滿足要求的，因?yàn)樵谶@樣的電話線網(wǎng)中，與之間就不能通話。因此，根據(jù)要求，設(shè)計(jì)出來的電話網(wǎng)方案必須是連通的。如果按照?qǐng)D4－5（b）來設(shè)計(jì)電話網(wǎng)，雖然方案能滿足不同城市之間通話的要求，但卻不能保證電話線的條數(shù)最少。原因是構(gòu)成一個(gè)圈，如果從這個(gè)圈上，任意去掉一條，并不影響電話網(wǎng)的連通性，同時(shí)又可節(jié)省一條線。所以圖4－5（b）對(duì)應(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)和軍隊(duì)建制中的隸屬關(guān)系、圖書分類、會(huì)計(jì)科目、決策過程等等都可以用樹表示。下面研究樹的性質(zhì)。樹的性質(zhì)可用下面定理給出。4.2.2最小生成樹算法尋找最小生成樹首先考慮構(gòu)建生成樹，但要在舍邊和增邊時(shí)，增加一些邊的權(quán)數(shù)的限制。一、破圈法破圈法步驟：從圖中任取一圈，去掉這個(gè)圈中權(quán)數(shù)最大的一條邊，得一支撐子圖。在中再任取一圈，再去掉圈中權(quán)數(shù)最大的一條邊，得。如此繼續(xù)下去，一直到剩下的子圖中不再含圈為止。該子圖就是的最小生成樹。二、Kruskal算法（避圈法）Kruskal算法是Kruskal于1956年提出的一個(gè)產(chǎn)生最小樹的算法，算法的基本思想是：每次將一條權(quán)最小的弧加入子圖T中，并保證不形成圈。即按照邊長由小到大排序，如果當(dāng)前弧加入后不形成圈，則加入這條弧。當(dāng)弧有條時(shí)，即為最小生成樹。例4-2用Kruskal算法求解下圖4-6(a)所示網(wǎng)絡(luò)的最小生成樹，每條邊上的數(shù)表示該邊的權(quán)值。解：通過對(duì)邊由小到大排序，按照避圈法的原則，初步增加到T中。最小生成樹如下：4.2.3最小生成樹Excel軟件求解樹是一種重要的簡單圖，在許多領(lǐng)域都有廣泛的應(yīng)用。我們稱連通且不含圈的無向圖為為樹。若圖的生成子圖是一棵樹，則該樹稱為的生成樹。樹的各條邊稱為樹枝，一般圖包含有多個(gè)生成樹，最小生成樹是其中樹枝總長最小的生成樹。圖的最小生成樹一般不唯一。最小生成樹是網(wǎng)絡(luò)優(yōu)化中一個(gè)重要的概念，它在交通網(wǎng)、電話網(wǎng)、管道網(wǎng)、電力網(wǎng)等設(shè)計(jì)中均有廣泛的應(yīng)用。在城市間高速公路的建設(shè)、城市間通信網(wǎng)絡(luò)線路的鋪設(shè)、輸油管線的架設(shè)、礦井通風(fēng)設(shè)施的優(yōu)化設(shè)計(jì)與改造等方面，可以應(yīng)用最小生成樹的原理使得建設(shè)的成本最小。盡管我們已經(jīng)介紹了破圈法、Kruskal算法求最小生成樹，但是這幾種方法對(duì)于復(fù)雜案例計(jì)算量太大，無法直接用來解決實(shí)際問題，因此，方便快捷地產(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所示。表中左上角是一個(gè)5×5的對(duì)稱權(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單元格,它取該行元素的和）。這意味著一個(gè)節(jié)點(diǎn)至少與其它一個(gè)節(jié)點(diǎn)相連。2）變量矩陣的每列的列和（A13：E13）等于相應(yīng)的行和（對(duì)稱矩陣）。3）總邊數(shù)（B16）等于頂點(diǎn)數(shù)減一(此例為4)，這是樹的定義?？傔厰?shù)就是A8：E12的所有元素和除以“2”（因?yàn)槊織l邊有兩個(gè)節(jié)點(diǎn)重復(fù)計(jì)算了一次，所有要除以“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計(jì)算過程（5）求解：目標(biāo)函數(shù)：Min（總建設(shè)費(fèi)用最?。┘s束條件：變量矩陣=bin總邊數(shù)=頂點(diǎn)個(gè)數(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)化問題可以使用這個(gè)模型，如設(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)用的重要組成部分。所謂的最大流量問題就是：給一個(gè)帶收發(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)號(hào)法）是公認(rèn)的好算法。在圖論中，所謂“好算法”，即在任何圖上施行這個(gè)算法所需要的計(jì)算步數(shù)都能以該圖頂點(diǎn)數(shù)和弧數(shù)的一個(gè)多項(xiàng)式（如）為其上界。若一個(gè)算法的施行需要指數(shù)步數(shù)（如），則對(duì)某些大的圖而言，它將是無效的。最后再強(qiáng)調(diào)一下,Dijkstra算法只適用于權(quán)值為正實(shí)數(shù)的情況，如果權(quán)值有負(fù)的，算法失效。Dijkstra算法都是求點(diǎn)到點(diǎn)之間的最短路。4.3.2最短路問題EXCEL軟件求解最短路問題是網(wǎng)絡(luò)計(jì)劃問題中應(yīng)用最廣泛的問題之一。在前面的學(xué)習(xí)中，求解最短路問題的方法主要介紹了Dijkstra算法。不同于傳統(tǒng)的Dijkstra算法，用excel求解最短路問題，利用了excel的“規(guī)劃求解”在確定最優(yōu)方案的計(jì)算方面有獨(dú)到之處的優(yōu)點(diǎn)，通過直接或間接地把電子表格中與公式相聯(lián)系的一組單元格中的數(shù)值進(jìn)行調(diào)整，使某個(gè)與公式相關(guān)聯(lián)的單元格達(dá)到期望的結(jié)果，由此來為電子表格中滿足一定要求的單元格找到一個(gè)優(yōu)化值。這是一個(gè)典型的圖論中的最短路問題，下面我們介紹使用EXCEL建模求解的具體思路。在用EXCEL解決最短路問題時(shí)，起點(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)，所以每一個(gè)所產(chǎn)生的凈流量為0；弧的長度可以看作是網(wǎng)絡(luò)中流的單位成本；如果我們選擇的路經(jīng)過某一特定的弧，則認(rèn)為該弧的流量為1，否則流量為0.這樣一來，使某條路的總長度最短就等價(jià)于網(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ù)這些條件，可以對(duì)圖中每一個(gè)頂點(diǎn)做一個(gè)約束。指向一個(gè)頂點(diǎn)的弧對(duì)應(yīng)C列的值之和即為該頂點(diǎn)的流入量，同理，從一頂點(diǎn)指出的弧對(duì)應(yīng)C列的值之和即為該頂點(diǎn)的流出量，對(duì)于中間各點(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）計(jì)算得出規(guī)劃求解結(jié)果。經(jīng)過規(guī)劃求解后，可以得到最短路徑的最小總距離，也可以通過表格觀察得到具體的路徑，C列中取1的即表示該弧被選入路徑中。倘若需要計(jì)算從起點(diǎn)到非終點(diǎn)的最短距離最短路，則相應(yīng)的改變約束條件即可。在此，我們利用Excel軟件對(duì)例4－11進(jìn)行求解，為讀者展示如何用Excel求解最短路問題。例4－5一個(gè)網(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個(gè)節(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列分別代表圖中的八個(gè)節(jié)點(diǎn)，由以上分析知，起始點(diǎn)v1的凈流量（即出度-入度）為1，終止點(diǎn)v8的凈流量為-1，其余中間點(diǎn)為0，I列即為設(shè)定好的凈流量數(shù)值列，G列為檢驗(yàn)列，需要和F列相應(yīng)行保持一致。其中，G列設(shè)置如下：圖4－13檢驗(yàn)列的輸入過程約束條件和目標(biāo)函數(shù)設(shè)置。約束條件總共有兩個(gè)，第一個(gè)需要將C列設(shè)為0-1變量；第二個(gè)約束需要使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)在考慮這樣一個(gè)問題，要把一批貨物從起點(diǎn)通過鐵路網(wǎng)絡(luò)運(yùn)到終點(diǎn)去，把鐵路網(wǎng)上的車站看作頂點(diǎn)，兩個(gè)車站間的鐵路線看作弧，而每條鐵路線上運(yùn)送的貨物總量（容量）總是有限的，我們把某線路上的最大可能運(yùn)送量稱為它的容量，即每條弧上通過的貨物總量不能超過這條弧的容量?？紤]：如何安排運(yùn)輸方案，使得從起點(diǎn)運(yùn)到終點(diǎn)的總運(yùn)量達(dá)到最大？圖4－16鐵路容量網(wǎng)絡(luò)圖上面這個(gè)問題就是要在鐵路網(wǎng)絡(luò)上，求最大流的問題。這里的“流”，是指鐵路線（?。┥系膶?shí)際運(yùn)輸量。圖4－16所示網(wǎng)絡(luò)中，每條弧旁的數(shù)字即為該弧的容量，弧的方向就是允許流的方向。顯然，在研究該問題時(shí)，可以把網(wǎng)絡(luò)中指向起點(diǎn)的弧以及從終點(diǎn)出發(fā)的弧都去掉，而不會(huì)影響問題的解。下面以圖4－17為例來介紹最大流問題的基本概念與模型。圖4－17網(wǎng)絡(luò)圖中的容量和可行流（1）容量網(wǎng)絡(luò)與流在研究網(wǎng)絡(luò)流問題時(shí)，首先應(yīng)給出各弧的通過能力，如圖4－16所示各弧的權(quán)數(shù)，它們表示弧的容量，記為，我們把標(biāo)有弧容量的網(wǎng)絡(luò)稱為容量網(wǎng)絡(luò)，記為。2)節(jié)點(diǎn)流量平衡條件：網(wǎng)絡(luò)中的流量必須滿足守恒條件，對(duì)收發(fā)點(diǎn)來說，發(fā)點(diǎn)的總流出量=收點(diǎn)的總流入量；對(duì)中間點(diǎn)來說，中間點(diǎn)的總流入量=總流出量。例如，對(duì)一個(gè)給定的容量網(wǎng)絡(luò)，凡是滿足以上兩個(gè)條件的網(wǎng)絡(luò)流都稱為可行流。顯然，上圖4－17網(wǎng)絡(luò)流為可行流。尋求網(wǎng)絡(luò)最大流就是找到一個(gè)可行流，使得網(wǎng)絡(luò)發(fā)點(diǎn)到收點(diǎn)的總流量達(dá)到最大。網(wǎng)絡(luò)最大流問題的線性規(guī)劃表達(dá)式是顯然，網(wǎng)絡(luò)最大流問題是一個(gè)典型而又特殊的線性規(guī)劃問題，一個(gè)可行流相當(dāng)于線性規(guī)劃中的一個(gè)可行解，而尋求最大流就相當(dāng)于求網(wǎng)絡(luò)容量的最優(yōu)解，自然可用介紹過的單純形法進(jìn)行求解。但利用單純形方法得到網(wǎng)絡(luò)最大流問題的解，計(jì)算量過大。由于這一問題的特殊性，用網(wǎng)絡(luò)模型方法求解，更直觀、簡便。下面介紹由Ford和Fulkerson于1956年提出的算法。為此，先介紹與求解方法有關(guān)的概念和原理。第四步：再標(biāo)號(hào)同上述第二步標(biāo)號(hào)，易見，當(dāng)給標(biāo)號(hào)后，無法再進(jìn)行下去，此時(shí)，，，。因此，目前所得到的可行流就是最大流，最大流量為。4.3.4最大流算法的Excel軟件求解最大流問題也具有極為廣泛的運(yùn)用，通過前面的學(xué)習(xí)，我們了解到求解此問題的方法為最大流最小截集定理以及Ford-Fulkerson標(biāo)號(hào)算法。由于最大流最小截集定理較為繁瑣，在運(yùn)用時(shí)也易出錯(cuò)，所以更為常用的方法是Ford-Fulkerson標(biāo)號(hào)算法。在本節(jié)，通過使用Excel對(duì)教材中例4－7進(jìn)行求解，為讀者展示如何用Excel求解最大流問題。這是一個(gè)典型的最大流問題，在用EXCEL規(guī)劃求解時(shí)，其思路不同于傳統(tǒng)算法。在用EXCEL求解時(shí)，最大流問題與最短路問題模型的構(gòu)建是類似的，但有幾個(gè)條件需要改變。首先是可行流量為小于或等于容量的關(guān)系；其次是起始與終止點(diǎn)的邏輯判斷值不再是1和-1而變?yōu)闊o限制；再者是目標(biāo)函數(shù)應(yīng)該求最大值。例4－8用Excel軟件求圖4－19所示的網(wǎng)絡(luò)最大流，括號(hào)中第一個(gè)數(shù)字是容量，第二個(gè)數(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)號(hào)算法獲得的結(jié)果是一致的。

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

圖4－23運(yùn)輸容量網(wǎng)絡(luò)圖這是一個(gè)典型的最大流問題。把圖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ù)。約束條件共兩個(gè)，即流量小于等于容量和凈流量等于供應(yīng)-需求。目標(biāo)函數(shù)即凈流量起點(diǎn)v1值最大。規(guī)劃求解方案如圖4－26：

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

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

序工序代號(hào)所需時(shí)間(天)緊后工序產(chǎn)品設(shè)計(jì)與工藝設(shè)計(jì)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個(gè)工序。箭線下面的數(shù)字表示為完成該個(gè)工序所需的時(shí)間（天數(shù)）。節(jié)點(diǎn)①、②、…、⑧分別表示某一或某些工序的開始和結(jié)束。例如，節(jié)點(diǎn)②表示a工序的結(jié)束和b、c、d、e等工序的開始，即a工序結(jié)束后，后四個(gè)工序才能開始。圖4－28網(wǎng)絡(luò)圖繪制12467835a6045c10d20e40f18g30h15k25l350在繪制網(wǎng)絡(luò)圖中，用一條弧和兩個(gè)節(jié)點(diǎn)表示一個(gè)確定的工序。例如，②→⑦表示一個(gè)確定的工序b。工序開始的節(jié)點(diǎn)稱為箭尾節(jié)點(diǎn)，如b工序的②；工序結(jié)束的節(jié)點(diǎn)稱為箭頭節(jié)點(diǎn)，如b工序的⑦。②稱為箭尾事項(xiàng)，⑦稱為箭頭事項(xiàng)。工序的箭尾事項(xiàng)與箭頭事項(xiàng)稱為該工序的相關(guān)事項(xiàng)。在一張網(wǎng)絡(luò)圖上只能有始點(diǎn)和終點(diǎn)兩個(gè)節(jié)點(diǎn)，分別表示工程的開始和結(jié)束，其它節(jié)點(diǎn)既表示上一個(gè)（或若干個(gè)）工序的結(jié)束，又表示下一個(gè)（或若干個(gè)）工序的開始。 為正確反映工程中各個(gè)工序的相互關(guān)系，在繪制網(wǎng)絡(luò)圖時(shí)，應(yīng)遵循以下規(guī)則：(1)方向、時(shí)序與節(jié)點(diǎn)編號(hào) 網(wǎng)絡(luò)圖是有向圖，按照工藝流程的順序，規(guī)定工序從左向右排列。網(wǎng)絡(luò)圖中的各個(gè)節(jié)點(diǎn)都有一個(gè)時(shí)間(某一個(gè)或若干個(gè)工序開始或結(jié)束的時(shí)間)，一般按各個(gè)節(jié)點(diǎn)的時(shí)間順序編號(hào)。為了便于修改編號(hào)及調(diào)整計(jì)劃，可以在編號(hào)過程中留出一些編號(hào)