数学系本科毕业设计

1、北京交通大学毕业设计（论文）具有不同信息精度的排队经济学研究摘 要在排队系统中，顾客为了使自身的利益最大化而单独行动，不考虑对整个队列的影响，这种实质上是相互作用的自私行为就导致了一个纳什均衡格局的形成，然而，这个均衡从全局角度看很可能并不是最优的，由此目光敏锐的经济学和排队论学者针对这一经济学现象在排队论和博弈论背景和框架下开始了研究工作，进而逐渐形成了一门经济学、博弈论与经典排队论有机融合的交叉学科，排队经济学 (economics of queues)。 本论文以前人提供的关于排队经济学的文献成果为基础，主要研究了若干类型的排队经济学模型并对其进行了纳什均衡策略和社会最优策略分析。针对实

2、际排队中的一些问题，进行了模型简化，并运用排队论、博弈论、随机过程的一些方法，就单服务器马尔可夫排队模型进行了nash均衡与社会最优分析。分析了一些不同的模型，并重点就可视不可视队列进行了社会最优与利润最大化分析。关键词：排队经济学 博弈论 nash均衡 m/m/1排队模型economics of queues with different information accuracyabstractcustomers in queueing systems act independently in order to maximize their own welfare. yet,each cus

3、tomers optimal behavior is affected by acts taken by both the system managers and the other customers. the result is an aggregate “equilibrium” pattern of behavior which may not be optimal from the point of view of society as a wholel.similar observations have been known to economists and researcher

4、s of queueing theory for a long time so that they began to solve this economic problem based on game and queueing theory.then it gradually developed into a cross-subject of economics, game theory and queueing theory named as economics of queues.based on the previous literatures on the subject of eco

5、nomics of queues, equilibrium and socially optimal strategies are analyzed in several types of models in this dissertation.on the terms of some promblems in the actual queuing models, we get it simplified and use queuing theory,game theory,methods of stochastic processes to analysis their nash equil

6、ibrium and social optimum on single server markov queuing model.analysis a number of different models,and focus on the socially optimal and profit maximization of visible and invisible queue. keywords: economics of queues; game theory; nash equilibrum; m/m/1 models of queuesii目 录摘 要iabstractii第1章 绪

7、论11.1 排队经济学的历史及发展现状11.1.1 可观察队列的历史及发展现状11.1.2 不可观察队列的历史及发展现状31.2 研究意义和发展动向41.3 论文结构5第2章 排队经济学简介62.1 排队问题的基本概念62.1.1 排队问题概述62.1.2 排队系统的特征及组成62.1.3 排队模型的分类与记号92.2 马尔可夫链简介102.3 纳什均衡142.4 排队经济学简介15第3章 单服务窗排队模型均衡分析173.1 单服务窗损失制排队模型m/m/1/1173.1.1 模型简介173.1.2 nash均衡173.2 单服务窗等待制排队模型m/m/1193.2.1 模型简介193.2.2

8、 nash均衡193.3 单服务窗混合制排队模型223.3.1 模型简介223.3.2 nash均衡223.4 可变服务率的排队模型253.4.1 模型简介253.4.2 nash均衡26第4章 社会最优与利润最大分析294.1 可观察队列294.1.1 社会最优294.1.2 利润最大化324.2 不可观察队列344.2.1 均衡354.2.2 社会最优374.2.3 利润最大化384.3 相对优先权404.3.1 模型描述404.3.2 纳什均衡414.3.3 利润最大化42第5章 总结45参考文献46第1章 绪 论1.1 排队经济学的历史及发展现状长期以来，经济学家发现在排队服务系统中，

9、顾客为了使自身的利益最大化而独立行动，每位顾客的最优行为都受到系统管理者和其他顾客的制约和影响，其结果就导致了一个均衡格局的形成，这种均衡的格局在经济学和博弈论中被称为“纳什均衡”或“非合作博弈均衡”(nash equilibrium)。然而，这个均衡从整个全局或社会角度看很可能并不是最优的(经典的案例就是纳什提出的“囚徒的困境”问题)，由此大量经济和排队论学者针对这一经济学现象在排队论和博弈论背景和框架下开始了研究工作。最早的研究成果要从naor在 1969年发表在econometrica上的一篇论文算起。此后，大量关于优化控制排队的排队经济学研究成果不断涌现。1.1.1 可观察队列的历史及

10、发展现状排队经济学的奠基人naor首次研究了怎样管理和控制可视mm/1排队系统的问题。他发现在可视排队系统中，个体顾客的决策往往背离整个社会的利益偏好。这种差异是由于个体最优行为所产生的负面作用引起的。每个个体顾客为了追求自身利益最大化而导致系统过度拥塞，使得整个社会的福利锐减。这个结论在许多类型的可视排队经济学模型中都是成立的，此后的部分研究工作也是在此模型基础上的拓展。hassn对naor的模型进行了改进，提出了lcfs一pr模型并对此进行了初步研究。他提出了一种新的方法，在此方法下，即使不对顾客收取费用，也能达到社会福利最优。随后，olson，nalebuff和landsburs都分别对

