最优化实例和matlab源程序文件

1、最优化平时作业一、目标规划1题目：见书中例题P110例42、 解题方法：利用Lingo求解3、具体步骤1.对应于第一优先等级，建立线性规划问题：model:min=-di;5*x1+10*x2<=60;x1-2*x2+d1_-d 仁0;end运行结果：-d仁02 对应于第二优先等级，将-d1=0作为约束条件，建立线性规划问题：min=d2_;5*x1+10*x2<=60;x1-2*x2+d1_-d 仁0;4*x1+4*x2+d2_-d2=36;-d 1=0;end运行结果：d2=0;3.对应于第三优先等级，将 -d仁0,-d仁0 作为约束条件，建立线性规划问题:min=d3_;5*

2、x1+10*x2<=60;x1-2*x2+d1_-d 仁0;4*x1+4*x2+d2_-d2=36;6x1+8*x2+d3_-d3=48;-d 1=0;d2=0;end运行结果：d3=0;X1X24.8000002.400000二、动态规划之0-1背包问题1、 题目：给定n种物品和一背包。物品i的重量是 Wi，其价值为 Vi，背包的容量是 c，问应 如何选择装入背包中的物品，使得装入背包中物品的总价值最大。2、 解题方法与思路：利用java求解，.思想方法是回溯思想3、需求分析对于给定n种物品和一背包。在容量最大值固定的情况下，要求装入的物品价值最大化4、java源程序与运行结果Back

3、Trace.java* To cha nge this template, choose Tools | Template Man ager* and ope n 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;kn apsack(v,w,c);Sys

4、tem.out.pri ntln( bestp);/ 比拟两个元素大小的类private static class Eleme nt impleme nts Comparable int id;double d;private Eleme nt(i nt idd,double dd) id=idd;d=dd;public int compareTo(Object x) double xd=(Eleme nt)x).d; if(d<xd)retur n -1; if(d=xd)retur n 0;return 1;public boolea n equals(Object x) retur

5、 n d=(Eleme nt)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 in t sortX;/ static int bestX;/排好序之后的解最有解static Date date = n ull; / jve:decl-in dex=0:public static

6、double kn apsack(doublepp,doubleww,double cc) c=cc;n=ppen gth-1;cw=0.0;cp=0.0;bestp=0.0;Eleme ntq=new Eleme nt n;/q为单位重量价值数组for(i nt i=1;i<=n ;i+)qi-1=new Eleme nt(i,ppi/wwi);MergeSort.mergeSort(q);p=new double n+1; w=new double n+1;x=new intn+1;sortX=new in t n+1;bestX=new intn +1;for(i nt i=1;i

7、<=n ;i+)pi=ppq n-i.id;wi=wwq n-i.id; sortXi=q n-i.id;backtrack(1);/回溯搜索return bestp;private static void backtrack(i nt i)if(i>=n)if(cp>bestp) bestp=cp;for(i nt j=1;j<=n ;j+) bestXj=xj; return;/搜索子树if(cw+wi<=c)/进入左子树xsortXi=1;cw+=wi;cp+=pi;backtrack(i+1);cw-=wi;cp-=pi;if(bou nd(i+1)>

8、;bestp)xsortXi=0;backtrack(i+1);/进入右子树/计算上界private static double boun d(i nt i)double cleft=c-cw;double boun d=cp;/以物品重量价值递减顺序装入物品while(i<=n&&wi<=cleft)cleft-=wi; boun d+=pi;i+;/装满背包if(i<=n)bou nd+=pi/wi*cleft;retur n bound;public static Stri ng getX()Stri ng solutio n=Stri ng.value

9、Of(bestX1);for(i nt i=2;i<bestX.le ngth;i+)soluti on+=","solutio n+=Stri ng.valueOf(bestXi);retur n soluti on;public static double getBestValue()return bestp;三、最短路径问题：给定距离矩阵，求第一点到其它点的最短距离1题目：给定以下矩阵，求第一点到其余各点的最短路径0504025105001520251501020402010010252520100551025255502、解题方法:利用matlab求解3、具体

10、步骤：源程序与运行结果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:le ngth(a)=0;pb(1)=1;d(1:le ngth (a) )=M;d(1)=0;temp=1;while sum(pb)<le ngth(a)tb=fi nd(pb=O);d(tb)=mi n(d(tb),d

11、(temp)+a(temp,tb);tmpb=fi nd(d(tb)=mi n(d(tb);temp=tb(tmpb(1);pb(temp)=1;end运行输出，第一个点到其它各点的最短路径长度，即:d = 035 45352510四、关键路径问题1.题目要求：某工程由下表作业组成，计算出其关键路径。作业方案完成时间紧前工作A5/B10/C11/D4BE4AF15CDG21BEH35BEI25BEJ15F,G,IK20FG2. 解题方法：用lingo求解3. LINGO源程序sets :eve nt/1.8/: et, lt;active(eve nt, eve nt)/! A B C D E

12、 0 F G H I 0 J K;1,2 1,3 1,4 3,4 2,5 3,5 4,6 5,6 5,8 5,7 6,7 7,8 6,8/: d, tf, ff;en dsetsdata :d = 5 10 11 4 4 0 15 21 35 25 0 15 20; en ddatan=size (event);et=0;for (event(k) | k #gt# 1:et(k)= maXactive(i,k): et(i)+d(i,k);)；lt( n)=et( n);for (event(k) | k #lt# n:lt(k)= mi n(active(k,j): et(j)-d(k,j

13、););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元/件； 每个零件的存贮费用为 0.3元/ (件月); 每个零件的缺货损失为1.1元/ (件月)。公司应如何安排这些零件的订货时间与订货规模，使得

14、全部费用最少？ 设该零件的每月需求量为800件.(1) 试求今年该公司对零件的最正确订货存贮策略与费用；(2) 假设明年对该零件的需求将提高一倍，那么需零件的订货批量应比今年增加多少？订货次 数以为多少？解：取一年为单位时间，由假设，订货费 CD = 12000元/次，存贮费 Cp= 3.6 (件年)，需求率D = 96000件/年，代入相关的公式得到：tc2CdD25298960002 1200 96000I360.2635252982CdCpD 2 3.6 12000 96000910732. LINGO源程序(1)MODEL:C_D = 12000;D = 96000;C_P = 3.6

15、;Q = (2*C_D*D/C_P)a0.5;T = Q/D;n = 1/T;TC = 0.5*C_P*Q+C_D*D/Q;END1 n = 3.7947全年的订货次数为T次sets:times/1.2/: n, Q, TC;en dsetsdata:n = 3, 4;C_D = 12000;D = 96000;C_P = 3.6;en ddatafor(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;en dse

16、tsfor(order(i):EOQ(i)=D/i;TC(i)=0.5*C_P*EOQ(i)+C_D*D/EOQ(i););TC_mi n=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;en ddataEND结果显示：一年组织4次订货(每季度1次)，每次的订货量为 24 000件，最优费用为91200 元六、矩阵对策给定以下矩阵，求最优决策1、题目：见书中 P337例72、 解题方法与思路：转化为线性规划问题，再用lin go求解3、具体步

17、骤：源程序与运行结果(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

18、*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:10arrive=zeros(1, n);for i=2:narrive(i)=arrive(i-1)+exprnd(0.1);endwait=zeros(1, n);for i=1:nif (i=1)wait(i)=0;elseservetime=u nifrn d(10,15);if (arrive(i-1)+servetime+wait(i-1)>arrive(i)wait(i)=arrive(i-1)+servetime+wait(i-1)-arrive(i);elsewait(i)=0;endendendmean time=mea n( wait) end运行结果