动态规划与最优控制模

《动态规划与最优控制模》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章最优控制模型（管理、决策方面应用，因此可说管理决策模型）§1最优控制的问题提法：§1.1最优控制问题举例一、例，详见最优控制课听课笔记第一节；§1.2最优控制数学模型最优控制模型问题的数学描述――最优控制模型。寻找（开，闭）可以固定或自由，使得：　　　　　　　　　　　　其中：　　，且（一阶连续可微），，：向量值函数，且对连续，对连续可微。上述最优控制的离散模型：求，使得目标泛函:达到最小。而且满足：状态方程:11最优控制问题的求解方法：1．古典变分法：U开集；2．极大值原理：U闭集；现代变分法，把古典变分法看作特例3

2、．动态规划：便于数值计算，并有通用算法；　　　　　　　发展了变分法，结果是充分条件。§2最优控制模型的动态规划解法§2.1动态规划方法概述§2.2生产——库存——销售管理系统的动态规划解法§2.1动态规划方法概述某一类管理问题的数学模型（状态方程）是一个差分方程：状态方程:目标泛函:达到最小。即:此为一个阶决策问题：动态规划法是求这一决策问题的有效办法，具有明显优点：（ⅰ）将一个阶决策问题转化为多次一步决策问题，即数学上的嵌入原理——将求一条极值曲线问题，嵌入到求一族极值曲线的更广泛的类似问题中；（ⅱ）大大简化了计算量；（

3、ⅲ）具有局部优，就是整体优的最优性原理：可广泛应用于运输系统、生产库存管理系统、生产计划制定及最优投资分配问题、最优价格制定问题。下面以最短路问题举例说明这种方法：一、最短路问题（最小时间问题）1．问题：若有一辆汽车以城出发经过若干城市到达城，如图：，是一些可以通过的城镇。·P16·P21·P344124S··F563·Q17·Q22·Q3图中两点间的数字：可以表示两城镇之间的距离（单位10公里），也可以表示行驶两城镇所用时间（应综合考虑：距离远近，路面好坏，是否拥挤等情况）。11于是：汽车从到可经多种途径选择到达。问题是

4、：从多种途径选择方案中，决定一种使到所走路线最短。或者若图中数字表示时间，则决定一种路径使从到所用时间最短。2．方法：Ⅰ.决策树法（穷举法）：决策树法是最容易想到的一种方法，但运算量很大——即把所有可能选择的路途所用的时间都求出来，然后取最小值，即有最优策略（最优决策）。即：因此有：1P34F15P261Q33F14P162P34F164Q22Q33F15S1P34F145P241Q33F13Q172P34F18Q22Q33F17因此，最终得出：困难：这样共有8条线路可选择，每条线路要作3次运算。第1次：；第2次：；第3次

5、：因此，共需24次运算：次，若阶段更多，则计算量更大。II．“走一步瞧一步”（瞎子爬山？近视眼？）法：第一步：从到或：显然，因此取决策；第二步：从到或：显然，因此取均可，但从到或距离为1，而到距离为2，因此，第2步决策为，因此取；第三步：到或到，均有，但到的距离为3，因此第3步取路线。11因此使用这种方法得到的决策为：显然不是“最优决策”，同时还有：问题出现在“局部优不能代替整体优”的问题。III．动态规划：　　　即可把每一步决策都看成一个状态的转移，而每一种状态的转移又影响到下一阶段的状态，因此又是动态的，故称为动态规划

6、法。将上述问题分为四个阶段的多阶决策问题，故可将问题分为四阶段问题来考虑：第一阶段问题：；第二阶段问题：；第三阶段问题：；第四阶段问题：·P16·P21·P344124S··F563·Q17·Q22Q3第1阶段第2阶段第3阶段第4阶段解题方法从最后一个阶段开始：1°　分别计算到的最小代价，此处花费代价为时间，记为，用分别表示或到的代价，则显然有：2°　由后往前，考虑倒数第二阶段（即第三阶段），再把第三阶段和第四阶段联合作为一个子问题来考虑，若从出发到，则有两种可能：　　线路最短，且，故将线路记成P2④Q3.类似以出发到，则

7、有两种可能：11　线路最短，则，故将线路记成⑤.3°　再由2、3、4这三个阶段构成的子问题：若从出发到有两种可能：　有线路最短，且，故将记成：⑩若从出发到有两种可能：　有线路最短，则，故将记成：⑧4°　把由1、2、3、4阶段作为子问题来考虑：从出发到有两种可能：故：最短，且5°因此有最优策略：即：61S4614F542372第1阶段第2阶段第3阶段第4阶段除“二决一”比较之外，且运算只用了10次，而穷举法则算了24次，11上次这种动态规划的办法：是将把一个四阶段决策问题化为四个互相嵌入子问题，逐一进行简化的计算方法，即数学

8、上嵌入定理。IV.最优性原理“最优策略的一部分也是最优策略”例如：上例中知：是最优决策，则也一定是从Q1出发到F的最优决策：证明［反证法］：设SQ1P2Q3F是最优决策，则Q1P2Q3F不是最优决策，则必存在另一个最优决策，不妨设为Q1Q2Q3F为最优决策。因而，SQ1Q2Q3F是整体最优决策，因而与S