4.3动态规划建模与求解ppt课件

1、4.3.1 建摸1、实际根据-最优化原理最优化原理： 一个过程的最优战略具有这样的性质，即无论初始形状及初始决策如何，对于先前决策所构成的形状而言，其以后的一切决策必构成最优战略2、动态规划模型的几个要素：1)阶段数k2)形状变量sk3)决策变量uk sk 4)目的函数Vk,n形状转移方程kkkusTs,15)最优值函数fk(sk)3、建立动态规划模型的根本要求：1所研讨的问题必需可以分成几个相互联络的阶段，而且在每一个阶段都具有需求进展决策的问题。2在每一阶段都必需有假设干个与该阶段相关的形状普通情况下，形状是所研讨系统在该阶段能够处于的情况或条件建模时总是从与决策有关的条件中，或是从问题的

2、约束条件中去选择形状变量。3)具有明确的目的函数，且阶段目的值可以计算4)能正确列出最优值函数的递推公式和边境条件b能经过现阶段的决策，使当前形状转移 成下一阶段的形状即 可以给出形状转移方程kkkusTs,1c形状的无后效性之前的过程无关最优策略应与的为出发点的后部子过程阶段的状态即以第kkssk形状的选取必需留意以下几个要点：a在所研讨问题的各阶段，都能直接或间 接确定形状变量的取值例 资源分配问题 某公司有资金a万元，拟投资于n个工程，知对第i个工程投资xi万元，收益为g i (xi)，问应如何分配资金可使总收益最大？解：阶段k=1,2, ,n形状变量sk决策变量uk：第k个工程的投资额

3、：在第k阶段时可以用于投资 第k到第n个工程的资金数形状转移方程：sk+1 = sk -uk目的函数Vk,nnkiiiug：第k阶段可分配的资金数为sk时，第k至第n个工程的最大总收益0|kkkksuuUkksf最优值函数 af1求kksf边境条件：k=n,n-1, ,2,1011nnsf资源分配问题的动态规划根本方程： 01 , 2 , 1,max11110nnkkkksukksfnnksfugsfkk建立递推公式：kkug11kksfkksu0max：在第k阶段分配的资金数为sk时，第k至第n个工程的最大总收益kksf最优值函数某种机器的任务系统由n个部件串联组成，只需有一个部件失灵，整个

4、系统就不能正常任务。为提高系统任务的可靠性，在每一个部件上均装有主要元件的备用件，并设计了备用元件自动投入安装。显然，备用元件越多，整个系统的可靠性越大，但备用元件增多也会导致系统的本钱、分量相应增大。设部件i(i=1,2, ,n)上装有xi个备用元件时，正常任务的概率为pi xi 。设装一个i部件的设备元件费用为ci ，分量wi为，要求整个系统所配备用元件的总费用不超越C，总分量不超越W，问如何选择个部件的备用元件数，使整个系统的任务可靠性最大？例 复合系统任务可靠性问题解：设A-整个系统正常任务，Ai部件i正常任务满足：Cxcniii1Wxwniii1且为整数0ix非线性规划问题 nAPA

5、PAPAP21则,21nAAAA iinixp1 iinixpP1max数学模型为：求系统由n个部件串联组成，每一个部件上装有备用件，部件i(i=1,2, ,n)上装有xi个备用元件时，正常任务的概率为pi xi 。设装一个i部件的设备元件费用为ci ，分量wi为，要求总费用不超越C，总分量不超越W，问如何选择个部件的备用元件数，使整个系统的任务可靠性最大？例 复合系统任务可靠性问题解： n个部件=n个阶段决策变量uk = 部件k上所装的备用元件数xk 形状变量：sk=第k个到第n个部件可运用的总费用yk=第k个到第n个部件允许的总分量形状转移方程：kkkkucss1kkkkuwyy1目的函数

