第五章 運(yùn)籌學(xué) 整數(shù)規(guī)劃

第五章整數(shù)規(guī)劃教學(xué)目的：掌握若干特殊整數(shù)規(guī)劃的解法教學(xué)內(nèi)容：1.整數(shù)規(guī)劃問題及特點(diǎn)

2.分枝定界法與割平面法

3.0-1規(guī)劃

4.指派問題教學(xué)重點(diǎn)：割平面法與指派問題教學(xué)難點(diǎn)：分枝定界法與割平面法學(xué)時(shí)安排：8-10學(xué)時(shí)。教學(xué)內(nèi)容第一節(jié)整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)第二節(jié)解純整數(shù)規(guī)劃的割平面法第三節(jié)分支定界法第四節(jié)０－１整數(shù)規(guī)劃第五節(jié)指派問題第一節(jié)整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)

一.整數(shù)規(guī)劃問題基本概念

（1）整數(shù)規(guī)劃：要求部分或全部決策變量取整數(shù)值的規(guī)劃問題。（2）整數(shù)規(guī)劃問題的松弛問題：不考慮整數(shù)條件的規(guī)劃問題。（3）整數(shù)線性規(guī)劃——部分或全部變量取整數(shù)值的線性規(guī)劃分類：

純整數(shù)線性規(guī)劃（pureintegerlinearprogramming)

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

integerlinearprogramming)

０-１整數(shù)線性規(guī)劃(zero-one

integerlinearprogramming）二.整數(shù)規(guī)劃問題的數(shù)學(xué)模型

三.整數(shù)規(guī)劃問題的特點(diǎn)問題：能否將松弛問題的最優(yōu)解近似作為整數(shù)規(guī)劃問題的最優(yōu)解？例１：求下述整數(shù)規(guī)劃的最優(yōu)解。三.整數(shù)規(guī)劃問題的特點(diǎn)1234567x115234x2A(3.25,2.5)maxZ=3x1+2x22x1+3x2≤14x1+0.5x2

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

三、整數(shù)規(guī)劃問題的特點(diǎn)

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

C′?C

整數(shù)規(guī)劃的可行解是松弛問題可行解集合的一個(gè)子集。所以⑴IP的可行解一定是它的松弛問題的可行解。⑵IP的最優(yōu)值不會(huì)優(yōu)于其松弛問題的最優(yōu)值。第二節(jié)割平面法112-x1+x2=13x1+x2=4maxZAA(3/4,7/4)C(1,1)第二節(jié)割平面法

一、基本思想：在IP的松弛問題中,每次增加一個(gè)線性約束，即Gomory約束或割平面。它的作用是：割去可行域中不包含問題整數(shù)解的部分，使松弛問題的可行域逐步縮??；最終，目標(biāo)函數(shù)值達(dá)到最優(yōu)的整數(shù)點(diǎn)成為縮減可行域的一個(gè)頂點(diǎn)。二、求解步驟１、求出松弛問題最優(yōu)解，若為整數(shù)，則停止，否則轉(zhuǎn)２２、構(gòu)造割平面方程。構(gòu)造的割平面約束應(yīng)當(dāng)具備兩個(gè)性質(zhì)：⑴已獲得的非整數(shù)最優(yōu)解不滿足該線性約束，從而保證在以后的解中不可能再出現(xiàn)。⑵所有的整數(shù)解皆滿足該線性約束，從而保證整數(shù)最優(yōu)解始終都保留在以后每次所形成的新的線性規(guī)劃的可行域中。3-10003-1013/79/731/71000101/7-2/7-3/70012/73/722/700-5/70-3/7X4=31/7不是整數(shù)，該行對應(yīng)的方程是：CBXBbx1x2x3x4x5x1x2x4X4-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ù)項(xiàng)皆化為兩部分：不超過該數(shù)的最大整數(shù)與非負(fù)分?jǐn)?shù)，即

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

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

Nk

≤

bk

