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

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

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

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

對于求整數(shù)解的線性規(guī)劃問題，能否采用四舍五入或者去尾的方法將求得的非整數(shù)解加以解決呢？如果不能，有無有效的解決方案呢？4.1整數(shù)規(guī)劃的數(shù)學(xué)建模4.1.1裝箱問題例4.1某廠擬用集裝箱托運(yùn)甲、乙兩種貨物，每箱的體積、重量、可獲利潤以及托運(yùn)所受限制如表4－1所示。問兩種貨物各托運(yùn)多少箱，可使獲得利潤為最大？表4－1貨物體積（米3/箱）重量（百公斤/箱）利潤（百元/箱）甲5220乙4510托運(yùn)限制24米313百公斤解：設(shè)、分別為甲、乙兩種貨物的托運(yùn)箱數(shù)，則數(shù)學(xué)模型可以表示為：其中，目標(biāo)函數(shù)表示追尋最大的利潤，約束條件分別表示裝箱的體積和重量限制，決策變量要求裝箱數(shù)必須為整數(shù)。例4.2某公司擬在市東、西、南三區(qū)建立門市部，有7個位置（）可供選擇，考慮到各地區(qū)居民消費(fèi)水平及居民居住密集度，公司制定了如下規(guī)定：在東區(qū)，由，，三個點(diǎn)中至多選兩個；在西區(qū)，由，兩個點(diǎn)中至少選一個；在南區(qū)，由，兩個點(diǎn)中至少選一個。如選用點(diǎn)，設(shè)備投資預(yù)計(jì)為元，每年可獲利潤預(yù)計(jì)為元，由于公司的投資能力及投資策略限制，要求投資總額不能超過B元。問應(yīng)如何選擇可使年利潤為最大？4.1.2工廠選址問題解：設(shè)表示是否在位置i建立門市部，有

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

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

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

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

無可行解圖4—1

