运筹学教学课件动态规划.pptVIP

第七章 动态规划７.1　动态;引言 动态规划与多阶段决策：多;例７.1 最短路问题 ;枚举法：例中，路线图(共18条;为解决这个最短路径问题，首先给;2）、 状态 (state);3）、决策（Decision ;4）、策略（ Policy） ;5）、目标函数 用于;在例７.1中，目标函数就是距离;6）、 状态转移方程在动态规划;为了求出例７.1的最短路线,一;下面应用动态规划方法求解例７.;第一步,从K=4开始 1;第二步,K=3状态变量S3可取;++)(),()(),(242;即从C3到E的最短距离为5,其;第三步, K=2由于第3段;同理有: ;++ )(32Bf=;第四步, K=1,只有一个状态;从城市A到城市E的最短距离为1;图例７.1各点到终点的最短路径;在例７.1的求解过程中,各段的;７.2.1 最优化原理 动态;如果把最优化原理用数学语言描述;7.2.2 动态规划求解的基;例P184 某公司有资金１０;2. 状态变量ks：表示第K段;投资问题: 设总投资额为A万元;2. 状态变量ks：表示第K段;7.2.3 动态规划求解时的几;例　用动态规划方法求解下列问题;当Ｋ＝3时，有可以看到,当 ;当Ｋ＝２时，有 求其极值点:这;当Ｋ＝1时，有分两种情况: ;例　用动态规划方法求解下列问题;当Ｋ＝１时，有;当Ｋ＝２时，有;当Ｋ＝3时，有记求导，得解得∴;极大值应在[0，s4]=[0，;７.3.1 资源分配问题;Max z＝?=3iiixg1;解： 1.将问题按工厂分为三个;4.目标函数为: fk(s;当K=3时状态变量3s的取值范;当K=2时223xss-=32;当k=1时，s1=5, x1的;例 7.5 一运输商拟用一10;背包问题是动态规划的典型问题。;段。用动态规划方法来求解1. ;当K=3时，S3={0，1，2;x2s25x2+ f3(S3);当K=1时，S1=10, f1;7.3.3 生产与存储问题;解：1.设阶段变量为K,则每月;当K=4时，S4的最小可能值为;当K=3时，S3的最小值={5;s3本阶段费用s4f4(s4);s2本阶段费用s3f3(s3);s2本阶段费用s3f3(s3);s1本阶段费用s2f2(s2);1234