運(yùn)籌學(xué)基礎(chǔ)整數(shù)規(guī)劃PPT

1、關(guān)于運(yùn)籌學(xué)基礎(chǔ)整數(shù)規(guī)劃第一張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月24.1整數(shù)規(guī)劃解決整數(shù)規(guī)劃問題不能僅僅是在線性規(guī)劃求解中，將解“四舍五入”就行了，因?yàn)榛蟮慕獠灰姷檬强尚薪?；即便是可行解，也不一定是?yōu)解。注意：在前面討論的線性規(guī)劃問題中，有些最優(yōu)解可能是分?jǐn)?shù)或小數(shù)，但對(duì)于某些具體的問題，常有要求解答必須是整數(shù)的情形（稱為整數(shù)解），解決這樣的問題即為整數(shù)規(guī)劃。一、整數(shù)規(guī)劃問題的提出整數(shù)規(guī)劃第二張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月3【例1】某廠擬用集裝箱托運(yùn)甲乙兩種貨物，每箱的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如表：?jiǎn)杻煞N貨物各托運(yùn)多少箱，可使利潤(rùn)為最大？建立線性規(guī)劃模型為： ma

2、xZ= 20 x1 +10 x2 5x1 +4x2 24 2x1 +5 x2 13x1 0, x2 0利用單純形法求得最優(yōu)解為：x14.8，x20，maxZ96整數(shù)規(guī)劃第三張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月4討論：如何調(diào)整滿足整數(shù)解（1）四舍五入：x15，x20，Z100但破壞了體積限制條件，因而不是可行解（2）舍小數(shù)：x14，x20，Z80是可行解，但不是最優(yōu)解，因 x14，x21，Z90也是可行解C(4.8,0) maxZ= 20 x1 +10 x2 5x1 +4x2 24 2x1 +5 x2 13x1 0, x2 0 x2x111023234567+B(4,1)x14.8，x20

3、，maxZ96非整數(shù)解整數(shù)規(guī)劃第四張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月5二、整數(shù)規(guī)劃的求解方法1、分枝定解法2、割平面法3、利用EXCEL求解整數(shù)規(guī)劃第五張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月61、整數(shù)規(guī)劃之分枝定解法問題A： maxZ= 20 x1 +10 x2 5x1 +4x2 24 2x1 +5 x2 13x1 0, x2 0 x1, x2 整數(shù)問題B： maxZ= 20 x1 +10 x2 5x1 +4x2 24 2x1 +5 x2 13x1 0, x2 0從問題B開始，若其最優(yōu)解不符合A的整數(shù)條件，那么B的最優(yōu)目標(biāo)函數(shù)必是A的最優(yōu)目標(biāo)函數(shù)Z*的上界，記作，（如果是求最小值，

4、即為下界）分枝定界法就是將B的可行域分成子區(qū)域的方法，逐步減小和增大，最終逼近Z* 。寫出整數(shù)規(guī)劃問題A的伴隨線性規(guī)劃問題為B 而A的任意可行解的目標(biāo)函數(shù)值將是Z*的一個(gè)下界，記作，（如果是求最小值，即為上界） Z* 整數(shù)規(guī)劃第六張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月7第一步：尋找替代問題并求解問題B： maxZ= 20 x1 +10 x2 5x1 +4x2 24 2x1 +5 x2 13x1 0, x2 0利用單純形法求得最優(yōu)解為：x14.8，x20，Z96問題B1： maxZ= 20 x1 +10 x2 5x1 +4x2 24 2x1 +5 x2 13 x1 4x1 0, x2 0問題

5、B2： maxZ= 20 x1 +10 x2 5x1 +4x2 24 2x1 +5 x2 13 x1 5x1 0, x2 0 0 Z* 96利用單純形法求得最優(yōu)解為：x14，x21，Z90無解；第二步：分枝與定界x2x111023234567+最后得最優(yōu)解為：x14，x21，Z90整數(shù)規(guī)劃第七張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月8【例2】問題A： maxZ= 40 x1 +90 x2 9x1 +7x2 56 7x1 +20 x2 70 x1 0, x2 0 x1, x2 整數(shù)利用單純形法求解問題B得最優(yōu)解為：x14.81，x21.82，Z356問題B2： maxZ= 40 x1 +90

