《动态规划h运筹学.ppt》由会员分享，可在线阅读，更多相关《动态规划h运筹学.ppt（59页珍藏版）》请在三一办公上搜索。
1、第七章 动态规划,动态规划是运筹学的一个重要分支，它是从1951年开始，由美国人贝克曼为首的一个学派发展起来的，动态规划在经济、管理、军事、工程技术等方面都有广泛的应用。动态规划是解决多阶段决策过程的最优化问题的一种方法。所谓多阶段决策过程是指这样一类决策过程：它可以把一个复杂问题按时间（空间）分成若干个阶段，每个阶段都要作出决策，以便得到过程的最优结局。由于在每个阶段采取的决策是与时间有关的而且前一阶段采取的决策如何，不但与该阶段的经济效果有关，还影响以后的各阶段的经济效果。可见，这类多阶段决策问题是一个动态问题。因此，处理的方法称为动态规划方法。然而，动态规划也可以处理一些本来与时间无关的
2、静态模型，这只需要在静态模型中人为引入“时间”因素，分成时段，就可以把它看作是多阶段的动态模型，用动态规划方法来处理。动态规划解决多阶段决策问题的效果是明显的，但也有一定的局限性，首先，它没有统一的处理方法；另外当变量的维数增大时，有“维数障碍”问题。,在研究经济、经营管理和工程技术领域内的有关问题中，有一类特殊形式的动态决策问题多阶段决策问题。在多阶段决策过程中，系统的动态过程可以按照时间进程分为相互联系而又相互区别的各个阶段，在每个阶段都需要进行决策，系统在每个阶段存在许多不同的状态，在某个时间的状态往往要依某种形式受到过去某些决策的影响，而系统的当前状态和决策又会影响系统过程的今后的发展
3、，因而在寻求多阶段决策问题的最优解时，重要的是不能从眼前的局部利益出发进行决策而需要从系统所经过的整个期间的总效益出发，有预见性进行动态决策，找到不同时点的最优决策及整个过程的最优策略。,第一节 多阶段决策问题,例7.1 最短路问题如图所示，要从A地到E地铺设管线，中间需要经过三个中间站，两点之间的连线上的数字表示距离，问应该选择什么路线，使总距离最短？,例7-2 机器负荷问题某工厂有100台机器，拟分四个周期使用，在每一个周期有两种生产任务。据经验，把机器x1台投入第一种生产任务，则在一个生产周期中将有1/3x1台机器报废；余下的机器全部投入第二种生产任务，则有1/10的机器报废，如果干第一
4、种生产任务每台机器可以收益10，干第二种生产任务每台机器可以收益7，问怎样分配机器使总收益最大？例7-3 资源分配问题假设有一种资源其数量为a，现将它分配给n个使用者。若分配给第i个使用者的数量为xi（i=1，n），产生的相应收益为gi（xi），问如何分配使总收益最大？投资决策问题、生产存贮问题、采购问题、设备更新问题等都具有多阶段决策问题的特征，都可以用动态规划方法求解。,第二节 动态规划的基本概念和基本原理一、动态规划的基本概念1.阶段（stage）动态规划通常都具有时间或空间上的次序性，因此，求解这类问题时，首先要将问题按一定次序划分为若干个相互联系的阶段，以便能按一定次序求解。描述阶段
5、的变量称为阶段变量（k）k=1，AB；k=2，BC；k=3，CD；k=4，DE。,2.状态（state）在多阶段决策过程中，每个阶段都要进行决策，而决策是根据系统所处情况决定的。状态表示各阶段开始所处的自然状况或客观条件，它既是某阶段过程演变的起点，又是前一阶段某种决策的结果。描述状态的变量称为状态变量()。状态变量 的取值集合称为状态集合，第k阶段的状态集合记为，,状态的选取应当满足无后效性：系统从某个阶段往后的发展演变，完全由系统本阶段所处的状态及决策所决定，与系统以前的状态及决策无关。也就是说，过去的历史只能通过当前的状态去影响未来的发展，当前的状态是过去历史的一个完整总结。只有具有无后
6、效性的多阶段决策过程才适合于用动态规划方法求解。,各阶段状态集合分别为：S1=AS2=B1，B2，B3S3=C1，C2，C3，C4S4=D1，D2,3.决策（decision）当各阶段的状态选定以后可以做出不同的决定（或选择）从而确定下一个阶段的状态，这种决定（或选择）称为决策。表述决策的变量称为决策变量，常用uk（sk）表示第k阶段当状态为sk时的决策变量。实际问题中，决策变量的取值往往限制在某一范围内，此范围称为允许决策集合，常用Dk（sk）表示第k阶段从状态sk出发的允许决策集合，uk（sk）Dk（sk）。从B2出发，可以选择C1，C2，C3，C4，即允许决策集合为：D2（B2）=C1，
7、C2，C3，C4当决定选择C3时，可以表示为：u2（B2）=C3,4.策略（policy）当各个阶段的决策确定以后，各阶段的决策形成一个决策序列，称此决策序列为一个策略.使系统达到最优效果的策略称为最优策略。在n阶段决策过程中，从第k阶段到终止状态的过程，称为k后部子过程（或称为k子过程），k后部子过程相应的决策序列称为k后部子过程策略，简称子策略，记为pk，n（sk）：pk，n（sk）=uk（sk），uk+1（sk+1），un（sn）当k=1时，即由第一阶段某个状态出发做出的决策序列称为全过程策略，简称策略，记为p1，n（s1）：p1，n（s1）=u1（s1），u2（s2），un（sn）,5
8、.状态转移方程（state transfer equation）设第k阶段状态为sk，做出的决策为uk（sk），则第k+1阶段的状态sk+1随之确定，他们之间的关系可以表示为：sk+1=Tk（sk，uk）表示从第k阶段到第k+1阶段状态转移规律的方程称为状态转移方程，它反映了系统状态转移的递推规律。,状态转移方程为：sk+1=uk（sk）,6.指标函数和最优指标函数衡量所选策略优劣的数量指标称为指标函数。它定义在全过程和所有后部子过程，常用Vk，n表示，即：Vk，n=Vk，n（sk，uk，sk+1，sn+1）当k=1时，V1，n表示初始状态为s1，采用策略p1，n时的指标函数值。V1，n=V1
9、，n（s1，u1，s2，sn+1）动态规划数学模型的指标函数应该具有可分离性，并满足递推关系，即：Vk，n（sk，uk，sk+1,sn+1）=ksk，uk，Vk+1，n(sk+1,sn+1)在阶段k状态为sk，决策为uk（sk）时得到的反映第k阶段的数量指标vk（sk，uk）称为k阶段的指标函数。在最短路线问题中，第k阶段指标函数vk（sk，uk）通常也用dk（sk，uk）表示。,常见的指标函数形式有两种：（1）任一后部子过程的指标函数是它所包含的各阶段指标的和，即：Vk，n（sk，uk，sn+1）=写成递推关系：Vk，n（sk，uk，sn+1）=vk（sk，uk）+Vk+1，n（sk+1，u
10、k+1，sn+1）（2）任一后部子过程的指标函数是它所包含的各阶段指标的积，即：Vk，n（sk，uk，sn+1）=写成递推关系：Vk，n（sk，uk，sn+1）=vk（sk，uk）Vk+1，n（sk+1，uk+1，sn+1）,指标函数的最优值记为fk（sk），它表示从第k阶段状态sk出发，采取最优策略p*k，n（sk）到第n阶段的终止状态时的最佳指标函数值，即：当k=1时，f1（s1）就是从初始状态s1出发到终止状态的最优函数。,A,B,C,二、动态规划的基本思想与基本原理,k=4时，状态变量s4可取两种状态D1，D2：f4（D1）=d4（D1，E）=3u4（D1）=Ef4（D2）=d4（D2
11、，E）=5u4（D2）=E,u3（C1）=D1,k=3时，状态变量s3可取四种状态C1，C2，C3，C4，当s3=C1时，,f3（C4）=d3（C4，D2）+f4（D2）=7+5=12 u3（C4）=D2,同理，从C2，C3，C4出发，有：,u3（C2）=D2,u3（C3）=D1,k=2时，,u2（B1）=C1,u2（B2）=C3,u2（B3）=C3,按计算顺序反向追踪，得到最优决策序列uku1（A）=B3，u2（B3）=C3，u3（C3）=D1，u4（D1）=E；最优路线为：AB3C3D1E。,k=1时，有：,u1（A）=B3,或f4（s4）=d4（s4，E）,从后向前标号：,从前向后标号：
12、,最优性原理：“作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略。”简言之：最优策略的任何一部分子策略也必须是最优的。,例、已知网络各段路线所需费用如图所示，选择从A线到B线最小费用路线，并计算总费用。,动态规划的基本思想：1、将多阶段决策问题按照空间或时间顺序划分成相互联系的阶段，即把一个大问题分解成一族同类型的子问题，选取恰当的状态变量和决策变量，写出状态转移方程，定义最优指标函数，写出递推关系式和边界条件。2、从边界条件开始，由后向前逐段递推寻找最优，在每一个阶段的计算中都要用到前一阶段的最优结果，依次进行
13、，求得最后一个子问题的最优解就是整个问题的最优解。3、在多阶段决策过程中，确定阶段k的最优决策时，不是只考虑本阶段最优，而是要考虑本阶段及其所有后部子过程的整体最优，也就是说，它是把当前效益和未来效益结合起来考虑的一种方法。,第三节 动态规划模型及求解方法一、动态规划的数学模型,2.建立动态规划模型的步骤（1）划分阶段（2）正确选择状态变量sk（描述演变特性、无后效性、递推性）（3）确定决策变量uk及允许决策集合Dk（sk）（4）确定状态转移方程sk+1=Tk（sk，uk）（5）确定阶段指标函数和最优指标函数（6）建立动态规划基本方程。,二、动态规划的求解方法例7.4 用动态规划方法解下列非线
14、性规划问题,解按问题的变量个数划分阶段，k=1，2，3设状态变量为s1，s2，s3，s4并记s1c取问题中的变量x1，x2，x3为决策变量状态转移方程为：s3=x3s3+x2=s2s2+x1=s1c允许决策集合为：x3=s30 x2s20 x1s1阶段指标函数为：v1（x1）=x1 v2（x2）=x22 v3（x3）=x3最优指标函数fk（sk）表示从第k阶段初始状态sk出发到第3阶段所得到的最大值，则动态规划基本方程为：,k=3时，,k=2时，,x3*=s3,令h2（s2，x2）=x22（s2x2）,解得：,x2=0（舍）,是极大值点。,k=1时，,令,是极大值点。,反向追踪得各阶段最优决策
15、及最优值：,第四节 动态规划的应用举例一、资源分配问题假设有一种资源，数量为a，将其分配给n个使用者，分配给第i个使用者数量xi时，相应的收益为gi（xi），问如何分配使得总收入最大？数学模型为：,解：按变量个数划分阶段，k=1，2，n；设决策变量uk=xk，表示分配给第k个使用者的资源数量；设状态变量为sk，表示分配给第k个至第n个使用者总的资源数量；状态转移方程：sk+1=skxk，其中s1=a；允许决策集合：Dk（sk）=xk|0 xksk阶段指标函数：vk（sk，uk）=gk（xk）表示分配给第k个使用者数量xk时的收益；最优指标函数fk（sk）表示以数量sk的资源分配给第k个至第n个
16、使用者所得到的最大收益，则动态规划基本方程为：,例7.7 某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表所示。试问在各地区如何设置销售点可使每月总利润最大。,解：将问题分为3个阶段，k=1，2，3；决策变量xk表示分配给第k个地区的销售点数；状态变量为sk表示分配给第k个至第3个地区的销售点总数；状态转移方程：sk+1=skxk，其中s1=4；允许决策集合：Dk（sk）=xk|0 xksk阶段指标函数：gk（xk）表示xk个销售点分配给第k个地区所获得的利润；最优指标函数fk（sk）表示将数量为sk的销售点分配给第k个至第3个地区
17、所得到的最大利润，动态规划基本方程为：,k=3时，,k=2时，,k=1时，,最优解为：x1*=2，x2*=1，x3*=1，f1(4)=47，即在第1个地区设置2个销售点，第2个地区设置1个销售点，第3个地区设置1个销售点，每月可获利润47。,例7.8 机器负荷问题某工厂有100台机器，拟分四期使用，每一期都可在高、低两种不同负荷下进行生产。若把x台机器投入高负荷下进行生产，则在本期结束时将有1/3x台机器损坏报废；余下的机器全部投入低负荷下进行生产，则在期末有1/10的机器报废。如果高负荷下生产时每台机器可获利润为10，低负荷下生产时每台机器可获利润为7，问怎样分配机器使四期的总利润最大？,解
18、 将问题按周期分为4个阶段，k=1，2，3，4；状态变量sk表示第k阶段初完好的机器数，s1=100，0sk100；决策变量xk表示第k阶段投入高负荷下生产的机器数，则skxk表示第k阶段投入低负荷下生产的机器数；允许决策集合：Dk（sk）=xk|0 xksk状态转移方程：sk+1=Tk（sk，xk），第k+1阶段初拥有的完好机器数sk+1为：,阶段指标函数：vk（sk，xk）=10 xk+7（skxk）表示第k阶段所获得的利润；最优指标函数fk（sk）表示从第k阶段初完好机器数为sk至第四阶段的最大利润，动态规划基本方程为：,k=4时，,x4*=s4,k=3时，,x3*=s3,k=2时，,k
19、=1时，,x2*=0,x1*=0,因为s1=100，所以f1（100）=2680，逆向追踪得：,第1，2期把全部完好机器投入低负荷下生产，第3，4期把全部完好机器投入高负荷下生产所得利润最大。,二、生产计划问题例7.9（生产库存问题）某工厂要对一种产品制定今后四个时期的生产计划，据估计在今后四个时期内，市场对该产品的需求量分别为2，3，2，4单位，假设每批产品固定成本为3千元，若不生产为0，每单位产品成本为1千元，每个时期最大生产能力不超过6个单位，每期期末未出售产品，每单位需付存贮费0.5千元，假定第1期初和第4期末库存量均为0，问该厂如何安排生产与库存，可在满足市场需求的前提下总成本最小。
20、,解 以每个时期作为一个阶段，k=1，2，3，4；决策变量xk表示第k阶段生产的产品数；状态变量sk表示第k阶段初的库存量；以dk表示第k阶段的需求，则状态转移方程：sk+1=sk+xkdk k=4，3，2，1s1=0，s5=0；允许决策集合Dk（sk）的确定：xk的下限为max（0，dksk）；xk的上限为min（，6），故有：,Dk（sk）=xk|max（0，dksk）xkmin（，6）,阶段指标函数rk（sk，xk）表示第k期的生产费用与存贮费用之和：,最优指标函数fk（sk）表示第k期库存为sk到第4期末的生产与存贮最低费用，动态规划基本方程为：,Dk（sk）=xk|max（0，dks
21、k）xkmin（，6）,例7-9（库存销售问题）设某公司计划在1至4月份从事某种商品经营。已知仓库最多可存储600件这种商品，已知1月初存货200件，根据预测知1至4月份各月的单位购货成本及销售价格如表7-13所示，每月只能销售本月初的库存，当月进货供以后各月销售，问如何安排进货量和销售量，使该公司四个月获得利润最大（假设四月底库存为零）。,解 按月份划分阶段，k=1，2，3，4；状态变量sk表示第k月初的库存量，s1=200，s5=0；决策变量 xk表示第k月售出的货物数量，yk表示第k月购进的货物数量；状态转移方程：sk+1=sk+ykxk；允许决策集合：0 xksk，0yk600（skx
22、k）；阶段指标函数为：pkxkckyk表示k月份的利润，其中pk为第k月份的单位销售价格，ck为第k月份的单位购货成本；最优指标函数fk（sk）表示第k月初库存为sk时从第k月至第4月末的最大利润，则动态规划基本方程为：,k=4时，,x4*=s4y4*=0,k=3时，,k=2时，,类似地求得：x2*=s2，y2*=600，f2（s2）=42s2+3600,k=1时，,类似地求得：x1*=s1，y1*=600，f1（s1）=45s1+4800=13800,逆向追踪得各月最优购货量及销售量：x1*=s1=200y1*=600；x2*=s2=s1+y1*x1*=600y2*=600；x3*=0y3*
23、=600s3=0 x4*=s4=（s3+y3*x3*）=600y4*=0即1月份销售200件，进货600件，2月份销售600件，进货600件，3月份销售量及进货量均为0，4月份销售600件，不进货，可获得最大总利润13800。,三、背包问题有人携带背包上山，其可携带物品的重量限度为a公斤，现有n种物品可供选择，设第i种物品的单件重量为ai公斤，其在上山过程中的价值是携带数量xi的函数ci（xi），问应如何安排携带各种物品的数量，使总价值最大。数学模型为：,按照装入物品的种类划分阶段，k=1，2，n；状态变量sk表示装入第k种至第n种物品的总重量；决策变量xk表示装入第k种物品的件数；状态转移方
24、程为：sk+1=skakxk允许决策集合为：其中 表示不超过 的最大整数；阶段指标函数ck（xk）表示第k阶段装入第k种商品xk件时的价值；最优指标函数fk（sk）表示第k阶段装入物品总重量为sk时的最大价值，动态规划基本方程为：,例7.11 某工厂生产三种产品，各产品重量与利润关系如表所示，现将此三种产品运往市场销售，运输能力总重量不超过6吨，问如何安排运输使总利润最大？,解 设xi为装载第i种货物的件数，i=1，2，3该问题数学模型为：,k=3时，,k=2时，,k=1时，,四、复合系统工作可靠性问题设第i（i=1，2，n）个部件上装有ui个备用元件，正常工作的概率为pi（ui），则整个系统
25、正常工作的可靠性为装第i个部件的费用为ci，重量为wi，要求总费用不超过c，总重量不超过w。,数学模型为：,按部件个数划分阶段，k=1，2，n；决策变量uk表示部件k上的备用元件数；状态变量xk表示从第k个到第n个部件的总费用，yk表示从第k个到第n个部件的总重量；状态转移方程为：xk+1=xkckukyk+1=ykwkuk允许决策集合为：阶段指标函数为pk（uk），表示第k个部件正常工作概率；最优指标函数fk（xk，yk）表示由状态xk，yk出发，从部件k到部件n的系统工作最大可靠性，则动态规划基本方程为：,例7.12 某厂设计的一种电子设备由三种元件A、B、C串联而成，已知三种元件的价格及可靠性如表所示，要求设计中使用元件的总费用不超过10万元，问如何设计使设备的可靠性达到最大（不考虑重量限制）。,解 如前所述建立动态规划数学模型；按元件种类划分为3个阶段，k=1，2，3；决策变量xk表示第k个部件配备的元件数；状态变量sk表示从第k阶段到第3阶段配备元件的总费用；状态转移方程为：sk+1=skckxk其中ck表示第k种部件的元件单价；允许决策集合为：以pk表示第k个部件中的1个元件的正常工作概率，假定部件k的xk个元件是并联的，则xk个元件均不正常工作的概率为fk（sk）表示由状态sk开始从第k个到第3个部件的设备最大可靠性。,k=3时，,k=2时，,k=1时，,
