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

最优化平时作业一、目标规划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;X1 4.800000 X2 2.400000 二、动态规划之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(dxd)return -1;if(d=xd)return 0;return 1;public boolean equals(Object x)return d=(Element)x).d;static double c; /背包容量static int n;/物品数static doublew;/物品重量数组static doublep; /物品价值数组static double cw;/当前重量static double cp;/当前价值static double bestp; /当前最优值static int x;/解static int sortX;/排好序之后的解static int bestX;/最有解 static Date date = null; / jve:decl-index=0:public static double knapsack(doublepp,doubleww,double cc)c=cc;n=pp.length-1;cw=0.0;cp=0.0;bestp=0.0;Elementq=new Elementn; /q为单位重量价值数组for(int i=1;i=n;i+)qi-1=new Element(i,ppi/wwi);MergeSort.mergeSort(q);p=new doublen+1;w=new doublen+1;x=new intn+1;sortX=new intn+1;bestX=new intn+1;for(int i=1;i=n)if(cpbestp) bestp=cp;for(int j=1;j=n;j+)bestXj=xj;return; /搜索子树if(cw+wibestp)xsortXi=0;backtrack(i+1);/进入右子树/计算上界private static double bound(int i)double cleft=c-cw;double bound=cp; /以物品重量价值递减顺序装入物品while(i=n&wi=cleft)cleft-=wi;bound+=pi;i+; /装满背包if(i=n)bound+=pi/wi*cleft;return bound;public static String getX()String solution=String.valueOf(bestX1);for(int i=2;ibestX.length;i+)solution+=,;solution+=String.valueOf(bestXi);return solution;public static double getBestValue()return bestp;三、最短路径问题：给定距离矩阵，求第一点到其它点的最短距离1、题目：给定下列矩阵，求第一点到其余各点的最短路径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)=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步 调查并收集和处理数据，记录客户到达时刻、等待时间和服务时间假定客户到达的间隔时间服从指数分布（均值为10分钟）；每个客户的服务时间服从均匀分布U10，15。第2步 构造模拟模型输人因素：客户的到达间隔时间和服务时间；排队规则：先到先服务；一个服务机构。第3步 模拟实验。设置模拟时钟及总的运行时间T，如8小时等。推进原则按下次事件推进或均匀间隔推进。2、用MATLAB编制程序如下：for n=1:10 arrive=zeros(1,n);for i=2:n arrive(i)=arrive(i-1)+exprnd(0.1);end wait=zeros(1,n);for i=1:n if (i=1) wait(i)=0; else servetime=unifrnd(10,15); if (arrive(i-1)+servetime+wait(i-1)arrive(i) wait(i)=arrive(i-1)+servetime+wait(i-1)-arrive(i); else wait(i)=0;endendend meantime=mean(wait)end运行结果meantime = 0meantime = 7.2542meantime = 12.1298meantime = 20.0985meantime = 26.8833meantime = 32.