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

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

2、的實(shí)際問(wèn)題，出現(xiàn)了整數(shù)規(guī)劃模型。 在所建模型中，在所建模型中，決策變量決策變量全為整數(shù)全為整數(shù)的問(wèn)題稱(chēng)為的問(wèn)題稱(chēng)為純整數(shù)規(guī)劃純整數(shù)規(guī)劃( (Pure Integer Programming) )或或全整數(shù)規(guī)劃全整數(shù)規(guī)劃( (All Integer Programming) )；決策變量決策變量中部分為整數(shù)、部分為非整數(shù)中部分為整數(shù)、部分為非整數(shù)的問(wèn)題的問(wèn)題稱(chēng)為稱(chēng)為混合整數(shù)規(guī)劃混合整數(shù)規(guī)劃( (Mixed Integer Programming) )；變量取值為變量取值為0 0或或1 1的問(wèn)題稱(chēng)為的問(wèn)題稱(chēng)為0-10-1整數(shù)規(guī)劃。整數(shù)規(guī)劃。 對(duì)于求整數(shù)解的線性規(guī)劃問(wèn)題，能否對(duì)于求整數(shù)解的線性規(guī)劃問(wèn)

3、題，能否采用采用四舍五入或者去尾四舍五入或者去尾的方法將求得的非的方法將求得的非整數(shù)解加以解決呢？如果不能，有無(wú)有效整數(shù)解加以解決呢？如果不能，有無(wú)有效的解決方案呢？的解決方案呢？4.1 4.1 整數(shù)規(guī)劃的數(shù)學(xué)建模整數(shù)規(guī)劃的數(shù)學(xué)建模 4.1.1 4.1.1 裝箱問(wèn)題裝箱問(wèn)題 例例4.1 4.1 某廠擬用集裝箱托運(yùn)甲、乙兩種貨物，每箱某廠擬用集裝箱托運(yùn)甲、乙兩種貨物，每箱的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如表的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如表4 41 1所示。問(wèn)兩種貨物各托運(yùn)多少箱，可使獲得利潤(rùn)為最所示。問(wèn)兩種貨物各托運(yùn)多少箱，可使獲得利潤(rùn)為最大？大？表表 4 41 1貨物貨物體積（

4、米體積（米3 3/ /箱）箱）重量（百公斤重量（百公斤/ /箱）箱） 利潤(rùn)（百元利潤(rùn)（百元/ /箱）箱）甲甲5 52 22020乙乙4 45 51010托運(yùn)限制托運(yùn)限制2424米米3 31313百公斤百公斤解：解： 設(shè)設(shè) 、 分別為甲、乙兩種貨物的托運(yùn)箱分別為甲、乙兩種貨物的托運(yùn)箱數(shù)，則數(shù)學(xué)模型可以表示為：數(shù)，則數(shù)學(xué)模型可以表示為：其中，目標(biāo)函數(shù)表示追尋最大的利潤(rùn)，約束條件其中，目標(biāo)函數(shù)表示追尋最大的利潤(rùn)，約束條件分別表示裝箱的體積和重量限制，決策變量要求分別表示裝箱的體積和重量限制，決策變量要求裝箱數(shù)必須為整數(shù)。裝箱數(shù)必須為整數(shù)。1212121212max201054242513,0,zxx

5、xxxxxxxx整 數(shù)1x2x例例4.2 4.2 某公司擬在市東、西、南三區(qū)建立門(mén)市某公司擬在市東、西、南三區(qū)建立門(mén)市部，有部，有7 7個(gè)位置個(gè)位置 （ ）可供選擇，考慮）可供選擇，考慮到各地區(qū)居民消費(fèi)水平及居民居住密集度，公司到各地區(qū)居民消費(fèi)水平及居民居住密集度，公司制定了如下規(guī)定：制定了如下規(guī)定：在東區(qū)，由在東區(qū)，由 ， ， 三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)中至多選兩個(gè)；在西區(qū)，由在西區(qū)，由 ， 兩個(gè)點(diǎn)中至少選一個(gè)；兩個(gè)點(diǎn)中至少選一個(gè)；在南區(qū)，由在南區(qū)，由 ， 兩個(gè)點(diǎn)中至少選一個(gè)。兩個(gè)點(diǎn)中至少選一個(gè)。如選用點(diǎn)如選用點(diǎn) ，設(shè)備投資預(yù)計(jì)為，設(shè)備投資預(yù)計(jì)為 元，每年可獲利元，每年可獲利潤(rùn)預(yù)計(jì)為潤(rùn)預(yù)計(jì)為

6、 元，由于公司的投資能力及投資策略元，由于公司的投資能力及投資策略限制，要求投資總額不能超過(guò)限制，要求投資總額不能超過(guò)B B元。問(wèn)應(yīng)如何選元。問(wèn)應(yīng)如何選擇可使年利潤(rùn)為最大？擇可使年利潤(rùn)為最大？iA1,2,7i 1A2A3A4A5A6A7AiAibic4.1.2 4.1.2 工廠選址問(wèn)題工廠選址問(wèn)題解：設(shè)解：設(shè) 表示是否在位置表示是否在位置i i 建立門(mén)市建立門(mén)市部，有部，有 則可以建立如下的數(shù)學(xué)模型：則可以建立如下的數(shù)學(xué)模型：(1,2,7)iix10iiiAxA，當(dāng) 點(diǎn)被選用，當(dāng) 點(diǎn)沒(méi)被選用1,2,7i 71711234567m ax2.1101iiiiiiizc xBb xxxxs txxx

7、xx 或 其中，目標(biāo)函數(shù)表示其中，目標(biāo)函數(shù)表示尋求獲利最大的設(shè)點(diǎn)方案，尋求獲利最大的設(shè)點(diǎn)方案，第一個(gè)約束條件表示投資第一個(gè)約束條件表示投資總額限制，之后的三個(gè)約總額限制，之后的三個(gè)約束條件分別表示在東、西束條件分別表示在東、西和南區(qū)的設(shè)點(diǎn)數(shù)限制，決和南區(qū)的設(shè)點(diǎn)數(shù)限制，決策變量取值策變量取值0 0或或1 1。4.1 4.1 整數(shù)規(guī)劃的數(shù)學(xué)建模整數(shù)規(guī)劃的數(shù)學(xué)建模 4.1.1 4.1.1 裝箱問(wèn)題裝箱問(wèn)題 例例4.1 4.1 某廠擬用集裝箱托運(yùn)甲、乙兩種貨物，每箱某廠擬用集裝箱托運(yùn)甲、乙兩種貨物，每箱的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如表的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如表4 41 1所示

8、。問(wèn)兩種貨物各托運(yùn)多少箱，可使獲得利潤(rùn)為最所示。問(wèn)兩種貨物各托運(yùn)多少箱，可使獲得利潤(rùn)為最大？大？表表 4 41 1貨物貨物體積（米體積（米3 3/ /箱）箱）重量（百公斤重量（百公斤/ /箱）箱） 利潤(rùn)（百元利潤(rùn)（百元/ /箱）箱）甲甲5 52 22020乙乙4 45 51010托運(yùn)限制托運(yùn)限制2424米米3 31313百公斤百公斤解：解： 設(shè)設(shè) 、 分別為甲、乙兩種貨物的托運(yùn)箱分別為甲、乙兩種貨物的托運(yùn)箱數(shù)，則數(shù)學(xué)模型可以表示為：數(shù)，則數(shù)學(xué)模型可以表示為：其中，目標(biāo)函數(shù)表示追尋最大的利潤(rùn)，約束條件其中，目標(biāo)函數(shù)表示追尋最大的利潤(rùn)，約束條件分別表示裝箱的體積和重量限制，決策變量要求分別表示裝箱

