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

第四章整數(shù)規(guī)劃(IntegerProgramming，IP)

在線(xiàn)性規(guī)劃問(wèn)題的求解過(guò)程中，最優(yōu)解可能是整數(shù)，也可能不是整數(shù)。在一些情況下，某些實(shí)際問(wèn)題要求最優(yōu)解必須是整數(shù)，例如，若所求得的解是安排上班的人數(shù)，需要采購(gòu)的機(jī)器臺(tái)數(shù)等。用前面介紹的線(xiàn)性規(guī)劃方法求解時(shí)，不一定能得到整數(shù)解。為解決這一類(lèi)變量為整數(shù)的實(shí)際問(wèn)題，出現(xiàn)了整數(shù)規(guī)劃模型。

在所建模型中，決策變量全為整數(shù)的問(wèn)題稱(chēng)為純整數(shù)規(guī)劃(PureIntegerProgramming)或全整數(shù)規(guī)劃(AllIntegerProgramming)；決策變量中部分為整數(shù)、部分為非整數(shù)的問(wèn)題稱(chēng)為混合整數(shù)規(guī)劃(MixedIntegerProgramming)；變量取值為0或1的問(wèn)題稱(chēng)為0-1整數(shù)規(guī)劃。

對(duì)于求整數(shù)解的線(xiàn)性規(guī)劃問(wèn)題，能否采用四舍五入或者去尾的方法將求得的非整數(shù)解加以解決呢？如果不能，有無(wú)有效的解決方案呢？4.1整數(shù)規(guī)劃的數(shù)學(xué)建模4.1.1裝箱問(wèn)題例4.1某廠(chǎng)擬用集裝箱托運(yùn)甲、乙兩種貨物，每箱的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如表4－1所示。問(wèn)兩種貨物各托運(yùn)多少箱，可使獲得利潤(rùn)為最大？表4－1貨物體積（米3/箱）重量（百公斤/箱）利潤(rùn)（百元/箱）甲5220乙4510托運(yùn)限制24米313百公斤解：設(shè)、分別為甲、乙兩種貨物的托運(yùn)箱數(shù)，則數(shù)學(xué)模型可以表示為：其中，目標(biāo)函數(shù)表示追尋最大的利潤(rùn)，約束條件分別表示裝箱的體積和重量限制，決策變量要求裝箱數(shù)必須為整數(shù)。例4.2某公司擬在市東、西、南三區(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)為最大？4.1.2工廠(chǎng)選址問(wèn)題解：設(shè)表示是否在位置i建立門(mén)市部，有

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

其中，目標(biāo)函數(shù)表示尋求獲利最大的設(shè)點(diǎn)方案，第一個(gè)約束條件表示投資總額限制，之后的三個(gè)約束條件分別表示在東、西和南區(qū)的設(shè)點(diǎn)數(shù)限制，決策變量取值0或1。4.1整數(shù)規(guī)劃的數(shù)學(xué)建模4.1.1裝箱問(wèn)題例4.1某廠(chǎng)擬用集裝箱托運(yùn)甲、乙兩種貨物，每箱的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如表4－1所示。問(wèn)兩種貨物各托運(yùn)多少箱，可使獲得利潤(rùn)為最大？表4－1貨物體積（米3/箱）重量（百公斤/箱）利潤(rùn)（百元/箱）甲5220乙4510托運(yùn)限制24米313百公斤解：設(shè)、分別為甲、乙兩種貨物的托運(yùn)箱數(shù)，則數(shù)學(xué)模型可以表示為：其中，目標(biāo)函數(shù)表示追尋最大的利潤(rùn)，約束條件分別表示裝箱的體積和重量限制，決策變量要求裝箱數(shù)必須為整數(shù)。能否采用四舍五入或者去尾法求得整數(shù)解？以例4.1的求解為例，先不考慮為整數(shù)的條件，采用單純形法求解該問(wèn)題，得到： 若對(duì)采用四舍五入法求解，則有，此解不是可行解；而去尾法得到，目標(biāo)函數(shù)，該解是否是最優(yōu)解呢？實(shí)際上，當(dāng)時(shí)，，表明，去尾法得到的解并非最優(yōu)解。

