运筹学-动态规划课件

管理运筹学教程

第三章动态规划

清华大学出版社管理运筹学教程

第三章动态规划

清华大学出版社1图3-1清华大学出版社图3-1清华大学出版社2名词解释阶段，用k表示。状态、状态变量，用Sk表示，通常是集合决策、决策变量，通常用uk或xk表示。状态转移及其方程：过程与子过程策略与子策略：指标函数与最优值函数：清华大学出版社名词解释阶段，用k表示。清华大学出版社3二、最优化原理与动态规划的基本方法Bellman原理动态规划的基本方法逆向顺序法前向顺序法清华大学出版社二、最优化原理与动态规划的基本方法Bellman原理清华大学4Bellman原理示意图清华大学出版社Bellman原理示意图清华大学出版社5逆向顺序法求解例3-2清华大学出版社逆向顺序法求解例3-2清华大学出版社6第二节动态规划建模与求解步骤建立动态规划模型的基本要求动态规划的求解步骤清华大学出版社第二节动态规划建模与求解步骤建立动态规划模型的基本要求7一、建立动态规划模型的基本要求将问题划分成若干阶段。有的问题的阶段性很明显，有的则不明显，需要分析后人为假设。确定各阶段的状态变量，并给出状态转移方程，状态转移方程的形式应当与递推顺序一致。状态变量应当满足无后效性要求。明确指标函数，给出最优函数递推方程，递推方程的形式应当与递推顺序一致。清华大学出版社一、建立动态规划模型的基本要求将问题划分成若干阶段。有的问题8二、动态规划的求解步骤正确划分阶段。确定状态变量和决策变量，并给出状态变量和决策变量的可行集合。确定求解的递推顺序，给出状态转移方程。确定阶段、子过程(子策略)的指标函数，确定最优值函数的递推方程和边界条件。递推求解。与递推过程反向求出最优策略(最优决策变量值系列)和最优状态变化路线。清华大学出版社二、动态规划的求解步骤正确划分阶段。清华大学出版社9第三节动态规划的应用举例定价问题资源分配问题生产存储问题清华大学出版社第三节动态规划的应用举例定价问题清华大学出版社10一、定价问题某公司考虑为某新产品定价，该产品的单价拟从每件5元、6元、7元和8元这四个中选取一个，每年允许价格有1元幅度的变动，该产品预计畅销五年，据预测不同价格下各年的利润如表3-1所示。清华大学出版社一、定价问题某公司考虑为某新产品定价，该产品的单价拟从每件511表3-2每年预计利润额单价第一年第二年第三年第四年第五年5元6元7元8元1012141612131415151616152020181425241814清华大学出版社表3-2每年预计利润额单价第一年第二年第三年第四年第五年512建立数学模型按年划分阶段，k=1,2,...,5每阶段的状态变量为本年(上一年已确定)的价格，状态变量的可行集合Sk=(5,6,7,8)。决策变量为每年依据当年价格为下一年度决定价格，根据题意决策变量的可行集合是：采用逆序算法，因此状态转移方程是最优值函数递推方程为清华大学出版社建立数学模型按年划分阶段，k=1,2,...,5清华大学出版13进行各阶段的计算采用逆序法，设当k=5时，S5=(5,6,7,8)，由表3-1得到当k=4时，S4=(5,6,7,8)，由递推方程得清华大学出版社进行各阶段的计算采用逆序法，设清华大学出版社14继续求解清华大学出版社继续求解清华大学出版社15反推得最优路线按照与求最优值函数方向相反的顺序求最优状态路线：最优决策变量。即从第一年单价应为8元开始，向后推算。得第二年定价8元，第三年定价7元，第四年定价6元，第五年定价5元。最大利润值为92万元。清华大学出版社反推得最优路线按照与求最优值函数方向相反的顺序求最优状态路线16用决策图求解清华大学出版社用决策图求解清华大学出版社17二、资源分配问题某公司将5台加工中心分配给甲、乙、丙、丁四个工厂，各工厂或设备后可产生如表3-2所示的利润，应怎么分配设备可使公司总利润最大？清华大学出版社二、资源分配问题某公司将5台加工中心分配给甲、乙、丙、丁四个18工厂设备数甲乙丙丁012345067101215037912130510111111046111212清华大学出版社工厂甲乙丙丁00000清华大学出版社19建立数学模型按工厂次序划分阶段，k=1，2，3，4状态变量为各阶段可用于分配的设备总台数决策变量是分配给第k工厂的设备数采用逆序算法，状态转移方程最优值函数递推方程清华大学出版社建立数学模型按工厂次序划分阶段，k=1，2，3，4清华大学出20第4阶段的最优解当k=4时，S4=(0,1,2,3,4,5)012345012345046111212046111212012345清华大学出版社第4阶段的最优解当k=4时，S4=(0,1,2,3,4,5)21第3阶段的最优解当k=3时，S3=(0,1,2)000000010105404551201205106406910102清华大学出版社第3阶段的最优解当k=3时，S3=(0,1,2)00000022第3阶段的最优解（续）当k=3时，S3=3301230510111164011111411142清华大学出版社第3阶段的最优解（续）当k=3时，S3=330011111423第3阶段的最优解（续）当k=3时，S3=44012340510111112116401216161511161，2清华大学出版社第3阶段的最优解（续）当k=3时，S3=440012121624第3阶段的最优解（续）当k=3时，S3=550123450510111111121211640121721171511212清华大学出版社第3阶段的最优解（续）当k=3时，S3=550012122125第2阶段的最优解当k=2时，S2=(0,1,2)000000010103505350201203710501087100清华大学出版社第2阶段的最优解当k=2时，S2=(0,1,2)00000026第2阶段的最优解（续）当k=2时，S2=33012303791410501413129140清华大学出版社第2阶段的最优解（续）当k=2时，S2=330014141427第2阶段的最优解（续）当k=2时，S2=4401234037912161410501617171412171，2清华大学出版社第2阶段的最优解（续）当k=2时，S2=440016161728第2阶段的最优解（续）当k=2时，S2=55012345037912132116141050211921191715210，2清华大学出版社第2阶段的最优解（续）当k=2时，S2=550021212129第1阶段的最优解（续）当k=1时，S1=5

