最优化实例和matlab源程序

最优化平时作业一、目标规划1、题目：见书中例题P110例42、解题方法：利用Lingo求解3、具体步骤（1）.对应于第一优先等级，建立线性规划问题：model:min=-d1;5*x1+10*x2=60;x1-2*x2+d1_-d1=0;end运行结果：-d1=0（2）对应于第二优先等级，将-d1=0作为约束条件，建立线性规划问题：min=d2_;5*x1+10*x2=60;x1-2*x2+d1_-d1=0;4*x1+4*x2+d2_-d2=36;-d1=0;end运行结果：d2=0;（3）.对应于第三优先等级，将-d1=0,-d1=0作为约束条件，建立线性规划问题：min=d3_;5*x1+10*x2=60;x1-2*x2+d1_-d1=0;4*x1+4*x2+d2_-d2=36;6x1+8*x2+d3_-d3=48;-d1=0;d2=0;end运行结果：d3=0;X14.800000X22.400000二、动态规划之0-1背包问题1、题目：给定n种物品和一背包。物品i的重量是Wi，其价值为Vi，背包的容量是c，问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。2、解题方法与思路：利用java求解，.思想方法是回溯思想3、需求分析对于给定n种物品和一背包。在容量最大值固定的情况下，要求装入的物品价值最大化4、java源程序及运行结果BackTrace.java*Tochangethistemplate,chooseTools|TemplateManager*andopenthetemplateintheeditor.*/packagesunfa;importjava.util.Date;publicclassBackTrace{/***@paramargs*/publicstaticvoidmain(String[]args){doublew[]={2,2,6,5,4};doublev[]={6,3,5,4,6};intn=5;doublec=10;knapsack(v,w,c);System.out.println(bestp);}//比较两个元素大小的类privatestaticclassElementimplementsComparable{intid;doubled;privateElement(intidd,doubledd){id=idd;d=dd;}publicintcompareTo(Objectx){doublexd=((Element)x).d;if(dxd)return-1;if(d==xd)return0;return1;}publicbooleanequals(Objectx){returnd==((Element)x).d;}}staticdoublec;//背包容量staticintn;//物品数staticdouble[]w;//物品重量数组staticdouble[]p;//物品价值数组staticdoublecw;//当前重量staticdoublecp;//当前价值staticdoublebestp;//当前最优值staticint[]x;//解staticint[]sortX;//排好序之后的解staticint[]bestX;//最有解staticDatedate=null;//@jve:decl-index=0:publicstaticdoubleknapsack(double[]pp,double[]ww,doublecc){c=cc;n=pp.length-1;cw=0.0;cp=0.0;bestp=0.0;Element[]q=newElement[n];//q为单位重量价值数组for(inti=1;i=n;i++)q[i-1]=newElement(i,pp[i]/ww[i]);MergeSort.mergeSort(q);p=newdouble[n+1];w=newdouble[n+1];x=newint[n+1];sortX=newint[n+1];bestX=newint[n+1];for(inti=1;i=n;i++){p[i]=pp[q[n-i].id];w[i]=ww[q[n-i].id];sortX[i]=q[n-i].id;}backtrack(1);//回溯搜索returnbestp;}privatestaticvoidbacktrack(inti){if(i=n){if(cpbestp){bestp=cp;for(intj=1;j=n;j++){bestX[j]=x[j];}}return;}//搜索子树if(cw+w[i]=c){//进入左子树x[sortX[i]]=1;cw+=w[i];cp+=p[i];backtrack(i+1);cw-=w[i];cp-=p[i];}if(bound(i+1)bestp)x[sortX[i]]=0;backtrack(i+1);//进入右子树}//计算上界privatestaticdoublebound(inti){doublecleft=c-cw;doublebound=cp;//以物品重量价值递减顺序装入物品while(i=n&&w[i]=cleft){cleft-=w[i];bound+=p[i];i++;}//装满背包if(i=n)bound+=p[i]/w[i]*cleft;returnbound;}publicstaticStringgetX(){Stringsolution=String.valueOf(bestX[1]);for(inti=2;ibestX.length;i++){solution+=,;solution+=String.valueOf(bestX[i]);}returnsolution;}publicstaticdoublegetBestValue(){returnbestp;}}三、最短路径问题：给定距离矩阵，求第一点到其它点的最短距离1、题目：给定下列矩阵，求第一点到其余各点的最短路径0552525105501020252510010204020100152520150501025405002、解题方法：利用matlab求解3、具体步骤：源程序及运行结果clear;clc;M=10000;a(1,:)=[0,50,M,40,25,10];a(2,:)=[zeros(1,2),15,20,M,25];a(3,:)=[zeros(1,3),10,20,M];a(4,:)=[zeros(1,4),10,25];a(5,:)=[zeros(1,5),55];a(6,:)=zeros(1,6);a=a+a';pb(1:length(a))=0;pb(1)=1;d(1:length(a))=M;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;end运行输出，第一个点到其它各点的最短路径长度，即：d=03545352510四、关键路径问题1.题目要求：某工程由下表作业组成，计算出其关键路径。作业计划完成时间紧前工作A5/B10/C11/D4BE4AF15CDG21BEH35BEI25BEJ15F,G,IK20FG2.解题方法：用lingo求解3.LINGO源程序sets:event/1..8/:et,lt;active(event,event)/!ABCDE0FGHI0JK;1,21,31,43,42,53,54,65,65,85,76,77,86,8/:d,tf,ff;endsetsdata:d=510114401521352501520;enddatan=@size(event);et(1)=0;@for(event(k)|k#gt#1:et(k)=@max(active(i,k):et(i)+d(i,k)););lt(n)=et(n);@for(event(k)|k#lt#n:lt(k)=@min(active(k,j):et(j)-d(k,j)););@for(active(i,j):tf(i,j)=lt(j)-et(i)-d(i,j);ff(i,j)=et(j)-et(i)-d(i,j););即项目的总工期为51天，作业在（1，3），（3,5），（5,6）和（6,8）位于关键路径上。五、存储问题1．题目要求：某电器公司的生产流水线需要某种零件，该零件需要靠订货得到．为此，该公司考虑到了如下费用结构：(1)批量订货的订货费12000元／次；(2)每个零件的单位成本为10元／件；(3)每个零件的存贮费用为0.3元／(件·月)；(4)每个零件的缺货损失为1.1元／(件·月)。公司应如何安排这些零件的订货时间与订货规模，使得全部费用最少？设该零件的每月需求量为800件．（1）试求今年该公司对零件的最佳订货存贮策略及费用；（2）若明年对该零件的需求将提高一倍，则需零件的订货批量应比今年增加多少？订货次数以为多少？解：取一年为单位时间，由假设，订货费CD＝12000元／次，存贮费Cp=3.6元／(件·年)，需求率D=96000件／年，代入相关的公式得到：*22120096000252983.6DPCDQC**252980.263596000QTD*223.6120009600091073DPTCCCD2.LINGO源程序(1)MODEL:C_D=12000;D=96000;C_P=3.6;Q=(2*C_D*D/C_P)^0.5;T=Q/D;n=1/T;TC=0.5*C_P*Q+C_D*D/Q;END全年的订货次数为13.7947Tn=次(2)sets:times/1..2/:n,Q,TC;endsetsdata:n=3,4;C_D=12000;D=96000;C_P=3.6;enddata@for(times:n=D/Q;TC=0.5*C_P*Q+C_D*D/Q;);END结果输出：全年组织4次订货更好一些，每季度订货一次，每次订货24000件。程序：(3)MODEL:sets:order/1..99/:TC,EOQ;endsets@for(order(i):EOQ(i)=D/i;TC(i)=0.5*C_P*EOQ(i)+C_D*D/EOQ(i););TC_min=@min(order:TC);Q=@sum(order(i):EOQ(i)*(TC_min#eq#TC(i)));N=D/Q;data:C_D=12000;D=96000;C_P=3.6;enddataEND结果显示：一年组织4次订货（每季度1次），每次的订货量为24000件，最优费用为91200元六、矩阵对策给定下列矩阵，求最优决策1、题目：见书中P337例72、解题方法与思路：转化为线性规划问题，再用lingo求解3、具体步骤：源程序及运行结果（1）求X（lingo源程序）min=x5;9*x1+2*x2+5*x3+10*x4-x5=0;8*x1+4*x2+8*x3+7*x4-x5=0;11*x1+6*x2+7*x3+9*x4-x5=0;8*x1+3*x2+8*x3+6*x4-x5=0;x1+x2+x3+x4=0;end（2）求Y（lingo源程序）max=x5;9*x1+8*x2+11*x3+8*x4-x5=0;2*x1+4*x2+6*x3+3*x4-x5=0;5*x1+8*x2+7*x3+8*x4-x5=0;10*x1+7*x2+9*x3+6*x4-x5=0;x1+x2+x3+x4=0;end运行输出：对策值V=8七、排队论1、解题步骤：第1步调查并收集和处理数据，记录客户到达时刻、等待时间和服务时间．假定客户到达的间隔时间服从指数分布（