運籌學(xué)-第5章整數(shù)規(guī)劃

1、第第5章章 整數(shù)規(guī)劃整數(shù)規(guī)劃 OR:SM2 第一節(jié)第一節(jié) 整數(shù)規(guī)劃問題及數(shù)學(xué)模型整數(shù)規(guī)劃問題及數(shù)學(xué)模型 純整數(shù)規(guī)劃純整數(shù)規(guī)劃 0-1規(guī)劃規(guī)劃 混合整數(shù)規(guī)劃混合整數(shù)規(guī)劃 第二節(jié)第二節(jié) 整數(shù)規(guī)劃求解整數(shù)規(guī)劃求解 分枝定界法分枝定界法 割平面法割平面法 隱枚舉法隱枚舉法 匈牙利法匈牙利法 OR:SM3 第一節(jié)第一節(jié) 整數(shù)規(guī)劃問題及數(shù)學(xué)模型整數(shù)規(guī)劃問題及數(shù)學(xué)模型 一、整數(shù)規(guī)劃問題簡述一、整數(shù)規(guī)劃問題簡述 線性規(guī)劃的決策變量取值可以是任意非負(fù)實數(shù)，但許多實際線性規(guī)劃的決策變量取值可以是任意非負(fù)實數(shù)，但許多實際 問題中，只有當(dāng)決策變量的取值為整數(shù)時才有意義問題中，只有當(dāng)決策變量的取值為整數(shù)時才有意義 例如

2、，產(chǎn)品的件數(shù)、機(jī)器的臺數(shù)、裝貨的車數(shù)、完成工作的人例如，產(chǎn)品的件數(shù)、機(jī)器的臺數(shù)、裝貨的車數(shù)、完成工作的人 數(shù)等，分?jǐn)?shù)或小數(shù)解顯然是不合理的。數(shù)等，分?jǐn)?shù)或小數(shù)解顯然是不合理的。 要求全部或部分決策變量的取值為整數(shù)的線性規(guī)劃問題，稱要求全部或部分決策變量的取值為整數(shù)的線性規(guī)劃問題，稱 為整數(shù)規(guī)劃為整數(shù)規(guī)劃( (Integer Programming) )。 全部決策變量的取值都為整數(shù)，全整數(shù)規(guī)劃全部決策變量的取值都為整數(shù)，全整數(shù)規(guī)劃(All IP) 僅要求部分決策變量的取值為整數(shù)，混合整數(shù)規(guī)劃僅要求部分決策變量的取值為整數(shù)，混合整數(shù)規(guī)劃(Mixed IP) 要求決策變量只取要求決策變量只取0或或1

3、值，則稱值，則稱0-1規(guī)劃規(guī)劃(0-1 Programming) OR:SM4 一、全一、全( (純純) )整數(shù)規(guī)劃整數(shù)規(guī)劃 產(chǎn)品產(chǎn)品 資源資源 甲甲乙乙現(xiàn)有量現(xiàn)有量 A219 B5735 單臺利潤單臺利潤65 例：例：某企業(yè)利用材料和設(shè)備生產(chǎn)甲乙產(chǎn)品，其工藝消耗系數(shù)和單臺某企業(yè)利用材料和設(shè)備生產(chǎn)甲乙產(chǎn)品，其工藝消耗系數(shù)和單臺 產(chǎn)品的獲利能力如下表所示，產(chǎn)品的獲利能力如下表所示，問如何安排利潤最大問如何安排利潤最大(變量取整變量取整)？ 解：解：設(shè)設(shè)x1為甲產(chǎn)品的臺數(shù)，為甲產(chǎn)品的臺數(shù)，x2為乙產(chǎn)品的臺數(shù)，則模型為：為乙產(chǎn)品的臺數(shù)，則模型為： maxZ = 6x1 +5x2 2x1 + x2 9

4、 5x1 +7x2 35 x1, x2 0,且為整數(shù)且為整數(shù) OR:SM5 二、二、0-10-1規(guī)劃規(guī)劃 登山隊員可攜帶最大重量為登山隊員可攜帶最大重量為2525公斤，問應(yīng)帶哪些物品，重要性最大？公斤，問應(yīng)帶哪些物品，重要性最大？ 解：對于每一種物品無非有兩種狀態(tài)，帶或者不帶，不妨設(shè)解：對于每一種物品無非有兩種狀態(tài)，帶或者不帶，不妨設(shè) 序號序號1234567 物品物品食品食品氧氣氧氣冰鎬冰鎬繩索繩索帳篷帳篷相機(jī)相機(jī)設(shè)備設(shè)備 重量重量55261224 重要性系數(shù)重要性系數(shù)201518148410 0-1規(guī)劃的模型：規(guī)劃的模型： OR:SM6 三、混合整數(shù)規(guī)劃三、混合整數(shù)規(guī)劃 例：例：某產(chǎn)品有某產(chǎn)

5、品有 n 個區(qū)域市場，各區(qū)域市場的需求量為個區(qū)域市場，各區(qū)域市場的需求量為 bj 噸噸/月；現(xiàn)月；現(xiàn) 擬在擬在 m 個地點中選址建生產(chǎn)廠，一個地方最多只能建一家工廠；若個地點中選址建生產(chǎn)廠，一個地方最多只能建一家工廠；若 選選 i 地建廠，生產(chǎn)能力為地建廠，生產(chǎn)能力為 ai 噸噸/月，其運營固定費用為月，其運營固定費用為Fi 元元/月；已知月；已知 址址 i 至至 j 區(qū)域市場的運價為區(qū)域市場的運價為cij元元/噸。如何選址和安排調(diào)運，可使總費噸。如何選址和安排調(diào)運，可使總費 用最??？用最?。?解：解： 假設(shè)假設(shè) yi =1，選擇第，選擇第 i 址建廠，址建廠， yi =0，不選擇第，不選擇第