11、此类模型进行了研究。从服务员利润最大化的角度考虑，naor在他的模型中提出了为使利润最大化而对顾客收取的费用要高于社会所希望收取的费用的观点。knudsen对此结论进行了一般化，考虑了多服务员非线性费用函数的复杂情况。simonovits也证明了在gl/m/s排队系统中也可以得出类似的结论。yechiali在gl/m/i排队模型中，指出了为使利润最大化应如何计算对顾客的收费额度。他考虑了两种情况，一种是各个顾客相互独立，一种是所有顾客联合起来提出一个价格上限。rue和rosenshine对价格上限的灵敏度进行了考量。larsen，afeche和mendelson对naor的模型进行了另一个角度

12、的一般化。他们假设顾客的服务价值(service value)是随机变量而不是相同的恒定的常数。与naor所得出的相关结论一致，即为使利润最大化而对顾客收取的费用要高于(或等于)社会所希望收取的费用。然而，edelson和hildebrand发现如果假设顾客的时间价值(time value)也不相同，则此结论不一定成立。schroeter则考虑了时间价值服从均匀分布的情况。devany考虑了服务需求是对顾客所收取费用额度的函数的可视排队模型，得到的主要结果就是由于服务员对顾客收取的费用过高，使得顾客的实际均衡到达率相对于社会最优到达率要低得多。miller和buckman考虑了一个具有随机服务

13、价值的m/m/s/s消失可视排队系统，此系统不会产生队列，顾客一旦发现系统满员则立即消失。此外，学者们还根据当时的经济学实例提出了一些较贴合实际的可视排队经济学模型。chen和frank通过在naor的模型中引入贴现率(discount rate)来使得原始模型更一般化，利用相同的贴现率，顾客和服务员都设法使自己的贴现效益最大化。ackere和ninios则通过仿真方法考虑了服务员为设备做广告的排队模型。近两年，单纯考虑可视排队的文献相对较少。economou和kanta考虑了一个具有非可靠单服务员的可视马尔可夫排队模型，导出了顾客的均衡阂值策略。1.1.2 不可观察队列的历史及发展现状首先发

14、现基本的不可视排队模型性质的是edelson和hildebrand，他们对naor的模型进行了改进，取消了队长可视的条件而假定队长不可视。与可视排队一样，得出了个体顾客为了追求自身利益最大化而导致系统过度拥塞的结论。而后，balachandran和srinidhi，chen和frank又对此进行了研究，而且chen和frank发现顾客需求的增加会导致价格下降。balachandran考虑了服务设施具有固定运行成本的不可视m/g/1排队模型，证明了纳什均衡下顾客的到达率是唯一确定的。针对可视和不可视两类模型的异同，hassin对可视与不可视排队模型的社会福利与服务员利润进行了比较，而larsen

15、则利用仿真方法对可视与不可视模型的这两个指标进行了比较。ehen和frank则假设“登记费”(registerfee)固定，对比了可视与不可视模型的有效到达率。近些年，关于可视和不可视排队之间对比的研究也有进展。stein等分别考虑了不同信息下的可视和不可视排队博弈模型，顾客成批到达且不许中途违约，用大量实验对其进行了平衡策略分析。burnetas和economou考察了可视(几乎可视)和不可视(几乎不可视)情形下具有启动时间的markov排队中顾客的均衡策略问题。guo和zipkin则讨论了三种具有不同滞后信息的排队模型，包括完全可视、部分可视和不可视类，比较这些信息类对顾客的平衡行为和系统

16、的影响。1.2 研究意义和发展动向 排队经济学的研究为工商、交通、公用事业、军事等部门中随机聚散现象及各种排队性质提供了理论基础，也为合理设计和管理排队系统提供了依据。运用排队经济学的一些研究成果，可以科学管理和有效使用一个服务系统，使它既能满足顾客需求，又能实现社会最优化与费用最小。有效解决通讯、运输、以及实际中各种排队问题。从1969年naor的第一份研究成果问世开始，迄今为止在排队经济学方面已经存在大量的文献可供后续研究的参考。然而近些年来，随着博弈论的迅速发展，以及实际排队经济学案例的不断复杂化，现存的大部分文献所研究的排队经济学模型的假设结构和限定条件相对比较简单，贴合实际的系统制约

