动态规划与最优控制模型.doc

第四章 最优控制模型（管理、决策方面应用，因此可说管理决策模型） 1最优控制的问题提法：1.1最优控制问题举例1.2最优控制数学模型一、例，详见最优控制课听课笔记第一节；二、问题的数学描述最优控制模型。寻找（开，闭）可以固定或自由，使得： 其中：，且（一个连续可微），：向量值函数，且对连续，对连续可微。最优控制问题的求解方法：1 古典变分法：U开集；2 极大值原理：U闭集；现代变分法，把古典变分法看作特例3 动态规划：便于数值计算，并有通用算法；发展了变分法，结果要充分条件。2最优控制模型的动态规划解法2.1动态规划方法概述 2.2生产库存销售管理系统的解法2.1动态规划方法概述某一类管理问题的数学模型（状态方程）是一个差分方程： 使 达到最小。此为一个阶决策问题：动态规划法是求这一决策问题的有效办法，具有明显优点：（）将一个阶决策问题转化为多次一步决策问题，即数学上的嵌入原理将求一条极值曲线问题，嵌入到求一族极值曲线的更广泛的类似问题中；（）大大简化了计算量；（）具有局部优，就是整体优的最优性原理：可广泛应用于运输系统、生产库存管理系统、生产计划制定及最优投资分配问题、最优价格制定问题。下面以最短路问题举例说明这种方法：一、最短路问题（最小时间问题）1问题：若有一辆汽车以城出发经过若干城市到达城，如图：，是一些可以通过的城镇。 P1 6 P2 1 P3 4 4 1 2 4S F 5 6 3 Q1 7 Q2 2 Q3图中两点间的数字：可以表示两城镇之间的距离（单位10公里），也可以表示行驶两城镇所用时间（应综合考虑：距离远近，路面好坏，是否拥挤等情况）。于是：汽车从到可经多种途径选择到达。问题是：从多种途径选择方案中，决定一种使到所走路线最短。或者若图中数字表示时间，则决定一种路径使从到所用时间最短。2方法：决策树法（穷举法）：决策树法是最容易想到的一种方法，但运算量很大即把所有可能选择的路途所用的时间都求出来，然后取最小值，即有最优策略（最优决策）。即： 因此有：1 P3 4 F 15 P2 6 1 Q3 3 F 14 P1 62 P3 4 F 16 4 Q22 Q3 3 F 15S 1 P3 4 F 14 5 P2 4 1 Q3 3 F 13 Q 1 7 2 P3 4 F 18 Q2 2 Q3 3 F 17因此，最终得出：困难：这样共有8条线路可选择，每条线路要作3次运算。第1次：；第2次：；第3次：因此，共需24次运算：次，若阶段更多，则计算量更大。2“走一步瞧一步”（瞎子爬山？）法：第一步：从到或：显然 ，因此取决策；第二步：从到或：显然 ，因此取均可，但从到或距离为1，而到距离为2，因此，第2步决策为，因此取；第三步：到或到，均有，但到的距离为3，因此第3步取路线。因此使用这种方法得到的决策为：显然不是“最优决策”，同时还有：问题出现在“局部优不能代替整体优”的问题。3动态规划：即可把每一步决策都看成一个状态的转移，而每一种状态的转移又影响到下一阶段的状态，因此又是动态的，故称为动态规划法。将上述问题分为四个阶段的多阶决策问题，故可将问题分为四阶段问题来考虑：第一阶段问题：； 第二阶段问题：；第三阶段问题：； 第四阶段问题：解题方法从最后一个阶段开始：1分别计算到的最小代价，此处花费代价为时间，记为，用分别表示或到的代价，则显然有：2由后往前，考虑倒数第二阶段（即第三阶段），再把第三阶段和第四阶段联合作为一个子问题来考虑，若从出发到，则有两种可能：线路最短，且，故将线路记成P2Q3.类似以出发到，则有两种可能：线路最短，则，故将线路记成.3再由2、3、4这三个阶段构成的子问题：若从出发到有两种可能：有线路最短，且，故将记成：若从出发到有两种可能：有线路最短，则，故将记成：4把由1、2、3、4阶段作为子问题来考虑：从出发到有两种可能：故： 最短，且5 因此有最优策略： 即： 除“二决一”比较之外，且运算只用了10次，而穷举法则算了24次，上次这种动态规划的办法：是将把一个四阶段决策问题化为四个互相嵌入子问题，逐一进行简化的计算方法，即数学上嵌入定理。3最优性原理 “最优策略的一部分也是最优策略”例如：上例中知：是最优决策，则也一定是从Q1出发到F的最优决策：证明反证法：设SQ1P2Q3F是最优决策，则Q1P2Q3F不是最优决策，则必存在另一个最优决策，不妨设为Q1Q2Q3F为最优决策。因而，SQ1Q2Q3F是整体最优决策，因而与SQ1P2Q3F是最优决策相矛盾，因而原结论正确。一般有最优性原理：如果是阶决策问题的最优策略序列，那么：也是一个最优策略序列，其初始状态为：证明：同最短路4 多阶决策问题的一般想法：设某系统的状态方程为：目标函数为：，表示控制步时的目标函数值。最优控制问题，即：求最优决策序列，使取最小(大)值。为简化假定为定常状态，即不明显还有时间变量因而有： 对目标函数(3)逐次应用(1)式有：因此，可以由上式看出：只依赖于 因而可写成：又若用某种方法求出了最优决策，则的最小值只依赖于初始值，记为，它可用下式来定义：初始值是可变化的，因此：表示初始状态为时，控制步的目标函数最小值。5动态规划的基本方程：动态规划的基本方程，给出阶决策问题的目标函数最优值与它的子问题目标函数最优值之间的递推关系式，它是用动态规划解一切多阶决策问题的基础。设已求出，则求序列的问题，构成一个以为初始条件的阶决策问题，若记这一子问题的目标函数最小值为：；又若记为阶决策问题最小值，则我们可以导出与之间的关系：则第一项： 第二项： 并不明显依赖， 可知：实际上第二项仍依赖于，因此，第二项可写成：因此有：动态规划基本方程：此给出了与之间的递推关系。它是动态规划的基本方程。类似有动态规划更一般的基本方程：(*) 因此依据基本递推方程的递推关系：可以把一个多阶决策问题化为若干个子问题，而在决策的每一个阶段中只须对一个变量进行最优化决策即可。例如：是对一个单变量的优化问题，当求出后，由基本递推方程(*)式可得： 这又是对的最优化决策问题，因而把原来阶决策问题化成一系列对单变量的最优化决策问题，从而使问题简化。2.2 生产库存库存管理决策问题的解设某工厂生产某种产品，四个季度定货量为：一季二季三季四季600件700件500件1200件生产费用与产品平方成正比，即比例系数为0.005，库存费每件每季为：1.0元。第季度库存量为：件；第季度生产量为：件；一季二季三季四季600件700件500件1200件第季度销售量为：因此有：下季度库存是 ：且要求年初、年终都没有存货即销售已空。x（0）x（5）0最优管理问题：求每季度的最优生产量，使之能正好完成订货计划且使生产费与库存费总和最小。即：求使（1）解：使用动态规划的办法：1 先由最后一个季度考虑起：由（2）得得代入（1）2 再考虑34两个季度，由基本递推方程知：其中代入上式即有：而应使上式取最小值，因此有：即：即有：为使，必须有，把代入3再考虑2-3-4