(完整word版)整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)

1、整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)整數(shù)規(guī)劃IP(integerprogramming):在許多規(guī)劃問題中，如果要求一部分或全部決策變量必須取整數(shù)。例如，所求的解是機(jī)器的臺數(shù)、人數(shù)、車輛船只數(shù)等，這樣的規(guī)劃問題稱為整數(shù)規(guī)劃，簡記IP。松弛問題(slackproblem):不考慮整數(shù)條件，由余下的目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)劃問題稱為該整數(shù)規(guī)劃問題的松弛問題。若松弛問題是一個線性規(guī)化問題，則該整數(shù)規(guī)劃為整數(shù)線性規(guī)劃(integerlinearprogramming)。一、整數(shù)線性規(guī)劃數(shù)學(xué)模型的一般形式max(或min)Z=fcxjjj=1s.thax,=)bijjij=1x0ji=1,2,.,nj=1,2

2、,.mx,x，x中部分或全部取整數(shù)12n整數(shù)線性規(guī)劃問題可以分為以下幾種類型1、純整數(shù)線性規(guī)劃(pureintegerlinearprogramming)：指全部決策變量都必須取整數(shù)值的整數(shù)線性規(guī)劃。有時，也稱為全整數(shù)規(guī)劃。2、混合整數(shù)線性規(guī)劃(mixedintegerlinerprogramming)：指決策變量中有一部分必須取整數(shù)值，另一部分可以不取整數(shù)值的整數(shù)線性規(guī)劃。3、01型整數(shù)線性規(guī)劃(zerooneintegerlinerprogramming):指決策變量只能取值0或1的整數(shù)線性規(guī)劃。1解整數(shù)規(guī)劃問題maxz=3x+x12TOC o 1-5 h z3x-2x10122x+x0且

3、為整數(shù)12129+x142maxz=x+x5110且為整數(shù)01型整數(shù)規(guī)劃01型整數(shù)規(guī)劃是整數(shù)規(guī)劃中的特殊情形，它的變量僅可取值0或1，這時的變量xi稱為01變量，或稱為二進(jìn)制變量。01型整數(shù)規(guī)劃中01變量作為邏輯變量(logicalvariable),常被用來表示系統(tǒng)是否處于某一特定狀態(tài)，或者決策時是否取某個方案。1如果決策i為是或有XVio如果決策i為否或無一、01型整數(shù)規(guī)劃的典型應(yīng)用問題例1：背包問題：一個登山隊(duì)員，他需要攜帶的物品有：食品、氧氣、冰鎬、繩索、帳篷、照相器材、通信器材等。每種物品的重量和重要性系數(shù)如表所示。設(shè)登山隊(duì)員可攜帶的最大重量為25kg,試選擇該隊(duì)員所應(yīng)攜帶的物品。序

4、號1234567物品食品氧氣冰鎬繩索帳篷照相器材通信設(shè)備重量/Kg55261224重要性系數(shù)201518148410解：弓I入01變量xi,xi=1表示應(yīng)攜帶物品i，,xi=0表示不應(yīng)攜帶物品inaxz=20 x+15x+18x+14x+8x+4x+10 x1234567+5x+2x+6x+12x+2x+4xW25234567上述問題就是一個標(biāo)準(zhǔn)的0-1整數(shù)規(guī)劃問題，解得X*=(1,1,1,1,0,1,1)Z*=81例2：集合覆蓋和布點(diǎn)問題某市消防隊(duì)布點(diǎn)問題。該市共有6個區(qū)，每個區(qū)都可以建消防站，市政府希望設(shè)置的消防站最少，但必須滿足在城市任何地區(qū)發(fā)生火時，消防車要在15min內(nèi)趕到現(xiàn)場。據(jù)實(shí)

5、地測定，各區(qū)之間消防車行駛的時間見表，請制定一個布點(diǎn)最少的計(jì)劃。地區(qū)1地區(qū)2地區(qū)3地區(qū)4地區(qū)5地區(qū)6地區(qū)101016282720地區(qū)210024321710地區(qū)316240122721地區(qū)428321201525地區(qū)527172715014地區(qū)620102125140解：弓I入01變量xi,xi=1表示在該區(qū)設(shè)消防站,xi=0表示不設(shè)minz=x+x+x+x+x+x123456112x+x+x1126x+x134Vx+x+x1345x+x+x1456x+x+x1256x=1或0i解得：X*=(0,1,0,1,0,0)Z*=2二、特殊約束的處理矛盾約束：建模時，有時會遇到相互矛盾的約束，而模型只

6、能兩者取一或例如下面兩個約束f(x)3(1)f(x)0(2)先不等式同向處理，原式可化為：3-f(x)0f(x)0(4)再引入一個0-1變量y,及一個很大的正數(shù)M,3-f(x)My(5)f(x)a(a對于形似f(x)af(x)-a約束同向處理，改為-f(x)-af(x)-a0)，可以用以下一對約束代替-f(x)-a+My引入01變量后，f(x)-a+M(1-y)多中選一的約束模型希望在下列幾個約束中，只能有一個約束有效f(x)0(i=1,2,n)(1)i引入n個01整數(shù)變量yi,i=1,2,n.TOC o 1-5 h zf(x)1123x+x124對于第3個小區(qū)：x+x135對于第4個小區(qū)：對