17、因素考虑得并不周全，因而与当今的经济生活脱节，不能研以致用。当今，对排队论的研究主流越来越趋于人性化排队。通过研究顾客和服务机构管理者的心理，来预知和分析均衡状态下博弈双方的行为。例如单就顾客来说，顾客可以判断何时退出队列会使自己后悔值最小，在不完全信息下顾客如何估计剩余效用而做出是否排队的决策。在顾客被告知各种不完全服务信息的情形下，合理并开创性地假设顾客心理遵循最大嫡原理，从而对实际的服务信息做出推测，用以指导其进行决策，秉承人性化排队的理念。1.3 论文结构论文主要研究了排队理论中各种排队系统的均衡解及可观察不可观察队列的社会最优问题。共分为五章，内容包括：绪论、排队经济学简介、单服务窗

18、排队模型分析、社会最优与利润最大化分析、总结。第一章，绪论。主要介绍了排队经济学的历史和发展现状，研究意义和发展动向，并分别对可观察及不可观察队列的历史分开介绍；第二章，排队经济学简介。主要介绍了简单的排队问题及排队经济学的基本概念，为后边提供理论基础；第三章，单服务窗排队模型分析。主要介绍了各种但服务窗牌多模型及其均衡解，即m/m/1模型及其变体模型的均衡解分析；第四章，社会最优与利润最大分析。主要就可观察与不可观察队列，分别分析其社会最优与利润最大条件；第五章，总结。总结了文章所研究的内容，以及存在的问题。第2章 排队经济学简介2.1 排队问题的基本概念2.1.1 排队问题概述众所周知，某

19、些资源、设备或空间（场地）的有限性及社会各部门对它们的需求是存在排队现象的主要因素，而诸如服务机构的管理水平低劣，服务窗（员）的素质差，效率不高，或顾客的无计划性以及其他原因也往往使不该有的排队现象出现。我们所要讨论的排队论是人们研究大量服务过程的一门数学理论。在社会生活中碰到的排队现象，诸如到商场购物，去图书馆借阅书刊、资料，汽车到加油站加油，船舶停靠码头，在公共电话亭打电话，将有毛病的电器送维修部门进行维修，病人去医院挂号看病，将有关数据输入计算机进行存储等，均可归结为顾客与服务窗之间的一种服务关系，并可用框图表示这类排队过程，如图2.1.1所示。图2.1.1 排队模型框图2.1.2 排队

20、系统的特征及组成输入过程输入过程是对顾客到达系统的一种描述。（）顾客总体可以有限或无限（如流入水库的水）；（）顾客到达系统的方式可以逐个或成批；（）顾客相继到来时间间隔可分为确定型（比如定期航班、定期的课程表等）和随机型（比如看病的病人、候车的旅客、进港口的船舶）；（）顾客到达系统可以是独立的或相关的（独立意即某时刻前到达的顾客对该时刻后到达的顾客无影响），输入过程可以是平稳、马尔可夫、齐次的等。排队规则排队规则是服务窗对顾客允许排队及对排队次序和方式的一种约定。排队规则可分为种制式。损失制顾客到达系统时，如果系统中所有服务窗均被占用，则到达的顾客随即离去，比如打电话时碰到占线，用户即重拨或离

21、去另找地方或过些时间再打；又如旅店客满谢客，挂牌大夫限额挂号，计算机限定的内存等均为此种情形。等待制顾客到达系统时，虽然发现服务窗均忙着，但系统设有场地供顾客排队等候之用，于是到达系统之顾客按先后顺序进行排队等候服务。通常的服务规则有先到先服务，后到先服务（比如仓库中同种物品堆垒后的出库过程），随机服务，优先服务（比如邮政中的快件与特快专递业务，重危病人的急诊，交通中让救火（护）车、警车及迎宾车队优先通过，设立专用车道）等。混合制它是损失制与等待制混合组成的排队系统，此系统仅允许有限个顾客等候排队，其余顾客只好离去永不再来；或者顾客中有的见到排队队伍而不愿费时等候，当队伍短时愿排队等候服务；也

22、有排队等候的顾客当等候时间超过某个时间就离队而去均属这种系统。服务窗（员）（）系统可以无窗口（如自选自付款购物）、一个窗口或多个窗口为顾客进行服务。（）在多个服务窗情形，顾客排队可以平行多队排列，串列或并串同时存在的混合排队。（）一个服务窗可以为单个顾客或成批顾客进行服务。（）各窗口的服务时间可为确定型（如交通路口红绿灯亮的时间、各单位固定的上下班时间）或随机型。服务时间往往假定是平稳的。排队系统的目标参量（或运行指标）（）绝对通过能力，表示单位时间内被服务完顾客的均值。（）相对通过能力，表示单位时间内被服务完顾客数与请求服务顾客数的比值。（）系统排队长度均值，表示系统内顾客数（排队等候顾客加