4.2整數(shù)規(guī)劃的求解算法【例】設(shè)整數(shù)規(guī)劃問(wèn)題如下首先不考慮整數(shù)約束，得到線(xiàn)性規(guī)劃問(wèn)題（一般稱(chēng)為松弛問(wèn)題）。用圖解法求出最優(yōu)解為：x1＝3/2,x2=10/3，且有Z=29/6 現(xiàn)求整數(shù)解(最優(yōu)解):如用舍入取整法可得到4個(gè)點(diǎn)即(1，3),(2，3),(1，4),(2，4)。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。x1x2⑴⑵33(3/2,10/3)其中(2,2),(3,1)點(diǎn)的目標(biāo)函數(shù)值最大，即為Z=4。整數(shù)規(guī)劃問(wèn)題的求解方法：分支定界法和割平面法假如放棄整數(shù)要求后，用單純形法求得最優(yōu)解，恰好滿(mǎn)足整數(shù)性要求，則此解也是原整數(shù)規(guī)劃的最優(yōu)解。4.2.1分支定界算法下面通過(guò)例子說(shuō)明分支定界方法的算法思想和步驟。例4.3對(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)題，即有（B）（A）問(wèn)題（A）和（B）的可行域中包含了原整數(shù)規(guī)劃問(wèn)題的所有整數(shù)可行解，而在中不可能存在整數(shù)可行解。分別求解這兩個(gè)線(xiàn)性規(guī)劃問(wèn)題，得到的解是：和變量仍不滿(mǎn)足整數(shù)的條件，對(duì)問(wèn)題（A），必有，將（A）增加約束條件，得到（A1）（A2）求解（A1），得到;求解（A2），得到。由于（A2）的最優(yōu)值小于（A1）的最優(yōu)值，原問(wèn)題的最優(yōu)值必大于等于340，盡管（A2）的解仍然不滿(mǎn)足整數(shù)條件，（A2）已無(wú)必要繼續(xù)分解。對(duì)（B），不滿(mǎn)足整數(shù)條件，必有，將這兩個(gè)約束條件分別加到（B）中，得到（B1）和（B2），求解得到：（B1）的最優(yōu)解為，（B2）無(wú)可行解。至此，原問(wèn)題的最優(yōu)解為：

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

無(wú)可行解圖4—1

將要求解的整數(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ù)”的約束條件），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ù)解：例：用分枝定界法求解解:先求對(duì)應(yīng)的松弛問(wèn)題（記為L(zhǎng)P0）用圖解法得到最優(yōu)解X＝(3.57,7.14),Z0=35.7,如下圖所示。1010松弛問(wèn)題LP0的最優(yōu)解X=(3.57,7.14),Z0=35.7x1x2oABC10x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8①②LP2:X=(4,6.5),Z2=35.510x1x2oABCLP1LP2134LP21:X=(4.33,6),Z21=35.33610x1x2oACLP1346LP211:X=(4,6),Z211=34LP212:X=(5,5),Z212=355LP212上述分枝過(guò)程可用下圖表示：LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x1≤3x1≥4LP21:X=(4.33,6)Z21=35.33x2≤6LP211:X=(4,6)Z211=34LP212:X=(5,5)Z212=35x1≤4x1≥5LP22無(wú)可行解x2≥7作業(yè)：課本P127T6（2）第三章案例分析1、6~10人一組，自由組合2、完成課本P100，案例3.5.13、建立線(xiàn)性問(wèn)題數(shù)學(xué)模型并利用軟件求解4、小組為單位上交word電子版求解結(jié)果5、文件中請(qǐng)注明每個(gè)人的分工情況4.2.2割平面方法割平面法的思想是，求解不含整數(shù)條件的線(xiàn)性規(guī)劃，然后不斷增加適當(dāng)?shù)木€(xiàn)性約束條件，割掉原可行域中不含整數(shù)可行解的一部分，最終得到一個(gè)具有整數(shù)坐標(biāo)的極點(diǎn)的可行域，而該極點(diǎn)恰好是原整數(shù)規(guī)劃問(wèn)題的最優(yōu)解。例4.4對(duì)如下整數(shù)規(guī)劃下面通過(guò)例子求解過(guò)程說(shuō)明割平面法的應(yīng)用步驟。步驟1：不考慮整數(shù)條件，引入松弛變量，化為標(biāo)準(zhǔn)形式，用單純形法求解得到：表4－23/410-1/41/47/4013/41/400-1/2-1/2最優(yōu)解為：。步驟2：

