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

關(guān)于運(yùn)籌學(xué)基礎(chǔ)整數(shù)規(guī)劃第一頁，共四十一頁，2022年，8月28日2§4.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ī)劃第二頁，共四十一頁，2022年，8月28日3【例1】某廠擬用集裝箱托運(yùn)甲乙兩種貨物，每箱的體積、重量、可獲利潤以及托運(yùn)所受限制如表：問兩種貨物各托運(yùn)多少箱，可使利潤為最大？建立線性規(guī)劃模型為：

maxZ=

20x1+10x25x1+4x2≤242x1+5x2≤13

x1≥0,x2≥0利用單純形法求得最優(yōu)解為：x1＝4.8，x2＝0，maxZ＝96整數(shù)規(guī)劃第三頁，共四十一頁，2022年，8月28日4討論：如何調(diào)整滿足整數(shù)解（1）四舍五入：x1＝5，x2＝0，Z＝100但破壞了體積限制條件，因而不是可行解（2）舍小數(shù)：x1＝4，x2＝0，Z＝80是可行解，但不是最優(yōu)解，因x1＝4，x2＝1，Z＝90也是可行解C(4.8,0)

maxZ=

20x1+10x25x1+4x2≤242x1+5x2≤13

x1≥0,x2≥0x2x111023234567++++++++++++B(4,1)x1＝4.8，x2＝0，maxZ＝96非整數(shù)解整數(shù)規(guī)劃第四頁，共四十一頁，2022年，8月28日5二、整數(shù)規(guī)劃的求解方法1、分枝定解法2、割平面法3、利用EXCEL求解整數(shù)規(guī)劃第五頁，共四十一頁，2022年，8月28日61、整數(shù)規(guī)劃之分枝定解法問題A：maxZ=

20x1+10x25x1+4x2≤242x1+5x2≤13

x1≥0,x2≥0

x1,x2整數(shù)問題B：maxZ=

20x1+10x25x1+4x2≤242x1+5x2≤13

x1≥0,x2≥0從問題B開始，若其最優(yōu)解不符合A的整數(shù)條件，那么B的最優(yōu)目標(biāo)函數(shù)必是A的最優(yōu)目標(biāo)函數(shù)Z*的上界，記作，（如果是求最小值，即為下界）

分枝定界法就是將B的可行域分成子區(qū)域的方法，逐步減小和增大，最終逼近Z*。寫出整數(shù)規(guī)劃問題A的伴隨線性規(guī)劃問題為B

而A的任意可行解的目標(biāo)函數(shù)值將是Z*的一個(gè)下界，記作，（如果是求最小值，即為上界）

≤Z*≤整數(shù)規(guī)劃第六頁，共四十一頁，2022年，8月28日7第一步：尋找替代問題并求解問題B：maxZ=

20x1+10x25x1+4x2≤242x1+5x2≤13

x1≥0,x2≥0利用單純形法求得最優(yōu)解為：x1＝4.8，x2＝0，Z＝96問題B1：maxZ=

20x1+10x2

5x1+4x2≤24

2x1+5x2≤13

x1≤4

x1≥0,x2≥0問題B2：maxZ=

20x1+10x2

5x1+4x2≤24

2x1+5x2≤13

x1≥5

x1≥0,x2≥0＝0≤Z*≤96＝利用單純形法求得最優(yōu)解為：x1＝4，x2＝1，Z＝90無解；第二步：分枝與定界x2x111023234567++++++++++++最后得最優(yōu)解為：x1＝4，x2＝1，Z＝90整數(shù)規(guī)劃第七頁，共四十一頁，2022年，8月28日8【例2】問題A：maxZ=

40x1+90x29x1+7x2≤567x1+20x2≤70

x1≥0,x2≥0

x1,x2整數(shù)利用單純形法求解問題B得最優(yōu)解為：x1＝4.81，x2＝1.82，Z＝356問題B2：maxZ=

40x1+90x29x1+7x2≤567x1+20x2≤70

x1≥5