23、上正被服务顾客数）的均值。（）排队等候顾客的平均队列长度，表示系统内排队等候顾客数的均值。注：如果（或）较大，那么说明该系统的工作效率较低。（）顾客在系统内逗留时间的均值；顾客排队等候服务的时间的均值；服务时间的均值定义为；显然有 （）（）服务窗连续繁忙的时间长度，即忙期，它是随机变量。（）对损失制排队模型，系统的损失概率损，即系统满员概率。2.1.3 排队模型的分类与记号记 为顾客相继到达系统的间隔时间 的概率分布； 为服务窗口所耗费的服务时间的概率分布；为服务系统内服务窗的个数； 为系统内（最大）排队容量或顾客在系统中排队所允许的（最大）长度（包括正在服务和排队等待的顾客）。又令 为负指数

24、分布；为确定型分布；为阶爱尔兰（）分布；为一般分布；为一般独立的分布。通常用记号（或）来表达排队模型。为方便起见，当系统最大排队容量为时，就可略写为，举例如下。排队模型表示顾客相继到达系统的间隔时间服从负指数分布，而服务时间也服从负指数分布，系统内设有个服务窗，系统容量为无限（充分大即可）的等待制排队模型。排队模型表示顾客到达的间隔时间和服务时间均为负指数分布，有个服务窗且系统容量为 的损失制排队模型。排队模型表示顾客到达的间隔时间为一般分布，服务时间为负指数分布，只设有一个服务窗且系统容量为无限的等待制排队模型。排队模型表示顾客到达的间隔时间为一般分布，服务时间为一般独立分布，只设有一个服务

25、窗且系统容量为无限的等待制排队模型。排队模型表示每批有个顾客到达系统，且批与批到达间隔时间是负指数分布，服务时间为负指数分布，只有一个服务窗，且系统容量为无限的等待制排队模型。排队模型表示顾客到达的间隔时间与服务时间均为负指数分布，系统内有个服务窗，顾客源为且系统容量也为的闭合式（循环）排队模型。2.2 马尔可夫链简介设（），是定义在概率空间（，f，）上，而取值在非负整数上的随机变量序列，用“”表示时刻系统 处于状态这一事件。称为在事件“”出现的条件下，事件“”出现的条件概率，又称它为系统的一步转移概率。如果对任意的非负整数，及一切，有= （）则称是一马尔可夫链（markov chain）。当

26、与起始时刻无关时，则称为齐次的马尔可夫链，并将式（）称为马尔可夫性（无后效性或无记忆性）。若将“”看作“现在”，将“”看作“将来”，“，”看作“过去”，则式（）表示在已知“现在”的条件下，“将来”与“过去”是独立的。今后考察齐次马尔可夫链的情形，可简记为。易知 （）称矩阵为马尔可夫链 的一步转移矩阵。式（）表明矩阵中每个元素非负且每一行之和为。又称为马尔可夫链 的步转移概率。而为 的步转移矩阵。容易验证它有如下性质： （）下述的kolmogorov-chapman方程（以后简称k-c方程）成立 （）事实上 ， 利用 及马尔可夫性 ， 并注意 可直接得到上式也可用矩阵形式写出特别地若记，则有；并

27、称为齐次马尔可夫链x的初始分布。又称为齐次马尔可夫链x的绝对概率。利用全概率公式及马尔可夫性，有 （225）且当时 （226）此式表明齐次马尔可夫链x的任意有限维分布 ， 完全可由其初始分布及一步转移概率确定 。 下面不加证明地给出x为马尔可夫链的两个等价定义：a. x为马尔可夫链的充分必要条件是对n时刻以前的任一事件b与n时刻以后的任一事件a，只要,就有b. x为马尔可夫链的充分必要条件是只要，就有2.3 纳什均衡 求解博弈问题的关键在于寻找各博弈方都不愿或不会单独改变自己策略的策略组合，只要这种策略组合存在且是唯一的，博弈问题就有绝对确定的解。这种各博弈方都不愿或不会单独改变自己策略的策略

28、组合就是博弈论中最重要的一个概念：“纳什均衡”。在纳什均衡点上，如果某个参与者的策略发生变化而其他参与者的策略保持不变，会导致这个参与者的获利减少。纳什均衡点的概念和求解方法已经成为博弈论中最重要的工具。 定义：在n个参与者的标准式博弈中，如果策略组合满足下面这个条件，对于每个参与者i， 是它针对其他n-1个参与者所选策略的最优反应策略，则称策略组合是该博弈的一个纳什均衡点，即：对于所有都成立。其中，表示参与者i的策略空间，表示除了参与者i之外其他n-1个参与者所选策略的集合，表示参与者i在策略空间中所选的任意策略，表示参与者i的博弈收益函数。 从纳什均衡的定义可以看出，有些博弈有一个或多个纳

