運(yùn)籌學(xué)第五章

1第五章整數(shù)規(guī)劃第五章整數(shù)規(guī)劃學(xué)時安排：8學(xué)時教學(xué)目的：掌握若干特殊整數(shù)規(guī)劃的解法教學(xué)內(nèi)容：1.整數(shù)規(guī)劃問題及特點2.分枝定界法與割平面法3.0-1規(guī)劃4.指派問題教學(xué)重點：割平面法與指派問題教學(xué)難點：分枝定界法與割平面法2第五章整數(shù)規(guī)劃教學(xué)內(nèi)容第一節(jié)整數(shù)規(guī)劃問題的提出第二節(jié)解純整數(shù)規(guī)劃的割平面法第三節(jié)分支定界法第四節(jié)０-１整數(shù)規(guī)劃第五節(jié)指派問題3第一節(jié)整數(shù)規(guī)劃問題的提出整數(shù)規(guī)劃問題基本概念整數(shù)規(guī)劃問題的數(shù)學(xué)模型整數(shù)規(guī)劃解的特點第五章整數(shù)規(guī)劃41.基本概念整數(shù)規(guī)劃：要求部分或全部決策變量取整數(shù)值的規(guī)劃問題。整數(shù)規(guī)劃問題的松弛問題：不考慮整數(shù)條件的規(guī)劃問題。整數(shù)線性規(guī)劃：整數(shù)規(guī)劃為線性規(guī)劃純整數(shù)線性規(guī)劃（pureintegerlinearprogramming)

混合整數(shù)線性規(guī)劃（mixedintegerlinearprogramming）

0-1整數(shù)線性規(guī)劃(zero-oneintegerlinearprogramming）注意：后面提到的整數(shù)規(guī)劃，一般指的都是整數(shù)線性規(guī)劃。第五章整數(shù)規(guī)劃52.整數(shù)規(guī)劃數(shù)學(xué)模型的一般形式第五章整數(shù)規(guī)劃63.整數(shù)規(guī)劃解的特點問題：能否將松弛問題最優(yōu)解的近似值（取整、四舍五入）作為整數(shù)規(guī)劃問題的最優(yōu)解？例1：求下述整數(shù)規(guī)劃的最優(yōu)解。第五章整數(shù)規(guī)劃7第五章整數(shù)規(guī)劃1234567x115234x2A(3.25,2.5)2x1+3x2=14X1+0.5x2

=4.5Z=3x1+2x2最優(yōu)解為(4,1)8第五章整數(shù)規(guī)劃結(jié)論：⑴不能把松弛問題的最優(yōu)解通過“四舍五入”或“截尾”（即湊整）處理后作為整數(shù)規(guī)劃的最優(yōu)解。不過，在變量取值很大時，用上述方法得到的解與最優(yōu)解差別不大。⑵點(4,1)不是可行域的頂點，所以直接用圖解法或單純形法無法求出整數(shù)規(guī)劃問題的最優(yōu)解．9第五章整數(shù)規(guī)劃

整數(shù)線性規(guī)劃的解與松弛問題的解既有聯(lián)系，又有本質(zhì)的區(qū)別。設(shè)IP的松弛問題的可行域為C，IP的可行域為C′，則有

C′?C

整數(shù)規(guī)劃的可行解是松弛問題可行解集合的一個子集。所以：⑴IP的可行解一定是它的松弛問題的可行解。⑵IP的最優(yōu)值不會優(yōu)于其松弛問題的最優(yōu)值。10第二節(jié)割平面法割平面方法的基本思想和步驟構(gòu)造割平面約束的方法示例第五章整數(shù)規(guī)劃112-x1+x2=13x1+x2=4maxZAA(3/4,7/4)C(1,1)1.割平面方法的基本思想和步驟基本思想：在IP問題的松弛問題中依次引進(jìn)線性約束（稱Gomory約束或割平面），使問題的可行域逐步縮小，所割去的區(qū)域僅包含問題的部分非整數(shù)解；當(dāng)規(guī)劃問題的最優(yōu)解恰好位于縮小的可行域的一個頂點時，算法結(jié)束。第五章整數(shù)規(guī)劃求解步驟：第五章整數(shù)規(guī)劃求出松弛問題最優(yōu)解，若為整數(shù)，則停止，否則轉(zhuǎn)２構(gòu)造割平面方程。構(gòu)造的割平面約束應(yīng)當(dāng)具備兩個性質(zhì)：已獲得的非整數(shù)最優(yōu)解不滿足該線性約束，從而保證在以后的解中不可能再出現(xiàn)。所有的整數(shù)解皆滿足該線性約束，從而保證整數(shù)最優(yōu)解始終都保留在以后每次所形成的新的線性規(guī)劃的可行域中。14第五章整數(shù)規(guī)劃3-10003-1013/79/731/71000101/7-2/7-3/70012/73/722/700-5/70-3/7X4=31/7不是整數(shù)，該行對應(yīng)的方程是：CBXBbx1x2x3x4x5x1x2x4第五章整數(shù)規(guī)劃X4-3/7x3+22/7x5=31/7基變量（整數(shù)）非基變量（整數(shù)）-3/7=-1+4/7

22/7=3+1/731/7=4+3/7在上述式子中，除第一部分X4

（即整數(shù)部分）外，我們將后面變量的系數(shù)與常數(shù)項皆化為兩部分：不超過該數(shù)的最大整數(shù)與非負(fù)分?jǐn)?shù)，即16第五章整數(shù)規(guī)劃

