數(shù)學系本科畢業(yè)設計

1、北京交通大學畢業(yè)設計（論文）具有不同信息精度的排隊經(jīng)濟學研究摘 要在排隊系統(tǒng)中，顧客為了使自身的利益最大化而單獨行動，不考慮對整個隊列的影響，這種實質(zhì)上是相互作用的自私行為就導致了一個納什均衡格局的形成，然而，這個均衡從全局角度看很可能并不是最優(yōu)的，由此目光敏銳的經(jīng)濟學和排隊論學者針對這一經(jīng)濟學現(xiàn)象在排隊論和博弈論背景和框架下開始了研究工作，進而逐漸形成了一門經(jīng)濟學、博弈論與經(jīng)典排隊論有機融合的交叉學科，排隊經(jīng)濟學 (economics of queues)。 本論文以前人提供的關(guān)于排隊經(jīng)濟學的文獻成果為基礎(chǔ)，主要研究了若干類型的排隊經(jīng)濟學模型并對其進行了納什均衡策略和社會最優(yōu)策略分析。針對實

2、際排隊中的一些問題，進行了模型簡化，并運用排隊論、博弈論、隨機過程的一些方法，就單服務器馬爾可夫排隊模型進行了nash均衡與社會最優(yōu)分析。分析了一些不同的模型，并重點就可視不可視隊列進行了社會最優(yōu)與利潤最大化分析。關(guān)鍵詞：排隊經(jīng)濟學 博弈論 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 排隊經(jīng)濟學的歷史及發(fā)展現(xiàn)狀11.1.1 可觀察隊列的歷史及發(fā)展現(xiàn)狀11.1.2 不可觀察隊列的歷史及發(fā)展現(xiàn)狀31.2 研究意義和發(fā)展動向41.3 論文結(jié)構(gòu)5第2章 排隊經(jīng)濟學簡介62.1 排隊問題的基本概念62.1.1 排隊問題概述62.1.2 排隊系統(tǒng)的特征及組成62.1.3 排隊模型的分類與記號92.2 馬爾可夫鏈簡介102.3 納什均衡142.4 排隊經(jīng)濟學簡介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章 社會最優(yōu)與利潤最大分析294.1 可觀察隊列294.1.1 社會最優(yōu)294.1.2 利潤最大化324.2 不可觀察隊列344.2.1 均衡354.2.2 社會最優(yōu)374.2.3 利潤最大化384.3 相對優(yōu)先權(quán)404.3.1 模型描述404.3.2 納什均衡414.3.3 利潤最大化42第5章 總結(jié)45參考文獻46第1章 緒 論1.1 排隊經(jīng)濟學的歷史及發(fā)展現(xiàn)狀長期以來，經(jīng)濟學家發(fā)現(xiàn)在排隊服務系統(tǒng)中，

9、顧客為了使自身的利益最大化而獨立行動，每位顧客的最優(yōu)行為都受到系統(tǒng)管理者和其他顧客的制約和影響，其結(jié)果就導致了一個均衡格局的形成，這種均衡的格局在經(jīng)濟學和博弈論中被稱為“納什均衡”或“非合作博弈均衡”(nash equilibrium)。然而，這個均衡從整個全局或社會角度看很可能并不是最優(yōu)的(經(jīng)典的案例就是納什提出的“囚徒的困境”問題)，由此大量經(jīng)濟和排隊論學者針對這一經(jīng)濟學現(xiàn)象在排隊論和博弈論背景和框架下開始了研究工作。最早的研究成果要從naor在 1969年發(fā)表在econometrica上的一篇論文算起。此后，大量關(guān)于優(yōu)化控制排隊的排隊經(jīng)濟學研究成果不斷涌現(xiàn)。1.1.1 可觀察隊列的歷史及

10、發(fā)展現(xiàn)狀排隊經(jīng)濟學的奠基人naor首次研究了怎樣管理和控制可視mm/1排隊系統(tǒng)的問題。他發(fā)現(xiàn)在可視排隊系統(tǒng)中，個體顧客的決策往往背離整個社會的利益偏好。這種差異是由于個體最優(yōu)行為所產(chǎn)生的負面作用引起的。每個個體顧客為了追求自身利益最大化而導致系統(tǒng)過度擁塞，使得整個社會的福利銳減。這個結(jié)論在許多類型的可視排隊經(jīng)濟學模型中都是成立的，此后的部分研究工作也是在此模型基礎(chǔ)上的拓展。hassn對naor的模型進行了改進，提出了lcfs一pr模型并對此進行了初步研究。他提出了一種新的方法，在此方法下，即使不對顧客收取費用，也能達到社會福利最優(yōu)。隨后，olson，nalebuff和landsburs都分別對

11、此類模型進行了研究。從服務員利潤最大化的角度考慮，naor在他的模型中提出了為使利潤最大化而對顧客收取的費用要高于社會所希望收取的費用的觀點。knudsen對此結(jié)論進行了一般化，考慮了多服務員非線性費用函數(shù)的復雜情況。simonovits也證明了在gl/m/s排隊系統(tǒng)中也可以得出類似的結(jié)論。yechiali在gl/m/i排隊模型中，指出了為使利潤最大化應如何計算對顧客的收費額度。他考慮了兩種情況，一種是各個顧客相互獨立，一種是所有顧客聯(lián)合起來提出一個價格上限。rue和rosenshine對價格上限的靈敏度進行了考量。larsen，afeche和mendelson對naor的模型進行了另一個角度

