最优化实例和matlab源程序.doc

《最优化实例和matlab源程序.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最优化平时作业一、目标规划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作为约束条件，建立线性规划问题：

2、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.X22.二、动态规划之0-1背包问题1、题目：给定n种物品和一背包。物品i的重量是Wi，其价值为Vi，背包的容量是c，问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。2、解题方法与思路：利用java求解，.思想方法是回溯思想3、需求分析对于给定n种物品和一背包。在容量最大值固定的情况下，要求装入的物品价值最大化4、java源程序及运行结果BackT

3、race.java*Tochangethistemplate,chooseTools

4、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.pri

5、ntln(bestp);}//比较两个元素大小的类privatestaticclassElementimplementsComparable{intid;doubled;privateElement(intidd,doubledd){id=idd;d=dd;}publicintcompareTo(Objectx){doublexd=((Element)x).d;if(d

6、blec;//背包容量staticintn;//物品数staticdouble[]w;//物品重量数组staticdouble[]p;//物品价值数组staticdoublecw;//当前重量staticdoublecp;//当前价值staticdoublebestp;//当前最优值staticint[]x;//解staticint[]sortX;//排好序之后的解staticint[]bestX;//最有解staticDatedate=null;//@jve:decl-index=0:publicstaticdoubleknapsack(double[]pp,doubl

7、e[]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-

8、i].id];w[i]=ww[q[n-i].id];sortX[i]=q[n-i].id;}backtrack(1);//回溯搜索returnbestp;}privatestaticvoidbacktrack(inti){if(i>=n){if(cp>bestp){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-=