根據(jù)單純形表，可得將上式中-1/4寫(xiě)成整數(shù)和非負(fù)真分?jǐn)?shù)之和的形式，有變換成如下形式：該式中，由于為整數(shù)，為整數(shù)，必有，化簡(jiǎn)得：對(duì)，切割掉了非整數(shù)最優(yōu)解，但是并沒(méi)有切割掉整數(shù)解，因?yàn)橄鄳?yīng)的線(xiàn)性規(guī)劃任意整數(shù)可行解都滿(mǎn)足該條件，故稱(chēng)之為:“割平面”。引入松弛變量，得到:將此約束方程加到表4－2中，得到表4－3：表4－33/410-1/41/407/4013/41/40-300-3-1100-1/2-1/20由表4－3，可采用對(duì)偶單純形法進(jìn)行求解，得到表4－4：換出基變量的確定規(guī)則。一般單純形方法是以最大檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量作為換出基變量，然后將已得到的基變量的值與換入基變量所在的列的正分量相除，以最小比值對(duì)應(yīng)的基變量作為換出基變量。在對(duì)偶單純形求解時(shí)，以基變量的負(fù)值中最小的對(duì)應(yīng)的為換出基變量，將檢驗(yàn)數(shù)與換出基變量所在行的負(fù)分量相除，然后選取最小比值對(duì)應(yīng)的非基變量為換入基變量。表4－411001/31/12101001/41001-1-1/3000-1/3-1/6由表4－4，，滿(mǎn)足整數(shù)條件。將上述步驟歸納如下：步驟1：不考慮整數(shù)規(guī)劃中的整數(shù)條件，依據(jù)單純形法求解線(xiàn)性規(guī)劃。步驟2：尋求切割方程。若最優(yōu)解存在但不滿(mǎn)足整數(shù)條件，根據(jù)最優(yōu)單純形表中最優(yōu)解為分?jǐn)?shù)值的一個(gè)基變量，寫(xiě)成，其中，為基變量，為非基變量。將寫(xiě)成整數(shù)部分N與非負(fù)真分?jǐn)?shù)（）之和的形式，即

將該式代入得到：則有切割方程。步驟3：