6、 i 址建廠；址建廠； 計劃從廠址計劃從廠址i 至市場至市場 j 的運輸?shù)倪\輸 量為量為xij (連續(xù)型決策變量連續(xù)型決策變量)。 OR:SM7 第一節(jié)第一節(jié) 整數(shù)規(guī)劃問題及數(shù)學(xué)模型整數(shù)規(guī)劃問題及數(shù)學(xué)模型 二、整數(shù)規(guī)劃問題建模舉例二、整數(shù)規(guī)劃問題建模舉例 參見教材：參見教材： P110: 5.1 P115: 5.1-5.6 P122: 5.9 OR:SM8 整數(shù)規(guī)劃建模舉例整數(shù)規(guī)劃建模舉例 一、生產(chǎn)基地規(guī)劃一、生產(chǎn)基地規(guī)劃 例：例：某公司擬建某公司擬建A、B兩種類型的生產(chǎn)基地若干個，每個基地占地兩種類型的生產(chǎn)基地若干個，每個基地占地 面積，所需經(jīng)費，建成后生產(chǎn)能力及現(xiàn)有資源情況如下表所示，問面

7、積，所需經(jīng)費，建成后生產(chǎn)能力及現(xiàn)有資源情況如下表所示，問A、 B類型基地各建設(shè)多少個，可使總生產(chǎn)能力最大？類型基地各建設(shè)多少個，可使總生產(chǎn)能力最大？ 解：設(shè)解：設(shè)A、B兩類基地各建兩類基地各建 設(shè)設(shè) x1,x2 個，則其模型為：個，則其模型為： OR:SM9 二、人員安排規(guī)劃二、人員安排規(guī)劃 某服務(wù)部門各時段某服務(wù)部門各時段( (每每2 2小時為一時段小時為一時段) )需要的服務(wù)人數(shù)如表：需要的服務(wù)人數(shù)如表： 解：設(shè)第解：設(shè)第j 時段開始時上班的服時段開始時上班的服 務(wù)員人數(shù)為務(wù)員人數(shù)為xj 第第 j 時段來上班的服務(wù)員將在時段來上班的服務(wù)員將在 第第j +3 時段結(jié)束時下班，故決策時段結(jié)束時

8、下班，故決策 變量有變量有x1, x2, x3, x4, x5 。 按規(guī)定，服務(wù)員連續(xù)工作按規(guī)定，服務(wù)員連續(xù)工作8 8小小 時時(4(4個時段個時段) )為一班。如何安排為一班。如何安排 服務(wù)員的工作時間，使服務(wù)員服務(wù)員的工作時間，使服務(wù)員 總數(shù)最少？總數(shù)最少？ OR:SM10 三、項目投資選擇三、項目投資選擇 有有600萬元投資萬元投資5個項目，收益如表，求利潤最大的方案？個項目，收益如表，求利潤最大的方案？ OR:SM11 四、互斥約束問題四、互斥約束問題 例如關(guān)于煤資源的限制，其約束條件為：例如關(guān)于煤資源的限制，其約束條件為： 企業(yè)也可以考慮采用天然氣進(jìn)行加熱處理：企業(yè)也可以考慮采用天然

9、氣進(jìn)行加熱處理： 這兩個條件是互相排斥。這兩個條件是互相排斥。 引入引入0-1變量變量 y ，令，令 互斥問題可由下述的條件來代替，其中互斥問題可由下述的條件來代替，其中M是任意大的正數(shù)。是任意大的正數(shù)。 OR:SM12 五、租賃生產(chǎn)問題五、租賃生產(chǎn)問題 某服裝公司租用生產(chǎn)線擬生產(chǎn)某服裝公司租用生產(chǎn)線擬生產(chǎn)T恤、襯衫和褲子，每年可使用勞動恤、襯衫和褲子，每年可使用勞動 力力 8200 h，布料，布料 8800m2，問如何安排利潤最大？，問如何安排利潤最大？ T恤恤襯衫襯衫褲子褲子 勞動力勞動力(h)326 布料布料(m2)0.81.11.5 售價售價(元元)250400600 可變成本可變成本

10、(元元)100180300 生產(chǎn)線租金生產(chǎn)線租金(萬萬)201510 假設(shè)：假設(shè)：yj=1，要租用生產(chǎn)線，要租用生產(chǎn)線 j yi=0，不租用生產(chǎn)線，不租用生產(chǎn)線 j 第第 j 種服裝生產(chǎn)量種服裝生產(chǎn)量 xj x1My1 x2My2 x3My3 其中，其中，M為任意大的正數(shù)。為任意大的正數(shù)。 OR:SM13 六、任務(wù)指派問題六、任務(wù)指派問題 甲乙丙丁四個人，甲乙丙丁四個人，ABCD四項任務(wù)，如何指派總時間最短？四項任務(wù)，如何指派總時間最短？ 解：解： 引入引入0-1變量變量xij ， xij =1：任務(wù)：任務(wù)j指派人員指派人員i去完成去完成 xij =0：任務(wù)：任務(wù)j不派人員不派人員i去完成去完