6、Vk,n iinkiup最优目的函数fk(sk， yk = 在部件k，可运用 的总费用为sk，总分量为yk 时，从部件k 到部件n的系统任务可靠性的最大值kumax111,kkkkkysfupKU复合系统任务可靠性的动态规划根本方程为：kkkysf,1,111nnnysf与问题无关WCf,1求1 , 2 , 1,nnk动态规划根本方程： 01 , 2 , 1,1111nnkkkkukksfnnksfugoptsfk 11 , 2 , 1,1111nnkkkkukksfnnksfugoptsfk或4.4.2 动态规划模型的求解解法离散型延续型：分段穷举法：利用解析方法或线性规划方法没有固定的方法

7、详细模型详细分析要求：阅历 、技巧、灵敏难！投资额收益工厂 12314.525274.57397.58410.511105121513一、离散变量的分段穷举法例资源分配问题某有色金属公司拟拨出50万元对所属三家冶炼厂进展技术改造，假设以十万元为最少分割单位，各厂收益与投资的关系如下表：问：对三个工厂如何分配，才干使总收益到达最大？形状变量sk：阶段k=1，2，3决策变量uk：给工厂k的投资额在第k阶段时可供工厂k到工厂3分配的资金数kksu 0形状转移方程：sk+1 = sk -ukg k (uk)=给工厂k投资 uk十万元的收益目的函数Vk,n3kiiiug 110maxkkkksukksf

8、ugsfkkfk sk 投资工厂k至工厂3所得的最大总收益求f1 5 =在工厂k，可供分配的资金数为sk时，kumax11kkkksfugkksu 0 044sf根本方程：k=33s03u0112233)(33sf0 57845451013投资额收益工厂 12314.525274.57397.58410.5111051215131 , 2 , 3k 3303333maxugsfsu *3u012345k=22s2u)(22sf0032fg 001*2u020 15 2050 1 27 7 4.50或1730 1 2 38 9 9.5 7.529.5450 1 2 3 4 101011.512.

9、511312.50 1 2 3 4 5131212.514.5 1615416 332202222maxsfugsfsu投资额收益工厂 12314.525274.57397.58410.511105121513sk+1 = sk -uk3s03u0112233)(33sf0 57845451013*3u012345k=1 221101111maxsfugsfsusk+1 = sk -uk投资额收益工厂 12314.525274.57397.58410.5111051215131s1u)(11sf 2211sfug*1u516 0 1 2 3 4 517 16.5 16 15.5 12117最大

10、总收益：十万元）(17)5(1f最优战略：1*1u3,*2u1,*3u2s2u)(22sf0032fg 001*2u020 15 2050 1 27 7 4.50或1730 1 2 38 9 9.5 7.529.5450 1 2 3 4 101011.512.511312.50 1 2 3 4 5131212.514.5 1615416二、延续变量的解法例季节工问题某工厂的消费义务随季节动摇，为降低本钱宜用季节暂时工，但熟练的消费工人暂时难以聘到，培训新手费用又高，各季节工人需用量如下表所示，每季节超越需用量聘用，每人浪费2000元，聘用或解聘费为200元乘上两个季节聘用人数之差的平方，问厂长

11、一年中应如何聘用工人可使总破费最小？假定工资按实践任务时间计算，那么聘用人数可为分数季度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 fksk=第k-1季度聘用人数为sk人时，第k季度到 第4季度的最小总费

12、用 ,220s2255gkuk255季度i 春 夏 秋 冬 春需用量gk 255 220 240 200 255234k=1,2,34s1=255,240s3255,200s4255知：每季节超越需用量聘用，每人浪费2000元，聘用 和解聘费为200元乘上两个季节聘用人数之差的平方=min +fk+1sk+1+2000(uk gk)gkuk255200(uk uk-1)2求f1255 =min +fk+1uk+2000(uk gk)gkuk255200(uk sk)2根本方程：fksk=min +fk+1ukf5s5=0求f1255+2000(uk gk)gkuk255200(uk sk)2m

13、in f4s4=+2000(u4 g4)g4u4255200(u4 s4)2u*4=255=200(255 s4)2,200s4255当k=4时min f3s3=+f4u3+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,1f3s3 =min +2000(u3 200)200(u3 s3)2200u3255+200(255 u3)22332332552002002000200uusuh令33332554002000400usududh则100

14、0040080033su03dudh令1252133su得0800232duhd且12521*33su为最小值点即1252133su所以f3s3=23323211302007521200021125200sss2332326050150100025050sss当k=3时,240s3255255,2003umin min f2s2=+f3u2+2000(u2 g2)200(u2 s2)2g2u2255fksk=+fk+1uk+2000(uk gk)gkuk255200(uk sk)2知：f3s32332326050150100025050sss当k=2时,220s2255=min +2000(u

15、2 240)200(u2 s2)2240u2255+f3u2=min 587500048000400200300222222ussu240u2255形状转移方程： sk+1 = uk f2s2当k=2时,220s2255=min 587500048000400200300222222ussu240u22552dudh4800040060022su02dudh令803222su得0600222duhd且8032*,22su所以f2s2=587500048000400200300222222ussuh令5875000)8032(48000400200)8032(300222222ssss39550

16、00320003200222ss255,2402u为最小值点即803222sumin fksk=+fk+1uk+2000(uk gk)gkuk255200(uk sk)2知：f2s23955000320003200222ss当k=1时，s1=255min f1255=+f2u1+2000(u1 g1)g1u1255200(u1 s1)2=min +2000(u1 220)220u1255200(u1 255)23955000320003200121uu形状转移方程： sk+1 = uk 3200034002000)255(400111uududh132000316001u01dudh令5 .2471u得031600212duhd且为最小值点即5 .2471uf1255=1850005