9、的體積和重量限制，決策變量要求裝箱數(shù)必須為整數(shù)。裝箱數(shù)必須為整數(shù)。1212121212max201054242513,0,zxxxxxxxxxx整 數(shù)1x2x 能否采用四舍五入或者去尾法求得整數(shù)解？能否采用四舍五入或者去尾法求得整數(shù)解？ 以例以例4.14.1的求解為例，先不考慮的求解為例，先不考慮 為整數(shù)的條為整數(shù)的條件，采用單純形法求解該問(wèn)題，得到：件，采用單純形法求解該問(wèn)題，得到： 若對(duì)若對(duì) 采用四舍五入法求解，則有采用四舍五入法求解，則有 ，此解，此解不是可行解不是可行解； 而去尾法得到而去尾法得到 ，目標(biāo)函數(shù)，目標(biāo)函數(shù) ，該解是否是最優(yōu)解呢？實(shí)際上，當(dāng)該解是否是最優(yōu)解呢？實(shí)際上，當(dāng) 時(shí)

10、，時(shí)， ，表明，表明，去尾法得到的解并非最優(yōu)解去尾法得到的解并非最優(yōu)解。 4.2 4.2 整數(shù)規(guī)劃的求解算法整數(shù)規(guī)劃的求解算法12,x x124.8,0,96xxz12,xx125,0 xx124,0 xx80z 124,1xx90z 【例】【例】 設(shè)整數(shù)規(guī)劃問(wèn)題如下設(shè)整數(shù)規(guī)劃問(wèn)題如下 且且為為整整數(shù)數(shù)0,13651914max21212121xxxxxxxxZ首先不考慮整數(shù)約束，得到線性規(guī)劃問(wèn)題（一般稱(chēng)為松弛問(wèn)首先不考慮整數(shù)約束，得到線性規(guī)劃問(wèn)題（一般稱(chēng)為松弛問(wèn)題）。題）。 0,13651914max21212121xxxxxxxxZ 用圖解法求出最優(yōu)解為：用圖解法求出最優(yōu)解為：x13/2,

11、 x2 = 10/3，且，且有有Z = 29/6現(xiàn)求整數(shù)解現(xiàn)求整數(shù)解(最優(yōu)解最優(yōu)解):如用如用舍入取整法可得到舍入取整法可得到4個(gè)點(diǎn)即個(gè)點(diǎn)即(1，3),(2，3),(1，4),(2，4)。顯然，。顯然，它們都不可能是整數(shù)規(guī)劃的它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。最優(yōu)解。x1x233(3/2,10/3)其中其中(2,2),(3,1)點(diǎn)的目標(biāo)函數(shù)值點(diǎn)的目標(biāo)函數(shù)值最大，即為最大，即為Z=4。 整數(shù)規(guī)劃問(wèn)題的求解方法：整數(shù)規(guī)劃問(wèn)題的求解方法： 分支定界法和割平面法分支定界法和割平面法4.2.14.2.1分支定界算法分支定界算法 下面通過(guò)例子說(shuō)明分支定界方法的算法思想下面通過(guò)例子說(shuō)明分支定界方法的算法思想和

12、步驟。和步驟。例例4.3 4.3 對(duì)如下整數(shù)規(guī)劃對(duì)如下整數(shù)規(guī)劃1212121212max4090975672070.,0,zxxxxxxs txxxx整數(shù)解：先不考慮整數(shù)條件，解相應(yīng)的線性規(guī)劃，解：先不考慮整數(shù)條件，解相應(yīng)的線性規(guī)劃，得最優(yōu)解：得最優(yōu)解： 。該解不。該解不符合整數(shù)條件。符合整數(shù)條件。 對(duì)其中一個(gè)非整數(shù)變量解，如對(duì)其中一個(gè)非整數(shù)變量解，如 ，顯，顯然，若要滿(mǎn)足整數(shù)條件，必定有然，若要滿(mǎn)足整數(shù)條件，必定有 于是，對(duì)原問(wèn)題增加兩個(gè)新約束條件，將原于是，對(duì)原問(wèn)題增加兩個(gè)新約束條件，將原問(wèn)題分為兩個(gè)子問(wèn)題，即有問(wèn)題分為兩個(gè)子問(wèn)題，即有14.81x 1204.81=1.82356xxz，1

13、154xx或（B B）121212112max4090975672070.4,0zxxxxxxs txx x121212112max4090975672070.5,0zxxxxxxs txx x（A A） 問(wèn)題（問(wèn)題（A A）和（）和（B B）的可行域中包含了原整數(shù)規(guī)）的可行域中包含了原整數(shù)規(guī)劃問(wèn)題的所有整數(shù)可行解，而在劃問(wèn)題的所有整數(shù)可行解，而在 中不可中不可能存在整數(shù)可行解。能存在整數(shù)可行解。145x 分別求解這兩個(gè)線性規(guī)劃問(wèn)題，得到的解是：分別求解這兩個(gè)線性規(guī)劃問(wèn)題，得到的解是： 和和 變量變量 仍不滿(mǎn)足整數(shù)的條件，對(duì)問(wèn)題（仍不滿(mǎn)足整數(shù)的條件，對(duì)問(wèn)題（A A），），必有必有 ，將（，將（

14、A A）增加約束條件，得到）增加約束條件，得到 124,2.1,349xxz125,1.57,341xxz1212121212m a x4 09 0975 672 07 0.42,0zxxxxxxs txxxx1212121212m ax4090975672070.43,0zxxxxxxs txxxx2x2232xx或（A1A1）（A2A2） 求解（求解（A1A1），得到），得到 ; ;求解（求解（A2A2），得到），得到 。由于。由于（A2A2）的最優(yōu)值小于（）的最優(yōu)值小于（A1A1）的最優(yōu)值，原問(wèn)題的最）的最優(yōu)值，原問(wèn)題的最優(yōu)值必大于等于優(yōu)值必大于等于340340，盡管（，盡管（A2A2）

15、的解仍然不滿(mǎn)足）的解仍然不滿(mǎn)足整數(shù)條件，（整數(shù)條件，（A2A2）已無(wú)必要繼續(xù)分解。）已無(wú)必要繼續(xù)分解。124,2,340 xxz121.42,3,327xxz2x22xx2或1125.44,1,308xxz 對(duì)（對(duì)（B B），）， 不滿(mǎn)足整數(shù)條件，必有不滿(mǎn)足整數(shù)條件，必有 ，將這兩個(gè)約束條件分別加到（，將這兩個(gè)約束條件分別加到（B B）中，得到（中，得到（B1B1）和（）和（B2B2），求解得到：（），求解得到：（B1B1）的）的最優(yōu)解為最優(yōu)解為 ，（，（B2B2）無(wú)可行）無(wú)可行解。至此，原問(wèn)題的最優(yōu)解為解。至此，原問(wèn)題的最優(yōu)解為： 上述求解過(guò)程稱(chēng)為分支定界算法，求解過(guò)程上述求解過(guò)程稱(chēng)為分支定

16、界算法，求解過(guò)程用圖用圖4 41 1表示：表示：124,2,340 xxz 無(wú)可行解無(wú)可行解圖41 123564.81,1.82zxx14x 15x 123494,2.1zxx123415,1.57zxx22x 23x 123404,2zxx123271.42,3zxx21x 22x123085.44,1zxx 將要求解的整數(shù)規(guī)劃問(wèn)題稱(chēng)為問(wèn)題將要求解的整數(shù)規(guī)劃問(wèn)題稱(chēng)為問(wèn)題A A，將與，將與之相應(yīng)的線性規(guī)劃問(wèn)題稱(chēng)為問(wèn)題之相應(yīng)的線性規(guī)劃問(wèn)題稱(chēng)為問(wèn)題B B（與問(wèn)題（與問(wèn)題A A 相相比較，僅不含有比較，僅不含有“變量為整數(shù)變量為整數(shù)”的約束條件），的約束條件），B B稱(chēng)為原問(wèn)題稱(chēng)為原問(wèn)題A A 的松