將整數(shù)部分放在等式的左邊,其余部分放在右邊,得：17第五章整數(shù)規(guī)劃上式的左邊是一個整數(shù)，右邊是一個小于１的數(shù)，因此，右邊是一個小于或等于０的整數(shù)，即通過分析，可以得出上式具有如下兩個性質(zhì)：①松弛問題的非整數(shù)最優(yōu)解不滿足該式②

IP的所有整數(shù)可行解都滿足此式18第五章整數(shù)規(guī)劃構(gòu)造割平面約束的一般方法如下：1、在松弛問題的最優(yōu)表中，設(shè)b列的第k個分量bk為非整數(shù)，可將它分解為整數(shù)和非整數(shù)部分之和，即bk=Nk+fk，

Nk＜bk

且為整數(shù)，0＜fk＜1。2、然后，第k行中的每一個非基變量xj的系數(shù)akj也分解為整數(shù)與非負(fù)數(shù)之和的形式，即akj=Nkj+fkj;Nkj≤akj;0≤fk＜1,則割平面方程為：xj為非基變量通常，從最優(yōu)單純形表中，選擇具有最大分?jǐn)?shù)部分的非整分量所在行構(gòu)造割平面約束，可以提高切割效果，減少切割次數(shù)。19第五章整數(shù)規(guī)劃例２：用割平面法求解純整數(shù)規(guī)劃。解:1、用單純形法求得松弛問題的最優(yōu)表如下。20第五章整數(shù)規(guī)劃3-10003-1013/79/731/71000101/7-2/7-3/70012/73/722/700-5/70-3/7⑴

松弛問題的最優(yōu)解為非整數(shù),而在13/7=1+6/7

，9/7=1+2/7，31/7=4+3/7的非負(fù)分?jǐn)?shù)中,6/7最大。所以，將13/7所在的行中非基變量所對應(yīng)的系數(shù)進(jìn)行分解:1/7=0+1/72/7=0+2/7。割平面方程為：CBXBbx1x2x3x4x5x1x2x421第五章整數(shù)規(guī)劃3-100003-10013/79/731/7-6/7100001001/7-2/7-3/7-1/700102/73/722/7-2/7000100-5/70-3/70

將割平面約束⑴變?yōu)榈仁郊s束后，并入松弛問題的最優(yōu)表中，見下表。CBXBbx1x2x3x4x5x1x2x4x6x622第五章整數(shù)規(guī)劃3-100003-10015/45/27/41000010000100-1/4-1/21/400011-5/4-11/2-3/4000-1/40-17/4利用對偶單純形法求出最優(yōu)解，見下表。CBXBbx1x2x3x4x5x1x2x3x5x623第五章整數(shù)規(guī)劃由上表第四行產(chǎn)生的割平面約束為：3-1000003-100015/45/27/41000001000001000-1/4-1/21/4-1/40001010-5/40-11/20-3/40-1/41000-1/40-17/40x1x2x4x6CBXBbx1x2x3x4x5x6x7-3/4x724第五章整數(shù)規(guī)劃3-1000003-10001241100000100000100000010001010-1-1-5-2-111-400000-4-1x1x2x4x6CBXBbx1x2x3x4x5x6x43x725第五章整數(shù)規(guī)劃3x1-2x2=35x1+4x2=102x1+x2=5ABCDmax

12315234-1/7x3-2/7x5≤

-6/7x1≤1-1/4x4-1/4x6≤-3/4x1+x2≥3x1≤1x1+x2≥3EF3x1-2x2≤35x1+4x2≥102x1+x2≤5maxZ=3x1-x23x1-2x2+

x3=35x1+4x2–