6、x2 9x1 +7x2 56 7x1 +20 x2 70 x1 5x1 0, x2 0 0 Z* 356利用單純形法求得最優(yōu)解為：x14，x22.1，Z349利用單純形法求得最優(yōu)解為：x15，x21.57，Z341問題B： maxZ= 40 x1 +90 x2 9x1 +7x2 56 7x1 +20 x2 70 x1 0, x2 0問題B1： maxZ= 40 x1 +90 x2 9x1 +7x2 56 7x1 +20 x2 70 x1 4 x1 0, x2 0 0 Z* 349第一步：尋找替代問題并求解第二步：分枝與定界整數(shù)規(guī)劃第八張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月9 分枝定解法求解

7、（續(xù)）利用單純形法求得最優(yōu)解為：x14，x22，Z340利用單純形法求得最優(yōu)解為：x11.52，x23，Z327問題B11： maxZ= 40 x1 +90 x2 9x1 +7x2 56 7x1 +20 x2 70 x1 4 x2 2 x1 0, x2 0 340 Z* 349x14x22.1Z349問題B12： maxZ= 40 x1 +90 x2 9x1 +7x2 56 7x1 +20 x2 70 x1 4 x2 3 x1 0, x2 0問題B21： maxZ= 40 x1 +90 x2 9x1 +7x2 56 7x1 +20 x2 70 x1 5x2 1x1 0, x2 0 x15x21

8、.57Z341x15.44，x21，Z308問題B21： maxZ= 40 x1 +90 x2 9x1 +7x2 56 7x1 +20 x2 70 x1 5x2 2x1 0, x2 0無可行解整數(shù)規(guī)劃第九張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月10問題Bx14.81x21.82Z356問題B1x14.00 x22.1Z349問題Bx15.00 x21.57Z341問題B11x14.00 x22.00Z340問題B12x11.42x23.00Z327問題B21x15.44x21.00Z308問題B22無可行解x1 4x1 5x2 2x2 3x2 1x2 2 0 Z* 356 0 Z* 349

9、340 Z* 349Z* 340 分枝定解法求解框圖整數(shù)規(guī)劃第十張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月11分枝為問題1、2后解可能出現(xiàn)如下幾種情況序號(hào)問題1問題2說 明1無可行解無可行解整數(shù)規(guī)劃無可行解2無可行解整數(shù)解此整數(shù)解即最優(yōu)解3無可行解非整數(shù)解對(duì)問題2繼續(xù)分枝4整數(shù)解整數(shù)解較優(yōu)的一個(gè)為最優(yōu)解5整數(shù)解，目標(biāo)函數(shù)優(yōu)于問題2非整數(shù)解問題1的解即最優(yōu)解6整數(shù)解非整數(shù)解，目標(biāo)函數(shù)優(yōu)于問題1問題1停止分枝(剪枝)，其整數(shù)解為界，對(duì)問題2繼續(xù)分枝情況 2, 4, 5 找到最優(yōu)解情況 3 在縮減的域上繼續(xù)分枝定界法情況 6 問題 1 的整數(shù)解作為界被保留，用于以后與問題 2 的后續(xù)分枝所得到的整數(shù)

10、解進(jìn)行比較，結(jié)論如情況 4情況 1 無可行解整數(shù)規(guī)劃第十一張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月12分枝定界法的一般步驟如下 第一步，先不考慮原問題的整數(shù)限制，求解相應(yīng)的松弛問題，若求得最優(yōu)解，檢查它是否符合整數(shù)約束條件；如符合整數(shù)約束條件，即轉(zhuǎn)下一步。 第二步，定界。在各分枝問題中，找出目標(biāo)函數(shù)值最大者Z*作為整數(shù)規(guī)劃最優(yōu)值 的上界，從已符合整數(shù)條件的分枝中，找出目標(biāo)函數(shù)值最大者作為下界，即 第三步，分枝。根據(jù)對(duì)變量重要性的了解，在最優(yōu)解中選擇一個(gè)不符合整數(shù)條件的xj ，令 xj=bj ，(bj不為整數(shù))則用下列兩個(gè)約束條件： 第四步，應(yīng)用對(duì)目標(biāo)函數(shù)估界的方法，或?qū)δ骋环种χ匾缘牧私猓?/p>