將切割方程增加松弛變量，加入最優(yōu)單純形表進(jìn)行迭代計(jì)算。若所得到的解為非整數(shù)，則轉(zhuǎn)到步驟2繼續(xù)迭代，直到找到最優(yōu)的整數(shù)解。cj1100XBbx1x2x3x4X15/3101/3-1/3X25/20101/200-1/3-1/6以x1所在的行為源行，得到相應(yīng)割平面加入松弛變量用對(duì)偶單純形法求解cj3-1-100θXBbx1x2x3x4x5x15/3101/3-1/30x25/20101/20X5-2/300-1/3-2/3100-1/3-1/60cj3-1-100θXBbx1x2x3x4x5x12101/20-1/2x2201-1/403/4X41001/21-3/200-1/40-1/4增加約束條件后LP問(wèn)題的最優(yōu)解（2,2,0,1,0），因此原整數(shù)規(guī)劃問(wèn)題的最優(yōu)解為（2,2），其最優(yōu)值為Z=44.2.30-1規(guī)劃及隱枚舉法在實(shí)際建模過(guò)程中，經(jīng)常遇到要求模型解決“是、否”或者“有、無(wú)”等問(wèn)題，這類(lèi)問(wèn)題一般可以借助引入數(shù)值為0或者1的決策變量加以解決，例4.2就是此類(lèi)問(wèn)題，這類(lèi)問(wèn)題被稱(chēng)為0-1整數(shù)規(guī)劃。被引入的0-1決策變量一般定義為：下面舉例說(shuō)明求解0-1整數(shù)規(guī)劃的隱枚舉法。例4.5有0-1整數(shù)規(guī)劃問(wèn)題：解：采用試探的方法找到一個(gè)可行解，容易看出符合約束條件，目標(biāo)函數(shù)值。對(duì)于極大化問(wèn)題，應(yīng)有，于是增加一個(gè)約束條件：◎新增加的約束條件稱(chēng)為過(guò)濾條件。原問(wèn)題的線(xiàn)性約束條件就變成5個(gè)，3個(gè)變量共有個(gè)解，原來(lái)4個(gè)約束條件共需32次運(yùn)算，增加了過(guò)濾條件后，將5個(gè)約束條件按◎～（4）的順序排好（表4－5），點(diǎn)條件滿(mǎn)足條件?

是(√)否(×)z值◎①②③④(0，0，0)0×(0，0，1)5-1101√5(0，1，0)-2×(0，1，1)315×(1，0，0)31110√3(1，0，1)80211√8(1，1，0)1×(1，1，1)626×對(duì)每個(gè)解，依次代入約束條件左側(cè)，求出數(shù)值，看是否滿(mǎn)足不等式條件，如某一條件不適合，同行以下條件就不必再檢查，因而可以減少運(yùn)算次數(shù)。于是求得最優(yōu)解在計(jì)算過(guò)程中，若遇到z值已超過(guò)條件◎右邊的值，應(yīng)改變條件◎，使右邊為迄今為止的最大z，繼續(xù)檢查。例如，當(dāng)檢查點(diǎn)（0，0，1）時(shí)因z=5>3，所以應(yīng)將條件◎換成◎這種對(duì)過(guò)濾條件的改進(jìn)，可以減少計(jì)算量。用隱枚舉法求下列0－1整數(shù)規(guī)劃的最優(yōu)解【解】容易求得X＝(1,0,0)是一可行解，Z0＝6。加一個(gè)約束(0)由于3個(gè)變量每個(gè)變量取0或1，共有8種組合，用列表的方法檢驗(yàn)每種組合解是否可行解，滿(mǎn)足約束打上記號(hào)“√”，不滿(mǎn)足約束打上記號(hào)“×”，計(jì)算如表5－3所示。表5－3變量組合約束(0)約束(1)約束(2)約束(3)Z（0，0，0）

（0，0，1）

（0，1，0）

（0，1，1）

（1，0，0）（1，0，1）（1，1，0）

（1，1，1）