12、的一般化。他們假設顧客的服務價值(service value)是隨機變量而不是相同的恒定的常數(shù)。與naor所得出的相關(guān)結(jié)論一致，即為使利潤最大化而對顧客收取的費用要高于(或等于)社會所希望收取的費用。然而，edelson和hildebrand發(fā)現(xiàn)如果假設顧客的時間價值(time value)也不相同，則此結(jié)論不一定成立。schroeter則考慮了時間價值服從均勻分布的情況。devany考慮了服務需求是對顧客所收取費用額度的函數(shù)的可視排隊模型，得到的主要結(jié)果就是由于服務員對顧客收取的費用過高，使得顧客的實際均衡到達率相對于社會最優(yōu)到達率要低得多。miller和buckman考慮了一個具有隨機服務

13、價值的m/m/s/s消失可視排隊系統(tǒng)，此系統(tǒng)不會產(chǎn)生隊列，顧客一旦發(fā)現(xiàn)系統(tǒng)滿員則立即消失。此外，學者們還根據(jù)當時的經(jīng)濟學實例提出了一些較貼合實際的可視排隊經(jīng)濟學模型。chen和frank通過在naor的模型中引入貼現(xiàn)率(discount rate)來使得原始模型更一般化，利用相同的貼現(xiàn)率，顧客和服務員都設法使自己的貼現(xiàn)效益最大化。ackere和ninios則通過仿真方法考慮了服務員為設備做廣告的排隊模型。近兩年，單純考慮可視排隊的文獻相對較少。economou和kanta考慮了一個具有非可靠單服務員的可視馬爾可夫排隊模型，導出了顧客的均衡閡值策略。1.1.2 不可觀察隊列的歷史及發(fā)展現(xiàn)狀首先發(fā)

14、現(xiàn)基本的不可視排隊模型性質(zhì)的是edelson和hildebrand，他們對naor的模型進行了改進，取消了隊長可視的條件而假定隊長不可視。與可視排隊一樣，得出了個體顧客為了追求自身利益最大化而導致系統(tǒng)過度擁塞的結(jié)論。而后，balachandran和srinidhi，chen和frank又對此進行了研究，而且chen和frank發(fā)現(xiàn)顧客需求的增加會導致價格下降。balachandran考慮了服務設施具有固定運行成本的不可視m/g/1排隊模型，證明了納什均衡下顧客的到達率是唯一確定的。針對可視和不可視兩類模型的異同，hassin對可視與不可視排隊模型的社會福利與服務員利潤進行了比較，而larsen

15、則利用仿真方法對可視與不可視模型的這兩個指標進行了比較。ehen和frank則假設“登記費”(registerfee)固定，對比了可視與不可視模型的有效到達率。近些年，關(guān)于可視和不可視排隊之間對比的研究也有進展。stein等分別考慮了不同信息下的可視和不可視排隊博弈模型，顧客成批到達且不許中途違約，用大量實驗對其進行了平衡策略分析。burnetas和economou考察了可視(幾乎可視)和不可視(幾乎不可視)情形下具有啟動時間的markov排隊中顧客的均衡策略問題。guo和zipkin則討論了三種具有不同滯后信息的排隊模型，包括完全可視、部分可視和不可視類，比較這些信息類對顧客的平衡行為和系統(tǒng)

16、的影響。1.2 研究意義和發(fā)展動向 排隊經(jīng)濟學的研究為工商、交通、公用事業(yè)、軍事等部門中隨機聚散現(xiàn)象及各種排隊性質(zhì)提供了理論基礎(chǔ)，也為合理設計和管理排隊系統(tǒng)提供了依據(jù)。運用排隊經(jīng)濟學的一些研究成果，可以科學管理和有效使用一個服務系統(tǒng)，使它既能滿足顧客需求，又能實現(xiàn)社會最優(yōu)化與費用最小。有效解決通訊、運輸、以及實際中各種排隊問題。從1969年naor的第一份研究成果問世開始，迄今為止在排隊經(jīng)濟學方面已經(jīng)存在大量的文獻可供后續(xù)研究的參考。然而近些年來，隨著博弈論的迅速發(fā)展，以及實際排隊經(jīng)濟學案例的不斷復雜化，現(xiàn)存的大部分文獻所研究的排隊經(jīng)濟學模型的假設結(jié)構(gòu)和限定條件相對比較簡單，貼合實際的系統(tǒng)制約

17、因素考慮得并不周全，因而與當今的經(jīng)濟生活脫節(jié)，不能研以致用。當今，對排隊論的研究主流越來越趨于人性化排隊。通過研究顧客和服務機構(gòu)管理者的心理，來預知和分析均衡狀態(tài)下博弈雙方的行為。例如單就顧客來說，顧客可以判斷何時退出隊列會使自己后悔值最小，在不完全信息下顧客如何估計剩余效用而做出是否排隊的決策。在顧客被告知各種不完全服務信息的情形下，合理并開創(chuàng)性地假設顧客心理遵循最大嫡原理，從而對實際的服務信息做出推測，用以指導其進行決策，秉承人性化排隊的理念。1.3 論文結(jié)構(gòu)論文主要研究了排隊理論中各種排隊系統(tǒng)的均衡解及可觀察不可觀察隊列的社會最優(yōu)問題。共分為五章，內(nèi)容包括：緒論、排隊經(jīng)濟學簡介、單服務窗

