運(yùn)籌學(xué)（第2版）課件 第三章 整數(shù)規(guī)劃

南京航空航天大學(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)營(yíng)航線(xiàn)，每種機(jī)型的運(yùn)營(yíng)成本也都有所不同，如何安排不同機(jī)型承擔(dān)運(yùn)輸任務(wù)是航空公司生產(chǎn)運(yùn)營(yíng)過(guò)程中一項(xiàng)非常重要的工作。

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

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

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

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

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

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

，顯然

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

必定有

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

和（LP2）

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

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

和

。

變量

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

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

；求解（LP12），得到

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

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

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

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

。上述求解過(guò)程稱(chēng)為分支定界算法，求解過(guò)程用圖3.1表示：

圖3.1例3.2求解過(guò)程

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

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

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

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

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

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

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

，若其值為

，以

表示小于

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

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

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

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

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

，若無(wú)可行解，則

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

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

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

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

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

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

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

某公司擬在市東、西、南三區(qū)建立門(mén)市部，有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ì)為

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

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

表示是否在位置i建立門(mén)市部，有

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

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

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

，重量為

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

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

W；②A(yíng)1與A3中最多安裝一件；③A2與A4中至少安裝一件；④A5與A6或者都安裝上，或者都不安裝。

總的目的是裝上去的儀器裝置使該科學(xué)實(shí)驗(yàn)衛(wèi)星發(fā)揮最大的實(shí)驗(yàn)價(jià)值。試建立這個(gè)問(wèn)題的數(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)星裝載要求,該問(wèn)題的決策變量是0-1整數(shù)變量。3.2.3隱枚舉法

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

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

稱(chēng)為0-1變量，這類(lèi)問(wèn)題被稱(chēng)為0-1整數(shù)規(guī)劃。對(duì)于

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

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

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

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

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

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

。

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

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

新增加的約束條件稱(chēng)為過(guò)濾條件。原問(wèn)題的線(xiàn)性約束條件就變成5個(gè)，3個(gè)變量共有23=8個(gè)解，原來(lái)4個(gè)約束條件共需32次運(yùn)算，增加了過(guò)濾條件后，將5個(gè)約束條件按(3.1)～(3.5)的順序排好(見(jiàn)表3.2)，對(duì)每個(gè)解，依次代入約束條件左側(cè)，求出數(shù)值，看是否滿(mǎn)足不等式條件，如某一條件不適合，同行以下條件就不必再檢查，這樣可以減少運(yùn)算次數(shù)。于是求得最優(yōu)解，maxZ=8。在計(jì)算過(guò)程中，若遇到z值已超過(guò)條件（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ī)劃求解問(wèn)題。把基礎(chǔ)數(shù)據(jù)輸入到Excel電子表格中，如圖3.6所示。圖3.6矩陣形式電子表格模型

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

在所有參數(shù)被設(shè)置完后點(diǎn)擊“求解”，最優(yōu)解報(bào)告會(huì)顯示出來(lái)。在可變單元格部分，“初值”欄顯示的是任意輸入的初始變量數(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指派問(wèn)題3.3.1指派問(wèn)題模型

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

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

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

表示指派第

i個(gè)人去完成第

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

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

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

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

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

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

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

，那么以

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

以例3.6來(lái)理解上述性質(zhì)，對(duì)甲來(lái)說(shuō)，只能完成一項(xiàng)任務(wù)，若其無(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ù)矩陣中，一般稱(chēng)位于不同行不同列的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年庫(kù)恩（W.W.Kuhn）利用匈牙利數(shù)學(xué)家康尼格（D.Konig）一個(gè)關(guān)于矩陣中0元素的定理，提出了指派問(wèn)題的解法，稱(chēng)為匈牙利法。該定理證明了以下結(jié)論：

系數(shù)矩陣中，獨(dú)立元素0元素的最大個(gè)數(shù)等于能覆蓋所有0元素的最小直線(xiàn)數(shù)。下面用例3.6來(lái)說(shuō)明該方法的應(yīng)用步驟。第一步：使指派問(wèn)題的系數(shù)矩陣經(jīng)變換，在各行各列中都出現(xiàn)0元素。（1）從系數(shù)矩陣的每行元素減去該行的最小元素；（2）再?gòu)乃孟禂?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í)，可用觀(guān)察法、試探法去找出n個(gè)獨(dú)立0元素。若n較大時(shí)，就必須按一定的步驟去找，常用的步驟為：①?gòu)闹挥幸粋€(gè)0元素的行（列）開(kāi)始，給這個(gè)0元素加圈，記作◎。這表示對(duì)這行所代表的人，只有一種任務(wù)可指派。然后劃去◎所在列（行）的其他0元素，記作

