第10章-动态规划课件

第十章动态规划DynamicProgramming

§1动态规划的基本概念和方法§2动态规划的基本原理§3动态规划的应用举例运筹学OperationsResearch重点掌握:1.动态规划的基本概念

2.动态规划的应用举例10.1动态规划的基本概念和方法v2v3v4v7v5v9v6v8v1028512131071013112865885405847【例10.1-1】最短路径问题图10－1表示从起点v1到终点v10之间各点的距离。求v1到v10的最短路径。图10－1v1第1阶段第2阶段第3阶段第4阶段阶段：1217142019Min{2+5,8+8,6+4}=7逆标法27七月2023动态规划问题具有以下基本特征

1.问题具有多阶段决策的特征。阶段可以按时间划分，也可以按空间划分。

2.每一阶段都有相应的“状态”与之对应。

3.每一阶段都面临一个决策，选择不同的决策将会导致下一阶段不同的状态，同时，不同的决策将会导致这一阶段不同的目标函数值。

4.每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题，各子问题与原问题具有完全相同的结构。能否构造这样的递推归结，是解决动态规划问题的关键。这种递推归结的过程，称为“不变嵌入”。27七月2023动态规划是解决多阶段决策过程最优化问题的一种方法。是现代企业管理中的一种重要决策方法。用于解决最优路径问题、资源分配问题、生产计划与库存问题、投资问题、排序问题及生产过程的最优控制等问题。在处理某些优化问题时，常比线性规划或非线性规划方法更有效。27七月20231.1多阶段决策过程的最优化多阶段决策过程：指这样一类特殊的活动过程，它们可以按时间顺序分解成若干相互联系的阶段，在每一阶段都要做出决策，全部过程的决策是一个决策序列。多阶段决策过程最优化的目标，是要达到整个活动过程的总体效果最优，所以多阶段的决策并不是各阶段决策的简单总合。27七月2023

由于各阶段决策间有机地联系着，本段决策的执行将影响到下一阶段的决策，以至于影响总体效果，所以决策者在每阶段决策时不应仅考虑本阶段最优，还应考虑对最终目标的影响，从而做出对全局来讲是最优的决策。动态规划就是符合这种要求的一种决策方法。动态规划方法与“时间”关系密切，随着时间过程的发展而决定各阶段的决策，产生一个决策序列，这就是“动态”的意思。对于静态问题，只要在问题中人为地引入“时间”因素，将问题看成多阶段的决策过程即可。27七月2023例：生产与存贮问题某工厂每月需供应市场一定数量的产品。供应需求所余产品应存入仓库，一般地，某月适当增加产量可降低生产成本，但超产部分存入仓库会增加库存费用，要确定一个逐月的生产计划，在满足需求条件下，使一年的生产与存贮费用之和最小。把每月作为一个阶段，全年分为12个阶段逐次决策。27七月2023例：投资决策问题某公司现有资金Ｑ万元，在今后5年内考虑给Ａ、Ｂ、Ｃ、Ｄ四个项目投资，这些项目的投资期限、回报率均不相同，问应如何确定这些项目每年的投资额，使到第5年末拥用资金的本利总额最大。看作5阶段决策问题。27七月2023例：设备更新问题企业在使用设备时都要考虑设备的更新问题，因为设备越陈旧所需的维修费用越多，但购买新设备则要一次性支出较大的费用。现在某企业要决策一台设备未来8年的更新计划，已预测了第j年购买设备的价格为kj，rj为设备经过j年后的残值，cj为设备连续使用j-1年后在第j年的维修费（j=1~8)，问应在哪年更新设备可使总费用最小。这是一个8阶段决策问题。27七月20231.2动态规划的基本概念(1)阶段(2)状态(3)决策和策略(4)状态转移(5)指标函数27七月202395例10.1-2、最短线路问题(状态)(决策)(方程)(目标)(思想)设某厂Ａ要把一批货运到Ｅ城市出售，中部可经过①~⑧城市，各城市间的交通线及距离如下图，问应选择什么路线，可使总距离最短？A12345678E864543356213987876阶段无后效性策略原理27七月2023例10.1-3：生产与存贮问题：某工厂生产并销售某种产品，已知今后4个月市场需求预测如下表，每月生产j单位产品费用为：c(j)=3+j千元(j=1~6)。每月库存j单位产品的费用为E(j)=0.5j(千元)。该厂最大库存容量为3个单位，每日最大生产能力为6个单位，计划开始和计划期末库存量都是零。试制定4个月的生产计划，在满足用户需求条件下总费用最小。假设第i+1个月的库存量是第i个月可销量与该月用户需求量之差。而第i个月的可销售量是本月初库存量和产量之和。(状态)(决策)(方程)(目标)i(月)1234gi(需求)2324阶段27七月2023(1)阶段(Stage)把问题的过程，按时间或空间特征分解成若干互相联系的阶段，以便按次序去求每阶段的解，常用k表示阶段变量。在例10.1-2和例10.1-3中，可知问题属于多阶段决策。例10.1-2，可把从Ａ到Ｅ看成一个4阶段问题。例10.1-3，把每个月作为一个阶段，共分为4个阶段。27七月2023(2)状态(State)