18、排隊模型分析、社會最優(yōu)與利潤最大化分析、總結(jié)。第一章，緒論。主要介紹了排隊經(jīng)濟學的歷史和發(fā)展現(xiàn)狀，研究意義和發(fā)展動向，并分別對可觀察及不可觀察隊列的歷史分開介紹；第二章，排隊經(jīng)濟學簡介。主要介紹了簡單的排隊問題及排隊經(jīng)濟學的基本概念，為后邊提供理論基礎(chǔ)；第三章，單服務窗排隊模型分析。主要介紹了各種但服務窗牌多模型及其均衡解，即m/m/1模型及其變體模型的均衡解分析；第四章，社會最優(yōu)與利潤最大分析。主要就可觀察與不可觀察隊列，分別分析其社會最優(yōu)與利潤最大條件；第五章，總結(jié)?？偨Y(jié)了文章所研究的內(nèi)容，以及存在的問題。第2章 排隊經(jīng)濟學簡介2.1 排隊問題的基本概念2.1.1 排隊問題概述眾所周知，某

19、些資源、設備或空間（場地）的有限性及社會各部門對它們的需求是存在排隊現(xiàn)象的主要因素，而諸如服務機構(gòu)的管理水平低劣，服務窗（員）的素質(zhì)差，效率不高，或顧客的無計劃性以及其他原因也往往使不該有的排隊現(xiàn)象出現(xiàn)。我們所要討論的排隊論是人們研究大量服務過程的一門數(shù)學理論。在社會生活中碰到的排隊現(xiàn)象，諸如到商場購物，去圖書館借閱書刊、資料，汽車到加油站加油，船舶停靠碼頭，在公共電話亭打電話，將有毛病的電器送維修部門進行維修，病人去醫(yī)院掛號看病，將有關(guān)數(shù)據(jù)輸入計算機進行存儲等，均可歸結(jié)為顧客與服務窗之間的一種服務關(guān)系，并可用框圖表示這類排隊過程，如圖2.1.1所示。圖2.1.1 排隊模型框圖2.1.2 排隊

20、系統(tǒng)的特征及組成輸入過程輸入過程是對顧客到達系統(tǒng)的一種描述。（）顧客總體可以有限或無限（如流入水庫的水）；（）顧客到達系統(tǒng)的方式可以逐個或成批；（）顧客相繼到來時間間隔可分為確定型（比如定期航班、定期的課程表等）和隨機型（比如看病的病人、候車的旅客、進港口的船舶）；（）顧客到達系統(tǒng)可以是獨立的或相關(guān)的（獨立意即某時刻前到達的顧客對該時刻后到達的顧客無影響），輸入過程可以是平穩(wěn)、馬爾可夫、齊次的等。排隊規(guī)則排隊規(guī)則是服務窗對顧客允許排隊及對排隊次序和方式的一種約定。排隊規(guī)則可分為種制式。損失制顧客到達系統(tǒng)時，如果系統(tǒng)中所有服務窗均被占用，則到達的顧客隨即離去，比如打電話時碰到占線，用戶即重撥或離

21、去另找地方或過些時間再打；又如旅店客滿謝客，掛牌大夫限額掛號，計算機限定的內(nèi)存等均為此種情形。等待制顧客到達系統(tǒng)時，雖然發(fā)現(xiàn)服務窗均忙著，但系統(tǒng)設有場地供顧客排隊等候之用，于是到達系統(tǒng)之顧客按先后順序進行排隊等候服務。通常的服務規(guī)則有先到先服務，后到先服務（比如倉庫中同種物品堆壘后的出庫過程），隨機服務，優(yōu)先服務（比如郵政中的快件與特快專遞業(yè)務，重危病人的急診，交通中讓救火（護）車、警車及迎賓車隊優(yōu)先通過，設立專用車道）等。混合制它是損失制與等待制混合組成的排隊系統(tǒng)，此系統(tǒng)僅允許有限個顧客等候排隊，其余顧客只好離去永不再來；或者顧客中有的見到排隊隊伍而不愿費時等候，當隊伍短時愿排隊等候服務；也

22、有排隊等候的顧客當?shù)群驎r間超過某個時間就離隊而去均屬這種系統(tǒng)。服務窗（員）（）系統(tǒng)可以無窗口（如自選自付款購物）、一個窗口或多個窗口為顧客進行服務。（）在多個服務窗情形，顧客排隊可以平行多隊排列，串列或并串同時存在的混合排隊。（）一個服務窗可以為單個顧客或成批顧客進行服務。（）各窗口的服務時間可為確定型（如交通路口紅綠燈亮的時間、各單位固定的上下班時間）或隨機型。服務時間往往假定是平穩(wěn)的。排隊系統(tǒng)的目標參量（或運行指標）（）絕對通過能力，表示單位時間內(nèi)被服務完顧客的均值。（）相對通過能力，表示單位時間內(nèi)被服務完顧客數(shù)與請求服務顧客數(shù)的比值。（）系統(tǒng)排隊長度均值，表示系統(tǒng)內(nèi)顧客數(shù)（排隊等候顧客加

23、上正被服務顧客數(shù)）的均值。（）排隊等候顧客的平均隊列長度，表示系統(tǒng)內(nèi)排隊等候顧客數(shù)的均值。注：如果（或）較大，那么說明該系統(tǒng)的工作效率較低。（）顧客在系統(tǒng)內(nèi)逗留時間的均值；顧客排隊等候服務的時間的均值；服務時間的均值定義為；顯然有 （）（）服務窗連續(xù)繁忙的時間長度，即忙期，它是隨機變量。（）對損失制排隊模型，系統(tǒng)的損失概率損，即系統(tǒng)滿員概率。2.1.3 排隊模型的分類與記號記 為顧客相繼到達系統(tǒng)的間隔時間 的概率分布； 為服務窗口所耗費的服務時間的概率分布；為服務系統(tǒng)內(nèi)服務窗的個數(shù)； 為系統(tǒng)內(nèi)（最大）排隊容量或顧客在系統(tǒng)中排隊所允許的（最大）長度（包括正在服務和排隊等待的顧客）。又令 為負指數(shù)