17、弛問(wèn)題。解問(wèn)題的松弛問(wèn)題。解問(wèn)題B B，可能得到，可能得到以下情況之一：以下情況之一： B B 沒(méi)有可行解，這時(shí)沒(méi)有可行解，這時(shí)A A 也沒(méi)有可行解，則也沒(méi)有可行解，則停止。停止。 B B 有最優(yōu)解，并符合問(wèn)題有最優(yōu)解，并符合問(wèn)題A A的整數(shù)條件，的整數(shù)條件，B B的最優(yōu)解即為的最優(yōu)解即為A A的最優(yōu)解，則停止。的最優(yōu)解，則停止。 B B 有最優(yōu)解，并不符合問(wèn)題有最優(yōu)解，并不符合問(wèn)題A A的整數(shù)條件，的整數(shù)條件，記它的目標(biāo)函數(shù)值為記它的目標(biāo)函數(shù)值為 。 0z 用觀察法找問(wèn)題用觀察法找問(wèn)題A A的一個(gè)整數(shù)可行解，一的一個(gè)整數(shù)可行解，一般可取般可取 試探，求試探，求得其目標(biāo)函數(shù)值，并記得其目標(biāo)函數(shù)

18、值，并記 。以。以 表示問(wèn)題表示問(wèn)題A A的最優(yōu)目標(biāo)函數(shù)值；這時(shí)有的最優(yōu)目標(biāo)函數(shù)值；這時(shí)有 ，然后按下述步驟進(jìn)行迭代。然后按下述步驟進(jìn)行迭代。0,1,jxjn z*z*0zzz 分支過(guò)程。在分支過(guò)程。在B B 的最優(yōu)解中任選一個(gè)不符的最優(yōu)解中任選一個(gè)不符合整數(shù)條件的變量合整數(shù)條件的變量 ，若其值為，若其值為 ，以，以 表示小于表示小于 的最大整數(shù)，構(gòu)造兩個(gè)約束條件的最大整數(shù)，構(gòu)造兩個(gè)約束條件： 。將這兩個(gè)約束條件，。將這兩個(gè)約束條件，分別加入問(wèn)題分別加入問(wèn)題B B ，得到后續(xù)規(guī)劃問(wèn)題，得到后續(xù)規(guī)劃問(wèn)題 。不考慮整數(shù)條件求解這兩個(gè)后續(xù)問(wèn)題。不考慮整數(shù)條件求解這兩個(gè)后續(xù)問(wèn)題。 定界過(guò)程。以每個(gè)后續(xù)

19、問(wèn)題為一分支標(biāo)明求定界過(guò)程。以每個(gè)后續(xù)問(wèn)題為一分支標(biāo)明求解的結(jié)果，在其他問(wèn)題解的結(jié)果中，找出最優(yōu)解的結(jié)果，在其他問(wèn)題解的結(jié)果中，找出最優(yōu)目標(biāo)函數(shù)值最大者作為新的上界目標(biāo)函數(shù)值最大者作為新的上界 。從已符合。從已符合整數(shù)條件的各分支中，找出目標(biāo)函數(shù)值最大者整數(shù)條件的各分支中，找出目標(biāo)函數(shù)值最大者作為新的下界作為新的下界 ，若無(wú)可行解，則，若無(wú)可行解，則 。jxjbjbjb1jjjjxbxb和12BB和zz0z 步驟步驟1 1：分支定界過(guò)程：分支定界過(guò)程步驟步驟2 2： 比較與剪支。各分支的最優(yōu)目標(biāo)函數(shù)中若比較與剪支。各分支的最優(yōu)目標(biāo)函數(shù)中若有小于有小于 者，則剪掉這支，以后不再考慮者，則剪掉這支

20、，以后不再考慮這個(gè)分支。若大于這個(gè)分支。若大于 ，且不符合整數(shù)條，且不符合整數(shù)條件，則重復(fù)步驟件，則重復(fù)步驟1 1，直到最后得到，直到最后得到 為止，得到最優(yōu)整數(shù)解：為止，得到最優(yōu)整數(shù)解：zz*zz*,1,jxjn。 例：例： 用分枝定界法求解用分枝定界法求解 且且均均取取整整數(shù)數(shù),0,255.22108.02.134max21212121xxxxxxxxZ解解: 先求對(duì)應(yīng)的松弛問(wèn)題（記為先求對(duì)應(yīng)的松弛問(wèn)題（記為L(zhǎng)P0）)(0,255 . 22108 . 02 . 134max021212121LPxxxxxxstxxZ 用圖解法得到最優(yōu)解用圖解法得到最優(yōu)解X(3.57,7.14),Z0=35

21、.7,如下圖所示。如下圖所示。1010108 . 02 . 121 xx255 . 2221 xx松弛問(wèn)題松弛問(wèn)題LP0的最優(yōu)解的最優(yōu)解X=(3.57,7.14),Z0=35.7x1x2oABC得得到到兩兩個(gè)個(gè)線線性性規(guī)規(guī)劃劃及及增增加加約約束束4311 xx10 x2oABC 0,3255 . 22108 . 02 . 1:134max211212121xxxxxxxLPxxZLP1LP234LP1:X=(3,7.6),Z1=34.8 0,4255 . 22108 . 02 . 1:234max211212121xxxxxxxLPxxZLP2:X=(4,6.5),Z2=35.510 x1x2

22、oABCLP1LP2134LP21:X=(4.33,6),Z21=35.33 0,64255 . 22108 . 02 . 1:2134max2121212121xxxxxxxxLPxxZ，不不可可行行，得得到到線線性性規(guī)規(guī)劃劃，顯顯然然及及進(jìn)進(jìn)行行分分枝枝，增增加加約約束束選選擇擇目目標(biāo)標(biāo)值值最最大大的的分分枝枝7762222 xxxLP6不可行72x 0,74255 . 22108 . 02 . 1:2234max2121212121xxxxxxxxLPxxZ，10 x1x2oACLP134可可行行域域是是一一條條線線段段即即，, 40,464255 . 22108 . 02 . 1:21

23、134max121121212121 xxxxxxxxxxLPxxZ：及及，得得線線性性規(guī)規(guī)劃劃及及進(jìn)進(jìn)行行分分枝枝，增增加加約約束束，選選擇擇由由于于212211542111121LPLPxxLPZZ 6 0,65255 . 22108 . 02 . 1:21234max2121212121xxxxxxxxLPxxZ，LP211:X=(4,6),Z211=34LP212:X=(5,5),Z212=355LP212LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6) Z1=34.8LP2:X=(4,6.5) Z2=35.5x13x14LP21:X=(4.33,6) Z2

24、1=35.33x26LP211:X=(4,6) Z211=34LP212:X=(5,5) Z212=35x14x15LP22無(wú)可行解無(wú)可行解x27作業(yè)：課本P127 T6（2）第三章第三章 案例分析案例分析 1、610人一組，自由組合人一組，自由組合 2、完成課本、完成課本P100，案例，案例3.5.1 3、建立線性問(wèn)題數(shù)學(xué)模型并利用、建立線性問(wèn)題數(shù)學(xué)模型并利用軟件求解軟件求解 4、小組為單位上交、小組為單位上交word電子版求電子版求解結(jié)果解結(jié)果 5、文件中請(qǐng)注明每個(gè)人的分工情、文件中請(qǐng)注明每個(gè)人的分工情況況 4.2.2割平面方法割平面方法 割平面法的思想是，求解不含整數(shù)條件的割平面法的思想

