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

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

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

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

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

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

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

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

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

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

10、，時， ，表明，表明，去尾法得到的解并非最優(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ī)劃問題如下設(shè)整數(shù)規(guī)劃問題如下 且且為為整整數(shù)數(shù)0,13651914max21212121xxxxxxxxZ首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱為松弛問首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱為松弛問題）。題）。 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個點即個點即(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)點的目標(biāo)函數(shù)值點的目標(biāo)函數(shù)值最大，即為最大，即為Z=4。 整數(shù)規(guī)劃問題的求解方法：整數(shù)規(guī)劃問題的求解方法： 分支定界法和割平面法分支定界法和割平面法4.2.14.2.1分支定界算法分支定界算法 下面通過例子說明分支定界方法的算法思想下面通過例子說明分支定界方法的算法思想和

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

13、154xx或（B B）121212112max4090975672070.4,0zxxxxxxs txx x121212112max4090975672070.5,0zxxxxxxs txx x（A A） 問題（問題（A A）和（）和（B B）的可行域中包含了原整數(shù)規(guī)）的可行域中包含了原整數(shù)規(guī)劃問題的所有整數(shù)可行解，而在劃問題的所有整數(shù)可行解，而在 中不可中不可能存在整數(shù)可行解。能存在整數(shù)可行解。145x 分別求解這兩個線性規(guī)劃問題，得到的解是：分別求解這兩個線性規(guī)劃問題，得到的解是： 和和 變量變量 仍不滿足整數(shù)的條件，對問題（仍不滿足整數(shù)的條件，對問題（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)值，原問題的最）的最優(yōu)值，原問題的最優(yōu)值必大于等于優(yōu)值必大于等于340340，盡管（，盡管（A2A2）

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

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

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

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

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

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

21、.7,如下圖所示。如下圖所示。1010108 . 02 . 121 xx255 . 2221 xx松弛問題松弛問題LP0的最優(yōu)解的最優(yōu)解X=(3.57,7.14),Z0=35.7x1x2oABC得得到到兩兩個個線線性性規(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ī)劃劃，顯顯然然及及進進行行分分枝枝，增增加加約約束束選選擇擇目目標(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ī)劃劃及及進進行行分分枝枝，增增加加約約束束，選選擇擇由由于于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無可行解無可行解x27作業(yè)：課本P127 T6（2）第三章第三章 案例分析案例分析 1、610人一組，自由組合人一組，自由組合 2、完成課本、完成課本P100，案例，案例3.5.1 3、建立線性問題數(shù)學(xué)模型并利用、建立線性問題數(shù)學(xué)模型并利用軟件求解軟件求解 4、小組為單位上交、小組為單位上交word電子版求電子版求解結(jié)果解結(jié)果 5、文件中請注明每個人的分工情、文件中請注明每個人的分工情況況 4.2.2割平面方法割平面方法 割平面法的思想是，求解不含整數(shù)條件的割平面法的思想