24、分布；為確定型分布；為階愛爾蘭（）分布；為一般分布；為一般獨立的分布。通常用記號（或）來表達排隊模型。為方便起見，當系統(tǒng)最大排隊容量為時，就可略寫為，舉例如下。排隊模型表示顧客相繼到達系統(tǒng)的間隔時間服從負指數(shù)分布，而服務時間也服從負指數(shù)分布，系統(tǒng)內(nèi)設有個服務窗，系統(tǒng)容量為無限（充分大即可）的等待制排隊模型。排隊模型表示顧客到達的間隔時間和服務時間均為負指數(shù)分布，有個服務窗且系統(tǒng)容量為 的損失制排隊模型。排隊模型表示顧客到達的間隔時間為一般分布，服務時間為負指數(shù)分布，只設有一個服務窗且系統(tǒng)容量為無限的等待制排隊模型。排隊模型表示顧客到達的間隔時間為一般分布，服務時間為一般獨立分布，只設有一個服務

25、窗且系統(tǒng)容量為無限的等待制排隊模型。排隊模型表示每批有個顧客到達系統(tǒng)，且批與批到達間隔時間是負指數(shù)分布，服務時間為負指數(shù)分布，只有一個服務窗，且系統(tǒng)容量為無限的等待制排隊模型。排隊模型表示顧客到達的間隔時間與服務時間均為負指數(shù)分布，系統(tǒng)內(nèi)有個服務窗，顧客源為且系統(tǒng)容量也為的閉合式（循環(huán)）排隊模型。2.2 馬爾可夫鏈簡介設（），是定義在概率空間（，f，）上，而取值在非負整數(shù)上的隨機變量序列，用“”表示時刻系統(tǒng) 處于狀態(tài)這一事件。稱為在事件“”出現(xiàn)的條件下，事件“”出現(xiàn)的條件概率，又稱它為系統(tǒng)的一步轉(zhuǎn)移概率。如果對任意的非負整數(shù)，及一切，有= （）則稱是一馬爾可夫鏈（markov chain）。當

26、與起始時刻無關(guān)時，則稱為齊次的馬爾可夫鏈，并將式（）稱為馬爾可夫性（無后效性或無記憶性）。若將“”看作“現(xiàn)在”，將“”看作“將來”，“，”看作“過去”，則式（）表示在已知“現(xiàn)在”的條件下，“將來”與“過去”是獨立的。今后考察齊次馬爾可夫鏈的情形，可簡記為。易知 （）稱矩陣為馬爾可夫鏈 的一步轉(zhuǎn)移矩陣。式（）表明矩陣中每個元素非負且每一行之和為。又稱為馬爾可夫鏈 的步轉(zhuǎn)移概率。而為 的步轉(zhuǎn)移矩陣。容易驗證它有如下性質(zhì)： （）下述的kolmogorov-chapman方程（以后簡稱k-c方程）成立 （）事實上 ， 利用 及馬爾可夫性 ， 并注意 可直接得到上式也可用矩陣形式寫出特別地若記，則有；并

27、稱為齊次馬爾可夫鏈x的初始分布。又稱為齊次馬爾可夫鏈x的絕對概率。利用全概率公式及馬爾可夫性，有 （225）且當時 （226）此式表明齊次馬爾可夫鏈x的任意有限維分布 ， 完全可由其初始分布及一步轉(zhuǎn)移概率確定 。 下面不加證明地給出x為馬爾可夫鏈的兩個等價定義：a. x為馬爾可夫鏈的充分必要條件是對n時刻以前的任一事件b與n時刻以后的任一事件a，只要,就有b. x為馬爾可夫鏈的充分必要條件是只要，就有2.3 納什均衡 求解博弈問題的關(guān)鍵在于尋找各博弈方都不愿或不會單獨改變自己策略的策略組合，只要這種策略組合存在且是唯一的，博弈問題就有絕對確定的解。這種各博弈方都不愿或不會單獨改變自己策略的策略

28、組合就是博弈論中最重要的一個概念：“納什均衡”。在納什均衡點上，如果某個參與者的策略發(fā)生變化而其他參與者的策略保持不變，會導致這個參與者的獲利減少。納什均衡點的概念和求解方法已經(jīng)成為博弈論中最重要的工具。 定義：在n個參與者的標準式博弈中，如果策略組合滿足下面這個條件，對于每個參與者i， 是它針對其他n-1個參與者所選策略的最優(yōu)反應策略，則稱策略組合是該博弈的一個納什均衡點，即：對于所有都成立。其中，表示參與者i的策略空間，表示除了參與者i之外其他n-1個參與者所選策略的集合，表示參與者i在策略空間中所選的任意策略，表示參與者i的博弈收益函數(shù)。 從納什均衡的定義可以看出，有些博弈有一個或多個納

29、什均衡點，而有些博弈是沒有納什均衡點的。2.4 排隊經(jīng)濟學簡介排隊是我們在日常生活中經(jīng)常遇到的現(xiàn)象，如顧客到商店購買物品形成的排隊;上下班坐公共汽車，等待公共汽車的排隊;文件等待打印和發(fā)送;電話局的占線;故障機器的停機待修;水庫的存貯調(diào)節(jié)等。由于顧客到達間隔時間和服務時間具有隨機性，使排隊現(xiàn)象不可避免。一般來說，從經(jīng)濟學角度看，排隊是一種分配稀缺商品(服務資源)的辦法。在資源配置不足的情況下，往往不得不引用排隊機制來解決分配問題，因為排隊可最大限度的節(jié)約顧客的時間成本，使資源得到相對的優(yōu)化配置。長期以來，經(jīng)濟學家發(fā)現(xiàn)在排隊服務系統(tǒng)中，顧客為了使自身的利益最大化而獨立行動，每位顧客的最優(yōu)行為都受