25、是，求解不含整數(shù)條件的線性規(guī)劃，然后不斷增加適當(dāng)?shù)木€性約束線性規(guī)劃，然后不斷增加適當(dāng)?shù)木€性約束條件，割掉原可行域中不含整數(shù)可行解的條件，割掉原可行域中不含整數(shù)可行解的一部分，最終得到一個(gè)具有整數(shù)坐標(biāo)的極一部分，最終得到一個(gè)具有整數(shù)坐標(biāo)的極點(diǎn)的可行域，而該極點(diǎn)恰好是原整數(shù)規(guī)劃點(diǎn)的可行域，而該極點(diǎn)恰好是原整數(shù)規(guī)劃問(wèn)題的最優(yōu)解。問(wèn)題的最優(yōu)解。例例4.4 4.4 對(duì)如下整數(shù)規(guī)劃對(duì)如下整數(shù)規(guī)劃1212121212max1.34,0,zxxxxstxxx xx x為整數(shù)下面通過(guò)例子求解過(guò)程說(shuō)明割平面法的應(yīng)用步驟。下面通過(guò)例子求解過(guò)程說(shuō)明割平面法的應(yīng)用步驟。步驟步驟1 1：不考慮整數(shù)條件，引入松弛變量不考慮

26、整數(shù)條件，引入松弛變量 ，化為標(biāo)準(zhǔn)形式，用單純形法求解得到：化為標(biāo)準(zhǔn)形式，用單純形法求解得到： 表表4 42 234,x x1x2x3/43/41 10 0-1/4-1/41/41/47/47/40 01 13/43/41/41/40 00 0-1/2-1/2-1/2-1/2最優(yōu)解為：最優(yōu)解為： 。Bxb3x4x1x2x123 / 4,7 / 4xx步驟步驟2 2： 根據(jù)單純形表，可得根據(jù)單純形表，可得 將上式中將上式中-1/4-1/4寫(xiě)成寫(xiě)成整數(shù)和非負(fù)真分?jǐn)?shù)整數(shù)和非負(fù)真分?jǐn)?shù)之和的形之和的形式，有式，有 變換成如下形式：變換成如下形式： 該式中，由于該式中，由于 為整數(shù)，為整數(shù)， 為整數(shù)，為整

27、數(shù)，必有必有 ，化簡(jiǎn)得：，化簡(jiǎn)得：1341/41/43/4xxx13343/41/43/4xxxx13343/43/41/4xxxx13,xx343/ 41/ 4xx343/4 3/41/40 xx3433xx 對(duì)對(duì) ，切割掉了非整數(shù)最，切割掉了非整數(shù)最優(yōu)解，但是并沒(méi)有切割掉整數(shù)解，因?yàn)橄鄳?yīng)的優(yōu)解，但是并沒(méi)有切割掉整數(shù)解，因?yàn)橄鄳?yīng)的線性規(guī)劃任意整數(shù)可行解都滿(mǎn)足該條件，故稱(chēng)線性規(guī)劃任意整數(shù)可行解都滿(mǎn)足該條件，故稱(chēng)之為之為:“:“割平面割平面” ” 。 引入松弛變量，得到引入松弛變量，得到: : 將此約束方程加到表將此約束方程加到表4 42 2中，得到表中，得到表4 43 3：3433xx3453

28、3xxx 表表4 43 3b1x2x3x4x5xBx1x2x5x3/43/41 10 0- -1/41/41/41/40 07/47/40 01 13/43/4 1/41/40 0-3-30 00 0-3-3-1-11 10 00 0- -1/21/2- -1/21/20 0 由表由表4 43 3，可采用，可采用對(duì)偶單純形法對(duì)偶單純形法進(jìn)行求解，進(jìn)行求解，得到表得到表4 44 4： 換出基變量的確定規(guī)則。換出基變量的確定規(guī)則。 一般單純形方法是以一般單純形方法是以最大檢驗(yàn)數(shù)最大檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量對(duì)應(yīng)的非基變量作為作為換出換出基變量，然后將已得到的基變量的值與基變量，然后將已得到的基變量的值與

29、換入基變量所在的列的正分量相除，以最小比值換入基變量所在的列的正分量相除，以最小比值對(duì)應(yīng)的基變量作為換出基變量。對(duì)應(yīng)的基變量作為換出基變量。 在對(duì)偶單純形求解時(shí)，以在對(duì)偶單純形求解時(shí)，以基變量的負(fù)值中最小基變量的負(fù)值中最小的的對(duì)應(yīng)的為對(duì)應(yīng)的為換出換出基變量，將檢驗(yàn)數(shù)與換出基變量所基變量，將檢驗(yàn)數(shù)與換出基變量所在行的負(fù)分量相除，然后選取最小比值對(duì)應(yīng)的非在行的負(fù)分量相除，然后選取最小比值對(duì)應(yīng)的非基變量為換入基變量?；兞繛閾Q入基變量。表表4 44 4b1x2x4x5xBx3x1x2x3x1 11 10 00 01/31/31/121/121 10 01 10 00 01/41/41 10 00 0

30、1 1-1-1-1/3-1/30 00 00 0-1/3-1/3-1/6-1/6由表由表4 44 4， ，滿(mǎn)足整數(shù)，滿(mǎn)足整數(shù)條件。條件。1231,1,1xxx將上述步驟歸納如下：將上述步驟歸納如下：步驟步驟1 1： 不考慮整數(shù)規(guī)劃中的整數(shù)條件，依據(jù)單純形不考慮整數(shù)規(guī)劃中的整數(shù)條件，依據(jù)單純形法求解線性規(guī)劃。法求解線性規(guī)劃。步驟步驟2 2： 尋求切割方程。若最優(yōu)解存在但不滿(mǎn)足整數(shù)尋求切割方程。若最優(yōu)解存在但不滿(mǎn)足整數(shù)條件，根據(jù)最優(yōu)單純形表中最優(yōu)解為分?jǐn)?shù)值的一條件，根據(jù)最優(yōu)單純形表中最優(yōu)解為分?jǐn)?shù)值的一個(gè)基變量，寫(xiě)成個(gè)基變量，寫(xiě)成 ，其中，其中， 為基變量，為基變量， 為非基變量。將為非基變量。將

31、寫(xiě)成整數(shù)部寫(xiě)成整數(shù)部分分N N與非負(fù)真分?jǐn)?shù)與非負(fù)真分?jǐn)?shù) （ ）之和的形式，即）之和的形式，即 iikkikxaxbixkx,ikiabif01if,iiiikikikbNf aNf 將該式代入得到：將該式代入得到：則有切割方程則有切割方程 。步驟步驟3 3： 將切割方程增加松弛變量，加入最優(yōu)單純將切割方程增加松弛變量，加入最優(yōu)單純形表進(jìn)行迭代計(jì)算。若所得到的解為非整數(shù)，形表進(jìn)行迭代計(jì)算。若所得到的解為非整數(shù)，則轉(zhuǎn)到步驟則轉(zhuǎn)到步驟2 2繼續(xù)迭代，直到找到最優(yōu)的整數(shù)繼續(xù)迭代，直到找到最優(yōu)的整數(shù)解。解。iikkiiikkkkxNxNffx0iikkkffx. .max21tsxxZ均為整數(shù)0,521

