动态规划运筹学基础及其应用胡运权第五版

1第九章动态规划（续）动态规划的基本原理动态规划方法的基本步骤动态规划方法应用举例本章以下内容2最优化原理（贝尔曼最优化原理）作为一个全过程的最优策略具有这样的性质：对于最优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个最优子策略。该原理的具体解释是，若某一全过程最优策略为：动态规划的基本原理)}(),(,),(),({)(221111nnkksususususp则对上述策略中所隐含的任一状态而言，第k子过程上对应于该状态的最优策略必然包含在上述全过程最优策略p1*中，即为)}(,),(),({)(11nnkkkkkksusususp33.动态规划方法的基本步骤1．应将实际问题恰当地分割成n个子问题(n个阶段)。通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数n，即k=n。2．正确地定义状态变量sk，使它既能正确地描述过程的状态，又能满足无后效性．动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的，动态规划中的状态变量必须具备以下三个特征：43.动态规划方法的基本步骤(1)要能够正确地描述受控过程的变化特征。(2)要满足无后效性。即如果在某个阶段状态已经给定，那么在该阶段以后，过程的发展不受前面各段状态的影响，如果所选的变量不具备无后效性，就不能作为状态变量来构造动态规划的模型。(3)要满足可知性。即所规定的各段状态变量的值，可以直接或间接地测算得到。一般在动态规划模型中，状态变量大都选取那种可以进行累计的量。此外，在与静态规划模型的对应关系上，通常根据经验，线性与非线性规划中约束条件的个数，相当于动态规划中状态变量sk的维数．而前者约束条件所表示的内容，常就是状态变量sk所代表的内容。53.动态规划方法的基本步骤3．正确地定义决策变量及各阶段的允许决策集合Uk(sk)，根据经验，一般将问题中待求的量，选作动态规划模型中的决策变量。或者在把静态规划模型(如线性与非线性规划)转换为动态规划模型时，常取前者的变量xj为后者的决策变量uk。4.能够正确地写出状态转移方程，至少要能正确反映状态转移规律。如果给定第k阶段状态变量sk的值，则该段的决策变量uk一经确定，第k+1段的状态变量sk+1的值也就完全确定，即有sk+1=Tk(sk,uk)63.动态规划方法的基本步骤5．根据题意,正确地构造出目标与变量的函数关系——目标函数，目标函数应满足下列性质：(1)可分性，即对于所有k后部子过程，其目标函数仅取决于状态sk及其以后的决策uk,uk+1,┈,un,就是说它是定义在全过程和所有后部子过程上的数量函数。(2)要满足递推关系，即(3)函数对其变元Rk+1来说要严格单调。)],,(,,[),,,,,(111111,nkkkkknkkkknkssRussususR)],,(,,[111nkkkkkssRus76．写出动态规划函数基本方程例如常见的指标函数是取各段指标和的形式其中表示第i阶段的指标，它显然是满足上述三个性质的。所以上式可以写成：3.动态规划方法的基本步骤nkiiiikkusgsR),()(),(iiiusg),,(),(111nkkkkkkssRusgR8学习方法建议：第一步先看问题，充分理解问题的条件、情况及求解目标。第二步结合前面讲到的理论和解题过程，考虑如何着手进行求解该问题的工作。分析针对该动态规划问题的“四大要素、一个方程”——这一步在开始时会感到困难，但是一定要下决心去思考，在思考过程中深入理解前文讲到的概念和理论。4.动态规划方法应用举例9第三步动手把求解思路整理出来，或者说，把该问题作为习题独立的来做。第四步把自己的求解放到一边，看书中的求解方法，要充分理解教材中的论述。第五步对照自己的求解，分析成败。4.动态规划方法应用举例12求最短路径13BACBDBCDEC212312312511214106104131211396581052阶段1阶段2阶段3阶段4阶段5求最短路径例5.514将问题分成五个阶段，第k阶段到达的具体地点用状态变量xk表示，例如：x2=B3表示第二阶段到达位置B3，等等。这里状态变量取字符值而不是数值。将决策定义为到达下一站所选择的路径，例如目前的状态是x2=B3，这时决策允许集合包含三个决策，它们是D2(x2)=D2(B3)={B3C1,B3C2,B3C3}求最短路径15最优指标函数fk(xk)表示从目前状态到E的最短路径。终端条件为f5(x5)=f5(E)=0其含义是从E到E的最短路径为0。第四阶段的递推方程为:fxvxdfxdDx4444455444()min{(,)()}()从f5(x5)到f4(x4)的递推过程用下表表示：x4D4(x4)x5v4(x4,d4)v4(x4,d4)+f5(x5)f4(x4)最优决策d4*D1D1EE55+0=5*5D1ED2D2EE22+0=2*2D2E求最短路径16其中*表示最优值，在上表中，由于决策允许集合D4(x4)中的决策是唯一的，因此这个值就是最优值。由此得到f4(x4)的表达式。由于这是一个离散的函数，取值用列表表示：f4(x4)的表达式x4f4(x4)最优决策d4*D15D1ED22D2E求最短路径17第三阶段的递推方程为：从f4(x4)到f3(x3)的递推过程用表格表示如下：x3D3(x3)x4v3(x3,d3)v3(x3,d3)+f4(x4)f3(x3)最优决策d3*C1C1D1C1D2D1D2393+5=8*9+2=118C1D1C2C2D1C2D2D1D2656+5=115+2=7*7C2D2C3C3D1C3D2D1D28108+5=1310+2=12*12C3D2)}(),({min)(44333)(33333xfdxvxfxDd求最短路径18由此得到f3(x3)的表达式：x3f3(x3)最优决策d3*C18C1D1C27C2D2C312C3D2第二阶段的递推方程为：)}(),({min)(33222)(22222xfdxvxfxDd从f3(x3)到f2(x2)的递推过程用表格表示如下：求最短路径19x2D2(x2)x3v2(x2,d2)v2(x2,d2)+f3(x3)f2(x2)最优决策d2*B1B1C1B1C2B1C3C1C2C312141012+8=20*14+7=2110+12=2220B1C1B2B2C1B2C2B2C3C1C2C361046+8=14*10+7=174+12=1614B2C1B3B3C1B3C2B3C3C1C2C313121113+8=2112+7=19*11+12=2319B3C2求最短路径20由此得到f2(x2)的表达式：x2f2(x2)最优决策d2*B120B1C1B214B2C1B319B3C2求最短路径21第一阶段的递推方程为：)}(),({min)(22111)(11111xfdxvxfxDd从f2(x2)到f1(x1)的递推过程用表格表示如下：x1D1(x1)x2v1(x1,d1)v1(x1,d1)+f2(x2)f1(x1)最优决策d1*AAB1AB2AB3B1B2B32512+20=225+14=19*1+19=2019AB2求最短路径22由此得到f1(x1)的表达式x1f1(x1)最优决策d1*A19AB2求最短路径23资源分配问题24例5.6:有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（万吨）和投入资金（万元）关系见下表：求对三个项目的最优投资分配，使总投资效益最大。资源分配问题251.阶段k：每投资一个项目作为一个阶段；2.状态变量xk：投资第k个项目前的资金数；3.决策变量dk：第k个项目的投资；4.决策允许集合：0≤dk≤xk5.状态转移方程：xk+1=xk-dk6.阶段指标：vk(xk,dk)见表中所示；7.递推方程：fk(xk)=max{vk(xk,dk)+fk+1(xk+1)}8.终端条件：f4(x4)=0资源分配问题26k=4，f4(x4)=0k=3，0≤d3≤x3，x4=x3-d3资源分配问题27k=2，0≤d2≤x2，x3=x2-d2资源分配问题28k=1，0≤d1≤x1，x2=x1-d1资源分配问题29背包问题30背包问题31则Maxz=c1x1+c2x2+…+cnxns.t.w1x1+w2x2+…+wnxn≤Wx1,x2,…,xn为正整数1.阶段k：第k次装载第k种物品（k=1,2,…,n）2.状态变量xk：第k次装载时背包还可以装载的重量；3.决策变量dk：第k次装载第k种物品的件数；背包问题324.决策允许集合：Dk(xk)={dk|0dkxk/wk，dk为整数}；5.状态转移方程：xk+1=xk-wkdk6.阶段指标：vk=ckdk7.递推方程fk(xk)=max{ckdk+fk+1(xk+1)}=max{ckdk+fk+1(xk-wkdk)}8.终端条件：fn+1(xn+1)=0背包问题33例5.7:对于一个具体问题c1=65，c2=80，c3=30；w1=2，w2=3，w3=1；以及W=5用动态规划求解f4(x4)=0对于k=3列出f3(x3)的数值表背包问题34对于k=3列出f3(x3)的数值表如下：35对于k=2)}3(80{max)}({max)(22323/03322/02222222dxfdxfdcxfxdwxd列出f2(x2)的数值表36对于k=1)}2(65{max)}({max)(11212/02211/01111111dxfdxfdcxfxdwxd列出f1(x1)的数值表37由题意知，x1=5，由表f1(x1)、f2(x2)、f3(x3)，经回朔可得：d1*=2，x2=x1-2d1=1，d2*=0，x3=x2-3d2=1，d3*=1，x4=x3-d3=0即应取第一种物品2件,第三种物品1件,最高价值为160元,背包没有余量。由f1(x1)得列表可以看出，如果背包得容量为W=4，W=3，W=2和W=1时，相应的最优解立即可以得到。38机器负荷分配问题39最短路径问题和背包问题的状态变量和决策变量都只能取离散的整数值。当状态变量和决策变量的取值范围很大，或者这些变量是连续的，用列举的方法就比较困难或者根本不可能了。这就需要用连续变量的处理方法。例5.8:某种机器可以在高、低两种负荷下生产。高负荷生产条件下机器完好率为0.7，即如果年初有u台完好机器投入生产，则年末完好的机器数量为0.7u台。系数0.7称为完好率。年初投入高负荷运行的u台机器的年产量为8u吨。系数8称为单台产量。低负荷运行时，机器完好率为0.9，单台产量为5吨。设开始时有1000台完好机器，要制订五年计划，每年年初将完好的机器一部分分配到高负荷生产，剩下的机器分配到低负荷生产，使五年的总产量为最高。40构造动态规划模型如下：阶段k：运行年份（k=1,2,3,4,5,6），其中k=1表示第一年初，…，依次类推；k=6表示第五年末（即第六年初）。状态变量xk：第k年初完好的机器数（k=1,2,3,4,5,6），其中x6表示第五年末（即第六年初）的完好机器数。决策变量dk：第k年投入高负荷运行的机器数；状态转移方程：xk+1=0.7dk+0.9(xk-dk)决策允许集合：Dk(xk)={dk|0dkxk}阶段指标：vk(xk,dk)=8dk+5(xk-dk)终端条件：f6(x6)=0机器负荷分配问题41递推方程：fk(xk)=max{vk(xk,dk)+fk+1(xk+1)}dkDk(xk)=max{8dk+5(xk-dk)+fk+1[0.7dk+0.9(xk-dk)]}0dkxk根据题意，本题的决策允许集合应该是一个整数集合，但由于决策允许集合中可取的决策