运筹学.ppt

,动态规划 （dynamic programming）,第一节：动态规划的研究对象,1、动态系统： 包含随时间变化的因素和变量的系统。线性系统、非线性系统。 动态系统的特点：系统在某个时刻的状态，往往要依赖过去某些决策的影响，而系统的当前状态和决策又会影响系统过程今后的发展。 2、动态决策问题： 将时间作为决策变量之一的决策问题称为动态决策问题。 动态决策问题的特点：在动态决策问题中，系统所处的状态和时刻是进行决策的重要因素，即在系统发展的不同时刻（或阶段）根据系统所处的状态，不断地做出决策，找到不同时刻的的最优决策以及整个过程的最优策略。,3、多阶段决策问题： 多阶段决策过程是系统的动态过程可以按照时间进程分为状态相互联系而又相互区别的各个阶段，并且在每个阶段都要进行决策。目的是使整个过程的决策达到最优效果。,第二节：多阶段决策问题引例,1、生产决策问题：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。 2、机器负荷分配问题：某种机器可以在高低两种不同的负荷下进行生产。 在高负荷下生产时，产品的年产量g和投入生产的机器数量u1的关系为： g=g(u1) 这时，机器的年完好率为a，即如果年初完好机器的数量为u，到年终完 好的机器就为au, 0a1。 在低负荷下生产时，产品的年产量h和投入生产的机器数量u2的关系为： h=h(u2) 相应的机器年完好率b, 0 b1。 假定开始生产时完好的机器数量为s1。要求制定一个五年计划，在每年开 始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量， 使在五年内产品的总产量达到最高,3、航天飞机飞行控制问题：由于航天飞机的运动的环境是不断变化 的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决 定航天飞机的飞行方向（姿态）和速度，使之能最省燃料和实现 目的（如软着落问题）。 线性规划、非线性规划等静态的规划问题：可以通过适当地引 入阶段的概念，应用动态规划方法加以解决,。,5 最短路问题：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从a点到g点的最短距离（总费用最小）。,我们将用此例来说明所有动态规划问题的理论和方法。,第三节：动态规划的基本概念,1 阶段：将所给问题的过程，按时间或空间特征分解成若干互相联系 的阶段，用k表示， 2 状态：各阶段开始时的客观条件。状态变量用sk表示；状态变量集 合用sk表示。 性质：当某阶段状态给定以后，在这阶段以后的过成的发展 不受这段以前各状态的影响。 3 决策：当各阶段的状态确定以后，可以作出不同的选择，从而确定 下一阶段状态，这个选择称为决策。决策变量用uk(sk)表示 4 允许决策集合：决策变量的取值范围，用dk(sk)表示,5 策略：各阶段决策确定后，整个问题的决策序列就构成一 个策略。p1.nu1(s1),u2(s2),un(sn). 允许策略集合：可供选择的策略范围。p1.n 6 状态转移方程：由k阶段到k+1段的状态转移规律。 sk+1=tk(sk,uk) 7 指标函数：用于衡量所选定策略优劣的数量指标。 v1.n(s1,p1.n)表示初始状态为s1，采用策略p1.n 时原过程的指标函数值。 8 最优指标函数：从第k阶段状态sk，采用最优策略pk.n 到过 程终止时的最佳效益值。 fk(sk)=vk.n(sk,pk.n ) =opt vk.n(sk,pk.n ),第四节：动态规划的基本原理,1 基本原理： （1）划分阶段，选取变量，定义最优指标函数。 （2）从边界条件开始，逆过成行进方向逐段递推寻优。 （3）把当前效益和未来各段分开，又把当前效益与未来效益结合起来考虑。 2 基本方程：,3、bellmen 最优化原理： 一个过程的最优策略具有这样的性质：无论初始状态及初 始决策如何，对于先前决策所形成的状态而言，其以后的 所有决策应构成最优决策，,4、动态规划的两种解法： （1） 逆序解法：适用于初始状态给定的情况。 （2） 顺序解法：适用于终止状态给定的情况。,5、多阶段决策过程：就是可以在各个阶段进行决策，去控制过程发展的多段过程。多阶段决策过程的发展是通过一系列的状态转移来实现的，一般来说，系统在某一阶段的状态转移不但与系统的当前（或本阶段）的状态和决策有关，而且还与系统过去的历史状态和决策有关。其状态转移方程如下（一般形式）,图示如下：,状态转移方程是确定过程由一个状态到另一个状态的演变过程。如果第k阶段状态变量sk的值、该阶段的决策变量一经确定，第k+1阶段状态变量sk+1的值也就确定。,无后效性或马尔可夫性：如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响。换句话说，过程的过去历史只能通过当前的状态去影响它未来的发展。这个性质称谓无后效性。在构造决策过程的动态规划模型时，要充分注意是否满足无后效性的要求。如果状态不能满足无后效性的要求，应适当地改变状态的定义或规定方法，以使状态变量能满足无后效性的要求。 状态具有无后效性的多阶段决策过程的状态转移方程如下,能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即具有无后效性的多阶段决策过程。,动态规划中能 处理的状态转移 方程的形式。,多阶段决策过程的数学模型：（具有无后效性的多阶段决策过程）,所谓求解多阶段决策过程问题，就是要求出 （1） 最优策略，即最优决策序列,（2） 最优轨线，即执行最优策略时的状态序列,（3）最优目标函数值,f1(s1),从k到终点最优策略 子策略的最优目标函数值,第五节：动态规划的基本思想和基本方程,以最短路问题的解法为例来说明。（穷举法48条路线）,最短路的特性：如果已有从起点到终点的一条最短路，那么从最短路线上中间任何一点出发到终点的路线仍然是最短路。（证明用反证法）,当k=6时,由f1到终点g只有一条路线，故f6(f1)=4.同理，f6(f2)=3. 当k=5时，出发点有e1,e2,e3三个。,当k=4时，有,当k=3时，有,当k=2时，有,当k=1时，有,且u1(a)=b1，于是得到从起点a到终点g的最短距离为18。 为了找到最短路线,在按计算的顺序反推之,可求出最优决策函数序列 uk：u1(a)=b1,u2(b1)=c2,u3=(c2)=d1,u4(d1)=e2, u5(e2)=f2,u6(f2)=g，即最优策略。 最短路线为ab1c2d1e2f2g。,动态规划（逆序法求解的）基本特性： （1）将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数，正确写出基本的递推关系式和恰当的边界条件（简言之为基本方程）。从而把问题化成一族同类的子问题， （2）求解时从边界条件开始，逆（或顺）过程行进方向，逐段递推寻优。在每个问题求解时，都要使用它前面已求出的子问题的最优结果，最后问题的最优解，就是整个问题的最优解。 （3）动态规划方法是既把当前一段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。每段决策的选取都是从全局考虑的，与该段的最优选择答案一般是不同的。 （4）在求整个问题的最优策略时，由于初始状态是已知的，每段的决策是该段状态的函数，故沿最优化策略所经过的各段状态便可确定了最优路线。,（5）求解的各个阶段,我们利用了k阶段与k+1阶段之间的递推关系:,练习：写出乘积形式指标函数的动态规划基本方程。,用动态规划求解时的几点注意：,（1）将问题的过程划分成恰当的阶段； （2）正确选择状态变量sk,使它既是能描述过程的变量，又要满足无后效应； （3）确定决策变量uk及每一阶段的允许决策集合dk(sk)； （4）正确写出状态转移方程； （5）正确写出指标函数vk,n的关系，它应满足下面两个性质： a)是定义在全过程和所有后部子过程上的数量函数； b)要具有可分离性，并满足递推关系。即,例题：已知图中数字表示节点间的距离，求节点a到g的最短路。,a,b,c,d,e,f,g,3,2 2 1 3 4,1 4 1 2,5,首先需要把问题划分为n个阶段。 方法：1 划分为“步” 2 增加虚节点化分为阶段。,a,b,c,d,e,f,g,2 2 1 3 4,1 2,0 0 5,b1,c1,c2,d1,e1,f,0 3 0,4,1,0,应用动态规划方法求解。,第六节：动态规划与静态规划之间的关系及其它相关总结,6.1 逆序（递推）法,设已知初始状态s1，最优值函数fk(sk)表示从k阶段到n阶段所得到的最大效益。以求最大化为例来说明。,具体方法如下： 当阶段k=n时,可得最优决策xn=xn(sn)和最优值fn(sn)。要注意的是,若d(sn)只有一个决策,则可写成 xn=xn(sn)。,当阶段k=n-1时,其中状态转移方程,得到最优决策xn-1=xn-1(sn-1)和最优值fn-1(sn-1)。,当阶段k=k时,其中状态转移方程,得最优决策xk=xk(sk)和最优值fk(sk)。 如此类推，直到第一阶段。,当阶段k=1时,其中状态转移方程,得最优决策x1=x1(s1)和最优值f1(s1)。,由于初始状态s1已知,故x1=x1(s1)和f1(s1)是确定的,根据状态转移方程按照上述递推过程相反顺序推算下去，就可逐步确定出每阶段的决策及效益。,例1 用动态规划的逆序法求解下面问题,解： 分阶段：（考虑效益函数的形式）分三个阶段，即k=1，2，3。 确定决策变量：通常可以取静态规划中的变量为决策变量。 确定状态变量：状态变量与决策变量有密切关系，状态变量一般为累计量或随递推过程变化的量。 此问题中可设（因此可得状态转移方程）：,则有,指标函数,最优指标函数fk(sk),可以想象成投资问题,基本方程,当阶段k=3时，有,最优决策,当阶段k=2时，有,有两个解，其中x2=0舍去。 因2阶导数在x*2处小于0，故有极大值。,当阶段k=1时，有,因此最后可得：,与前面一样 用微分法。,s3=s2-x*2=s1- x*1- x*2,6.2 顺序解法 自学内容,6.3 动态规划的优缺点,优点 最优解是全局最优解。 能得到一系列（包括子过程）的最优解。 不需要对系统状态转移方程、阶段效应函数等的解析性质作任何假设。,缺点： 没有统一的标准模型和标准的算法可供使用。 应用的局限性，要求满足“无后效性”。 “维数灾难”问题。,第七章：动态规划应用举例,建立动态规划模型的一般步骤： 1 划分阶段。即按时间和空间的先后顺序适当地划分为满足递推关系的若干个阶段。 2 正确选择状态变量。（可知性和无后效性） 3 根据状态变量和决策变量的含义，正确写出状态转移方程 sk+1=tk(sk,uk) 4 明确指标函数vk.n、最优指标函数fk(sk)及k阶段指标vk(sk,us)的含义。 5 正确列出最优指标函数的递推关系及边界条件。,所谓分配问题，就是将数量一定的一种或若干种资源（例如原材料，资金，机器设备，劳力，食品等等），恰当地分配给若干个使用者，使效益函数为最优。,1.1 多元投资分配问题(离散） 设有某种原料，总数量为a，用于生产n种产品。若分配数量xi用于生产第i种产品，其收益为gi(xi),问应如何分配，才能使生产n种产品的总收入最大？,静态规划,第一节：资源分配问题,决策变量uk表示分配给生产第k种产品的原料数量，即uk=xk； 设状态变量sk表示为分配给用于生产第k种产品至第n种产品的原料数量； 状态转移方程： sk+1=sk-uk=sk-xk 决策集合：dk(sk)=uk|0uk=xksk 最优值函数fk(sk)表示以数量为sk的原料分配给第k种产品至第n种产品所得到的最大总收益，动态规划的递推关系为：,动态规划 五要素,直接求解动态规划 求解静态规划,例1 某公司有资金10万元，若投资于项目i（i=1，2，3）的投资额为xi时，其效益分别为 ，问如何分配投资数额才能使总效益最大,解：可列出静态规划问题的模型如下,分阶段：（考虑效益函数的形式）分三个阶段，即k=1，2，3。 确定决策变量x k：通常可以取静态规划中的变量为决策变量，即决 定给第 k个项目投资的资金数。 确定状态变量s k：状态变量与决策变量有密切关系，状态变量一般为累计量或随递推过程变化的量。既第k阶段可以投资于第k项到第3项目的资金数量。,指标函数,最优指标函数fk(sk):当可投资金额为sk时，投资第k项到第3项所得的最大收益数。,基本方程,当阶段k=3时，有,sk+1=sk-xk,当阶段k=2时，有,是凹函数，最大值点只能在0，s2端点上取得，即,当阶段k=1时，有,2阶导数大于0,最优投资方案是全部资金投于第3个项目，可得最大收益200万元。,s29/2,s29/2,2阶导数0,例2 某大型公司拟将某种高效率的设备5台分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为公司提供的盈利如表。问这五台设备如何分配给各工厂，才能使公司得到的盈利最大。,解：将问题按工厂分为三个阶段，甲、乙、丙分别编号为1，2，3。用k表示，即阶段变量 决策变量uk表示分配给第k个工厂的设备台数，即uk=xk； 设状态变量sk表示为分配给第k个工厂至第3工厂的设备台数； 状态转移方程： sk+1=sk-uk=sk-xk 决策集合：dk(sk)=uk|0uk=xksk 最优值函数fk(sk)表示以数量为sk的设备台数分配给第k个工厂至第n个工厂所得到的最大总收益，动态规划的递推关系为：,即：（用逆推法） 当阶段k=3时，0s35， 0x3s3，有,x3(s3),结果列于下表：,当阶段k=2时， s3=s2-x2， 0s25， 0x2s2，有,结果列于下表：,当阶段k=1时， s2=s1-x1， s1=5， 0x1s1，有,结果可写成表格的形式,然后按计算表格的顺序反推，可知最优分配方案有两个： 由于x1*=0，根据s2=s1-x1*=5-0=5，查表知x2*=2，由s3=s2-x2*=5-2=3，故x3*=s3=3。即得甲工厂分配0台，乙工厂分配2台，丙工厂分配3台。 由于x1*=2，根据s2=s1-x1*=5-2=3，查表知x2*=2，由s3=s2-x2*=3-2=1，故x3*=s3=1。即得甲工厂分配2台，乙工厂分配2台，丙工厂分配1台。 以上两个分配方案所得到的总盈利均为21万元。,问题：如果原设备台数是4台，求最优分配方案？ 如果原设备台数是3台，求最优分配方案？,1.2 资源连续分配问题: 一般问题的提法是,如此进行n年，如何确定投入a的资源量u1、un，使总收入最大？,此问题的静态规划问题模型为：,。,设sk为状态变量，它表示在第k阶段（第k年）可投入a、b两种生产的资源量； uk为决策变量，它表示在第k阶段（第k年）用于a生产的资源量，则sk-uk表示用于b生产的资源量； 状态转移方程为：s k+1=auk+b(sk-uk) 最优值函数fk(sk)表示有资源量sk从第 k阶段至第n阶段采取最优分配方案进行生产后所得到的最大总收入。 动态规划的逆推关系方程为：,最后求得的f1(s1)即为所求问题的最大收入,例3 机器负荷分配问题 某种机器可在高低两种不同负荷下进行生产，设机器在高负荷情况下的产量函数为g=8u1，其中u1是投入生产的机器数量，年完好率为 a=0.7，在低负荷情况下的产量函数为h=5y，其中y是投入生产的机器数量，年完好率为b=0.9。假定开始生产时完好机器的数量为1000台，试问每年如何安排机器在高低两种负荷下的生产，可使5年内生产的产品总产量最高。, 允许决策集合0uksk,解： 设阶段数k表示年度。 状态变量sk为第k年度初拥有的完好机器台数。 决策变量uk为第k年度中分配高负荷下生产的机器台数。故低负荷下生产的机器台数是sk-uk。 状态转移方程,第k年度产量为,指标函数为,递推方程为,依次类推可得，,因为s1=1000，所以f1(s1)=23700,即前两年应在年初把全部完好的机器投入低负荷生产，后三年应在年初把全部完好的机器投入高负荷生产。最高产量为23700（台）。,每年年初的机器状态：s1=1000 s2=0.7u1+0.9(s1-u1)=0.9s1=900 s3= 0.7u2+0.9(s2-u2)=0.9s2=810 s4= 0.7u3+0.9(s3-u3)=0.7s3=567 s5= 0.7u4+0.9(s4-u4)=0.7s4=397 s6= 0.7u5+0.9(s5-u5)=0.7s5=278,练习：每年年初的完好机器数。 作业：如规定在第五年结束时完好机器数为500台，该如何安排生产？,第二节 生产与存贮问题,所谓生产与库存问题就是一个生产部门，如何在已知生产成本、库存费用和各阶段市场需求条件下，决定各阶段产量，使计划内的费用总和为最小的问题。很多问题可以化成此类问题来解决。 生产与库存问题本身就是一个多阶段决策过程。设某一生产部门，生产周期分为n个阶段， 已知最初库存量为x1， 阶段市场的需求为dk， 生产的固定成本为k， 单位产品的消耗费用为l， 单位产品的阶段库存费用为h， 仓库容量为m， 阶段最大生产能力为b。 问如何安排各阶段产量，使计划周期内的费用总和最小。,状态变量xk选为阶段k的初始库存量，x1已知，xn+1=0。 阶段k的库存量即不能超过库存容量m，也不能超过阶段k至阶段n的需求总量(因为n+1阶段的库存量为0），即,决策变量uk选为阶段k的产量。阶段产量必须不超过生产能力和第k阶段到第n阶段的总需求减去第k阶段初的库存量，同时要大于该阶段的需求和库存量之差，即,状态转移方程为,阶段效益为阶段生产费用和库存费用之和，即,阶段k的生产费用,k阶段末的库存费用,动态规划基本方程,例 已知n=3，k=8，l=2，h=2，x1=1，m=4，x4=0（计划周期末期的库存量为0），b=6，d1=3，d2=4，d3=3，求解生产与库存问题。 解：利用上述的递推方程得,若,若,则,则,结果见下表：,时,是唯一确定的，因此,最优决策为,最优路线为 1，0，0，0 最优目标函数值为42。,第三节：设备更新问题 个人、单位等随时均有设备更新问题。自行车、彩电、设备随着使用年限的增加而设备陈旧，处理价格愈低，因此需要维修和更新的费用增加。处于各种阶段的设备总是面临保留还是更新问题。保留还是更新，应该从整个计划期间的总回收额来考虑，而不能从局部的某个阶段的回收额来考虑，是一个多阶段的决策问题。,设备更新问题提法如下（以一台机器为例）： n为计划设备使用年数。 ik(t) 为第k年（阶段）已经使用过t年的机器再使用一年所得的收入。 ok(t) 为第k年已经使用过t年的机器再使用一年的维修费用 。 ck(t) 为第k年卖掉一台已经使用过t年的机器，买进一台新设备的更新净费用。,建立动态规划模型如下： 阶段k（k=1，2，n）表示计划使用该设备的年限数。 状态变量sk：第k年初，设备已使用过的年数。 决策变量xk：是第k年初更新（replacement），还是保留使用（keep）旧设备，分别用k，r表示。 状态转移方程为：,阶段效益为：,为折扣因子，表示一年以后的收入是上一年的单位。 要求在n年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使n年内总效益最大？,最优指标函数fk(sk)：表示第k年初，使用一台已用了sk年的设备，到第n年末的最大收益，动态规划的基本方程为,实际上,例：设某台新设备的年效益及年均维修费用、更新净费用如下表，试确定今后五年内的更新策略，使总效益最大。（设=1）,（单位：万元）,解：n=5,状态变量s5可取1，2，3，4,卖掉役龄2年的设备，买入新设备的更新费用,状态变量s4可取1，2，3,此时s3可取1或2,由于状态s2只能取1，所以有,由于状态s1只能取0，所以有,上述过程递推回去，当x*1(0)=k，由状态转移方程,本例的最优策略是k，r，r，r，k，即第一年初购买的设备到第二、三、四年初各更换一次，用到第五年年末，总效益为17万元。,s2=1，查f2(1)得x*2=r,s3=1，查f3(1)得x*3=r,s4=1，查f4(1)得x*4=r,s5=1，查f5(1)得x*5=k,动态规划总结,一、动态规划基本概念： 1 阶段：将所给问题的过程，按时间或空间特征分解成若干互 相联系的阶段，用k表示， 2 状态：各阶段开始时的客观条件。 状态变量用sk表示。 状态变量集合用sk表示。 性质：当某阶段状态给定以后，在这阶段以后的过 成的发展不受这段以前各状态的影响。,3 决策：当各阶段的状态确定以后，可以作出不同的选择，从 而确定下一阶段的状态。这个选择称为决策。 决策变量:uk(sk) 允许决策集合：决策变量的取值范围，用dk(sk)表示 4 策略：各阶段决策确定后，整个问题的决策序列就构成一 个策略。p1.nu1(s1),u2(s2),un(sn). 允许策略集合：可供选择的策略范围。p1.n 5 状态转移方程：由k阶段到k+1段的状态转移规律。 sk+1=tk(sk,uk),6 指标函数：用于衡量所选定策略优劣的数量指标。 v1.n(s1,p1.n)表示初始状态为s1，采用策略p1.n 时原过程的指标函数值。 7 最优指标函数：从第k阶段状态sk，采用最优策略pk.n 到过 程终止时的最佳效益值。 fk(sk)=vk.n(sk,pk.n ) =opt vk.n(sk,pk.n ),二、动态规划基本原理 bellmen 最优化原理： 一个过程的最优策略具有这样的性质：无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优决策，,三、动态规划的基本思想 （1）划分阶段，选取变量，定义最优指标函数。 （2）从边界条件开始，逆过成行进方向逐段递推寻优。 （3）把当前效益和未来各段分开，又把当前效益与未来效 益结合起来考虑。,四、动态规划的 基本解法 1 逆序解法：适用于初始状态给定的情况。 2 顺序解法：适用于终止状态给定的情况。,五、动态规划基本方程,六、动态规划模型的建立要点 1 划分满足递推关系的若干阶段 2 正确选择状态变量、决策变量（可知性和无后效性） 3 正确写出状态转移方程 sk+1=tk(sk,uk) 4 确定指标函数vk n,和最优指标函数fk(sk) 5 列出基本方程，确定边界条件。,七、几个典型示例动态规划模型的建立,最短路问题 阶段k：整体路线上的段数 状态变量sk