由表5－3知，X＝（1，0，1）是最優(yōu)解，最優(yōu)值Z＝9?！痢痢痢痢獭獭獭?√√√√9√√××√第四章案例分析1、6~10人一組，自由組合2、完成課本P122，案例4.3.13、建立線(xiàn)性問(wèn)題數(shù)學(xué)模型并利用軟件求解4、小組為單位上交word電子版求解結(jié)果5、文件中請(qǐng)注明每個(gè)人的分工情況作業(yè)教材P127第6題(2)。6、(2)解：求相應(yīng)的線(xiàn)性規(guī)劃（LP）得（LP）的最優(yōu)解首先注意其中一個(gè)非整數(shù)變量的解，如，在松弛問(wèn)題中的解，于是原問(wèn)題增加兩個(gè)約束條件將兩個(gè)約束分別并入原問(wèn)題的松弛問(wèn)題（LP）中，形成兩個(gè)分支，即后繼問(wèn)題（LP1）和(LP2)，這并不影響原問(wèn)題的可行域。解（LP1），得最優(yōu)解為再解（LP2），無(wú)最優(yōu)解。繼續(xù)對(duì)（LP1）進(jìn)行分解。對(duì)（LP1）增加兩個(gè)約束條件將兩個(gè)約束分別并入（LP1）中，形成兩個(gè)分支，即后繼問(wèn)題（LP11）和(LP12)，這并不影響（LP1）的可行域。解（LP11），得最優(yōu)解為再解（LP12），得最優(yōu)解為。繼續(xù)對(duì)（LP12）進(jìn)行分解。對(duì)（LP12）增加兩個(gè)約束條件將兩個(gè)約束分別并入（LP12）中，形成兩個(gè)分支，即后繼問(wèn)題（LP121）和（LP122），這并不影響（LP12）的可行域。解（LP121），得最優(yōu)解為再解（LP122），無(wú)最優(yōu)解。繼續(xù)對(duì)（LP121）進(jìn)行分解。對(duì)（LP121）增加兩個(gè)約束條件將兩個(gè)約束分別并入（LP121）中，形成兩個(gè)分支，即后繼問(wèn)題（LP1211）和（LP1212）。解（LP1211），得最優(yōu)解為。再解（LP1212），無(wú)最優(yōu)解。因此得原問(wèn)題的最優(yōu)解為在生活中經(jīng)常會(huì)遇到這樣的問(wèn)題：某單位需完成項(xiàng)任務(wù)，恰好有個(gè)人可承擔(dān)這些任務(wù)。每個(gè)人只做一項(xiàng)工作，同時(shí)，每項(xiàng)工作只由一個(gè)人完成。由于每人的專(zhuān)長(zhǎng)不同，各人完成任務(wù)所需的時(shí)間也不同。問(wèn)題是，應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成項(xiàng)任務(wù)的總時(shí)間最?。ɑ蛘呖傂首罡撸?？這類(lèi)問(wèn)題稱(chēng)為指派問(wèn)題或分配問(wèn)題（assignmentproblem）。

4.2.4指派問(wèn)題及匈牙利法例4.6有一份中文說(shuō)明書(shū)，需譯成英、日、德、俄四種文字，分別記作E、J、G、R?，F(xiàn)有甲乙丙丁四人。他們將中文說(shuō)明書(shū)翻譯成不同語(yǔ)種說(shuō)明書(shū)所需時(shí)間如表4－6所示。問(wèn)，若要求每一翻譯任務(wù)只分配給一人去完成，每一個(gè)人只接受一項(xiàng)任務(wù)，應(yīng)指派何人去完成何工作，使所需時(shí)間最少？表4－6任務(wù)人員EJGR甲215134乙1041415丙9141613丁78119一般地，稱(chēng)表4－6為效率矩陣或者系數(shù)矩陣，其元素表示指派第個(gè)人去完成第項(xiàng)任務(wù)所需的時(shí)間，或者稱(chēng)為完成任務(wù)的工作效率（或時(shí)間、成本等）。解：引入0-1變量，由此可得到指派問(wèn)題的數(shù)學(xué)模型：目標(biāo)函數(shù)表示個(gè)人完成任務(wù)所需的時(shí)間最少（或效率最高）；第一個(gè)約束條件說(shuō)明第項(xiàng)任務(wù)只能由1人去完成；第二個(gè)約束條件說(shuō)明第人只能完成1項(xiàng)任務(wù)。易得，上述問(wèn)題可行解可寫(xiě)成表格或矩陣形式，如例4.6的一個(gè)可行解矩陣是可以看出，解矩陣是各行和各列只能有一個(gè)元素是1，其他元素是0的n階方陣。回顧運(yùn)輸問(wèn)題的數(shù)學(xué)模型，運(yùn)輸問(wèn)題中若產(chǎn)量和銷(xiāo)量分別等于1，實(shí)際上所得到的數(shù)學(xué)模型與指派問(wèn)題相同，也即指派問(wèn)題是運(yùn)輸問(wèn)題的特例，因而可以用運(yùn)輸問(wèn)題的表上作業(yè)法求解。另外，指派問(wèn)題也是0－1規(guī)劃的特例。本節(jié)利用指派問(wèn)題的特點(diǎn)介紹一種更為簡(jiǎn)便的算法。指派問(wèn)題的最優(yōu)解有這樣的性質(zhì)：若從系數(shù)矩陣的某一行（列）各元素中分別減去該行（列）的最小元素，得到新矩陣，那么以為系數(shù)矩陣求得的最優(yōu)解和用原系數(shù)矩陣求得的最優(yōu)解相同。以例4.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ì)完成人的最佳選擇。

