數(shù)學建模-第02章整數(shù)

第二章整數(shù)規(guī)§1于整數(shù)線性規(guī)劃。目前還沒有法能有效地求解一切整數(shù)規(guī)劃。例1 zx12x14x2 x1 x2 x10,x24minz4例2 zx12x14x2 x1 x2 x10,x22minz2§2Landg和Dakin等人。由于這方法靈活且便于用計算機求解，所以現(xiàn)在它已是zAz*z。分枝定界法就Bzzz*。現(xiàn)用下例來3 z40x19x17x27x20x x14.8092,x21.8168,zzAz*z。而即0z*356。x1[4.8092]4，x1[4.8092]1問題B1： z40x19x17x27x20x 問題B2： z40x19x17x27x20x

0z*349。（i）對問B1再進行分枝得問B11B12，它們的最優(yōu)解B11B12

x14,x22,z11x11.43,x23.00,z12B21: x15.44,x21.00,z22308將B21,B22剪枝。x14,x22,z*A，將與它相應的線性規(guī)劃問題稱為問題B。Axj0,j1,Ln，試探，求得其目標函數(shù)值，并記作zz*表示問題A的最優(yōu)目標函數(shù)值；這時有zz*以[bj]表示小于bj的最大整數(shù)。構造兩個約束條件xjbj]和xjbj將這兩個約束條件，分別加入問題B，求兩個后繼規(guī)劃問題B1和B2。不考慮整數(shù)條件值為最大者作為新的下界z，若無作用z不變。jz，且不符合整數(shù)條件，則重復第一步驟。一直到最后得到z*z為止。得最優(yōu)整數(shù)解x*,j1,L,n。j§301為01xj01這個條件可由下述約束條件：0xj1先介紹引入01變量的實際問題，再研究解法。引入01例 某公司擬在市東、西、南三區(qū)建立門市部。擬議中有7個位置（點Ai(i1,2,L,7)在東區(qū)。A1A2A3三個點中至多選兩個；在西區(qū)。由A4A5兩個點中至少選一個；在南區(qū)，由A6A7兩個點中至少選一個。Ai點，設備投資估計為bi元，每年可獲利潤估計為ci元，但投資總額不能超過B元。問應選擇哪幾個點可使年利潤為最大？解題時先引入01xi(i令xxi

i1,2,L,7

zcibixix1x2x3xx x6x7

xi0或5x14x224或7x13x2455x14x2247x13x245(1y0或x10或500x1

500yx1800y0或ai1x1Lainxn i1,2,L,為了保證這m個約束條件只有一個起作用，我們引入m個01yi(i1,2,Lai1x1LainxnbiyiMy1Lymm1

i1,2,L, 關于固定費用的問題（FixedCost5某工廠為了生產(chǎn)某種產(chǎn)品，有幾種不同的生產(chǎn)方式可供選擇，如選定的生產(chǎn)Pkjcjxj 當xj jj 當xj在構成目標函數(shù)時，為了統(tǒng)一在一個問題中討論，現(xiàn)引入01變量yj，yj

當采用第j種生產(chǎn)方式，即xj0時，當不采用第j種生產(chǎn)方式，即xj0時

minz(k1y1c1x1)(k2y2c2x2)(k3y3c3x3yjxjyjM, j1,2,3 M是個充分大的正常數(shù)（4）xj0yj1xj0yj0時才有意義，所以（4）式完全可以代替（3）式。01型整數(shù)規(guī)劃解法之一（過濾隱枚舉法解01型整數(shù)規(guī)劃最容易想到的方法，和一般整數(shù)規(guī)劃的情形一樣，就是窮舉法，01的每一種組合，比較目標函數(shù)值以求得最優(yōu)解，這就需要檢查變量取值的2nn較大（n100，這幾乎是不可能的。因方法稱為隱枚舉法（ImplicitEnumeration，分枝定界法也是一種隱枚舉法。當然，對下面舉例說明一種解01型整數(shù)規(guī)劃的隱枚舉法。例6 z3x12x25x3x12x2x3x4xx x1x24xx 個可行解，且z3?！?法（隨機取樣法7Maxzx2x23x24x22x 8x12x23x3x40xi (ixxxxx x12x22x3x46x58002xx6x200 x3x45x5用去隨機計算106個點，便可找到滿意解，那么這種方法的可信度究竟怎樣下面就分析隨機取樣106個點計算時，應用概率理論來估計一下可信度。假設目標函數(shù)落在高值區(qū)的概率分別為0.01，0.00001，則當計算 個點后，10.9910000000.99L99(100多位10.9999910000000.999954602function[f,g]=mengte(x);fori=1:10^6ifp0<=fifsum(g<=0)==4ifa=111111221216000115;§5直接利用的函數(shù)，必須利用編程實現(xiàn)分枝定界解法和割平面解法。但對于指派問題等01整數(shù)規(guī)劃問題，可以直接利用的函數(shù)bintprog進行求解。8

3 7 5 59 c=[382103;87297;642784235;9106910];fori=1:5a(i,(i-x15x23x32x44x51121。求解的LINGO程序如下：c=3821087296427842391069§69某公司用兩種原油（AB）混合加工成兩種汽油（甲和乙。甲、乙兩種汽油含原油的最低比例分別為50％和60％，每噸售價分別為4800元和5600元。該公司現(xiàn)有AB的庫存量5001000噸，還可以從市場上買1500噸的原油A。原油A的市場價為：量不超過500噸時的單價為10000元/噸；采購價利潤為銷售汽油的收入與原油A的支出之差這里的難點在于原油A的采：c(x) 3000

0x500x1000x

A用于生產(chǎn)甲、乙兩種汽x11x12B用于生產(chǎn)甲、 z4.8(x11x215.6(x12x22)c(x) x11x12500xx21x221000x

x11,x12,x21,x22,x

且，對于這樣用分段函數(shù)定義的c(x)，一般的非線性規(guī)劃軟件也難以輸入和求解。能一個自然的想A的采x分解為三個量x1x2,x3分別表示以10千元/噸、8千元/噸、6千元/噸采購的原油A的噸數(shù)，總支出為c(x)10x18x26x3，且xx1x2maxz4.8(x11x21)5.6(x12x22)(10x18x26x3

應該注意到，只有當以10千元/噸的價格x1500（噸）時，才能以8千元/ x2(0)，這個條件可以表示為(x1500)x2 x3(0)(x2500)x3此外x1x2x3的取值范0x1,x2,x3

（16型輸入LINGO軟件如下：c=108可以用菜單命令“LINGO|Options”在“GlobalSolver”選項卡上啟動全局優(yōu)化選型，并運行上述程序求得全局最有解：1000噸原油A，與庫存的500噸原油A和1000B一起，共生產(chǎn)2500噸汽油乙，利潤為5000（千元。z11z21z3110千元/噸、8千元/噸、6千元/噸的價格采購原油A，則約束（15）和（16）可以替換為500z2x1500z1 500z3x2500z2 x3500z3 z1,z2,z30或 （7）～（14@for(var1(i)|i#lt#3:500*z(i+1)<x(i);x(i)<500*z(i));c=108直接處理分段線性函數(shù)c(x。式（5）表示的函數(shù)c(x1x軸上的分點為b10，b2500，b31000x屬于1個小區(qū)間[b1b2時xw1b1w2b2w1w21w1w20，因為c(x在[b1b2上是線1分段線性函c(x圖c(xw1c(b1w2c(b2。同樣，當x屬于第2個小區(qū)間[b2b3時，3[b3b4]時，xw3b3w4b4，w3w41，w3w40，c(xw3c(b3w4c(b4x0-1zk(k1,2,3)，足w1z1，w2z1z2，w3z2z3，w4 w1w2w3w41，wk0（k1,2,3,4 z1z2z31z1z2z30或x和c(xxw1b1w2b2w3b3w4b4500w2 c(x)w1c(b1)w2c(b2)w3c(b3)w4c(b4)5000w2

（6）～（13z=,,,0增加的虛擬變量z(4)=0;@for(var(i)|i#ne#1:w(i)<z(i-1)+z(i));設一個nf(x的分點為b1Lbnbn1wkxf(x為xkf(xk)wkf(bkkwk和0-1zk滿w1z1，w2z1z2，…，wnzn1zn，wn1 z1z2Lzn1，zk0或 w1w2Lwn11，wk0（k1,2,L,n Maxzx1x9x 14 2xx x1x20,x1x2試將下述非線性的01規(guī)劃問題轉(zhuǎn)換成線性的01規(guī)劃問題 zx1x1x2x32x13x2x3x xj105個鉆井探油，使總的鉆探費用為最小。10個井位的代號為s1s2L,s10，相應的鉆探費用為c1c2L,c10，并且或選s1s7，或選擇鉆s9選擇s3s4就不能s5，或反過來也一樣s5s6s7s8中最多只能選兩個；試建立這個問題的整數(shù)規(guī)劃模型成十五個小區(qū)，每個小區(qū)內(nèi)標有三個數(shù)字，分別表示該區(qū)域的海拔高度h(m)、面積S(km2)和被完全淹沒時土地、房屋和等損失總數(shù)k（百萬元我們假各小區(qū)間有相對高度為1.2m的小堤相互，例如第一區(qū)和第二區(qū)之間事實上有海拔5.2m小堤。pmf(k,kpf(k,p)

0pp求整個區(qū)域全部受損失的最小洪水量 當洪水量為Q6Q3時，分別制定泄洪方案，使總損失最?。ㄔ?高山 2 3 1