11、確定出首先要解的某一分枝的后繼問題，并解此問題。若所獲得的最優(yōu)解符合整數(shù)條件，則就是原問題的解，若不符合整數(shù)條件，再回到第二步，并參照第四步終止后繼問題。整數(shù)規(guī)劃第十二張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月13分枝定界法的EXCEL演示 整數(shù)規(guī)劃第十三張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月142、割平面解法割平面法也是求解整數(shù)規(guī)劃問題常用方法之一。【基本思路】 如果所得到最優(yōu)解不滿足整數(shù)約束條件，則在此非整數(shù)解的基礎(chǔ)上增加新的約束條件重新求解。這個(gè)新增加的約束條件的作用就是去切割相應(yīng)松弛問題的可行域，即割去松弛問題的部分非整數(shù)解(包括原已得到的非整數(shù)最優(yōu)解)。而把所有的整數(shù)解都保留下來

12、，故稱新增加的約束條件為割平面。當(dāng)經(jīng)過多次切割后，就會(huì)使被切割后保留下來的可行域上有一個(gè)坐標(biāo)均為整數(shù)的頂點(diǎn)，它恰好就是所求問題的整數(shù)最優(yōu)解。即切割后所對(duì)應(yīng)的松弛問題，與原整數(shù)規(guī)劃問題具有相同的最優(yōu)解。先不考慮整數(shù)約束條件，求松弛問題的最優(yōu)解，如果獲得整數(shù)最優(yōu)解，即為所求，運(yùn)算停止。整數(shù)規(guī)劃第十四張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月15 割平面法的具體求解步驟如下：1. 對(duì)于所求的整數(shù)規(guī)劃問題，先不考慮整數(shù)約束條件，求解相應(yīng)的松弛問題2. 如果該問題無可行解或已取得整數(shù)最優(yōu)解，則運(yùn)算停止；前者表示原問題也無可行解，后者表示已求得整數(shù)最優(yōu)解。如果有一個(gè)或更多個(gè)變量取值不滿足整數(shù)條件，則選擇某

13、個(gè)變量建立割平面。3. 增加為割平面的新約束條件，用前面介紹的靈敏分析的方法繼續(xù)求解，返回1。整數(shù)規(guī)劃第十五張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月16【例1】求解下列整數(shù)規(guī)劃問題解：引入松弛變量，寫成標(biāo)準(zhǔn)形式（1）+=,0,;2054;62;max432142132121xxxxxxxxxxxxz（2）對(duì)上述模型不考慮整數(shù)條件，用單純形法求解相應(yīng)松弛問題的最終單純形表為Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x411005/3105/6-1/68/301-2/31/3x1x211-13/300-1/6-1/6最優(yōu)解為x15/3，x28/3不是整數(shù)解整數(shù)規(guī)劃第十六張，PPT共四十一頁(yè)，創(chuàng)作于2

14、022年6月17 顯然， x1=5/3,x2=8/3為非整數(shù)解。為求得整數(shù)解，想辦法在原約束條件的基礎(chǔ)下引入一個(gè)新的約束條件，以保證一個(gè)或幾個(gè)變量取值為整數(shù)。為此，選擇分?jǐn)?shù)部分較大的非整數(shù)變量，如x2 ，寫出如下表達(dá)式：將上式的所有變量的系數(shù)及右端常數(shù)均改寫成一個(gè)整數(shù)與一個(gè)非負(fù)真分?jǐn)?shù)之和的形式。上式可以改寫成若將帶有整數(shù)系數(shù)的變量留在方程的左邊，其余移到方程的右邊，則有 由于要求變量取值為正整數(shù)，方程的左邊必為整數(shù)。當(dāng)然，方程的右邊也應(yīng)為整數(shù)。又x30,x40于是，必有x31,x41（3）（4）0此時(shí)，也可以選擇x2-x3-20，只是因?yàn)橄确治龀龇匠逃叶?整數(shù)規(guī)劃第十七張，PPT共四十一頁(yè)，創(chuàng)

15、作于2022年6月18 整理后得為了直觀地在圖形上描述，可將(2)式的兩個(gè)約束方程代入(5)式即+=且為整數(shù),0,;2054;62;max432142132121xxxxxxxxxxxxz則(5)式成為（5）這就是割平面的方程B(5/3,8/3)x1x2246246-20-4AECO加入新的約束條件，便形成新的線性規(guī)劃問題，其可行域?yàn)樾碌耐辜疧AEC。 即圖中紅色直線割去了紅色直線以外的ABE部分，其中包括原所求得的非整數(shù)最優(yōu)解點(diǎn)B(5/3,8/3)。三個(gè)方程是等價(jià)的，任意一個(gè)都可增加的新的約束條件整數(shù)規(guī)劃第十八張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月19 建立割平面以后，便可以把割平面方程