11、成 一項任務(wù)只由一個人完成一項任務(wù)只由一個人完成 一人只能完成一項任務(wù)一人只能完成一項任務(wù) OR:SM14 第二節(jié)第二節(jié) 整數(shù)規(guī)劃問題求解整數(shù)規(guī)劃問題求解 一、舍入化整法一、舍入化整法 maxZ = 6x1 + 5x2 2x1 + x2 9 5x1 + 7x2 35 x1,x20且為整數(shù)且為整數(shù) x1 x2 369 3 5 9 (28/9, 25/9) 對于本例，松馳問題對于本例，松馳問題的最的最 優(yōu)解：優(yōu)解：x1*=28/9， x2* =25/9， Z * =293/9 整數(shù)規(guī)劃問題取消整數(shù)限制整數(shù)規(guī)劃問題取消整數(shù)限制 后稱為松馳問題。后稱為松馳問題。 x1 =3， x2 =3，Z =33，

12、不滿足約束條件，不滿足約束條件5 x1 + 7 x2 35，不可行；，不可行； x1 =3， x2 =2，Z =28，滿足約束條件，是可行解，但不是最優(yōu)解；，滿足約束條件，是可行解，但不是最優(yōu)解； x1 =4， x2 =1，Z =29，滿足約束條件，而且是最優(yōu)解。，滿足約束條件，而且是最優(yōu)解。 OR:SM15 從數(shù)學(xué)模型上看整數(shù)規(guī)劃似乎是線性規(guī)劃從數(shù)學(xué)模型上看整數(shù)規(guī)劃似乎是線性規(guī)劃 的一種特殊形式，求解只需在線性規(guī)劃的基礎(chǔ)的一種特殊形式，求解只需在線性規(guī)劃的基礎(chǔ) 上，通過舍入取整，尋求滿足整數(shù)要求的解即上，通過舍入取整，尋求滿足整數(shù)要求的解即 可。但實際上兩者卻有很大的不同，通過舍入可。但實際

13、上兩者卻有很大的不同，通過舍入 得到的解（整數(shù)）也不一定就是最優(yōu)解，有時得到的解（整數(shù)）也不一定就是最優(yōu)解，有時 甚至不能保證所得倒的解是整數(shù)可行解。甚至不能保證所得倒的解是整數(shù)可行解。 OR:SM16 二、窮舉整數(shù)法二、窮舉整數(shù)法 對于決策變量少，整數(shù)可行解對于決策變量少，整數(shù)可行解 數(shù)量較少時，這種窮舉法有時是可數(shù)量較少時，這種窮舉法有時是可 行的，并且是有效的。行的，并且是有效的。 但對于大型的整數(shù)規(guī)劃問題，但對于大型的整數(shù)規(guī)劃問題， 可行的整數(shù)解數(shù)量很多，用窮舉法可行的整數(shù)解數(shù)量很多，用窮舉法 求解是不可能的。例如，指派問題。求解是不可能的。例如，指派問題。 5x1 +7 x2 =35

14、 2x1 + x2 = 9 x1 x2 123 1 2 5 3 4 4 17 ( 3, 2) 99 OR:SM17 三、分枝定界法三、分枝定界法 松馳問題：某一整數(shù)規(guī)劃對應(yīng)的線性規(guī)劃問題稱為松馳問題。松馳問題：某一整數(shù)規(guī)劃對應(yīng)的線性規(guī)劃問題稱為松馳問題。 即不考慮決策變量整數(shù)限制的整數(shù)規(guī)劃問題。即不考慮決策變量整數(shù)限制的整數(shù)規(guī)劃問題。 分支定界法基本思路：分支定界法基本思路： 在松馳問題可行域中尋找使目標(biāo)函數(shù)值達(dá)到最優(yōu)的整數(shù)解。在松馳問題可行域中尋找使目標(biāo)函數(shù)值達(dá)到最優(yōu)的整數(shù)解。 定理定理5-1： 對于某一求對于某一求max(min)的整數(shù)規(guī)劃問題，其目標(biāo)函數(shù)最優(yōu)值的整數(shù)規(guī)劃問題，其目標(biāo)函數(shù)最

15、優(yōu)值 不超過不超過(低于低于)其松馳問題的目標(biāo)函數(shù)最優(yōu)值。其松馳問題的目標(biāo)函數(shù)最優(yōu)值。 OR:SM18 分枝定界法基本步驟分枝定界法基本步驟 不考慮整數(shù)限制，先求出相應(yīng)松馳問題的最優(yōu)解。不考慮整數(shù)限制，先求出相應(yīng)松馳問題的最優(yōu)解。 若求得的最優(yōu)解符合整數(shù)要求，則是原若求得的最優(yōu)解符合整數(shù)要求，則是原IP的最優(yōu)解。的最優(yōu)解。 若不滿足整數(shù)條件，則任選一個不滿足整數(shù)條件的變量來構(gòu)造若不滿足整數(shù)條件，則任選一個不滿足整數(shù)條件的變量來構(gòu)造 新的約束，在原可行域中剔除部分非整數(shù)解。新的約束，在原可行域中剔除部分非整數(shù)解。 依次在縮小的可行域中求解新構(gòu)造的線性規(guī)劃的最優(yōu)解，直依次在縮小的可行域中求解新構(gòu)造

