实验5 动态规划.doc

年级、专业 2011应数2班 姓名 学号 名单序号 实验时间 2013年 5 月 16 日 MATLAB版本： R2010b 注：实验报告的最后一部分是实验小结与收获 实验五 动态规划1. 某公司打算向它的四个营业区增设4个销售点，从各区赚取的利润与增设的销售店个数有关，其数据为： 第1题数据表（数据文件：动态规划 Prob_1.xls ）销售店增加数第一区利润（万元）第二区利润（万元）第三区利润（万元）第四区利润（万元）01601902002501310225298308254144539948736005176016554705632721674 试求各区应分配几个增设的销售店，才能使总利润最大？其值是多少？%以下各题均要应用此逆序算法函数：dynprog函数function p_opt,fval=dynprog(x,DecisFun,SubObjFun,TransFun,ObjFun)% x为状态变量，一列代表一个阶段的状态% M_函数DecisFun（k,x)表示由阶段k的状态值x求出相应的允许决策集合% M_函数SubObjFun（k,x,u)表示阶段k的指标函数% M_函数TransFun（k,x,u)是状态转移函数，其中x是阶段k的状态值，u是其决策集合% M_函数ObjFun（v,f)是第k阶段到最后阶段的指标函数，当ObjFun（v,f)=v+f时，输入ObjFun（v,f)可以省略% 输出p_opt由4列组成，p_opt=序号组，最优轨线组，最优策略组，指标函数值组;% 输出fval是列向量，各元素分别表示p_opt各最优策略组对应始端状态x的最优函数值k=length(x(1,:); % k为阶段数x_isnan=isnan(x);t_vub=inf;t_vubm=inf*ones(size(x); % t_vubm为指标函数值的上限f_opt=nan*ones(size(x);% f_opt为不同阶段、状态下的最优值矩阵，初值为非数d_opt=f_opt; % d_opt为不同阶段不同状态下的决策矩阵，初值为非数tmp1=find(x_isnan(:,k); % 找出第k阶段状态值（不是非数）的下标tmp2=length(tmp1);for i=1:tmp2 u=feval(DecisFun,k,x(tmp1(i),k);% 求出相应的允许决策向量 tmp3=length(u); for j=1:tmp3 % 该for语句是为了求出相应的最有函数值以及最优决策 tmp=feval(SubObjFun,k,x(tmp1(i),k),u(j); if tmp=t_vub f_opt(i,k)=tmp; d_opt(i,k)=u(j); t_vub=tmp; end endendfor ii=k-1:-1:1% 从后往前面递推求出f_opt 以及d_opttmp10=find(x_isnan(:,ii);tmp20=length(tmp10);for i=1:tmp20 u=feval(DecisFun,ii,x(i,ii); tmp30=length(u); for j=1:tmp30 tmp00=feval(SubObjFun,ii,x(tmp10(i),ii),u(j); tmp40=feval(TransFun,ii,x(tmp10(i),ii),u(j); % 由该状态值及相应的决策值求出下一阶段的状态值 tmp50=x(:,ii+1)-tmp40; tmp60=find(tmp50=0); % 找出下一阶段的状态值在x(:,ii+1)的下标 if isempty(tmp60) if nargin5,tmp00=tmp00+f_opt(tmp60(1),ii+1); else tmp00=feval(ObjFun,tmp00,f_opt(tmp60(1),ii+1); end if tmp00 x=0;1;2;3;4;x=x,x,x,x; p,f=dynprog(x,eg13f1_4,eg13f2_4,eg13f3_4)p = 1 0 0 -160 2 0 0 -190 3 0 0 -200 4 0 0 -250 1 1 1 -310 2 0 0 -190 3 0 0 -200 4 0 0 -250 1 2 2 -541 2 0 0 -190 3 0 0 -200 4 0 0 -250 1 3 2 -541 2 1 0 -190 3 1 1 -298 4 0 0 -250 1 4 2 -541 2 2 2 -445 3 0 0 -200 4 0 0 -250f = -800 -950 -1181 -1279 -1436由此可知最佳方案为1 2两个营业区各设2个销售点，可得总利润1436万元！2下图为一线路网络，要铺设从v1点到v10点的电话线，中间需经过3个点。第1点可以是v2、v3、v4中的某一个点，第2点可以是v5、v6、v7中的一个点，第3点可以是v8、v9中的一个点。各点之间若能铺设电话线，则在图中以连线表示，连线旁的数字表示两点间的距离。用动态规划方法求一条从v1至v10的最短路线。V2vV1V33V4V6V7V8V9V1034677456354234366V5第2题图1、决策变量函数：% eg13f1_3.mfunction u=eg13f1_3(k,x)if x=1,u=2;3;4;elseif x=2,u=5;6;elseif x=3,u=5;6;7;elseif x=4,u=6;7;elseif x=5,u=8;elseif x=6,u=8;9;elseif x=7,u=8;9;elseif x=8,u=10;elseif x=9,u=10;elseif x=10,u=10;end3、 阶段指标函数：% eg13f2_3.mfunction v=eg13f2_3(k,x,u)tt=3;6;4;7;7;4;5;6;5;3;4;2;3;6;6;3;4;tmp=x=1&u=2,x=1&u=3,x=1&u=4,x=2&u=5,x=2&u=6,x=3&u=5,x=3&u=6,. x=3&u=7, x=4&u=6, x=4&u=7,x=5&u=8,x=6&u=8,x=6&u=9,x=7&u=8,x=7&u=9,x=8&u=10,x=9&u=10;v=tmp*tt;3、第k段到最后阶段指标函数：% eg13f3_3.mfunction y=eg13f3_3(k,x,u)y=u;输入条件运行程序： x=nan*ones(3,5); x(1,1)=1;x(1:3,2)=2;3;4;x(1:3,3)=5;6;7;x(1:2,4)=8;9;x(1,5)=10; p,f=dynprog(x,eg13f1_3,eg13f2_3,eg13f3_3)p = 1 1 4 4 2 4 6 5 3 6 8 2 4 8 10 3 5 10 10 0f =14由此可知最短路径为1-4-6-8-10，距离为143. 某船厂接受七艘船的订货，要求第一、二、三、四季度末分别交货1、1、2、3艘，该厂每季度的生产能力为2艘，预计各季度的单位生产成本为4、6、7、9，各季度多生产的船可存在仓库中，其每季度每条船的保管费为1.2，试制定一个完成订货合同且总费用最省的生产计划。1决策变量函数:qqq.mfunction u=DecisF_1(k,x)c=4, 6, 7, 9;q=1, 1 ,2, 3;if q(k)-x x=nan*ones(3,4); x(1,1)=0; x(1:2,2)=(0:1); x(2:3,3)=(1:2); x(2:3,4)=(1:2); p,f=dynprog(x,qqq,www,eee)p = 1.0000 0 2.0000 8.0000 2.0000 1.0000 2.0000 13.2000 3.0000 2.0000 2.0000 16.4000 4.0000 2.0000 0 2.4000 1.0000 1.0000 2.0000 9.2000 2.0000 2.0000 1.0000 8.4000 3.0000 2.0000 2.0000 16.4000 4.0000 2.0000 0 2.4000 1.0000 2.0000 2.0000 10.4000 2.0000 3.0000 0 3.6000 3.0000 2.0000 2.0000 16.4000 4.0000 2.0000 0 2.4000f = 40.0000 36.4000 32.8000在这里设的初始量为0-2由此可知最佳方案为：在初始量为零的情况下第一、二、三个月各生产两件，第四个月生产1件，最小成本为40选做题 某电子设备由5种元件1、2、3、4、5组成，这5种元件的可靠性分别为0.9、0.8、0.5、0.7、0.6。为保证电子设备系统的可靠性，同种元件可并联多个。现允许设备使用元件的总数为15个，问如何设计使设备可靠性最大的元件安排方案。function u=DecisF1(k,x)if k=5,u=x;else u=1:x-1endu=u(:);function v=SubObjF1(k,x,u)c=0.9 0.8 0.5 0.7 0.6;v=1-(1-c(k).u;v=-v;function y=TransF1(k,x,u)y=x-u;function y=ObjF1(v,f)y=v*f;y=-y; n=15; x1=n;nan*ones(n-1,1);x2=1:n;x2=x2;x=x1 x2 x2 x2 x2; p,f=dynprog(x,DecisF1,SubObjF1,TransF1,ObjF1)p = 1.0000 15.0000 2.0000 -0.9900 2.0000 13.0000 2.0000 -0.9600 3.0000 11.0000 4.0000 -0.9375 4.0000 7.0000 3.0000 -0.9730 5.0000 4.0000 4.0000 -0.9744f