x1≥0,x2≥0＝0≤Z*≤356＝利用單純形法求得最優(yōu)解為：x1＝4，x2＝2.1，Z＝349利用單純形法求得最優(yōu)解為：x1＝5，x2＝1.57，Z＝341問題B：maxZ=

40x1+90x29x1+7x2≤567x1+20x2≤70

x1≥0,x2≥0問題B1：maxZ=

40x1+90x29x1+7x2≤567x1+20x2≤70

x1≤4

x1≥0,x2≥0＝0≤Z*≤349＝第一步：尋找替代問題并求解第二步：分枝與定界整數(shù)規(guī)劃第八頁，共四十一頁，2022年，8月28日9

分枝定解法求解（續(xù)）利用單純形法求得最優(yōu)解為：x1＝4，x2＝2，Z＝340利用單純形法求得最優(yōu)解為：x1＝1.52，x2＝3，Z＝327問題B11：maxZ=

40x1+90x29x1+7x2≤567x1+20x2≤70

x1≤4

x2≤2

x1≥0,x2≥0＝340≤Z*≤349＝x1＝4x2＝2.1Z＝349問題B12：maxZ=

40x1+90x29x1+7x2≤567x1+20x2≤70

x1≤4

x2≥3

x1≥0,x2≥0問題B21：maxZ=

40x1+90x29x1+7x2≤567x1+20x2≤70

x1≥5

x2≤1

x1≥0,x2≥0x1＝5x2＝1.57Z＝341x1＝5.44，x2＝1，Z＝308問題B21：maxZ=

40x1+90x29x1+7x2≤567x1+20x2≤70

x1≥5

x2≥2

x1≥0,x2≥0無可行解整數(shù)規(guī)劃第九頁，共四十一頁，2022年，8月28日10問題Bx1＝4.81x2＝1.82Z＝356問題B1x1＝4.00x2＝2.1Z＝349問題Bx1＝5.00x2＝1.57Z＝341問題B11x1＝4.00x2＝2.00Z＝340問題B12x1＝1.42x2＝3.00Z＝327問題B21x1＝5.44x2＝1.00Z＝308問題B22無可行解x1≤4x1≥5x2≤2x2≥3x2≤1x2≥2＝0≤Z*≤356＝＝0≤Z*≤349＝＝340≤Z*≤349＝Z*＝340

分枝定解法求解框圖整數(shù)規(guī)劃第十頁，共四十一頁，2022年，8月28日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ù)解進(jìn)行比較，結(jié)論如情況4情況1

無可行解整數(shù)規(guī)劃第十一頁，共四十一頁，2022年，8月28日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=b’j

，(b’j不為整數(shù))則用下列兩個(gè)約束條件：

第四步，應(yīng)用對(duì)目標(biāo)函數(shù)估界的方法，或?qū)δ骋环种χ匾缘牧私?，確定出首先要解的某一分枝的后繼問題，并解此問題。若所獲得的最優(yōu)解符合整數(shù)條件，則就是原問題的解，若不符合整數(shù)條件，再回到第二步，并參照第四步終止后繼問題。整數(shù)規(guī)劃第十二頁，共四十一頁，2022年，8月28日13分枝定界法的EXCEL演示

整數(shù)規(guī)劃第十三頁，共四十一頁，2022年，8月28日142、割平面解法

割平面法也是求解整數(shù)規(guī)劃問題常用方法之一?！净舅悸贰?/p>

如果所得到最優(yōu)解不滿足整數(shù)約束條件，則在此非整數(shù)解的基礎(chǔ)上增加新的約束條件重新求解。這個(gè)新增加的約束條件的作用就是去切割相應(yīng)松弛問題的可行域，即割去松弛問題的部分非整數(shù)解(包括原已得到的非整數(shù)最優(yōu)解)。而把所有的整數(shù)解都保留下來，故稱新增加的約束條件為割平面。

當(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ī)劃第十四頁，共四十一頁，2022年，8月28日15

