物流運(yùn)籌學(xué)課件4

1、郭淑紅郭淑紅guoshuhong_1307455345313074553453n例如，產(chǎn)品的件數(shù)、機(jī)器的臺(tái)數(shù)、裝貨的車(chē)數(shù)、完成工作的人數(shù)等，分?jǐn)?shù)或小數(shù)解顯然是不合理的。n全部決策變量的取值都為整數(shù)，則稱(chēng)為全整數(shù)規(guī)劃(All IP)n僅要求部分決策變量的取值為整數(shù)，則稱(chēng)為混合整數(shù)規(guī)劃(Mixed IP)n要求決策變量只取0或1值，則稱(chēng)0-1規(guī)劃(0-1 Programming) 整數(shù)線性規(guī)劃數(shù)學(xué)模型的一般形式：且部分或全部為整數(shù)或 n)1.2(j 0)2 . 1( )min(max11jnjijijnjjjxmibxaxcZZ人員安排規(guī)劃某服務(wù)部門(mén)各時(shí)段某服務(wù)部門(mén)各時(shí)段( (每每2 2小時(shí)為一時(shí)

2、段小時(shí)為一時(shí)段) )需要的服務(wù)人數(shù)如表：需要的服務(wù)人數(shù)如表：解：設(shè)第j 時(shí)段開(kāi)始時(shí)上班的服務(wù)員人數(shù)為xj 第 j 時(shí)段來(lái)上班的服務(wù)員將在第j+3 時(shí)段結(jié)束時(shí)下班，故決策變量有x1,x2,x3,x4,x5 。 二、二、0-10-1規(guī)劃規(guī)劃)2 , 1(01iyi若不建工廠若建工廠 )2 , 1(1 , 0)4 , 3 , 2 , 1,(0200200600400150300400350.15001200min244434241134333231242322211413121144342414433323134232221241312111414121iyjixyxxxxyxxxxxxxxxxxx

3、xxxxxxxxxxxxxxxxtsyyxcziijijijij混合整數(shù)規(guī)劃問(wèn)題混合整數(shù)規(guī)劃問(wèn)題且為整數(shù)0,13651914max21212121xxxxxxxxZ首先不考慮整數(shù)約束，得到線性規(guī)劃問(wèn)題（一般稱(chēng)為松弛問(wèn)題）。0,13651914max21212121xxxxxxxxZx x1 1x x2 23 33 3(3/2,10/3)(3/2,10/3)5x1 +7 x2 =352x1 + x2 =9x1x2123125344)972,913(分支定界法分支定界法 LandDoig和和Dakin于于60年代提出年代提出一種隱枚舉法,用來(lái)解純整數(shù)規(guī)劃及混合整數(shù)規(guī)劃純整數(shù)規(guī)劃及混合整數(shù)規(guī)劃. 整

4、數(shù)規(guī)劃的可行域是相應(yīng)的線性規(guī)劃松弛問(wèn)題可行域的子集；因此，松弛問(wèn)題最優(yōu)解是整數(shù)規(guī)劃最優(yōu)解的一個(gè)界 （對(duì)于max，為上界；對(duì)于min，為下界）。 分析整數(shù)規(guī)劃問(wèn)題A對(duì)應(yīng)的松弛問(wèn)題B的最優(yōu)解（對(duì)于max）：說(shuō)明：該方法可計(jì)算機(jī)求解；在部分可行解中求解，計(jì)算量小于枚舉法；對(duì)于大問(wèn)題，計(jì)算量仍較大。例例取整數(shù)2121212121,0,35759256maxxxxxxxxxxxZ 第二步，定界過(guò)程。 這個(gè)解不滿足整數(shù)約束，因此不是原整數(shù)規(guī)劃的最優(yōu)解。 因?yàn)檫@個(gè)問(wèn)題是求最大化問(wèn)題，前面說(shuō)過(guò)整數(shù)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上增加了整數(shù)約束，現(xiàn)在不考慮整數(shù)約束求得這個(gè)解，其目標(biāo)函值 Z是原整數(shù)規(guī)劃目標(biāo)函數(shù)的上界，記

