運籌學(xué)第05章

1、(Integer Programming,IP)|整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點|解純整數(shù)規(guī)劃的割平面法|分支定界法|0-1型整數(shù)規(guī)劃|指派問題|投資組合問題|旅游售貨員問題|背包問題|證券投資證券投資：把一定的資金投入到合適的有價證券上以規(guī)避風(fēng)險并獲得最大的利潤|項目投資項目投資：財團或銀行把資金投入到若干項目中以獲得中長期的收益最大。|某財團有 萬元的資金，經(jīng)出其考察選中 個投資項目，每個項目只能投資一個。其中第 個項目需投資金額為 萬元，預(yù)計5年后獲利 萬元 ，問應(yīng)如何選擇項目使得5年后總收益最大？Bnjjcjbnj.,2 , 1|變量每個項目是否投資|約束總金額不超過限制|目標(biāo)總收益最大

2、njxBxbtsxcjnjjjnjjj.,2 , 1; 0 , 1. .max11|旅游線路安排 預(yù)定景點走且只走一次 路上時間最短；|配送線路貨郎擔(dān)問題 送貨地到達一次 總路程最短；|有一旅行團從 出發(fā)要遍游城市 ，已知從 到 的旅費為 ，問應(yīng)如何安排行程使總費用最??？0vnvvv,.,21jvivijc|變量是否從i第個城市到第j個城市；|約束每個城市只能到達一次、離開一次；|目標(biāo)總費用最??；njnixnjinnxuunjxnixtsxcijijjiniijnjijijninjij,.,2 , 1,.,2 , 1, 0 , 11 ; 1,.,2 , 1; 1,.,2 , 1; 1. .mi

3、n0000|郵遞包裹 把形狀可變的包裹用盡量少的車輛運走|旅行背包 容量一定的背包里裝盡可能的多的物品|某人出國留學(xué)打點行李，現(xiàn)有三個旅行包，容積大小分別為1000毫升、1500毫升和2000毫升，根據(jù)需要列出需帶物品清單，其中一些物品是必帶物品共有7件，其體積大小分別為400、300、150、250、450、760、190、（單位毫升）。尚有10件可帶可不帶物品，如果不帶將在目的地購買，通過網(wǎng)絡(luò)查詢可以得知其在目的地的價格（單位美元）。這些物品的容量及價格分別見下表，試給出一個合理的安排方案把物品放在三個旅行包里。 物品12345678910體積20035050043032012070042

4、0250100價格1545100705075200902030|變量變量對每個物品要確定是否帶同時要確定放在哪個包裹里，如果增加一個虛擬的包裹把不帶的物品放在里面，則問題就轉(zhuǎn)化為確定每個物品放在哪個包裹里。如果直接設(shè)變量為每個物品放在包裹的編號，則每個包裹所含物品的總?cè)萘烤秃茈y寫成變量的函數(shù)。為此我們設(shè)變量為第i個物品是否放在第j個包裹中3 ,2, 1,17.,2, 1;0 , 1jixij|約束約束 包裹容量限制： 必帶物品限制： 選帶物品限制：|目標(biāo)函數(shù)目標(biāo)函數(shù) 未帶物品購買費用最小3 , 2 , 1;171jrxcjijii7.,2 , 1; 131ixjij17.,2 , 8; 131