50123450671012152117141050212321201715231清华大学出版社第1阶段的最优解（续）当k=1时，S1=55030第4阶段的最优解当k=4时，S4=(0,1,2,3,4,5)012345012345046111212046111212012345清华大学出版社第4阶段的最优解当k=4时，S4=(0,1,2,3,4,5)31反向求最佳状态路线方案一方案二工厂名分配设备数工厂名分配设备数甲乙丙丁1121甲乙丙丁1220清华大学出版社反向求最佳状态路线方案一方案二工厂名分配设备数工厂名分配设备32三、生产存储问题某公司生产并销售某产品。根据市场预测，今后四个月的市场需求量如表3-7所示。时期（月）需求量（dk）12342324清华大学出版社三、生产存储问题某公司生产并销售某产品。根据市场预测，今后四33已知的其它条件已知生产一件产品的成本是1千元，每批产品的生产准备成本是3千元，每月仅能生产一批，每批6件。每件存储成本为0.5千元，且第一个月初无存货，第四个月末的存货要求为零。求最优（最低成本）生产与存储计划。设第k月的生产量uk，存储量为Sk,则总成本为清华大学出版社已知的其它条件已知生产一件产品的成本是1千元，每批产品的生产34建立数学模型以月划分阶段，k=1,2,3,4各阶段决策变量为该阶段生产量uk，状态变量为该阶段存储量Sk。采用逆序算法，则状态转移方程为最低成本递推公式是清华大学出版社建立数学模型以月划分阶段，k=1,2,3,4清华大学出版社35第四阶段的最优解当k=4时，d4=4,因地四阶段末无存货，因此S4=(0,1,2,3,4)S4u4本期成本C4S5f5(S5)f4(S4)生产存储01234432107654000.511.5276.565.52000000000076.565.52清华大学出版社第四阶段的最优解当k=4时，d4=4,因地四阶段末无存货，因36第三阶段最优解当k=3时，由于，且第三阶段需求量d3=2，S3=(0,1,2,3,4,5,6)S3u3本期成本C3S4f4(S4)f3(S3)生产存储0234565678900000567890123476.565.521212.51313.511清华大学出版社第三阶段最优解当k=3时，由于，且第三阶段37第三阶段最优解:S3=1S3u3本期成本C3S4f4(S4)f3(S3)生产存储112345456780.50.50.50.50.54.55.56.57.58.50123476.565.5211.512.012.513.010.5清华大学出版社第三阶段最优解:S3=1S3u3本期成本C3S4f4(S4)38第三阶段最优解:S3=2S3u3本期成本C3S4f4(S4)f3(S3)生产存储2012340456711111156780123476.565.52811.512.012.510.0清华大学出版社第三阶段最优解:S3=2S3u3本期成本C3S4f4(S4)39第三阶段最优解:S3=3,4S3u3本期成本C3S4f4(S4)f3(S3)生产存储3012304561.51.51.51.51.55.56.57.512346.565.52811.512.09.5401204522226723465.52811.59清华大学出版社第三阶段最优解:S3=3,4S3u3本期成本C3S4f4(S40第三阶段最优解:S3=5,6S3u3本期成本C3S4f4(S4)f3(S3)生产存储501042.52.52.56.5345.5288.560033425清华大学出版社第三阶段最优解:S3=5,6S3u3本期成本C3S4f4(S41第二阶段最优解当k=2时，d2=3，由于最生产能力为6，而d1=2，因此S2=(0,1,2,3,4)S2u2本期成本C2S3f3(S3)f2(S2)生产存储03456678900006789012311.010.58.08.01717.51617清华大学出版社第二阶段最优解当k=2时，d2=3，由于最生产能力为6，而d42第二阶段最优解:S2=1S2u2本期成本C2S3f3(S3)f2(S2)生产存储123456567890.50.50.50.50.55.56.57.58.59.50123411.010.58.08.08.016.51715.516.517.5清华大学出版社第二阶段最优解:S2=1S2u2本期成本C2S3f3(S3)43第二阶段最优解:S2=2S2u2本期成本C2S3f3(S3)f2(S2)生产存储2123456456789111111567891001234511.010.58.08.08.08.016.016.515.016.017.018.0清华大学出版社第二阶段最优解:S2=2S2u2本期成本C2S3f3(S3)44第二阶段最优解:S2=3S2u2本期成本C2S3f3(S3)f2(S2)生产存储3012345604567891.51.51.51.51.51.51.51.55.56.57.58.59.510.5012345611.010.58.08.08.08.05.012.516.014.515.516.517.515.5清华大学出版社第二阶段最优解:S2=3S2u2本期成本C2S3f3(S3)45第二阶段最优解:S2=4S2u2本期成本C2S3f3(S3)f2(S2)生产存储4012345045678222222267891012345610.58.08.08.08.05.012.51415161715清华大学出版社第二阶段最优解:S2=4S2u2本期成本C2S3f3(S3)46第一阶段最优解当k=1时，d1=2，S1=0S1u1本期成本C1S2f2(S2)f1(S1)生产存储0234565678900000567890123416.015.515.012.512.52121.52220.521.5清华大学出版社第一阶段最优解当k=1时，d1=2，S1=0S1u1本期成本47最优解从第一阶段向后反推最优路线，总结可得时期K期初存货期末存货最优生产量该期成本总成本SkSk+1123403043040506081.59220.512.5112清华大学出版社最优解从第一阶段向后反推最优路线，总结可得时期期初存货期末存48四.背包问题：[例3-5]现有一辆货车，最大运载量为10吨。准备用它装载三种货物，每种货物的单位重量及相应单位价值如表3—13。问如何装载可以使总价值最大？试用动态规划方法求解。清华大学出版社四.背包问题：[例3-5]现有一辆货车，最大运载量为149表3-13货物编号123单位重量（吨）345单位价值Ci

456清华大学出版社表3-13货物编号123单位重量（吨）3450解：设装载第i种货物的件数为（i=1,2,3）,则该问题的整数线性规划方程为:0,且为整数(i=1,2,3)。清华大学出版社解：设装载第i种货物的件数为（i=1,2,3）,则该问题的51按动态规划要求确定以下参数将装载问题按3种货物分为三个阶段，每阶段装载一种货物。各阶段的状态参数取为在各阶段还可以装载的重量。各阶段的决策变量取为该阶段装载货物的数量。决策变量的允许集合清华大学出版社按动态规划要求确定以下参数清华大学出版社52状态转移方程：阶段指标函数：最优指标函数：=边界条件清华大学出版社状态转移方程：清华大学出版社5300000+00010010+00020020+00030030+00040040+00050106500+06166010661061670106720616清华大学出版社00000+00010010+00020020+00030054801068306169010694061610012061210500612212清华大学出版社800801690090161000100212清华大学出版5500000+00010010+00020020+00030030+00040105400+05+015501055165+00660105620+65+00670105730+65+006清华大学出版社00000+00010010+00020020+00030056801205108400+65+010+0102901205109510+65+610+011110012051010620+125+610+0120清华大学出版社80080+610290090+61111000100+1257表3-16第一阶段计算表1000100+122131474+62848+5312112+0清华大学出版社表3-16第一阶段计算表1000100+12213147458五设备更新问题[例3-6]设某台新设备的年收益及年均维修费，更新净费用如下表3-17所示，试作今后5年内的更新决策使总效益最大：清华大学出版社五设备更新问题[例3-6]设某台新设备的年收益及年均维59役龄012345效益rk(t)54.543.7532.5维修费wk(t)0.511.522.53更新费Ck(t)0.51.52.22.533.5项目清华大学出版社役龄012345效益rk(t)54.543.7532.560按动态规划要求确定以下参数（1）将设备更新问题按今后5年分为K=5个阶段，（2）各阶段的状态参数取为第K年初，设备已使用过的年限，=[0,1,2,3,4,5]。（3）各阶段的决策变量只有两个:(保留)或(更新)（4）状态转移方程：清华大学出版社按动态规划要求确定以下参数（1）将设备更新问题按今后5年分为61续（5）阶段指数函数：（6）最优指标函数：清华大学出版社续（5）阶段指数函数：清华大学出版社62下面进行分阶段计算当K=5，S5=（1，2，3，4）清华大学出版社下面进行分阶段计算当K=5，清华大学出版社63表3-18第五阶段计算表1KR4.5-1=3.55-0.5-1.5=3K3.52KR4-1.5=2.55-0.5-2.2=2.3K2.53KR3.75-2=1.755-0.5-2.5=2R24KR3-2.5=0.55-0.5-3=1.5R1.5清华大学出版社表3-18第五阶段计算表1K4.5-1=3.5K3.5264当K=4，S4=（1，2，3）清华大学出版社当K=4，清华大学出版社65表3-19第四阶段计算表1KR4.5-1+2.5=65-0.5-1.5+3.5=6.5R6.52KR4-1.5+2=4.55-0.5-2.2+3.5=5.8R5.83KR3.75-2+1.5=3.255-0.5-2.5+3.5=5.5R5.5清华大学出版社表3-19第四阶段计算表1K4.5-1+2.5=6R6.5661KR4.5-1+5.8=9.35-0.5-1.5+6.5=9.5R9.52KR4-1.5+5.5=8.55-0.5-2.2+6.5=8.8R8.8表3-20第三阶段计算表清华大学出版社1K4.5-1+5.8=9.3R9.52K4-1.5+5.567当K=3，S3=（1，2）清华大学出版社当K=3，清华大学出版社68表3-21第二阶段计算表1KR4.5-1+8.8=12.35-0.5-1.5+9.5=12.5R12.5表3-22第一阶段计算表0KR5-0.5+12.5=175-0.5-0.5+12.5=16.5K17清华大学出版社表3-21第二阶段计算表1K4.5-1+8.8=12.369六可靠性问题某电子系统由若干个部件串联而成，如果其中一个部件失灵整个系统便会失灵。为了提高整个系统的可靠性，各部件可以采用并联相同元件的设计方案。例如部件1可以由若干个元件并联而成。这样部件1的可靠性就提高了，但同时成本也增加了。那么在整个系统成本是有定额的情况下，如何设计并联方案（即各部件分别由多少相同元件并联而成）才能使整个系统的可靠性最大，这就是一个系统可靠性优化的问题。这样的问题可以用下面的非线性规划模型来描写。清华大学出版社六可靠性问题某电子系统由若干个部件串联而成，如果其中一个部70并联元件的数目部件1部件2部件3部件410.70.50.70.620.80.70.90.730.90.80.950.9表3-24成本表并联元件的数目部件1部件2部件3部件4110201020220403030330504040清华大学出版社并联元件的数目部件1部件2部件3部件410.70.50.7071可靠性问题的非线性规划模型

且为整数，ｉ＝1，2……n清华大学出版社可靠性问题的非线性规划模型清华大学出版社72按动态规划要求确定以下的参数（1）按构成系统的部件数量，确定动态规划有4个阶段，即k=4（2）各阶段的状态参数为在各阶段可用的成本总值。即在第k阶段允许使用的总费用。（3）各阶段的决策变量为第k个部件采用的元件数。

清华大学出版社按动态规划要求确定以下的参数（1）按构成系统的部件数量，确73（续）（4）状态转换方程为（5）最优指数函数（6）边界条件清华大学出版社（续）（4）状态转换方程为清华大学出版社74下面进行各界段的计算k=4，清华大学出版社下面进行各界段的计算k=4，清华大学出版社75表3-25第四阶段计算表k=4S4u4=x4p4（S4）p4（S4）·f5（S5）F4(s4)uk*0≤S4≤190000020≤S4≤290100.600.60.6130≤S4≤3901200.60.700.60.70.7240≤S4≤100012300.60.70.900.60.70.90.93清华大学出版社表3-25第四阶段计算表k=4S4u4=x4p4（S476表3-26第三阶段计算表k=3S3u3=x3P3（x3）S4f4（S4）P3（x3）·f4（S4）u3*0≤S3≤2910.710≤S4≤190030≤S3≤39120.70.920≤S4≤290≤S4≤90.600.7×0.6=0.420140≤S3≤491230.70.90.9530≤S4≤3910≤S4≤190≤S4≤90.7000.7×0.7=0.4900150≤S3≤591230.70.90.9540≤S4≤4920≤S4≤2910≤S4≤190.90.600.7×0.9=0.630.9×0.6=0.541清华大学出版社表3-26第三阶段计算表k=3S3u3=x3P77表3-26第三阶段计算表k=3（续）S3u3=x3P3（x3）S4f4（S4）P3（x3）·f4（S4）u3*60≤S3≤691230.70.90.9550≤S4≤5930≤S4≤3920≤S4≤290.90.70.60.7×0.9=0.630.9×0.7=0.630.95×0.6=0.571.270≤S3≤791230.70.90.9560≤S4≤6940≤S4≤4930≤S4≤390.90.90.70.7×0.9=0.630.9×0.9=0.810.95×0.7=0.665280≤S3≤1001230.70.90.9570≤S4≤7950≤S4≤5940≤S4≤490.90.90.90.7×0.9=0.630.9×0.9=0.810.95×0.9=0.8553清华大学出