5、 。由于 必然滿足整數(shù)約束，其目標(biāo)函數(shù)值為0，確定為現(xiàn)有下界，記 。 第三步，分枝過(guò)程，將不滿足整數(shù)約束的變量x1進(jìn)行分枝，構(gòu)造兩個(gè)新的約束條件：這樣就把相應(yīng)的線性規(guī)劃的可行域分成兩個(gè)部分5 x2 1 2 5 3 4 x1 1 2 3 4 2x1 + x2 =9 5x1 +7x2 =35 17(3,2 )99121 623,2,3277L PxxZ：120 1753,2,3 2999L PxxZ：122 4,1,29LPxxZ：1233,2,2 8L PxxZ：124442,3 ,3 155L PxxZ：125462 ,3,2 977L PxxZ：6L P：無(wú) 可 行 解1272 ,3 ,2

6、7L PxxZ：128221,4 ,2 855L PxxZ：x13x1 4x22x2 3x12x1 3x23x2 409532下界：上界：297232下界：上界：295431下界：上界：297629下界：上界：2929下界：上界： 且且全全為為整整數(shù)數(shù)0,4 30 652 5min211212121xxxxxxxxxZ 0,4 30 652 5min211212121xxxxxxxxxZLPLPIPIPx x1 1x x2 23 3(18/11,40/11)(18/11,40/11)2 21 11 12 23 3x x1 118/11, 18/11, x x2 2 =40/11 =40/11Z

7、=Z=218/11(218/11(19.8)19.8)即即Z Z 也是也是IPIP最小值的下限。最小值的下限。對(duì)于對(duì)于x x1 118/111.6418/111.64，取值取值x x1 1 1 1， x x1 1 2 2對(duì)于對(duì)于x x2 2 =40/11 3.64 =40/11 3.64，取，取值值x x2 2 3 3 ，x x2 2 4 4先將（先將（LPLP）劃分為（）劃分為（LP1LP1）和）和（LP2LP2）, ,取取x1 1, x1 2x1 1, x1 2且為整數(shù)0,1 4 30 652 )1(5min2111212121xxxxxxxxIPxxZ且為整數(shù)0,2 4 30 652 )

8、2(5min2111212121xxxxxxxxIPxxZx1x233(18/11,40/11)11BAC同理求同理求LP2,LP2,如圖所示。在如圖所示。在C C 點(diǎn)點(diǎn)取得最優(yōu)解。即取得最優(yōu)解。即: :x x1 12, 2, x x2 2 =10/3, =10/3, Z Z(2)(2)56/356/318.7 18.7 ZZ(2)(2) Z Z(1)(1)16 16 原問(wèn)題有比原問(wèn)題有比1616更小的最優(yōu)更小的最優(yōu)解，但解，但 x2 x2 不是整數(shù)，故繼續(xù)不是整數(shù)，故繼續(xù)分支。分支。且為整數(shù)0,3 2 4 30 652 )21(5min21211212121xxxxxxxxxIPxxZ且為整

9、數(shù)0,4 2 4 30 652 )22(5min21211212121xxxxxxxxxIPxxZ分別求出分別求出LP21LP21和和LP22LP22的最優(yōu)解的最優(yōu)解x1x233(18/11,40/11)11BACD先求先求LP21,LP21,如圖所示。此時(shí)如圖所示。此時(shí)D D 在在點(diǎn)取得最優(yōu)解。點(diǎn)取得最優(yōu)解。即即 x x1 112/52.4, x12/52.4, x2 2 =3, =3, Z Z(21)(21)-87/5-17.4 Z-87/5-17.4 Z(211) 如對(duì)如對(duì)LP212繼續(xù)分解，其最小繼續(xù)分解，其最小值也不會(huì)低于值也不會(huì)低于15.5 ，問(wèn)題探，問(wèn)題探明明,剪枝。剪枝。LP1

10、x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x2=10/3Z(2) 18.5LP21x1=12/5, x2=3Z(21) 17.4LP22無(wú)可無(wú)可行解行解LP211x1=2, x2=3Z(211) 17LP212x1=3, x2=5/2Z(212) 15.5x11x12x23x24x12x13 且且均均取取整整數(shù)數(shù),0,255.22108.02.134max21212121xxxxxxxxZ)(0,255 . 22108 . 02 . 134max021212121LPxxxxxxstxxZ 1010108 . 02 . 121

11、 xx255 . 2221 xx松弛問(wèn)題松弛問(wèn)題LPLP0 0的最優(yōu)解的最優(yōu)解X X=(3.57,7.14),Z=(3.57,7.14),Z0 0=35.7=35.7x1x2oABC得到兩個(gè)線性規(guī)劃及增加約束4311xx10 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 x1x2oABCLP1LP2134LP21:X=

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

13、束，選擇由于212211542111121LPLPxxLPZZ6 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) Z21=35.33x26LP211:X=(4,6) Z211=34LP212:X=(5,5) Z212=35x14x15LP22無(wú)可行解無(wú)可行解x

