动态规划讲座

《动态规划讲座》由会员分享，可在线阅读，更多相关《动态规划讲座（21页珍藏版）》请在装配图网上搜索。

1、 4 动态规划动态规划 4.1 多阶段决策问题与动态规划 4.2 动态规划的基本概念 4.3 动态规划的步骤 4.4 动态规划的应用 1 求解静态规划问题 2 资源分配问题 3 不确定性采购问题 4 排序问题 例2 机器负荷分配问题 某种机器可以在高低两种不同的负荷下进行生产在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为 gg(u),这时机器的年完好率为a（0a1)在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为hh(v),这时机器的年完好率为b（ab1）假定开始生产时完好的机器数量为s1，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,

2、使五年内产品的总产量最高。4.1 多阶段决策问题与动态规划例1最短路问题以上两个问题都可以划分为先后多个决策阶段。这类问题就称为多阶段决策问题。多阶段决策问题的过程如下图所示：状态状态状态状态决策决策决策状态 多阶段决策问题和我们前面遇到的决策问题不同，它是和时间有关的。与时间有关的活动过程称为动态过程，其优化方法称为动态规划。而与时间无关的活动过程称为静态过程，相应的的优化方法称为静态规划。(1)阶段（stage）把所研究的决策问题，按先后顺序划分为若干相互联系的决策步骤，以便按一定的次序进行求解。描述阶段的变量称阶段变量，常用k表示。(2)状态（state）状态表示每个阶段开始时所处的自然

3、状况或客观条件，它描述了影响决策的因素随决策进程的变化情况，它既是前面阶段所作决策的结果，又是本阶段作出决策的出发点和依据。描述状态的变量称为状态变量，第k阶段的状态变量常用sk表示。通常，在第一阶段状态变量s1是确定的，称初始状态。(3)决策（decision）决策表示在某一阶段处于某种状态时，决策者在若干种方案中作出的选择决定。描述决策的变量称决策变量，第k阶段的决策变量常用uk表示。决策变量的取值会受到状态变量的制约，被限制在某一范围之内。4.2 动态规划的基本概念（一）(4)策略（policy）把从第一阶段开始到最后阶段终止的整个决策过程，称为问题的全过程；而把从第k阶段开始到最后阶段

4、终止的决策过程，或称为k子过程。在全过程上，各阶段的决策按顺序排列组成的决策序列p1,n u1,u2,un 称为全过程策略，简称 策 略；而 在 k 子 过 程 上 的 决 策 序 列 pk,n uk,uk+1,un 称为k子过程策略，也简称子策略。(5)状态转移方程 若第k阶段的状态变量值为sk，当决策变量uk的取值决定后，下一阶段状态变量sk+1的值也就完全确定。即sk+1的值对应于sk和uk的值。这种对应关系记为sk+1Tk(sk,uk)，称为状态转移方程。状态转移方程描述了由一个阶段的状态到下一阶段的状态的演变规律。4.2 动态规划的基本概念（二）(6)指标函数和最优值函数 指标函数分

5、为阶段指标函数和过程指标函数。阶段指标函数是对某一阶段的状态和决策产生的效益值的度量，用vk(sk,uk)表示。过程指标函数是指过程所包含的各阶段的状态和决策所产生的总的效益值，记为 Vk,nVk,n(sk,uk,sk+1,uk+1,sn,un)动态规划所要求的过程指标函数应具有可分离性，即可表达为它所包含的各阶段指标函数的函数形式。常见的两种过程指标函数形式是：各阶段指标函数的和 Vk,nvj(sj,uj)；各阶段指标函数的积 Vk,nvj(sj,uj)。把过程指标函数Vk,n对k子过程策略pk,n求最优，得到一个关于状态sk的函数，称为最优值函数，记为fk(sk)。即 fk(sk)opt

6、Vk,n(sk,uk,sn,un)uk,un式中的“opt”（optimization）可根据具体问题而取min或max。(7)基本方程 通常动态规划问题的最优值函数满足递推关系式。设过程指标函数为各阶段指标函数的和的形式，即Vk,nvj(sj,uj)，则有 fk(sk)opt vk(sk,uk)+fk+1(sk+1)ukDk(sk)(kn,n-1,1)递推方程 fn+1(sn+1)0 边界条件递推方程和边界条件一起称为动态规划的基本方程。可根据边界条件，从k=n开始，由后向前逆推，逐步求得各阶段的最优决策和相应的最优值，最后求出f1(s1)时，就得到整个问题的最优解。例 最 短 路 问 题此