32、02321221xxxxxcj1100XBbx1x2x3x4X15/3101/3-1/3X25/20101/200-1/3-1/6以以x1所在的行為源行，得到相應(yīng)割平面所在的行為源行，得到相應(yīng)割平面03231-3243xx 加入松弛變量加入松弛變量 用對(duì)偶單純形法求解用對(duì)偶單純形法求解3232-31-543 xxxcj3-1-100XBbx1x2x3x4x5x15/3101/3-1/30 x25/20101/20X5-2/300-1/3-2/3100-1/3-1/60cj3-1-100XBbx1x2x3x4x5x12101/20-1/2x2201-1/403/4X41001/21-3/200-

33、1/40-1/4增加約束條件后增加約束條件后LP問(wèn)題的最優(yōu)解（問(wèn)題的最優(yōu)解（2,2,0,1,0），），因此原整數(shù)規(guī)劃問(wèn)題的最優(yōu)解為（因此原整數(shù)規(guī)劃問(wèn)題的最優(yōu)解為（2,2），其最優(yōu)），其最優(yōu)值為值為Z=44.2.3 0-14.2.3 0-1規(guī)劃及隱枚舉法規(guī)劃及隱枚舉法 在實(shí)際建模過(guò)程中，經(jīng)常遇到要求模型解決在實(shí)際建模過(guò)程中，經(jīng)常遇到要求模型解決“是、否是、否”或者或者“有、無(wú)有、無(wú)”等問(wèn)題，這類(lèi)問(wèn)題一等問(wèn)題，這類(lèi)問(wèn)題一般可以借助引入數(shù)值為般可以借助引入數(shù)值為0 0或者或者1 1的決策變量加以解的決策變量加以解決，例決，例4.24.2就是此類(lèi)問(wèn)題，這類(lèi)問(wèn)題被稱(chēng)為就是此類(lèi)問(wèn)題，這類(lèi)問(wèn)題被稱(chēng)為0-10

34、-1整整數(shù)規(guī)劃。被引入的數(shù)規(guī)劃。被引入的0-10-1決策變量一般定義為：決策變量一般定義為： 下面舉例說(shuō)明求解下面舉例說(shuō)明求解0-10-1整數(shù)規(guī)劃的隱枚舉法。整數(shù)規(guī)劃的隱枚舉法。1,0iixi執(zhí)行決策“是”，“有”，不執(zhí)行決策，“否”，“無(wú)”例例4.5 4.5 有有0-10-1整數(shù)規(guī)劃問(wèn)題：整數(shù)規(guī)劃問(wèn)題：1251231231213123max3252244.346,01zxxxxxxxxxstxxxxx x x或解：采用試探的方法找到一個(gè)可行解，容易看出解：采用試探的方法找到一個(gè)可行解，容易看出 符合約束條件，目標(biāo)函數(shù)符合約束條件，目標(biāo)函數(shù)值值 。 對(duì)于極大化問(wèn)題，應(yīng)有對(duì)于極大化問(wèn)題，應(yīng)有 ，

35、于是增加一，于是增加一個(gè)約束條件：個(gè)約束條件： 新增加的約束條件稱(chēng)為過(guò)濾條件。原問(wèn)題的線新增加的約束條件稱(chēng)為過(guò)濾條件。原問(wèn)題的線性約束條件就變成性約束條件就變成5 5個(gè)，個(gè)，3 3個(gè)變量共有個(gè)變量共有 個(gè)解，個(gè)解，原來(lái)原來(lái)4 4個(gè)約束條件共需個(gè)約束條件共需3232次運(yùn)算，增加了過(guò)濾條件次運(yùn)算，增加了過(guò)濾條件后，將后，將5 5個(gè)約束條件按個(gè)約束條件按（4 4）的順序排好（表）的順序排好（表4 45 5），），123()(1,0,0)x ,x ,x3z 3z 1233253xxx328點(diǎn)點(diǎn)條件條件滿(mǎn)足條件滿(mǎn)足條件? ?是是()()否否( () )z z值值(0(0，0 0，0)0)0 0(0(0，

36、0 0，1)1)5 5-1-11 10 01 15 5(0(0，1 1，0)0) -2-2(0(0，1 1，1)1)3 31 15 5(1(1，0 0，0)0)3 31 11 11 10 03 3(1(1，0 0，1)1)8 80 02 21 11 18 8(1(1，1 1，0)0)1 1(1(1，1 1，1)1)6 62 26 6 對(duì)每個(gè)解，依次代入約束條件左側(cè)，求出數(shù)對(duì)每個(gè)解，依次代入約束條件左側(cè)，求出數(shù)值，看是否滿(mǎn)足不等式條件，如某一條件不適合，值，看是否滿(mǎn)足不等式條件，如某一條件不適合，同行以下條件就不必再檢查，因而可以減少運(yùn)算同行以下條件就不必再檢查，因而可以減少運(yùn)算次數(shù)。于是求得最

