最优化原理可以表述为:“一个过程的最优策略具有这样的性质 即无论初始状态和初始决策如何对于先前决策所形成的状态而言其以 后的所有决策必构成最优策略,” 将这一基本原理应用于例5.1的最短路线问题时可表述为:一方面, 条路线如果是最短路线,则对于该线上的任何一点来说,最短路线以此 点为起点的剩余部分,必然是从此点到终点的最短路线。另一方面,无论 是从哪一段的哪一种状态出发,到终点E的最短路线只与此状态有关,而 与以前的状态路线无关,即并不受从A点是如何到达这点的决策的影响 图52中的C2点可以清楚地证明这两种情况。 最优化原理用反证法极易证明。假定s是由始点到终点的最短路线 上的一点如果存在另一条最短路S与终点相连则这条最短路线与s4以前 的部分必构成全程的最短路线,这就与原策略为最短路线的假定相矛盾。所 以,对于一个过程的最优策略而言,不管其初始状态和决策如何,其后的任一 决策都构成最优策略。这也就是动态规划所以可以采用逆序递推法寻优的」 依据。 如果把最优化原理用数学语言描述,就得到了动态规划的基本方程,这就是 f(s4)=op[4(s4,u4)+f1(s)](k=n-1,,1) fn+1(Sn+1)=0 其中,opt可依题意取max或min16
2021/2/24 16 最优化原理用反证法极易证明。假定sk 是由始点到终点的最短路线 上的一点,如果存在另一条最短路 k s 与终点相连,则这条最短路线与 k s 以前 的部分必构成全程的最短路线,这就与原策略为最短路线的假定相矛盾。所 以,对于一个过程的最优策略而言,不管其初始状态和决策如何,其后的任一 决策都构成最优策略。这也就是动态规划所以可以采用逆序递推法寻优的 依据。 如果把最优化原理用数学语言描述,就得到了动态规划的基本方程，这就是: k f （ k s ）＝opt[ ( , ) ( )] +1 +1 + k k k k k d s u f s (k=n,n-1,…,1) n+1 f （ n+1 s ）＝0 其中,opt 可依题意取 max 或 min 最优化原理可以表述为：“一个过程的最优策略具有这样的性质, 即无论初始状态和初始决策如何,对于先前决策所形成的状态而言,其以 后的所有决策必构成最优策略， ” 将这一基本原理应用于例5.1的最短路线问题时可表述为：一方面, 一条路线如果是最短路线,则对于该线上的任何一点来说,最短路线以此 点为起点的剩余部分,必然是从此点到终点的最短路线。另一方面,无论 是从哪一段的哪一种状态出发,到终点E的最短路线只与此状态有关,而 与以前的状态路线无关,即并不受从A点是如何到达这点的决策的影响。 图5.2中的C2点可以清楚地证明这两种情况
5.2,2动态规划模型的建立 建立动态规划的模型,就是分析问题并建立问题的动态规划基本方程。 成功地应用动态规划方法的关键,在于识别问题的多阶段特征,将问题 分解成可用递推关系式联系起来的若干子问题,或者说是要正确地建立具 体问题的基本方程,无疑这需要经验和技巧。而正确地建立关于递推关系 基本方程的关键,又在于正确地选择状态变量,保证各阶段的状态变量具 有递推的状态转移关系SkH1=Tk(Sk,lk)。这是建立动态规划模型的两个 基本要点。 下面举例来说明动态规划模型的建立。 例5.2生产与存储问题 设某工厂生产并销售某种产品,已知每千件的变动成本为1万元,每季 度生产的固定成本为3万元经预测某一年四个季度中该产品的市场需求 量分别为2,3,24千件,设该厂的最大生产能力是6千件,最大库容是3千 件,每千件产品一个季度的存储费用为0.5万元,如果要求年初和年末该产品 均无库存,问如何安排各季度的产量,才能使全年的总费用最小 2021/2/24
2021/2/24 17 5.2.2 动态规划模型的建立 建立动态规划的模型,就是分析问题并建立问题的动态规划基本方程。 成功地应用动态规划方法的关键 ,在于识别问题的多阶段特征 ,将问题 分解成可用递推关系式联系起来的若干子问题 ,或者说是要正确地建立具 体问题的基本方程,无疑这需要经验和技巧。 而正确地建立关于递推关系 基本方程的关键，又在于正确地选择状态变量 ,保证各阶段的状态变 量具 有递推的状态转移关系 sk +1 ＝ ( , ) Tk sk uk 。这是建立动态规划模型的两个 基本要点。 下面举例来说明动态规划模型的建立。 例5.2 生产与存储问题 设某工厂生产并销售某种产品 ,已知每千件的变动成本为 1 万元,每季 度生产的固定成本为 3 万元,经预测某一年四个季度中该产品的市场需求 量分别为 2,3,2,4 千件,设该厂的最大生产能力是 6 千件,最大库容是 3 千 件,每千件产品一个季度的存储费用为 0.5 万元,如果要求年初和年末该产品 均无库存,问如何安排各季度的产量 ,才能使全年的总费用最小