运筹学---动态规划

•动态规划是一种研究多阶段决策问题的理论和方法。这种方法把一个多阶段决策问题转化成一系列相互联系的单阶段决策问题来求解。•动态规划主要应用于最短路问题、装载问题、库存问题、资源分配、生产过程最优化问题。•动态规划模型可以分为离散确定性、离散随机性、连续确定性、连续随机性四种决策过程。其中最基本的是离散确定性过程。第6章动态规划第6章动态规划§1多阶段的决策问题§2最优化原理与动态规划的数学模型§3动态规划应用举例§1多阶段的决策问题•多阶段决策问题：可以分为若干个互相联系的阶段，在每个阶段分别对应着一组可以选取的决策，当每个阶段的决策选定以后，过程也就随之确定。•多阶段决策问题，就是要在所有可能采取的策略中间选取一个最优的策略，是在预定的标准下得到最好的效果。[例1]最短路线问题。设有一旅行者从下图中的A点出发，途中要经过B、C、D等处，最后到达终点E。从A到E有很多条路可以选择，各点之间的距离如图所示，问该旅行者应选择哪一条路线，使从A到E的总路程最短？AB3B2B1C3C2C1D2D1E22351535657633414343用穷举法的计算量:如果从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天。[例2]设有某种机器设备，用于完成两类工作A和B.若k年初完好机器的数量为sk，若以数量xk用于A，余下的(sk-xk)用于工作B，则该年的预期收入为g(xk)+h(sk-xk).这里g(xk)和h(sk-xk)是已知函数，且g(0)=h(0)=0.又机器设备在使用中会有损坏，设机器用于工作A时，一年后能继续使用的完好机器数占年初投入量的a%；若用于B项工作时，一年后能继续使用的完好机器数占年初投入量的b%，即下一年初能继续用于完成这两项工作的设备数为sk+1=axk+b(sk-xk).设第一年初完好的机器总数为s0，问在连续三年内每年应如何分配用于A、B两项工作的机器数，使三年的总收益最大？[例3]将一个数c(c0)分成n个部分c1,c2,...,cn之和，且ci0(i=1,...,n)，问应如何分割使其乘积为最大？niic111max.0,(1,2,)niiniiiZCCCstCi§2最优化原理与动态规划的数学模型•动态规划问题的解题思路•动态规划的基本概念•最优化原理与动态规划的数学模型•逆序解法与顺序解法•动态规划模型的分类2.1动态规划问题的解题思路•基本思路：是将一个n阶段的决策问题转化为依次求解n个具有递推关系的单阶段的决策问题，从而简化计算过程。•在例1中，这种转化的实现是从终点E出发一步步进行反推，这种算法称为逆序算法。[例1]最短路线问题。设有一旅行者从下图中的A点出发，途中要经过B、C、D等处，最后到达终点E。从A到E有很多条路可以选择，各点之间的距离如图所示，问该旅行者应选择哪一条路线，使从A到E的总路程最短？AB3B2B1C3C2C1D2D1E22351535657633414343按逆序推算，例1的计算步骤为：•从D出发，f(D1)=3;f(D2)=4。•从C出发，f(C1)=4;f(C2)=7;f(C3)=6。•从B出发，f(B1)=11;f(B2)=7;f(B3)=8。•从A出发，f(A)=11。2.2动态规划的基本概念1、阶段(stage).是指一个问题需要做出决策的步数。如例1中旅行者需要在A、B、C、D四个阶段做出下一步的决策。通常用k来表示问题包含的阶段数，称为阶段变量。2、状态(state).这是动态规划中最关键的参数，它既反映前面各阶段决策的结局，又是本阶段做出决策的出发点和依据。状态是动态规划问题各阶段信息的传递点和结合点，第k阶段的状态通常用状态变量sk来描述。在例1中第2阶段的状态s2=(B1,B2,B3)。3、决策(decision).是指某阶段初从给定的状态出发，决策者在面临的若干种不同方案中做出的选择。用Dk(sk)表示k阶段状态为sk时决策允许的取值范围，xk(sk)表示第k阶段状态为sk时对方案的选择。如例1中D2(B1)={C1,C2,C3}。4、策略(policy)和子策略(subpolicy).动态规划问题各阶段决策组成的序列总体称作一个策略。如：{x1(s1),x2(s2),...,xn(sn)}。•把从某一阶段开始到过程最终的决策序列称为问题的子过程策略或子策略。如：{xk(sk),xk+1(sk+1),...,xn(sn)}。5、状态转移律，也称状态转移方程.从sk的某一状态值出发，当决策变量xk(sk)的取值决定后，下一阶段状态变量sk+1的取值也就随之确定。这种从上一阶段的某一状态值到下一阶段某一状态值的转移的规律成为状态转移律。如sk+1=T(sk,xk(sk))。6、指标函数.阶段的指标函数是对应某一阶段状态和从该状态出发的一个阶段的决策的某种效益度量，用rk(sk,xk)表示。过程的指标函数是指从状态sk(k=1,2,...,n)出发至过程最终，当采取某种子策略时，按预定标准得到的效益值。所谓最优指标函数，是指对某一确定状态选取最优策略后得到的指标函数值。记作fk(sk)。2.3最优化原理与动态规划的数学模型•求解动态规划的最优化原理(R.Bellman)：作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，对先前决策所形成的状态而言，余下的诸决策必构成最优策略。•基本方程：对于n阶段的动态规划问题，在求子过程上的最优指标函数时，k子过程与k+1过程有如下递推关系：fk(sk)=min{rk(sk,xk)+fk+1(xk+1)},k=n,...,2,1边界条件（终点条件）：fn+1(xn+1)=0•边界条件是指从最后一个阶段向前逆推时需要确定的条件。关于阶段的划分、状态变量、决策变量、允许决策集合和状态转移方程，应注意如下几点：•状态变量的确定是构造动态规划模型中最关键的一步，状态变量首先应描述反映研究过程的演变特征，其次它应包含到达这个状态前的足够信息，并具有无后效性，还应具有可知性。•决策变量是对过程进行控制的手段，复杂的问题决策变量也可以是多维的向量，允许决策集合相当于线性规划问题中的约束条件。•状态转移律。当给出sk、xk的取值后，如果sk+1的取值唯一确定，相应的决策过程称为确定性的多阶段决策过程，否则称为随机性的多阶段决策过程。•指标函数是衡量决策过程效益高低的指标，它是一个定义在全过程或从k到n阶段的子过程上的函数，指标函数必须具有递推性。2.4逆序解法与顺序解法•动态规划有两种基本方法：逆序解法与顺序解法。•所谓逆序解法，是从问题的最后一个阶段开始，逆多阶段决策的实际过程反向寻优。•顺序解法则从问题的最初阶段开始，同多阶段决策的实际过程顺序寻优。•具体采取哪一种解法，应根据问题的初始条件和终端条件来决定。2.5动态规划模型的分类动态规划（按过程演变特征）确定性动态规划随机性动态规划动态规划（状态变量的取值）离散性动态规划连续性动态规划动态规划（阶段数是否固定）定期的决策过程不定期决策过程§3动态规划应用举例•资源分配问题•背包问题•生产与存贮问题•其它•某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工厂，各工厂获得此设备后，预测可创造的利润如下表所示，问应如何分配这5台设备给3个工厂，可使所创造利润最大？资源分配问题工厂设备台时甲乙丙000013542710639111141211125131112解：将问题按工厂分为三个阶段，甲、乙、丙三厂分别编号为1、2、3厂。设：sk=在第k阶段可供分配的机器台数(k=1,2,3)；或者说，分配给第k个厂至第三个厂的设备台数(k=1,2,3)。xk=分配给第k个工厂的设备台数。已知s1=5，并有s2=T1(s1,x1)=s1-x1，s3=T2(s2,x2)=s2-x2,从sk与xk的定义，可知s3=x3.采用逆序算法：第三阶段：•显然将s3(s3=0,1,2,3,4,5)台机器设备都分配给第3个工厂时，也就是s3=x3时，第三阶段的指标值（即第3厂的盈利）最大，即maxr3(s3,x3)=r3(s3,s3)由于第3阶段是最后的阶段，故有f3(s3)=maxr3(s3,x3)=r3(s3,s3)其中x3可能取值为0，1，2，3，4，5.其数值计算见下表：其中x3*表示第3子过程上最优指标值f3(s3)时的x3的决策即为最优决策。例如s3=4时,有r3(4,4)=12,有f3(4)=12,此时x3*=4,即为最优决策。x3s3r3(s3,x3)f3(s3)x3*01234500——————————001——4————————412————6——————623——————11————1134————————12——1245——————————12125第二阶段：•当把s2(s2=0,1,2,3,4,5)台设备分配给第2个工厂和第3个工厂时，则对每个s2值，有一种最优分配方案，使最大盈利即最优。2子过程最优指标函数值为：f2(s2)=max[r2(s2,x2)+f3(s3)]因为s3=s2-x2，上式也可以写成f2(s2)=max[r2(s2,x2)+f3(s2-x2)]其中，x2可取值0，1，2，3，4，5，其数值计算结果如下表：其中，在s2=4的这一行里，当x2=1时r2(s2,x2)+f3(s2-x2)=r2(4,1)+f3(4-1)=r2(4,1)+f(3)=5+11=16同样可知，当x2=2时，f2(s2)也等于16。故这一行的最优决策有两种。x2s2r2(s2,x2)+f3(s2-x2)f2(s2)x2*01234500+0——————————0010+45+0————————5120+65+410+0——————10230+115+610+411+0————14240+125+1110+611+411+0——161,250+125+1210+1111+611+411+0212第一阶段：•把s1(s1=5)台设备分配给第1，第2，第3厂时，最大盈利为f1(5)=max[r1(5,x1)+f2(5-x1)]其中x1可取值0，1，2，3，4，5。数值计算结果见下表：x1s1r1(5,x1)+f2(5-x1)f1(x)x1*01234550+213+167+149+1012+513+0210,2最终的最优分配结果有两个：•甲厂0台，乙厂2台，丙厂3台。•甲厂2台，乙厂2台，丙厂1台。•这两种分配方案都能得到最高的总盈利21万元。•某咨询公司有10个工作日可以去处理四种类型的咨询项目，每种类型的咨询项目中待处理的客户数量、处理每个客户所需的工作日数以及所获得的利润如下表所示。显然该公司在10天内不能处理完所有的客户，它可以自己挑选一些客户，其余的请其他咨询公司去做，该咨询公司应如何选择客户使得在这10个工作日中获利最大？背包问题背包问题是指在携带物品总重量一定的情况下，怎样将N种不同重量和不同价值的物品装入背包，使得背包所装物品的总价值最大？咨询项目类型待处理客户数处理每个客户所需工作日处理每个客户所获利润123443221347281120按照咨询类型将决策分为四个阶段，第一阶段处理第一种咨询类型的客户；第二、三、四阶段处理第二、三、四种咨询类型的客户。设：sk=分配给第k种咨询项目到第四种咨询项目的所有客户的总工作日（状态变量）；xk=在第k种咨询项目中处理客户的数量（决策变量）。•显然，s1=10,s2=T1(s1,x1)=s1-x1,s3=T2(s2,x2)=s2-3x2,s4=T3(s3,x3)=s3-4x3=7x4.第四阶段：s4=0,1,...,10,x4=[s4/7],中括号[]为取整符号，因为s4