29、什均衡点，而有些博弈是没有纳什均衡点的。2.4 排队经济学简介排队是我们在日常生活中经常遇到的现象，如顾客到商店购买物品形成的排队;上下班坐公共汽车，等待公共汽车的排队;文件等待打印和发送;电话局的占线;故障机器的停机待修;水库的存贮调节等。由于顾客到达间隔时间和服务时间具有随机性，使排队现象不可避免。一般来说，从经济学角度看，排队是一种分配稀缺商品(服务资源)的办法。在资源配置不足的情况下，往往不得不引用排队机制来解决分配问题，因为排队可最大限度的节约顾客的时间成本，使资源得到相对的优化配置。长期以来，经济学家发现在排队服务系统中，顾客为了使自身的利益最大化而独立行动，每位顾客的最优行为都受

30、到系统管理者和其他顾客的制约和影响，其结果就导致了一个均衡格局的形成，这种均衡的格局在经济学和博弈论中被称为“纳什均衡”或“非合作博弈均衡”(nashequilibrium)。然而，这个均衡从整个全局或社会角度看很可能并不是最优的(经典的案例就是纳什提出的“囚徒的困境”问题)，由此大量经济和排队论学者针对这一经济学现象在排队论和博弈论背景和框架下开始了研究工作。排队经济学不仅研究了排队系统的一般特征，而且研究了各种不同的排队系统模型。并且给出了求解公式。所谓求解，就是用数学方法来确定用来判断排队系统运行优劣的数量指标。比如系统空舶概率；队长，也就是排队等待和正在接受服务的顾客数的平均值，以及顾

31、客排队等待时间的平均值等等。确定 这些数量指标的目的，在于研究排队系统的运行效率、提高排队系统的服务质量，找出改进的措施。当然，排队系统的类型和结构是多种多样的，有很多情况很难用数学方法来分析、求解。第3章 单服务窗排队模型均衡分析单个服务窗的排队系统模型，即 系 统只设一个服务窗的情况。假定顾客到达系统的间隔时间服从负指数分布，并且顾客是相互独立地到达系统；又服务窗为每一顾客的服务时间也服从负指数分布。3.1 单服务窗损失制排队模型m/m/1/13.1.1 模型简介排队模型是指系统内只设一个服务窗，系统容量为（即仅有一个排队位置而无排队等待位置），顾客到达和窗口 服务时间 均为负 指数分布，

32、且它们各自的参数为与的排队系统。如顾客到达时，发现服务窗正忙着，他即离去另求别处服务。比如可将只设一条外线的电话交换台看作此种排队模型。 因系统只有单个服务窗，故系统只能有两种可能状态：（服务窗空闲着）及（服务窗忙着）。于是，系统的状态流图如图.所示。3.1.2 nash均衡由氏微分方程，可知时刻系统处于空闲或忙着的概率（）或（）分别满足下列方程 （3.1.1）及正则性 （3.1.2）因系统仅有两个互通的状态，故必存在平稳分布，也即存在，事实上，由式（3.1.3）知 （3.1.4）其中，表示系统的负荷水平或强度。 当系统中已有一个顾客时，新来的顾客只好离去，故就是系统的损失概率，它等于 （3.

33、1.5）单位时间内平均损失的顾客数和平均进入系统的顾客数各为 (3.1.6) (3.1.7)从而 (3.1.8)3.2 单服务窗等待制排队模型m/m/13.2.1 模型简介设系统内只有单个服务窗口。顾客按参数为的泊松分布到达，如顾客到达系统时服务窗正忙着，则排队等待服务；且顾客到达的时间间隔与服务窗为每个顾客服务的时间均为负指数分布；平均服务率为。易知该系统构成一个生灭过程，其相应的密度矩阵q中各个元素为 （3.2.1）由此可画出其状态流图（本节考虑顾客是无限的），如图3.2.1所示。图排队模型的状态流图此处状态表示系统内有个顾客，服务窗正忙着，且有个顾客排队等待。3.2.2 nash均衡根据

34、公式（），直接写出状态概率所满足的微分方程式为 （3.2.2）我们感兴趣的是当时，系统能否从暂态进入稳态。理论上可以证明，当时，系统存在平稳分布，记为。此时，式（）可以改写为 （3.2.3）于是，可以解出 （3.2.4）再由正则性得即是服务窗空闲的概率，并且恰好是服务窗忙着的概率。越大，服务窗越忙。有时也称为系统的服务强度或负荷水平。由上易知利用式（）可以求出相应的目标参量：（） 系统内顾客的均值（包括正被服务和排队等候的顾客均值）。 （3.2.5） （） 由公式，可得顾客在系统内平均逗留时间 （3.2.6）（） 系统内排队等候的平均顾客数其中，为正被服务的顾客均值。因正被服务的顾客数或为（窗