37、優(yōu)解次數(shù)。于是求得最優(yōu)解 在計(jì)算過(guò)程中，若遇到在計(jì)算過(guò)程中，若遇到z z值已超過(guò)條件值已超過(guò)條件右右邊的值，應(yīng)改變條件邊的值，應(yīng)改變條件，使右邊為迄今為止的最，使右邊為迄今為止的最大大z z，繼續(xù)檢查。例如，當(dāng)檢查點(diǎn)（，繼續(xù)檢查。例如，當(dāng)檢查點(diǎn)（0 0，0 0，1 1）時(shí)）時(shí)因因z=53z=53，所以應(yīng)將條件，所以應(yīng)將條件換成換成 這種對(duì)過(guò)濾條件的改進(jìn)，可以減少計(jì)算量。這種對(duì)過(guò)濾條件的改進(jìn)，可以減少計(jì)算量。1233255xxx123(,)(0,1,0)xxxmax8z 用隱枚舉法求下列用隱枚舉法求下列01整數(shù)規(guī)劃的最優(yōu)解整數(shù)規(guī)劃的最優(yōu)解3 , 2 , 110)3(42)2(253) 1 (32

38、326max321321321321jxxxxxxxxxxxxxZj或【解】容易求得【解】容易求得X(1,0,0)是一可行解，是一可行解，Z06。加一個(gè)約束。加一個(gè)約束6326321xxx (0)由于由于3個(gè)變量每個(gè)變量取個(gè)變量每個(gè)變量取0或或1，共有，共有8種組合，用列表的方法檢驗(yàn)每種組合，用列表的方法檢驗(yàn)每種組合解是否可行解，滿(mǎn)足約束打上記號(hào)種組合解是否可行解，滿(mǎn)足約束打上記號(hào)“”，不滿(mǎn)足約束打上記，不滿(mǎn)足約束打上記號(hào)號(hào)“ ”，計(jì)算如表，計(jì)算如表53所示。所示。表53變量組合變量組合約束約束(0)約束約束(1)約束約束(2)約束約束(3)Z（0，0，0） （0，0，1） （0，1，0） （

39、0，1，1） （1，0，0）（1，0，1）（1，1，0） （1，1，1） 由表由表53知，知，X（1，0，1）是最優(yōu)解，最優(yōu)值）是最優(yōu)解，最優(yōu)值Z9。69第四章第四章 案例分析案例分析 1、610人一組，自由組合人一組，自由組合 2、完成課本、完成課本P122，案例，案例4.3.1 3、建立線性問(wèn)題數(shù)學(xué)模型并利用、建立線性問(wèn)題數(shù)學(xué)模型并利用軟件求解軟件求解 4、小組為單位上交、小組為單位上交word電子版求電子版求解結(jié)果解結(jié)果 5、文件中請(qǐng)注明每個(gè)人的分工情、文件中請(qǐng)注明每個(gè)人的分工情況況 作業(yè)作業(yè) 教材教材P127 第第6題題(2)。 6、(2) 解：求相應(yīng)的線性規(guī)劃（解：求相應(yīng)的線性規(guī)劃（

40、LP） 得（得（LP）的最優(yōu)解）的最優(yōu)解212maxxxz0,212605.21212121xxxxxxxxts75. 7,25. 2,75. 221zxx 首先注意其中一個(gè)非整數(shù)變量的解，如首先注意其中一個(gè)非整數(shù)變量的解，如 ，在松弛問(wèn)題中的解，于是原問(wèn)題增加兩個(gè)在松弛問(wèn)題中的解，于是原問(wèn)題增加兩個(gè)約束條件約束條件2x22x32x將兩個(gè)約束分別并入原問(wèn)題的松弛問(wèn)題（將兩個(gè)約束分別并入原問(wèn)題的松弛問(wèn)題（LP）中，）中，形成兩個(gè)分支，即后繼問(wèn)題（形成兩個(gè)分支，即后繼問(wèn)題（LP1）和）和(LP2)，這并，這并不影響原問(wèn)題的可行域。不影響原問(wèn)題的可行域。 解（解（LP1），得最優(yōu)解為），得最優(yōu)解為3

41、/23, 2, 6/1721zxx再解（再解（LP2），無(wú)最優(yōu)解。），無(wú)最優(yōu)解。 繼續(xù)對(duì)（繼續(xù)對(duì)（LP1）進(jìn)行分解。對(duì)（）進(jìn)行分解。對(duì)（LP1）增加）增加兩個(gè)約束條件兩個(gè)約束條件21x31x將兩個(gè)約束分別并入（將兩個(gè)約束分別并入（LP1）中，形成兩個(gè)分）中，形成兩個(gè)分支，即后繼問(wèn)題（支，即后繼問(wèn)題（LP11）和）和(LP12)，這并不影，這并不影響（響（LP1）的可行域。）的可行域。解（解（LP11），得最優(yōu)解為），得最優(yōu)解為6, 2, 221zxx再解（再解（LP12），得最優(yōu)解為。），得最優(yōu)解為。5 . 7, 5 . 1, 321zxx 繼續(xù)對(duì)（繼續(xù)對(duì)（LP12）進(jìn)行分解。對(duì)（）進(jìn)行分解。

42、對(duì)（LP12）增）增加兩個(gè)約束條件加兩個(gè)約束條件12x22x 將兩個(gè)約束分別并入（將兩個(gè)約束分別并入（LP12）中，形成兩）中，形成兩個(gè)分支，即后繼問(wèn)題（個(gè)分支，即后繼問(wèn)題（LP121）和）和（LP122），這并不影響（），這并不影響（LP12）的可行）的可行域。解（域。解（LP121），得最優(yōu)解為），得最優(yōu)解為7/22, 1, 6/1921zxx再解（再解（LP122），無(wú)最優(yōu)解。），無(wú)最優(yōu)解。繼續(xù)對(duì)（繼續(xù)對(duì)（LP121）進(jìn)行分解。對(duì)（）進(jìn)行分解。對(duì)（LP121）增加兩個(gè)約）增加兩個(gè)約束條件束條件31x41x將兩個(gè)約束分別并入（將兩個(gè)約束分別并入（LP121）中，形成兩個(gè)分支，即后）中，形成

43、兩個(gè)分支，即后繼問(wèn)題（繼問(wèn)題（LP1211）和（）和（LP1212）。）。解（解（LP1211），得最優(yōu)解為。），得最優(yōu)解為。7, 1, 321zxx再解（再解（LP1212），無(wú)最優(yōu)解。），無(wú)最優(yōu)解。因此得原問(wèn)題的最優(yōu)解為因此得原問(wèn)題的最優(yōu)解為 7, 1, 321zxx 在生活中經(jīng)常會(huì)遇到這樣的問(wèn)題：某單位需完在生活中經(jīng)常會(huì)遇到這樣的問(wèn)題：某單位需完成成 項(xiàng)任務(wù)，恰好有項(xiàng)任務(wù)，恰好有 個(gè)人可承擔(dān)這些任務(wù)。個(gè)人可承擔(dān)這些任務(wù)。每每個(gè)人只做一項(xiàng)工作，同時(shí)，每項(xiàng)工作只由一個(gè)人完成。個(gè)人只做一項(xiàng)工作，同時(shí)，每項(xiàng)工作只由一個(gè)人完成。由于每人的專(zhuān)長(zhǎng)不同，各人完成任務(wù)所需的時(shí)間由于每人的專(zhuān)長(zhǎng)不同，各人完成

44、任務(wù)所需的時(shí)間也不同。問(wèn)題是，應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，也不同。問(wèn)題是，應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成項(xiàng)任務(wù)的總時(shí)間最?。ɑ蛘呤雇瓿身?xiàng)任務(wù)的總時(shí)間最小（或者總效率最高總效率最高）？）？這類(lèi)問(wèn)題稱(chēng)為指派問(wèn)題或分配問(wèn)題（這類(lèi)問(wèn)題稱(chēng)為指派問(wèn)題或分配問(wèn)題（assignment problem）。）。 nn4.2.4 4.2.4 指派問(wèn)題及匈牙利法指派問(wèn)題及匈牙利法例例4.64.6有一份中文說(shuō)明書(shū)，需譯成英、日、有一份中文說(shuō)明書(shū)，需譯成英、日、德、俄四種文字，分別記作德、俄四種文字，分別記作E E、J J、G G、R R?，F(xiàn)?，F(xiàn)有甲乙丙丁四人。他們將中文說(shuō)明書(shū)翻譯成有甲乙丙丁四人。他們將中文說(shuō)明書(shū)

45、翻譯成不同語(yǔ)種說(shuō)明書(shū)所需時(shí)間如表不同語(yǔ)種說(shuō)明書(shū)所需時(shí)間如表4 46 6所示。問(wèn)，所示。問(wèn)，若要求每一翻譯任務(wù)只分配給一人去完成，若要求每一翻譯任務(wù)只分配給一人去完成，每一個(gè)人只接受一項(xiàng)任務(wù)，應(yīng)指派何人去完每一個(gè)人只接受一項(xiàng)任務(wù)，應(yīng)指派何人去完成何工作，使所需時(shí)間最少？成何工作，使所需時(shí)間最少？表表4 46 6 任務(wù)任務(wù)人員人員E EJ JG GR R甲甲2 2151513134 4乙乙10104 414141515丙丙9 9141416161313丁丁7 78 811119 9一般地，稱(chēng)表一般地，稱(chēng)表4 46 6為效率矩陣或者系數(shù)矩陣，為效率矩陣或者系數(shù)矩陣，其元素其元素 表示指派第表示指派第

46、 個(gè)人去完成第個(gè)人去完成第 項(xiàng)任務(wù)所需的時(shí)間，或者稱(chēng)項(xiàng)任務(wù)所需的時(shí)間，或者稱(chēng)為完成任務(wù)的工作效率（或時(shí)間、成本等）。為完成任務(wù)的工作效率（或時(shí)間、成本等）。0( ,1,2, )ijci jnij解：引入0-1變量 ， 由此可得到指派問(wèn)題的數(shù)學(xué)模型：ijx1,ijijxij指 派 第 人 去 完 成 第 項(xiàng) 任 務(wù)0 ,不 指 派 第 人 去 完 成 第 項(xiàng) 任 務(wù)m in1,1, 2,. .1,1, 2,10ijijijijiijjijzc xxjns txinx 或 目標(biāo)函數(shù)表示目標(biāo)函數(shù)表示 個(gè)人完成任務(wù)所需的時(shí)間最個(gè)人完成任務(wù)所需的時(shí)間最少（或效率最高）；第一個(gè)約束條件說(shuō)明第少（或效率最高