7、于第5個小區(qū)：x+x+x+x11234對于第6個小區(qū)：x+x156對于第7個小區(qū)：丈XMinz=j=1j解得：X*=(l,0,0,l,l,0)Tz*=3例2有兩個相互排斥的約束條件5x+4x2412或7x+3x45。為了統(tǒng)一在一個問題中，引入o-1變量y，則上述約束條件可改寫為:5x+4x24+yM127x+3x45+(1y)M12y=0或1其中M是充分大的數(shù)。例3約束條件x二0亠500 x8001或1可改寫為500yx1y二0或10P=彳jjjjj0,當(dāng)x=0l當(dāng)jj=1,2,3.在構(gòu)成目標(biāo)函數(shù)時，為了統(tǒng)一在一個問題中討論，現(xiàn)引入o-1變量y7，令1當(dāng)采用第/種生產(chǎn)方式，即Xj0時，y=仁j

8、0,當(dāng)不采用第種生產(chǎn)方式，即Xj=0時j于是目標(biāo)函數(shù)minz=（ky+cx）+（ky+cx）+（ky+cx）TOC o 1-5 h z111122223333（3）（3）式這個規(guī)定可表為下述3個線性約束條件：yx0時yj必須為1;當(dāng)xj二0時只有為0時才有意義，所以式完全可以代替式。例8求解下列指派問題，已知指派矩陣為TOC o 1-5 h z38210387297642754235求最小指派問題。106910數(shù)學(xué)模型為：ijijj=1i=1Minz=3*x11+8*x12+2*x13+10*x14+3*x15+8*x21+7*x22+9*x51+10*x52+6*x53+9*x54+10*x

9、55X11+x12+x13+x14+x15=1工x=1i=1.5ijj=1X51+x52+x53+x54+x55=1X11+x21+x31+x41+x51=1X15+x25+x35+x45+x55=1Xi,j=0,1Lingo程序?yàn)椋簃odel:sets:row/1.5/:;col/1.5/:;link(row,col):a,x;endsetsdata:a=382103872976427584235106910;enddatamin=sum(link(i,j):a(i,j)*x(i,j);for(row(i):sum(col(j):x(i,j)=1);for(col(j):sum(row(i)

10、|i#le#2:x(i,j)+sum(row(i)|i#ge#3:x(i,j)=1);end籃球隊(duì)需要選擇5名隊(duì)員組成出場陣容參加比賽。8名隊(duì)員的身高和擅長位置見下表：隊(duì)員身高（米）擅長位置11.92中鋒21.90中鋒31.88前鋒41.86前鋒51.85前鋒61.83后衛(wèi)71.80后衛(wèi)81.78后衛(wèi)出現(xiàn)陣容應(yīng)滿足以下條件：中鋒只能有一個上場；x1+x2=1至少有一名后衛(wèi)；x6+x7+x8=1如1號和4號上場，則6號不出場；y=x1+x4,ify=2x6=0X1=x62號和6號至少保個不出場。X2+x6=1應(yīng)當(dāng)選擇哪5名隊(duì)員上場，才能使出場隊(duì)員平均身高最高？22公司生產(chǎn)A、B、C三種產(chǎn)品，售價

11、分別為12元、7元和6元。生產(chǎn)每單位A需要1小時技術(shù)服務(wù)、10小時直接勞動、3千克材料；生產(chǎn)每單位B需要2小時技術(shù)服務(wù)、4小時直接勞動、2千克材料；生產(chǎn)每單位C需要1小時技術(shù)服務(wù)、5小時直接勞動、1千克材料；現(xiàn)在最多能提供100小時技術(shù)服務(wù)、700小時直接勞動、400千克材料；生產(chǎn)成本是生產(chǎn)量的非線性函數(shù)，如下所示：設(shè)產(chǎn)品A的產(chǎn)量為xi，且Jo,其他人|1,0 x401J0,其他人1,100 x1501設(shè)產(chǎn)品B的產(chǎn)量為x2，且=Jo,其他y21|1,0 x5021214o,1,o,1,o,1,其他40 x1501其他50 x1002設(shè)產(chǎn)品C產(chǎn)量為X3,且:31o,1,其他0 x1003設(shè)總利潤

12、為：yTOC o 1-5 h zMaxy=12-(10y+9y+8y+7y)x+【7-(6y+4y+3y)x+【6-(5y+4y)x111213141212223231323x+x+x100,10 x+42x+5x700,3x+2x+x40023123123y+y+y+y=1,y+y+y=1,y+y=112131421222331320 xy40,40 xy100,100 xy150,0 xy50,50 xy100,0 xy100,x0(j=1,2,3)323331332jy=0或1(j=1,2,3),y=0或1(j=1,2,3),y=0或1(j=1,2)1j2j3j2某鉆井隊(duì)要從以下10個可供選擇的井位中確定5個鉆井采油，目的是使總的鉆井費(fèi)用最小。若10個鉆井位代號為S1,S2,S10,相應(yīng)的鉆控費(fèi)用為分，C10，并且井位的選擇要滿足下列條件：若選擇S1和S7，或選擇鉆探S8:選擇了S3或S4，就不能選擇S5，反過來也是一樣。在S2,S6,S9,S10中最多只能選擇兩個。試建立這個問題的整數(shù)規(guī)劃模型。設(shè)S=0或1，其中j=0代表j點(diǎn)未