14、27課后練習(xí)：課后練習(xí)：12121212 max 85 1.56. .2 6,0,zxxxxstxxx x且為整數(shù)12341231241234 m ax 8500 2 3 12. 2 6, , ,0zxxxxxxxstxxxx x x x 計(jì)算步驟舉例求解整數(shù)規(guī)劃模型：化標(biāo)準(zhǔn)型：）分析：分析：第一步第一步，如果原問(wèn)題的系數(shù)有小數(shù)，將其化為整數(shù)。如第一個(gè)約束化為122312xx。(15/4, 3/2)X 37.5z松弛問(wèn)題的最優(yōu)解，非整數(shù)規(guī)劃的可行解。1x1341333884xxx134133(0)(0)(3)884xxx1343133488xxx 343130488xx在最終單純形表中選擇分?jǐn)?shù)

15、部分最大的基變量列出該行約束：將所有系數(shù)分成整數(shù)與一個(gè)正的分?jǐn)?shù)之和：將分?jǐn)?shù)部分移至右端：分析右邊的分?jǐn)?shù)項(xiàng)，其取值小于1，即得到了Gomory約束：引入0-1變量的實(shí)際問(wèn)題0-1型整數(shù)規(guī)劃的解法 如果線性規(guī)劃中的所有決策變量的取如果線性規(guī)劃中的所有決策變量的取值只能取值只能取0 0、1 1，則這類(lèi)線性規(guī)劃問(wèn)題是，則這類(lèi)線性規(guī)劃問(wèn)題是一種特殊的整數(shù)規(guī)劃問(wèn)題稱(chēng)之為一種特殊的整數(shù)規(guī)劃問(wèn)題稱(chēng)之為0-10-1規(guī)劃規(guī)劃，把只能取，把只能取0 0或或1 1值的變量稱(chēng)為值的變量稱(chēng)為0-10-1變量。變量。0-10-1變量是一種邏輯變量。變量是一種邏輯變量。 n, 2 , 1j ,A0A1xm, 2 , 1i,b

16、),(xa. t . sxc)x( fmax(min)jn1jijijn1jjj不不成成立立時(shí)時(shí)當(dāng)當(dāng)條條件件成成立立時(shí)時(shí)當(dāng)當(dāng)條條件件其其數(shù)學(xué)模型數(shù)學(xué)模型如下：如下：本節(jié)先介紹引入本節(jié)先介紹引入0-1變量的變量的實(shí)際問(wèn)題實(shí)際問(wèn)題： 投資場(chǎng)所（項(xiàng)目）的選定投資場(chǎng)所（項(xiàng)目）的選定相互排斥的約束條件相互排斥的約束條件關(guān)于固定費(fèi)用的問(wèn)題關(guān)于固定費(fèi)用的問(wèn)題 然后，再研究然后，再研究0-1規(guī)劃問(wèn)題的一般解法規(guī)劃問(wèn)題的一般解法-隱枚舉法隱枚舉法。7 , 2 , 1iA, 0A, 1xiii 點(diǎn)點(diǎn)沒(méi)沒(méi)有有被被選選用用當(dāng)當(dāng)點(diǎn)點(diǎn)被被選選用用當(dāng)當(dāng)令令 10 x1xx1xx)85(2xxxBxbxczmaxi76543

17、2171iii71iii約約束束條條件件目目標(biāo)標(biāo)函函數(shù)數(shù)：（1 1）兩個(gè)約束條件中只有一個(gè)起作用）兩個(gè)約束條件中只有一個(gè)起作用 當(dāng)采用車(chē)運(yùn)方式當(dāng)采用車(chē)運(yùn)方式當(dāng)采用船運(yùn)方式當(dāng)采用船運(yùn)方式, 0, 1y例：例：利用利用0 0 1 1變量將下題表示成一般線性約束條件變量將下題表示成一般線性約束條件x x 1 1+x +x 2 2 2 2 或或 2 2x x 1 1+3x +3x 2 2 5 ; 5 ; 為為非非常常大大的的正正數(shù)數(shù)）（或或MyyyyMyxxMyxxa10,1)1(532)1(2)(2121221121解：解： 為為非非常常大大的的正正數(shù)數(shù)）（或或MyyyyMyxxMyxxa10,1)