利用這個(gè)性質(zhì)，可使原系數(shù)矩陣變換為含有很多0元素的新系數(shù)矩陣，而最優(yōu)解保持不變。在系數(shù)矩陣中，一般稱(chēng)位于不同行不同列的0元素為獨(dú)立的0元素。若能在系數(shù)矩陣中找出個(gè)獨(dú)立的0元素，令解矩陣中對(duì)應(yīng)這個(gè)獨(dú)立的0元素的元素取值為1，其他元素取值為0，則將其代入目標(biāo)函數(shù)中得到的，它一定是最小，這就是以為系數(shù)矩陣的指派問(wèn)題的最優(yōu)解，也就得到了原問(wèn)題的最優(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ù)。下面用例4.6來(lái)說(shuō)明該方法的應(yīng)用步驟。第一步：使指派問(wèn)題的系數(shù)矩陣經(jīng)變換，在各行各列中都出現(xiàn)0元素。

（1）從系數(shù)矩陣的每行元素減去該行的最小元素；

（2）再?gòu)乃孟禂?shù)矩陣的每列元素中減去該列的最小元素。例4.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í)，就必須按一定的步驟去找，常用的步驟為：（1）從只有一個(gè)0元素的行（列）開(kāi)始，給這個(gè)0元素加圈，記作◎。這表示對(duì)這行所代表的人，只有一種任務(wù)可指派。然后劃去◎所在列（行）的其他0元素，記作。這表示這列所代表的任務(wù)已指派完，不必再考慮別人。（2）給只有一個(gè)0元素列（行）的0元素加圈，記作◎；然后劃去◎所在行的0元素，記作。（3）反復(fù)進(jìn)行（1），（2）兩步，直到所有0元素都被圈出和劃掉為止。（4）若仍有沒(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元素都已圈出和劃掉為止。（5）若◎元素的數(shù)目等于矩陣的階數(shù)，那么指派問(wèn)題的最優(yōu)解已得到。若，則轉(zhuǎn)入第三步。按步驟（1），先給加圈，然后給加圈，劃掉；按步驟（2），給加圈，劃掉，最后給加圈，得到由于，所以得最優(yōu)解為

（）這表示：指定甲譯出俄文，乙譯出日文，丙譯出英文，丁譯出德文，所需總時(shí)間最少

（小時(shí)）。例4.7求表4－7所示效率矩陣的指派問(wèn)題的最小解。表4－7任務(wù)人員ABCDE甲127979乙89666丙71712149丁15146610戊4107109解：按上述第一步，將這系數(shù)矩陣進(jìn)行變換。按第二步，得到：這里◎的個(gè)數(shù)，而；解題沒(méi)有完成，應(yīng)按以下步驟繼續(xù)進(jìn)行。第三步：作最少的直線(xiàn)覆蓋所有0元素，以確定該系數(shù)矩陣中能找到最多的獨(dú)立元素?cái)?shù)。為此按以下步驟進(jìn)行：（1）對(duì)沒(méi)有◎的行打√號(hào)；（2）對(duì)已打√號(hào)的行中所有含元素的列打√號(hào)；（3）再對(duì)打有√號(hào)的列中含◎元素的行打√號(hào)；（4）重復(fù)（2），（3）直到得不出新的打√號(hào)的行、列為止；（5）對(duì)沒(méi)有打√號(hào)的行畫(huà)一橫線(xiàn)，有打√號(hào)的列畫(huà)一縱線(xiàn)，這就得到覆蓋所有0元素的最少直線(xiàn)數(shù)。

