管理運籌實驗報告

實驗五：用MATLAB求解線性規(guī)劃2-10c=[-3,-1,-4];a=[6,3,5;3,4,5];b=[45,30];[x,fval]=linprog(c,a,b);Exiting:Oneormoreoftheresiduals,dualitygap,ortotalrelativeerrorhasgrown100000timesgreaterthanitsminimumvaluesofar:thedualappearstobeinfeasible(andtheprimalunbounded).(Theprimalresidual<TolFun=1.00e-08.)>>xx=1.0e+29*-1.5497-4.64924.64924-2>>c=[-240,-1200,-700];A=[1,1,1;0.5,0.5,0.5]B=[30000;20000][x,fval]=linprog(c,A,B)A=1.00001.00001.00000.50000.50000.5000B=3000020000Exiting:Oneormoreoftheresiduals,dualitygap,ortotalrelativeerrorhasstalled:thedualappearstobeinfeasible(andtheprimalunbounded).(Theprimalresidual<TolFun=1.00e-08.)x=1.0e+24*-4.63264.63260.0000fval=-4.4473e+27實驗六：非線性規(guī)劃5-4>>f='2*x(1)^2+2*x(2)^2-4*x(1)+2*x(1)*x(2)-4*x(1)-6*x(2)';x0=[1,1];[x,f_min]=fminsearch(f,x0)x=1.66670.6666f_min=-8.66675-10運用直接法編寫程序：h=[2,1,0;1,4,0;0,0,0];f=[-6;-2;-12];a=[-1,2,0];b=[3];aeq=[1,1,1];beq=[2];[x,value]=quadprog(h,f,a,b,aeq,beq,zeros(3,1))結(jié)果即得：Warning:Trust-region-reflectivealgorithmdoesnotsolvethistypeofproblem,usingactive-setalgorithm.Formorehelp,seeChoosingtheAlgorithminthedocumentation.>Inquadprogat371Warning:Yourcurrentsettingswillrunadifferentalgorithm(interior-point-convex)inafuturerelease.>Inquadprogat375Optimizationterminated.x=002value=-245-12.5-12>>H=[2000;0100;0000;0000];>>f=[0000];>>Aeq=[1-110;-2101];>>beq=[21];>>x0=[1;3;4;0];>>lb=zeros(4,1);>>[x,fval,exitflag,output,lambda]=quadprog(H,f,[],[],Aeq,beq,lb,[],x0)Theinterior-point-convexalgorithmdoesnotacceptaninitialpoint.IgnoringX0.Minimumfoundthatsatisfiestheconstraints.Optimizationcompletedbecausetheobjectivefunctionisnon-decreasinginfeasibledirections,towithinthedefaultvalueofthefunctiontolerance,andconstraintsaresatisfiedtowithinthedefaultvalueoftheconstrainttolerance.<stoppingcriteriadetails>x=0.00010.00022.00001.0001fval=2.4780e-08exitflag=1output=message:'Minimumfoundthatsatisfiestheconstraints.Optimizationcompletedbecausetheobjectivefunctionisnon-decrea...'algorithm:'interior-point-convex'firstorderopt:2.5030e-08constrviolation:2.2204e-16iterations:9cgiterations:[]lambda=ineqlin:[0x1double]eqlin:[2x1double]lower:[4x1double]upper:[4x1double]實驗七：動態(tài)規(guī)劃6-2functiony=beibao(product,weight,value)fprintf('請輸入數(shù)據(jù)product,weight,value:\n');product=input('product=');weight=input('weighe=');value=input('value=');Total_value=0;Total_weight=2000;fori=1:length(product),Total_value=Total_value+value(i);Total_weight=Total_weight-weight(i);if(Total_weight<0)Total_value=Total_value-value(i);Total_weight=Total_weight+weight(i);elsechanpin_N(i)=product(i);chanpin_W(i)=weight(i);chanpin_V(i)=value(i);endenddisp('輸出對應(yīng)裝入背包的產(chǎn)品號')chanpin_Ndisp('輸出裝入產(chǎn)品后背包總重量')sum(chanpin_W)disp('輸出裝入產(chǎn)品后背包總價值')sum(chanpin_V)運行：請輸入數(shù)據(jù)product,weight,value:product=[1234567891011]weighe=[800800500500300300300300200200200]value=[22*80022*80012*50012*5007*3007*3007*3007*3003*2003*2003*200]輸出對應(yīng)裝入背包的產(chǎn)品號chanpin_N=12005輸出裝入產(chǎn)品后背包總重量ans=1900輸出裝入產(chǎn)品后背包總價值ans=37300chanpin_N=120000009輸出裝入產(chǎn)品后背包總重量ans=1800輸出裝入產(chǎn)品后背包總價值ans=358006-4min=240*x1+220*x2+275*x3-430+0*s1+0*s2+0*s3;s1+x1<=5;x1<=3;s1+x1>=3;s2+x2<=6;x2<=2;s2+x2>=3;s3+x3<=4;x3<=3;s3+x3>=2;s3=1;s2<=2;s1<=3;s2=s3+x3-2;s1=s2+x2-3;@gin(x1);@gin(x2);@gin(x3);@gin(s1);@gin(s2);@gin(s3);實驗八：網(wǎng)絡(luò)規(guī)劃7-3在此題編程過程中，需要把其序號對應(yīng)改變，將s節(jié)點改為1號節(jié)點，1至4節(jié)點依次加1，t節(jié)點改為6節(jié)點。則s到各點的最短距離的編程具體程序如下：clc,cleara=zeros(6);a(1,2)=2;a(1,3)=5;a(2,4)=-3;a(3,2)=4;a(3,5)=3;a(4,3)=2;a(4,5)=2;a(4,6)=8;a(5,3)=-2;a(5,4)=4;a(5,6)=5;a=a+a';a(find(a==0))=inf;pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));d(1:length(a))=inf;d(1)=0;temp=1;whilesum(pb)<length(a)tb=find(pb==0);d(tb)=min(d(tb),d(temp)+a(temp,tb));tmpb=find(d(tb)==min(d(tb)));temp=tb(tmpb(1));pb(temp)=1;index1=[index1,temp];temp2=find(d(index1)==d(temp)-a(temp,index1));index2(temp)=index1(temp2(1));endd,index1,index2有下面的表達式：d=021-127index1=124356index2=1142347-4簡單變化序號利于編程，列出線性規(guī)劃表達式可得：轉(zhuǎn)化為MATLAB程序為：c=[-1;-1;0;0;0;0;0;0;0];aeq=[10-1-11000001100-10000001001-100000-11-100];ub=[4;5;2;4;1;3;3;5;4];beq=zeros(4,1);x=linprog(c,[],[],aeq,beq,zeros(9,1),ub)value=c'*x運行得出結(jié)果：Optimizationterminated.x=2.69782.30220.24432.88760.43412.54652.11245.00000value=-5.00007-5這里所介紹的求最小費用流的方法叫做迭代法，其中調(diào)用了利用Floyd算法求最短路的函數(shù)floydpath。其主要步驟如下：functionmainexample19clear;clc;globalMnumc=zeros(6);u=zeros(6);c(1,2)=5;c(1,3)=4;c(2,4)=2;c(3,2)=1;c(3,5)=3;c(4,3)=1;c(4,5)=2;c(4,6)=2;c(5,6)=5;u(1,2)=3;u(1,3)=1;u(2,4)=4;u(3,2)=1;u(3,5)=3;u(4,3)=2;u(4,5)=2;u(4,6)=4;u(5,6)=2;num=size(u,1);M=sum(sum(u))*num^2;[f,val]=mincostmaxflow(u,c);functionpath=floydpath(w);globalMnumw=w+((w==0)-eye(num))*M;p=zeros(num);fork=1:numfori=1:numforj=1:numifw(i,j)>w(i,k)+w(k,j)w(i,j)=w(i,k)+w(k,j);p(i,j)=k;endendendendifw(1,num)==Mpath=[];elsepath=zeros(num);s=1;t=num;m=p(s,t);while~isempty(m)ifm(1)s=[s,m(1)];t=[t,t(1)];t(1)=m(1);m(1)=[];m=[p(s(1),t(1)),m,p(s(end),t(end))];elsepath(s(1),t(1))=1;s(1)=[];m(1)=[];t(1)=[];endendendfunction[flow,val]=mincostmaxflow(rongliang,cost,flowvalue);globalMflow=zeros(size(rongliang));allflow=sum(flow(1,:));ifnargin<3flowvalue=M;endwhileallflow<flowvaluew=(flow<rongliang).*cost-((flow>0).*cost)';path=floydpath(w);ifisempty(path)val=sum(sum(flow.*cost));return;endtheta=min(min(path.*(rongliang-flow)+(path.*(rongliang-flow)==0).*M));theta=min([min(path'.*flow+(path'.*flow==0).*M),theta]);flow=flow+(rongliang>0).*(path-path').*theta;allflow=sum(flow(1,:));endval=sum(sum(flow.*cost));運行結(jié)果為：f=031000000400010000000004000000000000val=3657710018030900120955790368228596330825771001