/第二章 于整數(shù)線性規(guī)劃。目前還沒有法能有效地求解一切整數(shù)規(guī)劃。1o變量全限制為整數(shù)時，稱純（完全）1原線性規(guī)劃為 zx12x14x2 x2 x10x24minz42原線性規(guī)劃為 zx12x14x2 x2 x10,x22minz2。 對有約束條件的最優(yōu)化問題（其可行解為有限數(shù)）Landg和Dakin等人。由于這方法靈活且便于用計算機求解，所以現(xiàn)在它已是Bzzz*?，F(xiàn)用下例來例 z40x19x17x27x20x x14.8092,x21.8168,zzAz*z即0z*356x1[4.8092]4，x1[4.8092]1問題B1： z40x19x17x27x20x 問題B2： z40x19x17x27x20x

再定界：0z*349。B11B12

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

i1,2,L,7

zcibixix1x2x3xx

xi0或5x14x224或7x13x2455x14x2247x13x245(1

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

i1,2,L, 代入（1），就只有ii*的約束條件起作用，而別的式子都是多余的。關(guān)于固定費用的問題（FixedCost5某工廠為了生產(chǎn)某種產(chǎn)品，有幾種不同的生產(chǎn)方式可供選擇，如選定的生產(chǎn)Pkjcjxj 當xj j 當xj在構(gòu)成目標函數(shù)時，為了統(tǒng)一在一個問題中討論，現(xiàn)引入01yjyj

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

minz(k1y1c1x1)(k2y2c2x2)(k3y3c3x3yjxjyjM j 01型整數(shù)規(guī)劃解法之一（過濾隱枚舉法解01變量取值的2nn較大（n100方法稱為隱枚舉法（ImplicitEnumeration下面舉例說明一種解01型整數(shù)規(guī)劃的隱枚舉法。例 z3x12x2x12x2x3x4xx x1x24xx 個可行解，且z3?！?法（隨機取樣法7Maxzx2x23x24x22x 8x12x23x3x40xi (ixxxxx x2x2xx6x8002x 用去隨機計算106個點，便可找到滿意解，那么這種方法的可信度究竟怎樣下面就分析隨機取樣106個點計算時，應(yīng)用概率理論來估計一下可信度1 0.99L99(100多位 function[f,g]=mengte(x);fori=1:10^6ifp0<=fifsum(g<=0)==4ifa=111111221216000115;§5于指派問題等01整數(shù)規(guī)劃問題，可以直接利用的函數(shù)bintprog進行求解。8874222978423697 555 c=[382103;87297;642784235;9106910];fori=1:5x15x23x32x44x51121。求解的LINGO程序如下：c=3821087296427842391069§69某公司用兩種原油（AB）混合加工成兩種汽油（甲和乙。甲、乙兩種：c(x)

0x500x1000x

z4.8(x11x21)5.6(x12x22) 限制，以及兩種汽油含原油A的比例限制，它們表示為x11x12500xx21x221000x

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

應(yīng)該注意到，只有當以10千元/噸的價格x1500（噸）時，才能以8千元/噸的價格x2(0)，這個條件可以表示為(x1500)x2 x3(0)(x2500)x30x1,x2,x3

15（16型輸入LINGO軟件如下：c=108可以用菜單命令“LINGO|Options”在“GlobalSolver”選項卡上啟動全局優(yōu)化選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(x)11c(x所以c(xw1c(b1w2c(b2。同樣，當x屬于第2個小區(qū)間[b2b3時， [b3b4]時，xw3b3w4b4，w3w41，w3w40足w1z1，w2z1z2，w3z2z3，w4w1w2w3w41，wk0（k1,2,3,4z1z2z31z1z2z30或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));設(shè)一個nf(x的分點為b1Lbnbn1wkxf(x為xkf

)

f(b

w1 k

z1z2，…，wnzn1zn，wn1 zzLz1，z0 w1w2Lwn11，wk0（k1,2,L,n Maxzx1x9x 14 2xx x1x20,x1x2試將下述非線性的01規(guī)劃問題轉(zhuǎn)換成線性的01規(guī)劃問題 zx1x1x2x32x13x2x3x xj105個鉆井探油，使總的鉆探費成十五個小區(qū)，每個小區(qū)內(nèi)標有三個數(shù)字，分別表示該區(qū)域的海拔高度h(m)、面積S(km2和被完全淹沒時土地、房屋和財產(chǎn)等損失總數(shù)k（百萬元各小區(qū)間有相對高度為1.2m的小堤相互，例如第一區(qū)和第二區(qū)之間事實上有海拔5.2m小堤。當洪水淹沒一個小區(qū)且洪水高于該小區(qū)高度pmf(k,kpf(k,p)

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