18、1(532)1(2)(2121221121 10,1753)(321321321或或yyyyyyyyyxb變量變量 x x 只能取值只能取值0 0、3 3、5 5 或或 7 7 中的一個(gè)中的一個(gè) ; ; 10,17530321, 032103210或或或或yyyyyyyyyyyyx例：例：利用利用0 0 1 1變量將下題表示成一般線性約束條件變量將下題表示成一般線性約束條件 10,1753)(321321321或或yyyyyyyyyxb50(1)( )00 1()xyMxMycxyM 或或非非常常大大的的正正變量變量x x 或等于或等于 0 0，或，或 50 ;50 ;例：例：利用利用0 0

19、1 1變量將下題表示成一般線性約束條件變量將下題表示成一般線性約束條件50(1)( )00 1()xyMxMycxyM 或或非非常常大大的的正正1121122212122 (1)1 (1)2 (1)( )4 (1)1,01xyMxyMxyMdxyMyyMy y （ 非非常常大大的的正正）或或若若 x x1 1 2 2，則，則 x x2 2 1 1，否則，否則x x2 2 4 ; 4 ;例：例：利用利用0 0 1 1變量將下題表示成一般線性約束條件變量將下題表示成一般線性約束條件1121122212122 (1)1 (1)2 (1)( )4 (1)1,01xyMxyMxyMdxyMyyMy y

20、（ 非非常常大大的的正正）或或 非非常常大大的的正正數(shù)數(shù)）（或或MyyyyyyyyMyxxMyxMyxMyxxe10,2)1 (6)1 (2)1 (2)1 (5)(432143214433321121以下四個(gè)約束條件中至少滿足兩個(gè)以下四個(gè)約束條件中至少滿足兩個(gè)x x1 1+x+x2 2 5 5， x x1 1 2 2， x x3 3 2 2， x x3 3+x+x4 4 6 6 非非常常大大的的正正數(shù)數(shù)）（或或MyyyyyyyyMyxxMyxMyxMyxxe10,2)1 (6)1 (2)1 (2)1 (5)(432143214433321121例：例：利用利用0 0 1 1變量將下題表示成一般

21、線性約束條件變量將下題表示成一般線性約束條件項(xiàng)目投資選擇項(xiàng)目投資選擇有有600萬(wàn)元投資萬(wàn)元投資5個(gè)項(xiàng)目，收益如表，求利潤(rùn)最大的方案？個(gè)項(xiàng)目，收益如表，求利潤(rùn)最大的方案？ 互斥約束問(wèn)題互斥約束問(wèn)題 例如關(guān)于煤資源的限制，其約束條件為： 企業(yè)也可以考慮采用天然氣進(jìn)行加熱處理： 這兩個(gè)條件是互相排斥的。引入01變量y，令 互斥問(wèn)題可由下述的條件來(lái)代替，其中M是充分大的數(shù)。 租賃生產(chǎn)問(wèn)題),.,2 , 1(01njjjxj不投資對(duì)項(xiàng)目投資對(duì)項(xiàng)目投資問(wèn)題可以表示為：投資問(wèn)題可以表示為： ）（或或者者nxxxxxxxxBxatsxczjnjjjnjjj, 2 , 1j1021.max765431211隱枚

22、舉法的步驟：隱枚舉法的步驟： 1.找出任意一可行解，目標(biāo)函數(shù)值為找出任意一可行解，目標(biāo)函數(shù)值為Z0 2. 原問(wèn)題求最大值時(shí)，則增加一個(gè)約束原問(wèn)題求最大值時(shí)，則增加一個(gè)約束1 1220(*)nnc xc xc xZ當(dāng)求最小值時(shí)，上式改為小于等于約束當(dāng)求最小值時(shí)，上式改為小于等于約束 3. 列出所有可能解，對(duì)每個(gè)可能解先檢驗(yàn)式（列出所有可能解，對(duì)每個(gè)可能解先檢驗(yàn)式（*），若滿足再），若滿足再檢驗(yàn)其它約束，若不滿足式（檢驗(yàn)其它約束，若不滿足式（*），則認(rèn)為不可行，若所有約束），則認(rèn)為不可行，若所有約束都滿足，則認(rèn)為此解是可行解，求出目標(biāo)值都滿足，則認(rèn)為此解是可行解，求出目標(biāo)值 4. 目標(biāo)函數(shù)值最大（

23、最?。┑慕饩褪亲顑?yōu)解目標(biāo)函數(shù)值最大（最小）的解就是最優(yōu)解 【例例】用隱枚舉法求解下面問(wèn)題用隱枚舉法求解下面問(wèn)題 4 , 3 , 2 , 11010542324653103245326max43214321432143214321jxxxxxxxxxxxxxxxxxxxxxZj，或【解解】（1）不難看出，當(dāng)所有變量等于）不難看出，當(dāng)所有變量等于0或或1的任意組合時(shí)，的任意組合時(shí)，第一個(gè)約束滿足，說(shuō)明第一個(gè)約束沒(méi)有約束力，是多余的，第一個(gè)約束滿足，說(shuō)明第一個(gè)約束沒(méi)有約束力，是多余的，從約束條件中去掉。還能通過(guò)觀察得到從約束條件中去掉。還能通過(guò)觀察得到X0(1，0，0，1)是一是一個(gè)可行解，目標(biāo)值個(gè)

