文档介绍：第十章动态规划
动态规划(Dynamic Programming,简称DP)是一种解决多阶段决策过程最优化问题的一种的方法。该方法是由美国数学家贝尔曼()等人在本世纪50年代初提出的。他们针对多阶段决策问题的特点,提出了解决这类问题的最优化原理,把比较复杂的问题划分成若干阶段,并且逐段解决而最终达到全局最优。1957年,“动态规划”。
动态规划是现代企业管理中的一种重要决策方法,可用于解决最优路径问题、资源分配问题、生产调度问题、库存问题、排序问题及设备更新问题等。许多问题用动态规划方法求解常比线性规划或非线性规划更有效,特别对那些变量为离散型的问题,运用解析数学的方法往往不易奏效,而运用动态规划方法却能使问题迎刃而解。
根据时间参量是离散的变量还是连续的变量,可以把动态规划的模型分为离散决策过程和连续决策过程;根据决策过程的演变是确定性的还是随机性的,动态规划可分为确定性的决策过程和随机性的决策过程,组合起来就有离散确定性、离散随机性、连续确定性、连续随机性四种决策过程。
本章包含三部分的内容:
第一部分:多阶段决策过程最优化问题举例
第二部分:基本概念、基本原理
第三部分:动态规划应用——动态规划模型的建立和求解。
§1、多阶段决策过程最优化问题
1、1多阶段决策问题的概念
在经营管理中,有一些经营活动的过程,可划分为若干个相互联系的阶段。在每个阶段都要做出决策,而一个阶段的决策不仅影响本阶段的活动,还会影响下一阶段的活动及其决策,从而影响整个决策过程。各阶段的决策构成一个决策序列,称为一个策略,由于各阶段可采取诸多不同的决策,因此一个多阶段决策问题相应便有很多策略可供选择,那么在诸多可供选择的策略中,选择哪一策略才能取得最佳效果呢?这类问题就称为多阶段决策问题。
很多多阶段决策问题,各个阶段采取的决策一般来说与时间有关,随着时间的发展而决定各阶段的决策,产生一个决策序列,因此这类决策过程有“动态”的含义。对一些与时间无关的静态问题,只要在问题中人为地引入“时间因素”,即可将问题看成多阶段决策问题。
2、2为了具体了解这类问题的特点,下面举几个例子
例1 最短路线问题。
一个线路网络图,从A到E要修建一条石油管道,必须在B、C、D处设立加压站。各边上的数为长度,现需要找一条路使总长度最短。
例2 设备平行分配问题
某公司现有Q台设备,要分配给4个不同的车间,不同车间分配到不同数量的设备后,可以取得不同的利润。问如何分配设备,可使该公司取得的利润最大。
这是一个4阶段决策问题。
例3 机器负荷分配问题
某种机器可以在高低两种不同的负荷下进行生产。
在高负荷下进行生产时,产品的年产量g和投入生产的机器数量 U1 的关系为g=g(U1),这时,机器的年完好率为a,即如果年初完好机器的数量为u,到年终时完好的机器为au ,0<a<1 ,。在低负荷下生产时,产品的年产量h和投入生产的机器数量U2的关系为h=h(U2),相应的机器年完好率为b,0<b<1。