35、口空闲）或为（窗口忙着），它们对应的概率为及。于是从而 （3.2.7）（） 据公式，顾客平均排队等待时间为 （3.2.8）（） 系统内多于个顾客的概率为3.3 单服务窗混合制排队模型3.3.1 模型简介假设系统只有单个服务窗口，顾客到来的间隔时间服从负指数分布，参数为；服务时间是参数为的负指数分布；又设系统只有 个排队容量（又称 个截止队长）。当系统中已有 个顾客时，新来的顾客不再进入系统排队而立即离去另寻他处服务。这样，在任何情况下，排队长度均不会超过，称这类系统为即时拒绝系统。根据上述，可以画出系统的状态流图，如图所示。图状态流图3.3.2 nash均衡因系统内所有状态互通，且状态有限，故

36、必存在平稳分布。按第章氏代数方程的一般规律，可以写出下列方程：对0状态，有，故；对1状态，有，故；对m-1状态，有，故；由正则性 （3.3.1）可得 （3.3.2）当=1时现对求相应的目标参量：（） （3.3.3）这是当系统中已有个顾客，新来的顾客不再排队而即离去另寻他处服务的概率。（） （3.3.4）（） （3.3.5）（） 因为 （3.3.6）所以 （3.3.7）（） 单位时间内平均损失的顾客数为，而单位时间内平均到达系统的顾客数（也称系统的有效到达率）为 （3.3.8）（） 据公式可得顾客平均等待时间、平均逗留时间分别为 （3.3.9） （3.3.10）（） 服务窗平均服务强度实际服务强

37、度当=1时，于是3.4 可变服务率的排队模型3.4.1 模型简介第一种情况：假定在单服务窗的排队模型中，顾客按泊松流到达某系统，到达强度为，又服务窗在为顾客的服务过程中，视窗口前顾客的排队长度改变其平均服务强度（或时间），即当排队长度超过某个时，服务窗用快速服务率，反之则用慢速服务率。这样，可画出系统状态流图，如图所示。图可变服务率的状态流图之一3.4.2 nash均衡据k氏代数方程的一般规律，可写出如下方程：对0状态，有，故；对1状态，有，故；对n-1状态，有，故；对n状态，有，故；对n+r-1状态，有，故；总之有 （3.4.1）当时，由正则性可知 （3.4.2）于是 （3.4.3） （3.

38、4.4）再由little公式可得 （3.4.5） （3.4.6）第4章 社会最优与利润最大分析处在服务系统的顾客独立行动来最大化他们的利益。然而，每个顾客的最优选择取决于其他顾客的行为和系统管理者。结果未必是从社会整理利益来看最优的模式。因此，我们就要研究怎样的行为选择可以使社会效用最大化。先来介绍一些基本的概念：n 策略：令表示一个有限的顾客集合，令表示表示其中第i个顾客可能采取的一系列行为。纯策略是指中的一个行为。混合策略是指随机的选取中的某个行为的一个函数，用表示。则策略表示为，其中。n 付费：每个顾客都与一个付费函数相联系。n 均衡：最优选择即均衡，用公式表示为：4.1 可观察队列在排

39、队经济学中，仅对于顾客来说，可观察排队是指顾客在进入系统之前对系统的相关参数信息知情，比如当时的队列长度，服务率，服务价格，服务员所处状态等。4.1.1 社会最优这一部分源自于lcfs-pr政策下的阈值（极限）均衡策略。这个阈值与社会最佳阈值相一致。让n作为队列的最大可能长度，也就是说，一个顾客总是当在他前面有n个人的时候改变策略，这个n包括正在办理的，让fn作为顾客在lcfs-pr队列位置n的期望利益,当所有在n+1位置的人都改变策略。当然，fn关于n是单调递减的，且是最大值，所以fn0，下面我们通过模型确定fn的参数值。引理：证明：在既定条件下，顾客最终得到r的好处的可能性与投机商人失败问

40、题的失败可能性是一样的，当最初的资产是n，目标是n+1，并且每一回合获胜的可能性为，让q=1-p，则失败可能性为：由r乘的这个值是为了防止到达位置n+1而放弃计划的位置n的个人效用的积极作用。消极作用则是，注意到直到游戏结束的每一轮的期望值，投机商人要么获益要么损失，是：用这个结果乘以来获取系统中这样一个顾客的预计执行时间，然后通过c来获取预计等待费用。基于上式，当且仅当fn>0时，令上式右边为gn，注意到：函数g（n）是无限函数且随着n严格单调增大，对于任何给定的 > 0并且g(0) = 0。因此存在的确定的值使得，并且这是保持队列“稳定”的顾客的最大人数。在naor的研究中，让

