实验七.规划问题
一.实验目的：
学会用matlab 优化工具箱求解线性规划，非线性规划。
二.实验原理与方法
线性规划问题是目标函数和约束条件均为线性函数的问题，其标准数学模型为：
写成矩阵形式：
x
T
c min
其中
???????????????=n c c c c 21 ?????
??????????=n x x x x 21
?????
?????
???
??<=<=???<=<==+???++???????????????=+???++<=???++??????????????????<=+???++<=???+++???++++++++++u
n n l n u l k
m n n k m k m k m m n m m m m n mn m m n n n n n x x x x x x b x a x a x a b a x a x a b x a x a x a b a x a a b x a x a x a x c x c x c ,,,,11,1,22,11,1,122,111,1221
12222221112121
112211,min ub
x lb beq x Aeq b
Ax <=<==?<=
???????
???
?????????????????????=mn m m n n a a a a a a a a a A 2
1
22221
11211
????
?
??????????=
m b b b b 2
1 ??????
?
???
?????????????????=+++++++++n k m k m k m n m m m n m m m a a a a a a a a a Aeq ,2
,1
,,22,21
,2,12,11
,1...
???
?
?????
??????=+++k m m m b b b beq 21 ?????
?
?????????=
l n l l x x x lb ,,2,1
?????
????
??????=u n u
u x x x ub ,,2,1 用MATLAB 优化工具箱解线性规划
命令：x=linprog （c ，A ，b ）
2、模型：
beq
AeqX b AX ..min =≤=t s cX z
命令：x=linprog （c ，A ，b ，Aeq,beq ）
注意：若没有不等式：b AX ≤存在，则令A=[ ]，b=[ ]. 若没有等式约束, 则令Aeq=[ ], beq=[ ]. 3、模型： VUB
X VLB beq AeqX b AX ..min ≤≤=≤=t s cX z
命令：[1] x=linprog （c ，A ，b ，Aeq,beq, VLB ，VUB ）
[2] x=linprog （c ，A ，b ，Aeq,beq, VLB ，VUB, X0）
注意：[1] 若没有等式约束, 则令Aeq=[ ], beq=[ ]. [2]其中X0表示初始点 4、命令：[x,fval]=linprog(…)
min z=cX
b
AX t s
≤..1、模型：
返回最优解ｘ及ｘ处的目标函数值fval.
例1 max 6543216.064.072.032.028.04.0x x x x x x z +++++= 85003.003.003.001.001.001.0.
.654321≤+++++x x x x x x t s
70005.002.041≤+x x 10005.002.052≤+x x 90008.003.063≤+x x
6,2,10
=≥j x j
解 编写M 文件小xxgh1.m 如下：全部变为min 时对其进行计算 c=[-0.4 -0.28 -0.32 -0.72 -0.64 -0.6];
A=[0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08];
b=[850;700;100;900]; Aeq=[]; beq=[];
vlb=[0;0;0;0;0;0]; vub=[];
[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)
例2 321436min x x x z ++=
120.
.321=++x x x t s
301≥x 5002≤≤x 203≥x
解: 编写M 文件xxgh2.m 如下： c=[6 3 4]; A=[0 1 0]; b=[50];
Aeq=[1 1 1]; beq=[120];
vlb=[30,0,20];
vub=[];
[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)
例3 （任务分配问题）某车间有甲、乙两台机床，可用于加工三种工件。 假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、 600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工 费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使 加工费用最低？
解 设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上 加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：
6543218121110913min x x x x x x z +++++=
????
?????
??=≥≤++≤++=+=+=+6
,,2,1,0900
3.12.15.08001.1
4.0500600400x ..6
54321635241 i x x x x x x x x x x x x t s i
编写M 文件xxgh3.m 如下: f = [13 9 10 11 12 8];
A = [0.4 1.1 1 0 0 0
0 0 0 0.5 1.2 1.3]; b = [800; 900]; Aeq=[1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1]; beq=[400 600 500]; vlb = zeros(6,1);
vub=[];
[x,fval] = linprog(f,A,b,Aeq,beq,vlb,vub)
非线性规划 1、 二次规划
用MA TLAB 软件求解,其输入格式如下: 1. x=quadprog(H,C,A,b);
2. x=quadprog(H,C,A,b,Aeq,beq);
3. x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB);
4. x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0);
5. x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0,options);
6.
[x,fval]=quaprog(...);
7. [x,fval,exitflag]=quaprog(...);
8. [x,fval,exitflag,output]=quaprog(...); 例1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22
标准型为： Min Z= 21X T HX+c T X s.t. AX<=b beq X Aeq =? VLB ≤X ≤VUB
s.t. x1+x2≤2 -x1+2x2≤2 x1≥0, x2≥0 1、写成标准形式：
2、 输入命令：
H=[1 -1; -1 2];
c=[-2 ;-6];A=[1 1; -1 2];b=[2;2]; Aeq=[];beq=[]; VLB=[0;0];VUB=[]; [x,z]=quadprog(H,c,A,b,Aeq,beq,VLB,VUB) 3、运算结果为：
x =0.6667 1.3333 z = -8.2222
一般非线性规划 标准型为：
min F(X)
s.t AX<=b beq X Aeq =? G(X)0≤ Ceq(X)=0 VLB ≤X ≤VUB
其中X 为n 维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量，其它变量的含义与线
性规划、二次规划中相同.用Matlab 求解上述问题，基本步骤分三步： 1. 首先建立M 文件fun.m,定义目标函数F （X ）:
function f=fun(X); f=F(X);
2. 若约束条件中有非线性约束:G(X)0≤或Ceq(X)=0,则建立M 文件nonlcon.m 定义函数G(X)
与Ceq(X):
function [G,Ceq]=nonlcon(X) G=... Ceq=...
3. 建立主程序.非线性规划求解的函数是fmincon,命令的基本格式如下： (1) x=fmincon (‘fun’,X0,A,b)
(2) x=fmincon (‘fun’,X0,A,b,Aeq,beq)
(3) x=fmincon (‘fun’,X0,A,b, Aeq,beq,VLB,VUB)
(4) x=fmincon (‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’)
???
?
???
??
?
??--+???? ?????? ??-=212121622 11- 1 ),(min x x x x x x z T
?
??
?
??≤???? ?????
?
??≤???? ?????? ??-212100222 11 1 x x x x s.t.
(5)x=fmincon (‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’,options)
(6) [x,fval]= fmincon(...)
(7) [x,fval,exitflag]= fmincon(...)
(8)[x,fval,exitflag,output]= fmincon(...) 注意：
[1] fmincon 函数提供了大型优化算法和中型优化算法。默认时，若在fun 函数中提供了梯度（options 参数的GradObj 设置为’on’），并且只有上下界存在或只有等式约束，fmincon 函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。
[2] fmincon 函数的中型算法使用的是序列二次规划法。在每一步迭代中求解二次规划子问题，并用BFGS 法更新拉格朗日Hessian 矩阵。
[3] fmincon 函数可能会给出局部最优解，这与初值X0的选取有关。 例2 2
22
1212
1212min x x x x f +
+
--=
s.t.0
,546
32212121≥≤+≤+x x x x x x
2、先建立M-文件 fun3.m:
function f=fun3(x);
f=-x(1)-2*x(2)+(1/2)*x(1)^2+(1/2)*x(2)^2 3、再建立主程序youh2.m ： x0=[1;1]; A=[2 3 ;1 4]; b=[6;5]; Aeq=[];beq=[];
VLB=[0;0]; VUB=[];
[x,fval]=fmincon('fun3',x0,A,b,Aeq,beq,VLB,VUB) 4、运算结果为：
1、写成标准形式：
.
s.t
??
? ??≤??? ??-+-+00546322121x x x x ??
? ??≤??? ??2100x x 2
2
2
1212
1212min x x x x f +
+
--=
x = 0.7647 1.0588 fval = -2.0294 例3
1005.10
..)12424()(min 212121212212
22
11≤--≤--+=+++++=x x x x x x x x t s x x x x x e x f x
1．先建立M 文件 fun4.m,定义目标函数: function f=fun4(x);
f=exp(x(1))
*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1); 2．再建立M 文件mycon.m 定义非线性约束： function [g,ceq]=mycon(x)
g=[x(1)+x(2);1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10]; 3．主程序youh3.m 为: x0=[-1;1]; A=[];b=[]; Aeq=[1 1];beq=[0];
vlb=[];vub=[];
[x,fval]=fmincon('fun4',x0,A,b,Aeq,beq,vlb,vub,'mycon') 3. 运算结果为：
x = -1.2250 1.2250 fval = 1.8951
三实验内容
1：某厂每日8小时的产量不低于1800件。为了进行质量控制，计划聘请两种不同水平的检验员。一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15小时/件，正确率95%，计时工资3元/小时。检验员每错检一次，工厂要损失2元。为使总检验费用最省，该工厂应聘一级、二级检验员各几名？ 2求解如下二次优化问题。
212
22
1108)(min x x x x x f --+= 623.
.21≤+x x t s
0,21≥x x
3.设有400万元资金, 要求4年内使用完, 若在一年内使用资金x 万元, 则可得效益x 万元(效益不能再使用),当年不用的资金可存入银行, 年利率为10%. 试制定出资金的使用计划, 以使4年效益之和为最大.
§1动态规划模型 如图所示，给定一个线路网络，两点之间连线上的数字表示 两点间距离，试求一条从A到E的路线，使总距离为最短。Mattlab求解： 首先利用Excel建立两个工作表edge和n分别存储图的上三 角阵和顶点数量。其中edge= 99999 5 2 99999 99999 99999 99999 99999 99999 99999 99999 99999 3 7 99999 99999 99999 99999 99999 99999 99999 99999 6 3 99999 99999 99999 99999 99999 99999 99999 99999 99999 6 99999 99999 99999 99999 99999 99999 99999 99999 3 8 99999 99999 99999 99999 99999 99999 99999 99999 1 99999 99999 99999 99999 99999 99999 99999 99999 99999 3 99999 99999 99999 99999 99999 99999 99999 99999 7 99999 99999 99999 99999 99999 99999 99999 99999 99999 n=9,然后在Matlab调入以上数据。同时将自编的动态规划 软件“dynamic.m”调入当前目录之中，在Matlab命令窗口
输入dynamic,回车后则在窗口显示出路径Path 和距离distance §2 最小生成树 例1 某工厂要架设局域网联通工厂各个部门。已知工厂有7个部门，各个部门间铺设网线的距离如上图所示，计算出铺设网线的最短距离。 Matlab 的算法： 首先，将上图的邻接矩阵存储为G ,顶点数存储为N ；即：G= 99999 50 60 99999 99999 99999 99999 50 99999 99999 65 40 99999 99999 60 99999 99999 52 99999 99999 45 99999 65 52 99999 50 30 42 99999 40 99999 50 99999 70 99999 99999 99999 99999 30 70 99999 99999 99999 99999 45 42 99999 99999 99999 2 5 3 1 4 7 6 50 60 45 65 52 40 50 70 30 42
动态规划求解方法的Matlab实现及应用[1].txt我自横刀向天笑，笑完我就去睡觉。你的手机比话费还便宜。路漫漫其修远兮，不如我们打的吧。第 %卷第 ,期信息工程大学学报 S>:+% <>+, !""’年 >月 T>8D3F: >C 53C>DEFB2>3 G3?23@@D23? 032H@DA2BI 6@N+!""’ !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !! 动态规划求解方法的 !"#$"%实现及应用 于斌，刘姝丽，韩中庚 <信息工程大学信息工程学院，河南郑州 #’"""!） 摘要：文章对动态规划问题的求解方法进行了分析研究，根据问题的特点、难点和关键点做了 针对性的处理，然后用 !"#$"%做了实现尝试，从而实现了“最佳组队”和“最短路线”等问题的 求解。实践证明所采用方法和程序都是有效的。 关键词：动态规划；基本方程；!"#$"%实现；最佳组队 中图分类号：* !!&+,文献标识码：-文章编号：&%.& $ "%.,’
$ "# !"#$"% &’"$(>"#(*+ *, #-’ ./+"0(1 23*43"00(+4 5663*"1-"+7 8#9 566$(1"#(*+ /0 123，450 6789:2，。-< =7>3?9?@3? <53AB2B8B@ >C 53C>DEFB2>3 G3?23@@D23?，53C>DEFB2>3 G3?23@@D23? 032H@DA2BI，=7@3?J7>8 #’"""!，K723F） 5%9#3"1#：1I F3F:IJ23? F3L 23H@AB2?FB23? B7@ LI3FE2M ND>?DFEE23? FNND>FM7，F3 @CC@MB2H@ L2AN>AF: 7FA O@@3 L>3@
数学规划课程设计 题目：销售人员费配问题 姓名： 学号： 成绩： 2011年6月
销售人员费配问题 摘要：动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法，本论文通过对动态规划的基本概念和基本思路，并利用Matlab对动态规划中的销售人员分配问题进行了分析，然后利用Matlab语言进行了程序设计和计算，是复杂问题简单化，避免了繁琐的计算，从而使问题能跟方便地得到解决。 关键词：动态规划销售人员分配问题Matlab语言
一、问题重述 某企业甲、乙、丙三个销售市场，其市场的利润与销售人员的分配有关，现有6个销售人员， 二、问题分析 首先我们对设备的分配规定一个顺序，即先考虑分配给甲市场，其次乙市场，最后丙市场，但分配时必须保证企业的总收益最大。 将问题按分配过程分为三个阶段，根据动态规划逆序算法，可设： 1、阶段数k=1，2，3（即甲、乙、丙三个市场的编号分别为1，2，3）； 2、状态变量x k 表示分配给第k 个市场至第3个市场的人员数（即第k 阶段初尚未分配的人员数）； 3、决策变量u k 表示分配给第k 市场的人员数； 4、状态转移方程：x k+1=x k -u k ; 5、g k (u k )表示u k 个销售人员分配到第k 个市场所得的收益值，它由下表可查得； 6、f k (x k )表示将x k 个销售人员分配到第k 个市场所得到的最大收益值，因而可得出递推方程： f k (x k )= 6 ,...,1,0max =k u [ g k (u k )+ f k+1(x k -u k )]，k=1，2，3 f 4(x 4)=0 三、问题求解 1）k=3时，市场丙的分配方案和总收益. 最大收益：f 3(x 3)=6 ,...,1,0max 3=u [g 3(x 3)]
第九章最优化方法的MatIab实现 在生活和工作中，人们对于同一个问题往往会提出多个解决方案，并通过各方面的论证从中提取最佳方案。最优化方法就是专门研究如何从多个方案中科学合理地提取出最佳方案的科学。由于优化问题无所不在，目前最优化方法的应用和研究已经深入到了生产和科研的各个领域，如土木工程、机械工程、化学工程、运输调度、生产控制、经济规划、经济管理等，并取得了显著的经济效益和社会效益。 用最优化方法解决最优化问题的技术称为最优化技术，它包含两个方面的内容： 1）建立数学模型即用数学语言来描述最优化问题。模型中的数学关系式反映了最优化问题所要达到的目标和各种约束条件。 2）数学求解数学模型建好以后，选择合理的最优化方法进行求解。 最优化方法的发展很快，现在已经包含有多个分支，如线性规划、整数规划、非线性规划、动态规划、多目标规划等。 9.1 概述 利用Matlab的优化工具箱，可以求解线性规划、非线性规划和多目标规划问题。 具体而言，包括线性、非线性最小化，最大最小化，二次规划，半无限问题，线性、非线性方程（组）的求解，线性、非线性的最小二乘问题。另外，该工具箱还提供了线性、非线性最小化，方程求解，曲线拟合，二次规划等问题中大型课题的求解方法，为优化方法在工程中的实际应用提供了更方便快捷的途径。 9.1.1优化工具箱中的函数 优化工具箱中的函数包括下面几类： 1 ?最小化函数
2.方程求解函数 3.最小—乘（曲线拟合）函数
4?实用函数 5 ?大型方法的演示函数 6.中型方法的演示函数 9.1.3参数设置 利用OPtimSet函数，可以创建和编辑参数结构；利用OPtimget函数，可以获得o PtiOns优化参数。 ? OPtimget 函数 功能：获得OPtiOns优化参数。 语法：
动态规划方法的Matlab 实现与应用 动态规划(Dynamic Programming)是求解决策过程最优化的有效数学方法，它是根据“最优决策的任何截断仍是最优的”这最优性原理，通过将多阶段决策过程转化为一系列单段决策问题，然后从最后一段状态开始逆向递推到初始状态为止的一套最优化求解方法。 1．动态规划基本组成 (1) 阶段 整个问题的解决可分为若干个阶段依次进行，描述阶段的变量称为阶段变量，记为k (2) 状态 状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况。各阶段状态通常用状态变量描述，用k x 表示第k 阶段状态变量，n 个阶段决策过程有n+ 1个状态。 (3) 决策 从一确定的状态作出各种选择从而演变到下一阶段某一状态，这种选择手段称为决策。描述决策的变量称为决策变量，决策变量限制的取值范围称为允许决策集合。用()k k u x 表示第k 阶段处于状态k x 时的决策变量，它是k x 的函数。用()k k D x Dk(xk)表示k x 的允许决策的集合。 (4) 策略 每个阶段的决策按顺序组成的集合称为策略。由第k 阶段的状态k x 开始到终止状态的后部子过程的策略记为{}11(),(),,()k k k k n n u x u x u x ++ 。可供选择的策略的范围称为允许策略集合，允许策略集合中达到最优效果的策略称为最优策略。从初始状态* 11()x x =出发，过程按照最优策略和状态转移方程演变所经历的状态序列{ } **** 121,,,,n n x x x x + 称为最优轨线。 (5) 状态转移方程 如果第k 个阶段状态变量为k x ，作出的决策为k u ，那么第k+ 1阶段的状态变量1k x +也被完全确定。用状态转移方程表示这种演变规律，记为1(,)k k k x T x u +=。 (6) 指标函数 指标函数是系统执行某一策略所产生结果的数量表示，是衡量策略优劣的数量指标，它定义在全过程和所有后部子过程上，用()k k f x 表示。过程在某阶段j 的阶段指标函数是衡量该阶段决策优劣数量指标，取决于状态j x 和决策j u ，用(,)j j j v x u 表示。 2．动态规划基本方程 (){} 11()min ,,(),()k k k k k k k k k k f x g v x u f x u D x ++=∈???? Matlab 实现 (dynprog.m 文件) function [p_opt,fval]=dynprog (x,DecisFun,SubObjFun,TransFun,ObjFun) % x 是状态变量，一列代表一个阶段的所有状态； % M-函数DecisFun(k,x) 由阶段k 的状态变量x 求出相应的允许决策变量; % M-函数SubObjFun(k,x,u) 是阶段指标函数, % M-函数ObjFun(v,f) 是第k 阶段至最后阶段的总指标函数 % M-函数TransFun(k,x,u) 是状态转移函数, 其中x 是阶段k 的某状态变量, u 是相应的决策变量; %输出 p_opt 由4列构成，p_opt=[序号组;最优策略组;最优轨线组;指标函数值组]； %输出 fval 是一个列向量，各元素分别表示p_opt 各最优策略组对应始端状态x 的最优函数值。
图论实验三个案例 单源最短路径问题 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点，记()l v 为顶点 v 到源点v 1的最短距离， ,i j v v V ?∈，若 (,)i j v v E ?，记i v 到j v 的权ij w =∞。 Dijkstra 算法： ① 1{}S v =,1()0l v =；1{}v V v ??-,()l v =∞,1i =,1{}S V v =-； ② S φ=，停止，否则转③； ③ ()min{(),(,)} j l v l v d v v =， j v S ∈，v S ?∈； ④ 存在 1 i v +，使 1()min{()} i l v l v +=，v S ∈； ⑤ 1{} i S S v +=， 1{} i S S v +=-，1i i =+，转②； 实际上，Dijkstra 算法也是最优化原理的应用：如果12 1n n v v v v -是从1v 到 n v 的最短路径，则 12 1 n v v v -也必然是从1v 到 1 n v -的最优路径。 在下面的MATLAB 实现代码中，我们用到了距离矩阵，矩阵第i 行第j 行元 素表示顶点i v 到j v 的权ij w ，若i v 到j v 无边，则realmax ij w =，其中realmax 是 MATLAB 常量，表示最大的实数+308)。 function re=Dijkstra(ma)
一、问题重述 某企业甲、乙、丙三个销售市场，其市场的利润与销售人员的分配有关，现有6个销售人员，分配到各市场所获利润如下表示，试问应如何分配销售人员才能使总利润最大？ 二、问题分析 首先我们对设备的分配规定一个顺序，即先考虑分配给甲市场，其次乙市场，最后丙市场，但分配时必须保证企业的总收益最大。 将问题按分配过程分为三个阶段，根据动态规划逆序算法，可设： 1、阶段数k=1，2，3（即甲、乙、丙三个市场的编号分别为1，2，3）； 2、状态变量x k 表示分配给第k 个市场至第3个市场的人员数（即第k 阶段初尚未分配的人员数）； 3、决策变量u k 表示分配给第k 市场的人员数； 4、状态转移方程：x k+1=x k -u k ; 5、g k (u k )表示u k 个销售人员分配到第k 个市场所得的收益值，它由下表可查得； 6、f k (x k )表示将x k 个销售人员分配到第k 个市场所得到的最大收益值，因而可得出递推方程： f k (x k )= 6 ,...,1,0max =k u [ g k (u k )+ f k+1(x k -u k )]，k=1，2，3 f 4(x 4)=0 三、问题求解 1）k=3时，市场丙的分配方案和总收益. 最大收益：f 3(x 3)=6 ,...,1,0max 3=u [g 3(x 3)]
最大收益：f 2(x 2)=2 max u [g 2(u 2)+ f 3(x 3)]= 2 max u [g 2(u 2)+ f 3(x 2- u 2 )] 最大收益：f 1(x 1)=1 max u [g 1(u 1)+ f 2(x 1- u 1)]= max[g 1(u 1)+ f 2(4- u 1)] 为此，我们可以用Matlab 语言编程使问题能跟方便地得到解决，其算法设计如下图：
第四章动态规划 §1 引言 1.1 动态规划的发展及研究内容 动态规划（dynamic programming）是运筹学的一个分支，是求解多阶段决策问题的最优化方法。20世纪50年代初R. E. Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优性原理（principle of optimality），把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法—动态规划。1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的
一组规则，而必须对具体问题进行具体分析处理。因此，在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。 例1 最短路线问题 下面是一个线路网，连线上的数字表示两点之间的距离（或费用）。试寻求一条由A到G距离最短（或费用最省）的路线。 例2 生产计划问题 工厂生产某种产品，每单位（千件）的成本为1（千元），每次开工的固定成本为3（千元），工厂每季度的最大生产能力为6（千件）。经调查，市场对该产品的需求量第一、二、三、四季度分别为2，3，2，4（千件）。如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本（少付固定成本费），但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5（千元）。还规定年初和年末这种产品均无库存。试制定一个生产计划，即安排每个季度的产量，使一年的总费用（生产成本和存储费）最少。 1.2 决策过程的分类
动态规划在火力分配中地应用. 1.问题描述 设有m个目标，目标价值（重要性和危害性）各不相同，用数值A（K=1，K =，其n枚导弹突袭，导弹击毁目标地概率P2，..m）表 示，计划用K为向目标发射地导弹数，问是常数，取决于导弹地特性与目标地性质；中题：做出方案使预期地突击效果最大. 2.问题建模 上述问题可以表述为 约束条件为 （为非负整数） 3.算法描述 ），和（n=5am=4下面通过一个实例说明：设目标数目为4（），导弹为5K取值情况如下表所示：表1：A取值情况k 4 2 3 1 K 目标 3 6 7 8 0.9 0.3 0.2
将火力分配可分为4个阶段，每个阶段指标函数为： 可能取值为0，1，2，3，4，5，将函数值带人如下表：表2函数值 u 0 0 0 0 0 1.79 1 1.81 1.45 2.36 2.51 2 3.16 2.64 3.79 2.81 4.66 3 4.15 3.61 2.93 4 4.89 5.19 4.41
5 5.44 5.06 5.51 动态规划问题基本方程为： c =0 逐次向前推一级 K=4 K=3 K=2 K=1
（） 地最大值然后反推回去就可以获得最优地分配方案只需要求解4.Matlab仿 真求解 地最大值，对应取值为整数，可以采用动态规划地方法，获得与因为 地最优方案 function[p_opt,fval]=dynprog(x,DecisFun,SubObjFun,TransFun,ObjFun) %求解动态规划问题最小值函数 k=length(x(1,:)) %判断决策级数 x_isnan=~isnan(x)。 % 非空状态矩阵 t_vubm=inf*ones(size(x))。 % 性能指标中间矩阵 f_opt=nan*ones(size(x))。 % 总性能指标矩阵 d_opt=f_opt。 %每步决策矩阵 tmp1=find(x_isnan(:,k))。 % 最后一步状态向量 tmp2=length(tmp1)。 % 最后一步状态个数 for i=1:tmp2 u=feval(DecisFun,k,x(tmp1(i),k))。 tmp3=length(u)。%决策变量 for j=1:tmp3 % 求出当前状态下所有决策地最小性能指标 tmp=feval(SubObjFun,k,x(tmp1(i),k),u(j))。 if tmp <= t_vubm(i,k) %t_vub f_opt(i,k)=tmp。 d_opt(i,k)=u(j)。 t_vubm(i,k)=tmp。 end。 end。 end for ii=k-1:-1:1 tmp10=find(x_isnan(:,ii))。 tmp20=length(tmp10)。 for i=1:tmp20 %求出当前状态下所有可能地决策 u=feval(DecisFun,ii,x(tmp10(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。 % 找出下一状态在 x 矩阵地位置 tmp60=find(tmp50==0) 。 if~isempty(tmp60) if nargin<6 %矩阵不同需要修改nargin地值，很重要
第九章最优化方法的Matlab实现 在生活和工作中，人们对于同一个问题往往会提出多个解决方案，并通过各方面的论证从中提取最佳方案。最优化方法就是专门研究如何从多个方案中科学合理地提取出最佳方案的科学。由于优化问题无所不在，目前最优化方法的应用和研究已经深入到了生产和科研的各个领域，如土木工程、机械工程、化学工程、运输调度、生产控制、经济规划、经济管理等，并取得了显著的经济效益和社会效益。 用最优化方法解决最优化问题的技术称为最优化技术，它包含两个方面的内容：1）建立数学模型即用数学语言来描述最优化问题。模型中的数学关系式反映了最优化问题所要达到的目标和各种约束条件。 2）数学求解数学模型建好以后，选择合理的最优化方法进行求解。 最优化方法的发展很快，现在已经包含有多个分支，如线性规划、整数规划、非线性规划、动态规划、多目标规划等。 9.1 概述 利用Matlab的优化工具箱，可以求解线性规划、非线性规划和多目标规划问题。具体而言，包括线性、非线性最小化，最大最小化，二次规划，半无限问题，线性、非线性方程（组）的求解，线性、非线性的最小二乘问题。另外，该工具箱还提供了线性、非线性最小化，方程求解，曲线拟合，二次规划等问题中大型课题的求解方法，为优化方法在工程中的实际应用提供了更方便快捷的途径。 9.1.1 优化工具箱中的函数 优化工具箱中的函数包括下面几类： 1．最小化函数
表9-1 最小化函数表 2．方程求解函数 表9-2 方程求解函数表 3．最小二乘（曲线拟合）函数 表9-3 最小二乘函数表
4．实用函数 表9-4 实用函数表 5．大型方法的演示函数 表9-5 大型方法的演示函数表 6．中型方法的演示函数 表9-6 中型方法的演示函数表 9.1.3 参数设置 利用optimset函数，可以创建和编辑参数结构；利用optimget函数，可以获得o ptions优化参数。 ● optimget函数 功能：获得options优化参数。
动态规划的matlab算法，源码来自书上，只作分享用 function [p_opt,fval]=dynprog(x,DecisFun,ObjFun,TransFun) k=length(x(1,:)); x_isnan=~isnan(x); f_vub=inf; f_opt=nan*ones(size(x)); d_opt=f_opt; t_vubm=inf*ones(size(x)); tmp1=find(x_isnan(:,k)); tmp2=length(tmp1); for i=1:tmp2 u=feval(DecisFun,k,x(i,k)); tmp3=length(u); for j=1:tmp3 tmp=feval(ObjFun,k,x(tmp1(i),k),u(j)); if tmp<=f_vub f_opt(i,k)=tmp; d_opt(i,k)=u(j); t_vub=tmp; end end end %??Dò???? for ii=k-1:-1:1 tmp10=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(ObjFun,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); if ~isempty(tmp60) tmp00=tmp00+f_opt(tmp60(1),ii+1); if tmp00<=t_vubm(i,ii) f_opt(i,ii)=tmp00; d_opt(i,ii)=u(j); t_vubm(i,ii)=tmp00; end
动态规划在火力分配中的应用。 1.问题描述 设有m个目标，目标价值（重要性和危害性）各不相同，用数值A K（K=1，2，..m）表示，计划用n枚导弹突袭，导弹击毁目标的概率P K=，其中是常数，取决于导弹的特性与目标的性质；为向目标发射的导弹数，问题：做出方案使预期的突击效果最大。 2.问题建模 上述问题可以表述为 约束条件为 （为非负整数） 3.算法描述 下面通过一个实例说明：设目标数目为4（m=4），导弹为5（n=5），和a K取值情况如下表所示： 表1：A k 取值情况 目标K 1 2 3 4 8 7 6 3 0.2 0.3 0.5 0.9 将火力分配可分为4个阶段，每个阶段指标函数为：
可能取值为0，1，2，3，4，5，将函数值带人如下表： 表2 函数值 u 0 0 0 0 0 1 1.45 1.81 2.36 1.79 2 2.64 3.16 3.79 2.51 3 3.61 4.15 4.66 2.81 4 4.41 4.89 5.19 2.93 5 5.0 6 5.44 5.51 2.97 动态规划问题基本方程为： c =0 逐次向前推一级 K=4 K=3 K=2 K=1 （） 只需要求解的最大值然后反推回去就可以获得最优的分配方案
4.Matlab仿真求解 因为与取值为整数，可以采用动态规划的方法，获得的最大值，对应的
最优方案 function[p_opt,fval]=dynprog(x,DecisFun,SubObjFun,TransFun,ObjFun) %求解动态规划问题最小值函数 k=length(x(1,:)) %判断决策级数 x_isnan=~isnan(x); % 非空状态矩阵 t_vubm=inf*ones(size(x)); % 性能指标中间矩阵 f_opt=nan*ones(size(x)); % 总性能指标矩阵 d_opt=f_opt; %每步决策矩阵 tmp1=find(x_isnan(:,k)); % 最后一步状态向量 tmp2=length(tmp1); % 最后一步状态个数 for i=1:tmp2 u=feval(DecisFun,k,x(tmp1(i),k)); tmp3=length(u);%决策变量 for j=1:tmp3 % 求出当前状态下所有决策的最小性能指标 tmp=feval(SubObjFun,k,x(tmp1(i),k),u(j)); if tmp <= t_vubm(i,k) %t_vub f_opt(i,k)=tmp; d_opt(i,k)=u(j); t_vubm(i,k)=tmp; end; end; end for ii=k-1:-1:1 tmp10=find(x_isnan(:,ii)); tmp20=length(tmp10); for i=1:tmp20 %求出当前状态下所有可能的决策 u=feval(DecisFun,ii,x(tmp10(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; % 找出下一状态在 x 矩阵的位置 tmp60=find(tmp50==0) ; if~isempty(tmp60) if nargin<6 %矩阵不同需要修改nargin的值，很重要 tmp00=tmp00+f_opt(tmp60(1),ii+1); % set the default object value else tmp00=feval(ObjFun,tmp00,f_opt(tmp60(1),ii+1)); end %当前状态的性能指标 if tmp00<=t_vubm(i,ii) f_opt(i,ii)=tmp00; d_opt(i,ii)=u(j);
实验报告 课程名称：动态规划 实验名称：二维分配问题 专业：信息与计算科学指导教师：滕宇 完成日期： 2014年 11月 07日
MATLAB程序： clc;clear; P=[0.4 0.1 0.5; 0.2 0.4 0.2]; A=[3 2 5]; M=[6 10]; sv=@(u,w,pi)A(pi)*(1-((1-P(1,pi))^u)*((1-P(2,pi))^w));% 朝第pi目标发送u个第一种导弹，w 个第二种导弹，的价值; lmd=0.7; for ll=1:99 lmd=ll/100; v=@(u,w,pi)sv(u,w,pi)-lmd*w; vu=zeros(7,3);% vk(uk)的值 wi=vu;% 相应的决策 for l=1:3 lv=@(u,w)v(u,w,l); for m=0:6 mv=@(w)lv(m,w); for n=0:10 ff=mv(n); if vu(m+1,l) end end end end %% 动态规划 x=zeros(1,3); u=x; w=x; x(1)=find(fx(:,1)==max(fx(:,1)))-1; u(1)=ui(x(1)+1,1); x(2)=x(1)-u(1); u(2)=ui(x(2)+1,2); x(3)=x(2)-u(2); u(3)=ui(x(3)+1,3); w(1)=wi(u(1)+1,1); w(2)=wi(u(2)+1,2); w(3)=wi(u(3)+1,3); %% 判断是否符合 if sum(u)==6&&sum(w)==10 disp('lmd符合最大价值为'); max(fx(:,1)) disp('方案为'); u w lmd else disp('lmd不符合'); end end 动态规划方法的matlab实现及其应用 （龙京鹏，张华庆，罗明良，刘水林） (南昌航空大学，数学与信息科学学院，江西，南昌) 摘要：本文运用matlab语言实现了动态规划的逆序算法，根据状态变量的维数，编写了指标函数最小值的逆序算法递归计算程序。两个实例的应用检验了该程序的有效性，同时也表明了该算法程序对众多类典型的动态规划应用问题尤其是确定离散型的应用问题的通用性，提供了求解各种动态规划问题的有效工具。关键词：动态规划基本方程的逆序算法 MATLAB实现 MATLAB Achieve For Dynamic Programming and Its Application (JingpengLong，HuaqingZhang，MingliangLuo，ShuilinLiu) （School of Mathematics and Information Science,Nanchang Hangkong University,Nanchang,China） Abstract:This article achieves the reverse algorithm of dynamic programming by using the matlab language，and prepares the recursive calculation program of reverse algorithm which thetargetfunctionvalueisthesmallest.Theapplicationoftwoexamplesshowthattheprogram is effective，and this algorithm program is general to many typical application of dynamic programming,especially the application of deterministic discrete.This algorithm program provides a effective tool to the solution of a variety of dynamic programming problems. Key words:dynamic programming；reverse algorithm；Matlab achievement 动态规划是一类解决多阶段决策问题的数学方法, 在工程技术、科学管理、工农业生产及军事等领域都有广泛的应用。在理论上,动态规划是求解这类问题全局最优解的一种有效方法,特别是对于实际中某些非线性规划问题可能是最优解的唯一方法。然而,动态规划仅仅决多阶段决策问题的一种方法,或者说是考查问题的一种途径,而不是一种具体的算法。就目前而言,动态规划没有统一的标准模型,其解法也没有标准算法,在实际应用中,需要具体问题具体分析。动态规划模型的求解问题是影响动态规划理论和方法应用的关键所在,而子问题的求解和大量结果的存储、调用更是一个难点所在。然而, 随着计算机技术的快速发展,特别是内存容量和计算速度的增加,使求解较小规模的动态规划问题成为可能,从而使得动态规划的理论和方法在实际中的应用范围迅速增加。 目前,在计算机上实现动态规划的一般求解方法并不多见,尤其是用来解决较复杂的具体问题的成果甚少。本文从实际出发,利用数学工具软件matlab 的强大功能, 对动态规划模型的求解方法做了尝试,编写出了动态规划逆序算法的matlab程序，并结合“生产与存储问题”[1] 和“背包问题”[1]进行了应用与检验,实际证明结果是令人满意的。 1 动态规划的基本模型 实际中,要构造一个标准的动态规划模型,通常需要采用以下几个步骤: ①划分阶段按照问题的时间或空间特征,把问题分为若干个阶段。这些阶段必须是有序的或者是可排序的(即无 后向性) ,否则,应用无效。 ②选择状态将问题发展到各个阶段时所处的各种客观情况用不同的状态表示,即称为状态。状态的选择要满足无后效性和可知性,即状态不仅依赖于状态的转移规律,还依赖于允许决策集合和指标函数结构。 ③确定决策变量与状态转移方程当过程处于某一阶段的某个状态时,可以做出不同的决策,描述决策的变量称为决策变量。在决策过程中,由一个状态到另一个状态的演变过程称为状态转移。状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。 ④写出动态规划的基本方程动态规划的基本方程一般根据实际问题可分为两种形式,逆序形式和顺序形式。这里只考虑逆序形式。动态规划基本方程的逆序形式为 f s k k( ) = opt gv s x{ ( k k k( , )+f s k+1( k+1))} x D s k∈ k k( ) k nn= , ?1, ,1 边界条件 f s n+1( n+1) = 0或f s v s x n n() = n n n( , ) 其中第k 阶段的状态为s k,其决策变量x k表示状s k的决策,状态转移方程为s k+1 =T s x k k k( , ), 态处于k 阶段的允许决策集合记为D s k k( ) , v s x k k k( , ) 为指标函数。 动态规划在火力分配中得应用。 1.问题描述 设有m个目标，目标价值（重要性与危害性)各不相同,用数值A K(K＝1，2,、、m）表示，计划用ｎ枚导弹突袭，导弹击毁目标得概率P K＝，其中就是常数,取决于导弹得特性与目标得性质；为向目标发射得导弹数,问题：做出方案使预期得突击效果最大. 2.问题建模 上述问题可以表述为 约束条件为 (为非负整数） 3.算法描述 下面通过一个实例说明：设目标数目为４(m=4)，导弹为5(ｎ=5)，与a K取值情况如下表所示： 表１:Ａk 取值情况 目标K 1 ２ 3 4 8 7 6 3 0、2 0、3 0、5 0、9 将火力分配可分为4个阶段,每个阶段指标函数为: 可能取值为０，1，2，3,4,5，将函数值带人如下表: 表2函数值 u ０0 0 ０0 １1、4５1、81 2、3６1、7９ 2 2、6４3、１6 ３、7９２、５1 3 3、6１４、15 4、６6 2、８1 4 4、４1 4、89 5、1９２、９３ 5 5、0 6 5、44 ５、51 2、97 动态规划问题基本方程为: ｃ =０ 逐次向前推一级 K=4 K=3 Ｋ＝２ K＝1 () 只需要求解得最大值然后反推回去就可以获得最优得分配方案 4.Mａtlab仿真求解 因为与取值为整数，可以采用动态规划得方法,获得得最大值，对应得最优方案 functｉon［ｐ_opｔ，ｆｖal]=ｄyｎprｏg(x,ＤeｃisFun，ＳｕｂＯbjFｕn，Trａns Ｆuｎ,ObｊFｕｎ）％求解动态规划问题最小值函数 k=lengｔh(x（１，:)) %判断决策级数 x＿iｓnａn=～iｓnan(ｘ)；％非空状态矩阵 ｔ_ｖubｍ=inｆ＊ones（size（x）); %性能指标中间矩阵 f_opt=nan*ones(ｓiｚe（x)）； % 总性能指标矩阵 d＿opt＝f_opt; %每步决策矩阵 ｔmｐ1=find（x＿isnaｎ(：，k）); ％最后一步状态向量 ｔｍp２＝length（ｔmp1)；％最后一步状态个数 fｏr i＝１:ｔmp2 u=fevaｌ(DｅcisFuｎ,k，ｘ（ｔmｐ1(ｉ），k))； tmp3=lenｇtｈ（u)；％决策变量 for j=１:tmp3 ％求出当前状态下所有决策得最小性能指标 ｔmp=ｆeｖal(SuｂObjFun，k，x（tmp1(i），ｋ）,ｕ(j）)； ｉf tmp <＝ｔ_ｖubｍ(i，k) %t_vub ｆ＿opt(i，ｋ)=tｍｐ； d＿opt(i，k）=u(j)； ｔ_vubm(i,ｋ）=tｍp； ｅｎd； end; ｅnd foｒ ii=k—1：—1:1 tmp10=ｆind（x_isnaｎ（：，ii）); tmp2０=lenｇth(tｍｐ10）； fｏｒ i=1:ｔｍｐ20 %求出当前状态下所有可能得决策 u=fevaｌ(DeciｓＦun，ii，x（tｍp10(i），ii)); ｔｍp30＝lenｇth（u) ； ｆｏr j＝1：ｔmp３０％求出当前状态下所有决策得最小性能指标 tmp００=fevａl(SuｂObjFun，ｉi,x（ｔmp10(i），iｉ)，u(j））;% 单步性能指标 tｍｐ40＝feｖａl(ＴｒａnsFun,ii，x（ｔmp10（i），ｉi)，u(j)）; ％下一状态 tmp50＝x(：,ii＋1）-tｍp40；％找出下一状态在x 矩阵得位置 tmp60=ｆiｎｄ（tmｐ５0==0) ； if～iseｍpｔｙ（ｔｍp６０） iｆ nargiｎ<6 %矩阵不同需要修改nargin得值,很重要 tmp00=tｍp0０+f_opt(tmp60（1)，iｉ+1）；％ set ｔｈｅ deｆault ｏｂject 龙源期刊网 https://www.doczj.com/doc/4e15666082.html, 基于Matlab的动态规划算法的实现及应用作者：陈甜甜 来源：《中国校外教育(下旬)》2019年第01期 【摘要】介绍了动态规划的基本理论，包括动态规划的基本概念和基本原理，并针对生产与存储问题进行了分析，然后结合Matlab做了编程处理，使复杂问题简单化，从而使问题能更方便地得到解决。 【关键词】动态规划生产与存储问题Matlab语言一、引言 动态规划是用于解决运筹学中多阶段决策过程最优化问题的一种方法。其广泛应用于工程技术、科学管理、工农业生产及军事等领域。在理论上，动态规划是求解这类问题全局最优解的一种有效方法，特别是对于实际中的某些非线性规划问题可能是最优解的唯一方法。然而，动态规划仅仅是解决多阶段决策问题的一种方法，或者说是考查问题的一种途径，而不是一种具体的算法。就目前而言，动态规划没有统一的标准模型，其解法也没有标准算法。在实际应用中，需要具体问题具体分析。动态规划模型的求解问题是影响动态规划理论和方法应用的关键所在，而子问题的求解和大量结果的存储、调用更是一个难点所在。然而，随着计算机技术的快速发展，特别是内存容量和计算速度的增加，使求解较小规模的动态规划问题成为可能，从而使得动态规划的理论和方法在实际中的应用范围迅速增加。 目前，在计算机上实现动态规划的一般求解方法并不多见，尤其是用来解决较复杂的具体问题数学成果甚少。本文从实际出发，利用Matlab软件的强大功能，对动态规划中的生产与存储问题编制程序，并且进行了应用检验来说明方法的可行性。 二、动态规划的基本理论 实际中，要构造一个标准的动态规划模型，通常需要采用以下几个步骤： （1）划分阶段。将所给问题的过程，按照问题的时间或空间特征分解成若干互相联系的阶段，以便按次序求每阶段的解。 （2）选择状态。将问题发展到各个阶段时所处的各种客观条件用不同的状态表示，即称为状态。状态的选择要满足无后效性和可知性，即状态不仅依赖于状态的转移规律，还依赖于允许决策集合和指标函数结构。 （3）确定决策变量与状态转移方程。当各段的状态取定后，可以做出不同的决策，从而确定下一阶段的状态，这种决定称为决策。描述决策的变量称为决策变量。在决策过程中，由一个状态到另一个状态的演变过程称为状态转移。状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。动态规划方法的matlab实现及其应用
动态规划matlab仿真实例
基于Matlab的动态规划算法的实现及应用
相关主题
文本预览