最优化实例和matlab源程序

最优化平时作业

一、目标规划

1、题目：见书中例题P110例4 2、解题方法：利用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;

X1 4. X2 2.

二、动态规划之0-1背包问题

1、题目：给定n种物品和一背包。物品i的重量是Wi，其价值为Vi，背包的容量是c，问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。 2、解题方法与思路：利用java求解，.思想方法是回溯思想 3、需求分析

对于给定n种物品和一背包。在容量最大值固定的情况下，要求装入的物品价值最大化 4、java源程序及运行结果 BackTrace.java

* To change this template, choose Tools | Template Manager * and open the template in the editor. */

package sunfa;

import java.util.Date;

public class BackTrace { /** * @param args */ public static void main(String[] args) { double w[]={2,2,6,5,4}; double v[]={6,3,5,4,6}; int n=5; double c=10; knapsack(v,w,c); System.out.println(bestp); }

//比较两个元素大小的类 private static class Element implements Comparable{ int id; double d; private Element(int idd,double dd){ id=idd; d=dd; } public int compareTo(Object x){ double xd=((Element)x).d; if(d

static Date date = null; // @jve:decl-index=0: public static double knapsack(double[]pp,double[]ww,double cc){ c=cc; n=pp.length-1; cw=0.0; cp=0.0; bestp=0.0; Element[]q=new Element[n]; //q为单位重量价值数组 for(int i=1;i<=n;i++) q[i-1]=new Element(i,pp[i]/ww[i]); MergeSort.mergeSort(q); p=new double[n+1]; w=new double[n+1]; x=new int[n+1]; sortX=new int[n+1]; bestX=new int[n+1]; for(int i=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);//回溯搜索 return bestp; } private static void backtrack(int i){ if(i>=n){ if(cp>bestp){ bestp=cp; for(int j=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);//进入右子树 } //计算上界 private static double bound(int i){ double cleft=c-cw; double bound=cp;

//以物品重量价值递减顺序装入物品 while(i<=n&&w[i]<=cleft){ cleft-=w[i]; bound+=p[i];i++; }

//装满背包 if(i<=n) bound+=p[i]/w[i]*cleft; return bound; } public static String getX(){ String solution=String.valueOf(bestX[1]); for(int i=2;i

三、最短路径问题：给定距离矩阵，求第一点到其它点的最短距离

1、题目：给定下列矩阵，求第一点到其余各点的最短路径

?0?50?????40?25??10402510?01520?25??1501020???

201001025??2010055??25?25550?50?2、解题方法：利用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; while sum(pb)