运筹学 动态规划ppt课件.ppt

清华大学出版社,管理运筹学教程第三章 动态规划,清华大学出版社,图3-1,清华大学出版社,名词解释,阶段，用k表示。状态、状态变量，用Sk表示，通常是集合决策、决策变量，通常用uk或xk表示。状态转移及其方程：过程与子过程策略与子策略：指标函数与最优值函数：,清华大学出版社,二、最优化原理与动态规划的基本方法,Bellman原理动态规划的基本方法逆向顺序法前向顺序法,清华大学出版社,Bellman原理示意图,清华大学出版社,逆向顺序法求解例3-2,清华大学出版社,第二节 动态规划建模与求解步骤,建立动态规划模型的基本要求动态规划的求解步骤,清华大学出版社,一、建立动态规划模型的基本要求,将问题划分成若干阶段。有的问题的阶段性很明显，有的则不明显，需要分析后人为假设。确定各阶段的状态变量，并给出状态转移方程，状态转移方程的形式应当与递推顺序一致。状态变量应当满足无后效性要求。明确指标函数，给出最优函数递推方程，递推方程的形式应当与递推顺序一致。,清华大学出版社,二、动态规划的求解步骤,正确划分阶段。确定状态变量和决策变量，并给出状态变量和决策变量的可行集合。确定求解的递推顺序，给出状态转移方程。确定阶段、子过程(子策略)的指标函数，确定最优值函数的递推方程和边界条件。递推求解。与递推过程反向求出最优策略(最优决策变量值系列)和最优状态变化路线。,清华大学出版社,第三节 动态规划的应用举例,定价问题资源分配问题生产存储问题,清华大学出版社,一、定价问题,某公司考虑为某新产品定价，该产品的单价拟从每件5元、6元、7元和8元这四个中选取一个，每年允许价格有1元幅度的变动，该产品预计畅销五年，据预测不同价格下各年的利润如表3-1所示。,清华大学出版社,表3-2 每年预计利润额,清华大学出版社,建立数学模型,按年划分阶段，k=1,2,.,5每阶段的状态变量为本年(上一年已确定)的价格，状态变量的可行集合Sk=(5,6,7,8)。决策变量为每年依据当年价格为下一年度决定价格，根据题意决策变量的可行集合是：采用逆序算法，因此状态转移方程是最优值函数递推方程为,清华大学出版社,进行各阶段的计算,采用逆序法，设 当k=5时，S5=(5,6,7,8)，由表3-1得到当k=4时， S4=(5,6,7,8)，由递推方程得,清华大学出版社,继续求解,清华大学出版社,反推得最优路线,按照与求最优值函数方向相反的顺序求最优状态路线：最优决策变量。即从第一年单价应为8元开始，向后推算。得第二年定价8元，第三年定价7元，第四年定价6元，第五年定价5元。最大利润值为92万元。,清华大学出版社,用决策图求解,清华大学出版社,二、资源分配问题,某公司将5台加工中心分配给甲、乙、丙、丁四个工厂，各工厂或设备后可产生如表3-2所示的利润，应怎么分配设备可使公司总利润最大？,清华大学出版社,清华大学出版社,建立数学模型,按工厂次序划分阶段，k=1，2，3，4状态变量为各阶段可用于分配的设备总台数决策变量是分配给第k工厂的设备数采用逆序算法，状态转移方程最优值函数递推方程,清华大学出版社,第4阶段的最优解,当k=4时，S4=(0,1,2,3,4,5),清华大学出版社,第3阶段的最优解,当k=3时，S3=(0,1,2),清华大学出版社,第3阶段的最优解（续）,当k=3时，S3=3,清华大学出版社,第3阶段的最优解（续）,当k=3时，S3=4,清华大学出版社,第3阶段的最优解（续）,当k=3时，S3=5,清华大学出版社,第2阶段的最优解,当k=2时，S2=(0,1,2),清华大学出版社,第2阶段的最优解（续）,当k=2时，S2=3,清华大学出版社,第2阶段的最优解（续）,当k=2时，S2=4,清华大学出版社,第2阶段的最优解（续）,当k=2时，S2=5,清华大学出版社,第1阶段的最优解（续）,当k=1时，S1=5,清华大学出版社,第4阶段的最优解,当k=4时，S4=(0,1,2,3,4,5),清华大学出版社,反向求最佳状态路线,清华大学出版社,三、生产存储问题,某公司生产并销售某产品。根据市场预测，今后四个月的市场需求量如表3-7所示。,清华大学出版社,已知的其它条件,已知生产一件产品的成本是1千元，每批产品的生产准备成本是3千元，每月仅能生产一批，每批6件。每件存储成本为0.5千元，且第一个月初无存货，第四个月末的存货要求为零。求最优（最低成本）生产与存储计划。设第k月的生产量uk，存储量为Sk,则总成本为,清华大学出版社,建立数学模型,以月划分阶段，k=1,2,3,4各阶段决策变量为该阶段生产量uk，状态变量为该阶段存储量Sk。采用逆序算法，则状态转移方程为最低成本递推公式是,清华大学出版社,第四阶段的最优解,当k=4时，d4=4,因地四阶段末无存货，因此S4=(0,1,2,3,4),清华大学出版社,第三阶段最优解,当k=3时，由于 ，且第三阶段需求量d3=2，S3=(0,1,2,3,4,5,6),清华大学出版社,第三阶段最优解:S3=1,清华大学出版社,第三阶段最优解:S3=2,清华大学出版社,第三阶段最优解:S3=3,4,清华大学出版社,第三阶段最优解:S3=5,6,清华大学出版社,第二阶段最优解,当k=2时，d2=3，由于最生产能力为6，而d1=2，因此S2=(0,1,2,3,4),清华大学出版社,第二阶段最优解:S2=1,清华大学出版社,第二阶段最优解:S2=2,清华大学出版社,第二阶段最优解:S2=3,清华大学出版社,第二阶段最优解:S2=4,清华大学出版社,第一阶段最优解,当k=1时，d1=2，S1=0,清华大学出版社,最优解,从第一阶段向后反推最优路线，总结可得,清华大学出版社,四. 背包问题：,例3-5 现有一辆货车，最大运载量为10吨。准备用它装载三种货物，每种货物的单位重量及相应单位价值如表313。问如何装载可以使总价值最大？试用动态规划方法求解。,清华大学出版社,表3-13,清华大学出版社,解： 设装载第i种货物的件数为（i=1,2,3）,则该问题的整数线性规划方程为: 0,且为整数(i=1,2,3)。,清华大学出版社,按动态规划要求确定以下参数将装载问题按3种货物分为三个阶段，每阶段装载一种货物。各阶段的状态参数取为在各阶段还可以装载的重量。各阶段的决策变量取为该阶段装载货物的数量。决策变量的允许集合,清华大学出版社,状态转移方程：阶段指标函数：最优指标函数： =边界条件,清华大学出版社,清华大学出版社,清华大学出版社,清华大学出版社,清华大学出版社,表3-16 第一阶段计算表,清华大学出版社,五 设备更新问题,例3-6 设某台新设备的年收益及年均维修费，更新净费用如下表3-17所示，试作今后5年内的更新决策使总效益最大：,清华大学出版社,项目,清华大学出版社,按动态规划要求确定以下参数,（1）将设备更新问题按今后5年分为K=5个阶段， （2）各阶段的状态参数取为第K年初，设备已使用过的年限，=0,1,2,3,4,5。（3）各阶段的决策变量只有两个: (保留)或 (更新)（4）状态转移方程：,清华大学出版社,续,（5）阶段指数函数：（6）最优指标函数：,清华大学出版社,下面进行分阶段计算,当K=5 ，S5=（1，2，3，4）,清华大学出版社,表3-18 第五阶段计算表,清华大学出版社,当K=4，S4=（1，2，3）,清华大学出版社,表3-19 第四阶段计算表,清华大学出版社,表3-20 第三阶段计算表,清华大学出版社,当K=3，S3=（1，2）,清华大学出版社,表3-21 第二阶段计算表,表3-22 第一阶段计算表,清华大学出版社,六 可靠性问题,某电子系统由若干个部件串联而成，如果其中一个部件失灵整个系统便会失灵。为了提高整个系统的可靠性，各部件可以采用并联相同元件的设计方案。例如部件1可以由若干个元件并联而成。这样部件1的可靠性就提高了，但同时成本也增加了。那么在整个系统成本是有定额的情况下，如何设计并联方案（即各部件分别由多少相同元件并联而成）才能使整个系统的可靠性最大，这就是一个系统可靠性优化的问题。这样的问题可以用下面的非线性规划模型来描写。,清华大学出版社,表3-24 成本表,清华大学出版社,可靠性问题的非线性规划模型,且为整数，1，2n,清华大学出版社,按动态规划要求确定以下的参数,（1） 按构成系统的部件数量，确定动态规划有4个阶段，即k=4（2） 各阶段的状态参数为在各阶段可用的成本总值。即在第k阶段允许使用的总费用。（3） 各阶段的决策变量为第k个部件采用的元件数 。,清华大学出版社,（续）,（4） 状态转换方程为（5） 最优指数函数 （6） 边界条件,清华大学出版社,下面进行各界段的计算,k=4，,清华大学出版社,表3-25 第四阶段计算表 k=4,清华大学出版社,表3-26 第三阶段计算表 k=3,清华大学出版社,表3-26 第三阶段计算表 k=3（续）,清华大学出版社,表3-27 第二阶段计算表 k=2,清华大学出版社,表3-27 第二阶段计算表 k=2(续）,清华大学出版社,表3-28 第一阶段计算表 k=1,所以最优决策：,