割平面法的具體求解步驟如下：1.對(duì)于所求的整數(shù)規(guī)劃問題，先不考慮整數(shù)約束條件，求解相應(yīng)的松弛問題2.如果該問題無可行解或已取得整數(shù)最優(yōu)解，則運(yùn)算停止；前者表示原問題也無可行解，后者表示已求得整數(shù)最優(yōu)解。如果有一個(gè)或更多個(gè)變量取值不滿足整數(shù)條件，則選擇某個(gè)變量建立割平面。3.增加為割平面的新約束條件，用前面介紹的靈敏分析的方法繼續(xù)求解，返回1。整數(shù)規(guī)劃第十五頁，共四十一頁，2022年，8月28日16【例1】求解下列整數(shù)規(guī)劃問題解：引入松弛變量，寫成標(biāo)準(zhǔn)形式（1）???íì3＝++＝+++=,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)解為x1＝5/3，x2＝8/3不是整數(shù)解整數(shù)規(guī)劃第十六頁，共四十一頁，2022年，8月28日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ù)。又x3≥0,x4≥0于是，必有x3≥1,x4≥1（3）（4）≤0此時(shí)，也可以選擇x2-x3-2≤0，只是因?yàn)橄确治龀龇匠逃叶恕?整數(shù)規(guī)劃第十七頁，共四十一頁，2022年，8月28日18

整理后得

為了直觀地在圖形上描述，可將(2)式的兩個(gè)約束方程代入(5)式即???íì3＝++＝+++=且為整數(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ī)劃第十八頁，共四十一頁，2022年，8月28日19

建立割平面以后，便可以把割平面方程作為新的約束條件加到原整數(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ī)劃第十九頁，共四十一頁，2022年，8月28日20

Cj比值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ù)jx1x2x3x4x5110000100-15/240101-2x1x2x6110-40000-1/220011-3x1＝0，x2＝4為最優(yōu)解，最優(yōu)值為Z＝4整數(shù)規(guī)劃第二十頁，共四十一頁，2022年，8月28日21

Cj比值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-101x1x2x6110-40000-1/220011-3x1＝2，x2＝2為最優(yōu)解，最優(yōu)值為Z＝4另一選擇第二十一頁，共四十一頁，2022年，8月28日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ī)劃第二十二頁，共四十一頁，2022年，8月28日23【例2】求解下列整數(shù)規(guī)劃問題解：引入松弛變量，寫成標(biāo)準(zhǔn)形式：（1）（2）

第一步：對(duì)上述模型不考慮整數(shù)條件，用單純形法求解相應(yīng)松弛問題的最終單純形表為Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x432005/2011/2-1/213/410-1/43/4x2x123-59/400-1/4-5/4最優(yōu)解為x2＝5/2，x1＝13/4此最優(yōu)解非整數(shù)解整數(shù)規(guī)劃第二十三頁，共四十一頁，2022年，8月28日24

第二步：x1

＝13/4

,x2＝5/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ù)。又由于x3≥0,x4≥0于是，有方程右端小于等于零。≤0整數(shù)規(guī)劃第二十四頁，共四十一頁，2022年，8月28日25

即

為了直觀地在圖形上描述，可將標(biāo)準(zhǔn)式的兩個(gè)約束方程代入上式，則成為-(14-2x1-3x2)

–(9-2x1-x2)≤-1三個(gè)方程的任意一個(gè)都可做為后面增加的新的約束條件整理后得2x1+2x2≤11這就是割平面的方程整數(shù)規(guī)劃第二十五頁，共四十一頁，2022年，8月28日26

B(13/4,5/2)AEC2x1+2x2≤11F

加入新的約束條件，便形成新的線性規(guī)劃問題，其可行域?yàn)樾碌耐辜疧AEFC。即圖中所示的紅色直線的下半部分。顯然它割去了除紅色直線上所有點(diǎn)以外的△BEF部分，其中包括原所求得的非整數(shù)最優(yōu)解點(diǎn)B(13/4,5/2)。x1x2246246-20-4O這就是割平面的方程整數(shù)規(guī)劃第二十六頁，共四十一頁，2022年，8月28日27

