（应用数学专业论文）数学建模中的动态规划问题.pdf

摘要 动态规划( d y n 锄i cp r 0 留a m m i n g ) 的方法是二十世纪五十年代提出，并由 理查德贝尔曼( r i c h a r db e l l m a n ) 引入最优化原理，为动态规划奠定了坚实的 基础。在过去五十多年的进程中，动态规划在运筹学、控制论、管理科学等领域 的发展中，都发挥了无可比拟的领军作用，成为解决数学建模问题最常用的优化 方法之一。但是，作为一个重要的最优化方法，它又存在着很多亟待解决的问题 而显得很不完善。因此，在运用这个方法的过程中，人们一直致力于不断完善应 用动态规划的条件以及动态规划问题的求解方法。本文对动态规划在过去五十年 的发展进行了深入研究和综述，特别是注意研究了其各种新产生的算法。诸如确 定型一维动态规划的解析法、计算法等算法；确定型多维动态规划的拉格朗日乘 子、逐次迭代、策略与函数空间近似、多项式逼近、超曲面搜索等算法：随机动 态规划的基本算法等。文章最后通过使用动态规划方法解决一个数学建模问题， 以体现动态规划在实际应用中的优越性。 关键词：动态规划；确定型动态规划；一维动态规划的求解方法；多维动态 规划的处理方法；随机动态规划 a b s t r a c t t h em e t h o do fd y i l 姗i cp r o g r a m m i n gw a so r i 西n a l l yp r o p o s e di nt h e19 5 0 s ，雒l d 烈c h a r db e l l m a ni n t r o d m e di tt h em o s to p t i m i z e dp r i n c i p l ew h i c hh a dl a i das o l i d f o u n d a t i o nf o rt 1 1 em e t l l o d t h ed y n a m i cp r o 目锄m i n gh a sp l a y e dt h em o s ti m p o r 啪t r 0 1 ei nt h ea r e as u c ha so p e r a t i o n sr e s e a r c h ，c y b e m e t i c s ，m a n a g e m e n ts c i e n c e d e v e l o p m e n ti nt h ep a s t5 0v e a r s ，a i l di tb e c 锄eo n eo ft h em o s tc o m m o n l yu s e d o p t i m i z a t i o nf n e m o d si ns o l v i n gm a t h e m a ：t i c sm o d e l l i n gq u e s t i o n s b u ta s髓 i m p o r t a n to p t i m i z e dm e t h o d i th a st o om a n yq u e s t i o n sw h i c hu 唱e n t l ya w a j tt ob e s o l v e dt h a te x p o s ei t si m p e r l b c t i o n t h e r e f o r e ，i nt h ep r o c e s so fu t i l i z i n gt h j sm e t h o d p e o p l eh a v ed e v o t e dal o tt op e r 兜c tt h ec o n d i t i o no fa p p l y i n gd y n a m i cp r o 铲a m m i n g a s 、v e l la s 也es o l u t i o nm e t h o do fd y n 锄i cp r o 掣a m m i n gq u e s t i o n s t m sa n i c l eh a s c o n d u c t e dt h ed e e pr e s e a r c ha n dt h es 啪a 呵t ot h ed y n 锄i cp r 0 伊a m m i n gi nt h e d a s t5 0v e a r s d e v e l o p m e n t ，s p e c i a l l yp a j da t t e n t i o nt ot h es t u d yo fi t sv a o u sn e w l y a l g o r i t i u n s s u c ha st h ea n a l y s i sl a wo fd e t e r m i n i s t i cu n i v 2 u r i a t ed y n 撇i c p i o 汀锄m i n 臣c o m p u t a t i o nm e 也o d ：t h ed e t e m i n i s t i cm u l t i d i m e n s i o n a ld y n a m i c p r o g r a h 吼i n g sl a g r a n g em u l t i p l i e r i 馏砒e s ，t h es 仃a t e g y a j l dt h en m c t i o ns p a c e a p p r o x i m a t i o n ，m em u l t i n o m i a la p p r o a c h e s ，h y p e r s u r f a c e ；t h eb a s ea l g o r i t h mo f s t o c h a s t i cd y n 锄i cp r o g r a m m i n ga n ds oo n a tt h ee n do ft h ea n i c l e ，is 0 1 v e da m a t h e m a t i c sm o d e l l i n gp r o b l e m 也r o u g h 0 r d e rt om a n i f l e s tt ：h e s w 燃i o r 时o f 印p l i c a t i o n t h eu s ed y n 锄i cp r 0 黟a m m i n gm e t h o d ，i n d y n a m i cp r o 掣a m m i t 喀 i nt h ep r a c t i c a l k e yw o r d s ：d y n 锄i cp r o g r a m m i n g ： s 0 1 u t i o nm e t h o do fu n i v a r i a t ed y n a m i c m m t i m m e i l s i o n a ld y n 锄i cp r o g r a m m i n g ； i i d e t e m i i l i s t i cd y n a m i cp r o 娜m i n g ； p r 0 莎锄m i n g ；p r o c e s s i n gm e 也o d0 f s t o c l l a s t i cd ”a m i cp r 0 伊a m m i n g 独创性声明 本人声明所呈交的学位论文是本入在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得东北师范大学或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示谢意。 学位论文作者签名：日期：尘髟哇砂 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即：东 北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和磁盘，允许论 文被查阅和借阅。本人授权东北师范大学可以将学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：始 日 期：趁! 皇：坚：蛰 学位论文作 工作单位： 通讯地址： 指导教师签名垄丝壁 日期：墨笪移f 尘 电话：2 盟壁垒乡 邮编：! 堕竺 东北师范大学硕士学位论文 引言 无庸置疑，理查德贝尔曼( 础c h a r db e l l m a n ) 在二十世纪五十年代提出了 动态规划，引入了决策科学中最具革命性意义的最优化原理，为动态规划奠定了 坚实的基础。在过去五十多年的进程中，动态规划在运筹学、控制论、管理科学 等领域的发展中，都发挥了无可比拟的领军作用，对这些学科的成功影响卓越。 在适用的情况下，动态规划是求解动态决策问题的最有效工具。 值得说明的是，尽管动态规划已广泛应用于解各个领域和各种类型的问题， 但是，作为一个重要的最优化方法，它又存在着很多亟待解决的问题而显得很不 完善。因此，在运用这个方法的过程中，人们一直致力于不断完善应用动态规划 的条件以及动态规划问题的求解方法。作者在研修期间，倾听了导师为研究生开 设的数学模型课程，受到很大的启发，开始了这个方面的研究工作。在翻阅了大 量有关书籍、资料基础之上，对这一新兴的应用数学分支有了深刻的理解，并成 功地将这个方法运用在数学建模领域中。 东北9 币范大学硕士学位论文 第一章绪论 一、动态规划的起源与发展 动态规划是解决多阶段决策过程最优化的一种方法，大约产生于2 0 世纪5 0 年代。1 9 5 1 年，美国数学家理查德贝尔曼根据一类多阶段决策问题的特点， 把多阶段决策问题表示为一系列单阶段问题，即把一个一变量问题作为一系 列的个问题而逐个加以解决，提出了解决这类问题的“最优化原理 ，并将其 应用于很多实际问题的研究，从而建立了运筹学的一个分支一动态规划。1 9 5 7 年理查德贝尔曼在美国普林斯顿大学发表了第一本正式的著作。随后理查德- 贝 尔曼及其他科学工作者发表了一些列动态规划应用的著作，包括动态规划在最佳 控制论、资源理论、工业工程、经济学、管理科学、变分法和马尔柯夫过程中的 应用。动态规划的发展始终伴随着它的广泛应用而不断臻善的。 二、动态规划的优点与局限 动态规划的核心思想是贝尔曼提出的最优化原理，这个原理导致了分阶段决 策的方法。分阶段决策的方法是建立在整体最优化的基础上的，在寻求某一阶段 的决策时，不仅要考虑局部的利益，而且应考虑总体的最优。 动态规划通过将一个维变量的复杂问题进行分阶段处理，把维变量问 题变成求解个单变量问题，大大简化求解过程，节省巨大的计算量，这是经 典的求解极值方法所做不到的。 动态规划几乎超越了所有现在的计算方法，特别是经典最优化方法，它能确 定出绝对( 全局) 极大或极小，而不是相对( 局部) 的极值，使得我们不再需要 关心伤脑筋的局部极大或极小问题。 动态规划的另一特点是泛函方程的“嵌入”特性。动态规划方法求出的不仅 是对整个过程的某一特定状态的一个解，而且也是对所有后部子过程的所有可能 出现状态的一族解。 动态规划方法的局限性表现有以下几个方面： 第一，到目前为止，动态规划还没有一个统一的标准模型可供使用。实际问 题不同，其动态规划模型可能各异，虽然理论上说可以把其他数学规划问题化为 动态规划模型求解，但是这种转化的过程对于复杂的数学规划问题将变得十分困 难。 第二，构造动态规划模型时，状态变量必须满足“无后效性”条件，这是一 个相当强的条件。因为它不仅依赖于状态转移规律，还与允许决策集合和指标的 2 东北师范大学硕士学位论文 结构有关，不少实际问题在取自然特征作为状态变量时，往往不满足这个条件， 减低了动态规划通用性，当然原则上说，采用适当增多状态变量的办法，总能人 为地把过程变为无后效的，但动态规划还存在下述局限，所以这种作法的实际意 义不大。 第三，用动态规划方法进行数值求解时的主要问题是所谓“维数障碍 ，这 里状态变量与决策变量不是一回事。若状态变量大于2 或3 ，计算时涉及较大的 存储量和计算量。状态空间维数越高，即描述状态空间的向量分量越多，所遇到 的计算困难将变得越大。 三、动态规划的术语 研究系统优化时，遇到的系统可以是一个物理系统，也可能是可操作的系统， 也可以是一个概念的系统。但是，使用动态规划来研究系统时，必须将系统的现 实而具体的术语变为数学的统一术语。 阶段 阶段是指系统需要做出决策的步骤，即把系统顺序地向前发展划分为若干个 相互联系的阶段，使能按阶段的次序求解。描述阶段的变量称为阶段变量。在多 数情况下，阶段变量是离散的，用后表示。离散动态规划问题应理解为，阶段过 程结构是离散的，而不是状态变量的结构是离散的。阶段变量的连续情况也是存 在的。当阶段变量为时间，且可在任意的时间做决策时，阶段变量是连续的。阶 段变量的主要作用是按顺序编出所研究过程划分的编号。 状态 状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意识 为转移，也称为不可控因素。 过程的状态通常可以用一个或一组变数描述，称为状态变量。常用屯表示 第七阶段的某一状态。状态变量可以是离散的，也可以是连续的。但是，在现实 世界中，实际上没有连续的变量，或者是由于我们所遇到的就是离散的实体，或 者是由于所有物理测量中所固有的精确度的限制。然而，在处理某些问题时，数 学连续性则是一种有益的假设。状态可以是单变量，也可以是向量，它可以用若 干分量在任何阶段上对系统进行描述。状态变量取值的集合称为状态集合。 我们要求状态具有下面的性质：当前与未来的收益( 或代价) ，将仅仅取决 于当前的状态，并不依赖于过去的状态和决策的历史，即，不依赖于所论过程的 那些过去状态下所做的决策。这个性质称为无后效性。这正是在多阶段决策过程 中表现出来的动态规划的基本理论与特征。 决策 在每一阶段的状态给定后，往往可以作出不同的决定，从而确定下一阶段的 3 东北师范大学硕士学位论文 状态，这种决定称为决策。在最优控制中，也称为控制。描述决策的变量称为决 策变量( 控制变量) 。那么，系统的状态必须包含在某个给定的阶段上确定全部 允许决策所需的全部信息。在第七阶段用以) 表示处于状态以时韵决策变量， 决策变量限制的范围称为允许决策集合。用x 女( 以) 表示第足阶段从五l 出发的决 策集合，则屯仇) 以魄) 。 策略 由每一阶段的决策为瓴x f = l ，2 ，2 ) 组成的决策函数序列称为全过程策略， 简称策略，用p 表示，即 a “) = 冬，( l 屯他l ，( 以) 。 换句话说，策略是在任意阶段做出决策的决策规则的集合。 从后阶段开始到终点的过程称为原过程的后部子过程( 或称七子过程) ，其 决策函数序列k ( 以l + 。魄+ 。l ，矗阮) ) 称为七子过程策略，简称子策略。用 a 魄) 表示，即 a k ) = k ) l 屯+ ，+ 。卜，矗仉) ) 。 对于每个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个 范围称为允许策略集合，允许策略集合中达到最优效果的策略称为最优策略。 状态转移 利用动态规划解决优化问题时，所研究的是逐阶段的决策过程。给定第尼阶 段状态变量以的值后，如果这一阶段的决策变量一经确定，第七+ l 阶段的状态 变量五+ ，也就完全确定，即以“的值随五和以仇) 的值变化而变化，可以把这一 关系看成仇，屯( 九) ) 与 + 。的确定的对应关系，用以+ 。= 瓦仇，( 以) ) 表示。这 是从j i 阶段到七+ l 阶段的状态转移规律，称为状态转移方程。 瓦，坼( 五) ) 是 和& 似) 确定的函数，状态转移是完全确定的。这种状态 转移完全确定的多阶段决策过程称为确定型多阶段决策过程。 历程 从开始到结束的总阶段数称为历程，如果阶段变量从0 变到咒，则历程是 一+ l ，在离散的情形中，根据历程将多阶段决策过程分为： l 、定期多阶段决策过程，在决策之前就已知历程是确定的有限值，进行最 4 东北师范大学硕士学位论文 优化时已知确定的阶段数。 2 、不定期多阶段决策过程，预先知道历程是有限的、确定的，但是在得到 最优策略之前并不知道它的数值。 3 、随机多阶段决策过程。历程是与策略和外部条件有关的随机变量，它的 特点是在方程中没有阶段变量。 4 、无限期多阶段决策过程。历程无限( 或在实践中历程很大) 。 指标函数和最优值函数 用来衡量所实现过程优劣的一种数量指标，称为指标函数。在确定型过程中， 设过程由。开始，由任一七阶段开始0 = 1 ，2 ，) 的过程是原过程的后部子过程。 这时，指标函数y 是定义在原过程和后部子过程上确定的数量函数，即对任一七， 圪仇，魂，以以，小) 是定义在玩，以卅，戈。柏， 上的函数。要构成动态规划模 型，这个函数还需满足递推关系： 圪阮，坼，以，小) = 帆k ，坼，圪h 仇射，工。，) 】。 实际闯题中很多指标函数都满足这个性质。 常见指标函数的性质是： 1 、过程和它的任一子过程的指标是它所包含的各阶段指标之和，即 h - i 珞仇，屯，) = _ “，_ ) ， ，一七 其中_ 也，乃) 表示第阶段的指标这时 圪协，以，) = 唯阮，) + 圪+ 。似小黾+ ，) 。 2 、过程和它的任一子过程的指标是它所包含的各阶段的指标的乘积，即 珞仇，以，) = 什v ，阮。一) ， ，l 七 这时 圪，吼，) = 唯仇，以以+ ，协小工m ，) 。 3 、过程和它的任一子过程的指标是它所包含的各阶段的指标的最小值，即 圪，也，) 2 。墨貔。p ，也，_ ) j ， 这时 圪“，以，) = m i i l 卜。魄，) i 圪+ 。协+ ，坼+ ，) 】。 贝尔曼在多阶段火箭问题中曾经推出满足下列递推关系的指标函数： s 东北师范大学硕士学位论文 圪协，靠，) = 吒+ ，瓴，靠小) + 仇k q ，以h ，) 以+ ，一九】， 其中坼= + ，一五。 从上面的叙述可以看出，在初始状态给定，指标函数是策略确定的函数。指 标函数的最优值称为最优值函数，用g 七) 表示： g t 饥) 2 蹊) 圪仇，) ， 其中缈表示最优。实际问题中取最大时即为m a x ，取最小时即为m i i l 。 四、动态规划的最优化原理 一个最优策略瓴，x 2 ，) 所具有的性质是，不论初状态厶和初决策x 。如 何，剩余的决策如，工，毛) ，对于从第一次决策z 。产生的状态 开始的，那么 剩余g 1 ) 阶段过程也构成一个最优策略。 五、动态规划的基本方程 解决实际问题时，必须建立起动态规划模型。建立模型时，必须做到： l 、将过程进行恰当的分段( 一般根据时间和空间划分) ； 2 、正确选择状态变量以，使它既能描述过程，又满足无后效性： 3 、确定决策变量坼及每个阶段的允许决策集合玩( 五) ； 4 、写出状态转移方程：五柏= 疋，) ； 5 、根据题意写出指标函数圪，它应满足： ( 1 ) 是定义在全过程及所有后部子过程上的数量函数； ( 2 ) 满足递推关系 圪仇，以小小) = 沙k ，。圪+ 。仇小以，) 】： ( ”协，圪+ 。) 对于其变量以+ ，严格单调。通常取指标函数的形式1 ， 即 圪= 艺_ 阮，工，) ， _ 七 其中_ 协，_ ) 表示第阶段的指标，它显然满足上述三个性质，递推关系可以写 成 6 东北师范大学硕士学位论文 圪= v 七，) + 以+ l o 如果初始状态给定且过程策略也确定，则指标函数值也随之确定，即指标函 数的初始状态和策略的函数，记为以k ，仇) 】。所以上面的递推关系可以写成 圪k ，p 。仇) 】= y 。仇，以) + 圪+ 。阮，p m 仇“) 】， 而子策略仇仇) 可以写成由) 和p 七+ 。) 组合而成，即 仇) = “仇) 风+ ，瓴+ 。) 。 如果用( ) 表示初始状态为以的后部子过程所有子策略中的最优子策 略，则最优值函数为 g 。阮) = 圪k ，p ：) j = 叩f 圪阢，仇似) 】， 而 叫圪k ，p 。) 】= ，叫，h 协，) + 圪+ ，仇柚，n q 仇+ 。) ) 】 a t 吩，k + l j 羊叫lv 。，) + 掣l 靠l a + l j 但 所以 f g 量k ) = 9 矽、【v i o k ，屯) + g 。“c k + 。) l = l ，2 ，刀一1 ) 黾t k ( 厶) 【g 。阮) = o 。 这就是动态规划逆序解法的基本方程。 对于顺序解法，如果阶段序数和状态变量五的定义不变，第七阶段的允许决 策集合碟仇+ 。) 定义为 瓴) = k k 群仇) 瓦瓴，) = 以“ ， 或 坼魄+ ，) = 以。 这时一般的状态转移方程不是由以，去确定以+ i ，而是由以+ i 如去确定厶， 即 7 东北师范大学硕士学位论文 以= 巧小吨) 。 所以顺序解法的基本方程是 g t ) _ 铀篡限p h 以，) + g 纠仇一- ) l = 1 ，2 ，力) 【g 。) = o 。 8 东北师范大学硕士学位论文 第二章确定型动态规划的算法 一、一维动态规划的求解方法 一维动态规划过程是指一个单状态变量就足以描述系统的状态，即在每一阶 段用一个单状态变量以，就足以完全表明所研究系统的状态。通常为了求出 甑仇) ，在每个阶段只要选择一个单决策变量黾就够了。 求解一维动态规划问题基本上有两种方法，一种是解析法，一种是计算法。 ( 一) 解析法 解析法适用于大量的动态规划问题，其特点是在递推关系表达式中，不需要 指标函数的数字列表就能完成极大化或极小化，瓯仇) 可用数学公式表示，并能 用经典求极值的方法得到最优解，即用解析的方法求得最优解析解。 研究的原始模型为 m i i l z = 彤，妇 o ) ( 1 )m m z = z 7 ，i p o 01 ) 一j 、 约束为 善_ 拍o 0 l ( 2 ) 弋，- l ， h o 。o = 1 ，2 ，栉) 为了采用数学归纳法来得到解析解，首先求解p = 2 和行为任意情况，即 抖 m i n z = 霉j ( 3 ) _ ，i l 约束仍可由式( 2 ) 来表示。 为了使分析问謦简化，令力= 3 ，则研究问题变成 。1 r n i n z = 工；+ + 工；， ( 4 ) 约束为 嚣麓砸 0 x ( 5 ) 由上列三式所表示的问题是贝尔曼在他的著作中提到过的。为了说明这个问 9 东北师范大学硕士学位论文 题与上一节讨论过的阶段、状态变量、决策变量、状态转移等概念的关系，将式 ( 4 ) 、( 5 ) 式改写为下述形式 m i i l 二= 后l o h ，工1 ) + 后：o k ，工2 ) + 七3 0 b ，屯) ( 6 ) 约束为 以，= 瓦仇，屯魄) ) = 1 ，2 ，3 ) 。 ( 7 ) 在式( 6 ) 中引入状态变量厶， ，如，如，使我们能够以下述变换代替式( 5 ) ， 乃6 ，如= 如一戈3 ， = 乞一工2 ，厶= 五一x l 。 ( 8 ) 为了看出式( 5 ) 与式( 8 ) 的等价关系，将式( 8 ) 各式相加可得 屯+ z 2 + z 3 6 一九。 ( 9 ) 在这个具体问题中，令如= 0 ，结果式( 9 ) 等同于式( 5 ) 。则由式( 8 ) 知 而= 五。由于乇0 ，可得 0 。同理，z 2s 如，工3 五。这样，由式( 6 ) 和式( 7 ) 表示问题，改述为 m i n z = x ? + + 工；， ( 1 0 ) 约束为 f = 如一屯，o j ，= ， 如= 如一工3 ，osx 2s 如， ( 1 1 ) 【厶6 ，o 而乃。 可见，式( 1 0 ) 和式( 1 1 ) 具有式( 6 ) 和式( 7 ) 的形式，这一点是很重要 的这是因为 s 。瓴，) = 工；，+ 九一，= 瓦，魄) ) = 屯一，：g = 1 2 ，3 ) 这样，我们就可用递推方程来表述原始问题，即 g ，似) = 唣n 抚阮，工。“灌， g 七) = 粤仇k ， 仇) 】+ g t 。矿仇，魂仇珊，岱= 2 ，3 ) 这是给出的一般形式，若现在置换 + k ) = 戈；， 以一，= 五一x 毒，g = l ，2 3 ) l o 东北师范大学硕士学位论文 可得递推关系 g ，“) = m i p z ；， - g 量仇) = 黜k + 趾t 仇吨) j 。传= 2 ，3 ) ( 1 2 ) 这个逐阶段递推的过程可示于图( 1 ) 。可以设想状态变量丸为一不小于6 的 量，并将它在三个阶段中进行分配，使得z = 彳+ x ；+ 为极小。图( 1 ) 正好 表明我们将要以式( 1 2 ) 来完成工作。 图( 1 ) 我们将用一个顺序过程将量厶加以分割。这里顺序的编号是不重要的。逆 序和正序都不影响求解的实质。现在求解式( 1 2 ) ，从而解决原始问题。由于 g “) 2 卿z 0 很明显 。 g ，“) = 鸳， ( 1 3 ) 需要强调式( 1 3 ) 的含意。& “) 为最优值函数。这就是说，不管 多大， 最优值是鸳，且工：= 。同理，由式( 1 8 ) 可得 g z 亿) = 。蛾k + g t 似一z ：) j ， ( 1 4 ) 由式( 1 3 ) 可以看出 g ：亿一x ：) = 似一屯) 2 。 由上述二式可得 g z 似) = 。蛾k + 化一屯) 2 j o ( 1 5 ) 由此可以看出，必须求出满足0 j c 2s 屯的工2 ，使下述函数极小 g ：魄，屯) = + 他一工：) 2 。 ( 1 6 ) l i 东北师范大学硕士学位论文 对式( 1 6 ) 进行偏微分，得到必要条件 由于 警地：一2 仇吨) - o o ( 1 7 ) 冬：4 o ， a x ： 这个条件也是充分的。式( 1 7 ) 的解为 厶 j c 2 2 芎 将这个解代入式( 1 4 ) ，得到 g ：o k ) = ( 争) 2 + ( 如一等) 2 = 譬。 于是 以下完全按确定g ：协) 的方法确定g 。仇) ，即有 砒) - o 蛾b 砒飞) 】= 硪卜+ ( 孚) 2 ， 遗) = 霹+ ( 孚) 2 ， 鼍啦一亿一为) - 0 ( 1 8 ) 聋= 3 o 。 叙i 从式( 1 8 ) 可以解出z 3 ，得到 从而 无 黾2 ， j g 。码) = ( 争) 2 + 半= 等。 c - 9 ) 式( 1 9 ) 有重要的含意。它告诉我们，待分配的量为如，所有剩余的分配是最 1 2 东北师范大学硕士学位论文 优的，则对于三阶段过程的最优指标是争。由于在阶段l 和阶段2 分配是最优 的，所以对于任何的也值，g ，仇) = 拿将是最优解。已知如= 6 ，并且当如= 6 时将出现最优，则式( 4 ) 的解为 66 6 工l 2 j 戈2 2 j 屯2j ， z ：堡。 ( 2 0 ) z = 一o z u ， 3 总结式( 4 ) 到式( 2 0 ) 的工作，是求解式( 1 ) 、( 2 ) 和式( 3 ) 表示的原始 模型的p = 2 ，挖= 3 的情况。得到的结果下边立刻会用到： g 。“) = 鸳，工：仇) = 五； g ：瓴) = 譬，x ：似) = 鲁； ( 2 t ) g ，协) = 冬，工；似) = 每。 jj 下面回到研究式( 1 ) 表示的问题。此时p = 2 ，以为任意。由式( 2 1 ) 给出 的规律，似乎可以形成一种合理的猜想，对= 七，将有 g 七仇) = 譬，) = 争。 ( 2 2 ) g 七仇) = 年，) = 争。 ( 2 2 ) kk 这里用归纳法证明式( 2 2 ) 的正确性。已知当= l ，2 ，3 时( 2 1 ) 式是真的， 并假定= 七也是真的，即 那么， g 七) = 譬，x ：) = 争akk g “。) = 。蔓燃。b 五t + g 七吨h ) j = 艘。卜譬竽 1 3 东北师范大学硕士学位论文 工州为最优解的条件为 其解为 由于 2 怄慨+ 。g 川阮+ - ，屯+ - ) ， ( 2 3 ) 警地。一如型如o x k & ，一以+ 1 以+ 1 。甫。 ( 2 4 ) 等= 竿北 缸毛。 七 所以由式( 2 4 ) 表示满足式( 2 3 ) 求极小的要求，是最优解。则 ) = ( 舞) 2 + ( 一矗) 2 肛 - 亳， 仍， 于是由式( 2 4 ) 和式( 2 5 ) 完成了归纳。式( 1 ) 的解为 = 告，u = 跏。，刀) 6 2 以上是对式( 1 ) 的p = 2 ，n 为任意的研究。下面深入研究p 取不同值时的 情况。 令由式( 1 ) 表示的原始模型中p = 1 。这是一种简单的情况，因为 g t “) 2 辫z 2 ，嚣：= ， g ：仉) 2 融b ：+ g - 伉一如) 】= 。蛾b ：+ 亿一工2 ) 】= 如， 并且对满足os 石2 如的石2 的任何值，都是最优的。取x ：= 冬。这样的选择理 由，会在后面显得很清楚。采用数学归纳法证明g 七仇) = 以是容易做到的。若现 在假设仇) = 以，则有 似+ - ) 2 。驰+ k + 瓴圹t ) 】= “。 1 4 东北师范大学硕士学位论文 这就完成了归纳。这又遇到了荚1 以上述昀情况，满足0 黾s 以酮仕1 叫以但，邵 将是最优的，取工：( 厶) = 争。 令由式( 1 ) 表示的原始模型中p 1 。前面已经得到p = 1 和p = 2 的情况的 解 夕= 1 ：g ，“) = 乃，阮) = 等， ( 2 6 ) p = 2 ：g 仇) = 等，阮) = 等， 。 c 2 7 ， 由式( 2 6 ) 和式( 2 7 ) 可以提出第二个猜想： g ，也) = 笋，砒) = 等。 i 当然p = 1 和p = 2 的情况是满足这个猜想的a 采用归纳法来证明。设p 1 且 g 七) = 告，z ：仇) = 争， 则可得 鼽。仇“) = 。溉+ 。k t + g i 仇“一t ) j = 船一+ 纠 = ，m 堍g “饥+ l ，z m ) 。 略咄+ i s + i 一 对q + ，求导，并令其等于零，有 鲁= 芦瘩一掣一o o 癜i + l 疗。 上式所得解是极小的。由于对o 屯+ i 厶， 鲁= 比舢留+ p 肌“广2 0 ， 解上式，得出e + = 孚等，以及 庀+ l 东北师范大学硕士学位论文 纸川= ( 等) p + k 一瓮) p 纠= 寿， 至此完成归纳。 这样求到的式( 1 ) 对p 1 的解为 z ( 6 ) = 筹，工：( 6 ) = 告。o = 1 2 ，由 对于p 1 的情况，由于限制了p 满足p 1 ，根据条件衫，因而巧为一个凸 函数。而p = 1 ，- 是凸和凹的，这是出于分界的情况。由定理知，至少在闭凸 集上的凹函数的一全局极小值，将是凸集上的一个边界点。处理的凸集为 x 。= 七l o 以以) 。 = 1 ，2 ，甩) 这是一个特别简单的集合，有两个边界点，即零和以。 为了得到对于解的本质的深入了解，所考虑的问题是 m i n z = x + 蠢+ ， ( 2 7 ) 约束为 1 工i + x 2 + 屯6 ，( 2 8 ) 卜l ，工2 ；屯之u o 很明显 g 。“) = 卿茸= 前， g ：亿) = 。慨窿，g 。也一z ：) j = 溉窿+ 似一z ：) j 。 上式的全局极小将发生在屯= o 或屯= 如或二者皆是，所以仅限于考虑这两个 值。所以 g ：( 如) ：m i n l 9 + 砖，鹰+ o 】= 砖， 以及 ( 乞) = o 或x ：( 丸) = 乞。 二者将导致全局最优解。同理可得 g ，魄) = 勰k - + g ：仇喵) j 1 6 东北师范大学硕士学位论文 = 溉k + 似一而芦j = 蚵n 1 9 + 越，菇+ o j = 鹰， 以及 似) = o 或工；他) = 如。 最后得到 = = g ，( 6 ) = 6 ， 工；= 毛= 6 ， 如= 如一工3 = 6 6 = o ，工；= o ， = 五一工2 = o o = o ，工：= o 。 应注意，由于在阶段2 和阶段3 有几种不同的最优解，故还有另外的最优解 组。 现在推断式( 1 ) 对o p 1 的一般解，这是第三个猜想，其为 g ，“) = 秽，= 6 ( ， 刀) ，戈：= 6 。 用对的归纳法证明。对= 以，这明显是正确的。对= 七的情况 ) = 雒， 则 & h 仇q ) = 。黜+ ；+ g 七协+ l _ ) j = 略溉+ 。b 磊。+ 仇圹吒+ ) 1 一假溉+ 。b 磊。+ 丸+ 。，j ， 所以 g 。+ ，q ) = 五如， 且 + 。= o 或“= 五“。 至此完成了归纳。 1 7 东北师范大学硕士学位论文 至此已证明，对0 1 ) ； f 矽( o p s l ) ， ( 乃) = 铫小，= 嚣 l o ，( o p l ，_ = l ，2 ，”一1 ) ， 弓( 6 ) = 6 ，( o p l ，= 万) ， l j 鲁，( ；，；：，= = l ，2 ，z ) 对于o p p ， 工 栉川 = t 、_证m 为柬约 厶v 孙吣 i 斗“ 、- 、 一拧 乙x k 聆 = 一一 k k ： 岭 p p 人i 杰办仿) = z “) 。 ( 1 1 ) ，- 1，i i 但是，由于x 是由式( 6 ) 和式( 7 ) 组成问题的最优解，可知 由于 和 z k ) ：杰办) 一主化) 主力似) 一窆 ，似) = z 0 。) 。 一，- l_ ，一1，l l- ，i l 则可将上式改写为 z k 。) ：羔办似) ， z k 。) ：窆办似) ， - ，i l 东北师范大学硕士学位论文 z k 。) = ：0 。) 一窆7 l l j g ：) z k ) 一主 ，似) ：z k 。) 。 j i i，- l 由于x o 和x 均满足式( 1 0 ) ，即 和 则由上式可得 芝啊，k 。) = 啊， _ ，l 羔 。，0 。) 一6 l ， j 1 2 k ) z k 。) 。 这显然与式( 1 1 ) 中的假设矛盾。因此，当式( 1 0 ) 得到满足时，x 。应是由式 ( 4 ) 和式( 5 ) 组成问题的解。 在使用这个结果形成一个完整的算法之前，需要知道羔| 1 1 1 ，) 是怎样随 j i l 而变化的。这是因为必须对不同的值求解式( 6 ) ，直到式( 1 0 ) 满足为止。 证明当从o 增到o 。时，量 是单调减小的。定义 一，、 。，0 ”， _ ，一l 艺办b 似) ) = 和 ，一i ( 1 2 ) ( 1 3 ) 芝五。，似缸) ) ：心。 ( 1 4 ) 一l 由式( 1 3 ) 、式( 1 4 ) 和式( 6 ) 可知 z k 0 l ) 尘z 芦一芦， ( 1 5 ) 且注意到 假设 z 仁。0 l ) = z p 一俑芦。 ( 1 6 ) 东北师范大学硕士学位论文 0 o ， 而资源w 一工下降到夕 一z ) ，o 1 。希望求出x 的值，其结果是从经营中总 得益为最大。这个过程，可以认为是无限阶段的过程。当时的讨论是出于阶段数 趋于无限，将遇到极大的计算量，必须另辟新的途径。 若资源的经营过程在刀个状态上重复进行，可得到下述递推关系 g ，“) = 躐驴g t ) + 五“一工t ) 】， 既仇) = 霉鉴陟g 七) + j l z 一以) + d 詹+ 仇一心) ) 】。( 2 ) = 2 ，3 ，行) 若挖很大，或者过程实际上是无限地连续下去的，考虑一个无限阶段过程，作为 满足无限连续过程要求的一个合理近似，将是方便的。当过程视为无限阶段过程 时，则式( 2 ) 可用单个方程来代