8.1动态规划数学模型 第8章动态规划 电气信息学院 佃松宜、李彬、曾晓东 Mathematical model of dp Dynamic Programming 2021年1月26日星期 Page 16 k=3,递推方程为 f3(S3)=mn、{v3(S32x3)+f4(S4) x3∈D3(S3) 表8-2 S3DS)s:(3x)e(sx3)f(S))最优决策x vs→>v7 v5→>vv8 286 2+5=7* 8+8=16 V5→>vg vg 6+4=10 v→vr 12+5=17 v6→>vgwg 5+8=13 12 v6>V9 v6→>vg 8 8+4=12
第8章 动态规划 电气信息学院 Dynamic Programming 佃松宜、李彬、曾晓东 2021年1月26日星期二 Page 16 ( ) min { ( , ) ( )} 3 3 3 4 4 ( ) 3 3 3 3 3 f s v s x f s x D s = + k=3，递推方程为 表8-2 s3 D3 (s3 ) s4 v3 (s3 ,x3 ) v3 (s3 ,x3 )+f4 (s4 ) f3 (s3 ) 最优决策x3 * v5 v5→v7 v 5→v8 v 5→v9 v7 v8 v9 2 8 6 2+5=7* 8+8=16 6+4=10 7 v5→v7 v6 v6→ v7 v 6→v8 v 6→v9 v7 v8 v9 12 5 8 12+5=17 5+8=13 8+4=12* 12 v6→v9 8.1 动态规划数学模型 Mathematical Model of DP
8.1动态规划数学模型 第8章动态规划 电气信息学院 佃松宜、李彬、曾晓东 Mathematical model of dp Dynamic Programming 2021年1月26日星期 Page 17 k=2,递推方程为 f2(S2)=mn{v2(S2x2)+f3(S3)} x2∈D2(S2) 表8-3 D2S2)s3"4522)n2(2x2+5(S)f()最优决策x2 v2→v 10+7=17* 17 v2→>v6 13 13+12=25 v2→>v5 7 7+7=14 10 10+12=22 v4→)v 13 13+7=20 "v→v6;1 11+12=23 v4→>v5
第8章 动态规划 电气信息学院 Dynamic Programming 佃松宜、李彬、曾晓东 2021年1月26日星期二 Page 17 k=2，递推方程为 表8-3 s2 D2 (s2 ) s3 v2 (s2 ,x2 ) v2 (s2 ,x2 )+f3 (s3 ) f2 (s2 ) 最优决策x2 * v2 v2→ v5 v2→ v6 v5 v6 10 13 10+7=17* 13+12=25 17 v2→ v5 v3 v3→ v5 v3→ v6 v5 v6 7 10 7+7=14* 10+12=22 14 v3→v5 v4 v4→ v5 v4→ v6 v5 v6 13 11 13+7=20* 11+12=23 20 v4→v5 ( ) min { 2 ( 2 , 2 ) 3 ( 3 )} ( ) 2 2 2 2 2 f s v s x f s x D s = + 8.1 动态规划数学模型 Mathematical Model of DP
8.1动态规划数学模型 第8章动态规划 电气信息学院 佃松宜、李彬、曾晓东 Mathematical model of dp Dynamic Programming 2021年1月26日星期 Page 18 k=1,递推方程为 f1(S1)=min{v1(S12x1)+f2(S2) x1∈D1(S1) 表8-4 D(s)s2v(S1r)v(11)+f2)f(s)最优决策x1 v→>v2 2+17=19* 19 v1→>v v1>v3 285 8+14=22 v1→v4v4 5+20=25 最优值是表8-4中f(s1)的值,从v到vn的最短路长为19。最短路 线从表8-4到表8-1回朔,査看最后一列最优决策,得到最短路 径为: 1→>v2→v→v-v10
第8章 动态规划 电气信息学院 Dynamic Programming 佃松宜、李彬、曾晓东 2021年1月26日星期二 Page 18 k=1，递推方程为 表8-4 ( ) min { 1 ( 1 , 1 ) 2 ( 2 )} ( ) 1 1 1 1 1 f s v s x f s x D s = + s1 D1 (s1 ) s2 v1 (s1 ,x1 ) v1 (s1 ,x1 )+f2 (s2 ) f1 (s1 ) 最优决策x1 * v1 v1→v2 v1→v3 v1→v4 v2 v3 v4 2 8 5 2+17=19* 8+14=22 5+20=25 19 v1→v2 最优值是表8-4中f1 (s1 )的值，从v1到v10的最短路长为19。最短路 线从表8-4到表8-1回朔，查看最后一列最优决策，得到最短路 径为： v1→ v2 → v5 → v7 → v10 8.1 动态规划数学模型 Mathematical Model of DP
82资源分配问题 Resource assignment problem
8.2 资源分配问题 Resource Assignment Problem
82资源分配问题 第8章动态规划 电气信息学院 佃松宜、李彬、曾晓东 Resource assignment Problem Dynamic Programming 2021年1月26日星期 Page 20 【例8-2】公司有资金8万元,投资A、B、C三个项目,一个单位投资为2万 元。每个项目的投资效益率与投入该项目的资金有关。三个项目A、B、C 的投资效益(万元和投入资金(万元)的关系见表85。求对三个项目的最优 投资分配,使总投资效益最大。 表85 项目 投入资金 2万元 10 4万元 15 20 28 6万元 30 35 35 8万元 38 43 【解】设x为第k个项目的投资,该问题的静态规划模型为 maxz=v,(x)+v2(x2)+v3(x3) 「x+x2+x1=8 2,4,6,8
第8章 动态规划 电气信息学院 Dynamic Programming 佃松宜、李彬、曾晓东 2021年1月26日星期二 Page 20 【例8-2】公司有资金8万元，投资A、B、C三个项目，一个单位投资为2万 元。每个项目的投资效益率与投入该项目的资金有关。三个项目A、B、C 的投资效益(万元)和投入资金（万元）的关系见表8-5。求对三个项目的最优 投资分配，使总投资效益最大。 8.2 资源分配问题 Resource Assignment Problem 项目 投入资金 A B C 2万元 8 9 10 4万元 15 20 28 6万元 30 35 35 8万元 38 40 43 表8-5 【解】设xk为第k个项目的投资，该问题的静态规划模型为 1 1 2 2 3 3 1 2 3 max ( ) ( ) ( ) 8 0,2,4,6,8 j Z v x v x v x x x x x = + + + + = =