线性规划（第一、二、三章）回顾第四章动态规划DynamicProgramming动态规划是一项最优化技术，而不是一种算法；具体问题具体分析处理。1951年，美国数学家Bellman提出解决多阶段决策问题的“最优性原理”，创建了动态规划（1957年出版）。动态规划是一种将实际问题分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的方法策略。一般来说，只要原问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解，就可以考虑用动态规划解决。4.1动态规划基本概念与方法不同时间阶段的决策问题：（1）工厂生产过程：由于市场需求随着时间而变化，为了取得最佳经济效益，要在生产过程中，逐月或者逐季度地根据库存和需求情况决定生产计划安排。（2）设备更新问题：设备刚买来时故障少，经济效益高，转让处理价值也高；随着使用年限的增加，故障多，经济效益差，处理价值也越低。如果卖去旧的买新的，还需要付出更新费．因此就需要综合权衡决定设备的使用年限，使总的经济效益最好。[例2]空间阶段——最短路问题如图为一线路网络，现要从A点铺设一条管道到E点，图中两点间连线上数字表示两点间距离。现需选一条由A到E的铺管线路，使总距离最短。多阶段决策问题的特点：（1）多阶段决策过程的发展是通过状态的一系列变换来实现的。一般情况下，系统在某个阶段的状态转移除与本阶段的状态和决策有关外，还可能与系统过去经历的状态和决策有关。因此，问题的求解就比较复杂、困难。（2）适合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即具有“无后效性”的多阶段决策过程。无后效性：某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。即“未来与过去无关”，当前的状态是此前历史的一个完整总结。注意无后效性一般是针对问题的分析方式的，不是描述一个问题的。（3）类型：离散确定型、离散随机型、连续确定型、连续随机型。（1）全枚举法或穷举法从A到E的路程可分为4个阶段，共有16条可能的路线，分别算出各条路线的距离，最后进行比较，可知最优路线是A→B2→C1→D1→E，最短距离是19。当节点很多时，计算量庞大，且包含许多重复计算。（2）局部最优路径法从A出发，并不顾及全线是否最短，只是选择当前最短途径，“逢近便走”，这样所取决策必是：A→B3→C3→D1→E，全程长度是25。显然，该方法错误地以为局部最优会得到整体最优，结果常是错误的。（3）动态规划方法基本思想：从过程的最后阶段开始考虑，逆着实际过程发展的顺序，找出所有可能状态的最优后继过程，逐段向前递推计算直至始点。计算过程中删去了所有中间非最优的方案组合，从而使计算量比穷举法大为减少。穷举法计算量：二、基本概念与方程状态——每阶段初可能的情形或位置，用状态变量sk表示，sk的取值集合称为状态集合Sk。动态规划中的状态应具有无后效性。决策——每阶段状态确定后的抉择，即从该状态演变到下阶段某状态的选择，用决策变量xk(sk)表示。Dk(sk)表示第k阶段从状态sk出发的允许决策集合。策略——由各阶段决策组成的序列，记P1n(s1)={x1(s1),…,xn(sn)}，称Pkn(sk)={xk(sk),…,xn(sn)}为阶段k至n的后部子策略。允许策略集合、最优策略状态转移——由sk转变为sk+1的规律，记sk+1=Tk(sk,xk)。状态转移方程、状态转移函数阶段指标——每阶段选定决策xk后所产生的效益，记vk=vk(sk,xk)。指标函数——各阶段的总效益，记相应于Pkn的指标函数为vkn=vkn(sk,Pkn)。其中最优的称最优指标函数，记fk=fk（sk）=opt(vkn)。问题：动态规划的最优解和最优值各是什么？小结：多阶段决策问题的数学模型适于应用动态规划方法求解的一类多阶段决策问题，亦即具有无后效性的多阶段决策问题的数学模型总结如下:2、基本方程（5）（2）基本方程根据最优性原理，可建立从后向前逆推求解的递推公式——基本方程如下：动态规划求解的一般步骤：（1）确定过程的分段，构造状态变量；（2）设置决策变量，写出状态转移；（3）列出阶段指标和指标函数；（4）写出基本方程，由此逐段递推求解。三、求解方法解：kk2、连续型——用公式递推求解解：k=5k=3因此，最优计划为：4.2动态规划应用举例一、资源分配问题2、数学规划模型3、用动态规划方法求解[例5]某公司拟将某种高效设备5台分配给所属甲、乙、丙3厂。各厂获此设备后可产生的效益(万元)如下表。问应如何分配，可使所产生的总效益最大？解：资源分配问题的应用很广泛，例如：二、生产与存储问题解：k=4k=3k=2k=1因此，最优生产计划为：三、设备更新问题[例7]某台新设备