动态规划的基本原理.ppt

（一）例见PPT 最优化原理： 一个过程的最优策略具有这样的性质，即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策必构成最优策略 例3（生产与存储问题）某工厂生产并销售某种产品。已知今四个月市场需求预测如下表，又每月生产j个单位产品的费用为 每月库存i个单位产品的费用E(i)=0.5i(千元），该厂最大库存容量为3个单位，每月最大生产能力为6个单位，计划开始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，使总费用最小。 最优化原理： 一个过程的最优策略具有这样的性质，即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策必构成最优策略 * 对最短路问题： 来源于动态规划的最优化原理 最短路问题的基本方程： k=4,3,2,1 由后向前迭代 递推公式 对最短路问题： A ○ ○ B1 ○ F ○ B2 ○ B3 ○ C1 ○ C2 ○ C3 ○ D2 ○ D1 ○ E2 ○ E1 则不论前面A如何到达B，B又如何到达C1 上堂课的主要内容： 一、动态规划的基本概念 1、阶段： 指对整个过程的自然划分 ，用k表示 2、状态变量sk Sk ={sk} 第k阶段的状态集合 ：第k阶段开始时所处的自然状况 3、决策变量： 当一个阶段的状态确定后，可以作出各种选 择从而演变到下一阶段的某个状态，这种选 择手段称为决策 4、状态转移方程 sk 第k阶段的状态变量 状态转移方程： 5、策略： 由各阶段的决策组成的序列称为策略 ——允许策略集合 6、指标函数 用于衡量所选定的策略优劣的数量指标称为指标函数 最优策略 二、最优化原理： 一个过程的最优策略具有这样的性质，即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策必构成最优策略 对最短路问题： A ○ ○ B1 ○ F ○ B2 ○ B3 ○ C1 ○ C2 ○ C3 ○ D2 ○ D1 ○ E2 ○ E1 则不论前面A如何到达B，B又如何到达C1 对最短路问题： ○ C1 ○ A ○ B1 ○ E ○ B2 ○ B3 ○ C2 ○ C3 ○ D2 ○ D1 8 4 5 8 9 6 1 6 10 9 6 7 7 3 8 4 2 3 最短路问题的基本方程： k=4,3,2,1 动态规划方法即基于这种思想， 这种从终点逐段向始点方向寻找最短路线的方法， 称为逆序算法 阶段k=1，2，3，4 状态变量sk=第k个月月初的库存量 4 2 3 2 g(i)需求 4 3 2 1 i月 状态转移方程： 当k=4时， u4(s4)对应的总费用=生产费+库存费 4 2 3 2 g(i)需求 4 3 2 1 i月 库存费E(i)=0.5i， 最大库存容量为3个单位， 最大生产能力为6个单位， 计划开始和计划期末库存量为零 0 1 2 3 4 7 4 3 6.5 3 2 6 2 1 5.5 1 当k=3时， 4 2 3 2 g(i)需求 4 3 2 1 i月 库存费E(i)=0.5i， 最大库存容量为3个单位， 最大生产能力为6个单位， 计划开始和计划期末库存量为零 0 1 2 3 0 1 2 3 0 u3(3)对应的总费用=生产费+库存费 4 2 3 2 g(i)需求 4 3 2 1 i月 库存费E(i)=0.5i， 最大库存容量为3个单位， 最大生产能力为6个单位， 计划开始和计划期末库存量为零 0 2 3 4 5 12 12 .5 13 13.5 12 2 1 1 2 3 4 11.5 12 12.5 13 11.5 1 2 0 1 2 3 8 11.5 12 12.5 8 0 3 0 1 2 8 8 0 11.5 12 0 1 2 3 4 7 4 3 6.5 3 2 6 2 1 5.5 1 当k=2时， 4 2 3 2 g(i)需求 4 3 2 1 i月 u2(s2)对应的总费用=生产费+库存费 0 2 3 4 5 12 12 .5 13 13.5 12 2 1 1 2 3 4 11.5 12 12.5 13 11.5 1 2 0 1 2 3 8 11.5 12 12.5 8 0 3 0 1 2 8 11.5 12 8 0 k=3 当k=2时， 0 1 2 3 3 4 5 6 18 18.5 16 17 16 5 2 3 4 5 17.5 18 15.5 16.5 1 2 3 4 17 0 1