《动态规划的建模与求解经典运筹学.ppt》由会员分享，可在线阅读，更多相关《动态规划的建模与求解经典运筹学.ppt（26页珍藏版）》请在三一办公上搜索。
1、4.3 动态规划的 建模与求解,4.3.1 建摸,1、理论依据,-最优化原理,最优化原理：一个过程的最优策略具有这样的性质，即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策必构成最优策略,2、动态规划模型的几个要素：,1)阶段数k,2)状态变量sk,3)决策变量uk（sk）,4)指标函数Vk,n,状态转移方程,5)最优值函数fk(sk),3、建立动态规划模型的基本要求：,1）所研究的问题必须能够分成几个相互联系的阶段，而且在每一个阶段都具有需要进行决策的问题。,2）在每一阶段都必须有若干个与该阶段相关的状态,一般情况下，状态是所研究系统在该阶段可能处于的情况或条件,
2、建模时总是从与决策有关的条件中，或是从问题的约束条件中去选择状态变量。,3)具有明确的指标函数，且阶段指标值可以计算,4)能正确列出最优值函数的递推公式和边界条件,（b）能通过现阶段的决策，使当前状态转移 成下一阶段的状态,即 能够给出状态转移方程,（c）状态的无后效性,状态的选取必须注意以下几个要点：,（a）在所研究问题的各阶段，都能直接或间 接确定状态变量的取值,例（资源分配问题）,某公司有资金a万元，拟投资于n个项目，已知对第i个项目投资xi万元，收益为g i(xi)，问应如何分配资金可使总收益最大？,解：阶段k=1,2,n,状态变量sk,决策变量uk,：第k个项目的投资额,：在第k阶段
3、时可以用于投资 第k到第n个项目的资金数,状态转移方程：,sk+1=sk-uk,指标函数Vk,n,：第k阶段可分配的资金数为sk时，,第k至第n个项目的最大总收益,边界条件：,k=n,n-1,2,1,资源分配问题的动态规划基本方程：,建立递推公式：,：在第k阶段分配的资金数为sk时，,第k至第n个项目的最大总收益,某种机器的工作系统由n个部件串联组成，只要有一个部件失灵，整个系统就不能正常工作。为提高系统工作的可靠性，在每一个部件上均装有主要元件的备用件，并设计了备用元件自动投入装置。显然，备用元件越多，整个系统的可靠性越大，但备用元件增多也会导致系统的成本、重量相应增大。设部件i(i=1,2
4、,n)上装有xi个备用元件时，正常工作的概率为pi（xi）。设装一个i部件的设备元件费用为ci，重量wi为，要求整个系统所装备用元件的总费用不超过C，总重量不超过W，问如何选择个部件的备用元件数，使整个系统的工作可靠性最大？,例 复合系统工作可靠性问题,解：设A-整个系统正常工作，Ai部件i正常工作,满足：,非线性规划问题,系统由n个部件串联组成，每一个部件上装有备用件，部件i(i=1,2,n)上装有xi个备用元件时，正常工作的概率为pi（xi）。设装一个i部件的设备元件费用为ci，重量wi为，要求总费用不超过C，总重量不超过W，问如何选择个部件的备用元件数，使整个系统的工作可靠性最大？,例
5、复合系统工作可靠性问题,解：n个部件=n个阶段,决策变量uk=,部件k上所装的备用元件数xk,状态变量：,sk,=第k个到第n个部件可使用的总费用,yk,=第k个到第n个部件容许的总重量,状态转移方程：,指标函数Vk,n,最优指标函数fk(sk，yk）=,在部件k，可使用 的总费用为sk，总重量为yk 时，从部件k 到部件n的系统工作可靠性的最大值,复合系统工作可靠性的动态规划基本方程为：,与问题无关,动态规划基本方程：,4.4.2 动态规划模型的求解,解法,离散型,连续型,：分段穷举法,：利用解析方法或线性规划方法,没有固定的方法,具体模型具体分析,要求：经验,、技巧、灵活,难！,投资额,收
6、益,工厂,一、离散变量的分段穷举法,例（资源分配问题）某有色金属公司拟拨出50万元对所属三家冶炼厂进行技术改造，若以十万元为最少分割单位，各厂收益与投资的关系如下表：,问：对三个工厂如何分配，才能使总收益达到最大？,状态变量sk：,阶段k=1，2，3,决策变量uk：,给工厂k的投资额,在第k阶段时可供工厂k到工厂3分配的资金数,状态转移方程：,sk+1=sk-uk,g k(uk)=给工厂k投资 uk（十万元）的收益,指标函数Vk,n,fk（sk）,投资工厂k至工厂3所得的最大总收益,求f1（5）,=在工厂k，可供分配的资金数为sk时，,基本方程：,k=3,0,0,1,1,2,2,3,3,0,5
7、,7,8,4,5,4,5,10,13,投资额,收益,工厂,k=2,0,0,0,0,1,0,2,3,0 1 2 3,8,9,9.5,7.5,2,9.5,4,5,投资额,收益,工厂,sk+1=sk-uk,0,0,1,1,2,2,3,3,0,5,7,8,4,5,4,5,10,13,k=1,sk+1=sk-uk,投资额,收益,工厂,5,16,0 1 2 3 4 5,12,1,17,最大总收益：,最优策略：,0,0,0,0,1,0,2,3,0 1 2 3,8,9,9.5,7.5,2,9.5,4,5,二、连续变量的解法,例（季节工问题）某工厂的生产任务随季节波动，为降低成本宜用季节临时工，但熟练的生产工人
8、临时难以聘到，培训新手费用又高，各季节工人需用量如下表所示，每季节超过需用量聘用，每人浪费2000元，聘用或解聘费为200元乘上两个季节聘用人数之差的平方，问厂长一年中应如何聘用工人可使总花费最小？（假定工资按实际工作时间计算，则聘用人数可为分数）,季度i 春 夏 秋 冬 春,需用量gk 255 220 240 200 255,方案1：,255 220 240 200 255,总费用：,+200352,200552,+200202,+200402,=1249000,方案2：,255 245 245 245 255,总费用：,+200102,200102,+200025,+20005,+2000
9、45,=190000,解：,阶段1,，状态变量sk第k-1季度聘用人数,决策变量uk第k季度聘用人数,状态转移方程：,sk+1=uk,fk（sk）=第k-1季度聘用人数为sk人时，第k季度到 第4季度的最小总费用,220s2255,gkuk255,季度i 春 夏 秋 冬 春,需用量gk 255 220 240 200 255,2,3,4,k=1,2,34,s1=255,240s3255,200s4255,已知：每季节超过需用量聘用，每人浪费2000元，聘用 和解聘费为200元乘上两个季节聘用人数之差的平方,=min,+fk+1（sk+1）,+2000(uk gk),gkuk255,200(uk
10、 uk-1)2,求f1（255）,=min,+fk+1（uk）,+2000(uk gk),gkuk255,200(uk sk)2,基本方程：,fk（sk）=,min,+fk+1（uk）,f5（s5）=0,求f1（255）,+2000(uk gk),gkuk255,200(uk sk)2,min,f4（s4）=,+2000(u4 g4),g4u4255,200(u4 s4)2,u*4=255,=200(255 s4)2,200s4255,当k=4时,min,f3（s3）=,+f4（u3）,+2000(u3 g3),200(u3 s3)2,g3u3255,=min,+2000(u3 200),20
11、0(u3 s3)2,200u3255,+200(255 u3)2,当k=3时,240s3255,k=4,3,2,1,f3（s3）,=min,+2000(u3 200),200(u3 s3)2,200u3255,+200(255 u3)2,所以f3（s3）=,当k=3时,240s3255,min,min,f2（s2）=,+f3（u2）,+2000(u2 g2),200(u2 s2)2,g2u2255,fk（sk）=,+fk+1（uk）,+2000(uk gk),gkuk255,200(uk sk)2,已知：,f3（s3）,当k=2时,220s2255,=min,+2000(u2 240),200
12、(u2 s2)2,240u2255,+f3（u2）,=min,240u2255,状态转移方程：,sk+1=uk,f2（s2）,当k=2时,220s2255,=min,240u2255,所以f2（s2）=,min,fk（sk）=,+fk+1（uk）,+2000(uk gk),gkuk255,200(uk sk)2,已知：,f2（s2）,当k=1时,，s1=255,min,f1（255）=,+f2（u1）,+2000(u1 g1),g1u1255,200(u1 s1)2,=min,+2000(u1 220),220u1255,200(u1 255)2,状态转移方程：,sk+1=uk,f1（255）=185000,f4（s4）=,u*4=255,200(255 s4)2,f2（s2）,f1（255）=185000,最优策略：,=245,=247.5,u*4=255,最少总费用：为185000元,状态转移方程：,sk+1=uk,最佳聘用方案：,夏季247.5人，秋季245人，冬季247.5人，春季255人时，,