x4=102x1+x2+

x5=5maxZ=3x1-x2F26第五章整數(shù)規(guī)劃案例32x1+x2≤64x1+5x2≤20x1,x2≥0且為整數(shù)maxZ=x1+x21、求出松弛問題的最優(yōu)解2x1+x2+x3=64x1+5x2+x4=20x1,x2,

x3,x4≥0且為整數(shù)maxZ=x1+x227第五章整數(shù)規(guī)劃110015/3105/6-1/618/301-2/31/300-1/6-1/6x1x2CBXBbx1x2x3x42、構(gòu)造割平面第五章整數(shù)規(guī)劃11000

15/3105/6-1/6018/301-2/31/300-2/300-5/6-5/6100-1/6-1/60x1x2CBXBbx1x2x3x4x5x5第五章整數(shù)規(guī)劃11000

11100-11116/50101-4/504/50011-6/50000-1/5x1x2CBXBbx1x2x3x4x3x53、構(gòu)造割平面第五章整數(shù)規(guī)劃110000

11100-110116/50101-4/5004/50011-6/500-4/50000-4/510000-1/50x1x2CBXBbx1x2x3x4x3x5x6x6第五章整數(shù)規(guī)劃110000

10100-105/41401010-10200110-3/20100001-5/400000-1/4x1x2CBXBbx1x2x3x4x3x5x5x6第五章整數(shù)規(guī)劃2x1+x2≤64x1+5x2≤20x1,x2≥0且為整數(shù)maxZ=x1+x2

123451523462x1+x2=64x1+5x2=20maxZA(5/3,8/3)B(1,16/5)C(9/5,12/9)D(0,4)E(2,2)F(1,3)第三節(jié)分支定界法一、分支定界法步驟二、示例第五章整數(shù)規(guī)劃第五章整數(shù)規(guī)劃１２３x1x254321x1+9/14x2=51/14-2x1+x2=1/3maxA(3/2,10/3)x1=1x1=2BC第五章整數(shù)規(guī)劃LP2(CGE):C(2,23/9);Z=41/9LP1(BFD):B(1,7/3);Z=10/3不可能區(qū)域１２３５４３２１０x1x2maxABCx1=1x1=2EDFGMHLP21(HMEG):M(33/14,2);Z=61/14x1=3NLLP212(NEL):N(3,1);Z=4LP211(HG):H(2,2);Z=436一、分支定界法步驟第五章整數(shù)規(guī)劃1分支假設(shè)松弛問題的最優(yōu)解不是整數(shù)解，則選擇一個非整數(shù)分量構(gòu)造兩個約束條件：分別加入松弛問題中，得到兩個子問題LP1與LP2,即后繼問題，并求解之。x1+9/14x2≤51/14-2x1+x2≤1/3x1≤1x1,x2≥0,且為整數(shù)maxZ=x1+x2LP1x1+9/14x2≤51/14-2x1+x2≤1/3x1≥2x1,x2≥0,且為整數(shù)maxZ=x1+x2LP237一、分支定界法步驟第五章整數(shù)規(guī)劃2定界（以求極大值為例）以最優(yōu)目標(biāo)函數(shù)值中最大者（針對沒有分支的線性規(guī)劃問題而言）為上界，以符合整數(shù)條件的各子問題中目標(biāo)函數(shù)值最大者作為下界。若無整數(shù)解，在Z≥0的情況下，令Z=03比較與剪枝若上界等于下界，則停止；否則，剪去小于下界的分支。對于大于下界的分支，繼續(xù)重復(fù)２（函數(shù)值較大的分支優(yōu)先）。38第五章整數(shù)規(guī)劃X1≤1X1≥2X2≤2X2≥3X1≤2X1≥3LP0S:X1=3/2；X2=10/3；Z0=29/6S2X1=1,X2=7/3,Z=10/3LP1S1X1=2,X2=23/9,Z=41/9LP2S11X1=33/14,X2=2,Z=61/14LP21無可行解LP22S111X1=3,X2=1,Z=4LP211S112X1=2,X2=2,Z=4LP21239第五章整數(shù)規(guī)劃使用范圍:純整數(shù)、混合整數(shù)規(guī)劃9x1+7x2≤567x1+20x2≤70x1,x2≥0,且為整數(shù)maxZ=40x1+90x2LP例2:40第五章整數(shù)規(guī)劃9x1+7x2=561

2