16、作為新的約束條件加到原整數(shù)規(guī)劃問題(2)式中，在仍然不考慮整數(shù)條件的情況下，利用單純形法或?qū)ε紗渭冃畏ɡ^續(xù)求解。以選擇第一個(gè)為例，引入松馳變量x5，代入新增加的約束條件中從上面的推導(dǎo)過程可以看出，新約束對(duì)原約束方程起到了這樣的作用：對(duì)整數(shù)規(guī)劃(1)式所對(duì)應(yīng)的線性規(guī)劃的可行域，保留了其中的所有整數(shù)可行解，但割掉了一部分非整數(shù)解。三個(gè)約束條件任選其一-1/3x3 -1/3x4 + x5= -2/3整數(shù)規(guī)劃第十九張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月20Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x5110005/3105/6-1/608/301-2/31/30-2/300-1/3-1/31x1x

17、2x5110-13/300-1/6-1/60Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x5110000100-15/2401 01 -2x1x2x6110-400 00-1/220011-3x10， x24為最優(yōu)解，最優(yōu)值為Z4整數(shù)規(guī)劃第二十張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月21Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x5110005/3105/6-1/608/301-2/31/30-2/300-1/3-1/31x1x2x5110-13/300-1/6-1/60Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x51100021010-1/2201-10 1x1x2x6110-400 00-

18、1/220011-3x12， x22為最優(yōu)解，最優(yōu)值為Z4另一選擇第二十一張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月22分析因?yàn)樯鲜龅木€性規(guī)劃的最優(yōu)解已是整數(shù)解，所以得整數(shù)規(guī)劃問題（1）的最優(yōu)解：E(2,2)A(0,4)x1x2246246-20-4x1=0， x2=4。此最優(yōu)解位于圖A點(diǎn)。 x1=2， x2=2。此最優(yōu)解位于圖E點(diǎn)。整數(shù)規(guī)劃第二十二張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月23【例2】 求解下列整數(shù)規(guī)劃問題解：引入松弛變量，寫成標(biāo)準(zhǔn)形式：（1）（2）第一步：對(duì)上述模型不考慮整數(shù)條件，用單純形法求解相應(yīng)松弛問題的最終單純形表為Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x432005

19、/2011/2-1/213/410-1/43/4x2x123 -59/400-1/4-5/4最優(yōu)解為x25/2，x113/4此最優(yōu)解非整數(shù)解整數(shù)規(guī)劃第二十三張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月24 第二步：x1 13/4 , x25/2為非整數(shù)解，找出非整數(shù)解變量中分?jǐn)?shù)部分最大的一個(gè)基變量x2，寫出這一行的約束：將上式的所有變量的系數(shù)及右端常數(shù)均改寫成一個(gè)整數(shù)與一個(gè)非負(fù)真分?jǐn)?shù)之和的形式得：若將帶有整數(shù)系數(shù)的變量整數(shù)項(xiàng)留在方程的左邊，其余移到方程的右邊，則有 由于要求變量取值為正整數(shù)，方程的左邊必為整數(shù)。方程的右邊也應(yīng)為整數(shù)。又由于x30,x40于是，有方程右端小于等于零。0整數(shù)規(guī)劃第二十

20、四張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月25 即為了直觀地在圖形上描述，可將標(biāo)準(zhǔn)式的兩個(gè)約束方程代入上式，則成為- (14-2x1-3x2) (9-2x1-x2) -1三個(gè)方程的任意一個(gè)都可做為后面增加的新的約束條件整理后得2x1+2x211這就是割平面的方程整數(shù)規(guī)劃第二十五張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月26 B(13/4,5/2)AEC2x1+2x211F加入新的約束條件，便形成新的線性規(guī)劃問題，其可行域?yàn)樾碌耐辜疧AEFC。即圖中所示的紅色直線的下半部分。顯然它割去了除紅色直線上所有點(diǎn)以外的BEF部分，其中包括原所求得的非整數(shù)最優(yōu)解點(diǎn)B(13/4,5/2)。x1x22462

21、46-20-4O這就是割平面的方程整數(shù)規(guī)劃第二十六張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月27 建立割平面以后，便可以把割平面方程作為新的約束條件加到原整數(shù)規(guī)劃問題中，在仍然不考慮整數(shù)條件的情況下，利用單純形法或?qū)ε紗渭冃畏ɡ^續(xù)求解。將其作為新的約束條件，加入到前面的最終表中，便形成新的線性規(guī)劃問題。用對(duì)偶單純形法求解。第三步：引入松馳變量x5，代入新增加的約束條件中-1/2x3 -1/2x4 +x5-1/22x1+2x211任意一個(gè)都可做為增加的新的約束條件整數(shù)規(guī)劃第二十七張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月28Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x5320005/2011/2

