實驗5 整數規(guī)劃分支定界 的編程實現.doc

實驗5 整數規(guī)劃求解的分支定界法的編程實現成績專業(yè)班級 信息123學號 201212030330 姓名 戰(zhàn)應順 報告日期 .實驗類型：驗證性實驗 綜合性實驗 設計性實驗實驗目的：熟練整數規(guī)劃求解的分支定界法。實驗內容：整數規(guī)劃求解的分支定界法2個（題目自選1個混合整數規(guī)劃、1個0-1整數規(guī)劃）實驗原理 整數規(guī)劃求解的分支定界法，首先確定目標函數的一個初始上下界，然后通過逐步分支使上界減小，下界增大，直到兩者相等時，就求出了最優(yōu)值和最優(yōu)解。實驗步驟1 要求上機實驗前先編寫出程序代碼 2 編輯錄入程序3 調試程序并記錄調試過程中出現的問題及修改程序的過程4 經反復調試后，運行程序并驗證程序運行是否正確。5 記錄運行時的輸入和輸出。 預習編寫程序代碼：實驗報告：根據實驗情況和結果撰寫并遞交實驗報告。實驗總結：參考程序Max Z=3x1+2x22x1+3x2=14.54x1+x2=0 且為整數建立函數ILp.m文件function x,y=ILp(f,G,h,Geq,heq,lb,ub,x,id,options) %整數線性規(guī)劃分支定界法，可求解純整數規(guī)劃和混合整數規(guī)劃。 %y=minf*x s.t. G*x=h Geq*x=heq x為全整數或混合整數列向量 %用法 %x,y=ILp(f,G,h,Geq,heq,lb,ub,x,id,options) %參數說明 %lb:解的下界列向量（Default:-int） %ub:解的上界列向量（Default:int） %x:迭代初值列向量 %id：整數變量指標列向量，1-整數，0-實數（Default:1） global upper opt c x0 A b Aeq beq ID options; if nargin10,options=optimset();options.Display=off; options.LargeScale=off;end if nargin9,id=ones(size(f);end if nargin8,x=;end if nargin7 |isempty(ub),ub=inf*ones(size(f);end if nargin6 |isempty(lb),lb=zeros(size(f);end if nargin5,heq=;end if nargin4,Geq=;end upper=inf;c=f;x0=x;A=G;b=h;Aeq=Geq;beq=heq;ID=id; ftemp=ILP(lb(:),ub(:); x=opt;y=upper; %下面是子函數 function ftemp=ILP(vlb,vub) global upper opt c x0 A b Aeq beq ID options; x,ftemp,how=linprog(c,A,b,Aeq,beq,vlb,vub,x0,options); if how 0.00005 %in order to avoid error return; end; if max(abs(x.*ID-round(x.*ID)0.00005 %in order to avoid error opt=x;upper=ftemp; return; else opt=opt;x; return; end; end; notintx=find(abs(x-round(x)=0.00005); %in order to avoid error intx=fix(x);tempvlb=vlb;tempvub=vub; if vub(notintx(1,1),1)=intx(notintx(1,1),1)+1; tempvlb(notintx(1,1),1)=intx(notintx(1,1),1)+1; ftemp=IntLP(tempvlb,vub); end; if vlb(notintx(1,1),1)=intx(notintx(1,1),1) tempvub(notintx(1,1),1)=intx(notintx(1,1),1); ftemp=IntLP(vlb,tempvub); end;在Matlab命令窗口輸入：f=3,2;A=2,3;4,1;b=14.5;16.5;Aeq=;beq=;lb=0,0;ub=;xn,yn=ILp(f,A,b,Aeq,beq,lb,ub,1,1,1,)xn = 1.0e-015 * 0.1110 0yn = 3.3307e-016在Matlab命令窗口輸入：x,fval,exitflag=linprog(f,A,b,Aeq,beq,lb,ub)x = 1.0e-015 * 0.1392 0.0782f