动态规划习题

1、第七章动态规划规划问题得最终目得就就是确定$决策变量得取值,以使目标函数达到极大或极小。在 线性规划与非线性规划中,决策变量都就是以集合得形式被一次性处理得;然而，有时我们也 会面对决策变量需分期、分批处理得多阶段决策问题。所谓多阶段决策问题就是指这样一类 活动过程：它可以分解为若干个互相联系得阶段，在毎一阶段分别对应着一组可供选取得决 策集合;即构成过程得每个阶段都需要进行一次决策得决策问题。将$个阶段得决策综合起 来构成一个决策序列，称为一个策略。显然，由于齐个阶段选取得决策不同，对应整个过程可以 有一系列不同得策略。当过程采取某个具体策略时，相应可以得到一个确建得效果，采取不同 得策略，

2、就会得到不同得效果。多阶段得决策问题，就就是要在所有可能采取得策略中选取一 个最优得策略，以便得到最佳得效果。动态规划dynami c pro呂zwm”加g)同前面介绍过得$ 种优化方法不同，它不就是一种算法，而就是考察问题得一种途径。动态规划就是一种求解 多阶段决策问题得系统技术，可以说它横跨整个规划领域(线性规划与非线性规划)。当然，由 于动态规划不就是一种特左得算法，因而它不象线性规划那样有一个标准得数学表达式与明 确定义得一组规则，动态规划必须对具体问题进行具体得分析处理。在多阶段决策问题中, 有些问题对阶段得划分具有明显得时序性，动态规划得“动态”二字也由此而得需。动态规 划得主要创

3、始人就是美国数学家贝尔曼(Be/ /man). 20世纪40年代末50年代初，当时在兰 徳公司(Ra,u/Corpon,fio)从事研究工作得贝尔曼首先提出了动态规划得概念-1957年贝 尔曼发表了数篇研究论文，并出版了她得第一部著作动态规划九该著作成为了当时唯一得 进一步研究与应用动态规划得理论源泉。196 1年贝尔曼出版了她得第二部著作，并于196 2年同杜瑞佛思(Dreyfu 5)合作岀版了第三部著作。在贝尔曼及其助手们致力于发展与推广 这一技术得同时，其些学者也对动态规划得发展做出了重大得贡献,其中最值得一提得 就是爱尔思(沖r心)与梅特顿仙)。爱尔思先后于196 1年打1964年出版

4、了两部关于动 态规划得著作，并于1964年同尼母霍思尔Nemhanser).威尔德(側加)一道创建了处理分枝、 循环性多阶段决策系统得一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义 得基础性观点，并且对明晰动态规划路径得数学性质做出了巨大得贡献。动态规划在工程技术、经济管理等社会$个领域都有着广泛得应用,并且获得了显著得 效果。在经济管理方面,动态规划可以用来解决最优路径问题、资源分配问题、生产调度问 题、库存管理问题、排序问题、设备更新问题以及生产过程最优控制问题等,就是经济管理 中一种重要得决策技术。许多规划问题用动态规划得方法来处理，常比线性规划或非线性规 划更有效。特别就是

5、对于离散得问题,由于解析数学无法发挥作用，动态规划便成为了一种非 常有用得工具。动态规划可以按照决策过程得演变就是否确怎分为确定性动态规划与随机性动态规划: 也可以按照决策变量得取值就是否连续分为连续性动态规划与离散性动态规划。本教材主 要介绍动态规划得基本概念、理论与方法，并通过典型得案例说明这些理论与方法得应用。7.1 动态规划得基本理论1.1多阶段决策过程得数学描述有这样一类活动过程，英整个过程可分为若丁相互联系得阶段，毎一阶段都要作出相应 得决策，以使整个过程达到最佳得活动效果。任何一个阶段即决策点)都就是由输 入(inpu t)、决策(de cision)、状态转移律(tr a ns

6、f Orm a tion f Uncti On) 输出(o U切u8)构成得，如图7-1 (a)所示。其中输入与输出也称为状态(state),输入称为输入状态， 输出称为输出状态。图7-1由于每一阶段都有一个决策，所以每一阶段都应存在一个衡量决策效益大小得指标函数, 这一指标函数称为阶段指标函数.用呂表示。显然虽就是状态变量S”与决策变量也得函数， 即乳二r（$,也），如图7-1 （b）所示。显然，输出就是输入与决策得函数，即：（7-1）式（7-1）即为状态转移律。在由川个阶段构成得过程里，前一个阶段得输出即为后一个阶段得 输入。1. 2动态规划得基本概念动态规划得数学描述离不开它得一些基本概

