管理运筹学-第六章-动态规划.pptVIP

第六章动态规划广东工业大学管理学院第六章动态规划6.1动态规划的基本概念6.2最优化原理6.3经济管理问题举例多阶段决策过程动态规划的基本概念动态规划的基本概念标号法求解最短路问题最优化原理一个过程的最优策略具有这样的性质,即无论其初始状态与初始决策如何,对于先前决策形成的状态而言,其以后的所有决策应构成最优策略.基本方程动态规划求解问题的基本思路首先划分阶段n定义状态变量sk、写出各阶段的可选状态集合Sk；定义决策变量uk、写出各阶段各状态下的可选决策集合Dk(sk)；写出状态转移方程sk+1=Tk(sk,uk)。定义阶段效益函数和效益函数，建立基本方程按照基本方程递推地寻求最优策略。动态规划求解连续问题例6.4用动态规划方法求解动态规划求解连续问题6.3应用举例例6.5（不确定价格采购问题）某厂必须在5周内采购一批原料，其浮动价格和概率已测得，试求在哪一周以什么价格购入，使采购价格的数学期望值最小，并求出期望值。周浮动价格及概率如下表：不确定价格采购问题不确定价格采购问题最优化原理逆序法求解不确定价格采购问题不确定价格采购问题资源分配问题例6.6某公司拟聘请4-6名商业专家，分配给其甲、乙、丙三个商店任用。各商店分的不同数量的专家后，预测可创造的利润如表所示，问该公司聘请几名专家并如何分配，可使得所创造的总利润最大？资源分配问题解：阶段数n=3，3个阶段分别决定甲、乙、丙三个商店的专家数；状态变量sk：第k阶段初还剩余的专家数；决策变量xk：分配给第k个商店的专家数；可行决策集合：Xk={xk|0≤xk≤sk}状态转移方程：sk+1=sk-xk阶段效益函数vk(xk)：给第k个商店xk个专家能够获得的盈利；最优过程效益函数fk(sk):第k阶段初还剩余sk个专家能够获得的总利润。动态规划基本方程为：资源分配问题资源分配问题资源分配问题资源分配问题资源分配问题资源问题的Excel求解复合系统的可靠性问题为保证某设备正常运转，需对串联工作的三种零部件A1、A2、A3分别确定备件数量。若增加备用零件的数量，可提高设备正常运转的可靠性，但费用增加，而总投资额为8万。已知备用零件数与他的可靠性和费用关系如表所示，求A1、A2、A3的备用零件数各为多少时，设备运转的可靠性最高。复合系统的可靠性问题解：阶段数n=3状态变量sk：第k阶段初的剩余资金额决策变量xk：购买第k中备件的数量效益函数：系统可靠性动态规划在程序设计中的应用00000004630.70.90.533520.20.50.422310.10.20.31A3A2A1A3A2A1备用零件费用可靠性备件数8765432000000004630.70.90.533520.20.50.422310.10.20.31A3A2A1A3A2A1备用零件费用可靠性备件数0.30.40.50.20.50.20.20.70.20.110.70.20.10.140.040.020.042最优策略到底是什么呢？**动态规划的分类：离散确定型离散随机型连续确定型连续随机型决策1状态1决策2状态2决策n状态3……状态n例6.11、阶段，阶段数阶段变量：k;阶段数记作n。无后效性：如果某阶段的状态给定，这阶段以后过程的发展不受这阶段以前各阶段状态的影响3、决策某阶段状态确定后，为确定下一阶段的状态，所作出的决定（选择）。决策变量：uk(sk)表示第k阶段状态为sk时的决策允许决策集合：Dk(sk)2、状态每个阶段开始时所处的自然状态或客观条件状态变量：sk状态集合：Sk4、策略：由决策组成的序列称为策略。p1,n={u1(s1),u2(s2),…,un(sn)}允许策略集合：P1,n最优策略：p*1,n子策略：5、状态转移方程sk+1=Tk(sk,u