16、的線性規(guī)劃的最優(yōu)解，直 到獲得原整數(shù)規(guī)劃的最優(yōu)解。到獲得原整數(shù)規(guī)劃的最優(yōu)解。 定界的含義：定界的含義： IP是在相應(yīng)的是在相應(yīng)的LP基礎(chǔ)上增加整數(shù)約束基礎(chǔ)上增加整數(shù)約束 IP的最優(yōu)解不會優(yōu)于相應(yīng)的最優(yōu)解不會優(yōu)于相應(yīng)LP的最優(yōu)解的最優(yōu)解 對對MaxZ的的IP，LP的的Z*是是IP的上界的上界 OR:SM19 x2 x1 5 3 0 6 3 21 (1) (2) 分枝定界法舉例：分枝定界法舉例： 12 12 12 12 951 1414 1 2 3 0 max , Zxx xx xx x x 且且為為整整數(shù)數(shù) 2 4 OR:SM20 x2 x1 5 3 0 6 3 21 (1) (2) 第一步：圖

17、解法求松馳問題最優(yōu)解第一步：圖解法求松馳問題最優(yōu)解 (定界定界) 12 12 12 12 951 1414 1 2 3 0 max , Zxx xx xx x x 且且為為整整數(shù)數(shù) 2 4 A (3/2 , 10/3) (0 ) 0 (0 ) 3 10 (,) 23 : 29 6 T X LP Z LP0 29 6 0 上上 界界 ： 下下 界界 ： OR:SM21 x2 x1 5 3 0 6 3 21 (1) (2) 第二步：分枝第二步：分枝 2 4 A LP2 選擇其中一個取值非整數(shù)變量進(jìn)行分支，如選擇其中一個取值非整數(shù)變量進(jìn)行分支，如x1。 當(dāng)當(dāng)1x1Z(1)，故選擇，故選擇LP2進(jìn)行分

18、支，進(jìn)行分支， x2=23/9，分支結(jié)果：，分支結(jié)果：x22，x23 LP4 D 3 12 12 12 1 2 12 951 1414 1 2 3 2 2 0 ( ) max , Zxx xx xx x x xx 4 12 12 12 1 2 12 951 1414 1 2 3 2 3 0 ( ) max , Zxx xx xx x x x x (33/14 , 2) (3) 3 (3) 33 (, 2) 14 : 61 14 T X LP Z 4 :LP無 可 行 解 6 1 1 4 0 上上 界界 ： 下下 界界 ： OR:SM23 x2 x1 5 3 0 6 3 21 (1) (2) 第

19、四步：比較分枝結(jié)果，選第四步：比較分枝結(jié)果，選 擇下一步分支區(qū)域，擇下一步分支區(qū)域，定界定界 2 4 A LP3LP1 B C 因因Z(3)Z(1)，故選擇，故選擇LP3進(jìn)行分支，進(jìn)行分支， x1=33/14，分支結(jié)果：，分支結(jié)果：x12，x13 LP4 D 5 12 12 12 1 2 1 12 951 1414 1 2 3 2 2 2 0 ( ) max , Zxx xx xx x x x xx 6 12 12 12 1 2 1 12 951 1414 1 2 3 2 2 3 0 ( ) max , Zxx xx xx x x x x x E LP5 LP6 (2, 2) (5) 5 (5

20、) (2, 2) : 4 T X LP Z F (3, 1) (6) 6 (6) (3,1) : 4 T X LP Z 4 4 上上 界界 ： 下下 界界 ： OR:SM24 1 (1) 12 710 1, 33 LP xxZ ： 0 (0 ) 12 31029 , 236 LP xxZ ： 2 (2) 12 2341 2, 99 LP xxZ ： x11x1 2 29 6 0 上上 界界 ： 下下 界界 ： 4 1 9 0 上上 界界 ： 下下 界界 ： x22x2 3 3 (3 ) 12 3361 ,2, 1414 L P xxZ ： 4 LP ： 無可行解 6 1 1 4 0 上上 界界

21、 ： 下下 界界 ： x12x1 3 5 (5) 12 2,2,4 LP xxZ ： 6 (6) 12 3,1,4 LP xxZ ：4 4 上上 界界 ： 下下 界界 ： OR:SM25 x2 x1 5 7 0 9 453 (1) (2) 12 12 12 1212 max65 5735 29 ,0;, Zxx xx xx xxxxI 分支定界法舉例：分支定界法舉例： OR:SM26 x2 x1 5 7 0 9 453 (1) (2) A ( 28/9, 25/9 ) (0) 0 (0) 17 (3, 2) 99 : 5 32 9 T X LP Z LP0 OR:SM27 x2 x1 5 7

22、0 9 453 (1) (2) A (1) 1 (1) 6 (3, 2) 7 : 2 32 7 T X LP Z LP1 LP2 B B( 3, 20/7 ) C C( 4, 1 ) (2) 2 (2) (4,1) : 29 T X LP Z OR:SM28 x2 x1 5 7 0 9 453 (1) (2) E (3) 3 (3) 4 (2,3) 5 : 4 31 5 T X LP Z E( 14/5, 3) D (4) 4 (4) (3, 2) : 28 T X LP Z LP3 LP4 3 2 D( 3, 2) OR:SM29 x2 x1 5 7 0 9 453 (1) (2) F (5

23、) 5 (5) 4 (2,3) 7 : 6 29 7 T X LP Z F( 2, 25/7) D LP4 3 2 D( 3, 2) 2 LP6: 無可行解(x1=3) LP5 OR:SM30 x2 x1 5 7 0 9 453 (1) (2) H (7) 7 (7) (2,3) : 27 T X LP Z G( 2, 3)G LP8 LP4 3 2 H( 7/5, 4) 2 (8) 8 (8) 7 (, 4) 5 : 2 28 5 T X LP Z 4 LP7 OR:SM31 1 (1 ) 12 62 3,2,3 2 77 L P xxZ ： 0 (0 ) 12 175 3,2,32 999

