《动态规划的建模与求解经典运筹学》由会员分享，可在线阅读，更多相关《动态规划的建模与求解经典运筹学（26页珍藏版）》请在金锄头文库上搜索。
1、4.3.1 建摸1、理论依据-最优化原理最优化原理： 一个过程的最优策略具有这样的性质，即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策必构成最优策略2、动态规划模型的几个要素：1)阶段数k2)状态变量sk3)决策变量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阶段时可以用于投资 第k到第n个项目的资金数状态转移方程：sk+1 = sk
3、 -uk指标函数Vk,n：第k阶段可分配的资金数为sk时，第k至第n个项目的最大总收益边界条件：k=n,n-1, ,2,1资源分配问题的动态规划基本方程：建立递推公式：在第k阶段分配的资金数为sk时，第k至第n个项目的最大总收益某种机器的工作系统由n个部件串联组成，只要有一个部件失灵，整个系统就不能正常工作。为提高系统工作的可靠性，在每一个部件上均装有主要元件的备用件，并设计了备用元件自动投入装置。显然，备用元件越多，整个系统的可靠性越大，但备用元件增多也会导致系统的成本、重量相应增大。设部件i(i=1,2, ,n)上装有xi个备用元件时，正常工作的概率为pi （ xi ）。设装一个i部件的设
4、备元件费用为ci ，重量wi为，要求整个系统所装备用元件的总费用不超过C，总重量不超过W，问如何选择个部件的备用元件数，使整个系统的工作可靠性最大？例 复合系统工作可靠性问题解：设A-整个系统正常工作，Ai部件i正常工作满足：非线性规划问题系统由n个部件串联组成，每一个部件上装有备用件，部件i(i=1,2, ,n)上装有xi个备用元件时，正常工作的概率为pi （ xi ）。设装一个i部件的设备元件费用为ci ，重量wi为，要求总费用不超过C，总重量不超过W，问如何选择个部件的备用元件数，使整个系统的工作可靠性最大？例 复合系统工作可靠性问题解： n个部件=n个阶段决策变量uk = 部件k上所装
5、的备用元件数xk 状态变量：sk=第k个到第n个部件可使用的总费用yk=第k个到第n个部件容许的总重量状态转移方程：指标函数Vk,n最优指标函数fk(sk， yk ）= 在部件k，可使用 的总费用为sk，总重量为yk 时，从部件k 到部件n的系统工作可靠性的最大值复合系统工作可靠性的动态规划基本方程为：与问题无关动态规划基本方程：4.4.2 动态规划模型的求解解法离散型连续型：分段穷举法：利用解析方法或线性规划方法没有固定的方法具体模型具体分析要求：经验 、技巧、灵活难！投资额收益工厂 12314.525274.57397.58410.511105121513一、离散变量的分段穷举法例（资源分
6、配问题）某有色金属公司拟拨出50万元对所属三家冶炼厂进行技术改造，若以十万元为最少分割单位，各厂收益与投资的关系如下表：问：对三个工厂如何分配，才能使总收益达到最大？状态变量sk：阶段k=1，2，3决策变量uk：给工厂k的投资额在第k阶段时可供工厂k到工厂3分配的资金数状态转移方程：sk+1 = sk -ukg k (uk)=给工厂k投资 uk（十万元）的收益指标函数Vk,nfk（ sk ）投资工厂k至工厂3所得的最大总收益求f1（ 5 ）=在工厂k，可供分配的资金数为sk时，基本方程：k=3001122330 57845451013投资额收益工厂 12314.525274.57397.584
7、10.511105121513012345k=200001020 15 2050 1 27 7 4.50或1730 1 2 38 92450 1 2 3 4 10 10 11.512.511312.50 1 2 3 4 513 1212.514.5 1615416投资额收益工厂 12314.525274.57397.58410.511105121513sk+1 = sk -uk001122330 57845451013012345k=1sk+1 = sk -uk投资额收益工厂 12314.525274.57397.58410.511105121513516 0 1 2 3 4 517 16.5
8、 16 15.5 12117最大总收益：最优策略：00001020 15 2050 1 27 7 4.50或1730 1 2 38 92450 1 2 3 4 10 10 11.512.511312.50 1 2 3 4 513 1212.514.5 1615416二、连续变量的解法例（季节工问题）某工厂的生产任务随季节波动，为降低成本宜用季节临时工，但熟练的生产工人临时难以聘到，培训新手费用又高，各季节工人需用量如下表所示，每季节超过需用量聘用，每人浪费2000元，聘用或解聘费为200元乘上两个季节聘用人数之差的平方，问厂长一年中应如何聘用工人可使总花费最小？（假定工资按实际工作时间计算，则
9、聘用人数可为分数）季度i 春 夏 秋 冬 春需用量gk 255 220 240 200 255方案1：255 220 240 200 255总费用：+200352200552+200202+200402=1249000方案2：255 245 245 245 255总费用：+200102200102+200025+20005+200045=190000解：阶段1，状态变量sk第k-1季度聘用人数决策变量uk第k季度聘用人数状态转移方程： sk+1 = uk fk（sk）=第k-1季度聘用人数为sk人时，第k季度到 第4季度的最小总费用 ,220s2255gkuk255季度i 春 夏 秋 冬 春需
10、用量gk 255 220 240 200 255234k=1,2,34s1=255,240s3255,200s4255已知：每季节超过需用量聘用，每人浪费2000元，聘用 和解聘费为200元乘上两个季节聘用人数之差的平方=min +fk+1（sk+1）+2000(uk gk)gkuk255200(uk uk-1)2求f1（255） =min +fk+1（uk）+2000(uk gk)gkuk255200(uk sk)2基本方程：fk（sk）=min +fk+1（uk）f5（s5）=0求f1（255）+2000(uk gk)gkuk255200(uk sk)2min f4（s4）=+2000(u
11、4 g4)g4u4255200(u4 s4)2u*4=255=200(255 s4)2,200s4255当k=4时min f3（s3）=+f4（u3）+2000(u3 g3)200(u3 s3)2g3u3255=min +2000(u3 200)200(u3 s3)2200u3255+200(255 u3)2当k=3时,240s3255k=4,3,2,1f3（s3） =min +2000(u3 200)200(u3 s3)2200u3255+200(255 u3)2所以f3（s3）=当k=3时,240s3255min min f2（s2）=+f3（u2）+2000(u2 g2)200(u2 s
12、2)2g2u2255fk（sk）=+fk+1（uk）+2000(uk gk)gkuk255200(uk sk)2已知：f3（s3）当k=2时,220s2255=min +2000(u2 240)200(u2 s2)2240u2255+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)gkuk255200(uk sk)2已知：f2（s2）当k=1时，s1=255min f1（255）=+f2（u1）+2000(u1 g1)g1u1255200(u1 s1)2=min +2000(u1 220)220u1255200(u1 255)2状态转移方程： sk+1 = uk f1（255）=185000f4（s4）=u*4=255200(255 s4)2f2（s2）f1（255）=185000最优策略：=245u*4=255最少总费用：为185000元状态转移方程： sk+1 = uk 最佳聘用方案：夏季人，秋季245人，冬季人，春季255人时，