47、）；第一個(gè)約束條件說(shuō)明第 項(xiàng)任務(wù)只能由項(xiàng)任務(wù)只能由1 1人去完成；第二個(gè)約束條件說(shuō)明人去完成；第二個(gè)約束條件說(shuō)明第第 人只能完成人只能完成1 1項(xiàng)任務(wù)。項(xiàng)任務(wù)。易得，上述問(wèn)題可行解易得，上述問(wèn)題可行解 可寫(xiě)成表格或矩陣可寫(xiě)成表格或矩陣形式，如例形式，如例4.64.6的一個(gè)可行解矩陣是的一個(gè)可行解矩陣是njiijx0100001010000001ijx（） 可以看出，解矩陣可以看出，解矩陣 是各行和各列只能是各行和各列只能有一個(gè)元素是有一個(gè)元素是1 1，其他元素是，其他元素是0 0的的n n 階方陣。階方陣。 回顧運(yùn)輸問(wèn)題的數(shù)學(xué)模型，運(yùn)輸問(wèn)題中若回顧運(yùn)輸問(wèn)題的數(shù)學(xué)模型，運(yùn)輸問(wèn)題中若產(chǎn)量和銷(xiāo)量分別

48、等于產(chǎn)量和銷(xiāo)量分別等于1 1，實(shí)際上所得到的數(shù)學(xué)模，實(shí)際上所得到的數(shù)學(xué)模型與指派問(wèn)題相同，也即指派問(wèn)題是運(yùn)輸問(wèn)題型與指派問(wèn)題相同，也即指派問(wèn)題是運(yùn)輸問(wèn)題的特例，因而可以用運(yùn)輸問(wèn)題的表上作業(yè)法求的特例，因而可以用運(yùn)輸問(wèn)題的表上作業(yè)法求解。另外，指派問(wèn)題也是解。另外，指派問(wèn)題也是0 01 1規(guī)劃的特例。規(guī)劃的特例。 本節(jié)利用指派問(wèn)題的特點(diǎn)介紹一種更為簡(jiǎn)本節(jié)利用指派問(wèn)題的特點(diǎn)介紹一種更為簡(jiǎn)便的算法。便的算法。ijx（） 指派問(wèn)題的最優(yōu)解有這樣的性質(zhì)：若從系數(shù)指派問(wèn)題的最優(yōu)解有這樣的性質(zhì)：若從系數(shù)矩陣矩陣 的某一行（列）各元素中分別減去該的某一行（列）各元素中分別減去該行（列）的最小元素，得到新矩陣行

49、（列）的最小元素，得到新矩陣 ，那么，那么以以 為系數(shù)矩陣求得的最優(yōu)解和用原系數(shù)矩為系數(shù)矩陣求得的最優(yōu)解和用原系數(shù)矩陣求得的最優(yōu)解相同。陣求得的最優(yōu)解相同。 以例以例4.64.6來(lái)理解上述性質(zhì)，對(duì)甲來(lái)說(shuō)，只能來(lái)理解上述性質(zhì)，對(duì)甲來(lái)說(shuō)，只能完成一項(xiàng)任務(wù)，若其無(wú)論完成哪項(xiàng)任務(wù)都減少相完成一項(xiàng)任務(wù)，若其無(wú)論完成哪項(xiàng)任務(wù)都減少相同的時(shí)間，這種時(shí)間變動(dòng)并不改變甲在四項(xiàng)任務(wù)同的時(shí)間，這種時(shí)間變動(dòng)并不改變甲在四項(xiàng)任務(wù)中的最佳選擇；若完成某項(xiàng)任務(wù)的四個(gè)人都減少中的最佳選擇；若完成某項(xiàng)任務(wù)的四個(gè)人都減少相同的時(shí)間，同樣，這種時(shí)間的節(jié)省并不改變?nèi)蜗嗤臅r(shí)間，同樣，這種時(shí)間的節(jié)省并不改變?nèi)蝿?wù)對(duì)完成人的最佳選擇。務(wù)對(duì)

50、完成人的最佳選擇。 ijc（）ijb（）ijb（） 利用這個(gè)性質(zhì)，可使原系數(shù)矩陣變換為含利用這個(gè)性質(zhì)，可使原系數(shù)矩陣變換為含有很多有很多0 0元素的新系數(shù)矩陣，而最優(yōu)解保持不變。元素的新系數(shù)矩陣，而最優(yōu)解保持不變。在系數(shù)矩陣在系數(shù)矩陣 中，一般稱(chēng)位于不同行不同列中，一般稱(chēng)位于不同行不同列的的0 0元素為獨(dú)立的元素為獨(dú)立的0 0元素。若能在系數(shù)矩陣元素。若能在系數(shù)矩陣 中找出個(gè)獨(dú)立的中找出個(gè)獨(dú)立的0 0元素，令解矩陣元素，令解矩陣 中對(duì)應(yīng)中對(duì)應(yīng)這個(gè)獨(dú)立的這個(gè)獨(dú)立的0 0元素的元素取值為元素的元素取值為1 1，其他元素取，其他元素取值為值為0 0，則將其代入目標(biāo)函數(shù)中得到的，則將其代入目標(biāo)函數(shù)中得

51、到的 ，它一定是最小，這就是以它一定是最小，這就是以 為系數(shù)矩陣的指為系數(shù)矩陣的指派問(wèn)題的最優(yōu)解，也就得到了原問(wèn)題的最優(yōu)解。派問(wèn)題的最優(yōu)解，也就得到了原問(wèn)題的最優(yōu)解。ijb（）ijb（ ）ijb（）ijx（）0bz 1955年庫(kù)恩（W.W.Kuhn）利用匈牙利數(shù)學(xué)家康尼格（D.Konig）一個(gè)關(guān)于矩陣中0元素的定理，提出了指派問(wèn)題的解法，稱(chēng)為匈牙利法。該定理證明了以下結(jié)論：系數(shù)矩陣中獨(dú)立元素0元素的最多個(gè)數(shù)等于能覆蓋所有0元素的最小直線數(shù)。下面用例4.6來(lái)說(shuō)明該方法的應(yīng)用步驟。第一步：第一步：使指派問(wèn)題的系數(shù)矩陣經(jīng)變換，在各行使指派問(wèn)題的系數(shù)矩陣經(jīng)變換，在各行各列中都出現(xiàn)各列中都出現(xiàn)0 0元素

52、。元素。 （1 1）從系數(shù)矩陣的每行元素減去該行的最小元素； （2 2）再?gòu)乃孟禂?shù)矩陣的每列元素中減去該列的最小元素。min2 15 134 20 13 11 20 13 7 0104 14 15 460 10 11606 9( )( )9 14 16 13 90574053 278119 70142010 042minijijcb例例4.64.6的計(jì)算結(jié)果為：的計(jì)算結(jié)果為：第二步：進(jìn)行試指派，以尋求最優(yōu)解。第二步：進(jìn)行試指派，以尋求最優(yōu)解。 經(jīng)第一步變換后，系數(shù)矩陣中每行每列都已有了0元素；但需找出n個(gè)獨(dú)立的0元素。若能找出，就以這些獨(dú)立0元素對(duì)應(yīng)解矩陣（ ）中的元素為1，其余為0，這就得

53、到最優(yōu)解。當(dāng)n較小時(shí)，可用觀察法、試探法去找出n個(gè)獨(dú)立0元素。若n較大時(shí)，就必須按一定的步驟去找，常用的步驟為：（1 1）從只有一個(gè)0元素的行（列）開(kāi)始，給這個(gè)0元素加圈，記作。這表示對(duì)這行所代表的人，只有一種任務(wù)可指派。然后劃去所在列（行）的其他0元素，記作 。這表示這列所代表的任務(wù)已指派完，不必再考慮別人。ijx（2 2）給只有一個(gè)0元素列（行）的0元素加圈，記作；然后劃去所在行的0元素，記作 。（3 3）反復(fù)進(jìn)行（1），（2）兩步，直到所有0元 素都被圈出和劃掉為止。（4 4）若仍有沒(méi)有畫(huà)圈的0元素，且同行（列）的0元素至少有兩個(gè)（表示對(duì)這個(gè)可以從兩項(xiàng)任務(wù)中指派其一）。則從剩有0元素最少