7、问题的基本方程为此问题的基本方程为f fk k(s(sk k)MindMindk k(u(uk k)+f)+fk+1k+1(s(sk+1k+1)u uk kDDk k(s(sk k)k k6,5,4,3,2,16,5,4,3,2,1f f7 7(s(s7 7)0 04.3 动态规划的步骤（一）动态规划的步骤（一）当k=6时s s6 6 u u6 6 D D(u u6 6)+f f7 7(s s7 7)F F6 6(s s6 6)F F1 1 F F1 1G G 4 4+0 0=4 4*4 4 F F2 2 F F2 2G G 3 3+0 0=3 3*3 3 按基本方程由后向前按基本方程由后向前

8、继续继续递推有递推有:当k=5时当k=4时s s4 4 u u4 4 d d(u u4 4)+f f5 5(s s5 5)f f4 4(s s4 4)D D1 1 D D1 1E E1 1 D D1 1E E2 2 2 2+7 7=9 9 2 2+5 5=7 7*7 7 D D2 2 D D2 2E E2 2 D D2 2E E3 3 1 1+5 5=6 6*2 2+9 9=1 11 1 6 6 D D3 3 D D3 3E E2 2 D D3 3E E3 3 3 3+5 5=8 8*3 3+9 9=1 12 2 8 8 s s5 5 u u5 5 d d(u u5 5)+f f6 6(s s

9、6 6)f f5 5(s s5 5)E E1 1 E E1 1F F1 1 E E1 1F F2 2 3 3+4 4=7 7*5 5+3 3=8 8 7 7 E E2 2 E E2 2F F1 1 E E2 2F F2 2 5 5+4 4=9 9 2 2+3 3=5 5*5 5 E E3 3 E E3 3F F1 1 E E3 3F F2 2 6 6+4 4=1 10 0 6 6+3 3=9 9*9 9 当当k=3时时s s3 3 u u3 3 d d(u u3 3)+f f4 4(s s4 4)f f3 3(s s3 3)C C1 1 C C1 1D D1 1 C C1 1D D2 2 6

10、6+7 7=1 13 3*8 8+6 6=1 14 4 1 13 3 C C2 2 C C2 2D D1 1 C C2 2D D2 2 3 3+7 7=1 10 0*5 5+6 6=1 11 1 1 10 0 C C3 3 C C3 3D D2 2 C C3 3D D3 3 3 3+6 6=9 9*3 3+8 8=1 11 1 9 9 C C4 4 C C4 4D D2 2 C C4 4D D3 3 8 8+6 6=1 14 4 4 4+8 8=1 12 2*1 12 2 当当k=2时时当当k=1时时s s2 2 u u2 2 d d(u u2 2)+f f3 3(s s3 3)f f2 2(

11、s s2 2)B B1 1 B B1 1C C1 1 B B1 1C C2 2 B B1 1C C3 3 1 1+1 13 3=1 14 4 3 3+1 10 0=1 13 3*6 6+9 9=1 15 5 1 13 3 B B2 2 B B2 2C C2 2 B B2 2C C3 3 B B2 2C C4 4 8 8+9 9=1 17 7 7 7+9 9=1 16 6*6 6+1 12 2=1 18 8 1 16 6 s s1 1 u u1 1 d d(u u1 1)+f f2 2(s s2 2)f f1 1(s s1 1)A A A AB B1 1 A AB B2 2 5 5+1 13 3

12、=1 18 8*3 3+1 16 6=1 19 9 1 18 8 由此可以看出，由此可以看出，A到到G的最短路长为的最短路长为18，路径为：，路径为：AB1C2D1E2F2G现在把动态规划法的步骤归纳如下：现在把动态规划法的步骤归纳如下：(1)(1)将所研究问题的过程划分为将所研究问题的过程划分为n n个恰当的阶段，个恰当的阶段，k k 1,2,n 1,2,n；(2)(2)正确地选择状态变量正确地选择状态变量S Sk k，并确定初始状态并确定初始状态S S1 1的值；的值；(3)(3)确定决策变量确定决策变量u uk k以及各阶段的允许决策集以及各阶段的允许决策集D Dk k(S(Sk k)；

13、(4)(4)给出状态转移方程；给出状态转移方程；(5)(5)给出满足要求的过程指标函数给出满足要求的过程指标函数V Vk,nk,n及相应的最优及相应的最优 值函数；值函数；(6)(6)写出递推方程和边界条件，建立基本方程；写出递推方程和边界条件，建立基本方程；(7)(7)按照基本方程递推求解。按照基本方程递推求解。以上步骤是动态规划法处理问题的基本步骤，其以上步骤是动态规划法处理问题的基本步骤，其中的前六步是建立动态规划模型的步骤。中的前六步是建立动态规划模型的步骤。4.3 动态规划的步骤（二）动态规划的步骤（二）例：机器负荷问题例：机器负荷问题 某种机器可以在高低两种某种机器可以在高低两种不

14、同的负荷下进行生产在高负荷下进行生产不同的负荷下进行生产在高负荷下进行生产时，产品的年产量时，产品的年产量g g和投入生产的机器数量和投入生产的机器数量u u的的关系为关系为 g g8u,8u,这时机器的年完好率为这时机器的年完好率为a=0.7a=0.7在低负荷下生产时，产品的年产量在低负荷下生产时，产品的年产量h h和和投入生产的机器数量投入生产的机器数量v v的关系为的关系为h h5v,5v,这时机这时机器的年完好率为器的年完好率为b=0.9b=0.9假定开始生产时完好假定开始生产时完好的机器数量为的机器数量为s s1 1，要求制定一个五年计划要求制定一个五年计划,在在每年开始时决定机器在

15、两种不同负荷下生产的每年开始时决定机器在两种不同负荷下生产的数量数量,使五年内产品的总产量最高。使五年内产品的总产量最高。(1)按年数划分为5个阶段，k=1,2,3,4,5(2)取第k年初完好的机器数sk为状态变量,s1=1000(3)取第k年投入高负荷的机器数xk为决策变量,0 xksk(4)状态转移方程为 sk+1=0.7xk+0.9(sk-xk)=0.9sk-0.2xk(5)指标函数为Vk,5=8xj+5(sj-xj)=(5sj+3xj)(6)基本方程为 fk(sk)max 5sj+3xj+fk+1(sk+1)k=5,4,3,2,1 0 xksk f6(s6)0解:当k=5时f5(s5)

16、max5s5+3x5+f6(s6)=max5s5+3x5=8s5 (x5*=s5)0 x5s5 0 x5s5当k=4时f4(s4)max5s4+3x4+8s5=max5s4+3x4+8(0.9s4-0.2x4)0 x4s4 0 x4s4 =max12.2s4+1.4x4=13.6s4 (x4*=s4)0 x4s4当k=3时f3(s3)max5s3+3x3+13.6s4=max5s3+3x3+13.6(0.9s3-0.2x3)0 x3s3 0 x3s3 =max17.24s3+0.28x3=17.5s3 (x3*=s3)0 x3s3当k=2时f2(s2)=max5s2+3x2+17.52s3=m

17、ax5s2+3x2+17.52(0.9s2-0.2x2)0 x2s2 0 x2s2 =max20.77s2-0.504x2=20.7s4 (x2*=0)0 x2s2当k=1时f1(s1)=23.7s1 (x1*=0)f1(1000)=23700s1=1000,x1*=0s2=900,x2*=0s3=810,x3*=810s4=576,x4*=576s5=397,x5*=397 某些静态规划问题可用动态规划法来求解。某些静态规划问题可用动态规划法来求解。例例 用动态规划法求解用动态规划法求解 max z=x12.x22.x3 x1+x2+x3=c xi0 i=1,2,34.4 动态规划的应用动态

18、规划的应用(一一)1 求解静态规划问题求解静态规划问题 资源分配问题可描述如下：设有某种原料，资源分配问题可描述如下：设有某种原料，总数量为总数量为a，分配给分配给n个使用者。已知第个使用者。已知第i个使用个使用者得到数量者得到数量xi的资源，可创造的收益为的资源，可创造的收益为gi（xi）。）。问应如何分配该资源，才能使总收益最大。问应如何分配该资源，才能使总收益最大。4.4 动态规划的应用动态规划的应用(二二)用动态规划法处理这种问题时，通常把给一用动态规划法处理这种问题时，通常把给一个使用者分配资源的过程看成一个阶段，按个使用者分配资源的过程看成一个阶段，按n n个使用者分成先后个使用者

19、分成先后n n个决策阶段。即先给第个决策阶段。即先给第1 1个个使用者分配资源，为第一阶段；再给第使用者分配资源，为第一阶段；再给第2 2个使个使用者分配，为第用者分配，为第2 2阶段；依此类推，最后给第阶段；依此类推，最后给第n n个使用者分配，为第个使用者分配，为第n n阶段。阶段。2 资源分配问题资源分配问题 例例 某工业部门根据国家计划安排，拟将某工业部门根据国家计划安排，拟将五台某种高效率的机器分配给所属的甲、五台某种高效率的机器分配给所属的甲、乙、丙三个工厂，各工厂得到不同数量的乙、丙三个工厂，各工厂得到不同数量的机器可获得的收益如下表。问应如何分配机器可获得的收益如下表。问应如何

20、分配机器，才能使各厂的总效益最大。机器，才能使各厂的总效益最大。工工厂厂机机器器数数 甲甲 乙乙 丙丙0 01 12 23 34 45 50 0 0 0 0 03 3 5 5 4 4 7 7 1 10 0 6 6 9 9 1 11 1 1 11 1 1 12 2 1 11 1 1 12 2 1 13 3 1 11 1 1 12 2 某单位准备在以后的某单位准备在以后的n n个时期内采购一批物资。各个时期内采购一批物资。各时期的价格不是确定的，而是按照某种已知的概率分时期的价格不是确定的，而是按照某种已知的概率分布取值。试制定采购策略，确定在哪一时期以什么价布取值。试制定采购策略，确定在哪一时期

21、以什么价格采购，能使采购价的数学期望值最低。这类问题也格采购，能使采购价的数学期望值最低。这类问题也适合用动态规划法进行处理。下面通过实例加以说明。适合用动态规划法进行处理。下面通过实例加以说明。例例7 7 某厂生产上需要在近五周某厂生产上需要在近五周内采购一批原料，而估计在未内采购一批原料，而估计在未来五周的价格有波动，其浮动来五周的价格有波动，其浮动价格和概率策得如下表。试确价格和概率策得如下表。试确定该厂应在哪一周以什么价格定该厂应在哪一周以什么价格购入，能使其采购价的数学期购入，能使其采购价的数学期望值最小，并求出期望值。望值最小，并求出期望值。价价 格格 概概 率率 5 50 00

22、0 6 60 00 0 7 70 00 00 0.3 30 0.3 30 0.4 44.4 动态规划的应用(三)3 不确定性采购问题 设有n个工件需要在机床A、B上加工，每个工件都必须先经过A而后B两道加工工序。以ai、bi分别表示工件i(1in)在A、B上的加工时间。问应如何在两机床上安排各工件的加工顺序，使在机床A上加工第一个工件开始到在机床B上加工完最后一个工件为止，所用的加工总时间最少？加工工件在机床A上有加工顺序问题，在机床B上也有加工顺序问题。可以证明：最优加工顺序在两台机床上可同时实现。因此，最优排序方案可以只在机床A、B上加工顺序相同的排序中寻找。即使如此，所有可能的方案仍有n

23、!个，这是一个不小的数，用穷举法是不现实的。4.4 动态规划的应用(四)4 排序问题 用动态规划法可以推出，用动态规划法可以推出，工件工件i i应该排在工件应该排在工件j j之之前的条件前的条件为为 min(amin(ai i,b,bj j)min(a)min(aj j,b,bi i)。根据这个条件，根据这个条件，构造下列排序方法：构造下列排序方法：a a1 1 a a2 2 a an n 1)1)建立工时矩阵建立工时矩阵 M=M=b b1 1 b b2 2 b bn n 2)2)在工时矩阵在工时矩阵M M中找出最小元素（若不止一个可任中找出最小元素（若不止一个可任选其一），若它在上行，则相应

24、的工件排在最前位选其一），若它在上行，则相应的工件排在最前位置；若它在下行，则相应的工件排在最后位置。置；若它在下行，则相应的工件排在最后位置。3)3)将排定位置的工件所对应的列从将排定位置的工件所对应的列从M M中划去，然后中划去，然后对余下的工件再按对余下的工件再按2)2)进行排序。如此进行下去，直进行排序。如此进行下去，直到把所有工件都排完为止。到把所有工件都排完为止。当加工顺序排定之后，工件在当加工顺序排定之后，工件在A A上没有等待时间，上没有等待时间，而在而在B B上则常常需要等待。因此，寻求最优排序方案上则常常需要等待。因此，寻求最优排序方案只有尽量减少在只有尽量减少在B B上等待加工的时间，才能使总加工上等待加工的时间，才能使总加工时间最短。时间最短。例 设有5个工件需在机床A、B上加工，加工的次序为先A后B，每个工件需要的加工时间如下表。试安排加工顺序，使总加工时间最少，并求出总加工时间。工工件件 A A B B 1 2 3 4 5 3 7 4 5 7 6 2 7 3 4