1、多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例例1 最短路径问题最短路径问题 下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。1BACBDBCDEC4123123123221647248386756110643751 11 1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例穷举法穷举法:如果从A到E的站点有k个，除A、E之外每站有3个位置，则总共有3k-12条路径；计算各路径长度总共要进行(k+1)3k-12次加法以及3k-12-1次比较。例如：当 k=20时，加法进行4.261015 次，比较1.371014次。若用1亿次/秒的计算机计算需要约508天。2 11
2、 1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例讨论：讨论：以上求从A到E的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从Di、Ci、Bi、A到E的最短路径问题。3 11 1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例第四阶段：第四阶段：两个始点D1和D2，终点只有一个；分析得知：从D1和D2到E的最短路径唯一。4本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)ED1D210*6106EE 15第三阶段：第三阶段：有三个始点C1，C2，C3，终点有D1，D2，分别求C1，C2，C3到D1，D2 的最短路径问题：分析得
3、知：如果经过C1，则最短路为C1-D2-E；如果经过C2，则最短路为C2-D2-E；如果经过C3，则最短路为C3-D1-E。多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)D1D2C1C2C38+10=187+10=171+10=116+6=125+6=116+6=1212 11 11D2D2D1 16第二阶段：第二阶段：始点B1,B2,B3,B4，终点C1,C2,C3，分别求B1,B2,B3,B4到C1,C2,C3的最短路径问题：分析得知：如果经过B1，则走B1-C2-D2-E；如果经过B2，则走B2-C3
4、-D1-E；如果经过B3，则走B3-C3-D1-E；如果经过B4，则走B4-C3-D1-E。本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)C1 C2 C3 B1 B2 B3 B4 2+12=14 4+12=16 4+12=16 7+12=19 1+11=12 7+11=18 8+11=19 5+11=16 6+11=17 2+11=13 3+11=14 1+11=12 12 13 14 12 C2 C3 C3 C3 1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例7第一阶段：第一阶段：只有1个始点A，终点有B1,B2,B3,B4，分别求A到B1,B2,
5、B3,B4的最短路径问题：可以得到：从A到E的最短路径为A B4 C3 D1 E本阶段始点(状态)本阶段各终点（决策）到E的最短距离本阶段最优终点(最优决策)B1 B2 B3 B4 A4+12=16 3+13=163+14=172+12=14 14 B4 1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例8 以上计算过程及结果，可用下图表示，不仅得到了从A到D的最短路径，同时也得到了从图中任一点到E的最短路径。以上过程，仅用了22次加法，计算效率远高于穷举法。BACBDBCDEC412312312332164724838675161060106121111121314144B12751
6、2 1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例9一、基本概念：一、基本概念：1、阶段阶段k：表示决策顺序的离散的量，可以按时间或空间划分。2、状态状态sk：能确定地表示决策过程当前特征的量。可以是数量、字符，数量状态可以连续、离散。3、决策决策xk：从某一状态向下一状态过渡时所做的选择。是所在状态的函数，记为xk(sk)。4、决策允许集合决策允许集合Dk(sk)：在状态sk下，允许采取决策的全体。5、策略策略Pk,n(sk)：从第k阶段开始到最后第n阶段的决策序列，称k子策略。P1,n(s1)即为全过程策略。2基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理106、
7、状态转移方程状态转移方程sk+1=Tk(sk,xk)：某一状态及该状态下的决策，与下一状态之间的函数关系。7、阶段指标函数阶段指标函数vk(sk,xk)：从状态sk出发，选择决策xk所产生的第k阶段指标。8、过程指标函数过程指标函数Vk,n(sk,xk,xk+1,xn)：从状态sk出发，选择决策xk,xk+1,xn所产生的过程指标。过程指标具有可分离性：若Vk,n(sk,xk,xk+1,xn)=vk(sk,xk)+Vk+1(sk+1,xk+1,xn),称指标具有可加性；若Vk,n(sk,xk,xk+1,xn)=vk(sk,xk)Vk+1(sk+1,xk+1,xn)，称指标具有可乘性。2基本概念
8、、基本方程与最优化原理基本概念、基本方程与最优化原理11二、基本方程：二、基本方程：最优指标函数最优指标函数fk(sk)：从状态sk出发，对所有的策略Pk,n，过程指标Vk,n的最优值，即对于可加性指标函数，上式可以写为 上式中“opt”表示“max”或“min”。对于可乘性指标函数，上式可以写为 称为动态规划最优指标的递推方程动态规划最优指标的递推方程。终端条件终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，一般（对加指标）最后一个状态n+1下最优指标fn+1(sn+1)=0。nksfxsvsfkkkkksDxkkoptkkk,.,2,1)(),()(11)(nks
9、fxsvsfkkkkksDxkkoptkkk,.,2,1)(),()(11)(2基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理),()(,)(nkknksDxkkPsVsfoptkkk12三、最优化原理三、最优化原理作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。就是说，最优策略的任意最优策略的任意子策略都是最优的子策略都是最优的。2基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理13一、资源分配问题一、资源分配问题 例2.某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工厂。各工
10、厂获得此设备后，预测可创造的利润如表所示，问这5台设备应如何分配给这3个工厂，使得所创造的总利润为最大？工厂 盈利设备台数 甲 厂 乙 厂 丙 厂 0 0 0 0 1 3 5 4 2 7 10 6 3 9 11 11 4 12 11 12 5 13 11 12 3动态规划的应用动态规划的应用(1)(1)14解：按甲、乙、丙工厂分为三个阶段分为三个阶段，编号1、2、3。设 =分配给第k个厂至第3个厂的设备台数。=分配给第k个厂的设备台数。已知 ,并有 从与的定义和 本题目已知数据的特点，可知222223),(xsxsTskskx33xs111112),(xsxsTs 3动态规划的应用动态规划的应
11、用(1)(1)kskx51s15第三阶段第三阶段:将台设备都分配给第3工厂时，第3阶段的指标值（盈利）为最大，即 由于第3阶段是最后的阶段，故有 其中可取值为0,1,2,3,4,5。其数值计算见表。)5,4,3,2,1,0(33ss).,(),(max)(333333333ssrxsrsfx3x;),(),(max3333333?ssrxsrx33xs 3动态规划的应用动态规划的应用(1)(1)16 3x3s)(33sf3*x 3动态规划的应用动态规划的应用(1)(1)01234500-001-4-412-6-623-11-1134-121245-12125),(333xsr表示取3子过程上最
12、优指标值时的的决策。3*x)(33sf3x17例：在表中可知当 时，有此时，即当时，此时取（把4台设备分配给第3厂）是最优决策，此时阶段指标值（盈利）为12，最优3子过程最优指标值也为12。43s;12)4,4(3r,12)4(3f43*x43s43x 3动态规划的应用动态规划的应用(1)(1)18 第二阶段：第二阶段：当把台设备分配给第2工厂和第3工厂时，则对每个值，有一种最优分配方案，使最大盈利，即最优2子过程最优指标函数值为)5,4,3,2,1,0(22ss2s)(),(max)(33222222sfxsrsfx因为上式也可写成,223xss)(),(max)(223222222xsfx
13、srsfx 3动态规划的应用动态规划的应用(1)(1)19数值计算如表。3动态规划的应用动态规划的应用(1)(1)0123450-001-512-1023-1424-161,252122x2s)(),(233222xsfxsr)(22sf2*x000511501041061011104060110120120411456512561141101101101120例如在的这一行里，当 时，查前两表可知，当时，同样可知 当时，；当时，当时，42s12x16115)3()1,4()14()1,4()(),(3232223222frfrxsfxsr5)1,4(2r11)3(3f22x16610)2()
14、2,4()24()2,4()(),(3232223222frfrxsfxsr02x12120)04()0,4(32 fr32x15411)34()3,4(32 fr 3动态规划的应用动态规划的应用(1)(1)42x11011)44()4,4(32fr21由于，不可能分2厂5台设备，故 当 时，栏不填。从这些数值中取最大，即得 。在取最大值的 上加一横，可知的最优决策为1或2。42s52x)54()5,4(32 fr16)4(2f)(),(223222xsfxsr2x 3动态规划的应用动态规划的应用(1)(1)22第一阶段：第一阶段：把台设备分配给第1，第2，第3厂时，最大盈利为其中 然后按计算
15、表格的顺序推算，可知最优分配方案有两个：)5(11ss),5(),5(max)5(111111xfxrfx01234551x1s)5(),5(1211xfxr210147)(1xf1*x 3动态规划的应用动态规划的应用(1)(1)163109512013212,0?.5,4,3,2,1,01?x2322*x1232*23xss133*sx 3动态规划的应用动态规划的应用(1)(1)21*x3251*12xss1.由于，根据，查表107可 知，再由 ，求得。即分配给甲厂0台，乙厂2台，丙厂3台。2.由于，根据，查表107可知，再由 ,求得，即分配给甲厂2台，乙厂2台，丙厂1台。这两种分配方案都能
16、得到最高的总盈利这两种分配方案都能得到最高的总盈利21万元。万元。01*x5051*12xss*22x3252*23xss333*sx24二、背包问题二、背包问题设有 种物品，每种物品数量无限。第 种物品每件重量为 公斤，每件价值 元。现有一只可装载重量为 公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。用整数规划整数规划模型来描述。设 为第 种物品装入背包的件数 ，背包中物品的总价值为 ，则 且为整数 3动态规划的应用动态规划的应用(1)(1)niiwicWiXin),2,1,=(iz 0 x.,x,x wxw+xw+x ws.t.xc+xc+xc =zmax n21nn
17、2211nn221125 用动态规划动态规划方法解：设阶段变量阶段变量 ：第k次装载第k种物品状态变量状态变量 ：第k次装载时背包还可以装载的重量；决策变量决策变量 ：第k次装载第k种物品的件数；决策允许集合决策允许集合：；状态转移方程状态转移方程：；阶段指标阶段指标：；最优过程指标函数最优过程指标函数 ：第k到n阶段容许装入物品的最大价值；递推方程递推方程：终端条件终端条件：3动态规划的应用动态规划的应用(1)(1)n),2,1,=(kkkSkk x u 0,1,2.nx,/wSx0|x )(SDkkkkkkkkkk1kxws skkkxc v)(sfkk;xw(sfxcmax )(sfxc
18、max )(sfkkk1kkk1k1kkkkk)(sD xkk0 )(sf1n1n26例3.某咨询公司有10个工作日可以去处理四种类型的咨询项目，每种类型的咨询项目中待处理的客户数量、处理每个客户所需工作日数以及所获得的利润如表所示。显然该公司在10天内不能处理完所有的客户，它可以自己挑选一些客户，其余的请其他咨询公司去做，应如何选择客户使得在这10个工作日中获利最大？咨询项目类型待处理客户数处理每个客户所需工作日数处理每个客户所获利润123443221347281120 3动态规划的应用动态规划的应用(1)(1)27解：我们把此问题分成我们把此问题分成四个阶段四个阶段。第一阶段我们决策将处理
19、多少个第一种咨询项目类型中的客户，第二阶段决策将处理多少个第二种咨询项目类型中的客户，第三阶段、第四阶段我们也将作出类似的决策。设 分配给第k种咨询项目到第四种咨询项目的客户的总工作日（第k阶段的状态变量）。=在第k种咨询项目中处理客户的数量（第k阶段的决策变量）。已知10，并有 kx1s,),(111112xsxsTsks 3动态规划的应用动态规划的应用(1)(1),3),(222223xsxsTs.4),(333334xsxsTs28第四阶段：第四阶段：将 个工作日尽可能分配给第四类咨询项目，即时，第四阶段的指标值为最大，表示取不大于 的最大整数，符号为取整符号，故有由于第四阶段是最后的阶
20、段，故有4s)10,.,1,0(4s7/44sx 7/4s).7/,(),(max4444444ssrxsrx)7/,(),(max)(4444*44444ssrxsrsfx 3动态规划的应用动态规划的应用(1)(1)4x因为至多为10，数值计算见表。4s29010001002003004005006007020180201902011002014x4s),(444xsr)(44sf4*x000000020202020 3动态规划的应用动态规划的应用(1)(1)30第三阶段：第三阶段：当把个工作日分配给第四类和第三类咨询项目时，则对每个值，都有一种最优分配方案，使其最大盈利即最优3子过程最优指
21、标函数值为 因为，故 因为至多为10，所以的取值可为0,1,2。数值计算见表。)10,.,2,1,0(33ss3s.)(),(max)(44333333sfxsrsfx4334ssx.)4(),(max)(334333333xsfxsrsfx3s3x 3动态规划的应用动态规划的应用(1)(1)31 3动态规划的应用动态规划的应用(1)(1)0120-001-002-003-004-1115-1116-1117-2008222922210222)(33sf3x)4(),(334333xsfxsr3s3x00000000002002000110110110110110110110000200200
22、02202202232 第二阶段：第二阶段：同样以每个值都有一种最优分配方案，使其最大盈利即最优2子过程最优指标函数值为：因为，故 因为至多为10，所以的取值为0,1,2,3。其数值计算见表。.)3(),(max)(223222222xsfxsrsfx2233xss.)3(),(max)(223222222xsfxsrsfx2s2x2s 3动态规划的应用动态规划的应用(1)(1)33 3动态规划的应用动态规划的应用(1)(1)01230-001-002-003-814-1105-1106-1627-2008-2209243102810000002s2x22()fs*2x222322(,)(3)
23、rsxfsx008024024016016 016 016 016 118080808118118118200 110 110200220 220 220 1134 第一阶段：第一阶段：已知，又因为 ，同样有 因为 ,故可取值为0,1,2,10。其数值计算见表。101s.)(),(max)(112111111xsfxsrsfx112xss.)10(),10(max)10(121111xfxrfx101s1x 3动态规划的应用动态规划的应用(1)(1)35由上表知，从而 ，由表的 的这一行可知 由 由表的的这一行可知 由 ，查表的这一行得综上所述得综上所述得最优解最优解为为：最大盈利为28。28
24、)10(1f01*x10010101*2xs102s,12*x731032*23xss73s03*x7073*34xss74s14*x,1,0,1,04*3*2*1*xxxx 3动态规划的应用动态规划的应用(1)(1)012345678910102801121(10,)(10)rxfx0282244226208 16101112 1114816018020011()f s*1x1x1s36 3动态规划的应用动态规划的应用(1)(1)现在我们假设该咨询公司的工作计划有所改变，只有8个工作日来处理这四类咨询项目，那么该咨询公司如何选择客户使得获利最大？我们只要在第一阶段上把改成只要在第一阶段上把改
25、成8，重新计算即可，如下表所示，这是动态规划的一个好处。1s0123456788220.1)8(),8(1211xfxr1*x)(11sf1x1s16422020211611881001401601237从而得到两组最优解如下：最优解（即最大盈利）都为22。一旦咨询的工作日不是减少而是增加，那么我们不仅要重新计算第一阶段，而且要在第二、第三、第四阶段的计算表上补上增加的工作日的新的信息，也可得到新的结果。3042)4321xxxx1001)4*3*2*1*xxxx 3动态规划的应用动态规划的应用(1)(1)38三、生产与存贮问题三、生产与存贮问题 例4.某公司为主要电力公司生产大型变压器，由于
26、电力采取预订方式购买，所以该公司可以预测未来几个月的需求量。为确保需求，该公司为新的一年前四个月制定一项生产计划，这四个月的需求如表所示。生产成本随着生产数量而变化。调试费为4，除了调试费用外，每月生产的头两台各花费为2，后两台花费为1。最大生产能力每月为4台，生产成本如表所示。3动态规划的应用动态规划的应用(1)(1)39 3动态规划的应用动态规划的应用(1)(1)每台变压器在仓库中由这个月存到下个月的储存费为1，仓库的最大储存能力为3台，另外，1月1日时仓库里存有一台变压器，要求在4月30日仓库的库存量为零。生产件数总成本00162839410月份n需求量（台）12243143试问：该公司
27、应如何制定生产计划，使得四个月的生产成本和储存总费用最少？40解：第k个月为第i阶段设 为第k阶段期初库存量；为第k阶段生产量；为第k阶段需求量；因为下个月的库存量等于上个月的库存量加上上个月的产量减去上个月的需求量，得到状态转移方程状态转移方程：因为，故有因为，故有 ks 3动态规划的应用动态规划的应用(1)(1)kxkd,1112dxss11s,1121dxs,2223dxss,3334dxss,4445dxss05s,4440dxsk1,2,3,441由于必须要满足需求，则有 通过移项得到 另一方面，第k阶段的生产量必不大于同期的生产能力（4台），也不大于第k阶段至第四阶段的需求之和与第
28、k阶段期初库存量之差，否则第k阶段的生产量就要超过从第k阶段至第四阶段的总需求，故有),4,3,2,1(,kdxskkkkkksdxkx44,)(minkikiksdx 3动态规划的应用动态规划的应用(1)(1)42第四阶段：第四阶段：从状态转移方程可知这样就有阶段指标可以分成生产成本与储存费，即由于第四阶段末要求库存为零，即有，可得 ,0444dxs,34444ssdx)3,(),(min)(444444444ssrxsrsfx 3动态规划的应用动态规划的应用(1)(1),(nnnxsr),()(),(nnnnnnnnxshxcxsr001),(444xsh)3()3,()3()3,()(4
29、44444444444scsshscssrsf43对于每个的可行值，的值列于表。当时，可知第四阶段要生产 台，总成本为9。同理算出当为1,2,3时的情况。4s)(44sf 3动态规划的应用动态规划的应用(1)(1)04s3344sx4s01230-9931-8-822-6-6130-0044()fs4x*4x4s44444(,3)(3)r sscs44第三阶段：第三阶段：此时有：因为以及所以有结果所示：)(1)(),()(),(3333333333333dxsxcxshxcxsr,3334dxss,13d)()1(1)(min)(443333)4,4min(133333sfxsxcsfsxs)
30、1()1(1)(min3343333)4,4min(1333xsfxsxcsxs 3动态规划的应用动态规划的应用(1)(1)012340-1341-902-903-80)1-(),(334333xsfxsr)(33sf3*x3x3s906818629816628039038036626031090081062045 计算结果如表所示。)(),(min)(33222)4,8min(422222sfxsrsfsxs)(),()(min3322222)4,8min(4222sfxshxcsxs)()(1)(min222322222)4,8min(4222dxsfdxsxcsxs)4()4(1)(mi
31、n2232222)4,8min(4222xsfxsxcsxs 3动态规划的应用动态规划的应用(1)(1)第二阶段：第二阶段：因为所以有,422232dxssd012340-2341-2042-193-)4-(),(223222xsfxsr)(22sf2*x2x2s1301091109199181309130813069298310921046第一阶段：第一阶段：因为故有计算结果见表。,1,2211111sdxssd)(),(min)1()(22111411111sfxsrfsfx)21()21(1)(min12111411xfxxcx 3动态规划的应用动态规划的应用(1)(1)012341-2
32、91,22306?2018?1929183101*x)(11sf)2-(),(112111xsfxsr1x1s47利用递推关系得到两组最优解：这时有最低总成本29。0441)4321xxxx3042)4321xxxx 3动态规划的应用动态规划的应用(1)(1)四、系统可靠性问题四、系统可靠性问题 例5.某科研项目组由三个小组用不同的手段分别研究，它们失败的概率各为0.40，0.60，0.80。为了减少三个小组都失败的可能性，现决定给三个小组中增派两名高级科学家到各小组，各小组科研项目失败概率如下表，问如何分派科学家才能使三个小组都失败的概率（即科研项目最终失败的概率）最小？高级科学家小组123
33、00.400.600.8010.200.400.5020.150.200.3048 3动态规划的应用动态规划的应用(1)(1)解：用逆序算法用逆序算法。设阶段：每个研究小组为一个阶段 决策变量决策变量 ：分配给第n小组的高级科学家数目，相应的失败概率为 ；状态变量状态变量 ：在阶段n时可分配于阶段 的高级科学家人数。递推关系递推关系：阶段123小组12349 3动态规划的应用动态规划的应用(1)(1)nx)(nnxPns3,.,1,nn)(min)(333*33xPsfsx.2,1),(*)(min)(1*nxsfxPsfnnnnnsxnnnn当n=3时，当n=2时，50s3f3*(s3)x3
34、*00.80010.50120.302 x2s2f2(s2,x2)=P2(x2)*f3*(s2-x2)f2*(s2)x2*01200.480.48010.300.320.30020.180.200.160.162 3动态规划的应用动态规划的应用(1)(1)当n=1时，最优解为 x1*=1，x2*=0，x3*=1；科研项目最终失败的概率为0.060。51 x1s1f1(s1,x1)=P1(x1)f2*(s1-x1)f2*(s2)x2*01220.064 0.060 0.072 0.060 1 3动态规划的应用动态规划的应用(1)(1)一、一、连续确定性动态规划连续确定性动态规划 对于状态变量和决
35、策变量只取连续值，过程的演变方式为确定性时，这种动态规划问题就称为连续确定性动态规划问题。52 4动态规划的应用动态规划的应用(2)(2)机器负荷分配问题机器负荷分配问题 例例1 一种机器能在高低两种不同的负荷状态下工作。设机器在高负荷下生产时，产量函数为P1=8u1，其中u1为在高负荷状态下生产的机器数目，年完好率为a=0.7，即到年底有70的机器保持完好。在低负荷下生产时，产量函数为P2=5u2，其中u2为在低负荷状态下生产的机器数目，年完好率为b=0.9。设开始生产时共有1000台完好的机器，请问每年应该如何把完好机器分配给高、低两种负荷下生产，才能使得5年内生产的产品总产量最高。53
36、4动态规划的应用动态规划的应用(2)(2)解 建立动态规划模型：分为5个阶段，每个阶段为1年。设状态变量sk表示在第k阶段初拥有的完好机器数目；k=1,2,3,4,5。决策变量xk表示第k阶段中分配给高负荷状态下生产的机器数目；sk-xk为分配给低负荷状态下生产的机器数目。状态转移方程为sk+1=0.7xk+0.9(sk-xk)阶段指标rk(sk,xk)=8xk+5(sk-xk)最优指标函数 f6(s6)=0)()58max)(11kkkkkkksfxsxsf（kksx 054 4动态规划的应用动态规划的应用(2)(2)第第5阶段：阶段：因为f5(s5)是x5的线性单调增函数，故有x5*=s5
37、，于是有f5(s5)=8s5。第第4阶段：阶段：同样，f4(s4)是x4的线性单调增函数，有x4*=s4，f4(s4)=13.6s4。55)(2.126.13max)(9.07.0 8)(58max8)(58max)()(58max)(44404444440544405544404444444444xsxxsxxsxsxsxsfxsxsfsxsxsxsx 4动态规划的应用动态规划的应用(2)(2)依次类推，可得f3(s3)=17.52s3，f2(s2)=20.768s2，f1(s1)=23.6912s1。因为期初共有完好机器1000台，故s1=1000。有f1(s1)=23.6912s1236
38、91.2，即5年最大的产量为23691台。最优解为 即前两年应把年初完好机器完全投入低负荷生产，后三年应把年初完好机器完全投入高负荷生产。565*54*43*3*2*1,0,0sxsxsxxx 4动态规划的应用动态规划的应用(2)(2)下一步工作是确定每年初的状态，按照从前向后的顺序依次计算出每年年初完好的机器数目。已知 ,根据状态转移方程，有:572789.0)(9.07.03979.0)(9.07.05679.0)(9.07.08109.0)(9.07.09009.0)(9.07.05*55*564*44*453*33*342*22*231*11*12sxsxssxsxssxsxssxsx
39、ssxsxs 4动态规划的应用动态规划的应用(2)(2)10001s 上面所讨论的最优策略过程，初始端状态s1=1000台是固定的，终点状态s6没有要求。这种情况下得到最优决策称为初始端固定终点自由的最优策略。如果终点附加一定的条件，则问题就称为“终端固定问题”。例如，规定在第5年度结束时仍要保持500台机器完好（而不是278台），应如何安排生产才能使得总产量最大？58 4动态规划的应用动态规划的应用(2)(2)显然，由于固定了终点的状态，x5的取值受到了约束。因此有类似的，容易解得 ，。5975005.18)25005.4(5)25005.4(8max)(555555sssssf75007.
40、065.21max75005.18)(58max)()(58max)(4405444055444044444444xssxsxsfxsxsfsxsxsx0*4x 4动态规划的应用动态规划的应用(2)(2)根据终点条件有 可得500)(9.07.05556xsxs25005.455sx7500-65.21)(444ssf依次类推，得再采用顺序方法递推计算各年的状态，有 609009.0)(9.07.01*11*12sxsxs8109.0)(9.07.02*22*23sxsxs7297.0)(9.07.03*33*34sxsxs6567.0)(9.07.04*44*45sxsxs 4动态规划的应用
41、动态规划的应用(2)(2)7500-29.333255s)(sf7500-27.03695s)(sf7500-24.4855s)(sf0111222333*1*2*3xxx1000s1 可见，为了使终点完好的机器数量增加到500台，需要安排前四年中全部完好机器都要投入低负荷生产，且在第5年，有 台投入高负荷生产，204台投入低负荷生产。相应的最优指标为 可以看到，因为增加了附加条件，总产量 要比终点自由情况下的产量要低。614522500-656*5.425005.45*5sx 4动态规划的应用动态规划的应用(2)(2)21833.2557500-29.333255s=)(sf111)(sf1
42、1二、离散随机性动态规划二、离散随机性动态规划随机型的动态规划是指状态的转移律是不确定的，即对给定的状态和决策，下一阶段的到达状态是具有确定概率分布的随机变量，这个概率分布由本阶段的状态和决策完全确定。其基本结构如下：62 sk状态 xk决策概率k阶段的收益p1p2pN.k+1阶段的状态sk+1c1c2cN 1 2N 4动态规划的应用动态规划的应用(2)(2)图中N表示第k+1阶段可能的状态数，p1、p2、pN为给定状态sk和决策xk的前提下，可能达到下一个状态的概率。ci为从k阶段状态sk转移到k+1 阶段状态为i时的指标函数值。在随机性的动态规划问题中，由于下一阶段到达的状态和阶段的效益值
43、不确定，只能根据各阶段的期望效益值进行优化。63 4动态规划的应用动态规划的应用(2)(2)例例2 某公司承担一种新产品研制任务，合同要求三个月内交出一件合格的样品，否则将索赔2000元。根据有经验的技术人员估计，试制品合格的概率为0.4，每次试制一批的装配费为200元，每件产品的制造成本为100元。每次试制的周期为1个月。问该如何安排试制，每次生产多少件，才能使得期望费用最小？64 4动态规划的应用动态规划的应用(2)(2)解：解：把三次试制当作三次试制当作三个阶段三个阶段（k=1,2,3）决策变量决策变量xk表示第k次生产的产品的件数；状态变量状态变量sk表示第k次试制前是否已经生产出合格
44、品，如果有合格品，则sk=0；如果没有合格品，记sk=1。最优函数最优函数fk(sk)表示从状态sk、决策xk出发的第k阶段以后的最小期望费用。故有fk(0)0。生产出一件合格品的概率为0.4，所以生产xk件产品都不合格的概率为 ，至少有一件合格品的概率为1-，故有状态状态转移方程转移方程为 kx6.0kx6.065kkxkxkspsp6.01)0(6.0)1(11 4动态规划的应用动态规划的应用(2)(2)用 表示第 阶段的费用，第第 阶段的费用包括制造阶段的费用包括制造成本和装配费用成本和装配费用，故有 根据状态转移方程以及 ，可得到 如果3个月后没有试制出一件合格品，则要承担2000元的
45、罚金，因此有 。660002)(kkkkxxxxC)1(6.0)0()6.01()(min)1(11kxkxkxkffxcfkkk)1(6.0)(min1kxkxfxckk 4动态规划的应用动态规划的应用(2)(2)(kxC)(kxCkk20)1(4f当k=3时，计算如下表：67 x3 s3 C(x3)+200.6X3f3(s3)x3*0 1 2 3 4 5 6 0 0 0 0 1 20 1511.29.328.598.568.93 8.56 5 4动态规划的应用动态规划的应用(2)(2)当k=2时，计算如下表：68 x2 s2 C(x2)+8.560.6X2f2(s2)x2*0 1 2 3
46、4 0 0 00 18.568.147.086.857.11 6.85 3 4动态规划的应用动态规划的应用(2)(2)当k=1时，有 69 x1 s1 C(x1)+6.850.6X1f1(s1)x1*0 1 2 3 0 0 0 0 16.857.116.466.48 6.46 2 4动态规划的应用动态规划的应用(2)(2)因为C(xk)+0.6XKfk+1(1)的值是对对xk单调增加单调增加，所以上面三个表中并没有列出xk取更大数值的情况。因此最优策略是最优策略是，在第1个阶段试制2件产品；如果都不合格，在第2阶段试制3件产品；如果仍都不合格，则在第3个阶段试制5件产品。该策略得到的最小的期望
47、费用6.46百元。70 4动态规划的应用动态规划的应用(2)(2)随机采购问题随机采购问题例例3 某公司打算在5周内采购一批原料，未来5周内的原料的价格有三种，这些价格的出现概率可以估计，如下表。该部分由于生产需要，必须在5周内采购这批原料。如果第一周价格很高，可以等到第2周；同样的，第2周如果仍对价格不满意，可以等到第3周；类似地，未来几周都可能选择购买或者等待，但必须保证第5周时采购了该原料。试问该选择哪种采购方案，才能使得采购费用最小？71 价格 概率 450 0.25 470 0.35 500 0.40 4动态规划的应用动态规划的应用(2)(2)解解：按照采购周期分为按照采购周期分为5
48、个阶段个阶段，将每周的价格看作该阶段的状态。假设状态变量状态变量sk表示第k周的实际价格，决策变量决策变量xk表示第k周是否采购的0-1变量。如决定采购，则xk=1；如选择等待，则xk=0。skE表示第k周等待，而在以后采取最优决策时采购价格的期望值。动态规划基本方程动态规划基本方程如下：72)500(40.0)470(35.0)450(25.0)(11111kkkkkEkfffsEfs,min)(Ekkkksssf 4动态规划的应用动态规划的应用(2)(2)第五阶段：第五阶段：因为如果前4周都没有买，那第5周必须购买，因此有 即73 4动态规划的应用动态规划的应用(2)(2)?500)500
49、(470)470(450)450(555fff555)(ssf第四阶段：第四阶段：如第4周购买，则需花费s4；如果不买，则必须在第5周购买。在第第5周采购的费用的期望值周采购的费用的期望值为于是 ，有 故第第4周的最优决策周的最优决策为 74477,min,min)(44444ssssfE500s477470s470450s450)(44444当当当sf500s0470450s1x444当或当 4动态规划的应用动态规划的应用(2)(2)47750040.047035.045025.0)500(40.0)470(35.0)450(25.05554fffsE 第三阶段：第三阶段：如果第3周采购，则
50、需花费s3；也要和第3周后再采购的费用的期望值作比较。于是 ，有 故第第3周的最优决策周的最优决策为 758.46747740.047035.045025.0)500(40.0)470(35.0)450(25.04443fffsE8.467,min,min)(33333ssssfE500;470s467.8450s450)(3333?sf500;470s0450s1x333?4动态规划的应用动态规划的应用(2)(2)第二阶段：第二阶段：同理可得 故第第2周的最优决策周的最优决策为76500470s463.35450s450)(2222或当当sf500470s0450s1x222或当当 4动态规