22、-1/2013/410-1/40-1/200-1/2-1/21x2x1x5230-59/400-1/4-5/40Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x5110002010-117/21001 -1/2x2x1x3230-29/200 0-1-1/210011-2x17/2， x22為最優(yōu)解，最優(yōu)值為Z29/2，不是整數(shù)解第二十八張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月29 由于仍有非整數(shù)解，重復(fù)第二步： 寫出另一行的約束：將上式的所有變量的系數(shù)及右端常數(shù)均改寫成一個(gè)整數(shù)與一個(gè)非負(fù)真分?jǐn)?shù)之和的形式得：若將帶有整數(shù)系數(shù)的變量整數(shù)項(xiàng)留在方程的左邊，其余移到方程的右邊，則有此得到新約束：整數(shù)規(guī)

23、劃第二十九張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月30 2x1+2x211又加入的新約束條件，便形成新的線性規(guī)劃問題，其可行域又隨之改變B(13/4,5/2)AECFx1x2246246-20-4Ox1+x25整數(shù)規(guī)劃第三十張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月31 2010-110將其作為新的約束條件，加入到前面的最終表中，便形成新的線性規(guī)劃問題。用對(duì)偶單純形法求解。第三步：引入松馳變量x6，代入新增加的約束條件中-1/2 x5 + x6-1/2Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x5x63200007/21001 -1/20 x2x1x3x62300-29/200 0-1-1/

24、2010011-20-1/20000-1/21新增加的約束條件整數(shù)規(guī)劃第三十一張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月32 Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x5x632000041001 0-1x2x1x3x62300-1400 0-10-1300110-41010-102100001-2x14， x21為最優(yōu)解，最優(yōu)值為Z14，是整數(shù)解整數(shù)規(guī)劃第三十二張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月33 E(1,4)因?yàn)樯鲜龅木€性規(guī)劃的最優(yōu)解已是整數(shù)解，所以得整數(shù)規(guī)劃問題的最優(yōu)解：x1=1， x2=4。maxZ14B(13/4,5/2)AECFx1x2246246-20-4O整數(shù)規(guī)劃第

25、三十三張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月34【例3】 求解下列整數(shù)規(guī)劃問題解引入松弛變量，寫成標(biāo)準(zhǔn)形式：（1）+=,0,;43;1-;max432142132121xxxxxxxxxxxxz（2）對(duì)上述模型不考慮整數(shù)條件，用單純形法求解相應(yīng)松弛問題的最終單純形表為Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x411003/410-1/41/47/4013/41/4x1x211-5/200-1/2-1/2+=且為整數(shù),0,;43;1-;max21212121xxxxxxxxz最優(yōu)解為x13/4，x27/4整數(shù)規(guī)劃第三十四張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月35 顯然， x13/4，x27

26、/4 為非整數(shù)解。找出非整數(shù)解變量中分?jǐn)?shù)部分最大的一個(gè)基變量，寫出相應(yīng)的約束：將上式的所有變量的系數(shù)及右端常數(shù)均改寫成一個(gè)整數(shù)與一個(gè)非負(fù)真分?jǐn)?shù)之和的形式。據(jù)此，上式可以改寫成若將帶有整數(shù)系數(shù)的變量整數(shù)項(xiàng)留在方程的左邊，其余移到方程的右邊，則有 ,4/34/14/1431=+-xxx,4/74/14/3432=+xxx,4/30)4/10()4/31()01(431+=+-+xxx,4/31)4/10()4/30()01(432+=+ +xxx43314/14/34/3xxxx-=-4324/14/34/31xxx-=-整數(shù)規(guī)劃第三十五張，PPT共四十一頁(yè)，創(chuàng)作于2022年6月36 整理后得為了直觀地在圖形上描述，可將標(biāo)準(zhǔn)式的兩個(gè)約束方程代入上式，則成為由于要求變量取值為正整數(shù)，方程的左邊必為整數(shù)。當(dāng)然，方程的右邊也應(yīng)為整數(shù)。又由于x30,x40于是，有,04/14/34/343-xx-3x3 -x4 -3x2 1+=且為整數(shù),0,;43;1-;max432142132121xxxxxxxxxxxxz-3(1+x1-x2) (4