25、是，求解不含整數(shù)條件的線性規(guī)劃，然后不斷增加適當(dāng)?shù)木€性約束線性規(guī)劃，然后不斷增加適當(dāng)?shù)木€性約束條件，割掉原可行域中不含整數(shù)可行解的條件，割掉原可行域中不含整數(shù)可行解的一部分，最終得到一個具有整數(shù)坐標(biāo)的極一部分，最終得到一個具有整數(shù)坐標(biāo)的極點的可行域，而該極點恰好是原整數(shù)規(guī)劃點的可行域，而該極點恰好是原整數(shù)規(guī)劃問題的最優(yōu)解。問題的最優(yōu)解。例例4.4 4.4 對如下整數(shù)規(guī)劃對如下整數(shù)規(guī)劃1212121212max1.34,0,zxxxxstxxx xx x為整數(shù)下面通過例子求解過程說明割平面法的應(yīng)用步驟。下面通過例子求解過程說明割平面法的應(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寫成寫成整數(shù)和非負真分數(shù)整數(shù)和非負真分數(shù)之和的形之和的形式，有式，有 變換成如下形式：變換成如下形式： 該式中，由于該式中，由于 為整數(shù)，為整數(shù)， 為整數(shù)，為整

27、數(shù)，必有必有 ，化簡得：，化簡得：1341/41/43/4xxx13343/41/43/4xxxx13343/43/41/4xxxx13,xx343/ 41/ 4xx343/4 3/41/40 xx3433xx 對對 ，切割掉了非整數(shù)最，切割掉了非整數(shù)最優(yōu)解，但是并沒有切割掉整數(shù)解，因為相應(yīng)的優(yōu)解，但是并沒有切割掉整數(shù)解，因為相應(yīng)的線性規(guī)劃任意整數(shù)可行解都滿足該條件，故稱線性規(guī)劃任意整數(shù)可行解都滿足該條件，故稱之為之為:“:“割平面割平面” ” 。 引入松弛變量，得到引入松弛變量，得到: : 將此約束方程加到表將此約束方程加到表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，可采用，可采用對偶單純形法對偶單純形法進行求解，進行求解，得到表得到表4 44 4： 換出基變量的確定規(guī)則。換出基變量的確定規(guī)則。 一般單純形方法是以一般單純形方法是以最大檢驗數(shù)最大檢驗數(shù)對應(yīng)的非基變量對應(yīng)的非基變量作為作為換出換出基變量，然后將已得到的基變量的值與基變量，然后將已得到的基變量的值與

29、換入基變量所在的列的正分量相除，以最小比值換入基變量所在的列的正分量相除，以最小比值對應(yīng)的基變量作為換出基變量。對應(yīng)的基變量作為換出基變量。 在對偶單純形求解時，以在對偶單純形求解時，以基變量的負值中最小基變量的負值中最小的的對應(yīng)的為對應(yīng)的為換出換出基變量，將檢驗數(shù)與換出基變量所基變量，將檢驗數(shù)與換出基變量所在行的負分量相除，然后選取最小比值對應(yīng)的非在行的負分量相除，然后選取最小比值對應(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， ，滿足整數(shù)，滿足整數(shù)條件。條件。1231,1,1xxx將上述步驟歸納如下：將上述步驟歸納如下：步驟步驟1 1： 不考慮整數(shù)規(guī)劃中的整數(shù)條件，依據(jù)單純形不考慮整數(shù)規(guī)劃中的整數(shù)條件，依據(jù)單純形法求解線性規(guī)劃。法求解線性規(guī)劃。步驟步驟2 2： 尋求切割方程。若最優(yōu)解存在但不滿足整數(shù)尋求切割方程。若最優(yōu)解存在但不滿足整數(shù)條件，根據(jù)最優(yōu)單純形表中最優(yōu)解為分數(shù)值的一條件，根據(jù)最優(yōu)單純形表中最優(yōu)解為分數(shù)值的一個基變量，寫成個基變量，寫成 ，其中，其中， 為基變量，為基變量， 為非基變量。將為非基變量。將

31、寫成整數(shù)部寫成整數(shù)部分分N N與非負真分數(shù)與非負真分數(shù) （ ）之和的形式，即）之和的形式，即 iikkikxaxbixkx,ikiabif01if,iiiikikikbNf aNf 將該式代入得到：將該式代入得到：則有切割方程則有切割方程 。步驟步驟3 3： 將切割方程增加松弛變量，加入最優(yōu)單純將切割方程增加松弛變量，加入最優(yōu)單純形表進行迭代計算。若所得到的解為非整數(shù)，形表進行迭代計算。若所得到的解為非整數(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 加入松弛變量加入松弛變量 用對偶單純形法求解用對偶單純形法求解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問題的最優(yōu)解（問題的最優(yōu)解（2,2,0,1,0），），因此原整數(shù)規(guī)劃問題的最優(yōu)解為（因此原整數(shù)規(guī)劃問題的最優(yōu)解為（2,2），其最優(yōu)），其最優(yōu)值為值為Z=44.2.3 0-14.2.3 0-1規(guī)劃及隱枚舉法規(guī)劃及隱枚舉法 在實際建模過程中，經(jīng)常遇到要求模型解決在實際建模過程中，經(jīng)常遇到要求模型解決“是、否是、否”或者或者“有、無有、無”等問題，這類問題一等問題，這類問題一般可以借助引入數(shù)值為般可以借助引入數(shù)值為0 0或者或者1 1的決策變量加以解的決策變量加以解決，例決，例4.24.2就是此類問題，這類問題被稱為就是此類問題，這類問題被稱為0-10

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

35、于是增加一，于是增加一個約束條件：個約束條件： 新增加的約束條件稱為過濾條件。原問題的線新增加的約束條件稱為過濾條件。原問題的線性約束條件就變成性約束條件就變成5 5個，個，3 3個變量共有個變量共有 個解，個解，原來原來4 4個約束條件共需個約束條件共需3232次運算，增加了過濾條件次運算，增加了過濾條件后，將后，將5 5個約束條件按個約束條件按（4 4）的順序排好（表）的順序排好（表4 45 5），），123()(1,0,0)x ,x ,x3z 3z 1233253xxx328點點條件條件滿足條件滿足條件? ?是是()()否否( () )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 對每個解，依次代入約束條件左側(cè)，求出數(shù)對每個解，依次代入約束條件左側(cè)，求出數(shù)值，看是否滿足不等式條件，如某一條件不適合，值，看是否滿足不等式條件，如某一條件不適合，同行以下條件就不必再檢查，因而可以減少運算同行以下條件就不必再檢查，因而可以減少運算次數(shù)。于是求得最

37、優(yōu)解次數(shù)。于是求得最優(yōu)解 在計算過程中，若遇到在計算過程中，若遇到z z值已超過條件值已超過條件右右邊的值，應(yīng)改變條件邊的值，應(yīng)改變條件，使右邊為迄今為止的最，使右邊為迄今為止的最大大z z，繼續(xù)檢查。例如，當(dāng)檢查點（，繼續(xù)檢查。例如，當(dāng)檢查點（0 0，0 0，1 1）時）時因因z=53z=53，所以應(yīng)將條件，所以應(yīng)將條件換成換成 這種對過濾條件的改進，可以減少計算量。這種對過濾條件的改進，可以減少計算量。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。加一個約束。加一個約束6326321xxx (0)由于由于3個變量每個變量取個變量每個變量取0或或1，共有，共有8種組合，用列表的方法檢驗每種組合，用列表的方法檢驗每種組合解是否可行解，滿足約束打上記號種組合解是否可行解，滿足約束打上記號“”，不滿足約束打上記，不滿足約束打上記號號“ ”，計算如表，計算如表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、建立線性問題數(shù)學(xué)模型并利用、建立線性問題數(shù)學(xué)模型并利用軟件求解軟件求解 4、小組為單位上交、小組為單位上交word電子版求電子版求解結(jié)果解結(jié)果 5、文件中請注明每個人的分工情、文件中請注明每個人的分工情況況 作業(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 首先注意其中一個非整數(shù)變量的解，如首先注意其中一個非整數(shù)變量的解，如 ，在松弛問題中的解，于是原問題增加兩個在松弛問題中的解，于是原問題增加兩個約束條件約束條件2x22x32x將兩個約束分別并入原問題的松弛問題（將兩個約束分別并入原問題的松弛問題（LP）中，）中，形成兩個分支，即后繼問題（形成兩個分支，即后繼問題（LP1）和）和(LP2)，這并，這并不影響原問題的可行域。不影響原問題的可行域。 解（解（LP1），得最優(yōu)解為），得最優(yōu)解為3

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

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

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

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

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

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

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

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

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

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

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

52、。元素。 （1 1）從系數(shù)矩陣的每行元素減去該行的最小元素； （2 2）再從所得系數(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的計算結(jié)果為：的計算結(jié)果為：第二步：進行試指派，以尋求最優(yōu)解。第二步：進行試指派，以尋求最優(yōu)解。 經(jīng)第一步變換后，系數(shù)矩陣中每行每列都已有了0元素；但需找出n個獨立的0元素。若能找出，就以這些獨立0元素對應(yīng)解矩陣（ ）中的元素為1，其余為0，這就得

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

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

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

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

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

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

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

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