30、到系統(tǒng)管理者和其他顧客的制約和影響，其結(jié)果就導致了一個均衡格局的形成，這種均衡的格局在經(jīng)濟學和博弈論中被稱為“納什均衡”或“非合作博弈均衡”(nashequilibrium)。然而，這個均衡從整個全局或社會角度看很可能并不是最優(yōu)的(經(jīng)典的案例就是納什提出的“囚徒的困境”問題)，由此大量經(jīng)濟和排隊論學者針對這一經(jīng)濟學現(xiàn)象在排隊論和博弈論背景和框架下開始了研究工作。排隊經(jīng)濟學不僅研究了排隊系統(tǒng)的一般特征，而且研究了各種不同的排隊系統(tǒng)模型。并且給出了求解公式。所謂求解，就是用數(shù)學方法來確定用來判斷排隊系統(tǒng)運行優(yōu)劣的數(shù)量指標。比如系統(tǒng)空舶概率；隊長，也就是排隊等待和正在接受服務的顧客數(shù)的平均值，以及顧

31、客排隊等待時間的平均值等等。確定 這些數(shù)量指標的目的，在于研究排隊系統(tǒng)的運行效率、提高排隊系統(tǒng)的服務質(zhì)量，找出改進的措施。當然，排隊系統(tǒng)的類型和結(jié)構(gòu)是多種多樣的，有很多情況很難用數(shù)學方法來分析、求解。第3章 單服務窗排隊模型均衡分析單個服務窗的排隊系統(tǒng)模型，即 系 統(tǒng)只設一個服務窗的情況。假定顧客到達系統(tǒng)的間隔時間服從負指數(shù)分布，并且顧客是相互獨立地到達系統(tǒng)；又服務窗為每一顧客的服務時間也服從負指數(shù)分布。3.1 單服務窗損失制排隊模型m/m/1/13.1.1 模型簡介排隊模型是指系統(tǒng)內(nèi)只設一個服務窗，系統(tǒng)容量為（即僅有一個排隊位置而無排隊等待位置），顧客到達和窗口 服務時間 均為負 指數(shù)分布，

32、且它們各自的參數(shù)為與的排隊系統(tǒng)。如顧客到達時，發(fā)現(xiàn)服務窗正忙著，他即離去另求別處服務。比如可將只設一條外線的電話交換臺看作此種排隊模型。 因系統(tǒng)只有單個服務窗，故系統(tǒng)只能有兩種可能狀態(tài)：（服務窗空閑著）及（服務窗忙著）。于是，系統(tǒng)的狀態(tài)流圖如圖.所示。3.1.2 nash均衡由氏微分方程，可知時刻系統(tǒng)處于空閑或忙著的概率（）或（）分別滿足下列方程 （3.1.1）及正則性 （3.1.2）因系統(tǒng)僅有兩個互通的狀態(tài)，故必存在平穩(wěn)分布，也即存在，事實上，由式（3.1.3）知 （3.1.4）其中，表示系統(tǒng)的負荷水平或強度。 當系統(tǒng)中已有一個顧客時，新來的顧客只好離去，故就是系統(tǒng)的損失概率，它等于 （3.

33、1.5）單位時間內(nèi)平均損失的顧客數(shù)和平均進入系統(tǒng)的顧客數(shù)各為 (3.1.6) (3.1.7)從而 (3.1.8)3.2 單服務窗等待制排隊模型m/m/13.2.1 模型簡介設系統(tǒng)內(nèi)只有單個服務窗口。顧客按參數(shù)為的泊松分布到達，如顧客到達系統(tǒng)時服務窗正忙著，則排隊等待服務；且顧客到達的時間間隔與服務窗為每個顧客服務的時間均為負指數(shù)分布；平均服務率為。易知該系統(tǒng)構(gòu)成一個生滅過程，其相應的密度矩陣q中各個元素為 （3.2.1）由此可畫出其狀態(tài)流圖（本節(jié)考慮顧客是無限的），如圖3.2.1所示。圖排隊模型的狀態(tài)流圖此處狀態(tài)表示系統(tǒng)內(nèi)有個顧客，服務窗正忙著，且有個顧客排隊等待。3.2.2 nash均衡根據(jù)

34、公式（），直接寫出狀態(tài)概率所滿足的微分方程式為 （3.2.2）我們感興趣的是當時，系統(tǒng)能否從暫態(tài)進入穩(wěn)態(tài)。理論上可以證明，當時，系統(tǒng)存在平穩(wěn)分布，記為。此時，式（）可以改寫為 （3.2.3）于是，可以解出 （3.2.4）再由正則性得即是服務窗空閑的概率，并且恰好是服務窗忙著的概率。越大，服務窗越忙。有時也稱為系統(tǒng)的服務強度或負荷水平。由上易知利用式（）可以求出相應的目標參量：（） 系統(tǒng)內(nèi)顧客的均值（包括正被服務和排隊等候的顧客均值）。 （3.2.5） （） 由公式，可得顧客在系統(tǒng)內(nèi)平均逗留時間 （3.2.6）（） 系統(tǒng)內(nèi)排隊等候的平均顧客數(shù)其中，為正被服務的顧客均值。因正被服務的顧客數(shù)或為（窗

