f第七章动态规划解析.ppt

1.阶段 2.状态 3.决策 4.策略 5.状态转移方程 6.指标函数和最优值函数 国外机器制造厂 ―出口港 进口港 国内城市 国内某工厂 第六章 动态规划（2） 出租汽车高负荷运行效果？ 出租汽车低负荷运行效果？ 动态规划应用之三：生产计划调度问题 P 219 例2 动态规划应用举例 动态规划求解 机器负荷分配问题 某种机器可以在高低两种不同的负荷下生产，高负荷生产产量函数为G= 8 U1 其中U1 表示投入生产的机器数量， 年完好率A=0.7 低负荷生产产量函数为H=5Y, 其中Y 表示投入生产的机器数量， 年完好率 B = 0. 9, 如果初始投入生产的机器1000台，问如何安排生产，使在5年内生产的产品总量达到最大？ 第六章 动态规划（2） 高负荷生产 低负荷生产 动态规划建模 1 划分阶段：年度 2 状态变量： SK为K 年度完好的机器数 3 决策变量： UK为K 年度分配高负荷生产的机器数， SK － UK为K 年度 低负荷生产的机器数 4 状态转移方程： SK＋1 ＝0.7 UK + 0. 9 ( SK － UK ) 5 指标函数： VK为K 年度产量 ， VK＝8 UK + 5 ( SK － UK ) MAX{V1 + V2 + V3 + V4 + V5 } 6 递推公式： F6 (S6) =0 F6 (S6)表示当6年度完好的机器数S6时，从6年到5年最大产量 FK (SK) = MAX{8 UK + 5 ( SK － UK ) + FK+1 [0.7 UK + 0. 9 ( SK － UK ) ]} 第六章 动态规划（2） FK (SK)表示当K 年度完好的机器数SK时，从k年到5年最大产量 K＝5 F5 (S5) = MAX{8 U5 + 5 ( S5 － U5 ) + F6[0.7 U5 + 0. 9 ( S5 － U5 ) ]} 因为F6[0.7 U5 + 0. 9 ( S5 － U5 ) ]}＝0 F5 (S5) = MAX{8 U5 + 5 ( S5 － U5 )}＝ MAX{3 U5 + 5 S5 } U5 = S5 , 当U5 = S5 , F5 (S5) ＝ 8 S5 K＝4 F4 (S4) = MAX{8 U4 + 5 ( S4 － U4 ) + F5[0.7 U4 + 0. 9 ( S4 － U4 ) ]} = MAX{8 U4 + 5 ( S4 － U4 ) + 8[0.7 U4 + 0. 9 ( S4 － U4 ) ] = MAX{1. 4 U4 + 12 . 2 S4 } U4 = S4 , 当U4 = S4 , F4 (S4) ＝ 13 . 6 S4 同理，当U3 = S3 F3 (S3) ＝ 17 . 5 S3 当U2 =0 , F2 (S2) ＝ 20 . 8 S2 当U1 = 0 , F1 (S1) ＝ 23 .7 S1 第六章 动态规划（2） 最优解：前两年完好机器全部低负荷生产，后三年完好机器全部高负荷生产，最优产量23700台 第六章 动态规划（2） 动态规划（3） P226 应用举例 固定资金分配 有N个企业， 都需要两种资源，对于第K个企业，如果用第1种资源 XK ，用第2种资源 YK ,可以得到利润 RK (XK , YK) , 第1种资源 的单位价格为A, 第2种资源 的单位价格为B, 现有资金Z, 问应该购买第1种资源（设为X） 和第2种资源（设为Y） 各多少单位分配到N个企业，可以使总利润达到最大？ 第六章 动态规划（3） 动态规划应用之二：资源分配问题 有N个企业， 都需要两种资源，对于第K个企业，如果用第1种资源 XK ，用第2种资源 YK ,可以得到利润 RK (XK , YK) , 第1种资源 的单位价格为A, 第2种资源 的单位价格为B, 现有资金Z, 问应该购买第1种资源（设为X） 和第2种资源（设为Y） 各多少单位分配到N个企业，