24、 LP xxZ ： 2 (2) 12 4,1,29 LP xxZ ： 3 (3) 12 3,2,28 LP xxZ ：4 (4) 12 44 2,3,31 55 LP xxZ ： 5 ( 5 ) 12 46 2 ,3,2 9 77 L P xxZ ： 6 LP ： 無 可 行 解 7 (7) 12 2,3,27 LP xxZ ： 8 (8 ) 12 22 1,4,28 55 LP xxZ ： x13x1 4 x22x2 3 x12x1 3 x23x2 4 0 9 5 32 下界： 上界： 29 7 2 32 下界： 上界： 29 5 4 31 下界： 上界： 29 7 6 29 下界： 上界：

25、 29 29 下界： 上界： OR:SM32 步驟步驟1、整數(shù)規(guī)劃問題為、整數(shù)規(guī)劃問題為A，其松弛問題為，其松弛問題為B，設(shè)為問，設(shè)為問 題題A（max）的初始下界（）的初始下界（min問題為上界）問題為上界） 步驟步驟2、求解問題求解問題B，有三種情況：，有三種情況： （a）B 無可行解，此時問題無可行解，此時問題A也無可行解，停止。也無可行解，停止。 （b）B 有最優(yōu)解且為整數(shù)，則問題有最優(yōu)解且為整數(shù)，則問題B的最優(yōu)解即是的最優(yōu)解即是 問題問題A的最優(yōu)解，停止。的最優(yōu)解，停止。 （c）B 有最優(yōu)解但不是整數(shù)，設(shè)目標(biāo)函數(shù)值為問題有最優(yōu)解但不是整數(shù)，設(shè)目標(biāo)函數(shù)值為問題 A的上（下）界，轉(zhuǎn)入步驟

26、的上（下）界，轉(zhuǎn)入步驟3。 步驟步驟3、分支、定界。分支、定界。 步驟步驟4、比較、剪枝。比較、剪枝。 步驟步驟5、重復(fù)步驟重復(fù)步驟 3 和和 4 ，直至求出最優(yōu)整數(shù)解。，直至求出最優(yōu)整數(shù)解。 OR:SM33 【練習(xí)練習(xí)】用分枝定界法求解整數(shù)規(guī)劃問題用分枝定界法求解整數(shù)規(guī)劃問題 【解解】先求對應(yīng)的松弛問題（記為先求對應(yīng)的松弛問題（記為LP0）：）： 12 12 012 12 max43 1.20.810 :22.525 ,0 Zxx xx LPxx x x 用圖解法得到最優(yōu)解用圖解法得到最優(yōu)解X(0)(3.57, 7.14)T, Z(0)=35.7, 如下圖所示。如下圖所示。 12 12 12

27、 12 43 1 20 810 22 525 0 m ax . . , Zxx xx xx xx 且且 為為 整整 數(shù)數(shù) OR:SM34 8.33 10 108 . 02 . 1 21 xx 255 . 22 21 xx 松弛問題松弛問題LP0的最優(yōu)解：的最優(yōu)解： X(0)=(3.57,7.14)T, Z(0)=35.7 x1 x2 o A B C 10 OR:SM35 10 10 x1 x2 o A B C 12 12 12 1 1 12 max43 1.20.810 22.525 : 3 ,0 Zxx xx xx LP x x x LP1 LP2 34 LP1: X(1)=(3, 7.6)

28、T, Z(1)=34.8 LP2: X(2)=(4, 6.5)T, Z(2)=35.5 12 12 12 2 1 12 max43 1.20.810 22.525 : 4 ,0 Zxx xx xx LP x x x 11 34xx增增加加約約束束及及得得到到兩兩個個線線性性規(guī)規(guī)劃劃問問題題 OR:SM36 10 10 x1 x2 o A B C LP1 LP3 34 LP3: X(3)=(4.33, 6)T, Z(3)=35.33 12 12 12 3 12 12 max43 1.20.810 22.525 : 46 ,0 Zxx xx xx LP xx x x ， 2 222 677 LP

29、xxx 選擇目標(biāo)值最大的分枝進(jìn)行分枝，增加約束 及，顯然不可行，得到線性規(guī)劃 6 不可行7 2 x LP1: X(1)=(3, 7.6)T, Z(1)=34.8 D OR:SM37 10 10 x1 x2 o A C LP1 34 12 12 12 4 121 12 1 max43 1.20.810 22.525 : 464 ,0 4, Zxx xx xx LP xxx x x x ， 即可行域是一條線段 (3)(1) 3 1145 45 ZZLP xxLPLP 由于，選擇進(jìn)行分枝，增加約束 及，線性規(guī)劃及： 6 12 12 12 5 12 12 max43 1.20.810 22.525 :