各阶段开始时的自然状况或客观条件，叫状态。描述各阶段状态的变量为状态变量。常用sk表示第k阶段的状态变量，状态变量sk的取值集合用状态集合Sk表示。例10.1-2，第一阶段的状态为Ａ，第二阶段有三个状态，城市①、②、③。状态变量s2的集合S2={①、②、③},S3={④、⑤、⑥}例10.1-3，把每月月初的产品库存量作为状态27七月2023动态规划的状态具有如下性质：当某阶段状态给定以后，在这阶段以后过程的过去历史不受这段以前各段状态的影响。即过程的过去历史只能通过当前状态去影响它未来的发展，称为无后效性。如果所选的变量不具备无后效性，就不能作为状态变量来构造动态规划模型。如例10.1-2中，当某段的初始状态所在的城市选定后，从这个城市以后的运货路线只与这个城市有关，不受以前的运货路线影响，有无后效性。27七月2023(3)决策和策略(DecisionandPolicy)当各阶段的状态取定后，就可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策。表示决策的变量称为决策变量，用uk(sk)表示第k个阶段当状态为sk时的决策变量。决策变量的取值范围称为允许决策集合，用Dk(sk)表示第k阶段从状态sk出发的允许决策集合。uk(sk)∈Dk(sk)27七月2023例10.1-2，第二阶段的状态集合S2={①、②、③}。从城市①出发，可选择走城市④、⑤、⑥，即其允许决策集合D2(①)={④、⑤、⑥}.

如决策选择城市⑤，则此时决策变量表示为：

u2(①)=⑤见例10.1-2例10.1-3，决策变量是各月的产品产量。见例10.1-3

27七月2023各阶段决策确定后，整个问题的决策序列就构成一个策略。用P1,n(u1,u2,……,un)表示。例10.1-2对每个实际问题，可供选择的策略有一定范围，称为允许策略集合，用P表示。使整个问题达到最优效果的策略称为最优策略。27七月2023(4)状态转移方程

动态规划中本阶段的状态往往是上一阶段的决策结果。如果给定了第k阶段的状态sk，本阶段决策为uk(sk)，则第k+1阶段的状态为sk+1也就确定，关系如下：

sk+1=Tk(sk,uk)由于它表示了k阶段到k＋1阶段的状态转移规律，故称为状态转移方程。例10.1-2：sk+1=uk(sk)如u2(①)=⑤(见例10.1-2)例10.1-3：第k+1阶段的库存量等于第k阶段库存量及产量的和，再减去当月的需求量，即：