35、口空閑）或為（窗口忙著），它們對應的概率為及。于是從而 （3.2.7）（） 據(jù)公式，顧客平均排隊等待時間為 （3.2.8）（） 系統(tǒng)內(nèi)多于個顧客的概率為3.3 單服務窗混合制排隊模型3.3.1 模型簡介假設系統(tǒng)只有單個服務窗口，顧客到來的間隔時間服從負指數(shù)分布，參數(shù)為；服務時間是參數(shù)為的負指數(shù)分布；又設系統(tǒng)只有 個排隊容量（又稱 個截止隊長）。當系統(tǒng)中已有 個顧客時，新來的顧客不再進入系統(tǒng)排隊而立即離去另尋他處服務。這樣，在任何情況下，排隊長度均不會超過，稱這類系統(tǒng)為即時拒絕系統(tǒng)。根據(jù)上述，可以畫出系統(tǒng)的狀態(tài)流圖，如圖所示。圖狀態(tài)流圖3.3.2 nash均衡因系統(tǒng)內(nèi)所有狀態(tài)互通，且狀態(tài)有限，故

36、必存在平穩(wěn)分布。按第章氏代數(shù)方程的一般規(guī)律，可以寫出下列方程：對0狀態(tài)，有，故；對1狀態(tài)，有，故；對m-1狀態(tài)，有，故；由正則性 （3.3.1）可得 （3.3.2）當=1時現(xiàn)對求相應的目標參量：（） （3.3.3）這是當系統(tǒng)中已有個顧客，新來的顧客不再排隊而即離去另尋他處服務的概率。（） （3.3.4）（） （3.3.5）（） 因為 （3.3.6）所以 （3.3.7）（） 單位時間內(nèi)平均損失的顧客數(shù)為，而單位時間內(nèi)平均到達系統(tǒng)的顧客數(shù)（也稱系統(tǒng)的有效到達率）為 （3.3.8）（） 據(jù)公式可得顧客平均等待時間、平均逗留時間分別為 （3.3.9） （3.3.10）（） 服務窗平均服務強度實際服務強

37、度當=1時，于是3.4 可變服務率的排隊模型3.4.1 模型簡介第一種情況：假定在單服務窗的排隊模型中，顧客按泊松流到達某系統(tǒng)，到達強度為，又服務窗在為顧客的服務過程中，視窗口前顧客的排隊長度改變其平均服務強度（或時間），即當排隊長度超過某個時，服務窗用快速服務率，反之則用慢速服務率。這樣，可畫出系統(tǒng)狀態(tài)流圖，如圖所示。圖可變服務率的狀態(tài)流圖之一3.4.2 nash均衡據(jù)k氏代數(shù)方程的一般規(guī)律，可寫出如下方程：對0狀態(tài)，有，故；對1狀態(tài)，有，故；對n-1狀態(tài)，有，故；對n狀態(tài)，有，故；對n+r-1狀態(tài)，有，故；總之有 （3.4.1）當時，由正則性可知 （3.4.2）于是 （3.4.3） （3.

38、4.4）再由little公式可得 （3.4.5） （3.4.6）第4章 社會最優(yōu)與利潤最大分析處在服務系統(tǒng)的顧客獨立行動來最大化他們的利益。然而，每個顧客的最優(yōu)選擇取決于其他顧客的行為和系統(tǒng)管理者。結(jié)果未必是從社會整理利益來看最優(yōu)的模式。因此，我們就要研究怎樣的行為選擇可以使社會效用最大化。先來介紹一些基本的概念：n 策略：令表示一個有限的顧客集合，令表示表示其中第i個顧客可能采取的一系列行為。純策略是指中的一個行為。混合策略是指隨機的選取中的某個行為的一個函數(shù)，用表示。則策略表示為，其中。n 付費：每個顧客都與一個付費函數(shù)相聯(lián)系。n 均衡：最優(yōu)選擇即均衡，用公式表示為：4.1 可觀察隊列在排

39、隊經(jīng)濟學中，僅對于顧客來說，可觀察排隊是指顧客在進入系統(tǒng)之前對系統(tǒng)的相關(guān)參數(shù)信息知情，比如當時的隊列長度，服務率，服務價格，服務員所處狀態(tài)等。4.1.1 社會最優(yōu)這一部分源自于lcfs-pr政策下的閾值（極限）均衡策略。這個閾值與社會最佳閾值相一致。讓n作為隊列的最大可能長度，也就是說，一個顧客總是當在他前面有n個人的時候改變策略，這個n包括正在辦理的，讓fn作為顧客在lcfs-pr隊列位置n的期望利益,當所有在n+1位置的人都改變策略。當然，fn關(guān)于n是單調(diào)遞減的，且是最大值，所以fn0，下面我們通過模型確定fn的參數(shù)值。引理：證明：在既定條件下，顧客最終得到r的好處的可能性與投機商人失敗問

40、題的失敗可能性是一樣的，當最初的資產(chǎn)是n，目標是n+1，并且每一回合獲勝的可能性為，讓q=1-p，則失敗可能性為：由r乘的這個值是為了防止到達位置n+1而放棄計劃的位置n的個人效用的積極作用。消極作用則是，注意到直到游戲結(jié)束的每一輪的期望值，投機商人要么獲益要么損失，是：用這個結(jié)果乘以來獲取系統(tǒng)中這樣一個顧客的預計執(zhí)行時間，然后通過c來獲取預計等待費用?；谏鲜?，當且僅當fn>0時，令上式右邊為gn，注意到：函數(shù)g（n）是無限函數(shù)且隨著n嚴格單調(diào)增大，對于任何給定的 > 0并且g(0) = 0。因此存在的確定的值使得，并且這是保持隊列“穩(wěn)定”的顧客的最大人數(shù)。在naor的研究中，讓