24、可行解，目標(biāo)值Z0=11是該問(wèn)題的下界是該問(wèn)題的下界,增加下面約束增加下面約束1153264321xxxx)9 . 3()9 . 3()9 . 3()9 . 3(4 , 3 , 2 , 110105423246531153265326max43214321432143214321dcbajxxxxxxxxxxxxxxxxxxxxxZj，或(2) 列出變量取值列出變量取值0和和1的組合，共的組合，共2416個(gè)，分別代入約束條件個(gè)，分別代入約束條件判斷是否可行。首先判斷式（判斷是否可行。首先判斷式（3.9a）是否滿足，如果滿足，接下）是否滿足，如果滿足，接下來(lái)判斷其它約束，否則認(rèn)為不可行。來(lái)判斷其

25、它約束，否則認(rèn)為不可行。 (3) 由表知，由表知，該該問(wèn)題的最優(yōu)解：?jiǎn)栴}的最優(yōu)解：X（1，0，1，1），最優(yōu)值），最優(yōu)值Z14 選擇不同的初始可行解，計(jì)算量會(huì)不一樣。一般地，選擇不同的初始可行解，計(jì)算量會(huì)不一樣。一般地，當(dāng)目標(biāo)函數(shù)求最大值時(shí)，首先考慮目標(biāo)函數(shù)系數(shù)最大當(dāng)目標(biāo)函數(shù)求最大值時(shí)，首先考慮目標(biāo)函數(shù)系數(shù)最大的變量等于的變量等于1。當(dāng)目標(biāo)函數(shù)求最小值時(shí)，先考慮目標(biāo)。當(dāng)目標(biāo)函數(shù)求最小值時(shí)，先考慮目標(biāo)函數(shù)系數(shù)最大的變量等于函數(shù)系數(shù)最大的變量等于0。 解：(1)觀察一個(gè)可行解x1 = 1 x2 = x3 = 0 此時(shí)，z = 3 (2) (2)增加一個(gè)過(guò)濾條件增加一個(gè)過(guò)濾條件 3x3x1 1-2x

