運籌學（第2版）課件 第3-5章 整數(shù)規(guī)劃；圖論與網(wǎng)絡計劃；存儲論

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

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

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

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

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

從上述情況可以看出，航空公司機型分配與前面介紹的線性規(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ù)要求和限制來進行區(qū)分的。3.1.1整數(shù)規(guī)劃的求解例3.1某廠擬用集裝箱托運甲、乙兩種貨物，兩種貨物的體積、質(zhì)量、單件利潤以及集裝箱托運限制情況如表3.1所示。問兩種貨物各托運多少箱，可使獲得的利潤為最大？表3.1兩種貨物的體積、質(zhì)量、單件利潤以及集裝箱托運限制情況解：設分別為甲、乙兩種貨物的托運箱數(shù)，則數(shù)學模型可以表示為：其中，目標函數(shù)代表追求最大利潤，約束條件是對集裝箱的體積和質(zhì)量限制，決策變量要求集裝箱數(shù)量必須是整數(shù)。3.1.2分支定界算法當涉及整數(shù)規(guī)劃問題的求解時，可以使用單純形算法來求得非整數(shù)約束下的最優(yōu)解，然后通過四舍五入或取整法來獲得最優(yōu)整數(shù)解。然而，這種方法有時并不能保證得到整數(shù)規(guī)劃的最優(yōu)解。

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

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

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

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

，顯然

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

必定有

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

和（LP2）

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

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

和

。

變量

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

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

；求解（LP12），得到

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

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

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

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

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

圖3.1例3.2求解過程

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

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

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

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

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

，然后按下述步驟進行迭代。分支過程。在

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

，若其值為

，以

表示小于

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

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

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

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

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

，若無可行解，則

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

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

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

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

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

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

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

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

（

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

三個點中至多選兩個；在西區(qū)，由

兩個點中至少選一個；在南區(qū)，由

兩個點中至少選一個。

如選用

點，設備投資預計為

元，每年可獲利潤預計為

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

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

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

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

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

，重量為

，該裝置在實驗中的價值為

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

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

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

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

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

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

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

的取值只能為0或1，此時變量

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

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

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

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

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

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

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

。

對于極大化問題，應有

，于是增加一個約束條件：（5）

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

Z=5＞3，所以應將條件（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進行0-1整數(shù)規(guī)劃求解的步驟與一般的整數(shù)規(guī)劃求解類似。不同點是需要指明所有變量是0-1決策變量。例如說明在“B8”位置上的第一個變量是0-1形式的變量，在選擇按鈕處選擇“bin”就意味著第一個變量被限制為“0-1”決策變量，如圖3.7所示。

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

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

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

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

表示指派第

i個人去完成第

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

目標函數(shù)表示

n個人完成任務所需的時間最少（或效率最高）；第一個約束條件說明第

j項任務只能由1人去完成；第二個約束條件說明第

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

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

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

，那么以

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

以例3.6來理解上述性質(zhì)，對甲來說，只能完成一項任務，若其無論完成哪項任務都減少相同的時間，這種時間變動并不改變甲在四項任務中的最佳選擇；若完成某項任務的四個人都減少相同的時間，同樣，這種時間的節(jié)省并不改變?nèi)蝿諏ν瓿扇说淖罴堰x擇。

3.3.2匈牙利法

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

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

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

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

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

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

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

在例3.7中，對矩陣按以下次序進行：

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

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

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

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

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

，可令

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

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

，這時

，符合匈牙利法的條件。

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

，所得最小解就是原問題最大解，因為：

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

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

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

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

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

按照圖3.9設置完參數(shù)后，點擊“求解”，則可以得到指派問題的最優(yōu)解，如圖3.10所示。

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

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

設

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

，

表示從工廠i

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

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

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

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

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

，

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

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

單位：元/件

2、某地準備投資D元建民用住宅，可以建宅的地點有

處，在

處的造價為

，最多可建

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

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

件物品的體積為

，重量為

，價值為

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

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

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

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

4.3.1最短路算法

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

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

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

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

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

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

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

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