41、被定義在真實隊列之上，并讓成為的唯一解，則。并且：因此，這就是說:比起社會期望，個人最優(yōu)能導致更長的隊伍。就意義上而言這個結(jié)果是好，且適用于其他更普遍的排隊模型。4.1.2 利潤最大化現(xiàn)假設收取服務費，作為反對資金募集是為了轉(zhuǎn)移支付這一社會觀點，現(xiàn)在他們是服務費用，該模型假定服務費是決定顧客是否加入隊列的基礎(chǔ)。因此，一個顧客只有在價值r至少和預計足價相等時才會加入隊伍。另外一個衡量這一行為的方法是顧客通過r-p來評估服務。給定p，則最大的隊伍長度為記得，qn表示系統(tǒng)中有n個可觀察的顧客的概率，而且，n也是他們接受的閾值。n是同一時間可能出現(xiàn)的顧客數(shù)量的最大值。因此，qn是止步概率。有效的到達率

42、是，利潤率是。服務系統(tǒng)選擇所需的閾值n并且設置符合該閾值的最高價格，也就是：服務系統(tǒng)的利潤是：這里。利潤最大化的閾值滿足以下兩個條件：和。因此有或者假設。請注意，在左側(cè)的一小部分是積極的，這樣雙方都可以分解在不改變不平等號方向的情況下。這將導致將n代成n+1，并且改變不等號方向，第二個條件變?yōu)檫@兩個條件可以概括為在的情況下，通過下邊的關(guān)系，定義一個基于的變量：相應的盈利率是很顯然，所以，。同時，可以得出得出如下結(jié)論：在lcfs-pr隊列中，沒個顧客的預期福利與他到達時間的隊列長度都是獨立的。利潤最大化的費用恰好等于預期的福利價值。在這樣的費用下，沒個顧客都加入隊列，而且他加入后的行為獨立于費用

43、。4.2 不可觀察隊列不可觀察排隊是指這些系統(tǒng)參數(shù)信息在顧客作出決策之前不被告知顧客。對于較早些的文獻一般都是指隊長信息可視與否，而現(xiàn)今其含義越來越豐富。當然，如果是多服務員排隊，服務員之間也存在相互之間的信息可觀察與否的問題，比如服務率和價格等。模型假設：n 當客戶需要服務時，他只能選擇加入隊列或不加入。在他做出決定之前不可能觀察到隊列長度。n 服務紀律性強并且連續(xù)工作。正如在可觀測模型中，加入隊列的客戶給別人施加負外部性，因此除非隊列得到調(diào)節(jié)，否則個別優(yōu)化將會導致過度擁塞。4.2.1 均衡當入場費p和潛在到達率確定時，我們開始評估顧客在平衡時的行為。顧客有兩種純策略可供選擇：加入或者不加入

44、隊列。一個純策略或混合策略可以用q描述，0q1，表示加入的概率。鑒于入場費是p，我們用表示隊列平衡概率，以及相應的平衡（有效的）到達率用表示。當然，=。當有效到達率是時，我們制定期望等待時間。這一函數(shù)是連續(xù)的并且是單調(diào)遞增的。對于加入隊列的顧客來說，純收益是服務價值，r，減去全價，p+cw（）。我們區(qū)分三種情況：n p+cw（0）r。在這種情況下，即使沒有其他顧客加入，加入的顧客的純收益不樂觀。然而，在概率=0的情況下加入的策略是一個均衡策略，而且，沒有其它均衡策略。此外，在這種情況下，不加入是占優(yōu)策略。n p+cw（）r。在這種情況下，即使所有潛在顧客加入，他們都享受到積極的收益。而且，在概

45、率=1的情況下加入的策略是一種均衡策略，并且沒有其它均衡策略。此外，在這種情況下，加入是占優(yōu)策略。n p+cw（0）<r<p+cw（）。在這種情況下，如果=1，那么，加入的顧客享受積極的收益。因此，這不可能是平衡策略。同樣，如果=0，加入的顧客相對不加入的顧客而言享受積極的收益。因此，這也不可能是一個平衡策略。因此，存在一個唯一的均衡策略，此時，=，并且滿足cw（）=r-p。將w（）=代入，我們得到如下表格。圖4.1 最好的應答和加入概率4.2.2 社會最優(yōu)我們現(xiàn)在來關(guān)注社會最優(yōu)問題。設最理想的社會加入概率為，最理想的社會加入比率為，此處，=。那么，=arg由于是嚴格凸函數(shù)，最大化

46、的函數(shù)是嚴格凹函數(shù)，并且有唯一的最大值。將w（）=代入，我們得到如下解只要他在0, 區(qū)間內(nèi)，就是最佳解。在rc的假設條件下，此解是積極的。因此，如果- ，那么。否則，=。令為最優(yōu)到達率下的社會福利。表4.2總結(jié)了最佳加入策略。表4.2 社會最優(yōu)策略在假設rc下，。因此，正如在可觀察隊列里一樣，個別優(yōu)化導致隊列長度超過社會理想。這個差距在實行適當入場費的情況下可以被糾正，正如下一部分討論的一樣。如果，那么4.2.3 利潤最大化我們現(xiàn)在考慮一個設置了利潤最大化的入場費的壟斷服務器。壟斷不留下一個積極的消費者剩余，因為在這種情況下，入場費可以在不減少到達率的情況下增加。所以，。壟斷的問題是在和的條件

