运筹帷幄之中教学要求：第一节动态规划原理和模型动态规则是将一个较复杂的多阶段决策问题分解为若干相互关联的较容易求解的子(单）决策问题。而每一个子决策问题都有多种选择当一个子决策问题确定以后，将影响另一个子决策问题从而影响到整个问题的决策例2、机器负荷分配问题：年初完好机器数为u台，其中有u1台用于高负荷生产，产品的年产量为s1=g(u1)，年终完好机器数为au1(a称完好率,a<0<1)，另外有u2台机器用于低负荷生产，产品的年产量为s2=g(u2)，年终完好机器数为bu2(0<b<1)，试制定一个五年计划，使产品产量最高。例某运输公司有500辆运输卡车，在超负荷运输(即每天满载行驶500km以上)情况下，年利润为25万元/辆，这时卡车的年损坏率为0.3，在低负荷运输(即每天行驶300KM以下)情况下，年利润为16万元/辆、年损坏率为0.1，现在要求制订一个5年运输计划，问每年年初应如何分配完好车辆在两种不同负荷下运输的卡车数量，使在5年内总利润最大？例3、排序问题：有5个零件需要在A、B两台机床上加工，每个零件都必须经过先A后B的加工顺序，加工时间如下表，问应如何安排加工顺序，使总的加工时间最少？以上问题的一个共同特点是问题的过程可以分解成相互联系的若干阶段，在每个阶段均需要作出决策，各个阶段的决策取决于目前的状态，它又将影响到以后的发展，当各个阶段的决策确定之后，就构成一个决策序列，我们的目的就是要在决策系列中，寻找最优的决策序列二、动态规则的分类离散确定性离散随机性连续确定性连续随机性三、动态规则的基本概念1、阶段将所给问题，按时间或空间特性分解成若干互相联系的部分，用字母K表示阶段变量决胜千里之外但同时要求必须及时满足需求。(2)k=3第三阶段将一种或多种有限的资源，分配给若干个使用者，而使目标达到最优第一节动态规划原理和模型d2(B2,C2)+f3(C2)=4+15=19f2(x2)=max{v2(x2,u2)+f3(x3)}0≤u2≤x2第一节动态规划原理和模型f1(B1)=min[d(B1,A)+f0(A)]=4顺序法：是从过程的第一阶段开始，用顺序递推的方法求解，逐步求出各阶段各点到起点最短路线，最后求得A到E点的最短路线。f2(x2)=max{v2(x2,u2)+f3(x3)}0≤u2≤x2第一节动态规划原理和模型即C3到A的最佳路径为C3-B1-ASk+1=uk(sk)设部件i上装有zi个备用元件时，它正常工作的概率是pi(zi)。第一节动态规划原理和模型3、决策从一个阶段给定状态出发，到下阶段某一状态的选择决策变量：描述决策的变量，常用uk(xk)表示第k阶段状态xk的决策变量允许的决策集合：第K阶段某给定状态xk的决策变量uk(xk)的允许取值范围常用Dk(xk)表示允许策略集合：可供选择策略的范围最优策略：允许策略集合中最优的一个策略在例1中最优策略为：A-B1-C3-D2-E5、状态转换方程它是确定过程由某一阶段的一个状态到下一阶段另一状态的演变过程，用sk+1=Tk(sk,uk)表示，该方程描述了由第k阶段到第k+1阶段的状态转换规律，又称状态转换函数例1中，前一阶段的终点就是后一阶段的起点，所以状态转换方程为：Sk+1=uk(sk)6、指标函数衡量多阶段决策过程优劣的一种数量指标，一个n阶段决策过程，从1到n称为问题的原过程,对于任意一个给定的k，从第k阶段到第n阶段的过程称为原过程的一个后部子过程，用V1,n(s1,p1,n)表示初始状态为s1，采用策略p1,n时，原过程的指标函数值如V1,4(A,P1,4)而Vk,n(sk,pk,n)表示在第k阶段，状态为sk采用策略pk,n时，后部子过程的指标函数值，V2,4(B1,P2,4)从第k阶段状态sk采用最优策略pk*,n到过程终止时的最佳效益值，称为最优指标函数记fk(sk)=Vk,n(sk,pk*,n)=optimumpk,nVk,n(sk,pk,n)在例1中，每阶段所走的距离为指标函数，如V2,4(B1)表示在第2阶段，状态为B1时，从B1到E的距离而f2(B1)则表示从B1到E最短距离，本问题所要求的目标是距离之和的最小值，即f1(A)五、动态规划贝尔曼的最优化原理最优决策具有这样的性质：无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略贝尔曼的最优化原理如果最短路线在第k阶段通过状态xk，则这条最短路线在由xk出发到达终点的这段线段，对于从xk出发到终点的所有其它线路来说仍然是最优的4一动态规划求解的思想逆序法：是从过程的最后一阶段开始，用逆序递推方法求解，逐步求出各阶段各点到终点E的最短