且為整數(shù)，0≤fk＜1。2、然后，第k行中的每一個(gè)非基變量xj的系數(shù)akj也分解為整數(shù)與非負(fù)數(shù)之和的形式，即akj=Nkj+fkj;Nkj≤akj;0≤fk＜1,則割平面方程為：xj為非基變量通常，從最優(yōu)單純形表中，選擇具有最大分?jǐn)?shù)部分的非整分量bm所在行構(gòu)造割平面約束，可以提高切割效果，減少切割次數(shù)。例２用割平面法求解純整數(shù)規(guī)劃。解:1、用單純形法求得松弛問題的最優(yōu)表如下。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。割平面方程為：CBXBbx1x2x3x4x5x1x2x43-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)表中，見下表。CBXBbx1x2x3x4x5x1x2x4x6x63-100003-10015/45/27/41000010000100-1/4-1/21/400011-5/4-11/2-3/4000-1/40-17/4利用對偶單純形法求出最優(yōu)解，見下表。CBXBbx1x2x3x4x5x1x2x3x5x6由上表第四行產(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/40x1x2x3x5CBXBbx1x2x3x4x5x6x7-3/4x73-1000003-10001241100000100000100000010001010-1-1-5-2-111-400000-4-1x1x2x3x5CBXBbx1x2x3x4x5x6x43x73x1-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-x2F例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+x2110015/3105/6-1/618/301-2/31/300-1/6-1/6x1x2CBXBbx1x2x3x42、構(gòu)造割平面11000

15/3105/6-1/6018/301-2/31/30

0-2/300-5/6-5/6100-1/6-1/60x1x2CBXBbx1x2x3x4x5x511000

11100-11116/50101-4/5

04/50011-6/50000-1/5x1x2CBXBbx1x2x3x4x3x53、構(gòu)造割平面110000

11100-110116/50101-4/5004/50011-6/50

0-4/50000-4/510000-1/50x1x2CBXBbx1x2x3x4x3x5x6x6110000

10100-105/41401010-10200110-3/20100001-5/400000-1/4x1x2CBXBbx1x2x3x4x3x5x5x62x1+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)

例1：某公司欲在東、西、南三區(qū)建立門市部，共有7個(gè)地方可供選擇。規(guī)定:在東區(qū)，由A1、A2、A3三個(gè)點(diǎn)中至多選兩個(gè)；在西區(qū)，由A4、A5兩點(diǎn)中至少選一個(gè)；在南區(qū)，由A6、A7兩點(diǎn)中至少選一個(gè)。選用Ai點(diǎn)，投資為bi元，每年可獲利潤ci元，但投資總額不能超過B元。問應(yīng)選擇哪幾個(gè)點(diǎn)可使年利潤最大？解：設(shè)一、0-1型整數(shù)規(guī)劃問題的描述：

0-1變量作為邏輯變量，常用來表示系統(tǒng)處于某個(gè)特定狀態(tài)，或?qū)δ硞€(gè)決策方案的選擇。第三節(jié):０-１型整數(shù)規(guī)劃例2含有相互排斥的約束條件問題。1200.40.24025利潤（元／件）1500.50.3B31000.10.2B2250工時(shí)限額（h/周）0.7A20.3A1B1產(chǎn)品工時(shí)／件工序方式Ⅰ方式Ⅱ要求B3只能從加工方式Ⅰ與Ⅱ中選擇一種，那么工廠應(yīng)如何安排生產(chǎn)，才能使總利潤最大？解：設(shè)生產(chǎn)兩種產(chǎn)品分別為x1與x2件。當(dāng)工序B3選用加工方式Ⅰ，即滿足當(dāng)工序B3不選用加工方式Ⅰ當(dāng)工序B3選用加工方式Ⅱ，即滿足當(dāng)工序B3不選用加工方式Ⅱ方式Ⅰ與Ⅱ中選擇一種等價(jià)于該問題也可以令當(dāng)工序B3采用加工方式Ⅰ

當(dāng)工序B3采用加工方式Ⅱ則，僅從加工方式中選擇一種等價(jià)于：設(shè)：P個(gè)約束條件中有q個(gè)約束起作用，令當(dāng)?shù)趇個(gè)約束起作用

當(dāng)?shù)趇個(gè)約束不起作用相互排斥約束的一般情況。則該問題等價(jià)于例3試?yán)?-1變量將下列各約束條件表示成一般的線性約束條件。⑴x1+x2≤3或2x1+3x2≥8解：令選第一個(gè)約束選第二個(gè)約束則原命題等價(jià)于⑵則⑶若x2≤4,則x5≥0;否則，x5≤3。設(shè)則（4）用0-1變量表示整數(shù)變量。任何一個(gè)整數(shù)變量x≤u，可以表示為：其中，K滿足2k+1≥u+1。例如，x≤9，可以表示為：

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