41、被定义在真实队列之上，并让成为的唯一解，则。并且：因此，这就是说:比起社会期望，个人最优能导致更长的队伍。就意义上而言这个结果是好，且适用于其他更普遍的排队模型。4.1.2 利润最大化现假设收取服务费，作为反对资金募集是为了转移支付这一社会观点，现在他们是服务费用，该模型假定服务费是决定顾客是否加入队列的基础。因此，一个顾客只有在价值r至少和预计足价相等时才会加入队伍。另外一个衡量这一行为的方法是顾客通过r-p来评估服务。给定p，则最大的队伍长度为记得，qn表示系统中有n个可观察的顾客的概率，而且，n也是他们接受的阈值。n是同一时间可能出现的顾客数量的最大值。因此，qn是止步概率。有效的到达率

42、是，利润率是。服务系统选择所需的阈值n并且设置符合该阈值的最高价格，也就是：服务系统的利润是：这里。利润最大化的阈值满足以下两个条件：和。因此有或者假设。请注意，在左侧的一小部分是积极的，这样双方都可以分解在不改变不平等号方向的情况下。这将导致将n代成n+1，并且改变不等号方向，第二个条件变为这两个条件可以概括为在的情况下，通过下边的关系，定义一个基于的变量：相应的盈利率是很显然，所以，。同时，可以得出得出如下结论：在lcfs-pr队列中，没个顾客的预期福利与他到达时间的队列长度都是独立的。利润最大化的费用恰好等于预期的福利价值。在这样的费用下，没个顾客都加入队列，而且他加入后的行为独立于费用

43、。4.2 不可观察队列不可观察排队是指这些系统参数信息在顾客作出决策之前不被告知顾客。对于较早些的文献一般都是指队长信息可视与否，而现今其含义越来越丰富。当然，如果是多服务员排队，服务员之间也存在相互之间的信息可观察与否的问题，比如服务率和价格等。模型假设：n 当客户需要服务时，他只能选择加入队列或不加入。在他做出决定之前不可能观察到队列长度。n 服务纪律性强并且连续工作。正如在可观测模型中，加入队列的客户给别人施加负外部性，因此除非队列得到调节，否则个别优化将会导致过度拥塞。4.2.1 均衡当入场费p和潜在到达率确定时，我们开始评估顾客在平衡时的行为。顾客有两种纯策略可供选择：加入或者不加入

44、队列。一个纯策略或混合策略可以用q描述，0q1，表示加入的概率。鉴于入场费是p，我们用表示队列平衡概率，以及相应的平衡（有效的）到达率用表示。当然，=。当有效到达率是时，我们制定期望等待时间。这一函数是连续的并且是单调递增的。对于加入队列的顾客来说，纯收益是服务价值，r，减去全价，p+cw（）。我们区分三种情况：n p+cw（0）r。在这种情况下，即使没有其他顾客加入，加入的顾客的纯收益不乐观。然而，在概率=0的情况下加入的策略是一个均衡策略，而且，没有其它均衡策略。此外，在这种情况下，不加入是占优策略。n p+cw（）r。在这种情况下，即使所有潜在顾客加入，他们都享受到积极的收益。而且，在概

45、率=1的情况下加入的策略是一种均衡策略，并且没有其它均衡策略。此外，在这种情况下，加入是占优策略。n p+cw（0）<r<p+cw（）。在这种情况下，如果=1，那么，加入的顾客享受积极的收益。因此，这不可能是平衡策略。同样，如果=0，加入的顾客相对不加入的顾客而言享受积极的收益。因此，这也不可能是一个平衡策略。因此，存在一个唯一的均衡策略，此时，=，并且满足cw（）=r-p。将w（）=代入，我们得到如下表格。图4.1 最好的应答和加入概率4.2.2 社会最优我们现在来关注社会最优问题。设最理想的社会加入概率为，最理想的社会加入比率为，此处，=。那么，=arg由于是严格凸函数，最大化

46、的函数是严格凹函数，并且有唯一的最大值。将w（）=代入，我们得到如下解只要他在0, 区间内，就是最佳解。在rc的假设条件下，此解是积极的。因此，如果- ，那么。否则，=。令为最优到达率下的社会福利。表4.2总结了最佳加入策略。表4.2 社会最优策略在假设rc下，。因此，正如在可观察队列里一样，个别优化导致队列长度超过社会理想。这个差距在实行适当入场费的情况下可以被纠正，正如下一部分讨论的一样。如果，那么4.2.3 利润最大化我们现在考虑一个设置了利润最大化的入场费的垄断服务器。垄断不留下一个积极的消费者剩余，因为在这种情况下，入场费可以在不减少到达率的情况下增加。所以，。垄断的问题是在和的条件

