運籌學基礎整數(shù)規(guī)劃

關于運籌學基礎整數(shù)規(guī)劃2§4.1整數(shù)規(guī)劃解決整數(shù)規(guī)劃問題不能僅僅是在線性規(guī)劃求解中，將解“四舍五入”就行了，因為化整后的解不見得是可行解；即便是可行解，也不一定是優(yōu)解。注意：在前面討論的線性規(guī)劃問題中，有些最優(yōu)解可能是分數(shù)或小數(shù)，但對于某些具體的問題，常有要求解答必須是整數(shù)的情形（稱為整數(shù)解），解決這樣的問題即為整數(shù)規(guī)劃。一、整數(shù)規(guī)劃問題的提出整數(shù)規(guī)劃第2頁,共41頁，星期六，2024年，5月3【例1】某廠擬用集裝箱托運甲乙兩種貨物，每箱的體積、重量、可獲利潤以及托運所受限制如表：問兩種貨物各托運多少箱，可使利潤為最大？建立線性規(guī)劃模型為：

maxZ=

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

x1≥0,x2≥0利用單純形法求得最優(yōu)解為：x1＝4.8，x2＝0，maxZ＝96整數(shù)規(guī)劃第3頁,共41頁，星期六，2024年，5月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ī)劃第4頁,共41頁，星期六，2024年，5月5二、整數(shù)規(guī)劃的求解方法1、分枝定解法2、割平面法3、利用EXCEL求解整數(shù)規(guī)劃第5頁,共41頁，星期六，2024年，5月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)目標函數(shù)必是A的最優(yōu)目標函數(shù)Z*的上界，記作，（如果是求最小值，即為下界）

分枝定界法就是將B的可行域分成子區(qū)域的方法，逐步減小

和增大

，最終逼近Z*。

寫出整數(shù)規(guī)劃問題A的伴隨線性規(guī)劃問題為B

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

≤Z*≤整數(shù)規(guī)劃第6頁,共41頁，星期六，2024年，5月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ī)劃第7頁,共41頁，星期六，2024年，5月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ī)劃第8頁,共41頁，星期六，2024年，5月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ī)劃第9頁,共41頁，星期六，2024年，5月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ī)劃第10頁,共41頁，星期六，2024年，5月11分枝為問題1、2后解可能出現(xiàn)如下幾種情況序號問題1問題2說

明1無可行解無可行解整數(shù)規(guī)劃無可行解2無可行解整數(shù)解此整數(shù)解即最優(yōu)解3無可行解非整數(shù)解對問題2繼續(xù)分枝4整數(shù)解整數(shù)解較優(yōu)的一個為最優(yōu)解5整數(shù)解，目標函數(shù)優(yōu)于問題2非整數(shù)解問題1的解即最優(yōu)解6整數(shù)解非整數(shù)解，目標函數(shù)優(yōu)于問題1問題1停止分枝(剪枝)，其整數(shù)解為界，對問題2繼續(xù)分枝情況2,4,5

找到最優(yōu)解情況3

在縮減的域上繼續(xù)分枝定界法情況6

問題1的整數(shù)解作為界被保留，用于以后與問題2的后續(xù)分枝所得到的整數(shù)解進行比較，結論如情況4情況1

無可行解整數(shù)規(guī)劃第11頁,共41頁，星期六，2024年，5月12分枝定界法的一般步驟如下

第一步，先不考慮原問題的整數(shù)限制，求解相應的松弛問題，若求得最優(yōu)解，檢查它是否符合整數(shù)約束條件；如符合整數(shù)約束條件，即轉(zhuǎn)下一步。

第二步，定界。在各分枝問題中，找出目標函數(shù)值最大者Z*作為整數(shù)規(guī)劃最優(yōu)值的上界，從已符合整數(shù)條件的分枝中，找出目標函數(shù)值最大者作為下界，即

第三步，分枝。根據(jù)對變量重要性的了解，在最優(yōu)解中選擇一個不符合整數(shù)條件的xj

，令xj=b’j

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

第四步，應用對目標函數(shù)估界的方法，或?qū)δ骋环种χ匾缘牧私猓_定出首先要解的某一分枝的后繼問題，并解此問題。若所獲得的最優(yōu)解符合整數(shù)條件，則就是原問題的解，若不符合整數(shù)條件，再回到第二步，并參照第四步終止后繼問題。整數(shù)規(guī)劃第12頁,共41頁，星期六，2024年，5月13分枝定界法的EXCEL演示

整數(shù)規(guī)劃第13頁,共41頁，星期六，2024年，5月142、割平面解法

割平面法也是求解整數(shù)規(guī)劃問題常用方法之一。【基本思路】

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

當經(jīng)過多次切割后，就會使被切割后保留下來的可行域上有一個坐標均為整數(shù)的頂點，它恰好就是所求問題的整數(shù)最優(yōu)解。即切割后所對應的松弛問題，與原整數(shù)規(guī)劃問題具有相同的最優(yōu)解。