、y1、y2、y3為0-1變量。

枚舉法是解0-1規(guī)劃的一種算法。具體做法是：檢查每個(gè)變量等于0或1的所有組合。滿足所有約束條件，且使目標(biāo)函數(shù)值最優(yōu)的組合就是0-1規(guī)劃的最優(yōu)解。由于n個(gè)變量時(shí)，須檢查2n個(gè)變量組合，而當(dāng)n>15時(shí)，這幾乎是不可能的。所以，有人提出了隱枚舉法。二、0-1型整數(shù)規(guī)劃的解法——隱枚舉法(x1,x2,x3)Z值約束條件(0,0,0)0√(0,0,1)5√(0,1,0)-2√(0,1,1)3×(1,0,0)3√(1,0,1)8√(1,1,0)1×(1,1,1)6×１、先找一個(gè)可行解,如（0,0,0)，并將其目標(biāo)函數(shù)值Z=0作為下界。２、由上步得出過濾性約束條件

３、對某種變量的組合，檢驗(yàn)其是否滿足上述過濾條件，若滿足且又是可行解，則修改過濾條件，重復(fù)（３）。隱枚舉法步驟(x1,x2,x3)Z值約束條件過濾條件(0,0,0)0√z≥0(0,0,1)5√z≥5(0,1,0)-2(0,1,1)3(1,0,0)3(1,0,1)8√z≥8(1,1,0)1(1,1,1)6注意:上述計(jì)算步驟還可以進(jìn)一步得到改善，即對極大化問題，若將目標(biāo)函數(shù)中xj的價(jià)值系數(shù)按遞增（不減）的次序排列（求極小，價(jià)值系數(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)都為可行解，則其他變量的組合可不必考慮。(x2,x1,x3)Z值約束條件過濾條件√(0,0,0)0√√(0,0,1)5√√(0,1,1)8√√(1,1,1)6作業(yè)：P149:5.6(1)、5.8(1)第四節(jié)：分支定界法１２３x1x254321x1+9/14x2=51/14-2x1+x2=1/3maxA(3/2,10/3)x1=1x1=2BCLP2(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=4第四節(jié):分支定界法第四節(jié):分支定界法—步驟1分支假設(shè)松弛問題的最優(yōu)解不是整數(shù)解，則選擇一個(gè)非整數(shù)分量構(gòu)造兩個(gè)約束條件：分別加入松弛問題中，得到兩個(gè)子問題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+x2LP2第四節(jié):分支定界法2定界（以求極大值為例）以最優(yōu)目標(biāo)函數(shù)值中最大者（針對沒有分支的線性規(guī)劃問題而言）為上界，以符合整數(shù)條件的各子問題中目標(biāo)函數(shù)值最大者作為下界。若無整數(shù)解，在Z≥0的情況下，令Z=03比較與剪枝若上界等于下界，則停止；否則，剪去小于下界的分支。對于大于下界的分支，繼續(xù)重復(fù)２（函數(shù)值較大的分支優(yōu)先）。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=4LP212第四節(jié):分支定界法使用范圍:純整數(shù)、混合整數(shù)規(guī)劃9x1+7x2≤567x1+20x2≤70x1,x2≥0,且為整數(shù)maxZ=40x1+90x2LP例2: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=308X1≤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é)指派問題一、標(biāo)準(zhǔn)形式指派問題及其數(shù)學(xué)模型二、標(biāo)準(zhǔn)形式指派問題數(shù)學(xué)模型的特點(diǎn)三、標(biāo)準(zhǔn)形式指派問題的解法—匈牙利解法四、非標(biāo)準(zhǔn)形式的指派問題假定n個(gè)人去做n件事，要求每人完成其中一件，每件事交給其中一個(gè)人去完成（即人與事都不閑置），每人做各種事的費(fèi)用（或時(shí)間）已知，試求總費(fèi)用最小的分配方案。一、標(biāo)準(zhǔn)形式指派問題及其數(shù)學(xué)模型1.問題的提出特點(diǎn)：（1）人和事數(shù)目相等（2）一人只能做一件事，一件事只能有一個(gè)人來做（3）目標(biāo)極小化2、指派問題的數(shù)學(xué)模型事人費(fèi)用人1…..人n事1事2…事nc11c12c1ncn1cn2cnnx11x12x1nxn1xn2xnnminZ=c11x11+c12x12+…+cnnxnnx11+x12+…+

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