30、 56 ,0 Zxx xx xx LP xx x x ， LP4: X(4)=(4, 6)T, Z(4)=34 LP5:X(5)=(5, 5)T, Z(5)=35 5 LP1: X(1)=(3, 7.6)T, Z(1)=34.8 LP3 LP5 E F OR:SM38 盡管還可以對盡管還可以對Z(1)中的中的x2分支，但分支，但Z(5)Z(1)，因此，因此LP5的最的最 優(yōu)解就是原整數(shù)規(guī)劃的最優(yōu)解。優(yōu)解就是原整數(shù)規(guī)劃的最優(yōu)解。 上述分枝過程可用下圖表示上述分枝過程可用下圖表示 LP0:X(0)=(3.57, 7.14)T, Z0=35.7 LP1:X(1)=(3, 7.6)T Z(1)=34.

31、8 LP2:X(2)=(4, 6.5)T Z(2) =35.5 x13x14 LP3:X(3)=(4.33, 6)T Z(3)=35.33 x26 LP4:X(4)=(4, 6)T Z(4)=34 LP5:X(5)=(5, 5)T Z(5)=35 x14x15 無可行解無可行解 x27 3 5 7 0 .上上 界界 ： 下下 界界 ： 3 5 5 0 .上上 界界 ： 下下 界界 ： 3 5 3 3 0 .上上 界界 ： 下下 界界 ： 3 5 3 5 上上 界界 ： 下下 界界 ： OR:SM39 四、割平面法四、割平面法 步驟：步驟： 1、用單純形法求解松馳問題；、用單純形法求解松馳問題；

32、 2、在松馳問題最終單純形表中任選一約束條、在松馳問題最終單純形表中任選一約束條 件，構(gòu)造新的約束條件件，構(gòu)造新的約束條件(割平面約束割平面約束)； 3、將新的約束條件加入最終單純形表中，求、將新的約束條件加入最終單純形表中，求 解最優(yōu)整數(shù)解。解最優(yōu)整數(shù)解。 注意：注意： 割平面約束往往不是一次就可以找到。割平面約束往往不是一次就可以找到。 OR:SM40 例：用割平面法求解整數(shù)規(guī)劃問題例：用割平面法求解整數(shù)規(guī)劃問題 12 12 12 12 max43 30 . .10 ,0, 64 2 Z st I xx xx xx x x 解：解：1、標(biāo)準(zhǔn)化、標(biāo)準(zhǔn)化 1234 123 124 max 30

33、 .10 0,1,2,3,4 4300 64 2 j Z st I j xxxx xxx xxx x OR:SM41 2、單純形法求解松馳問題、單純形法求解松馳問題 cj 4 3 0 0 CB XB b x1 x2 x3 x4 0 0 x3 x4 30 10 6 4 1 0 1 2 0 1 j 4 3 0 0 4 0 x1 x4 5 5 1 2/3 1/6 0 0 4/3 -1/6 1 j 0 1/3 -2/3 0 4 3 x1 x2 5/2 15/4 1 0 1/4 -1/2 0 1 -1/8 3/4 j 0 0 -5/8 -1/4 * 5/2,15/4,0,0 T X * 85/4Z OR

34、:SM42 3、尋找割平面約束（、尋找割平面約束（1） cj 4 3 0 0 CB XB b x1 x2 x3 x4 4 3 x3 x4 5/2 15/4 1 0 1/4 -1/2 0 1 -1/8 3/4 j 0 0 -5/8 -1/4 1234 115 0 422 xxxx 134 111 12 422 xxx 1434 111 2 242 xxxx 思考：等式左端在什么條件下有可能為整數(shù)？思考：等式左端在什么條件下有可能為整數(shù)？ OR:SM43 1434 111 2 242 xxxx 34 1/2 11 0,1/2) 42 (1/2,) xx 14 0 20 0 xx 整數(shù)整數(shù) 可能為整

35、數(shù)可能為整數(shù) 所以，等式左端若為整數(shù)，則有：所以，等式左端若為整數(shù)，則有： 34 111 0 242 xx 34 111 422 xx 345 111 422 xxx 即為所尋找的割平面約束。即為所尋找的割平面約束。 OR:SM44 4、求最優(yōu)整數(shù)解、求最優(yōu)整數(shù)解 345 111 422 xxx cj 4 3 0 0 0 CB XB b x1 x2 x3 x4 x5 4 3 x1 x2 x5 5/2 15/4 1 0 1/4 -1/2 0 1 -1/8 3/4 j 0 0 -5/8 -1/4 4 3 x1 x2 j * 3,3,0,1,0 T X * 21Z OR:SM45 4、求最優(yōu)整數(shù)解、

36、求最優(yōu)整數(shù)解 345 22 xxx cj 4 3 0 0 0 CB XB b x1 x2 x3 x4 x5 4 3 x1 x2 x5 5/2 15/4 1 0 1/4 -1/2 0 1 -1/8 3/4 j 0 0 -5/8 -1/4 4 3 x1 x2 j * 3,3,0,1,0 T X * 21Z OR:SM46 新的約束新的約束(割平面約束割平面約束)： 34 111 422 xx 34 22xx 松馳問題原約束：松馳問題原約束： 123 124 6430 210 xxx xxx 312 412 3064 102 xxx xxx 將原約束代入割平面約束：將原約束代入割平面約束： 12 6

37、xx OR:SM47 加入割平面約束后加入割平面約束后 約束條件變?yōu)椋杭s束條件變?yōu)椋?12 12 12 6430 210 6 xx xx xx x1 x2 O 10 5 10 (5/2, 15/4) 12 6430 xx 12 210 xx 7.5 6 56 2, 4 3,3 OR:SM48 3、尋找割平面約束（、尋找割平面約束（2） cj 4 3 0 0 CB XB b x1 x2 x3 x4 4 3 x3 x4 5/2 15/4 1 0 1/4 -1/2 0 1 -1/8 3/4 j 0 0 -5/8 -1/4 234 1315 844 xxx 234 733 13 844 xxx 233