7、念打符号，因此有必要在介绍多阶段决策 过程得数学描述得基础上，系统地介绍动态规划得一些基本概念。1. 阶段（S t age）阶段就是过程中需要做出决策得决策点。描述阶段得变量称为阶段变量，常用&来表示。 阶段得划分一般就是根据时间与空间得自然特征来进行得，但要便于将问题得过程转化为 多阶段决策得过程。对于具有N个阶段得决策过程，其阶段变量=，N2. 状态（state）状态表示每个阶段开始所处得自然状况或客观条件，它描述了研究问题过程得状况。状 态既反映前面各阶段系列决策得结局，又就是本阶段决策得一个出发点与依据；它就是外阶 段信息得传递点与结合点。各阶段得状态通常用状态变量6来加以描述。作为状

8、态应具有 这样得性质：如果某阶段状态给立后，则该阶段以后过程得发展不受此阶段以前各阶段状态 得影响。换句话说，过程得历史只能通过当前得状态来彫响未来，当前得状态就是以往历史 得一个总结。这个性质称为无后效性（E力e future is indepcndcn t of the p a st） 或健忘性（f 力 e pr O cess is f O rg e tfu / ）。3. 决策 e cis i on）决策就是指决策者在所而临得若干个方案中做出得选择。决策变量几表示第k阶段得 决策。决策变量山得取值会受到状态G得某种限制，用必（9）表示第&阶段状态为S时决 策变量允许得取值范帀，称为允许决策

9、集合，因而有仇（员）7 （d。4. 状态转移律tr a nsfo rma t i On functi On）状态转格律就是确定由一个状态到另一状态演变过程得方程，这种演变得对应关系记 为 Sn-t Ti （Sz , d o5. 策略（p o licy与子策略sub-p olicy）由所有阶段决策所组成得一个决策序列称为一个策略，具有用个阶段得动态规划问题得 策略可表示为：从某一阶段开始到过程终点为止得一个决策子序列，称为过程子策略或子策略从第k 个阶段超得一个子策略可表示为：6.指标函数指标函数有阶段指标函数丁过程指标函数Z分。阶段指标函数就是对应某一阶段决策 得效率度量，用r （血）来表示；

10、过程指标函数就是用来衡量所实现过程优劣得数S 指标，就是立义在全过程（策略）或后续子过程（子策略）上得一个数量函数，从第k个阶段起 得一个子策略所对应得过程指标函数常用氐来表示，即：构成动态规划得过程指标函数，应具有可分性并满足递推关系;即:这里得表示某种运算，最常见得运算关系有如下二种：(1) 过程指标函数就是貝所包含得各阶段指标函数得“与，即: 于就是(2) 过程指标函数就是英所包含得各阶段指标函数得“枳”，即: 于就是7-最优指标函数从第个阶段起得最优子策略所对应得过程指标函数称为最优指标函数，可以用式(7-2 ) 加以表乔：(7-2)艮中“ opt就是最优化“ opS / 2 5 ti

11、o n ”得缩写，可根据题意取最大“mx”或最小“ m in在不同得问题中，指标函数得含义可能就是不同得，它可能就是距离、利润、成本、产 量或资源量等。1. 3动态规划得数学模型动态规划得数学模型除包括式(7-2)外，还包括阶段得划分、各阶段得状态变量与决 策变量得选取、允许决策集合与状态转移律得确定等。如何获得最优指标函数呢? 一个阶段得决策过程，具有如下一些特性：刚好有个决策点；对阶段而言，除了所处得状态与所选择得决策外,再没有任何其它因素影响决 策得最优性了；阶段仅影响阶段得决策，这一影响就是通过来实现得；贝尔曼Be / Iman)最优化原理:在最优策略得任意一阶段上，无论过去得状态与