54、的行（列）開(kāi)始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個(gè)0元素加圈（表示選擇性多的要“禮讓”選擇性少的）。然后劃掉同行同列的其他0元素?？煞磸?fù)進(jìn)行，直到所有0元素都已圈出和劃掉為止。（5 5）若元素的數(shù)目 等于矩陣的階數(shù) ，那么指派問(wèn)題的最優(yōu)解已得到。若 ，則轉(zhuǎn)入第三步。 按步驟（1），先給 加圈，然后給 加圈，劃掉 ；按步驟（2），給 加圈，劃掉 ，最后給 加圈，得到mnmn22b31b4111, bb43b44b14b 由于 ，所以得最優(yōu)解為 （ ） 這表示：指定甲譯出俄文，乙譯出日文，丙譯出英文，丁譯出德文，所需總時(shí)間最少 （小時(shí)）。4 nmijx010000010

55、01010000minijijijbxbz28min14432231ccccxczijijij例例4.7 4.7 求表47所示效率矩陣的指派問(wèn)題的最小解。表47 任務(wù)人員ABCDE甲127979乙89666丙71712149丁15146610戊4107109解：解：按上述第一步，將這系數(shù)矩陣進(jìn)行變換。 56360400892751000003220205467679107104106614159141217766698979712按第二步，得到： 這里的個(gè)數(shù) ，而 ；解題沒(méi)有完成，應(yīng)按以下步驟繼續(xù)進(jìn)行。 4m5n第三步：作最少的直線覆蓋所有第三步：作最少的直線覆蓋所有0 0元素，以確定元素，以

56、確定該系數(shù)矩陣中能找到最多的獨(dú)立元素?cái)?shù)。為此該系數(shù)矩陣中能找到最多的獨(dú)立元素?cái)?shù)。為此按以下步驟進(jìn)行：按以下步驟進(jìn)行：（1 1）對(duì)沒(méi)有）對(duì)沒(méi)有的行打的行打號(hào)；號(hào)；（2 2）對(duì)已打）對(duì)已打號(hào)的行中所有含號(hào)的行中所有含 元素的列打元素的列打號(hào)；號(hào)；（3 3）再對(duì)打有）再對(duì)打有號(hào)的列中含號(hào)的列中含元素的行打元素的行打號(hào)；號(hào)；（4 4）重復(fù)（）重復(fù)（2 2），（），（3 3）直到得不出新的打）直到得不出新的打號(hào)號(hào)的行、列為止；的行、列為止；（5 5）對(duì)沒(méi)有打）對(duì)沒(méi)有打號(hào)的行畫(huà)一橫線，有打號(hào)的行畫(huà)一橫線，有打號(hào)的號(hào)的列畫(huà)一縱線，這就得到覆蓋所有列畫(huà)一縱線，這就得到覆蓋所有0 0元素的最少直元素的最少直線數(shù)

57、。線數(shù)。 令這直線數(shù)為令這直線數(shù)為 。若。若 ，說(shuō)明必須再，說(shuō)明必須再變換當(dāng)前的系數(shù)矩陣，才能找到變換當(dāng)前的系數(shù)矩陣，才能找到 個(gè)獨(dú)立的個(gè)獨(dú)立的0 0元素，為此轉(zhuǎn)第四步：若元素，為此轉(zhuǎn)第四步：若 ，而，而 ，應(yīng)回到第二步（應(yīng)回到第二步（4 4），另行試探。），另行試探。 llnnnl mn 在例在例4.74.7中，對(duì)矩陣按以下次序進(jìn)行：中，對(duì)矩陣按以下次序進(jìn)行： 先在第五行旁打先在第五行旁打號(hào)，接著在第一列打號(hào)，接著在第一列打號(hào)，號(hào)，接著在第三列旁打接著在第三列旁打號(hào)。經(jīng)檢查不能再打號(hào)。經(jīng)檢查不能再打號(hào)了。號(hào)了。對(duì)沒(méi)有打?qū)](méi)有打行，畫(huà)一直線以覆蓋行，畫(huà)一直線以覆蓋0 0元素，已打元素，已打的列

58、畫(huà)一直線以覆蓋的列畫(huà)一直線以覆蓋0 0元素。得元素。得 由此可見(jiàn)由此可見(jiàn) 。所以應(yīng)繼續(xù)對(duì)矩陣。所以應(yīng)繼續(xù)對(duì)矩陣進(jìn)行變換，轉(zhuǎn)第四步。進(jìn)行變換，轉(zhuǎn)第四步。 第四步：該步進(jìn)行矩陣變換的目的是增加第四步：該步進(jìn)行矩陣變換的目的是增加0 0元素。在沒(méi)有被直線覆蓋的部分中找出最小元素。元素。在沒(méi)有被直線覆蓋的部分中找出最小元素。然后在打然后在打行各元素中都減去這最小元素，而在行各元素中都減去這最小元素，而在打打列的各元素都加上這最小元素，以保證原來(lái)列的各元素都加上這最小元素，以保證原來(lái)0 0元素不變。這樣得到新系數(shù)矩陣（它的最優(yōu)解元素不變。這樣得到新系數(shù)矩陣（它的最優(yōu)解和原問(wèn)題相同）。若得到個(gè)獨(dú)立的和原問(wèn)

59、題相同）。若得到個(gè)獨(dú)立的0 0元素，則已元素，則已得最優(yōu)解，否則回到第三步重復(fù)進(jìn)行。得最優(yōu)解，否則回到第三步重復(fù)進(jìn)行。 4ln34140400811053800003420207 它具有它具有 個(gè)獨(dú)立的個(gè)獨(dú)立的0 0元素。這就得到了最優(yōu)元素。這就得到了最優(yōu)解，相應(yīng)的解矩陣為解，相應(yīng)的解矩陣為：n 在沒(méi)有被覆蓋部分（第在沒(méi)有被覆蓋部分（第3 3、5 5行）中找出最小元行）中找出最小元素為素為2 2，然后在第，然后在第3 3、5 5行各元素分別減行各元素分別減2 2，給第一，給第一列各元素加列各元素加2 2，得到新矩陣。按第二步，找出所有，得到新矩陣。按第二步，找出所有獨(dú)立的獨(dú)立的0 0元素，得到

60、：元素，得到：0000100100100000100000010 由解矩陣得最優(yōu)指派方案：甲由解矩陣得最優(yōu)指派方案：甲BB，乙，乙DD，丙，丙EE，丁丁CC，戊，戊AA。本例還可以得到另一最優(yōu)指派方案：。本例還可以得到另一最優(yōu)指派方案：甲甲BB，乙，乙CC，丙，丙EE，丁，丁DD，戊，戊AA。所需總時(shí)間。所需總時(shí)間為為 。 當(dāng)指派問(wèn)題的系數(shù)矩陣，經(jīng)過(guò)變換得到了同行和同當(dāng)指派問(wèn)題的系數(shù)矩陣，經(jīng)過(guò)變換得到了同行和同列中都有兩個(gè)或兩個(gè)以上列中都有兩個(gè)或兩個(gè)以上0 0元素時(shí)，這時(shí)可以任選一行元素時(shí)，這時(shí)可以任選一行（列）中某一個(gè)（列）中某一個(gè)0 0元素，再劃去同行（列）的其他元素，再劃去同行（列）的其