47、下最大化記得，社會目標是最大化服務器和客戶的總福利，也就是。一項消去，反應社會效用是添加劑這樣的假設，因此，從社會的角度看，入場費只是轉(zhuǎn)移支付，沒有社會福利。因此，社會問題是在0的條件下，最大化。圖3.2 壟斷價格和到達率社會最優(yōu)的到達率可誘發(fā)適當?shù)娜雸鲑M，這也最大限度地提高利潤總額。當此費用等于當，利潤最大化選擇最高收費，誘導出這個比率，即。一個社會規(guī)劃者會選擇這個費，或任何小的費用，因為任何這樣的選擇，導致相同的最佳到達率，。4.3 相對優(yōu)先權(quán)在排隊系統(tǒng)中顧客越多，單個顧客獲得服務能力的比率也就相越低。相對優(yōu)先權(quán)是指，每一位顧客獲得一個相對優(yōu)先權(quán)參數(shù)并根據(jù)參數(shù)值的大小成比例的獲得服務資源。

48、如果系統(tǒng)中存在n類顧客，且每類顧客數(shù)為，賦予每類顧客的相對優(yōu)先權(quán)參數(shù)分別為，其中，則每一個第i類顧客可獲得比例的服務能力。特別的，所有第i類顧客獲得的總服務能力比例為。4.3.1 模型描述考慮具有兩類顧客的無記憶單服務員排隊經(jīng)濟學模型。在此模型中，服務員對兩類顧客的服務率不盡相同，即具有服務差異。假設實行不可視排隊規(guī)則，且允許顧客在加入隊列前放棄離開，但不允許顧客加入隊列后中途違約。當然，沒有進入系統(tǒng)而離開的顧客沒有回報也沒有損失。服務員沒有權(quán)利任意選擇顧客的支付金額，即兩類顧客分別需支付各自固定的服務費用 。服務員唯一能控制隊列的手段就是選擇對兩類顧客服務的相對優(yōu)先權(quán)參數(shù)尸和。假設第i類顧客

49、的到達過程服從參數(shù)為，i=1，2的泊松到達過程，且到達率，i=1，2足夠大。服務員對第i類顧客的服務時間服從參數(shù)為的指數(shù)分布。同時，在每個第i類顧客的逗留時間內(nèi)，都承擔著每單位時間以的等待損耗 。當然，服務完成后也將獲得r;的服務回報。假設，。每個進入系統(tǒng)的第i類顧客都將支付服務費用，且此費用金額將公布于眾，以使得顧客做出是否進入系統(tǒng)的決定。因此，任意一個第i類顧客在接受完服務之后的平均收益為，其中表示此顧客在系統(tǒng)中的逗留時間(等待時間與服務時間之和)。假設第i類顧客以概率進入系統(tǒng)，實際有效到達率。定義，i=1,2為第i類顧客的平均逗留時間，并簡寫為。定義為兩類顧客的一對納什均衡到達率，為凈收

50、益與單位等待損耗的比率。因此，在均衡狀態(tài)下，不失一般性，假設，且系統(tǒng)穩(wěn)定，即4.3.2 納什均衡當時，有其中，。因此，假設第一類顧客相比第二類顧客獲得絕對優(yōu)先權(quán)，也就是且，則他們的逗留時間分別為綜合上式，得到兩類顧客的一對納什均衡到達率4.3.3 利潤最大化現(xiàn)在考慮當兩類顧客的支付費用一定的情況下，如何選擇相對優(yōu)先權(quán)參數(shù)來使得服務員的利潤最大化。這個問題其實就是選擇第一類顧客的相對優(yōu)先權(quán)參以使得的值最大化。首先，考慮第一種不等情。如果得到服務員的平均利潤率為定義最優(yōu)優(yōu)先權(quán)參數(shù)為成，則其可以通過求解上式的一階優(yōu)化條件而求得。 如果上式的解處于區(qū)間的內(nèi)部，則它是最優(yōu)解。否則，最優(yōu)解存在于兩個邊界點

51、之中。 類似地，考慮另一種不等情況。如果則需要在非空區(qū)間aminb，1內(nèi)使利潤最大化。 特別地，觀察一種特殊情況，即兩類顧客的支付費用相等的情況。假定，下圖描述了最優(yōu)優(yōu)先權(quán)參數(shù)為=0.2596，且其嚴格處于區(qū)間(a=0.2，b=0.3443)的內(nèi)部。第5章 總結(jié)本文首先根據(jù)現(xiàn)實中用到排隊經(jīng)濟學的諸多方面，提出了研究排隊經(jīng)濟學的必要性。簡單介紹了排隊論及博弈論有關(guān)的預備知識，以及排隊經(jīng)濟學的基本概念。其次，分析了排隊系統(tǒng)中一些常用簡單模型，包括其模型假設、均衡及其算法與公式推導。逐級增加假設條件，使其更貼合實際情況。再次，引進了可觀察與不可觀察隊列的概念，并對其分別進行分析，考慮社會最優(yōu)與利潤最

52、大化條件。并結(jié)合圖表進行分析。最后，隨著博弈論的迅速發(fā)展，以及實際排隊經(jīng)濟學案例的不斷復雜化，本文對排隊經(jīng)濟學模型的假設結(jié)構(gòu)和限定條件相對比較簡單，貼合實際的系統(tǒng)制約因素考慮得并不周全。總之，本論文簡單的完成了排隊經(jīng)濟學的簡介、基本模型的均衡分析，及可觀察不可觀察隊列的最優(yōu)化分析，可以為實際排隊問題提供一定的理論依據(jù)與參考。參考文獻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