建立割平面以后，便可以把割平面方程作為新的約束條件加到原整數(shù)規(guī)劃問題中，在仍然不考慮整數(shù)條件的情況下，利用單純形法或?qū)ε紗渭冃畏ɡ^續(xù)求解。

將其作為新的約束條件，加入到前面的最終表中，便形成新的線性規(guī)劃問題。用對(duì)偶單純形法求解。

第三步：引入松馳變量x5，代入新增加的約束條件中-1/2x3-1/2x4

+x5＝-1/22x1+2x2≤11任意一個(gè)都可做為增加的新的約束條件整數(shù)規(guī)劃第二十七頁，共四十一頁，2022年，8月28日28

Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x5320005/2011/2-1/2013/410-1/4?0-1/200-1/2-1/21x2x1x5230-59/400-1/4-5/40Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x5110002010-117/21001-1/2x2x1x3230-29/2000-1-1/210011-2x1＝7/2，x2＝2為最優(yōu)解，最優(yōu)值為Z＝29/2，不是整數(shù)解第二十八頁，共四十一頁，2022年，8月28日29

由于仍有非整數(shù)解，重復(fù)第二步：寫出另一行的約束：將上式的所有變量的系數(shù)及右端常數(shù)均改寫成一個(gè)整數(shù)與一個(gè)非負(fù)真分?jǐn)?shù)之和的形式得：

若將帶有整數(shù)系數(shù)的變量整數(shù)項(xiàng)留在方程的左邊，其余移到方程的右邊，則有此得到新約束：整數(shù)規(guī)劃第二十九頁，共四十一頁，2022年，8月28日30

2x1+2x2≤11

又加入的新約束條件，便形成新的線性規(guī)劃問題，其可行域又隨之改變B(13/4,5/2)AECFx1x2246246-20-4Ox1+x2≤5整數(shù)規(guī)劃第三十頁，共四十一頁，2022年，8月28日31

2010-110

將其作為新的約束條件，加入到前面的最終表中，便形成新的線性規(guī)劃問題。用對(duì)偶單純形法求解。

第三步：引入松馳變量x6，代入新增加的約束條件中-1/2x5+x6＝-1/2Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x5x63200007/2100

1-1/20x2x1x3x62300-29/2000-1-1/2010011-20-1/20000-1/21新增加的約束條件整數(shù)規(guī)劃第三十一頁，共四十一頁，2022年，8月28日32

Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x5x63200004100

10-1x2x1x3x62300-14000-10-1300110-41010-102100001-2x1＝4，x2＝1為最優(yōu)解，最優(yōu)值為Z＝14，是整數(shù)解整數(shù)規(guī)劃第三十二頁，共四十一頁，2022年，8月28日33

E‘(1,4)因?yàn)樯鲜龅木€性規(guī)劃的最優(yōu)解已是整數(shù)解，所以得整數(shù)規(guī)劃問題的最優(yōu)解：x1=1，x2=4。maxZ＝14B(13/4,5/2)AECFx1x2246246-20-4O整數(shù)規(guī)劃第三十三頁，共四十一頁，2022年，8月28日34【例3】求解下列整數(shù)規(guī)劃問題解引入松弛變量，寫成標(biāo)準(zhǔn)形式：（1）???íì3＝++＝+++=,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???íì3￡+￡++=且為整數(shù),0,;43;1-;max21212121xxxxxxxxz最優(yōu)解為x1＝3/4，x2＝7/4整數(shù)規(guī)劃第三十四頁，共四十一頁，2022年，8月28日35

顯然，x1＝3/4，x2＝7/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ī)劃第三十五頁，共四十一頁，2022年，8月28日36

整理后得

為了直觀地在圖形上描述，可將標(biāo)準(zhǔn)式的兩個(gè)約束方程代入上式，則成為

由于要求變量取值為正整數(shù)，方程的左邊必為整數(shù)。當(dāng)然，方程的右邊也應(yīng)為整數(shù)。又由于x3≥0,x4≥0于是，有,04/14/34/343￡--xx-3x3-x4

≤-3x2

≤1???íì3＝++＝+++=且為整數(shù),0,,,;43;1-;max43214213212