先不考慮整數(shù)約束條件，求松弛問題的最優(yōu)解，如果獲得整數(shù)最優(yōu)解，即為所求，運算停止。整數(shù)規(guī)劃第14頁,共41頁，星期六，2024年，5月15

割平面法的具體求解步驟如下：1.對于所求的整數(shù)規(guī)劃問題，先不考慮整數(shù)約束條件，求解相應的松弛問題2.如果該問題無可行解或已取得整數(shù)最優(yōu)解，則運算停止；前者表示原問題也無可行解，后者表示已求得整數(shù)最優(yōu)解。如果有一個或更多個變量取值不滿足整數(shù)條件，則選擇某個變量建立割平面。3.增加為割平面的新約束條件，用前面介紹的靈敏分析的方法繼續(xù)求解，返回1。整數(shù)規(guī)劃第15頁,共41頁，星期六，2024年，5月16【例1】求解下列整數(shù)規(guī)劃問題解：引入松弛變量，寫成標準形式（1）???íì3＝++＝+++=,0,,,;2054;62;max432142132121xxxxxxxxxxxxz（2）對上述模型不考慮整數(shù)條件，用單純形法求解相應松弛問題的最終單純形表為Cj比值CBXBb檢驗數(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ī)劃第16頁,共41頁，星期六，2024年，5月17

顯然，x1=5/3,x2=8/3為非整數(shù)解。為求得整數(shù)解，想辦法在原約束條件的基礎下引入一個新的約束條件，以保證一個或幾個變量取值為整數(shù)。為此，選擇分數(shù)部分較大的非整數(shù)變量，如x2

，寫出如下表達式：

將上式的所有變量的系數(shù)及右端常數(shù)均改寫成一個整數(shù)與一個非負真分數(shù)之和的形式。上式可以改寫成

若將帶有整數(shù)系數(shù)的變量留在方程的左邊，其余移到方程的右邊，則有

由于要求變量取值為正整數(shù)，方程的左邊必為整數(shù)。當然，方程的右邊也應為整數(shù)。又x3≥0,x4≥0于是，必有x3≥1,x4≥1（3）（4）≤0此時，也可以選擇x2-x3-2≤0，只是因為先分析出方程右端≤0整數(shù)規(guī)劃第17頁,共41頁，星期六，2024年，5月18

整理后得

為了直觀地在圖形上描述，可將(2)式的兩個約束方程代入(5)式即???íì3＝++＝+++=且為整數(shù),0,,,;2054;62;max432142132121xxxxxxxxxxxxz則(5)式成為（5）這就是割平面的方程B(5/3,8/3)x1x2246246-20-4AECO

加入新的約束條件，便形成新的線性規(guī)劃問題，其可行域為新的凸集OAEC。

即圖中紅色直線割去了紅色直線以外的△ABE部分，其中包括原所求得的非整數(shù)最優(yōu)解點B(5/3,8/3)。三個方程是等價的，任意一個都可增加的新的約束條件整數(shù)規(guī)劃第18頁,共41頁，星期六，2024年，5月19

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

從上面的推導過程可以看出，新約束對原約束方程起到了這樣的作用：對整數(shù)規(guī)劃(1)式所對應的線性規(guī)劃的可行域，保留了其中的所有整數(shù)可行解，但割掉了一部分非整數(shù)解。三個約束條件任選其一-1/3x3-1/3x4+

x5=-2/3整數(shù)規(guī)劃第19頁,共41頁，星期六，2024年，5月20

Cj比值CBXBb檢驗數(shù)jx1x2x3x4x5110005/3105/6-1/608/301-2/31/30-2/300-1/3-1/31x1x2x5110-13/300-1/6-1/60Cj比值CBXBb檢驗數(shù)jx1x2x3x4x5110000100-15/240101-2x1x2x6110-40000-1/220011-3x1＝0，x2＝4為最優(yōu)解，最優(yōu)值為Z＝4整數(shù)規(guī)劃第20頁,共41頁，星期六，2024年，5月21

Cj比值CBXBb檢驗數(shù)jx1x2x3x4x5110005/3105/6-1/608/301-2/31/30-2/300-1/3-1/31x1x2x5110-13/300-1/6-1/60Cj比值CBXBb檢驗數(shù)jx1x2x3x4x51100021010-1/2201-101x1x2x6110-40000-1/220011-3x1＝2，x2＝2為最優(yōu)解，最優(yōu)值為Z＝4另一選擇第21頁,共41頁，星期六，2024年，5月22分析因為上述的線性規(guī)劃的最優(yōu)解已是整數(shù)解，所以得整數(shù)規(guī)劃問題（1）的最優(yōu)解：E(2,2)A(0,4)x1x2246246-20-4x1=0，x2=4。此最優(yōu)解位于圖A點。x1=2，x2=2。此最優(yōu)解位于圖E點。整數(shù)規(guī)劃第22頁,共41頁，星期六，2024年，5月23【例2】求解下列整數(shù)規(guī)劃問題解：引入松弛變量，寫成標準形式：（1）（2）