令這直線(xiàn)數(shù)為。若，說(shuō)明必須再變換當(dāng)前的系數(shù)矩陣，才能找到個(gè)獨(dú)立的0元素，為此轉(zhuǎn)第四步：若，而，應(yīng)回到第二步（4），另行試探。在例4.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元素不變。這樣得到新系數(shù)矩陣（它的最優(yōu)解和原問(wèn)題相同）。若得到個(gè)獨(dú)立的0元素，則已得最優(yōu)解，否則回到第三步重復(fù)進(jìn)行。

它具有個(gè)獨(dú)立的0元素。這就得到了最優(yōu)解，相應(yīng)的解矩陣為：在沒(méi)有被覆蓋部分（第3、5行）中找出最小元素為2，然后在第3、5行各元素分別減2，給第一列各元素加2，得到新矩陣。按第二步，找出所有獨(dú)立的0元素，得到：由解矩陣得最優(yōu)指派方案：甲—B，乙—D，丙—E，丁—C，戊—A。本例還可以得到另一最優(yōu)指派方案：甲—B，乙—C，丙—E，丁—D，戊—A。所需總時(shí)間為。當(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ì)例4.6，若系數(shù)矩陣中各元素為翻譯人員從事某種語(yǔ)言翻譯工作后所得到的收益，要求一種指派，使翻譯人員的收益最大，即求可令，其中M是足夠大的常數(shù)（如選中最大元素為M），這時(shí)系數(shù)矩陣可變換為，這時(shí)，符合匈牙利法的條件。目標(biāo)函數(shù)經(jīng)變換后，即解

所得最小解就是原問(wèn)題最大解，因?yàn)椋阂驗(yàn)槌?shù)，所以當(dāng)取最小時(shí)，即為最大。（2）任務(wù)數(shù)與工作人員數(shù)不等。當(dāng)時(shí)，可設(shè)“虛工作人員”，虛工作人員從事各項(xiàng)任務(wù)的效率為0，分配給虛擬人的工作實(shí)際上無(wú)法安排；當(dāng)時(shí)，可設(shè)“虛工作”，各工作人員從事虛工作的效率為0，被指派做虛擬工作的人的狀態(tài)，實(shí)際是休息狀態(tài)。此時(shí)，即可將問(wèn)題得到轉(zhuǎn)化。若例4.6中，只有甲乙丙三個(gè)工作人員，則轉(zhuǎn)化的矩陣為表4－8；表4－8

任務(wù)人員EJGR甲215134乙1041415丙9141613“虛工作人員”0000表4-9：任務(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)從事?；诖?，可設(shè)“虛工作人員”，與（2）不同的是，該虛工作人員完成任務(wù)的時(shí)間花費(fèi)等于，各項(xiàng)任務(wù)中三人的最少花費(fèi)時(shí)間，該問(wèn)題即得到表4－10。用匈牙利法求解該問(wèn)題，若虛工作人員從事G工作，則表明，第四項(xiàng)工作由甲完成；若虛工作人員從事J工作，表明第四項(xiàng)工作由乙完成。

