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

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

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

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

機(jī)型分配問題主要通過考慮飛機(jī)飛行時間、旅客數(shù)量、兩地航班次數(shù)等約束條件，建立總成本最小的目標(biāo)函數(shù)，從而得到最優(yōu)的機(jī)型配置方案。在這類問題中，最優(yōu)解是各種類型飛機(jī)班次，所以是一定是整數(shù)。因此航空公司大多采用基于整數(shù)規(guī)劃算法的航班計劃編制管理系統(tǒng)解決機(jī)型分配問題，該系統(tǒng)能為航空公司提高飛機(jī)利用率、節(jié)省航班計劃編制時間，從而提高航空公司整體的經(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ù)代表追求最大利潤，約束條件是對集裝箱的體積和質(zhì)量限制，決策變量要求集裝箱數(shù)量必須是整數(shù)。3.1.2分支定界算法當(dāng)涉及整數(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。此時，目標(biāo)函數(shù)z=80,這個解也不是最優(yōu)解。由此表明，四舍五入或者取整法得到的解并不是整數(shù)規(guī)劃的最優(yōu)解。

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

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

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

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

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

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

，若其值為

，以

表示小于

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

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

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

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

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

，若無可行解，則

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

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

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

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

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

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

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

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

（

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

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

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

兩個點中至少選一個。

如選用

點，設(shè)備投資預(yù)計為

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

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

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

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

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

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

，重量為

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

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

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

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

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

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

其中，目標(biāo)函數(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比較大的情況，仍需要進(jìn)行大量的計算，計算工作也是很難完成的。

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

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

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

。

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

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

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

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ī)劃求解類似。不同點是需要指明所有變量是0-1決策變量。例如說明在“B8”位置上的第一個變量是0-1形式的變量，在選擇按鈕處選擇“bin”就意味著第一個變量被限制為“0-1”決策變量，如圖3.7所示。

在所有參數(shù)被設(shè)置完后點擊“求解”，最優(yōu)解報告會顯示出來。在可變單元格部分，“初值”欄顯示的是任意輸入的初始變量數(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)常會遇到這樣的問題：某單位需完成n項任務(wù)，恰好有n個人可承擔(dān)這些任務(wù)。由于每人的專長不同，各人完成任務(wù)所需的時間也不同。問題是，應(yīng)指派哪個人去完成哪項任務(wù)，使完成n項任務(wù)的總體所需總時間最??？這類問題稱為指派問題或分配問題（AssignmentProblem）。例3.6

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

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

表示指派第

i個人去完成第

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

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

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

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

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

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

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

，那么以

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

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

3.3.2匈牙利法

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

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

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

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

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

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

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

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

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

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

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

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

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

，可令

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

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

，這時

，符合匈牙利法的條件。

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

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

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

當(dāng)m>n時，可設(shè)“虛工作人員”，虛工作人員從事各項任務(wù)的效率為0，分配給虛擬人的工作實際上無法安排；當(dāng)m<n時，可設(shè)“虛工作”，各工作人員從事虛工作的效率為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)化矩陣表(二)人員任務(wù)EJGR甲215134乙1041415丙9141613虛工作人員0000人員任務(wù)EJG虛工作甲215130乙104140丙914160丁78110（3）不平衡指派問題的擴(kuò)展

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

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

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

按照圖3.9設(shè)置完參數(shù)后，點擊“求解”，則可以得到指派問題的最優(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ù)期將有需求增長，該公司計劃在D2、D3、D4、D5中的一個或多個城市建新工廠以增加生產(chǎn)能力。根據(jù)調(diào)查，被提議的四個城市中建立工廠的固定成本和年生產(chǎn)能力如表3.8所示。該公司對3個地區(qū)分銷中心的年需求量做了如下預(yù)測，見表3.9：表3.8各城市建立工廠的固定成本和年生產(chǎn)能力表表3.9各分銷中心的年需求量預(yù)測目標(biāo)工廠固定成本/萬元年生產(chǎn)能力/萬件D217.510D330.020D437.5030D550.040分銷中心年需求量/萬件M130M220M320根據(jù)估計，每件產(chǎn)品從每個工廠到各分銷中心的運(yùn)費（萬元）見表3.10：請問：公司是否需要在四個地區(qū)中建廠，若建廠，各工廠到各分銷中心如何配送調(diào)運(yùn)？表3.10每件產(chǎn)品從每個工廠到各分銷中心的運(yùn)費目標(biāo)工廠分銷中心M1M2M3D1523D2434D3975D41042D5843解：

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

設(shè)

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

，

表示從工廠i

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

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

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

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

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

，

，即該公司應(yīng)當(dāng)投資第2、5、7、10個項目，實際總投資為910萬元，五年后回報總額為170.9萬元。案例分析4（值班人員安排問題）某部門計劃購買一臺設(shè)備，并需要人員進(jìn)行設(shè)備的監(jiān)測工作。目前部門有四名工人和兩名工程師可勝任該工作，但由于他們目前已承擔(dān)其他工作，因此只能通過加班來安排他們的監(jiān)測任務(wù)。關(guān)于設(shè)備，計劃在周一到周五的上午8點至晚上10點期間運(yùn)行，并且只需要一名人員值班。要求每名工人每周值班不少于8小時，工程師不少于7小時，每次值班不少于2小時，每天安排值班的人不超過三人，并且必須有一名工程師，由于工作強(qiáng)度的原因，每人每周值班不能超過三次。每人每天可以安排的值班時間和加班工資如表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小時，并不能超過當(dāng)天值班人員的可安排時間（2）工人每周值班不少于8小時（4）設(shè)備每天運(yùn)行時間從上午8點至晚上10點，共14小時（3）工程師每周值班不少7小時（5）每人每周值班不超過3次（6）每天值班不超過3人變量非負(fù)約束（7）每天至少有一名工程師值班目標(biāo)函數(shù)為總支付工資最少：因此，該問題的線性規(guī)劃問題為利用Excel求解可以得到值班安排表3.14最低運(yùn)行該設(shè)備所需的工資為1373