第六章动态规到(1) 动态规划顺序解法 第一步:划分阶段 第二步:选择状态变量 第三步:确定决策变量 第四步:写状态转移方程 第五步:指标函数 运学 熊中描教
运筹学 熊中楷教授 动态规划顺序解法： 第一步：划分阶段 第二步：选择状态变量 第三步：确定决策变量 第四步：写状态转移方程 第五步： 指标函数 第六章 动态规划（1）
第六章动态规划(1 动态规划应用之二:资源分配问题 类似P208例4顺推法求解非线性规划: maxZ=4x, +9x +2x 2 X1+x,+x3=10 x>=0I12.3 X+X+X 分析:理解为 第一阶段投资x,第二阶段投资x 第三阶段投资x3 求最大利润maxZ=4x+9x2+2x2 三阶段投资总额共有10亿元 非线性规划问题求解 第一阶段投资总额S1(状态变量) 第一二阶段投资总额S2(状态变量 第一二三阶段投资总额S2(状态变量) 运学 熊中描教
运筹学 熊中楷教授 第六章 动态规划（1） 类似P208例4 顺推法求解非线性规划： maxZ=4x1+9x2+2x3 2 x1+x2+x3 =10 xi>=0 I=1,2,3 分析：理解为 第一阶段投资x1， 第二阶段投资x2 第三阶段投资x3 求最大利润maxZ=4x1+9x2+2x3 2 三阶段投资总额共有10亿元 非线性规划问题求解 第一阶段投资总额S1（状态变量） 第一二阶段投资总额S2（状态变量） 第一二三阶段投资总额S3（状态变量） x1 x2 x3 S3 S2 S1 S1 = X1 S2 = X1 +X2 S3 = X1+X2+X3 动态规划应用之二：资源分配问题
第六章动态规到(1) 解:设状态变量S=Xn,S2=S1+X2,S3S2+X3 F1(S1)=4X1=4sS1(第一阶段投资x产生的效益4X1) 第一二阶段投资总量为S2产生的效益 第一阶段投资x产生的效益+第二阶段投资X2产生的效益 F2(S2)=9X2+F1S)=4S2+5 当X2=S2时maxF2(S2)=9S 第 阶段投资总量为S产生的效益= 第一二阶段投资S2产生的效益+第三阶段投资X2产生的效3 F3S3)=2X32+F2(S2)=2x32+9(S3X3)=2X329X+9S3=h3(S3,X3) dh3S3,X)/dX3=4X39=0 X2=9/4 10 在X3=9/4,FS)有最小值,F3(S3)最大值X3=10 maxF3(S3)=22102=200 即X3=10,则X1x2为0 max z200 运学 熊中描教
运筹学 熊中楷教授 第六章 动态规划（1） 解:设状态变量S1=X1 ,S2=S1+X2, S3=S2+X3. F1 (S1 )=4X1 =4S1 (第一阶段投资x1产生的效益4X1） 第一二阶段投资总量为S2产生的效益＝ 第一阶段投资x1产生的效益＋第二阶段投资X2产生的效益 F2 (S2 )=9X2+F1 (S1 )=4S2+5X2 X2 <＝S2 当X2=S2时 maxF2 (S2 )=9S2 第一二三阶段投资总量为S3产生的效益＝ 第一二阶段投资S2产生的效益＋第三阶段投资X2产生的效3 S2=S3 -X3 F3 (S3 )= 2X3 2 +F2 (S2 )= 2X3 2 + 9(S3 -X3 ) = 2X3 2 -9X3+9S3 =h3 (S3 ,X3 ) d h3 (S3 ,X3 ) /dX3 =4X3 -9=0 =>X3 =9/4 0<=X3 <=10 在X3 =9/4, F3 (S3 )有最小值, F3 (S3 ) 最大值 X3 ＝10 max F3 (S3 )=2*102=200 即X3 =10,则X1,X2为0 max Z=200
第六章动态规到(1) H3(S3,X3) 9/4 10 X3 在X3=94,F3S)有最小值,F3S)最大值X3=10 运学 熊中描教
运筹学 熊中楷教授 第六章 动态规划（1） X3 H3(S3,X3) 9/4 10 在X3=9/4, F3 (S3 )有最小值, F3 (S3 ) 最大值 X3 ＝10
第六章动态规到(1) 冰海沉船: 背包逃命 登月: 背包上天 运学 熊中描教
运筹学 熊中楷教授 冰海沉船： 背包逃命 登月 ： 背包上天 第六章 动态规划（1）