xnn=1x11+x21+…+

xn1=1……x1n+x2n+…+

xnn=1xij=0或1；i,j=1,…,n一人只能做一件事一件事只能一人來做minZ=c11x11+c12x12+…+cnnxnnx11+x12+…+

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

xnn=1x11+x21+…+

xn1=1……x1n+x2n+…+

xnn=1xij=0或11.標(biāo)準(zhǔn)形式的指派問題是特殊的運(yùn)輸問題。用表上作業(yè)法求解時(shí)有2n-1個(gè)基變量，其中只有n個(gè)取“1”值，其余都取“0”值。也是特殊的０－１整數(shù)規(guī)劃問題，共有解組合2n×n個(gè)，用隱枚舉法也不合適。2.每一個(gè)可行解可用解矩陣來表示：

因?yàn)閄中每行及每列都有且僅有一個(gè)１，所以，共有n!個(gè)可行解（n個(gè)1的分配方式）。二、指派問題數(shù)學(xué)模型的特點(diǎn)1、思想依據(jù)如果系數(shù)矩陣的所有元素cij≥0，而其中存在n個(gè)位于不同行不同列的零元素，則對應(yīng)的指派方案總費(fèi)用為零，從而也一定是最優(yōu)的。如令三、匈牙利方法⑴如果從分配問題的系數(shù)矩陣C=(cij)n×n的每行（或每列）各元素分別減去一個(gè)常數(shù)，得到一個(gè)新的矩陣C′=(cij′)n×n，則以C和C′為系數(shù)矩陣的兩個(gè)指派問題具有相同的最優(yōu)解。2、理論基礎(chǔ)（康尼格定理）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-k2、理論基礎(chǔ)（康尼格定理）⑵若矩陣C的元素可分成“０”與非“０”兩部分，則覆蓋“０”元素的最少直線數(shù)目，等于位于不同行不同列獨(dú)立零元素的最大個(gè)數(shù)。1、變換系數(shù)矩陣對各行元素分別減去該行中的最小元素，再對各列元素分別減去該列中的最小元素。直到每行每列都有0元素為止。三、匈牙利方法步驟在零元素最少的行（或列）開始，選擇一個(gè)0元素，并加上標(biāo)記：獨(dú)立零元素的含義是：它所在行的人，已經(jīng)不能再安排其他的事情做；它所在列的事（工作），已經(jīng)有人去做。如此反復(fù)，直到所有的零元素都被劃去為止。在此過程中，若存在零元素的閉回路，可任選其中一個(gè)零元素加標(biāo)記，同時(shí)劃去同行和同列中的其他零元素。０2、在變換后的矩陣中確定獨(dú)立零元素

同時(shí)，劃去此零元素所在行及其列的其他零元素。獲標(biāo)記的零元素稱為獨(dú)立零元素。3、覆蓋(1)對沒有獨(dú)立零元素的行打√。(2)在已打√的行中,對元素所在的列打√。(3)在打√的列中,對獨(dú)立零元素所在的行打√。(4)重復(fù)(2)和(3),直到無法打√為止。(5)對沒有打√的行劃線,對打√的列劃線,這樣就得到了能覆蓋所有零元素的最少直線數(shù)目的直線集合。√√√在未被直線覆蓋的元素中找出一個(gè)最小元素；對未被直線覆蓋的元素所在的行（或列）中各個(gè)元素都減去這一最小元素，然后在出現(xiàn)負(fù)元素的列(或行）中加上這一最小元素。5、重復(fù)上述各個(gè)步驟，直至得到完全的分配方案為止。4、繼續(xù)變換系數(shù)矩陣X※＝√√√√√√⑵目標(biāo)函數(shù)極小化；⑴cij≥0；⑶人與工作個(gè)數(shù)相等。匈牙利方法適用范圍1．最大化指派問題四、非標(biāo)準(zhǔn)形式的指派問題現(xiàn)準(zhǔn)備分派4個(gè)人去做4件事，每個(gè)人做每件事所得到的利潤如下表，問分派哪個(gè)人去完成哪項(xiàng)工作，使總利潤最大？甲乙丙丁ABCD15182124192322182617161919212317人事1、最大化指派問題maxZ=15

x11+18

x12+…+17

x44x11+x12+x13+

x14=1…….x41+x42+x43+

x44=1x11+x21+x31+

x41