47、下最大化记得，社会目标是最大化服务器和客户的总福利，也就是。一项消去，反应社会效用是添加剂这样的假设，因此，从社会的角度看，入场费只是转移支付，没有社会福利。因此，社会问题是在0的条件下，最大化。图3.2 垄断价格和到达率社会最优的到达率可诱发适当的入场费，这也最大限度地提高利润总额。当此费用等于当，利润最大化选择最高收费，诱导出这个比率，即。一个社会规划者会选择这个费，或任何小的费用，因为任何这样的选择，导致相同的最佳到达率，。4.3 相对优先权在排队系统中顾客越多，单个顾客获得服务能力的比率也就相越低。相对优先权是指，每一位顾客获得一个相对优先权参数并根据参数值的大小成比例的获得服务资源。

48、如果系统中存在n类顾客，且每类顾客数为，赋予每类顾客的相对优先权参数分别为，其中，则每一个第i类顾客可获得比例的服务能力。特别的，所有第i类顾客获得的总服务能力比例为。4.3.1 模型描述考虑具有两类顾客的无记忆单服务员排队经济学模型。在此模型中，服务员对两类顾客的服务率不尽相同，即具有服务差异。假设实行不可视排队规则，且允许顾客在加入队列前放弃离开，但不允许顾客加入队列后中途违约。当然，没有进入系统而离开的顾客没有回报也没有损失。服务员没有权利任意选择顾客的支付金额，即两类顾客分别需支付各自固定的服务费用 。服务员唯一能控制队列的手段就是选择对两类顾客服务的相对优先权参数尸和。假设第i类顾客

49、的到达过程服从参数为，i=1，2的泊松到达过程，且到达率，i=1，2足够大。服务员对第i类顾客的服务时间服从参数为的指数分布。同时，在每个第i类顾客的逗留时间内，都承担着每单位时间以的等待损耗 。当然，服务完成后也将获得r;的服务回报。假设，。每个进入系统的第i类顾客都将支付服务费用，且此费用金额将公布于众，以使得顾客做出是否进入系统的决定。因此，任意一个第i类顾客在接受完服务之后的平均收益为，其中表示此顾客在系统中的逗留时间(等待时间与服务时间之和)。假设第i类顾客以概率进入系统，实际有效到达率。定义，i=1,2为第i类顾客的平均逗留时间，并简写为。定义为两类顾客的一对纳什均衡到达率，为净收

50、益与单位等待损耗的比率。因此，在均衡状态下，不失一般性，假设，且系统稳定，即4.3.2 纳什均衡当时，有其中，。因此，假设第一类顾客相比第二类顾客获得绝对优先权，也就是且，则他们的逗留时间分别为综合上式，得到两类顾客的一对纳什均衡到达率4.3.3 利润最大化现在考虑当两类顾客的支付费用一定的情况下，如何选择相对优先权参数来使得服务员的利润最大化。这个问题其实就是选择第一类顾客的相对优先权参以使得的值最大化。首先，考虑第一种不等情。如果得到服务员的平均利润率为定义最优优先权参数为成，则其可以通过求解上式的一阶优化条件而求得。 如果上式的解处于区间的内部，则它是最优解。否则，最优解存在于两个边界点

51、之中。 类似地，考虑另一种不等情况。如果则需要在非空区间aminb，1内使利润最大化。 特别地，观察一种特殊情况，即两类顾客的支付费用相等的情况。假定，下图描述了最优优先权参数为=0.2596，且其严格处于区间(a=0.2，b=0.3443)的内部。第5章 总结本文首先根据现实中用到排队经济学的诸多方面，提出了研究排队经济学的必要性。简单介绍了排队论及博弈论有关的预备知识，以及排队经济学的基本概念。其次，分析了排队系统中一些常用简单模型，包括其模型假设、均衡及其算法与公式推导。逐级增加假设条件，使其更贴合实际情况。再次，引进了可观察与不可观察队列的概念，并对其分别进行分析，考虑社会最优与利润最

52、大化条件。并结合图表进行分析。最后，随着博弈论的迅速发展，以及实际排队经济学案例的不断复杂化，本文对排队经济学模型的假设结构和限定条件相对比较简单，贴合实际的系统制约因素考虑得并不周全。总之，本论文简单的完成了排队经济学的简介、基本模型的均衡分析，及可观察不可观察队列的最优化分析，可以为实际排队问题提供一定的理论依据与参考。参考文献1 hassin, r. and haviv, m. to queue or not to queue: equilibrium behavior in queueing systems, kluwer academic publishers, boston, 20

53、03.2 hassin, r. and haviv, m. nash equilibrium and subgame perfection in observable queues, annals of operations research 113, 1526, 2002 3 hassin, r. and haviv, m. on optimal and equilibrium retrial rates in a queueing system, probability in engineering and informational sciences, 10(1996): 223-227

54、.4 sun, wei, li, shiyong, tian, naishuo and zhang, hongke. equilibrium analysis in batch-arrival queues with complementary services, applied mathematical modelling, vol 33, issue 1, january 2009, 224-241. 5 wang, jinting and zhang feng. equilibrium analysis of the observable queues with balking and delayed