關(guān)于MATLAB整數(shù)規(guī)劃分支定界法.doc

《關(guān)于MATLAB整數(shù)規(guī)劃分支定界法.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、一、編程利用Matlab的線性規(guī)劃指令：[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub)編寫計(jì)算整數(shù)規(guī)劃函數(shù)，輸入與輸出與上述指令相同分枝定界法（遞歸實(shí)現(xiàn)）function[x,fval,status]=intprog(f,A,B,I,Aeq,Beq,lb,ub,e)%整數(shù)規(guī)劃求解函數(shù)intprog()%其中f為目標(biāo)函數(shù)向量%A和B為不等式約束Aeq與Beq為等式約束%I為整數(shù)約束%lb與ub分別為變量下界與上界%x為最優(yōu)解，fval為最優(yōu)值%例子:%maximize20x1+10x2%S.T.%5x1+4x2<=2

2、4%2x1+5x2<=13%x1,x2>=0%x1,x2是整數(shù)%f=[-20,-10];%A=[54;25];%B=[24;13];%lb=[00];%ub=[infinf];%I=[1,2];%e=0.;%[xvs]=IP(f,A,B,I,[],[],lb,ub,,e)%x=41v=-90.0000s=1%控制輸入?yún)?shù)ifnargin<9,e=0.00001;ifnargin<8,ub=[];ifnargin<7,lb=[];ifnargin<6,Beq=[];ifnargin<5,Aeq=[];ifnargin<4,I=[1:length

3、(f)];end,end,end,end,end,end%求解整數(shù)規(guī)劃對(duì)應(yīng)的線性規(guī)劃,判斷是否有解options=optimset('display','off');[x0,fval0,exitflag]=linprog(f,A,B,Aeq,Beq,lb,ub,[],options);ifexitflag<0disp('沒(méi)有合適整數(shù)解');x=x0;fval=fval0;status=exitflag;return;else%采用分支定界法求解bound=inf;[x,fval,status]=branchbound(f,A,B,I,x0,f

4、val0,bound,Aeq,Beq,lb,ub,e);end子函數(shù)function[newx,newfval,status,newbound]=branchbound(f,A,B,I,x,fval,bound,Aeq,Beq,lb,ub,e)%分支定界法求解整數(shù)規(guī)劃%f,A,B,Aeq,Beq,lb,ub與線性規(guī)劃相同%I為整數(shù)限制變量的向量%x為初始解，fval為初始值options=optimset('display','off');[x0,fval0,status0]=linprog(f,A,B,Aeq,Beq,lb,ub,[],op

5、tions);%遞歸中的最終退出條件%無(wú)解或者解比現(xiàn)有上界大則返回原解ifstatus0<=0

6、

7、fval0>=boundnewx=x;newfval=fval;newbound=bound;status=status0;return;end%是否為整數(shù)解,如果是整數(shù)解則返回intindex=find(abs(x0(I)-round(x0(I)))>e);ifisempty(intindex)newx(I)=round(x0(I));newfval=fval0;newbound=fval0;status=1;return;end%當(dāng)有非整可行

8、解時(shí)，則進(jìn)行分支求解%此時(shí)必定會(huì)有整數(shù)解或空解%找到第一個(gè)不滿足整數(shù)要求的變量n=I(intindex(1));addA=zeros(1,length(f));addA(n)=1;%構(gòu)造第一個(gè)分支x<=floor(x(n))A=[A;addA];B=[B,floor(x(n))];[x1,fval1,status1,bound1]=branchbound(f,A,B,I,x0,fval0,bound,Aeq,Beq,lb,ub,e);A(end,:)=[];B(:,end)=[];%解得第一個(gè)分支，若為更優(yōu)解則替換，若不是則保持原狀statu

9、s=status1;ifstatus1>0&&bound1

10、支，并與第一分支做比較，如果更優(yōu)則替換ifstatus2>0&&bound2