大学动态规划方法简介.pptx

动态规划是现代企业管理中的一种重要决策方法,可用于最优路径问题、资源分配问题、生产计划和库存问题、投资问题、装载问题、排序问题及生产过程的最优控制等。,他们可以按时间顺序分解成若干相互联系的阶段,在每个阶段都要做出决策,全部过程的决策是一个决策序列,所以多阶段决策问题也称为序贯决策问题。动态规划的基本原理dae_meng12n状态决策状态决策状态状态决策图示多阶段决策问题,不论其本身是否与时间有关,由于分为阶段依次解决,这便具有明显的时序性,而在各阶段中所采取的决策是随阶段而变动的,不同阶段采取不同决策,,但动态规划在一定条件下也可以解决一些与时间无关的静态最优化问题,只要人为地引入“时段”因素,就可以将其转化为一个多阶段决策问题。dae_meng动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于,它可以把一个n维决策问题变换为几个一维最优化问题,从而一个一个地去解决。需指出:动态规划是求解某类问题的一种方法,是考察问题的一种途径,而不是一种算法。必须对具体问题进行具体分析,运用动态规划的原理和方法,建立相应的模型,然后再用动态规划方法去求解。dae_meng二、多阶段决策问题举例1)工厂生产过程:由于市场需求是一随着时间而变化的因素,因此,为了取得全年最佳经济效益,就要在全年的生产过程中,逐月或者逐季度地根据库存和需求情况决定生产计划安排。dae_meng2)设备更新问题:一般企业用于生产活动的设备,刚买来时故障少,经济效益高,即使进行转让,处理价值也高,随着使用年限的增加,就会逐渐变为故障多,维修费用增加,可正常使用的工时减少,加工质量下降,经济效益差,并且,使用的年限越长、处理价值也越低,自然,如果卖去旧的买新的,,使总的经济效益最好。dae_meng3)连续生产过程的控制问题:一般化工生产过程中,常包含一系列完成生产过程的设备,前一工序设备的输出则是后一工序设备的输入,因此,应该如何根据各工序的运行工况,控制生产过程中各设备的输入和输出,以使总产量最大。dae_mengdae_meng4)运输网络问题(最短路问题):如图1所示的运输网络,点间连线上的数字表示两地距离(也可是运费、时间等),要求从v1至v10的最短路线。这种运输网络问题也是静态决策问题。但是,按照网络中点的分布,可以把它分为4个阶段,而作为多阶段决策问题来研究。dae_meng以上所举问题的发展过程都与时间因素有关,阶段的划分常取时间区段来表示,并且各个阶段上的决策往往也与时间因素有关,这就使它具有了“动态”的含义,所以把处理这类动态问题的方法称为动态规划方法。不过,实际中尚有许多不包含时间因素的一类“静态”决策问题,就其本质而言是一次决策问题,是非动态决策问题,但是也可以人为地引入阶段的概念当作多阶段决策问题,应用动态规划方法加以解决。dae_meng