5、ixjij)1 (min31178jijiixp)1 (min31178jijiixp17.,2 , 8; 131ixjij3 , 2 , 1;171jrxcjijii7.,2 , 1; 131ixjij3 , 2 , 1,17.,2 , 1; 0 , 1jixijs.t.n特征特征變量整數(shù)性要求；n來源來源 問題本身的要求； 引入的邏輯變量的需要；n性質(zhì)性質(zhì)可行域是離散集合；|一般整數(shù)規(guī)劃模型|0-1整數(shù)規(guī)劃模型|混合整數(shù)規(guī)劃模型整數(shù)線性規(guī)劃線性數(shù)學(xué)問題模型的一般形式為nj=1nj=112max(min)=(=) (1,2,.,). .0(1,2,., ),.,iji jjijnc xa x

6、b imstxjnx xx或或 ，或中全部取整數(shù)nj=1nj=1max(min)=(=) (1,2,.,). .=01(1,2,., )iji jjijc xa xb imstxjn或或 ，或，nj=1nj=112max(min)=(=) (1,2,.,). .0(1,2,., ),.,iji jjijnc xa xb imstxjnx xx或或 ，或中部分取整數(shù)|令|問題模型為：1(1,2,., )0jjxjnj對項目 投資對項目 不投資112134max1. .10njjjnjjjjzc xa xxxs txxx1 1,2,.,n或（）|例2 現(xiàn)有資金總額為B。可供選擇的投資項目有n個，項

7、目j所需投資額和預(yù)期收益分別為aj和cj(j=1,2,，n)。此外，由于種種原因，有三個附加條件：第一，若選擇項目1，就必須同時選擇項目2。反之，則不一定；第二，項目3和項目4中至少選擇一個；第三，項目5、項目6和項目7中恰好選擇兩個。應(yīng)當(dāng)怎樣選擇投資項目，才能使總預(yù)期收益最大?屬于 0-1規(guī)劃問題為整數(shù)整數(shù)規(guī)劃問題：jxXbAXtsCXz0.max0.maxXbAXt sCXz（IP）問題的松弛問題的可行解域）（IP1松弛問題的可行解域若松弛問題無可行解，無可行解則IP的最優(yōu)值）（IP2松弛問題的最優(yōu)值松弛問題的最優(yōu)值是原整數(shù)規(guī)劃的目標(biāo)函數(shù)值的上界。，個整數(shù)解若松弛問題可以找到一X)3(最優(yōu)

8、值的下界的目標(biāo)函數(shù)值是則IPX為整數(shù)解）若松弛問題的最優(yōu)解（*4X的最優(yōu)解也是則IPX *|最優(yōu)解不一定在頂點上達到|最優(yōu)解不一定是放松問題最優(yōu)解的鄰近整數(shù)解|整數(shù)可行解遠多余于頂點，枚舉法不可取|整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點|解純整數(shù)規(guī)劃的割平面法|分支定界法|0-1型整數(shù)規(guī)劃|指派問題割平面法的基本思想：若整數(shù)規(guī)劃IP的松弛規(guī)劃L0的最優(yōu)解不是整數(shù)解，對L0增加一個約束條件，得線性規(guī)劃L1，此過程縮小了松弛規(guī)劃的可行解域，在切去松弛規(guī)劃的最優(yōu)解的同時，保留松弛規(guī)劃的任一整數(shù)解，因此整數(shù)規(guī)劃IP的解均在L1中，若L1的最優(yōu)解為整數(shù)解，則得IP的最優(yōu)解。若L1的最優(yōu)解不是整數(shù)解，重復(fù)以上步驟，

9、由于可行解域在不斷縮小，且保留IP所有的整數(shù)解，總可以在有限次后得到IP的最優(yōu)解.|由放松問題的可行域向整數(shù)規(guī)劃的可行域逼近|方法利用超平面切除|要求整數(shù)解保留 放松問題最優(yōu)值向最優(yōu)解逼近|目標(biāo)得到的新的可行域的某個整數(shù)坐標(biāo)的極點恰好是問題的最優(yōu)解 iNjijbfaf非基變量下標(biāo)集合 ijijijijijijbfbbafaan符號*表示不超過“*”的最大整數(shù)，f(*)表示“*”的非負真分數(shù)。|Gomory約束為整數(shù)：對整數(shù)規(guī)劃問題jxXbAXtsCXzIP0.max0.max0XbAXtsCXzL其松弛問題不是整數(shù)解的最優(yōu)解設(shè)00XL0, 0 ,00100mibbbX不妨設(shè)是非基變量是基變量，

10、即nmmixxxxx,11是分數(shù)其中0ibL0的最優(yōu)單純形表：x1 xi xmxm+1 xm+j xn解檢0 0 01 m+j nz-z0 x11 0 0a1m+1 a1m+j a1nb10 xi0 1 0aim+1 aim+j ainbi0 xm0 0 1amm+1 amm+j amnbm0所在行的方程為：0ib011ininjmjimmimibxaxaxax源方程0, 0 ,001000mibbbXL 的最優(yōu)解設(shè)是分數(shù)0,ib011ininjmjimmimibxaxaxax對源方程：00iifb100ifjimjimfa10 jimf01ijmmnjjimibxax001)(iijmjim

11、jimmnjifbxfax0011iijmmnjjimjmmnjjimifbxfxaxjmmnjimijmmnjjimiixffxabx11010010jmmnjjimixff令-對應(yīng)于生成行i的割平面x1 xixmxm+1xm+jxn解檢0 001m+jnz-z0 x11 00a1m+1a1m+ja1nb10 xi0 10aim+1aim+jainbi0 xm0 01amm+1amm+jamnbm0為整數(shù)：對整數(shù)規(guī)劃問題jxXbAXtsCXzIP0.max0.max0XbAXtsCXzL其松弛問題0, 0 ,001000mibbbXL 的最優(yōu)解是分數(shù)其中0ibL0的最優(yōu)單純形表：生成行0:1

12、0jmmnjjimixff對應(yīng)于生成行i的割平面00iifb100ifjimjimfa10 jimfmnj, 2 , 10.max:1XbAXtsCXzL線性規(guī)劃01ijmmnjjimfxf01,ijmmnjjimfxf即非基變量|求解整數(shù)線性規(guī)劃121212121212max3 -3 -23510. . 25,0,zx xxxxxstxxx xx x為整數(shù)第一步：解整數(shù)規(guī)劃問題的松弛問題，見表5-3 ，x1=13/7， x2=9/7；cj3-1000cBxBbx1x2x3x4x53x113/7101/702/7-1x29/701-2/703/70 x431/700-3/7122/7cj-zj

13、00-5/70-3/7表 5-3|第二步：寫出割平面方程，選擇第一行產(chǎn)生割平面約束，126126-777xxxcj3-10000cBxBibix1x2x3x4x5x63-100 x1x2x4x613/79/731/7-6/7100001001/7-2/7-3/7-1/700102/73/722/7-2/70001cj-zj-5/200-5/70-3/703-100 x2x1x3x515/45/27/41000010000100-1/4-1/21/400011-5/4-11/2-3/4cj-zj000-1/40-17/4表 5-4cj3-1000 00cBxBibix1x2x3x4x5x6x73

14、-1000 x1x2x3x5x41241310000010000010000001000101-1-5-110-1-21-4cj-zj-100000-4-1表 5-5原整數(shù)規(guī)劃問題的最優(yōu)解為，x1=1, x2=2,max z=1四、割平面計算步驟：第一步： 用單純刑法解整數(shù)問題IP的松弛問題L0若L0沒有最優(yōu)解，則IP沒有最優(yōu)解。停止若L0有最優(yōu)解X0:(1)X0是整數(shù)解， 則X0也是IP的最優(yōu)解，停止(2)X0不是整數(shù)解， 轉(zhuǎn)第二步第二步： 求割平面方程，的一個非整數(shù)分量任選00ibX所在的行的數(shù)據(jù)，的最優(yōu)單純型表中由00ibL011ijmmnjimfxf得割平面：011ijmmnjimfs

15、xf即第三步：將割平面加到L0得L1第四步：解L1在L0的最優(yōu)單純型表中增加一行一列，得L1的單純型表，用對偶單純刑法求解，若其解是整數(shù)解，則該解也是原整數(shù)規(guī)劃的最優(yōu)解否則將該解記為X0，返回第二步|整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點|解純整數(shù)規(guī)劃的割平面法|分支定界法分支定界法|0-1型整數(shù)規(guī)劃|指派問題 分支定界法(branch and bound method)是一種隱枚舉法(implicit enumeration)或部分枚舉法，它不是一種有效算法，是枚舉法基礎(chǔ)上的改進。 分支定界法的關(guān)鍵是分支和定界。 分支 求解放松問題 舍棄 變界 分支最優(yōu)值比界壞最優(yōu)解為整數(shù)最優(yōu)值比界好最優(yōu)解為非整數(shù)最

16、優(yōu)值比界好|分枝定界法的基本思路： 通過對松弛問題的分枝，不斷降低（IP）最優(yōu)值的上界，提高下界，當(dāng)上界等于下界時，得到最優(yōu)解。 是不超過 的最大整數(shù) rbrbIPIZ最優(yōu)值松弛問題L00LZ最優(yōu)值0LIZZ L1L21LZ最優(yōu)值2LZ最優(yōu)值01LLZZ 02LLZZ 1,LIZZ2LIZZ或通過對（L0）分枝，使（IP）的最優(yōu)值的上界不斷下降，L3L4L5L6是整數(shù)解的最優(yōu)解若某個00*iiXL的可行解是則)(*0IPXiIiZCX0*,有,*0ikkCXZL的最優(yōu)值若的下界即找到IZ,*kCX將下界改為0,iL關(guān)閉是整數(shù)解最優(yōu)解kX *) 1 (剪枝：的最優(yōu)值若0*ikkCXZL:kL討論

17、子問題0*iCXkL關(guān)閉,不是整數(shù)解最優(yōu)解kX *)2(分枝繼續(xù)對kL下界不斷上升，上界=下界得最優(yōu)值|當(dāng)前得到的最好整數(shù)解的目標(biāo)函數(shù)值|分支后計算放松的線性規(guī)劃的最優(yōu)解|整數(shù)解且目標(biāo)值優(yōu)于原有最好解的值則替代原有最好解；|整數(shù)解且目標(biāo)值劣于原有最好解的值則 刪除該分支其中無最優(yōu)解；|非整數(shù)解且目標(biāo)值優(yōu)于原有最好解的值則繼續(xù)分支；|非整數(shù)解且目標(biāo)值劣于原有最好解的值則刪除該分支其中無最優(yōu)解；|例6 求解下述整數(shù)規(guī)劃1212121212max951141412. .3,0,zxxxxxxs tx xx x為整數(shù)|第一步：舍棄整數(shù)要求，用單純形法求解，得X(0)=(3/2,10/3),點 A,目標(biāo)

18、函數(shù)值z (0) =29/6（上界），（0，0）顯然是一個可行解，目標(biāo)函數(shù)值0（下界）12121211212max9511414123. .1,0,zxxxxxxs txxxxx為整數(shù)|第二步，由于x1,x2都不是整數(shù)，分解成子問題（分支）。先考慮x1 ， x1 =3/2。 12121211212max9511414123. .2,0,zxxxxxxs txxxxx為整數(shù)（1）（2）X(1)=(2,23/9), B點z (1) =41/9X(2)=(1,7/3), C點,z (2) =10/3 (新下界)|第三步，由于z (2) z (1) z (0) , z (1) =41/9代替z (0)

19、 成為新的上界。此時，問題（2）已探明，結(jié)束。問題（1）需繼續(xù)分支。121212121212max9511414123. .23,0,zxxxxxxstxxx xx x為整數(shù)（3）（4）無可行解，刪去（剪枝）X(4)=(33/14,2), D點， z (4) =61/14121212121212max9511414123. .22,0,zxxxxxxstxxx xx x為整數(shù)|第四步，由于z (2) z (4) z (0) , 問題（1）需繼續(xù)分支。121212121212max9511414123. .33,0,zxxxxxxs txxx xx x為整數(shù)（5）（6）X(6)=(2,2), F

20、點, z (6) =4121212121212max9511414123. .22,0,zxxxxxxstxxx xx x為整數(shù)X(5)=(3,1), E點, z (5) =4得到原整數(shù)規(guī)劃問題的最優(yōu)解。S0Ax1=3/2,x2=10/3 z=29/6S2Bx1=2,x2=23/9 z=41/9S4Dx1=33/14,x2=2 z=61/14S3無可行解S1Cx1=1,x2=7/3 z=10/3S6Ex1=3,x2=1 z=4S5Fx1=2,x2=2 z=41x11x21x31x22x22x3初始分支為可行解集，確定初始界是停止當(dāng)前最好解為最優(yōu)解判定是否分支集空是按非整數(shù)變量分支并加入分支集判

21、定是否為整數(shù)解判定最優(yōu)值是否優(yōu)于當(dāng)前界否判定最優(yōu)值是否優(yōu)于當(dāng)前界是否以最優(yōu)解替代當(dāng)前最好解最優(yōu)值替代當(dāng)前界是否選一分支寫出并求解放松問題，同時從分支集中刪除該分支否|整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點|解純整數(shù)規(guī)劃的割平面法|分支定界法|0-1型整數(shù)規(guī)劃型整數(shù)規(guī)劃|指派問題一、決策問題與0-1變量件事是否做第決策變量ixiix10做第i件事不做第i件事ni,2, 1n件事中必須做k件并只做k件事kxxxn21n件事中最多做k件事kxxxn21n件事中至少做k件事nxxx21k做第i件事的充要條件是做第j件事jixx 做第i件事的充要條件是不做第j件事jixx1只在做了第i件事前提下才考慮是否做第j件

22、事ijxx例 8 有三種資源被用于生產(chǎn)三種產(chǎn)品，資源量、產(chǎn)品單件可變費用及售價、資源單耗量及組織三種產(chǎn)品生產(chǎn)的固定費用見表5-6。要求制訂一個生產(chǎn)計劃，使總收益最大。表5-6123123213123123111222333123123max456-100-150-20024850023430023100s.t.y ,01,0zxxxyyyxxxxxxxxxxM yxMyxMyyyxxx或且 為 整 數(shù)|求解設(shè)xj是第 j 種產(chǎn)品的產(chǎn)量，j=1,2,3；再設(shè)1 (0)=0 (=0)jjjxyx若生產(chǎn)第j種產(chǎn)品 即若不生產(chǎn)第j種產(chǎn)品 即其中約束條件 如何理解？111xM y|隱枚舉法（適合于變量個

23、數(shù)較少的0-1規(guī)劃）| 例 10 求解0-1整合規(guī)劃10,6434422s.t.52-3max3213221321321321或xxxxxxxxxxxxxxxxz（5.14a）（5.14b）（5.14d）（5.14c）|解： 約束條件(x2, x1, x3)abcdz(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最優(yōu)解231 0 1,max81xxxzTT（,） （ , ,）|整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點|解純整數(shù)規(guī)劃的割平面法|分支定界法|0-1型整數(shù)規(guī)劃|

24、指派問題（指派問題（assignment problem）n模型10, 2 , 1, 1, 2 , 1, 1min1111或ijnjijniijninjijijxnixnjxxcz一般稱矩陣C=(cij)nn為指派問題的系數(shù)矩陣。事人做第，若不指派第事人做第，若指派第jijixij01令|性質(zhì)：假定C=(cij)為分派問題的價值系數(shù)矩陣?，F(xiàn)將它的某一行（或某一列）的各元素都減去一個常數(shù)k，得到一新矩陣 。若以C代替C作為該分派問題的價值系數(shù)矩陣，而構(gòu)成一新的分派問題，則這個分派問題的最優(yōu)解與原分派問題的最優(yōu)解相同。ijC =(C )第1步：把各行元素分別減去本行元素的最小值；然后在此基礎(chǔ)上再把

25、每列元素減去本列中的最小值。4 8 7 15 127 9 17 14 106 9 12 8 76 7 14 6 106 9 12 10 6C例12系數(shù)矩陣4 8 7 15 120 3 0 11 87 9 17 14 100 1 7 7 36 9 12 8 70 2 3 2 16 7 14 6 100 0 5 0 46 9 12 10 60 2 3 4 0CC此時每行及每列中肯定都有0元素了。第2步：確定獨立零元素，并作標(biāo)記。（1）首先逐行判斷是否有含有獨立0元素的行，如果有，則按行繼續(xù)處理；如沒有，則要逐列判斷是否有含有獨立0元素的列，若有，則按列繼續(xù)處理。若既沒有含有獨立0元素的行，也沒有含有獨立0元素的列，則仍然按行繼續(xù)處理。（2）在按行處理時，若某行有獨立0元素，把該0元素標(biāo)記為a，把該0所在的列中的其余0元素標(biāo)記為b；否則，暫時越過本行，處理后面的行。把所有含有獨立0元素的行處理完畢后，再回來處理含有2個以及2個以上的0元素的行：任選一個0做a標(biāo)記，再把該0所在行中的其余0元