26、-2x2 2+5x+5x3 33 3 * * 最優(yōu)解：最優(yōu)解：x x1 1* * = 1 x = 1 x2 2* * = 0 x = 0 x3 3* * = 1 = 1 此時(shí)，此時(shí)，z z* * = 8 = 8例： 用窮舉法解0-1整數(shù)規(guī)劃1 , 0,322228232243max32132132321321321xxxxxxxxxxxxxxxxxS321xxx最優(yōu)解為最優(yōu)值為S=3., 0, 0, 1321xxx解：對(duì)于這個(gè)問(wèn)題，很容易建立一個(gè)數(shù)學(xué)模型的，解：對(duì)于這個(gè)問(wèn)題，很容易建立一個(gè)數(shù)學(xué)模型的， 引入引入0-1變量變量 ， 當(dāng)當(dāng) =1時(shí)，表示分配第時(shí)，表示分配第i個(gè)人完成第個(gè)人完成第j項(xiàng)

27、任務(wù)項(xiàng)任務(wù) 當(dāng)當(dāng) =0時(shí)，表示不分配第時(shí)，表示不分配第i個(gè)人完成第個(gè)人完成第j項(xiàng)任務(wù)項(xiàng)任務(wù) 一項(xiàng)任務(wù)只由一個(gè)人完成，有如下約束一項(xiàng)任務(wù)只由一個(gè)人完成，有如下約束 一人只能完成一項(xiàng)任務(wù)，有如下約束一人只能完成一項(xiàng)任務(wù)，有如下約束 設(shè)設(shè) 工作人做不分配第工作人做分配第jijixij01數(shù)學(xué)模型如下：數(shù)學(xué)模型如下：4443424134333231242322211413121188809086907983829578879590739285maxxxxxxxxxxxxxxxxxZ要求每人做一項(xiàng)工作，約束條件為：要求每人做一項(xiàng)工作，約束條件為： 1111444342413433323124232221

28、14131211xxxxxxxxxxxxxxxx 111144342414433323134232221241312111xxxxxxxxxxxxxxxx：4 ,3,2, 110 jixij、，或或指派問(wèn)題的數(shù)學(xué)模型:nBBB21nAAA21nnnnnnccccccccc212222111211要求每個(gè)工人有一項(xiàng)工作,每項(xiàng)工作只有一個(gè)工人來(lái)作.如何安排使總的效益最好., 2 , 1, .0,1njijixjixijij項(xiàng)工作個(gè)人不去做第表示第項(xiàng)工作個(gè)人去做第表示分配第設(shè)10., 2 , 11., 2 , 11min1111或ijniijnjijninjijijxnjxnixxcS二、指派問(wèn)題的

29、解法匈牙利法匈牙利法(1955年W.W.Kuhn求解分配問(wèn)題,使用了匈牙利數(shù)學(xué)家Kuhn的兩個(gè)定理,故稱(chēng)匈牙利解法. .)()(,配問(wèn)題的最優(yōu)解相同配問(wèn)題的最優(yōu)解與原分目標(biāo)函數(shù)系數(shù)矩陣的分為則以矩陣的最小元素后得到的新列該行各元素分別減去列中某一行是在系數(shù)矩陣是分配問(wèn)題目標(biāo)函數(shù)的設(shè)BAbBaAnnijnnij 若方陣中的一部分元素為零,一部分非零,則覆蓋方陣內(nèi)所有零元素的最小直線數(shù),等于方陣內(nèi)位于不同行不同列的零元素的最多個(gè)數(shù)。根據(jù)定理1,2設(shè)計(jì)出分配問(wèn)題的一般解法:第一步:將效率矩陣A的每一行各減去該行的最小元素,再?gòu)男戮仃囍械母髁袦p去該列的最小元素,得矩陣B;第二步:從有零元素最少的行(列

30、)開(kāi)始,圈出零元素后劃去同行(列)的其他零元素.若被圈出的零元素恰好布滿B的不同行不同列,則將這些零元素改為1,其余元素改為0,得最優(yōu)分配矩陣.否則轉(zhuǎn)第三步;分配問(wèn)題的一般解法詳解: 對(duì)沒(méi)有被圈出零的打”; 對(duì)有的行上所有有零元素的列打; 再對(duì)打的列上有被圈出零的行打;第三步:根據(jù)定理2作出覆蓋零元素的最小直線集: 重復(fù) ,直到得不出新打的行,列為止; 對(duì)沒(méi)有打的行畫(huà)橫虛線;對(duì)所有打的列畫(huà)縱虛線,這就是覆蓋所有零元素的最小直線集,轉(zhuǎn)第四步;第四步:在沒(méi)有被覆蓋的元素中找出最小元素,對(duì)沒(méi)有畫(huà)直線的行上各元素都減去這個(gè)最小元素;對(duì)畫(huà)有直線的列上各元素都加上這個(gè)最小元素,這樣得到的矩陣如果不同行不同

