运筹08(第八章动态规划)

2020/4/21运筹学OPERATIONSRESEARCH2020/4/22第八章动态规划§1多阶段决策最优化问题举例§2基本概念、基本方程与最优化原理§3离散确定性动态规划求解§4离散随机性动态规划求解§5一般数学规划模型的动态规划解法2020/4/23§1多阶段决策过程最优化问题举例例1最短路径问题下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。BACBDBCDEC41231231232216472483867561106437512020/4/24用穷举法的计算量:如果从A到E的站点有k个，除A、E之外每站有3个位置则总共有3k-1×2条路径；计算各路径长度总共要进行(k+1)3k-1×2次加法以及3k-1×2-1次比较。随着k的值增加时，需要进行的加法和比较的次数将迅速增加；例如当k=20时，加法次数为4.2550833966227×1015次，比较1.3726075472977×1014次。若用1亿次/秒的计算机计算需要约508天。2020/4/25讨论：1、求从A到E的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从Di、Ci、Bi、A到E的最短路径问题。第四阶段：两个始点D1和D2，终点只有一个；分析得知：从D1和D2到E的最短路径唯一。阶段4本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)ED1D2106106EE2020/4/26第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点和终点进行分析和讨论分别求C1，C2，C3到D1，D2的最短路径问题：表-2分析得知：如果经过C1，则最短路为C1-D2-E；如果经过C2，则最短路为C2-D2-E；如果经过C3，则最短路为C3-D1-E。阶段3本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)D1D2C1C2C38+10=187+10=171+10=116+6=125+6=116+6=12121111D2D2D12020/4/27第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和终点进行分析和讨论分别求B1,B2,B3,B4到C1,C2,C3的最短路径问题：表-3分析得知：如果经过B1，则走B1-C2-D2-E；如果经过B2，则走B2-C3-D1-E；如果经过B3，则走B3-C3-D1-E；如果经过B4，则走B4-C3-D1-E。阶段2本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)C1C2C3B1B2B3B42+12=144+12=164+12=167+12=191+11=127+11=188+11=195+11=166+11=172+11=133+11=141+11=1212131412C2C3C3C32020/4/28第一阶段：只有1个始点A，终点有B1,B2,B3,B4。对始点和终点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：表10-4最后，可以得到：从A到E的最短路径为AB4C3D1E阶段1本阶段始点(状态)本阶段各终点（决策）到E的最短距离本阶段最优终点(最优决策)B1B2B3B4A4+12=163+13=163+14=172+12=1414B42020/4/29以上计算过程及结果，可用图2表示，可以看到，以上方法不仅得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最短路径。以上过程，仅用了22次加法，计算效率远高于穷举法。BACBDBCDEC412312312332164724838675161060106121111121314144B1275122020/4/210动态规划是用来解决多阶段决策过程最优化的一种方法。多阶段决策：是动态决策问题的一种特殊形式；系统的动态过程可以按照时间等进程分为状态相互联系而又相互区别的各个阶段；每个阶段都要进行决策,目的是使整个过程的决策达到最优效果2020/4/211动态规划问题具有以下基本特征1.问题具有多阶段决策的特征。阶段可以按时间划分，也可以按空间划分。2.每一阶段都有相应的“状态”与之对应。3.每一阶段都面临一个决策，选择不同的决策将会导致下一阶段不同的状态，同时，不同的决策将会导致这一阶段不同的目标函数值。4.每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题，各子问题与原问题具有完全相同的结构。能否构造这样的递推归结，是解决动态规划问题的关键。这种递推归结的过程，称为“不变嵌入”。2020/4/2125.状态具有无后效性当某阶段状态确定后，此阶段以后过程的发展不受此阶段以前各阶段状态的影响。动态规划基本原理是将一个问题的最优解转化为求子问题的最优解，研究的对象是决策过程的最优化，其变量是流动的时间或变动的状态，最后到达整个系统最优。基本原理一方面说明原问题的最优解中包含了子问题的最优解，另一方面给出了一种求解问题的思路，将一个难以直接解决的大问题，分割成一些规模较小的相同子问题，每一个子问题只解一次，并将结果保存起来以后直接引用，避免每次碰到时都要重复计算，以便各个击破，分而治之，即分治法，是一种解决最优化问题的算法策略。动态规划求解可分为三个步骤：分解、求解与合并。2020/4/213例2资源分配问题设有某种机器数台，用于完成两类工作A，B。由于机器使用后有一定的损坏率，所以每年初的机器数量是变化的；A、B两项工作产生的收益也不同。如何合理的分配机器的使用，可使得三年的总收益最大?假设第k年年初完好机器数是SK，用于A生产的机器数是XK，则用于B生产的机器数是（SK-XK）；用于A工作的设备的完好率是：a%，用于B工作的设备的完好率是：b%。则下一年初的完好机器数是SK+1=a%XK+b%（SK-XK）第k年的收益：h(XK)+g(SK-XK)2020/4/214例3背包问题设有n种物品，每一种物品数量无限。第i种物品每件重量为wi公斤，每件价值ci元。现有一只可装载重量为W公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。这个问题可以用整数规划模型来描述。设xi为第i种物品装入背包的件数（i=1,2,…,n），背包中物品的总价值为z，则Maxz=c1x1+c2x2+…+cnxns.t.w1x1+w2x2+…+wnxn≤Wx1,x2,…,xn0且为整数。2020/4/215一、基本概念：1、阶段(stage)k：表示决策顺序的离散的量，阶段可以按时间或空间划分。(顺序编号法、逆序编号法）2、状态(state)sk：反应前一阶段决策的结果，又是本阶段组作决策的依据和出发点（能确定地表示决策过程当前特征的量）。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。3、决策(decision)xk：从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为xk(sk)。决策允许集合Dk(sk)：在状态sk下，允许采取决策的全体xk(sk)∈Dk(sk)§2基本概念、基本方程与最优化原理2020/4/2164、策略Pk,n(sk)：从第k阶段开始到最后第n阶段的决策序列，称k子策略。P1,n(s1)即为全过程策略。5、状态转移方程Sk+1=Tk(Sk,Xk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。6、指标函数或收益函数(Returnfunction)：是衡量对决策过程进行控制的效果的数量指标，具体可以是收益、成本、距离等指标。分为k阶段指标函数、k子过程指标函数及最优指标函数。k阶段指标函数从k阶段状态sk出发，选择决策xk所产生的第k阶段指标，称为k阶段指标函数,记为vk(sk,xk)。2020/4/217从k阶段状态sk出发，选择决策xk,xk+1,…,xn所产生的过程指标，称为k子过程指标函数或简称过程指标函数，记为Vk(sk,xk,xk+1,…,xn)或Vk，n为阶段数。过程指标函数最优指标函数从k阶段状态sk出发，对所有的子策略，最优的过程指标函数称为最优指标函数，记为fk(sk)，通常取Vk的最大值或最小值。)},({)(,,)(nkknksDdkkPsVsfoptkkk（Opt＝optimization表示“max”或“min”2020/4/218动态规划要求过程指标满足递推关系，即1111(,,,,)[(,),(,,,)]kkkknkkkkkknVsxxxVvsxVsxx(8-2)连和形式：1111(,,,,)(,(,,,)(,KKkkknkkkKkknnjjjnjkVVsxxxvsxVsxxvsxV＋）＋）(8-3)最优指标函数是nksfxsvOptsfkkkkksDxkkkkk,,2,1)},(},({)(11)((8-4)2020/4/219动态规划数学模型由式(8-4)或(8-6)、边界条件及状态转移方程构成。如连和形式的数学模型连乘形式(vj≠0)：1111(,,,,)(,)(,,,)(,)KKkkknkkkKkknnjjjnjkVVsxxxvsxVsxxvsxV＋=(8-5)最优指标函数是nksfdsvOptsfkkkkksDxkkkkk,,2,1)},(},({)(11)((8-6)),(0)(,,2,1)},(},({)(111)(kkknnkkkkksDxkkxsTssfnksfxsvOptsfkkk2020/4/220对于可加性指标函数，上式可以写为nksfxsvsfkkkkksDdkkoptkkk,,2,1)}(},({)(11)(上式中“opt”表示“max”或“min”。对于可乘性指标函数，上式可以写为nksfxsvsfkkkkksDxkkoptkkk,,2,1)}(},({)(11)(上式称为动态规划最优指标的递推方程，是动态规划的基本方程。终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，即确定最后一个状态n下最优指标fn(sn)的值。2020/4/221三、最优化原理作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。就是说，最优策略的任意子策略都是最优的。2020/4/222用逆序法列表k=n=5时，f5(v10)＝0)}(),({min)(55444)(44444sfxsvsfsDxk=4，递推方程为s4D4(s4)s5v4(s4,x4)v4(s4,x4)+f5(s5)f4(s4)最优决策x4*v7v7v10v1055+0=5*5v7v10v8v8v10v1088+0＝8*8v8→v10v9v9v10v1044+0=4*4v9v102020/4/223)}(),({min)(44333)(33333sfxsvsfsDxk=3，递推方程为表8-2s3D3(s3)s4v3(s3,x3)v3(s3,x3)+f4(s4)f3(s3)最优决策x3*v5v5v7v5v8v5v9v7v8v92862+5=7*8+8=166+4=107v5v7v6v6v7v6v8v6v9v7v8v9125812+5=175+8=138+4=12*12v6v92020/4/224k=2，递推方程为表8-3s2D2(s2)s3v2(s2,x2)v2(s2,x2)+f3(s3)f2(s2)最优决策x2*v2v2v5v2v6v5v6101310+7=17*13+12=2517v2v5v3v3v5v3v6v5v67107+7=14*10+12=2214v3v5v4v4v5v4v6v5v6131113+7=20*11+12=2320v4v5)}(),({min)(33222)(22222sfxsvsfsDx2020/4/225k=1，递推方程为表8-4)}(),({min)(22111)(11111sfxsvs