sk+1=(sk+uk)－gk见例10.1-327七月2023(5)指标函数用于衡量所选定策略优劣的数量指标称为指标函数。一个n阶段决策过程，从第1阶段到第n阶段，叫问题的原过程。对于任意一个给定的k(1≤k≤n)，从第k段到第n段的过程，称为原过程的一个后部子过程。n1k…………..27七月2023V1,n(s1,P1,n)表示初始状态为s1采用策略P1,n时原过程的效益值。Vk,n(sk,Pk,n)表示初始状态为sk采用策略Pk,n时后部子过程的效益值。27七月2023最优指标函数记为fk(sk)，表示从第k阶段状态为sk，采用最优策略p*k,n到过程终止时的最佳效益值。

fk(sk)=Vk,n(sk,P*k,n)=OptVk,n(sk,Pk,n)当k=1时，f1(s1)就是从初始状态s1到全过程结束的整体最优函数。最优27七月2023例10.1-2，指标函数是距离。如第二阶段，状态为城市②时，V2,4(②)表示从城市②到城市Ｅ的距离。见例10.1-2

而f2(②)表示从城市②到城市Ｅ的最短距离。

本问题的总目标f1(A)，即从城市Ａ到终点城市Ｅ的最短距离。例10.1-3，衡量决策效果的指标函数是生产与存贮的费用，最优指标函数是指生产与存贮费用之和最低。本问题的总目标是求f1(0)，即初始库存量为0时，第1~4月的最低总费用。见例10.1-327七月20231.3动态规划的基本思想结合例10.1-2最短路线问题介绍动态规划的基本思想。例10.1-2分为四个阶段，从第一阶段状态A开始，到第二阶段的城市①、②、③有三种选择。从第二阶段的某个状态出发，又有④、⑤、⑥三种选择，这样得出一个决策序列，即一个策略。即从Ａ到Ｅ的一条路线。可用比较法把从Ａ到Ｅ的所有路线的路长求出，加以比较。27七月202395例10.1-2、最短线路问题

设某厂Ａ要把一批货运到Ｅ城市出售，中部可经过①~⑧城市，各城市间的交通线及距离如下图，问应选择什么路线，可使总距离最短？A12345678E86454335621398787627七月2023用动态规划求解：从过程的最后一个阶段开始，用逆序递推方法求解，逐步求出各段各点到终点Ｅ的最短路线，最后求得Ａ到Ｅ点的最短路线。用动态规划基本思想解例10.1-2。nn-1127七月2023v2v3v4v7v5v9v6v8v1028512131071013112865885405847图10－1v1第1阶段第2阶段第3阶段第4阶段阶段：1217142019Min{2+5,8+8,6+4}=7用逆序法列表求解例10.1-127七月2023用逆序法列表求解例10.1-1k=n=5时，f5(v10)＝0k=4，递推方程为

s4D4(s4)s5v4(s4,x4)v4(s4,x4)+f5(s5)f4(s4)最优决策x4*v7v7v10v1055+0=5*5v7v10v8v8v10v1088+0＝8*8v8→v10v9v9v10v1044+0=4*4v9v1027七月2023k=3，递推方程为表10-2s3D3(s3)s4v3(s3,x3)v3(s3,x3)+f4(s4)f3(s3)最优决策x3*v5v5v7v5v8v5v9v7v8v92862+5=7*8+8=166+4=107v5v7v6v6v7v6v8v6v9v7v8v9125812+5=175+8=138+4=12*12v6v910.1动态规划的基本概念27七月2023v2v3v4v7v5v9v6v8v1028512131071013112865885405847图10－1v1第1阶段第2阶段第3阶段第4阶段阶段：1217142019用逆序法列表求解例10.1-1f4(s4)27七月2023k=2，递推方程为表10-3s2D2(s2)s3v2(s2,x2)v2(s2,x2)+f3(s3)f2(s2)最优决策x2*v2v2v5v2v6v5v6101310+7=17*13+12=2517v2v5v3v3v5v3v6v5v67107+7=14*10+12=2214v3v5v4v4v5v4v6v5v6131113+7=20*11+12=2320v4v527七月2023k=1，递推方程为表10-4s1D1(s1)s2v1(s1,x1)v1(s1,x1)+f2(s2)f1(s1)最优决策x1*v1v1v2v1v3v1v4v2v3v42852+17=19*8+14=225+20=2519v1v2最优值是表10-4中f1(s1)的值，从v1到v10的最短路长为19。最短路线从表10-4到表10-1回朔，查看最后一列最优决策，得到最短路径为：v1