12、决策如何,对过去决策所形成得当前状态而言，余下得诸决策必须构成最优子策 略。(1)(3)(4)根据贝尔曼(毗“如最优化原理，可以将式(7-2)表示为递推最优指标函数关系式 (7-3)或式(7-4):(7-3)(7-4)利用式(7-3)打式(7-4)可表示出最后一个阶段(第W个阶段,EP k-V)得最优指标函数:(7-5)(76)K中称为边界条件。一般情况下，第阶段得输出状态已经不再影响本过程得策略即式(7- 5)中得边界条件，式(7-6)中得边界条件;但当问题第阶段得输出状态对本过程得策略产生 某种影响时，边界条件就要根据问题得具体情况取适当得值这一情况将在后续例题中加以 反映。已知边界条件，

13、利用式(7-3)或式(7-4 )即可求得最后一个阶段得最优指标函数；有 了，继续利用式(7-3)或式(7-4)即可求得最后两个阶段得最优指标函数；有了，进一步又 可以求得最后三个阶段得最优指标函数;反复递推下去，最终即可求得全过程个阶段得最优 指标函数，从而便问题得到解决。由于上述最优指标函数得构建就是按阶段得逆序从后向前 进行得，所以也称为动态规划得逆序算法。通过上述分析可以瞧出，任何一个多阶段决策过程得最优化问题，都可以用非线性规划 (特殊得可以用线性规划)模型来描述;因此,从原则上讲，一般也可以用非线性规划(或线 性规划)得方法来求解。那么利用动态规划求解多阶段决策过程有什么优越性、又有

14、什么局限性呢？动态规划得优点:第一,求解更容易、效率更高。动态规划方法就是一种逐步改善法，它 把原问题化成一系列结构相似得最优化子问题，而每个子问题得变量个数比原问题少得多, 约束集合也简单得多，故较易于确左最优解。第二，解得信息更丰富。非线性规划（或线性规 划）得方法就是对问题得整体进行一次性求解得,因此只能得到全过程得解;而动态规划方法 就是将过程分解成多个阶段进行求解得，因此不仅可以得到全过程得解，同时还可以得到所 有子过程得解。动态规划得缺点:第一，没有一个统一得标准模型。由于实际问题不同，英动态规划模 型也就各有差异，模型构建存在一定困难.第二，应用条件苛刻。由于构造动态规划模型状

15、态变量必须满足“无后效性”条件，这一条件不仅依赖于状态转移律，还依赖于允许决策集合 与指标函数得结构，不少实际问题在取英自然特征作为状态变量时并不满足这一条件，这就 降低了动态规划得通用性。第三,状态变量存在“维数障碍”。最优指标函数就是状态变量 得函数，当状态变量得维数增加时，最优指标函数得il 算疑将成指数倍增长；因此，无论就是 手工计算还就是电算“维数障碍都就是无法完全克服得。7、2确定性动态规划问题确定性动态规划问题即阶段得输出状态完全由尖输入状态与决策所决圧得动态规划问 题。确左性动态规划解决得问题可能包含经济管理得方方而面，可以就是最短路线问题，可以 就是资源配置问题，也可以就是其

16、她得规划优化问题。最短路线问题直观、具体地演示了动 态规划得基本概念与基本步骤;因此，让我们首先来分析一下最短路线问题。2-1最短路线问题例7-1美国黑金石油公司（The B / ack Gold Pe trole U m pa刀y）最近在阿拉斯 加Alaska得北斯洛波Norths发现了大得石油储量。为了大规模开发这一油田，首先必须建立相应得输运网络，使北斯洛波生产得原汕能运至美国得3个装运港之一。任油 田得集输站（结点C）与装运港（结点只、A）之间需要若干个中间站，中间站之间得联 通情况如图7-2所示，图中线段上得数字代表两站之间得距离（单位：1 0千米）。试确定一最 佳得输运线路，使原汕

17、得输送距离最短。解:最短路线有一个重要性质，即如果由起点经过万点与C点到达终点0就是一条最短 路线，则由万点经Q点到达终点0_定就是B到0得最短路（贝尔曼最优化原理）。此性质用 反证法很容易证明，因为如果不就是这样，则从巧点到Q点有另一条距离更短得路线存在，不 妨假设为B PD;从而可知路线A -B-PD比原路线A-B-C-D距离短，这与原路线 FTYT就是最短路线相矛盾性质得证0根据最短路线得这一性质，寻找最短路线得方法就就是从最后阶段开始，由后向前逐步 递推求岀各点到终点得最短路线,最后求得由始点到终点得最短路;即动态规划得方法就是 从终点逐段向始点方向寻找最短路线得一种方法。按照动态规划

18、得方法，将此过程划分为4 个阶段，即阶段变量;取过程在各阶段所处得位置为状态变量，按逆序算法求解。当时：由结点3伤到达目得地有两rx-nD g MnPP3M3311PiMil俟弘，到达目得M22选32M3I8择几择刃由结点到达目得地有两条路线可以选择，即选择上或Py;故: 选择Pt当时：由结点见到达下一阶段有三条路线可以选择，即选择环&或如 故： 选择朋2由结点必:到达下一阶段也有三条路线可以选择，即选择弘、Mq或如;故: 选择或心由结点胚,到达下一阶段也有三条路线可以选择，即选择血、血或麵,;故：选择或血当时：由结点妁到达下一阶段有两条路线可以选择，即选择址或Mr:；故： 选择由结点址到达下

19、一阶段也有两条路线可以选择，即选择址或Mm故:选择当时：由结点Q到达下一阶段有两条路线可以选择，即选择M”或故：选择必2从而通过顺序（计算得反顺序）追踪（黑体标示）可以得到两条最佳得输运线路:C-Mn- M22MsiP2,CMuMmMsiPa最短得输送距离就是2 8 0千卷e2-2资源分配问题函数 即G = f J X5 X小、 静态模型加以描述：若”就是严变鼠当Gf（ 2jt ,=f（X打，上丿，脸M）就是线性函数时，该模型就是线性规 就是非线性函数时，该模型就是非线性规划模型。若JT“所谓资源分配问题，就就是将一过数量得一种或若干种资源（如原材料、机器设备、资 金、劳动力等）恰当地分配给若

20、干个使用者，以使资源得到最有效地利用。设有加种资源，总 量分別为矗（，=1,2, 诊，用于生产口种产品，若用jr打代表用于生产第J种产品得第f 种资源得数MO = 1,2,，打），则生产第J种产品得收益就是其所获得得徉种资源数量得 3）。由于总收益就是种产品收益得与，此问题可用如下划模型：当名丿=就是离散变虽或卜与）呂.=f （盟” 5,也）就是离散函数时，此模型用线性规划或非线 性规划来求解都f就是非常麻烦得。然而在此情况下，由于这类问题得特殊结构，可以将它瞧 成为一个多阶段决策问题，并利用动态规划得递推关系来求解。本教材只考虑一维资源得分配问题，设状态变量Sz表示分配于从第k个阶段至过程最

21、 终（第个阶段）得资源数it即第&个阶段初资源得拥有量;决策变量X*表示第&个阶段资 源得分配量.于就是有状态转移律： 允许决策集合: 最优指标函数（动态规划得逆序递推关系式）：用这一递推关系式,最后求得得即为所求问题得最大总收益，下而来瞧一个具体得例子。例72某公司拟将500万元得资本投入所属得甲、乙、丙三个工厂进行技术改造， 外工厂获得投资后年利润将有相应得增长，增长额如表7-1所示。试确定5 0 0万元资本得 分配方案,以使公司总得年利润增长额最大。表7-1投资额】0 0万元2 00万元3 0 0万元10 0万元5 0 0万元甲3乙51 0丙40解:将问题按工厂分为三个阶段，设状态变*(

22、)代表从第个工厂到第3个工厂得投资额, 决策变fi代表第个工厂得投资额。于就是有状态转移率、允许决策集合与递推关系式：当时:于就是有表7-2,表中表示第三个阶段得最优决策。表7-2伸位:百万元)01234501234000. 40. 61、11、21、2当时:于就是有表7-3。表7-3(爪位:百万元&(X2)+ f S ： xj01234500 +00010+0、40、5+00、512OP、60 、 5+0.41. 0+01、0230+ 1、10、5+0、61、 0+0.41 . 1+01、4240+1、20、5+1、11. 0+0、61、 1+0、41、1+01、61,2507、20、5+1

23、、21. 0+1、11、1+ 0.61、1+0、41、1+02、12当时:于就是有表7-4表7-4*1(x2)(si - X1)01234550+2、10、3 +1、60、7+、40、9+1、01、 2+0、01. 3+02、10,2然后按讣算表格得顺序反推算.可知最优分配方案有两个：（1）甲工厂投资2 00万元, 乙工厂投资200万元，丙工厂投资100万元；（2）甲工厂没有投资，乙工厂投资200万元，丙工 厂投资300万元。按最优分配方案分配投资（资源），年利润将增长2 I 0万元。这个例于就是决策变虽取离散值得一类分配问题，在实际问题中，相类似得问题还有销 售店得布局（分配）问题、设备或人

24、力资源得分配问题等。在资源分配问题中,还有一种决策 变量为连续变量得资源分配问题,请见例7-3.例7-3机器负荷分配问题。某种机器可在高低两种不同得负荷下进行生产,设机器 在高负荷下生产得产S（件）函数为，其中为投入高负荷生产得机器数量，年度完好率（年底得 完好设备数等于年初完好设备数得7 0 %）;在低负荷下生产得产S （件）函数为，其中为投入 低负荷生产得机器数呈,年度完好率。假立开始生产时完好得机器数量为1000台，试问每年 应如何安排机器在高、低负荷下得生产,才能使5年生产得产品总量最多？解:设阶段表示年度0；状态变量为第年度初拥有得完好机器数量（同时也就是第年度末 时得完好机器数虽:

25、）。决策变S为第年度分配高负荷下生产得机器数量，于就是为该年度分 配在低负荷下生产得机器数量。这里得与均为连续变量，它们得非整数值可以这样理解:如 就表示一台机器在第年度中正常工作时间只占全部时间得60%：就表示一台机器在第年度中 只有30%得工作时间在高负荷下运转0状态转移方程为：Sz =aq 七 PIS* -xJ = 0.7忑 +O.9（S女-忑）= 0.9S* -O.2x*允许决策集合： 设阶段指标为第年度得产量，则: 过程指标池是阶段指标得与,即: 令最优值函农示从资源量出发，采取最优子策略所生产得产品总量，因而有逆推关系式:边界条件。当时:因就是关于得单调递增函数，故取，相应有。 当

26、时：因就是关于得单调递增函数，故取，相应有;依次类推，可求得：当时：，当时:，当时:，il算结果表明最优策略为:即前两年将全部设备都投入低负荷生产，后三年将全 部设备都投入高负荷生产，这样可以使5年得总产量最大,最大产量就是23 7 00件。有了上述最优策略，各阶段得状态也就随之确崔了，即按阶段顺序计算出各年年初得完 好设备数量.上而所讨论得过程始端状态就是固定得，而终端状态就是自由得,实现得目标函数就是 5年得总产量最奇。如果在终端也附加上一；4得约束条件,如规世在第5年结束时，完好得机 器数量不低于35 0台（上而得例子只有278台），问应如何安排生产，才能在满足这一终端要 求得情况下使产

27、量最高呢？解：阶段表示年度0；状态变量为第年度初拥有得完好机器数量：决策变量为第年度分 配高负荷下生产得机器数量;状态转移方程为：Jt-hlS如=aq + pS 一 xj = 07忑 + 0.9（S女-忑）=0.9S* - 02x*终端约束：允许决策集合：“加”第阶段得终端递推条件 对于，考虑终端递推条件有：同理瓦她各阶段得允许决策集合可在过程指标函数得递推中产生。 设阶段指标： 过程指标: 最优值函数: 边界条件。 当时：因就是关于得单调递增函数，故取，相应有:即: 当时:由可得，又因就是关于得单调递减函数，故取，相应有:当时:由可得，又因就是关于得单调递减函数，故取，相应有:由于，所以就是

28、恒成立得，即。当时:因就是关于得单调递减函数，而得取值并不对有下界得约束，故取，相应有: 当时:因就是关于得单调递减函数，故取，相应有:计算结果表明最优策略为：(1)第1年将全部设备都投入低负荷生产。(2)第2年将全部设备都投入低负荷生产。(3 )第3年将台完好设备投入高负荷生产，将剩余得台完好设备投入低负荷生产。(4)第4年将台完好设备均投入高负荷生产，将剩余得1台完好设备均投入低负荷生产。第5年将，即将台完好设备均投入高负荷生产。2-3存贮控制问题由于供给与需求在时间上存在差异，需要在供给与需求之间构建存贮环节以平衡这种 羞异。存贮物资需要付出资本占用费与保管费等，过多得物资储备意味着浪费

29、;而过少得储备 又会影响需求适成缺货损失。存贮控制问题就就是要在平衡双方得矛盾中，寻找最佳得采购 批量与存贮;以期达到最佳得经济效果。例7-4某鞋店销售一种雪地防潮鞋，以往得销售经历表明，此种鞋得销售季节就是 从10月1日至3月31日。下个销售季节各月得需求预测值如表7-5所示。表7-5仲位:双)刀份101 112123需求4该鞋店得此种鞋完全从外部生产商进货，进货价每双4萸元。进货批量得基本单位就是 箱，每箱10双。由于存贮空间得限制，每次进货不超过5箱。对应不同得订货批量,进价享 受一泄得数量折扣,具体数值如表7-6所示。表76进货批量1箱2箱3箱4箱5箱数S折扣4%5%1 0 %2 0%25%假设需求就是按一泄速度均匀发生得，订货不需时间,但订货只能在月初办理一次，毎次 订货得采购费(打采购数量无关)为10美元。月存贮费按每月月底鞋得存量计，每双0、2 美元。由于订货不需时间，所以销售季节外得貝她月份得存贮量为“0。试确世最佳得进货方案，以使总得销售费用最小。解:阶段：将销售季节6个月中得每一个月作为一个阶段，即： 状态变量:第阶段得状态变量代表第个月初鞋得存量； 决策变量：决策变量代表第个月得采购批量；