。這表示這列所代表的任務(wù)已指派完，不必再考慮別人。②反復(fù)進(jìn)行步驟（1），直到所有0元素都被圈出或劃掉為止。③若仍有沒(méi)有畫(huà)圈的0元素，且同行（列）的0元素至少有兩個(gè)（表示對(duì)這個(gè)可以從兩項(xiàng)任務(wù)中指派其一）。則從剩有0元素最少的行（列）開(kāi)始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個(gè)0元素加圈（表示選擇性多的要“禮讓”選擇性少的）。然后劃掉同行同列的其他0元素。可反復(fù)進(jìn)行，直到所有0元素都已圈出或劃掉為止。④若◎元素的數(shù)目m等于矩陣的階數(shù)n，那么指派問(wè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所示效率矩陣的指派問(wèn)題的最小解。解：按上述第一步，將這系數(shù)矩陣進(jìn)行變換。表3.7例3.7的效率矩陣按第二步，得到：這里◎的個(gè)數(shù)m=4，而

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

元素的列打√號(hào)；再對(duì)打有√號(hào)的列中含◎元素的行打√號(hào)；重復(fù)（2），（3）直到得不出新的打√號(hào)的行、列為止；對(duì)沒(méi)有打√號(hào)的行畫(huà)一橫線(xiàn)，已打√號(hào)的列畫(huà)一縱線(xiàn)，這就得到覆蓋所有0元素的最少直線(xiàn)數(shù)。令這直線(xiàn)數(shù)為l。若l<n，說(shuō)明必須再變換當(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ì)沒(méi)有打√行，畫(huà)一直線(xiàn)以覆蓋0元素，已打√的列畫(huà)一直線(xiàn)以覆蓋0元素。得

√√√由此可見(jiàn)。所以應(yīng)繼續(xù)對(duì)矩陣進(jìn)行變換，轉(zhuǎn)第四步。第四步：該步進(jìn)行矩陣變換的目的是增加0元素。在沒(méi)有被直線(xiàn)覆蓋的部分中找出最小元素。然后在打√行各元素中都減去這最小元素，而在打√列的各元素都加上這最小元素，以保證原來(lái)0元素不變。若得到n個(gè)獨(dú)立的0元素，則已得最優(yōu)解，否則回到第三步重復(fù)進(jìn)行。在沒(méi)有被覆蓋部分（第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)指派問(wèn)題的系數(shù)矩陣，經(jīng)過(guò)變換得到了同行和同列中都有兩個(gè)或兩個(gè)以上0元素時(shí)，這時(shí)可以任選一行（列）中某一個(gè)0元素，再劃去同行（列）的其他0元素。這時(shí)會(huì)出現(xiàn)多重解。

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

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

，可令

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

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

，這時(shí)

，符合匈牙利法的條件。

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