31、列上都有被圈出的零,則可將其換為1,其余元素?fù)Q為0,最優(yōu)分配方案求出,否則轉(zhuǎn)第三步.例： 某配送中心有 四項(xiàng)配送任務(wù),分配給 四輛汽車(chē) 去完成,每輛汽車(chē)完成各項(xiàng)配送任務(wù)的時(shí)間如下表,問(wèn)如何分配任務(wù)使總的用時(shí)最少.4321,AAAA4321,BBBB4321AAAA4321BBBB解:取出效率矩陣進(jìn)行運(yùn)算.9118713161491514410413152A794224在B中找出位于不同行,不同列的四個(gè)零元素,作法如下:24104750111006211130B00102350960607130 先從零元素最少的行(列)開(kāi)始,選取一個(gè)零元素將其圈起來(lái),同時(shí)將零元素所在行,列的其余零元素劃去; 如

32、果恰有四個(gè)被圈起來(lái)的零元素,處于不同行不同列,則將這些零改為1,其余元素改為0,得到最優(yōu)分配方案.00102350960607130B00000100000100101000B最優(yōu)分配方案是: .,34132241ABABABAB最優(yōu)值(即總用時(shí))是minS=4+4+9+11=28.9118713161491514410413152A注意:對(duì)于 來(lái)說(shuō)不是最優(yōu)方案,但對(duì)整體來(lái)說(shuō)達(dá)到最優(yōu),這就是運(yùn)籌學(xué)思想.4B例：工廠有 五個(gè)獨(dú)立車(chē)間,該廠計(jì)劃生產(chǎn)五種產(chǎn)品 ,由于產(chǎn)品性質(zhì)和各車(chē)間設(shè)備不同,每個(gè)車(chē)間生產(chǎn)各種產(chǎn)品消耗的資金(萬(wàn)元)不同,如下表.問(wèn)如何安排生產(chǎn)任務(wù),使總的耗資最少.54321,AAAAA

33、54321,BBBBB54321AAAAA54321BBBBB解:610710410661415121412177666989797124676726360400895751000003220205263604008957510000032202052636040089575100000322020500414040081135380000342020722 , 6 , 3 , 6 , 5 , 7 , 5 ,10min),(),(),(),(),(5534134221BABABABABA).(3266767min萬(wàn)元S4347511576469637964589117129118957 713

34、2036304520142405263402-1 -2 5032015304310140305242402 50320153043101403052424022 2）試指派（找獨(dú)立）試指派（找獨(dú)立0 0元素）元素） 獨(dú)立獨(dú)立0 0元素的個(gè)數(shù)元素的個(gè)數(shù)l l4545，故畫(huà)直線調(diào)整矩陣。，故畫(huà)直線調(diào)整矩陣。 5032015304310140305242402選擇直線外的最小元素選擇直線外的最小元素為為1；直線外元素減；直線外元素減1，直線交點(diǎn)元素加直線交點(diǎn)元素加1，其，其他保持不變。他保持不變。 5033004203310240306231301l =m=4 n=5選擇直線外最小元素為選擇直線外最小元素為1，直線外元素減直線外元素減1，直線交點(diǎn)，直線交點(diǎn)元素加元素加1，其他保持不變，其他保持不變，得到新的系數(shù)矩陣。得到新的系數(shù)矩陣。 6044003202300230206130300總費(fèi)用為總費(fèi)用為=5+7+6+6+4=28=5+7+6+6+4=28注：此問(wèn)題有多個(gè)最優(yōu)解注：此問(wèn)題有多個(gè)最優(yōu)解 6044003202300230206130300總費(fèi)用為總費(fèi)用為=7+9+4+3+5=28=7+9+4+3+5=28 6044003202300230206130300總費(fèi)用為總費(fèi)用為=8+9+4+3+4=28=8