38、4 373 3 484 xxxx 等式左端在什么條件下有可能為整數(shù)？等式左端在什么條件下有可能為整數(shù)？ OR:SM49 2334 373 3 484 xxxx 34 3/4 73 0,3/4) 84 (3/4,) xx 23 0 30 0 xx 整數(shù)整數(shù) 可能為整數(shù)可能為整數(shù) 所以，等式左端若為整數(shù)，則有：所以，等式左端若為整數(shù)，則有： 34 373 0 484 xx 34 733 844 xx 345 733 844 xxx 即為所尋找的割平面約束。即為所尋找的割平面約束。 OR:SM50 4、求最優(yōu)整數(shù)解、求最優(yōu)整數(shù)解 345 733 844 xxx cj 4 3 0 0 0 CB XB

39、b x1 x2 x3 x4 x5 4 3 x1 x2 x5 5/2 15/4 1 0 1/4 -1/2 0 1 -1/8 3/4 j 0 0 -5/8 -1/4 4 3 x1 x2 j * 3,3,0,1,0 T X * 21Z OR:SM51 新的約束新的約束(割平面約束割平面約束)： 34 733 844 xx 34 766xx 松馳問題原約束：松馳問題原約束： 123 124 6430 210 xxx xxx 312 412 3064 102 xxx xxx 將原約束代入割平面約束：將原約束代入割平面約束： 12 6533xx OR:SM52 加入割平面約束后加入割平面約束后 約束條件變

40、為：約束條件變?yōu)椋?12 12 12 6430 210 6533 xx xx xx x1 x2 O 10 5 10 (5/2, 15/4) 12 6430 xx 12 210 xx 7.5 6 56 1627 , 77 3,3 OR:SM53 第三節(jié)第三節(jié) 整數(shù)規(guī)劃求解整數(shù)規(guī)劃求解 五、隱枚舉法五、隱枚舉法 u用于求解用于求解0-1整數(shù)規(guī)劃問題的一種方法。整數(shù)規(guī)劃問題的一種方法。 u求解步驟：求解步驟： u1、尋找目標(biāo)函數(shù)值下界；、尋找目標(biāo)函數(shù)值下界；(max) u2、構(gòu)造過濾約束，并將其加入到原約束條件中；、構(gòu)造過濾約束，并將其加入到原約束條件中； u3、寫出所有解組合，比較、寫出所有解組合

41、，比較Z值，并檢查是否滿足約值，并檢查是否滿足約 束條件和過濾條件，得出最優(yōu)解。束條件和過濾條件，得出最優(yōu)解。 u例：例： OR:SM54 123 123 123 12 23 max325 22 44 3 46 0,1;1,2,3 j Zxxx xxx xxx xx xx xj 過濾約束過濾約束(目標(biāo)函數(shù)目標(biāo)函數(shù))： 3x1 - 2x2 + 5x30 (0,0,0)T 解組合解組合 (x1, x2, x3)T Z值值 約束約束 條件條件 過濾過濾 約束約束 (0, 0, 0)T (0, 0, 1)T (0, 1, 0)T (0, 1, 1)T (1, 0, 0)T (1, 0, 1)T (1,

42、 1, 0)T (1, 1, 1)T * * 1,0,1 8 T X Z OR:SM55 123 123 123 12 23 max325 22 44 3 46 0,1;1,2,3 j Zxxx xxx xxx xx xx xj 過濾約束過濾約束(目標(biāo)函數(shù)目標(biāo)函數(shù))： 3x1 - 2x2 + 5x33 (1,0,0)T 解組合解組合 (x1, x2, x3)T Z值值 約束約束 條件條件 過濾過濾 約束約束 (0, 0, 0)T (0, 0, 1)T (0, 1, 0)T (0, 1, 1)T (1, 0, 0)T (1, 0, 1)T (1, 1, 0)T (1, 1, 1)T * * 1,

43、0,1 8 T X Z OR:SM56 123 123 123 12 23 max325 22 44 3 46 0,1;1,2,3 j Zxxx xxx xxx xx xx xj 過濾約束過濾約束(目標(biāo)函數(shù)目標(biāo)函數(shù))： 3x1 - 2x2 + 5x35 (0,0,1)T 解組合解組合 (x1, x2, x3)T Z值值 約束約束 條件條件 過濾過濾 約束約束 (0, 0, 0)T (0, 0, 1)T (0, 1, 0)T (0, 1, 1)T (1, 0, 0)T (1, 0, 1)T (1, 1, 0)T (1, 1, 1)T * * 1,0,1 8 T X Z OR:SM57 123 1

44、23 123 23 max432 2534 433 1 0,1;1,2,3 j Zxxx xxx xxx xx xj 過濾約束：過濾約束： 4x1 + 3x2 + 2x3 0 (0,0,0)T 解組合解組合 (x1, x2, x3)T Z值值 約束約束 條件條件 過濾過濾 約束約束 (0, 0, 0)T (0, 0, 1)T (0, 1, 0)T (0, 1, 1)T (1, 0, 0)T (1, 0, 1)T (1, 1, 0)T (1, 1, 1)T * * 1,1,1 9 T X Z OR:SM58 123 123 123 23 max432 2534 433 1 0,1;1,2,3 j