3456789x1x2123456787x1+20x2=70maxZx1=4x1=5B(4,2.1);Z=349x2=2x2=3E(4,2);Z=340D(1.42,3);Z=327C(5,1.57);Z=341x2=1LP2(OGBH):BLP1(MKC):CHMA(4.81,1.82)GOKF(5.44,1);Z=30841第五章整數(shù)規(guī)劃X1≤4X1≥5X2≤2X2≥3X2≤1X2≥2LP0S:X1=4.81；X2=1.82；Z0=356S1X1=5,X2=1.57,Z=341LP1:CS2X1=4,X2=2.1,Z=349LP2:BX1=4,X2=2,Z=340S21LP21:EX1=1.42,X2=3,Z=327LP22:DS11X1=5.44,X2=1,Z=308LP11:FLP12無可行解第四節(jié)0-1整數(shù)規(guī)劃一、0-1變量及其應(yīng)用二、0-1規(guī)劃的隱枚舉法第五章整數(shù)規(guī)劃43注：決策時，如果要考慮某個特定方案是否被選?。炊鄠€方案不一定全用），可以使用0-1變量?！纠?】某公司欲在東、西、南三區(qū)建立門市部，共有7個門市部可供選擇。規(guī)定；在東區(qū)，由A1、A2、A3三個點中至多選兩個；在西區(qū)，由A4、A5兩點中至少選一個；在南區(qū)，由A6、A7兩點中至少選一個。選用Ai點，投資為bi元，，每年可獲利潤ci元，但投資總額不能超過B元。問應(yīng)選擇哪幾個點可使年利潤最大？一、0-1變量及應(yīng)用第五章整數(shù)規(guī)劃44解：設(shè)Ai被選用Ai不被選用則問題變?yōu)榈谖逭抡麛?shù)規(guī)劃45【例2】含有相互排斥的約束條件問題120150100250工時限額（h/周）400.40.50.10.7A2250.20.30.20.3A1利潤（元／件）B3方式1方式2B2B1工時/件工序產(chǎn)品第五章整數(shù)規(guī)劃46要求B3只能從加工方式Ⅰ與Ⅱ中選擇一種，那么工廠應(yīng)如何安排生產(chǎn)，才能使總利潤最大？設(shè)生產(chǎn)兩種產(chǎn)品分別為x1與x2件當(dāng)工序B3選用加工方式Ⅰ，即滿足當(dāng)工序B3不選用加工方式Ⅰ當(dāng)工序B3選用加工方式Ⅱ，即滿足當(dāng)工序B3不選用加工方式Ⅱ第五章整數(shù)規(guī)劃47當(dāng)工序B3選用加工方式Ⅰ，即滿足當(dāng)工序B3不選用加工方式Ⅰ當(dāng)工序B3選用加工方式Ⅱ，即滿足當(dāng)工序B3不選用加工方式Ⅱ方式Ⅰ與Ⅱ中選擇一種等價于第五章整數(shù)規(guī)劃48則數(shù)學(xué)模型為：第五章整數(shù)規(guī)劃49該問題也可以令：當(dāng)工序B3采用加工方式Ⅰ當(dāng)工序B3采用加工方式Ⅱ則從兩種加工方式中選擇一種等價于：第五章整數(shù)規(guī)劃50一般情形下，如果有P個約束條件，q個起作用可以令：當(dāng)?shù)趇個起作用當(dāng)?shù)趇個不起作用則問題轉(zhuǎn)化為：第五章整數(shù)規(guī)劃51【例3】試?yán)?-1變量將下列各約束條件表示成一般的線性約束條件。⑴解：設(shè)選第一個約束選第二個約束則原命題等價于第五章整數(shù)規(guī)劃52⑵x3只能取r1,r2,…,rk中的一個。⑶若x2≤4,則x5≥0；否則，x5≤3設(shè)x3取ri否則則設(shè)當(dāng)x2≤4；當(dāng)x2＞4第五章整數(shù)規(guī)劃53則（4）當(dāng)變量可以取多個整數(shù)值時，可以用多個0-1變量來表示，例如，x≤9可以表示為

x=20y0+21y1+22y2+23y3≤9

其中，y0,y1,y2,y3是0-1變量。第五章整數(shù)規(guī)劃54二、0-1規(guī)劃的隱枚舉法枚舉法是解0-1規(guī)劃的一種算法。具體方法就是檢查每個變量等于0或1的所有組合。滿足所有約束條件，且使目標(biāo)函數(shù)值達(dá)到最優(yōu)的組合就是0-1規(guī)劃的最優(yōu)解。由于當(dāng)0-1變量有n個時，須檢查2n個變量組合，而當(dāng)n>15時，這幾乎是不可能的。所以有人提出隱枚舉法。第五章整數(shù)規(guī)劃55尋找一種方法，使問題在達(dá)到最優(yōu)解之前，僅須依次檢查所有可能變量組合的很少一部分。下面介紹兩種這樣的方法。求解步驟：【例4】求解1.隱枚舉方法的求解思路和方法第五章整數(shù)規(guī)劃56１、先找一個可行解,如（0,0,0)，并將其目標(biāo)函數(shù)值z=0

