分支定界法資料

整數(shù)線性規(guī)劃之分支定界法摘要最優(yōu)化理論和方法是在上世紀(jì)40年代末發(fā)展成為一門獨(dú)立的學(xué)科。1947年，Dantaig首先提出求解一般線性規(guī)劃問題的方法，即單純形算法，隨后隨著工業(yè)革命、計(jì)算機(jī)技術(shù)的巨大發(fā)展，以及信息革命的不斷深化，到現(xiàn)在的幾十年時(shí)間里，它有了很快的發(fā)展。目前，求解各種最優(yōu)化問題的理論研究發(fā)展迅速，例如線性規(guī)劃、非線性規(guī)劃以及隨機(jī)規(guī)劃、非光滑規(guī)劃、多目標(biāo)規(guī)劃、幾何規(guī)劃、整數(shù)規(guī)劃等，各種新的方法也不斷涌現(xiàn)，并且在軍事、經(jīng)濟(jì)、科學(xué)技術(shù)等方面應(yīng)用廣泛，成為一門十分活躍的學(xué)科。整數(shù)規(guī)劃（integerprogramming）是一類要求要求部分或全部決策變量取整數(shù)值的數(shù)學(xué)規(guī)劃，實(shí)際問題中有很多決策變量是必須取整數(shù)的。本文主要介紹求解整數(shù)線性規(guī)劃問題的分支定界法及其算法的matlb實(shí)現(xiàn)。關(guān)鍵詞：整數(shù)線性規(guī)劃；分支定界法；matlb程序；引言1.1優(yōu)化問題發(fā)展現(xiàn)狀最優(yōu)化理論與算法是一個(gè)重要的數(shù)學(xué)分支，它所討論的問題是怎樣在眾多的方案中找到一個(gè)最優(yōu)的方案.例如，在工程設(shè)計(jì)中，選擇怎樣的設(shè)計(jì)參數(shù)，才能使設(shè)計(jì)方案既滿足要求又能降低成本；在資源分配中，資源有限時(shí)怎樣分配，才能使分配方案既可以滿足各方面的要求，又可以獲得最多的收益；在生產(chǎn)計(jì)劃安排中，怎樣設(shè)計(jì)生產(chǎn)方案才能提高產(chǎn)值和利潤；在軍事指揮中，確定怎樣的最佳作戰(zhàn)方案，才能使自己的損失最小，傷敵最多，取得戰(zhàn)爭的勝利；在我們的生活中，諸如此類問題，到處可見.最優(yōu)化作為數(shù)學(xué)的一個(gè)分支，為這些問題的解決提供了一些理論基礎(chǔ)和求解方法.最優(yōu)化是個(gè)古老的課題.長期以來，人們一直對最優(yōu)化問題進(jìn)行著探討和研究.在二十世紀(jì)四十年代末，Dantzig提出了單純形法，有效地解決了線性規(guī)劃問題，從而最優(yōu)化成為了一門獨(dú)立的學(xué)科。目前，有關(guān)線性規(guī)劃方面的理論和算法發(fā)展得相當(dāng)完善,但是關(guān)于非線性規(guī)劃問題的理論和算法還有待進(jìn)一步的研究，實(shí)際應(yīng)用中還有待進(jìn)一步的完善。傳統(tǒng)的非線性全局最優(yōu)化方法只能求出問題的局部最優(yōu)解，但由于許多問題的局部最優(yōu)解不一定是全局最優(yōu)解，使得傳統(tǒng)的非線性最優(yōu)化方法不能直接成功地應(yīng)用于求解非線性全局最優(yōu)化問題。另外，沒有一個(gè)固定的評判標(biāo)準(zhǔn)來判斷得到的局部最優(yōu)解是否為全局最優(yōu)解。隨著科學(xué)技術(shù)的發(fā)展和計(jì)算機(jī)計(jì)算能力的提高，最優(yōu)化理論在最近這幾年來得到了迅速的發(fā)展，涌現(xiàn)出了許多新的算法,如打洞函數(shù)法,填充函數(shù)法，lagrangian乘子函數(shù)方法，信賴域方法，慮子方法等。本文主要介紹求解整數(shù)線性規(guī)劃問題的分支定界法及其算法的matlb實(shí)現(xiàn)。1.2整數(shù)線性規(guī)劃及其數(shù)學(xué)模型整數(shù)規(guī)劃主要有以下三大類：（1）全整數(shù)規(guī)劃（allintegerprogramming）：所有的決策變量都取整數(shù)值，也稱為純整數(shù)規(guī)劃（pureintegerprogramming）；（2）混合整數(shù)規(guī)劃（mixedintegerprogramming）：僅要求一部分決策變量取整數(shù)值；（3）0-1規(guī)劃（zero-oneintegerprogramming）：該類問題的決策變量只能取0或1.本文主要討論的整數(shù)線性規(guī)劃問題模型為：求解線性規(guī)劃問題LP得:按條件和將問題LP分解成子問題LP1和LP2并賦它們下界為14.2①求線性規(guī)劃子問題LP1得：；求線性規(guī)劃子問題LP得：；；因中，因此以條件和將LP2分成兩個(gè)子問題LP3和LP4并賦它們下界為14.33②求線性規(guī)劃子問題LP3得：；求線性規(guī)劃子問題LP4得：；因和是原整數(shù)規(guī)劃問題的可行解且，所以令為上界。再將LP1分支，因中，因此以條件和將LP1分成兩個(gè)子問題LP5和LP6并賦它們下界為14.33③求線性規(guī)劃子問題LP5得：；求線性規(guī)劃子問題LP6得：；由于，>,所以LP5和LP6都沒有繼續(xù)分支求解的必要,至此求得最優(yōu)解為，,最優(yōu)目標(biāo)函數(shù)值為。3．matlab程序?qū)崿F(xiàn)下面給出整數(shù)線性規(guī)劃分支定界法的matlab程序ILp1.m.function[x,y]=ILp1(f,G,h,Geq,heq,lb,ub,x,id,options)globalupperoptcx0AbAeqbeqIDoptions;ifnargin<10,options=optimset({});options.Display='off';options.LargeScale='off';endifnargin<9,id=ones(size(f));endifnargin<8,x=[];endifnargin<7lisempty(ub),ub=inf*ones(size(f));endifnargin<6lisempty(lb),lb=zeros(size(f));endifnargin<5,heq=[];endifnargin<4,Geq=[];endupper=inf;c=f;x0=x;A=G;b=h;Aeq=Geq;beq=heq;ID=id;ftemp=ILP(lb(:),ub(:));x=opt;y=upper;%下面是子函數(shù)functionftemp=ILP(vlb,vub)globalupperoptcx0AbAeqbeqIDoptions;[x,ftemp,how]=linprog(c,A,b,Aeq,beq,vlb,vub,x0,options);ifhow<=0return;end;ifftemp-upper>0.00005%inordertoavoiderrorreturn;end;ifmax(abs(x*ID-round(x*ID)))<0.00005ifupper-ftemp>0.00005%inordertoavoiderroropt=x';upper=ftemp;return;elseopt=[opt;x'];return;end;end;notintx=find(abs(x-round(x))>=0.00005);%inordertoavoider-rorintx=fix(x);tempvlb=vlb;tempvub=vub;ifvub(notintx(1,1),1)>=intx(notintx(1,1),1)+1;tempvlb(notintx(1,1),1)=intx(notintx(1,1),1)+1;ftemp=ILP(tempvlb,vub);end;ifvlb(notintx(1,1),1)<=intx(notintx(1,1),1)tempvub(notintx(1,1),1)=intx(notintx(1,1),1);ftemp=ILP(vlb,tempvub);end;對例1的matlab實(shí)現(xiàn)c=[7,3,4];a=[-1,-2,-3;-3,-1,-1];b=[-8;-5];[x,z]=ILp1(c,a,b,[],[],[0;0;0],[inf;inf;inf])輸出結(jié)果x=05.00000z=15.0000這與之前討論的結(jié)果一致，說明該算法的正確性。4．總結(jié)雖然對于用分支定界法解決整數(shù)規(guī)則等問題在運(yùn)籌學(xué)里有一套完整的理論,但將它用計(jì)算機(jī)來實(shí)現(xiàn)還是有一定的難度。本文正是在這個(gè)方面作了一些探討,主要介紹了求解整數(shù)線性規(guī)劃問題的分支定界法及其算法的matlb實(shí)現(xiàn)，并以實(shí)例驗(yàn)證了該算法的正確性。參考文獻(xiàn)[1]王開榮.最優(yōu)化方法[M].北京:科學(xué)版社,2012.219-222[2]李勝華.分支與定界算法的實(shí)現(xiàn)研究[J]