第一步：對上述模型不考慮整數(shù)條件，用單純形法求解相應松弛問題的最終單純形表為Cj比值CBXBb檢驗數(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ī)劃第23頁,共41頁，星期六，2024年，5月24

第二步：x1

＝13/4

,x2＝5/2為非整數(shù)解，找出非整數(shù)解變量中分數(shù)部分最大的一個基變量x2，寫出這一行的約束：

將上式的所有變量的系數(shù)及右端常數(shù)均改寫成一個整數(shù)與一個非負真分數(shù)之和的形式得：

若將帶有整數(shù)系數(shù)的變量整數(shù)項留在方程的左邊，其余移到方程的右邊，則有

由于要求變量取值為正整數(shù)，方程的左邊必為整數(shù)。方程的右邊也應為整數(shù)。又由于x3≥0,x4≥0于是，有方程右端小于等于零?！?整數(shù)規(guī)劃第24頁,共41頁，星期六，2024年，5月25

即

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

–(9-2x1-x2)≤-1三個方程的任意一個都可做為后面增加的新的約束條件整理后得2x1+2x2≤11這就是割平面的方程整數(shù)規(guī)劃第25頁,共41頁，星期六，2024年，5月26

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

加入新的約束條件，便形成新的線性規(guī)劃問題，其可行域為新的凸集OAEFC。即圖中所示的紅色直線的下半部分。顯然它割去了除紅色直線上所有點以外的△BEF部分，其中包括原所求得的非整數(shù)最優(yōu)解點B(13/4,5/2)。x1x2246246-20-4O這就是割平面的方程整數(shù)規(guī)劃第26頁,共41頁，星期六，2024年，5月27

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

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

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

+x5＝-1/22x1+2x2≤11任意一個都可做為增加的新的約束條件整數(shù)規(guī)劃第27頁,共41頁，星期六，2024年，5月28

Cj比值CBXBb檢驗數(shù)jx1x2x3x4x5320005/2011/2-1/2013/410-1/4?0-1/200-1/2-1/21x2x1x5230-59/400-1/4-5/40Cj比值CBXBb檢驗數(shù)jx1x2x3x4x5110002010-117/21001-1/2x2x1x3230-29/2000-1-1/210011-2x1＝7/2，x2＝2為最優(yōu)解，最優(yōu)值為Z＝29/2，不是整數(shù)解第28頁,共41頁，星期六，2024年，5月29

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

若將帶有整數(shù)系數(shù)的變量整數(shù)項留在方程的左邊，其余移到方程的右邊，則有此得到新約束：整數(shù)規(guī)劃第29頁,共41頁，星期六，2024年，5月30

2x1+2x2≤11

又加入的新約束條件，便形成新的線性規(guī)劃問題，其可行域又隨之改變B(13/4,5/2)AECFx1x2246246-20-4Ox1+x2≤5整數(shù)規(guī)劃第30頁,共41頁，星期六，2024年，5月31

2010-110

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

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

1-1/20x2x1x3x62300-29/2000-1-1/2010011-20-1/20000-1/21新增加的約束條件整數(shù)規(guī)劃第31頁,共41頁，星期六，2024年，5月32

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

10-1x2x1x3x62300-14000-10-1300110-41010-102100001-2x1＝4，x2＝1為最優(yōu)解，最優(yōu)值為Z＝14，是整數(shù)解整數(shù)規(guī)劃第32頁,共41頁，星期六，2024年，5月33

E‘(1,4)因為上述的線性規(guī)劃的最優(yōu)解已是整數(shù)解，所以得整數(shù)規(guī)劃問題的最優(yōu)解：x1=1，x2=4。maxZ＝14B(13/4,5/2)AECFx1x2246246-20-4O整數(shù)規(guī)劃第33頁,共41頁，星期六，2024年，5月34【例3】求解下列整數(shù)規(guī)劃問題解引入松弛變量，寫成標準形式：（1）???íì3＝++＝+++=,0,,,;43;1-;max432142132121xxxxxxxxxxxxz（2）對上述模型不考慮整數(shù)條件，用單純形法求解相應松弛問題的最終單純形表為Cj比值CBXBb檢驗數(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ī)劃第34頁,共41頁，星期六，2024年，5月35

顯然，x1＝3/4，x2＝7/4

為非整數(shù)解。找出非整數(shù)解變量中分數(shù)部分最大的一個基變量，寫出相應的約束：將上式的所有變量的系數(shù)及右端常數(shù)均改寫成一個整數(shù)與一個非負真分數(shù)之和的形式。據(jù)此，上式可以改寫成

若將帶有整數(shù)系數(shù)的變量整數(shù)項留在方程的左邊，其余移到方程的右邊，則有

,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ī)劃第35頁,共41頁，星期六，2024年，5月36

整理后得

為了直觀地在圖形上描述，可將標準式的兩個約束方程代入上式，則成為

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

≤-3x2

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