作為下界；２、由上步得出過濾條件

3x1-2x2+5x3≥0３、對某種變量的組合，檢驗其是否滿足上述過濾條件，若滿足且又是可行解，則修改過濾條件。重復(fù)步驟3。第五章整數(shù)規(guī)劃57第五章整數(shù)規(guī)劃(x2,x1,x3)Z值約束條件過濾條件√(0,0,0)0√√(0,0,1)5√√(0,1,1)8√√(1,1,1)658第五章整數(shù)規(guī)劃注意:上述計算步驟還可以進(jìn)一步得到改善，即對極大化問題，若將目標(biāo)函數(shù)中xj的價值系數(shù)按遞增（不減）的次序排列（求極小，價值系數(shù)按照遞減的次序排列）。即則可知(0,0,1)的目標(biāo)值一定不小于(0,1,0)及(1,0,0)的目標(biāo)值。同樣(0,1,1)的目標(biāo)值一定不小于(1,1,0)與(1,0,1)的目標(biāo)值。故若(0,0,0)、(0,0,1)、(0,1,1)、(1,1,1)都為可行解，則其他變量的組合可不必考慮。第五章整數(shù)規(guī)劃59第五節(jié)指派問題一、指問題的標(biāo)準(zhǔn)形式及數(shù)學(xué)模型二、匈牙利方法三、非標(biāo)準(zhǔn)形式的指派問題601、指派問題（assignmentproblem)假定n個人去做n件事，并指定每人完成其中一項，每項交給其中一個人去完成（即人與事一一對應(yīng))，問應(yīng)如何分配才能使完成這件事的總費(fèi)用最少。2、標(biāo)準(zhǔn)形式的數(shù)學(xué)模型指派問題的系數(shù)矩陣設(shè)第i人完成第j件事的費(fèi)用為cij

，則稱一、指派問題的標(biāo)準(zhǔn)形式及數(shù)學(xué)模型第五章整數(shù)規(guī)劃61為指派問題的系數(shù)矩陣（coefficientmatrix)或效率矩陣。令指派第i人做第j件事不指派第i人做第j件事則數(shù)學(xué)模型為：第五章整數(shù)規(guī)劃62可以看出：⑴標(biāo)準(zhǔn)形式的指派問題是特殊的運(yùn)輸問題。也是特殊的0-1整數(shù)規(guī)劃問題。⑵每一個可行解可用一個解矩陣表示X中每行及每列都有且僅有一個１，所以共有個可行解。第五章整數(shù)規(guī)劃63第五章整數(shù)規(guī)劃1、思想依據(jù)如果系數(shù)矩陣的所有元素cij≥0，而其中存在n個位于不同行不同列的零元素，則對應(yīng)的指派方案總費(fèi)用為零，從而也一定是最優(yōu)的。如令二、匈牙利方法64問題：如何產(chǎn)生或者尋找n個位于不同行不同列的零元素定理1、如果從分配問題的系數(shù)矩陣的每行（或每列）各元素分別減去(或加上)一個常數(shù)，得到一個新的矩陣則以C和C′為系數(shù)矩陣的兩個指派問題有相同的最優(yōu)解（見下頁）。2、理論基礎(chǔ)（康尼格定理）第五章整數(shù)規(guī)劃65第五章整數(shù)規(guī)劃minZ=c11x11+c12x12+…+cnnxnnx11+x12+…+

x1n=1…….xn1+xn2+…+

xnn=1x11+x21+…+

xn1=1……x1n+x2n+…+

xnn=1xij=0或1minZ(1)=(c11–k)x11+(c12–k)

x12+…+(c1n–k)x1n+c21x21+…+cnnxnnminZ(1)=c11x11+c12x12+…+cnnxnn-k(x11+x12+…+x1n)

=c11x11+c12x12+…+cnnxnn-k66第五章整數(shù)規(guī)劃67第五章整數(shù)規(guī)劃⑵若矩陣C的元素可分成“０”與非“０”兩部分，則覆蓋“０”元素的最少直線數(shù)目，等于位于不同行不同列獨立零元素的最大個數(shù)。68第五章整數(shù)規(guī)劃1、變換系數(shù)矩陣對各行