v2

v5

v7v1027七月2023作业：教材P225第1题下一节：基本原理27七月202310.2动态规划的基本原理27七月2023一、最优化原理一个过程的最优策略具有这样的性质：即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策必构成最优策略。即：最优策略的任一后部子策略总是最优的。27七月2023例10.1-2正是据这一原理求解的，从图中可看出，无论从哪一段的某状态出发到终点Ｅ的最短路线，只与此状态有关，而与这点以前的状态、路线无关，即不受从Ａ点是如何到达这点的决策影响。而且从Ａ点到Ｅ点的最短路线若经过sk点，则此路线由sk到Ｅ点的后半部，必是由sk点到Ｅ的最短路线。此特性用反证法易证。ＥＡsk27七月2023二、动态规划基本方程的基本要素①将问题的过程划分为恰当的阶段；②正确选择状态变量sk，使它既能描述过程的演变，又要满足无后效性。③确定决策变量uk及每阶段的允许决策集合Dk(sk)④正确写出状态转移方程；⑤根据题意明确指标函数Vk,n，最优指标函数fk(sk)及一段效益即阶段指标dk(sk,uk)的含义。正确列出最优指标函数的递推关系及边界条件，即基本方程。10.3动态规划应用一、资源分配问题二、系统可靠性问题27七月2023一.资源分配问题27七月2023【例10.3-1】公司有资金8万元，投资A、B、C三个项目，一个单位投资为2万元。每个项目的投资效益率与投入该项目的资金有关。三个项目A、B、C的投资效益(万元)和投入资金（万元）的关系见表10-5。求对三个项目的最优投资分配，使总投资效益最大。

项目投入资金ABC2万元89104万元1520286万元3035358万元384043表10-5K=327七月2023【解】设xk为第k个项目的投资，该问题的静态规划模型为27七月20231.阶段k：每投资一个项目作为一个阶段，共3个阶段。k=1,2,3。2.状态变量sk：投资第k个项目前的资金数3.决策变量xk：第k个项目的投资额决策允许集合：0≤xk≤sk4.状态转移方程：sk+1=sk－xk5.阶段指标：vk(sk，xk)见表10-5中的数据递推方程：

27七月2023终端条件：f4(s4)=0数学模型为

27七月2023第3阶段，s3取值为0、2、4、6、8

(分配给C的金额)

0

2

4

6

8

00－－－－00

20

10－－－102

40

10

28－－284

60

10

28

35

-

356

80

10

28

3543

438K=1题27七月2023

第二阶段：

当把资金分配给项目B和C时，则对每个值，有一种最优分配方案，使最大盈利即最优2子过程最优指标函数值为

27七月2023因为上式也可写成其数值计算如表所示。

0

2

4

6

8

0－－－－00

2

9+0－－－100

4

9＋10

20+0－－280

60＋35

20+10

35＋0－372

80＋43

9+35

35+10

40＋0

48410.3动态规划应用说明:s2分配给B,C,其中x2是分配给B的,s3=s2-x2是分配给C的k=3表的值27七月2023

第一阶段：把资金分配给项目A、B、C时，最大盈利为其中可取值0,2,4,6,8.数值计算见表

然后按计算表格的顺序推算，可知最优分配方案：由于，根据，查表k=2可知，再由，求得。即分配给不分给项目A，分配给B项目4万元资金，分配给C项目4万元，最优值为48万元。

0

2

4

6

8

8

8＋3715+2830+1038+048