，所得最小解就是原問(wèn)題最大解，因?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í)際上無(wú)法安排；當(dāng)m<n時(shí)，可設(shè)“虛工作”，各工作人員從事虛工作的效率為0，被指派做虛擬工作的人的狀態(tài)，實(shí)際是休息狀態(tài)。此時(shí)，即可將問(wèn)題得到轉(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）不平衡指派問(wèn)題的擴(kuò)展

三個(gè)工人從事四項(xiàng)工作，某一工人從事二項(xiàng)工作，求花費(fèi)時(shí)間最小的指派。先不考慮“某一工人從事二項(xiàng)工作”，則增加虛擬工作人員，得到最優(yōu)指派后，剩余工作必定由三人中完成該項(xiàng)任務(wù)花費(fèi)時(shí)間最少的來(lái)從事。與（2）不同的是，該虛工作人員完成任務(wù)的時(shí)間花費(fèi)等于各項(xiàng)任務(wù)中三人的最少花費(fèi)時(shí)間，該問(wèn)題即得到表3.7。用匈牙利法求解該問(wèn)題，若虛工作人員從事G工作，表明第四項(xiàng)工作由甲完成；若虛工作人員從事J工作，表明第四項(xiàng)工作由乙完成。表3.7不平衡指派問(wèn)題擴(kuò)展表人員任務(wù)EJGR甲215134乙1041415丙9141613“虛工作人員”24134在不平衡指派問(wèn)題中，在工人數(shù)大于工作數(shù)情況下，增加虛工作：某人必須被指派工作。則該人從事虛工作的時(shí)間花費(fèi)為“M”，表示工作花費(fèi)時(shí)間無(wú)窮大，其余人從事該虛工作的時(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指派問(wèn)題的Excel求解

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

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

按照?qǐng)D3.9設(shè)置完參數(shù)后，點(diǎn)擊“求解”，則可以得到指派問(wè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指派問(wèn)題求解參數(shù)設(shè)置圖3.10指派問(wèn)題的最優(yōu)解3.4案例分析案例分析1（分銷(xiāo)中心選址問(wèn)題）A公司在D1處經(jīng)營(yíng)一家年生產(chǎn)量為30萬(wàn)件產(chǎn)品的工廠(chǎng)，產(chǎn)品被運(yùn)輸?shù)轿挥贛1、M2、M3的分銷(xiāo)中心。由于預(yù)期將有需求增長(zhǎng)，該公司計(jì)劃在D2、D3、D4、D5中的一個(gè)或多個(gè)城市建新工廠(chǎng)以增加生產(chǎn)能力。根據(jù)調(diào)查，被提議的四個(gè)城市中建立工廠(chǎng)的固定成本和年生產(chǎn)能力如表3.8所示。該公司對(duì)3個(gè)地區(qū)分銷(xiāo)中心的年需求量做了如下預(yù)測(cè)，見(jiàn)表3.9：表3.8各城市建立工廠(chǎng)的固定成本和年生產(chǎn)能力表表3.9各分銷(xiāo)中心的年需求量預(yù)測(cè)目標(biāo)工廠(chǎng)固定成本/萬(wàn)元年生產(chǎn)能力/萬(wàn)件D217.510D330.020D437.5030D550.040分銷(xiāo)中心年需求量/萬(wàn)件M130M220M320根據(jù)估計(jì)，每件產(chǎn)品從每個(gè)工廠(chǎng)到各分銷(xiāo)中心的運(yùn)費(fèi)（萬(wàn)元）見(jiàn)表3.10：請(qǐng)問(wèn)：公司是否需要在四個(gè)地區(qū)中建廠(chǎng)，若建廠(chǎng)，各工廠(chǎng)到各分銷(xiāo)中心如何配送調(diào)運(yùn)？表3.10每件產(chǎn)品從每個(gè)工廠(chǎng)到各分銷(xiāo)中心的運(yùn)費(fèi)目標(biāo)工廠(chǎng)分銷(xiāo)中心M1M2M3D1523D2434D3975D41042D5843解：

引入0-1變量表示在Di處是否建立工廠(chǎng),

設(shè)

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

，

表示從工廠(chǎng)i

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

，其余類(lèi)似；考慮分銷(xiāo)中心的需求量約束條件，以M1為例，有

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

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

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

，

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

根據(jù)表3.13的數(shù)據(jù)，為該部門(mén)安排一張人員值班表，使得總支付的工資最少。表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í)，并不能超過(guò)當(dāng)天值班人員的可安排時(shí)間（2）工人每周值班不少于8小時(shí)（4）設(shè)備每天運(yùn)行時(shí)間從上午8點(diǎn)至晚上10點(diǎn)，共14小時(shí)（3）工程師每周值班不少7小時(shí)（5）每人每周值班不超過(guò)3次（6）每天值班不超過(guò)3人變量非負(fù)約束（7）每天至少有一名工程師值班目標(biāo)函數(shù)為總支付工資最少：因此，該問(wèn)題的線(xiàn)性規(guī)劃問(wèn)題為利用Excel求解可以得到值班安排表3.14最低運(yùn)行該設(shè)備所需的工資為1373