表4－10任務(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)時(shí)，將各人得到的賠償費(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”。4.3案例分析4.3.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的地區(qū)分銷(xiāo)中心。由于預(yù)期將有需求增長(zhǎng)，該公司計(jì)劃在D2，D3，D4，D5中的一個(gè)或多個(gè)城市建新工廠(chǎng)以增加生產(chǎn)能力，根據(jù)調(diào)查，被提議四個(gè)城市中建立工廠(chǎng)的固定成本和年生產(chǎn)能力如下表4－11所示：目標(biāo)工廠(chǎng)年固定成本（萬(wàn)元）年生產(chǎn)能力（萬(wàn)件）D117500010000D230000020000D337500030000D45000040000該公司對(duì)3個(gè)地區(qū)分銷(xiāo)中心的年需求量做了如下預(yù)測(cè)，見(jiàn)表4－12;根據(jù)估計(jì)，每件產(chǎn)品從每個(gè)工廠(chǎng)到各分銷(xiāo)中心的運(yùn)費(fèi)（萬(wàn)元）見(jiàn)表4－13：表4－12表4－13分銷(xiāo)中心年需求量（萬(wàn)件）M130000M220000M320000M1M2M3D1523D2434D3975D41042D5843請(qǐng)問(wèn)：公司是否需要在四個(gè)地區(qū)中建廠(chǎng)，若建廠(chǎng)后，分廠(chǎng)到各分銷(xiāo)中心如何配送調(diào)運(yùn)？解：引入0-1變量表示在Di處是否建立分廠(chǎng),設(shè)表示從每個(gè)分廠(chǎng)到分銷(xiāo)中心的運(yùn)輸量。年運(yùn)輸成本和經(jīng)營(yíng)新廠(chǎng)的固定成本之和為：

考慮被提議工廠(chǎng)的生產(chǎn)能力約束條件，以D1為例，有，其余類(lèi)似；考慮分銷(xiāo)中心的需求量約束條件，以M1為例，有，其余類(lèi)似。因此，有整數(shù)規(guī)劃模型：利用lingo求解得到：

結(jié)果表明，在Ｄ４處建立一個(gè)分廠(chǎng)，從Ｄ４處運(yùn)輸給Ｍ２的數(shù)量為２００００萬(wàn)件，運(yùn)給Ｍ３的數(shù)量為２００００萬(wàn)件。實(shí)際上，這一模型可以應(yīng)用于含有工廠(chǎng)和倉(cāng)庫(kù)間，工廠(chǎng)與零售店之間的直接運(yùn)輸和產(chǎn)品分配系統(tǒng)。利用０－１變量的性質(zhì)，還可以多種廠(chǎng)址的配置約束，比如，由于Ｄ１和Ｄ４兩地距離較近，公司不愿意同時(shí)在這兩地建廠(chǎng)等。4.3.2攝像機(jī)安裝優(yōu)化問(wèn)題某藝術(shù)館考慮安裝一個(gè)攝像安全系統(tǒng)以減少其保安費(fèi)用，圖4－2是該藝術(shù)館用以展覽的房間示意圖，房間的通道顯示為1－13。一家保安公司建議在一些通道安裝雙向攝像機(jī)，每架雙向攝像機(jī)都可以監(jiān)視到其兩側(cè)的房間，如，在通道4安裝攝像機(jī)，房間1和房間4就可以被監(jiān)視，在通道11處安裝攝像機(jī)，房間7和房間8就可以被監(jiān)視。管理部門(mén)決定不在入口處安裝攝像機(jī)，請(qǐng)給出雙向攝像機(jī)使用數(shù)量最少而能覆蓋所有8間房的攝像機(jī)安裝方案。若房間7的陳列品尤為重要，要求兩架攝像機(jī)監(jiān)視該房間，請(qǐng)給出雙向攝像機(jī)安裝的數(shù)量及位置。解：引入變量，若通道安裝雙向攝像機(jī)，則，否則。雙向攝像機(jī)的數(shù)量可表示為，目標(biāo)函數(shù)追求使用數(shù)量最少的雙向攝像機(jī)，則有。對(duì)房間1，通道1，4，6安裝雙向攝像機(jī)可以對(duì)該房間設(shè)施監(jiān)控，上述3個(gè)通道至少安裝1臺(tái)雙向攝像機(jī)，有；對(duì)房間2，有通道6，8，12可以對(duì)該房間實(shí)施監(jiān)控，則有；同理，對(duì)其它房間，有相應(yīng)得雙向攝像機(jī)設(shè)施監(jiān)控。由此，采用lingo7軟件計(jì)算得到：，。即在通道3，6，10，11處安裝雙向攝像機(jī)，共4架。若房間7需要兩架攝像機(jī)監(jiān)控，則上述約束條件中改成，模型中其它式子不變，計(jì)算得到：