（概率论与数理统计专业论文）连续时间马尔可夫决策过程平均最优的新条件.pdf

中山大学硕士学位论文 连续时间马尔可夫决策过程 平均最优的新条件 专业：概率论与数理统计 学位申请人：张兰兰 导师及职称：郭先平教授 摘要： 连续时间马尔可夫决策过程在很多领域有着广泛的应用，其中，平均报 酬( 费用) 准则是最常用的准则之一，因为它被广泛应用于电信与排队系统， 生产过程等领域。因此，对连续时间平均准则的研究不仅有一定的理论价值， 而且有一定的实际意义。本文在转移率和报酬( 费用) 率有界的情形下，给 出了一种特殊的马尔可夫决策过程一受控生灭系统平均最优的新条件。我 们利用生灭过程的遍历性理论来确定其指数遍历的条件，这些仅仅建立在模 型中初始数据之上的条件，可以被我们用以证明最优平稳策略的存在性，而 且我们还将实现其在排队系统中的应用。 关键词： 连续时间马尔可夫控制过程，平均报酬( 费用) 准则，受控排队系统， 指数遍历，最优平稳策略。 t h en e wc 0 n d i t i o n sf o rc o n t i n u o u s t i m e m a r k o vd e c i s i 咖p r o c e s s e s w i t ha n a v e r a g ec r i t e r i o n m a j o r ：p m b a b m t ya n ds t a t i s t i c s n a m e ：z h a n gi 盘n l 柚 s u p e r v i s o r ： p r o g u ox i a n p i n g a b s t r a c t ： c o n t h i o u 争t 岫em a r k o vd e c i s i o np r o c e s s e sh a v e b e e 玎w i d e i ya p p t i e di n m a n y6 e l d s ，a n dt h ea v e r a g er e w a r d ( c o s t ) c r i t e r j o 力i so n eo ft h em o s p o p u l a r p e r f b r m n c ec r i t e r j ab e c a u s eo fi t sa p p l i c a t i o n si i lt e l c c o m m u n i c a t i o na n dq u e u i n g s y s t e m s ，m a n u f a c t u r i n gp r o c e s s e s ，a n dm a n yo t h e rr e a i w o r l ds 矗u a t 如n s s oi ti s p r a c t i c a lf o rs t u d y i n gt h ec o n t 劬o u s t i i i l em a r k o vd e c 豇i o np r o c c s sw i t ha l l a v e r a g ec r h e r i o n 1 nt h i st h e s i s ，w eg i v en e wc o n d 缸i o 璐f o ft h ee x i s t e n c eo f a v e r a g eo p t i l l l a lp o l i c i e sf o ras p e c i a lm a r k o vd e c i s j o np r o c e s s e 争茁o n t r o u e d b i n h - d e a t hs y s t e m t h et r a n s i t i o nr a t e sa i l d t h er e w a r d ( c d s t ) r a t e sa r eb o t h b o l l n d e d 。w cp r o p o s ean e ws e to f n d i t i o so nt h 零p r i m i t i v ed a t au n d e rw h i c h t h eo p t j m a ls t a t j o i i a r yp o l i c i e se x i s t ，a i l dw eu s eac o n l m l l e dq u e u e i i l gs y s t e mt 0 s h o wt h a to u rc o n d n 主0 n s 甜es a t i s 矗e d k e y w o r d ： ( b m 如u 叫s t j l n em a r k o vd e c i s i o np r o c e s s e s ，a v e m g er e w a r d ( c o s t ) c r j e r j o n ， n t r o n e db i r t h d e a t hs y s t e m ，o p t i m a ls t 缸b n a r yp o l 记y 第一章绪论 第一章绪论 1 1马尔可夫决策过程的历史背景： 马尔可夫决策过程( m a r k o vd e c i s i o np r o c e s s e s ，也称为马尔可夫 决策规划或马尔可夫控制过程等) 是研究一类随机序贯决策问题的理论。 所谓随机序贯决策问题，是指在一系列相继的或连续的时刻( 称之为决 策时刻) 点上作出决策，在每个决策时刻点，决策者根据观察到的系统 状态从可用的若干个决策中选择一个，将决策付诸实施后，系统将获得 与所处状态和所采取决策有关的一项报酬( 或费用) 并影响系统在下一 决策时刻点所处的状态。系统在下一决策时刻点处的状态是随机的。在 这一新的决策时刻点上，决策者要观察系统所处的新的状态( 即收集新 的信息) 并采取新的决策，如此一步一步进行下去。在每一决策时刻采 取的决策都会影响下一决策时刻系统的运行( 状态，决策) ，并以此影响 将来。因此可以蜕马尔可夫决策过程是为了研究和控制( 至少影响) 系 统未来的发展而建立起来的一门学科。它以马尔可夫( 或半马尔可夫) 过程作为数学模型，为了研究和控制系统未来的发展，我们必须周期地 或连续地对它进行观察，这两种情形分别称为离散时间和连续时间参数。 在每个观察时刻，决策者根据观察到的系统状态，从他可用的行动( 措 施、方案等) 集中选用其一( 即作出决策) ，这将导致两件事发生：( i ) 系统将获得一定的经济效应； ( i i ) 能确定以后系统状态发展的概率规 律。马尔可夫决策过程的宗旨就是在各个时刻作出决策( 即制定决策) ， 第一章绪论 使系统的运行在某种意义下( 称为准则) 达到最优。 马尔可夫决策过程是( 确定性) 动态规划与马尔可夫过程相结合的 产物。它不像动态规划那样以b e l l m a n 的“晟优化原理”作为研究的出 发点，而是从一些简单的、易于验证的条件( 或公理) 出发束严格证明 “最优化原理”。马尔可夫决策过程既是随机运筹学的一门分支，也是应 用概率的一门分支，同时，作为马尔可夫型系统最优控制的理论它亦 属于随机系统最优控制的范畴。马尔可夫决策过程与近年来必起的计算 机集成制造系统中的系统理论一一离散事件动态系统理论密切相关。实 际上，它是随机型离散事件动态系统的唯。的动态控制方法，与离散事 件动态系统的逻辑控制方法也有着密切的关系。 马尔可夫决策过程中的一些概念可以说在1 9 6 0 年之前就已经产生， 但1 9 6 0 年h o w a r d 2 8 奠定了马尔可夫决策过程作为独立学科的基础。 1 9 6 2 年b l a c k w e l l 2 则为在这一领域进行进一步的研究提供了动力。马 尔可夫决策过程中的基本模型有离散时间马氏决策过程、连续时问马氏 决策过程和半马氏决策过程，在此基础上，考虑更为接近实际问题的的 模型有状态部分可观察的、多目标的、自适应的，带约束条件的以及随 机环境的马尔可夫决策过程。从准则函数来说，有折扣准则、平均准则、 期望总报酬准则、加权准则、折扣矩最优准则、样本路径准则等。 马尔可夫决策过程的应用领域十分广泛，这些领域有：生产存贮系 统、系统更换维修、制造系统的调度控制、计算机通信网络系统控制、 动态资产定价、广告优化、商品与服务的定价、质量控制、序贯搜索、 水资源管理、森林管理、航空订票、高速公路管理等等。 1 2 离散时间马尔可夫决策过程及其研究现状 离散时间马尔可夫决策过程是在离散的时间点如n ；0 ，1 2 ，观察系 第一卓绪论 统，这里n 可取有限多个值，如h ；0 1 ，2 ，也可取所有的非负整数。 一个离散时间马尔可夫决策过程的模型由如下的五重组组成： 忸，爿o x p 。- i r ( f ，d x ，f ，j s ，n 爿( f ) ( 1 1 ) 其中各元的含义如下： 1 5 是系统所有可能的状态所组成的非空的状态集，即系统的状念 空间，它可以是有限的、可列的或任意的非空集。我们用小写的字母f ， 等来表示状态。 2 对状态f s ，爿( f ) 是在状态f 处可用的决策集，它是非空的；当 不特别指出时亦假定它是可数集。常用口来表示决策。 3 当系统在决策时刻点n 处于状态f ，采取决策口一( f ) 时，则系统 在下一决策时刻点n + 1 时处于状态j 的概率为p 。( a ) ，假定它与决策时 刻n 无关。称p ；b “0 l f ，s ，n 爿o ) 为系统的状态转移概率族，于是， 对f s ，口彳( f ) ，有荟n ，仁) = 1 ，即恼u ( 口l j s 为一随机向量。范围 稍广一点的是扫叫( 口l ，s 为次随机向量的情形，即善p f ，( n ) s 1 。在大 多数情况下，这两种情形可统一考虑。 4 当系统在决策时刻点n 处于状态f ，采取决策口爿( f ) 时，系统于 本阶段获得的报酬为r ( f ，n ) 。若记r j ( 1 ，n ) l i s ，n 4 ( i 计，则r 是定义 在r 上的一个广义函数r ：r 一 _ 。，+ * ，于是我们常称，为报酬函数。， 可以只取有限实值，也可取广义实值。当r ( f ，4 ) 5o 时，它表示的实际上 是费用。，( f ，n ) 的含义随具体应用问题的不同而有所不同。 5 形为准则( c r i t e r i o n ) 函数( 也称为目标( o b j e c t i v e ) 函数) ， 可分为期望总报酬的( 包括折扣的，正的和负的等) 和平均的等多种。 3 第一章绪论 h o w a r d 是第一个研究平均准则的作者，他所提出的策略迭代法是在 算法方面的第一个晕程碑。另外，他证明了对于有限状态集和决策集， 其策略迭代法所得到的平稳策略在平稳策硌范围内是最优的。d e r j i l a n 1 0 及v i s k o va n ds h i r y a e v 4 3 分别独立地证明了策略迭代法所得到的平 稳策略在整个策略范围内也是最优的。 2 则对理论方面进行了开创性的 研究，对有限( 状态和决策的) 折扣的马尔可夫决策过程得到了许多重 要结果，同时还提出了研究平均准则的折扣因子消失法( v a n i s h i n g d i s c o u n ta p p r o a c h ) ：将平均准则作为折扣准则当折扣因子趋于1 ( 即 折扣因子的作用消失) 时的极限证明了存在一个当折扣因子充分接近 于1 时均为折扣最优的平稳策略，这种类型的最优现在称之为b l a c k w e l l 最优。在h e y m a na n ds o b e l 2 6 中使用t a u b e r i a n 定理也讨论了折扣准 则与平均准则之间的关系，这种方法首先是由g i l l e t t e 1 7 在证明随机 对策问题平均准则最优平稳策略的存在性时提出的，文献 1 0 将之用于 证明b l a c k w e l l 最优策略的平均准则最优性。当状态集或决策集非有限 时，b l a e k w e l l 最优策略不一定存在。实际上，此时的平均最优策略也 不一定存在( 见h ua n dl i u 3 0 第五章例l 。1 ) 。平均准则比折扣准则要 涉及到更多的马氏过程的性质，对它的研究要复杂一些，同时，其内容 也更丰富一些。b a t h e r 3 等在一定条件下证明了存在最优策略， d e r m a n 9 研究了可数状态集、有限决策集的马尔可夫决策过程，提出了 平均准则最优不等式，其作用与折扣准则中的最优方程相同。r o s s 3 4 将b l a c k w e l l 的折扣因子消去法用于从折扣最优方程获得平均最优方 程。1 9 8 9 年，s e n n o t t 3 5 更进一步提出了平均准则最优不等式的概念， 其作用与平均最优方程相同，而条件更弱。 这里我们再着重介绍一下研究平均准则的方法： 研究平均准则的常用方法就是上面所提及的折扣因子消去法。它首 先是b l a c k w e l l 在 2 中提出的，对于有限马尔可夫决策过程， b 1 a c k w e l l l 利用折扣准则函数与平均准则函数之间的关系，运用阿贝尔 4 第一章绪论 ( a b e l ) 定理证明了存在一个最优策略。另一方面，t a y l o r 4 0 针对一 个马尔可夫序贯问题，通过研究相对值函数h 。( f ) ( 如( 4 1 ) 所定义) 当 折扣因子口t1 时的渐近性质，而将折扣因子消去法用于从折扣最优方程 导出平均最优方程。f e i n b e r g 【1 4 】对折扣因子消去法作了进一步的研究， 并证明了在d e 瑚a n 【1 1 】中的条件下“。( f ) 关于a 一致有界，通过令nt1 证 明了平均最优方程有有界解。这使得折扣因子消去法的适用范围得以拓 展并变得非常广泛。其后，【1 1 】中条件的各种变异提了出来，s t r a u c h 【3 9 】 研究了平均准则和折扣准则下的无界报酬半马氏决策过程，利用折扣因 子消去法，在比较强的条件下证明了一些结果。t h o m a s 【4 1 】是这方面的 综述。以上条件对保证最优方程或最优平稳策略的存在性是必要的。另 一方面，f 打n a n d e z 【1 6 】在很一般的条件下证明了h 。( f ) 的一致有界性也是 平均最优方程存在有界解的必要条件。g a v a 2 0 s c a d e n a 【4 ，5 】证明了在 一定的条件下，平均最优方程有界解的存在性包含了模型中很强的常返 结构。因此要求平均最优方程具有有界解在一般情况下是太过于苛刻了， 一个自然的推广是无界解。【2 5 】，h u 【2 9 】等将折扣因子消去法推广到无界 报酬和平均最优方程有无界解的情形。而【9 】沿着同样的思路提出了平均 最优不等式，其中仍然适用折扣因子消去法而所需条件更弱。 另外，对于特殊的问题，可能会有特殊的方法，如s f i d h a m 【3 8 1 ， w c b e r 【4 4 】研究了排队系统问题，针对排队系统最优控制这一特定问题， 提出了新的方法：f 0 表示队长，将平均准则化为从f 出发首达状态0 的期望总报酬目标，而后者的求解较为简单。他们证明了平均最优方程 的解( 可能无界) 的存在性和最优平稳策略的存在性。 相应于马氏过程中的离散时间马氏链、连续时间马氏过程和半马氏 过程，在马尔可夫决策过程中亦有离散时间马尔可夫决策过程( d i s c r e t e t ij 1 】em a r k o vd e c i s i o np r o c e s s e s ) 、连续时间马尔可夫决策过程 ( c o n t i n u o u st i m em a r k o vd e c i s i o np r o c e s s e s ) 和半马氏决策过程 5 第一章绪论 ( s e m i m a r k o vd e c i s i o np r o c e s s e s ) 等。 关于离散时间马尔可夫决策过程的研究已经比较完善了( 可参考 d y n k i n a n d y u s h k e v i c h 1 2 ，p u t e r m a n 3 3 ，s e n n o t 3 6 ， h e r n a n d e z l e r m aa n dl a s s e r r e 2 5 ，h o ua n dg u o 2 7 ) ，然而，在许 多实际领域( 如排队系统) 中都需要在时间连续变化的情形下观察系统， 并连续的采取决策，即利用连续时间马尔可夫决策过程( 可参考 3 3 ， 3 6 ，k a k u 腿n u 3 1 ，g u oa n dh e r n a n d e z l e r f i l a 1 9 ，f e i n b e r g 1 3 ， z h e n g 4 7 ) 来描述受控的系统。 1 3 连续时间马尔可夫决策过程及其研究现状 连续时问马尔可夫决策过程仍然可大致分为两种类型： 一类为连续时问带跳跃的马尔可夫决策过程，其决策者只在特定( 随机) 时刻选择他( 或她) 的行动，因此可以转化为半马氏甚至是离散时间的 马尔可夫决策过程( 可参考 3 3 ， 3 6 ， 1 3 ) 。在另一类连续时间马尔可 夫决策过程，决策者能连续地选择他( 或她) 的行动( 这一类型将在第 二章中详细介绍) 。这也是本文研究的主要类型。 离散时间马氏决策过程和半马氏决策过程都只是在一些离散时刻点 处采取决策。而连续时间马尔可夫决策过程需要连续观察系统，并且连 续地采取决策。相应于离散时间马氏链和半马氏过程中的状态转移概率， 在连续时间马尔可夫过程中的则是状态转移概率函数 亿f ( f ) ：f ，s ，f 2 0 ，但在实际问题中，其确定可能是很困难的，而且在 连续时间马尔可夫决策过程中，此转移概率函数还依赖于决策，其确定 就更加困难，甚至是不可行的了。一个选择的途径是确定转移率矩阵， 而且它只要用短时间的观察资料就可近似地决定。 6 第璋绪论 在某个时刻f 位0 ) ，如果观察到系统处于状态f ，决策者从可用的 决策集中选取一个决策口，相应的转移速率为吼( 口) ，对于充分小的 r ，o ，当系统在时间区问k h 出i 中只要处于状态f 时就采取决策d ， 则系统于时刻f + 血时转移到状态，的概率为吼( 口p + 。( 血) ，作两次或 更多次状态转移的概率为d ( & ) 。因此，在连续时间马尔可夫决策过程中， 直接给出的不是转移概率矩阵族，而是转移率矩阵族。 一个连续时间马尔可夫决策过程是由一个五重组 岱，0 ( i 、l s l 口，r ， 所构成( 具体定义见第二章) 。 马尔可夫决策过程中常用的准则有有限阶段总报酬准则，折扣准则 和平均准则等。在本文中，我们主要考虑连续时间马尔可夫决策过程的 平均报酬( 或费用) 准则。其主要研究内容可归结为三点： ( 1 ) 最优策略存在的条件； ( 2 ) 最优策略的有效算法： ( 3 ) 特殊模型的具体应用。 而最优策略的存在性问题是研究的基础与关键，迄今为止，人们对该问 题的研究已取得了许多令人满意的结果。如c a o 【6 】，l ( a k u m a 删【3 1 ，3 2 】， 【3 3 】，【3 6 】，y u s h k e v i c ha n df c i l l b e r g 【4 5 】及【4 7 】对转移率一致有界情形进 行了研究，c a o 【6 】，g u oa n dl u 【2 1 】，【2 7 】，勋k u m a n u 【3 1 ，3 2 】，s o n g 【3 7 】 及y u s h k e v i c ha n df e 抽b e r g 【4 5 】则对报酬( 费用) 率有界情形进行了研究。 当转移率与报酬( 费用) 率均无界时，g u oa i l d z h u 【2 2 ，2 3 】， h c m n d e z k r m a 【2 4 】h o ua i l dg u o 【2 7 】及g u oa n dh e m n d e z k 瑚a 【1 8 】 也给出了相应的最优性条件。本文则在转移率一致有界，报酬( 费用) 率有界的情况下，给出了一种特殊的马尔可夫决策过程一一受控生灭系 统的平均最优的新条件。 以上所提及的文献在最优策略存在性证明中，均需涉及到相对值函 7 第章绪论 数“。( f ) 。在f 3 1 】，【3 7 】中，“。o ) 被假定为对任意的折扣因子a ，o 及状态 i 是一致有界的；在1 2 3 】中“。( i ) 被假定为仅对折扣因子是有界的；在1 4 7 】 中，“。“) 可以既无上界，也无下界，但仍然需要将假设直接建立在相对 值函数“。o ) 上。这就给验证带来了不便。而本文是利用z c i f m a l l 【4 6 】中的 遍历性理论来建立指数遍历的条件( 见假设c ) ，从而保证相对值函数 。( f ) 有界( 见引理4 1 ) ，进而可以证明最优策略的存在性，并由于有 关生灭过程收敛率的估计已有了相当完善的结果( 见c h e n 【7 】，d o o m 【4 1 】， 【4 6 】) ，因此假设c 的验证非常简单。在第五章中我们给出了本文在排 队系统中的应用，并在例1 中将本文的条件与【1 8 】的条件相对比。 本文余下几部分的内容为： 第二章介绍连续时间马尔可夫决策过程的模型及生灭过程，并实现从一 般马尔可夫决策过程到生灭系统的转化；第三章将给出几个所需假设引 理：第四章给出摄优策略存在性这一重要结论；第五章将实现在排队系 统中的应甩。 8 第二章最优控制问题 第二章最优控制问题 2 1 连续时间马尔可夫决策过程的模型： 一个连续时i 司马尔司夫决策过程是具有如f 意义的血重组 忸，o l f s l 口，r ，) ，( 2 1 ) 其中，s 是可数状态空间，这旱可令s ； o ，1 ，2 ，) ： 爿( f s ) 为系统处于状态f 时的可控行动集，假设其为一b o r e l 空间， 口( f ) ) 为其b o r e l 盯一代数； 令k ( f ，) ：f s ，n 爿( f ) 1 ， q ( 川f ，n ) 为转移率，满足q ( ，i f ，口) o 对所有( f ，n ) k 且，一f ， 设矩阵k ( j | f a ) 是保守的，即荟q ( ji f ，n ) o v ( f ，口) k ， ( 2 - 2 ) 且是稳定的，即g ( f ) 昌s u p 吼( d ) t 。v f s ， ( 2 3 ) 口6 d 其中口，( n ) | 一口( f k n ) 对所有的n 爿( f ) 及f s ， 对任意固定的f ，j sq ( ，i f ，n ) 是4 ( f ) 上的可测函数； 报酬( 费用) 函数，( f ，n ) ：k 一( 一* ，+ 。) ，当f 固定时，r ( f ，口) 为( f ) 上 的可测函数； 为准则( 目标) 函数，它主要为折扣目标和平均目标。在这篇文章中， 我们主要考虑连续时间马尔可夫决策过程的平均报酬( 或费用) 准则( 见 ( 2 1 5 1 ) 。 9 第二章最优控制问题 2 2 策略的定义： 定义2 1 称函数，为决策函数，若，：s 一爿：- u 锄一( f ) ，且，g ) 4 ( f ) v f s 。 f = i ，：，( 1 ) 彳( f x f s 为决策函数集。 一个随机马氏策略万是一个序列石一k ：f 乏o ) ，满足： ( 1 ) 对固定的i s ，f = o ，啊( l f ) 为盯0 ( j ) ) 上的一个概率分布： ( 2 ) 对固定的f 和口爿“) ，疗，( 口l f ) 作为f 的函数是勒贝格可测的。 全体随机马氏策略集记为，；随机马氏策略玎sb 。：f = o ) 称为随机 平稳的，若万，一石。，fzo ；称为确定的，若玎，oz 0 ) 均为退化分布；确定 的平稳马氏策略称为平稳策略，即存在，f ，使得一( 厂g ) i f ) = 1 对每一 个f e s ，f o 成立，此时石由，决定，视为平稳策略类。 全体随机平稳马氏策略集记为n ，全体确定性马氏策略集记为n ：，全体 平稳策略集记为! 。 对任意的一k ，f o ) 。，f ，j s 且f o ，定义： q ( ，旧，石) i 一( jl f ，口k ，f ，s ，f 苫o ， m “ ，( f ，f ，z ) - r r ( f ，口k ，l f ) ，f s ，f 之o ， 矗l 特别地。当石一，f 时，记： ( 2 4 ) ( 2 - 5 ) 口7 ( ，i f ) ：i q ( i f ，o ) ) ，r ( f ，) 奢r ( f ，o ) ) ， 对每一个石h 。及f = o ，考虑矩阵q ( f ，玎) ，k ( ，i f ，f ，玎) ，以q o ，万) 为密度 1 0 第二章最优控制同题 矩阵的马尔可夫过程称为q 一过程。为了保证q 一过程的存在性，我们在 控制策略集 n ：= 访。：g ( f i ，r ，玎) 对每个固定的f ，s ，关于t 连续j 上考虑，显然f c n 。另一方面，由( 2 2 ) 及( 2 3 ) 可知，对任意的f 0 ， q ( f ，矗) ( 玎) 仍然是保守和稳定的，即 毋( f ，石) - 一碍( f l ，f ，石) = q ( j l i ，f ，耳) t m ，v f s ，fz o 及万n 。 ( 2 6 ) 因此，对每一个z n ，q 一过程( 如最小q 一过程b ”g ，i ，f ，石) ) 的存 在性得到了保证。若该q 一过程还为正则( 唯一且诚实) 的，对任意给定的 s 上的初始状态f ，可记其确定的唯一概率测度为牟( 相应于只的期望运算 用雕表示) ，对应的马尔可夫链记为缸t ，丌x f ，o 。但如【2 7 】，a n d e r s o n 【1 】， c h u n 越8 】，f e l l e r 【1 5 】所述，其f 则性不一定成立，即可能对某些f s 及 ，zs o ，有罗p “( 5 ，i ，f ，玎) 0 ；肛，：， o ，则称x 是一个生灭过程。 ( 2 7 ) 现考虑一个连续时间马尔可夫决策过程仁，0 ( f x i s l 目，r ，其转移率满 足： 口( jl f ，n ) i h - ) 一掣；( 口) 一 g ) ( 口) 0 其中对任意的fz 1 ，地( 4 ) | 肛( f ，n ) ，丑仁) - l a ( f ，n ) ，肛与a 均为从s 爿“) 到 ( o ，* ) 上的可测函数。 当石= ，f 时，令 q 7 ( ，i f ) 兰 仙 一| 一雄 a f 0 ，l f 一1 i4 ，p j o ， j4 l + l 其他 其中p j 净弘o ，( f ) ) ，置a o ，g ) ) ，f ，fz 1 。 显然矩阵q 是保守稳定的。 假设a ： ( a ) s u p 0 ，+ 吖) t m ， j 邑j ，日 ( 6 1 ) 对所有的 2 1 和，f ，硝 o ，且r ，= + * ，其中， ( 2 - 9 ) o 1 0卢 一 + 川她 第二章最优控制问题 肌；薹睁耘+ 糕”+ 筹焉) p 或 ( 扫：) 对所有的n 1 和，f ，肛j o ，且l 一+ m ，其中， 儿= 薹去( - + 筹+ 箍+ ( c ) 弘? 难lv f s ，f 。 + 鲁筹) ， p 引理2 3 假设a 成立时，矩阵q ：k 7 ( j l f ) j 对应的q 过程是f 规的生灭过程。 证明：由生灭过程的定义及【1 ，1 2 ，啦3 】知引理2 3 成立。 定义2 4 平均报酬准则： 对任意的玎，f s ，定义平均报酬准则如下： 矿k ，z ) ：= 1 1 罂p ；fk ，扛，z e ，打l z 碚】， ( 2 1 2 ) 对应的最优值函数为： 矿+ 0 ) ：= s u p 矿仁，f ) ，对任意的f 5 ， ( 2 1 3 ) 矗 称石兀为平均最优的，若对任意的f s ，有矿k ，f ) = y o ) 。( 2 。1 4 ) 平均准则表示在策略刀下从初始状态f 出发长期运行的平均期望报酬。 平均准则是无限阶段随机动态系统最优控制中的常用准则。当需要最优化的 阶段足够长，而且较短阶段并不比较长阶段更重要时，就可以使用平均准则。 因此，对于相对较快地进入“稳态”运行的系统( 如通信网络) 来说，采用 极限的时间平均报酬( 费用) 准则是合理的。而在折扣准则( 见( 3 3 ) ) 中， 将来的报酬按折扣率进行折扣，于是当阶段足够大时，所获得的报酬的作用 第二章晟优控制问题 越来越小，因此，折扣准则实质上只注重于考虑近期行为。与此相反，对于 平均准则，近期所获得的报酬不起作用，它注重于长期的稳定行为。因此， 折扣准则和平均准则时所考虑准则中的两个极端。 在最优控制问题中，准则的引入是为了比较策略的优劣，我们的目的是 根据某一给定的准则在所有允许的策略中寻找一个使准则函数达到最优的 策略。对于函数值越小越优的情形( 如函数r ( f ，4 ) 表示费用时) ，只要将r ( f ，口) 改为一r ( f ，口) 就可将问题转为最大化。 1 4 第三章技术初步 第三章技术初步 这一章中，我们先给出几个已有引理，用以证明本文的重要结果 定理4 1 。 假设b ： ( a ) 对任意的f ，s ， r ( f ，口) 与g ( ，i f ，口) 关于n 爿( f ) 连续， ( b ) 存在常数mzo ，使得：s u p l r ( f ，口】s m ， 善“) ( c ) 对每一个f s ，爿( f ) 紧。 引理3 1 ：若假设a 和b ( b ) 成立，则对任意的石n f s ， i 矿仁，f l s 肘，m 如假设b 中定义。 证明：陆，】s1 1 雩严扫眇m ，玎l 玎叫 r - lj 3 1 折扣报酬准则： 现引入折扣报酬准则：对任意的万n ，f s 及给定的折扣因子口，o ( 3 - 1 ) ( 3 2 ) 彻 ， 1 一r p 弓j m m n 。 u m v l = 第二章妓本仞步 k k ，班一? f e “r ( f ，z o ，z l 耳皿 对应的最优值函数： 吒( f ) ：- s u p 屹( f ，石) _ 口 策略为口一折扣最优的，若： 圪仁+ ，f ) 。吒( f ) ，对任意的f s 。 引理3 2 ：若假设a 和b 成立，则： ( a ) v 耳，f s ，a ) 0 i 屹0 ，州；丝 8 ( b ) 最优值函数吃是最优方程 ( 3 3 ) ( 3 4 ) ( 3 5 ) 训。瓣，卜) + 驴i f ，制 ) ，s ( 3 7 ) 的唯一有界解，且对任意的a ，o ，存在一个n 一折扣最优平稳策略 f ：f ， 即吃( f ) 一圪，f ) ，s 。 证明：( a ) i 圪仁，f ) | i | e ? f e ，( f ，x ( f ，石l z 枷 s m r 扣专 ( b ) 由f 2 0 ，n 3 2 】知。 现固定一个任意状态k s ，对每一个折扣因子o t 。t1 ，定义相对值函数 w 。g ) - 0 ) 一屹( f 。) ，圪，f ) 一圪( f ，f 。) ， 1 6 第三章技术初步 3 2 指数遍历的条件： 假设c ：设存在个常数r ，o 及f 数序列和。) ，满足： ( a ) i n f d ：= d 0 ， ( b ) 专 砭t + j 一一肛厶s _ ，对任意的n zo 其中r 是一个与， 无关的常数，d 一。；0 。 显然，相对于文献【2 1 2 3 】，【2 7 】，【3 1 】，【3 7 】与【4 7 】中将假设直接建立在相对值 函数“。( f ) 上来说，假设c 的验证要简单得多，例如在文献【2 7 】中需假设“。o ) 关 于折扣因子a 一致有界( 见【2 7 】假设a 1 3 2 ) ，这个条件不仅较强，而且因为h 。( f ) 是由折扣准则定义出的，验证它的有界性自然不太容易。而本文的假设均是建立 在模型所给定的初始数据的基础上的，通过下面的引理3 3 及引理4 1 我们不仅 可以得到生灭过程忸( f ，l f ) o 的遍历性，而且可以进一步证明h 。( f ) 是有界的。 在下引理中，对任意的厂f ，p j ( p j ( f ) ) 为一行向量， p j ( f ) - = p 伍( f ，) ；f ) ，p j ( f ，j ) | p 伍( f ，) 一i z ( o ，厂) 一f ) ，万，= k j ) 为齐时马 氏链忸( f ，i f ) o ) 的平稳分布，满足忙川。一杉- 1 。 引理3 3 ：若假设a 与c 成立，则生灭过程忸o ，l f ，o 对任意的，f 是指 数遍历的，即对任意的，存在石，tk j ) 为平稳分布，满足： i p j 一玎川。- - 善l p ( j o ，) - r ) 一玎j is 昙e 一“卢 且对一切f s ，善陋7 ( f ，j ) 一石引5 昙e 一“卢， 1 7 ( 3 - 9 ) ( 3 - 1 0 ) 第三章技术初步 其中卢_ 争踟州与，耽州萨硝“- s 妒p ， 4 s 垆( 等) 一扣 证明：由【4 6 ，t _ 1 1 1 】知，在假设b 、c 成立的情况下，有 1 卜姜- t ) 一一ls 詈e “芦v t 乩 其中多。弘) 一f ， 我们知道石j j 长若口；- 咀熹吖t * 。见。4 ：p 其中q ， i o其他 令( 分s 甲盼由假设喇知( * t ， 令a 4 i 呼4 s 严p j 则 珏jt 娜川，s 华翘a 悯。卜。 邮小肌芦j 华跏洲慨且关。 莩叭加石卅弘咧p j 一石引 生蟹：丝! i l il t ：t l f 1 。莩j 摹p j ( f 姚小 ( 3 一1 1 ) 3 军( 小石卅18 。s 芦。 ( 3 _ 1 2 ) 1 8 d h y 岛 l窿 久一 二l牛 1ll上、li，趔黔 第四卓平均最优策略的存在性证明 第四章平均最优策略存在性证明 引理4 1 若假设a ，b ，c 成立，f 。s 如上，则对任意的f s ，有 s 警。 ( 4 - 1 ) 证明：i “。( f 】= k ( 一，1 ) 一屹( c ，f 。】 ；i 军f e 一“p f ( f ，卜( ，c ( “) h 一；f e 一“p f ( f 。， ( j ，c ( ，) k i s 胁“炉峥能小；p 栌 s m f e “( 1 莩c p ，c “，一万叫+ i 莩b f o 。，) 一石j j 卜 s m f e “詈e “触( 由( 3 _ 1 2 ) ) ：孚墼；盟。 2 碉了。 对任意定义于s 上的实值函数“，定义范数净s u p b o 】以及b a n a c h 空间 口临) 墨缸：| | c 。 。 定理4 1 如果假设a 、b 、c 成立，则存在一个常数g ，函数“口0 ) 及平稳 策略，+ f ，使得： ( a ) 对任意的f 5 ，平均报酬最优方程成立，即： g 2 群卜) + 驴i f 圳叫 1 9 第四章平均最优黄略的存在性证明 ；r 0 ，( f ) ) + q ( 巾，+ o ) k ( ，) v f s 。 睁2 ) 怒 ( b ) g + 是平均报酬最优值函数即g - 矿+ o ) 对所有的f s ，并且任意使得( 4 2 ) 成立的，是平均最优的。 证明：( a ) 选择折扣因子序列扛 ，满足吒一o ( 当万一* 时) 。 由假设a 及引理3 ，2 ( a ) 知f q 呓( f 。1 对任意的一z 1 有界。 因此，存在k 。) 的子序列讧。， 及常数g ，满足g 一l i m a ，一 f 0 ) 。 由引理4 1 知，t 口lj 有界，固由t y c h o n o 任乘积定理知，存在仁。- 的 予序列 口。 及s 上的函数n ，使得： l i m d 。吃( f o ) 一g ，l i m u 。o ) 一：“( f ) _ t 且l i m “。h 。( f ) ；o ，v f s 。 ( 4 - 3 ) 由引理( 4 - 1 ) 及( 4 - 3 ) 式知，对所有的f s ，k ( f 】s 詈，所以“口o ) 。 ( 3 7 ) 式可改写为： 鬻枷) t 黑) 错+ 荟【掣吨m ， 降q 其中：m o ) ：一- + g ( f ) ，。，且6 。：- ：耋：；筹。 由引理3 2 ( b ) 知： 错帆。m 帮+ 荟 掣吨h 咖啡 吼掣+ 等州“，z 捌+ 斟掣咆h ， v 口彳( f ) 。 由f a t o u 引理及f 4 3 、有o 第网章平均摄优策略的存在性证硝 品枷，z 捌+ 荟 帮地v 瞄且 眠窨z 翟，卜) + 驴k 瘁叫妊s 。 ( 4 - 5 ) 又对任意的n 苫1 及s n o ，且填罂5 n = o ，由引理3 2 知存在丘。，使得 对所有的f s 及n 1 ， 掣+ 锗峨m 掣+ 荟f 掣城卜小岛 因为对所有的f s ，4 ( f ) 是紧的，所以我们可以假设存在，。f ，使 得填婴正o ) = ，。( f ) ，又由扩充的f a t 。u 引理，令n o 。，我们可以 得到： 高枷，s 铡+ 荟 掣墙m v 川， 即：g + s r 0 ，( f ) ) + 荟鼋( ，i f ，( f ) - ( ，) s 潞卜) + 驴k 碳，4v 矧。 ( 4 s ) 结合( 4 1 5 ) 与( 4 _ 6 ) 有暑。蚓制+ 荟m ，口叫v 矧a d “衡 由假设b 知，存在r ，使得f 4 3 1 成立： ( b ) 对每一个石n 及( a ) 中的函数h 毋$ ) ，由( 4 3 ) ，( 2 4 ) ，( 2 5 ) 知， g + 2 帆) + 善口( 小) o ) v 及f s 。 ( 4 - 7 ) 另一方面，因为h b ) ，由【2 0 ，l e m m a 6 1 】我们有，对任意的 j 苫0 及f s ， 第玎章平均最优策略的存在性证明 i ? 0 ，f ) il i m f 一k 0 “b b + r ，z ) ) 一“( f ) j f 1 0 。荟目( ，慨) o ) r 又由h 的定义及引理4 1 ， 陆h 等 眦有姆型掣，。跏乩 由( 4 6 ) 一( 4 8 ) 及【2 4 ，p r o p 3 5 】，我们有 g 矿仁，f ) v f s 及。 因此g 矿o ) v f s 。 同样，由( 4 2 ) ，我们有 g + 。矿( 厂+ ，f ) s 。 ( 4 8 ) ( 4 9 ) ( 4 1 0 ) ( 4 1 1 ) 结合( 4 9 ) 与( 4 1 0 ) 可得：g + ，矿( ，+ ，f ) 。矿o ) 对所有的f s ，( b ) 成立。 第血章排队系统t 卜的应用 第五章排队系统中的应用 这一章中，我们着重考虑随机服务系统中应用面最广的一类一一排队系 统。 根据排队系统的组成，排队系统的最优控制可分为到达控制和服务控制 两大类。到达控制是对到达顾客能否进入系统进行控制的，而服务控制是对 到达( 从而进入) 系统的顾客服务时间进行控制的。从排队系统中服务台多 少及其之间的关系通常将排队系统分为单服务台排队系统和多服务台的排 队网络。这里，我们主要介绍m m n 排队系统的到达控制和服务控制，从中 证明其最优平稳策略的存在性。 5 1 排队系统的到达控制： 排队系统的到达控制有以下几个要素： 1 顾客的到达：顾客在某时刻到达系统外部以期允许后进入系统， 2 控制：系统决策者在顾客到达时接收或拒绝顾客的进入，如果拒 绝，则顾客离去；如果接收，则顾客进入系统，并使系统状态( 队 长，或工作总负荷) 增加。 3 服务：系统对进入的顾客进行服务，可以是针对一个一个的顾客， 也可以是针对进入顾客所携带的工作负荷，甚至是两者的混合。 4 报酬：进入的顾客给系统带来一项报酬，此项报酬可依赖于系统 状态、顾客的类型以及顾客所携带的工作负荷等；而顾客在系统 中等待时，系统需付出费用( 等待或存贮费用等) 。 第五章排队系统中的应聪 5 目标：有限阶段折扣准则、无限阶段折扣准则和平均准则等，这 里我们主要讨论平均准则。 在摊跌系统镪弱达控裁鹄研究中，有两稗最伉仕：一种是所谓的个俸 最优( i n d i v i d u a l l yo p t i m a l ，简记为i o ) ，其含义是当报酬和费用 均由顾客自己获得或支付时使每一个到达顾客的获利最大。另一种是 所谓的社会最优( s o c i a l l y0 p t i 髓1 ，简记为s o ) ，其含义是使系统 莰利最大，这里的系统获利即指所有顾客的获利总和。也称1 0 策略 为平衡( e q u i l i b r ju m ) 策略，称s o 策略为p a r e t o 最优策略。 例一：考虑一个排队系统，其状态表示每个时刻fzo 时的总人数，a 往o ) 与 p go ) 分另q 为自然出生( 到达) 率与死亡( 服务) 率。n ( 口) 为转入参数。出决 策者控制。当系统的状态f s i 置