將要求解的整數(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ù)解：例：用分枝定界法求解解:先求對應(yīng)的松弛問題（記為LP0）用圖解法得到最優(yōu)解X＝(3.57,7.14),Z0=35.7,如下圖所示。1010松弛問題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上述分枝過程可用下圖表示：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無可行解x2≥7作業(yè)：課本P127T6（2）第三章案例分析1、6~10人一組，自由組合2、完成課本P100，案例3.5.13、建立線性問題數(shù)學(xué)模型并利用軟件求解4、小組為單位上交word電子版求解結(jié)果5、文件中請注明每個人的分工情況4.2.2割平面方法割平面法的思想是，求解不含整數(shù)條件的線性規(guī)劃，然后不斷增加適當(dāng)?shù)木€性約束條件，割掉原可行域中不含整數(shù)可行解的一部分，最終得到一個具有整數(shù)坐標(biāo)的極點(diǎn)的可行域，而該極點(diǎn)恰好是原整數(shù)規(guī)劃問題的最優(yōu)解。例4.4對如下整數(shù)規(guī)劃下面通過例子求解過程說明割平面法的應(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寫成整數(shù)和非負(fù)真分?jǐn)?shù)之和的形式，有變換成如下形式：該式中，由于為整數(shù)，為整數(shù)，必有，化簡得：對，切割掉了非整數(shù)最優(yōu)解，但是并沒有切割掉整數(shù)解，因?yàn)橄鄳?yīng)的線性規(guī)劃任意整數(shù)可行解都滿足該條件，故稱之為:“割平面”。引入松弛變量，得到:將此約束方程加到表4－2中，得到表4－3：表4－33/410-1/41/407/4013/41/40-300-3-1100-1/2-1/20由表4－3，可采用對偶單純形法進(jìn)行求解，得到表4－4：換出基變量的確定規(guī)則。一般單純形方法是以最大檢驗(yàn)數(shù)對應(yīng)的非基變量作為換出基變量，然后將已得到的基變量的值與換入基變量所在的列的正分量相除，以最小比值對應(yīng)的基變量作為換出基變量。在對偶單純形求解時，以基變量的負(fù)值中最小的對應(yīng)的為換出基變量，將檢驗(yàn)數(shù)與換出基變量所在行的負(fù)分量相除，然后選取最小比值對應(yīng)的非基變量為換入基變量。表4－411001/31/12101001/41001-1-1/3000-1/3-1/6由表4－4，，滿足整數(shù)條件。將上述步驟歸納如下：步驟1：不考慮整數(shù)規(guī)劃中的整數(shù)條件，依據(jù)單純形法求解線性規(guī)劃。步驟2：尋求切割方程。若最優(yōu)解存在但不滿足整數(shù)條件，根據(jù)最優(yōu)單純形表中最優(yōu)解為分?jǐn)?shù)值的一個基變量，寫成，其中，為基變量，為非基變量。將寫成整數(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)割平面加入松弛變量用對偶單純形法求解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問題的最優(yōu)解（2,2,0,1,0），因此原整數(shù)規(guī)劃問題的最優(yōu)解為（2,2），其最優(yōu)值為Z=44.2.30-1規(guī)劃及隱枚舉法在實(shí)際建模過程中，經(jīng)常遇到要求模型解決“是、否”或者“有、無”等問題，這類問題一般可以借助引入數(shù)值為0或者1的決策變量加以解決，例4.2就是此類問題，這類問題被稱為0-1整數(shù)規(guī)劃。被引入的0-1決策變量一般定義為：下面舉例說明求解0-1整數(shù)規(guī)劃的隱枚舉法。例4.5有0-1整數(shù)規(guī)劃問題：解：采用試探的方法找到一個可行解，容易看出符合約束條件，目標(biāo)函數(shù)值。對于極大化問題，應(yīng)有，于是增加一個約束條件：◎新增加的約束條件稱為過濾條件。原問題的線性約束條件就變成5個，3個變量共有個解，原來4個約束條件共需32次運(yùn)算，增加了過濾條件后，將5個約束條件按◎～（4）的順序排好（表4－5），點(diǎ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×對每個解，依次代入約束條件左側(cè)，求出數(shù)值，看是否滿足不等式條件，如某一條件不適合，同行以下條件就不必再檢查，因而可以減少運(yùn)算次數(shù)。于是求得最優(yōu)解在計(jì)算過程中，若遇到z值已超過條件◎右邊的值，應(yīng)改變條件◎，使右邊為迄今為止的最大z，繼續(xù)檢查。例如，當(dāng)檢查點(diǎn)（0，0，1）時因z=5>3，所以應(yīng)將條件◎換成◎這種對過濾條件的改進(jìn)，可以減少計(jì)算量。用隱枚舉法求下列0－1整數(shù)規(guī)劃的最優(yōu)解【解】容易求得X＝(1,0,0)是一可行解，Z0＝6。加一個約束(0)由于3個變量每個變量取0或1，共有8種組合，用列表的方法檢驗(yàn)每種組合解是否可行解，滿足約束打上記號“√”，不滿足約束打上記號“×”，計(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、建立線性問題數(shù)學(xué)模型并利用軟件求解4、小組為單位上交word電子版求解結(jié)果5、文件中請注明每個人的分工情況作業(yè)教材P127第6題(2)。6、(2)解：求相應(yīng)的線性規(guī)劃（LP）得（LP）的最優(yōu)解首先注意其中一個非整數(shù)變量的解，如，在松弛問題中的解，于是原問題增加兩個約束條件將兩個約束分別并入原問題的松弛問題（LP）中，形成兩個分支，即后繼問題（LP1）和(LP2)，這并不影響原問題的可行域。解（LP1），得最優(yōu)解為再解（LP2），無最優(yōu)解。繼續(xù)對（LP1）進(jìn)行分解。對（LP1）增加兩個約束條件將兩個約束分別并入（LP1）中，形成兩個分支，即后繼問題（LP11）和(LP12)，這并不影響（LP1）的可行域。解（LP11），得最優(yōu)解為再解（LP12），得最優(yōu)解為。繼續(xù)對（LP12）進(jìn)行分解。對（LP12）增加兩個約束條件將兩個約束分別并入（LP12）中，形成兩個分支，即后繼問題（LP121）和（LP122），這并不影響（LP12）的可行域。解（LP121），得最優(yōu)解為再解（LP122），無最優(yōu)解。繼續(xù)對（LP121）進(jìn)行分解。對（LP121）增加兩個約束條件將兩個約束分別并入（LP121）中，形成兩個分支，即后繼問題（LP1211）和（LP1212）。解（LP1211），得最優(yōu)解為。再解（LP1212），無最優(yōu)解。因此得原問題的最優(yōu)解為在生活中經(jīng)常會遇到這樣的問題：某單位需完成項(xiàng)任務(wù)，恰好有個人可承擔(dān)這些任務(wù)。每個人只做一項(xiàng)工作，同時，每項(xiàng)工作只由一個人完成。由于每人的專長不同，各人完成任務(wù)所需的時間也不同。問題是，應(yīng)指派哪個人去完成哪項(xiàng)任務(wù)，使完成項(xiàng)任務(wù)的總時間最?。ɑ蛘呖傂首罡撸窟@類問題稱為指派問題或分配問題（assignmentproblem）。

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

利用這個性質(zhì)，可使原系數(shù)矩陣變換為含有很多0元素的新系數(shù)矩陣，而最優(yōu)解保持不變。在系數(shù)矩陣中，一般稱位于不同行不同列的0元素為獨(dú)立的0元素。若能在系數(shù)矩陣中找出個獨(dú)立的0元素，令解矩陣中對應(yīng)這個獨(dú)立的0元素的元素取值為1，其他元素取值為0，則將其代入目標(biāo)函數(shù)中得到的，它一定是最小，這就是以為系數(shù)矩陣的指派問題的最優(yōu)解，也就得到了原問題的最優(yōu)解。1955年庫恩（W.W.Kuhn）利用匈牙利數(shù)學(xué)家康尼格（D.Konig）一個關(guān)于矩陣中0元素的定理，提出了指派問題的解法，稱為匈牙利法。該定理證明了以下結(jié)論：系數(shù)矩陣中獨(dú)立元素0元素的最多個數(shù)等于能覆蓋所有0元素的最小直線數(shù)。下面用例4.6來說明該方法的應(yīng)用步驟。第一步：使指派問題的系數(shù)矩陣經(jīng)變換，在各行各列中都出現(xiàn)0元素。

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

（2）再從所得系數(shù)矩陣的每列元素中減去該列的最小元素。例4.6的計(jì)算結(jié)果為：第二步：進(jìn)行試指派，以尋求最優(yōu)解。經(jīng)第一步變換后，系數(shù)矩陣中每行每列都已有了0元素；但需找出n個獨(dú)立的0元素。若能找出，就以這些獨(dú)立0元素對應(yīng)解矩陣（）中的元素為1，其余為0，這就得到最優(yōu)解。當(dāng)n較小時，可用觀察法、試探法去找出n個獨(dú)立0元素。若n較大時，就必須按一定的步驟去找，常用的步驟為：（1）從只有一個0元素的行（列）開始，給這個0元素加圈，記作◎。這表示對這行所代表的人，只有一種任務(wù)可指派。然后劃去◎所在列（行）的其他0元素，記作。這表示這列所代表的任務(wù)已指派完，不必再考慮別人。（2）給只有一個0元素列（行）的0元素加圈，記作◎；然后劃去◎所在行的0元素，記作。（3）反復(fù)進(jìn)行（1），（2）兩步，直到所有0元素都被圈出和劃掉為止。（4）若仍有沒有畫圈的0元素，且同行（列）的0元素至少有兩個（表示對這個可以從兩項(xiàng)任務(wù)中指派其一）。則從剩有0元素最少的行（列）開始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個0元素加圈（表示選擇性多的要“禮讓”選擇性少的）。然后劃掉同行同列的其他0元素。可反復(fù)進(jìn)行，直到所有0元素都已圈出和劃掉為止。（5）若◎元素的數(shù)目等于矩陣的階數(shù)，那么指派問題的最優(yōu)解已得到。若，則轉(zhuǎn)入第三步。按步驟（1），先給加圈，然后給加圈，劃掉；按步驟（2），給加圈，劃掉，最后給加圈，得到由于，所以得最優(yōu)解為

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

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

令這直線數(shù)為。若，說明必須再變換當(dāng)前的系數(shù)矩陣，才能找到個獨(dú)立的0元素，為此轉(zhuǎn)第四步：若，而，應(yīng)回到第二步（4），另行試探。在例4.7中，對矩陣按以下次序進(jìn)行：先在第五行旁打√號，接著在第一列打√號，接著在第三列旁打√號。經(jīng)檢查不能再打√號了。對沒有打√行，畫一直線以覆蓋0元素，已打√的列畫一直線以覆蓋0元素。得√√√由此可見。所以應(yīng)繼續(xù)對矩陣進(jìn)行變換，轉(zhuǎn)第四步。

第四步：該步進(jìn)行矩陣變換的目的是增加0元素。在沒有被直線覆蓋的部分中找出最小元素。然后在打√行各元素中都減去這最小元素，而在打√列的各元素都加上這最小元素，以保證原來0元素不變。這樣得到新系數(shù)矩陣（它的最優(yōu)解和原問題相同）。若得到個獨(dú)立的0元素，則已得最優(yōu)解，否則回到第三步重復(fù)進(jìn)行。

它具有個獨(dú)立的0元素。這就得到了最優(yōu)解，相應(yīng)的解矩陣為：在沒有被覆蓋部分（第3、5行）中找出最小元素為2，然后在第3、5行各元素分別減2，給第一列各元素加2，得到新矩陣。按第二步，找出所有獨(dú)立的0元素，得到：由解矩陣得最優(yōu)指派方案：甲—B，乙—D，丙—E，丁—C，戊—A。本例還可以得到另一最優(yōu)指派方案：甲—B，乙—C，丙—E，丁—D，戊—A。所需總時間為。當(dāng)指派問題的系數(shù)矩陣，經(jīng)過變換得到了同行和同列中都有兩個或兩個以上0元素時，這時可以任選一行（列）中某一個0元素，再劃去同行（列）的其他0元素。這時會出現(xiàn)多重解。下面討論幾種特殊的情況，經(jīng)過適當(dāng)變換后，即可以采用匈牙利法求解。（1）目標(biāo)函數(shù)求極大化的問題。對例4.6，若系數(shù)矩陣中各元素為翻譯人員從事某種語言翻譯工作后所得到的收益，要求一種指派，使翻譯人員的收益最大，即求可令，其中M是足夠大的常數(shù)（如選中最大元素為M），這時系數(shù)矩陣可變換為，這時，符合匈牙利法的條件。目標(biāo)函數(shù)經(jīng)變換后，即解

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

任務(wù)人員EJGR甲215134乙1041415丙9141613“虛工作人員”0000表4-9：任務(wù)人員EJG虛工作甲215130乙104140丙914160丁78110（3）不平衡指派問題的擴(kuò)展。三個工人從事四項(xiàng)工作，某一工人從事二項(xiàng)工作，求花費(fèi)時間最小的指派。先不考慮“某一工人從事二項(xiàng)工作”，則增加虛擬工作人員，得到最優(yōu)指派后，剩余工作必定由三人中完成該項(xiàng)任務(wù)花費(fèi)時間最少的來從事?；诖耍稍O(shè)“虛工作人員”，與（2）不同的是，該虛工作人員完成任務(wù)的時間花費(fèi)等于，各項(xiàng)任務(wù)中三人的最少花費(fèi)時間，該問題即得到表4－10。用匈牙利法求解該問題，若虛工作人員從事G工作，則表明，第四項(xiàng)工作由甲完成；若虛工作人員從事J工作，表明第四項(xiàng)工作由乙完成。

表4－10任務(wù)人員EJGR甲215134乙1041415丙9141613虛工作人員24134在不平衡指派問題中，在工人數(shù)大于工作數(shù)情況下，則增加虛工作：某人必須被指派工作。則該人從事虛工作的時間花費(fèi)為“M”，表示工作花費(fèi)時間無窮大，其余人從事該虛工作的時間花費(fèi)為0。工人不能得到指派時存在一定賠償損失費(fèi)時，將各人得到的賠償費(fèi)作為從事該虛工作的時間花費(fèi)。

當(dāng)工作數(shù)大于工人數(shù)時，則增加虛工作人員：若某項(xiàng)工作必須完成，則該虛工作人員從事必須完成工作的時間花費(fèi)為“M”，表示該項(xiàng)工作不得由虛工作人員從事，虛工作人員從事其它工作的時間花費(fèi)為0；若工作不能完成時存在懲罰損失費(fèi)時，則直接將懲罰費(fèi)作為虛工作人員從事各項(xiàng)工作的時間；若某人不能完成某項(xiàng)工作，則在系數(shù)矩陣中，相應(yīng)位置處填入“M”。4.3案例分析4.3.1分銷中心選址問題

A公司在D1處經(jīng)營一家年生產(chǎn)量為30萬件產(chǎn)品的工廠，產(chǎn)品被運(yùn)輸?shù)轿挥贛1、M2、M3的地區(qū)分銷中心。由于預(yù)期將有需求增長，該公司計(jì)劃在D2，D3，D4，D5中的一個或多個城市建新工廠以增加生產(chǎn)能力，根據(jù)調(diào)查，被提議四個城市中建立工廠的固定成本和年生產(chǎn)能力如下表4－11所示：目標(biāo)工廠年固定成本（萬元）年生產(chǎn)能力（萬件）D117500010000D230000020000D337500030000D45000040000該公司對3個地區(qū)分銷中心的年需求量做了如下預(yù)測，見表4－12;根據(jù)估計(jì)，每件產(chǎn)品從每個工廠到各分銷中心的運(yùn)費(fèi)（萬元）見表4－13：表4－12表4－13分銷中心年需求量（萬件）M130000M220000M320000M1M2M3D1523D2434D3975D41042D5843請問：公司是否需要在四個地區(qū)中建廠，若建廠后，分廠到各分銷中心如何配送調(diào)運(yùn)？解：引入0-1變量表示在Di處是否建立分廠,設(shè)表示從每個分廠到分銷中心的運(yùn)輸量。年運(yùn)輸成本和經(jīng)營新廠的固定成本之和為：

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

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