45、 Zxxx xxx xxx xx xj 過濾約束：過濾約束： (0,0,1)T 4x1 + 3x2 + 2x3 2 解組合解組合 (x1, x2, x3)T Z值值 約束約束 條件條件 過濾過濾 約束約束 (0, 0, 0)T (0, 0, 1)T (0, 1, 0)T (0, 1, 1)T (1, 0, 0)T (1, 0, 1)T (1, 1, 0)T (1, 1, 1)T * * 1,1,1 9 T X Z OR:SM59 1234 1234 1234 1234 min2534 40 24244 1 0,1;1,2,3,4 j Zxxxx xxxx xxxx xxxx xj 過濾約束：過

46、濾約束： (1,1,1,1)T 2x1 +5x2 +3x3 +4x314 解組合解組合 (x1, x2, x3, x4)T Z 值值 約束約束 條件條件 過濾過濾 約束約束 (0, 0, 0, 0)T (0, 0, 0, 1)T (0, 0, 1, 0)T (0, 0, 1, 1)T (0, 1, 0, 0)T (1, 0, 0, 0)T (1, 1, 1, 1)T * * 0,0,0,1 4 T X Z OR:SM60 1234 1234 1234 1234 min2534 40 24244 1 0,1;1,2,3,4 j Zxxxx xxxx xxxx xxxx xj 過濾約束：過濾約束：

47、 (0,1,0,0)T 2x1 +5x2 +3x3 +4x35 解組合解組合 (x1, x2, x3, x4)T Z 值值 約束約束 條件條件 過濾過濾 約束約束 (0, 0, 0, 0)T (0, 0, 0, 1)T (0, 0, 1, 0)T (0, 0, 1, 1)T (0, 1, 0, 0)T (1, 0, 0, 0)T (1, 1, 1, 1)T * * 0,0,0,1 4 T X Z OR:SM61 六、匈牙利法六、匈牙利法 1955年，庫恩根據(jù)匈牙利數(shù)學(xué)家康尼格得年，庫恩根據(jù)匈牙利數(shù)學(xué)家康尼格得 出的結(jié)論，提出了求解指派問題的方法出的結(jié)論，提出了求解指派問題的方法 匈牙利法。匈牙

48、利法。 1、原理、原理 若指派問題的系數(shù)矩陣若指派問題的系數(shù)矩陣C = (cij)n n的某行 的某行 (或某列或某列)各元素分別減去一個常數(shù)各元素分別減去一個常數(shù)k，得到一個，得到一個 新的矩陣新的矩陣C = (cij)n n ，則兩個矩陣所對應(yīng)的指 ，則兩個矩陣所對應(yīng)的指 派問題的最優(yōu)解相同。派問題的最優(yōu)解相同。 OR:SM62 六、匈牙利法六、匈牙利法 2、求解步驟、求解步驟 (1)讓效率矩陣中的每行每列都出現(xiàn)零元素。讓效率矩陣中的每行每列都出現(xiàn)零元素。 (2)尋找獨立零元素尋找獨立零元素(分別位于不同的行和列中分別位于不同的行和列中)。 若獨立零元素個數(shù)等于若獨立零元素個數(shù)等于n，計算

49、停止；若小，計算停止；若小 于于n，則繼續(xù)尋找獨立零元素，至其數(shù)量為，則繼續(xù)尋找獨立零元素，至其數(shù)量為n。 (3)變換矩陣元素，將獨立零元素改寫為變換矩陣元素，將獨立零元素改寫為1，其，其 它元素改寫為它元素改寫為0，即得到最優(yōu)解。，即得到最優(yōu)解。 OR:SM63 匈牙利法舉例：匈牙利法舉例： 48715 12 79 17 14 10 69 1287 67 14610 69 12 106 C 4 7 6 6 6 OR:SM64 每行減去該行最小元素后：每行減去該行最小元素后： 04311 8 02 1073 03621 01804 03640 C 13 OR:SM65 第第2 2、3 3列分別

50、減去其最小元素后：列分別減去其最小元素后： 030 11 8 01773 02321 00504 02340 C OR:SM66 尋找獨立零元素：尋找獨立零元素： 030 11 8 01773 02321 00504 02340 C OR:SM67 第第2 2、3 3行分別減去最小元素行分別減去最小元素( (除除0 0外外) )： 030 11 8 1 0662 1 1210 00504 02340 C OR:SM68 第第1 1列元素加上列元素加上“1” 1” ： 130 11 8 00662 01210 10504 12340 C OR:SM69 繼續(xù)尋找獨立零元素：繼續(xù)尋找獨立零元素：

51、130 11 8 00662 01210 10504 12340 C OR:SM70 求出最優(yōu)解：求出最優(yōu)解： * 00100 01000 10000 00010 00001 X * 6976634Z * 7966634Z OR:SM71 匈牙利法練習(xí)匈牙利法練習(xí)1 1： 215 134 10414 15 914 16 13 78119 C OR:SM72 匈牙利法練習(xí)匈牙利法練習(xí)1 1： 215 1340 13 112 10414 156010 11 914 16 130574 781190142 C OR:SM73 匈牙利法練習(xí)匈牙利法練習(xí)1 1： 0 13 1120 1370 6010 116069 05740532 01420100 C OR:SM74 匈牙利法練習(xí)匈牙利法練