數(shù)學建模算法大全排隊論及咖啡店創(chuàng)業(yè)計劃書

第六章排隊論模型排隊論起源于1909年丹麥工程師A.K．愛爾朗的工作，他對通話擁擠問題進行了研究。1917年，愛爾朗發(fā)表了他的著名的文章—“自動交換中的概率理論的幾個問題的解決”。排隊論已廣泛應用于解決軍事、運輸、維修、生產(chǎn)、服務、庫存、醫(yī)療衛(wèi)生、教育、水利灌溉之類的排隊系統(tǒng)的問題，顯示了強大的生命力。排隊是在日常生活中經(jīng)常遇到的現(xiàn)象，如顧客到商店購買物品、病人到醫(yī)院看病常常要排隊。此時要求服務的數(shù)量超過服務機構（服務臺、服務員等）的容量。也就是說，到達的顧客不能立即得到服務，因而出現(xiàn)了排隊現(xiàn)象。這種現(xiàn)象不僅在個人日常生活中出現(xiàn)，局的占線問題，車站、碼頭等交通樞紐的車船堵塞和疏導，故障機器的停機待修，水庫的存貯調(diào)節(jié)等都是有形或無形的排隊現(xiàn)象。由于顧客到達和服務時間的隨機性?？梢哉f排隊現(xiàn)象幾乎是不可避免的。排隊論（QueuingTheory）也稱隨機服務系統(tǒng)理論，就是為解決上述問題而發(fā)展的一門學科。它研究的內(nèi)容有下列三部分：（=1\*romani）性態(tài)問題，即研究各種排隊系統(tǒng)的概率規(guī)律性，主要是研究隊長分布、等待時間分布和忙期分布等，包括了瞬態(tài)和穩(wěn)態(tài)兩種情形。（=2\*romanii）最優(yōu)化問題，又分靜態(tài)最優(yōu)和動態(tài)最優(yōu)，前者指最優(yōu)設計。后者指現(xiàn)有排隊系統(tǒng)的最優(yōu)運營。（=3\*romaniii）排隊系統(tǒng)的統(tǒng)計推斷，即判斷一個給定的排隊系統(tǒng)符合于那種模型，以便根據(jù)排隊理論進行分析研究。這里將介紹排隊論的一些基本知識，分析幾個常見的排隊模型。§1基本概念1.1排隊過程的一般表示下圖是排隊論的一般模型。服務機構（服務時間隨機）顧客排隊顧客隨機達到顧客離去服務機構（服務時間隨機）顧客排隊圖中虛線所包含的部分為排隊系統(tǒng)。各個顧客從顧客源出發(fā)，隨機地來到服務機構，按一定的排隊規(guī)則等待服務，直到按一定的服務規(guī)則接受完服務后離開排隊系統(tǒng)。凡要求服務的對象統(tǒng)稱為顧客，為顧客服務的人或物稱為服務員，由顧客和服務員組成服務系統(tǒng)。對于一個服務系統(tǒng)來說，如果服務機構過小，以致不能滿足要求服務的眾多顧客的需要，那么就會產(chǎn)生擁擠現(xiàn)象而使服務質(zhì)量降低。因此，顧客總希望服務機構越大越好，但是，如果服務機構過大，人力和物力方面的開支也就相應增加，從而會造成浪費，因此研究排隊模型的目的就是要在顧客需要和服務機構的規(guī)模之間進行權衡決策，使其達到合理的平衡。1.2排隊系統(tǒng)的組成和特征一般的排隊過程都由輸入過程、排隊規(guī)則、服務過程三部分組成，現(xiàn)分述如下：1.2.1輸入過程輸入過程是指顧客到來時間的規(guī)律性，可能有下列不同情況：（=1\*romani）顧客的組成可能是有限的，也可能是無限的。（=2\*romanii）顧客到達的方式可能是一個—個的，也可能是成批的。（=3\*romaniii）顧客到達可以是相互獨立的，即以前的到達情況對以后的到達沒有影響；否則是相關的。（=4\*romaniv）輸入過程可以是平穩(wěn)的，即相繼到達的間隔時間分布及其數(shù)學期望、方差等數(shù)字特征都與時間無關，否則是非平穩(wěn)的。1.2.2排隊規(guī)則排隊規(guī)則指到達排隊系統(tǒng)的顧客按怎樣的規(guī)則排隊等待，可分為損失制，等待制和混合制三種。（=1\*romani）損失制（消失制）。當顧客到達時，所有的服務臺均被占用，顧客隨即離去。（=2\*romanii）等待制。當顧客到達時，所有的服務臺均被占用，顧客就排隊等待，直到接受完服務才離去。例如出故障的機器排隊等待維修就是這種情況。（=3\*romaniii）混合制。介于損失制和等待制之間的是混合制，即既有等待又有損失。有隊列長度有限和排隊等待時間有限兩種情況，在限度以內(nèi)就排隊等待，超過一定限度就離去。排隊方式還分為單列、多列和循環(huán)隊列。1.2.3服務過程（=1\*romani）服務機構。主要有以下幾種類型：單服務臺；多服務臺并聯(lián)（每個服務臺同時為不同顧客服務）；多服務臺串聯(lián)（多服務臺依次為同一顧客服務）；混合型。（=2\*romanii）服務規(guī)則。按為顧客服務的次序采用以下幾種規(guī)則：①先到先服務，這是通常的情形。②后到先服務，如情報系統(tǒng)中，最后到的情報信息往往最有價值，因而常被優(yōu)先處理。③隨機服務，服務臺從等待的顧客中隨機地取其一進行服務，而不管到達的先后。④優(yōu)先服務，如醫(yī)療系統(tǒng)對病情嚴重的病人給予優(yōu)先治療。1.3排隊模型的符號表示排隊模型用六個符號表示，在符號之間用斜線隔開，即。第一個符號表示顧客到達流或顧客到達間隔時間的分布；第二個符號表示服務時間的分布；第三個符號表示服務臺數(shù)目；第四個符號是系統(tǒng)容量限制；第五個符號是顧客源數(shù)目；第六個符號是服務規(guī)則，如先到先服務FCFS，后到先服務LCFS等。并約定，如略去后三項，即指的情形。我們只討論先到先服務FCFS的情形，所以略去第六項。表示顧客到達間隔時間和服務時間的分布的約定符號為：—指數(shù)分布（是Markov的字頭，因為指數(shù)分布具有無記憶性，即Markov性）；—確定型（Deterministic）；—階愛爾朗(Erlang)分布；—一般（general）服務時間的分布；—一般相互獨立（GeneralIndependent）的時間間隔的分布。例如，表示相繼到達間隔時間為指數(shù)分布、服務時間為指數(shù)分布、單服務臺、等待制系統(tǒng)。表示確定的到達時間、服務時間為指數(shù)分布、個平行服務臺（但顧客是一隊）的模型。1.4排隊系統(tǒng)的運行指標為了研究排隊系統(tǒng)運行的效率，估計其服務質(zhì)量，確定系統(tǒng)的最優(yōu)參數(shù)，評價系統(tǒng)的結構是否合理并研究其改進的措施，必須確定用以判斷系統(tǒng)運行優(yōu)劣的基本數(shù)量指標，這些數(shù)量指標通常是：(=1\*romani)平均隊長：指系統(tǒng)內(nèi)顧客數(shù)（包括正被服務的顧客與排隊等待服務的顧客）的數(shù)學期望，記作。(=2\*romanii)平均排隊長:指系統(tǒng)內(nèi)等待服務的顧客數(shù)的數(shù)學期望，記作。(=3\*romaniii)平均逗留時間：顧客在系統(tǒng)內(nèi)逗留時間（包括排隊等待的時間和接受服務的時間）的數(shù)學期望，記作。（=4\*romaniv）平均等待時間：指一個顧客在排隊系統(tǒng)中排隊等待時間的數(shù)學期望，記作。（=5\*romanv）平均忙期：指服務機構連續(xù)繁忙時間（顧客到達空閑服務機構起，到服務機構再次空閑止的時間）長度的數(shù)學期望，記為。還有由于顧客被拒絕而使企業(yè)受到損失的損失率以及以后經(jīng)常遇到的服務強度等，這些都是很重要的指標。計算這些指標的基礎是表達系統(tǒng)狀態(tài)的概率。所謂系統(tǒng)的狀態(tài)即指系統(tǒng)中顧客數(shù)，如果系統(tǒng)中有個顧客就說系統(tǒng)的狀態(tài)是，它的可能值是（=1\*romani）隊長沒有限制時，，（=2\*romanii）隊長有限制，最大數(shù)為時，，（=3\*romaniii）損失制，服務臺個數(shù)是時，。這些狀態(tài)的概率一般是隨時刻而變化，所以在時刻、系統(tǒng)狀態(tài)為的概率用表示。穩(wěn)態(tài)時系統(tǒng)狀態(tài)為的概率用表示?！?輸入過程與服務時間的分布排隊系統(tǒng)中的事件流包括顧客到達流和服務時間流。由于顧客到達的間隔時間和服務時間不可能是負值，因此，它的分布是非負隨機變量的分布。最常用的分布有泊松分布、確定型分布，指數(shù)分布和愛爾朗分布。2.1泊松流與指數(shù)分布設表示在時間區(qū)間內(nèi)到達的顧客數(shù)（），令表示在時間區(qū)間內(nèi)有個顧客到達的概率，即當合于下列三個條件時，我們說顧客的到達形成泊松流。這三個條件是：1o在不相重疊的時間區(qū)間內(nèi)顧客到達數(shù)是相互獨立的，我們稱這性質(zhì)為無后效性。2o對充分小的，在時間區(qū)間內(nèi)有一個顧客到達的概率與無關，而約與區(qū)間長成正比，即（1）其中，當時，是關于的高階無窮小。是常數(shù)，它表示單位時間有一個顧客到達的概率，稱為概率強度。3o對于充分小的，在時間區(qū)間內(nèi)有兩個或兩個以上顧客到達的概率極小，以致可以忽略，即（2）在上述條件下，我們研究顧客到達數(shù)的概率分布。由條件2o，我們總可以取時間由0算起，并簡記。由條件1o和2o，有由條件2o和3o得因而有，.在以上兩式中，取趨于零的極限，當假設所涉及的函數(shù)可導時，得到以下微分方程組：，.取初值，，容易解出；再令，可以得到及其它所滿足的微分方程組，即，.由此容易解得.正如在概率論中所學過的，我們說隨機變量服從泊松分布。它的數(shù)學期望和方差分別是；。當輸入過程是泊松流時，那么顧客相繼到達的時間間隔必服從指數(shù)分布。這是由于內(nèi)呼叫次數(shù)為零那么，以表示的分布函數(shù)，則有而分布密度函數(shù)為.對于泊松流,表示單位時間平均到達的顧客數(shù),所以就表示相繼顧客到達平均間隔時間，而這正和的意義相符。對一顧客的服務時間也就是在忙期相繼離開系統(tǒng)的兩顧客的間隔時間，有時也服從指數(shù)分布。這時設它的分布函數(shù)和密度函數(shù)分別是，我們得到這表明，在任何小的時間間隔內(nèi)一個顧客被服務完了（離去）的概率是。表示單位時間能被服務完成的顧客數(shù)，稱為平均服務率，而表示一個顧客的平均服務時間。2.2常用的幾種概率分布及其產(chǎn)生2.2.1常用的連續(xù)型概率分布我們只給出這些分布的參數(shù)、記號和通常的應用范圍，更詳細的內(nèi)容參看專門的概率論書籍。（=1\*romani）均勻分布區(qū)間內(nèi)的均勻分布記作。服從分布的隨機變量又稱為隨機數(shù)，它是產(chǎn)生其它隨機變量的基礎。如若為分布，則服從。（=2\*romanii）正態(tài)分布以為期望，為方差的正態(tài)分布記作。正態(tài)分布的應用十分廣泛。正態(tài)分布還可以作為二項分布一定條件下的近似。（=3\*romaniii）指數(shù)分布指數(shù)分布是單參數(shù)的非對稱分布，記作，概率密度函數(shù)為：它的數(shù)學期望為，方差為。指數(shù)分布是唯一具有無記憶性的連續(xù)型隨機變量，即有，在排隊論、可靠性分析中有廣泛應用。（=4\*romaniv）Gamma分布Gamma分布是雙參數(shù)的非對稱分布，記作，期望是。時蛻化為指數(shù)分布。個相互獨立、同分布（參數(shù)）的指數(shù)分布之和是Gamma分布（。Gamma分布可用于服務時間，零件壽命等。Gamma分布又稱愛爾朗分布。（=5\*romanv）Weibull分布Weibull分布是雙參數(shù)的非對稱分布，記作。時蛻化為指數(shù)分布。作為設備、零件的壽命分布在可靠性分析中有著非常廣泛的應用。（=6\*romanvi）Beta分布Beta分布是區(qū)間內(nèi)的雙參數(shù)、非均勻分布，記作。2.2.2常用的離散型概率分布（=1\*romani）離散均勻分布（=2\*romanii）Bernoulli分布（兩點分布）Bernoulli分布是處取值的概率分別是和的兩點分布，記作。用于基本的離散模型。（=3\*romaniii）泊松（Poisson）分布泊松分布與指數(shù)分布有密切的關系。當顧客平均到達率為常數(shù)的到達間隔服從指數(shù)分布時，單位時間內(nèi)到達的顧客數(shù)服從泊松分布，即單位時間內(nèi)到達位顧客的概率為記作。反過來也是這樣。泊松分布在排隊服務、產(chǎn)品檢驗、生物與醫(yī)學統(tǒng)計、天文、物理等領域都有廣泛應用。（=4\*romaniv）二項分布在獨立進行的每次試驗中，某事件發(fā)生的概率為，則次試驗中該事件發(fā)生的次數(shù)服從二項分布，即發(fā)生次的概率為.記作。二項分布是個獨立的Bernoulli分布之和。它在產(chǎn)品檢驗、保險、生物和醫(yī)學統(tǒng)計等領域有著廣泛的應用。當很大時，近似于正態(tài)分布；當很大、很小，且約為常數(shù)時，近似于?！?標準的模型標準的模型是指適合下列條件的排隊系統(tǒng)：（=1\*romani）輸入過程—顧客源是無限的，顧客單個到來，相互獨立，一定時間的到達數(shù)服從泊松分布，到達過程已是平穩(wěn)的。（=2\*romanii）排隊規(guī)則—單隊，且對隊長沒有限制，先到先服務。（=3\*romaniii）服務機構—單服務臺，各顧客的服務時間是相互獨立的，服從相同的指數(shù)分布。此外，還假定到達時間間隔和服務時間是相互獨立的。在分析標準的模型時，首先要求出系統(tǒng)在任意時刻的狀態(tài)為（系統(tǒng)中有個顧客）的概率，它決定了系統(tǒng)運行的特征。因已知到達規(guī)律服從參數(shù)為的泊松過程，服務時間服從參數(shù)為的指數(shù)分布，所以在時間區(qū)間內(nèi)有：（=1\*romani）有一個顧客到達的概率為；沒有顧客到達的概率就是。（=2\*romanii）當有顧客在接受服務時，1個顧客被服務完了（離去）的概率是，沒有離去的概率就是。（=3\*romaniii）多于一個顧客的到達或離去的概率是，是可以忽略的。設（否則隊列將排至無限遠），我們可以推出在系統(tǒng)穩(wěn)態(tài)時以上式為基礎可以算出系統(tǒng)的運行指標：（=1\*romani）在系統(tǒng)中的平均顧客數(shù)（隊長期望值）（=2\*romanii）在隊列中等待的平均顧客數(shù)（排隊長期望值）（=3\*romaniii）在系統(tǒng)中顧客逗留時間的期望值（=4\*romaniv）在隊列中顧客等待時間的期望值§4產(chǎn)生給定分布的隨機數(shù)的方法Matlab可以產(chǎn)生常用分布的隨機數(shù)。下面我們介紹按照給定的概率分布產(chǎn)生隨機數(shù)的一般方法，這些方法都以分布的隨機變量為基礎。(=1\*romani)反變換法定理設是一個具有連續(xù)分布函數(shù)的隨機變量，則在[0，1]上有均勻分布。設概率分布函數(shù)是嚴格單調(diào)增的，的反函數(shù)記作。先產(chǎn)生，再取即為所求，稱為反變換法。指數(shù)分布能夠方便地用反變換法產(chǎn)生。由的分布函數(shù)，可得思考有的書上用代替上式，對嗎，為什么？（=2\*romanii）卷積法如果隨機變量是個獨立、同分布的另一隨機變量之和，而又容易產(chǎn)生時，先產(chǎn)生個獨立的，再令即可。因為的分布函數(shù)是分布函數(shù)的卷積，故稱為卷積法。二項分布可以用卷積法產(chǎn)生。因為是個獨立的之和，而很容易由按以下方法得到：若，令；否則令。(=3\*romaniii)取舍法若隨機變量在有限區(qū)間內(nèi)變化，但概率密度具有任意形式（甚至沒有解析表達式），無法用前面的方法產(chǎn)生時，可用取舍法。一種比較簡單的取舍法的步驟是：1o產(chǎn)生和；2o記，若，則?。环駝t，舍去，返回1o?！?排隊模型的計算機模擬5.1確定隨機變量概率分布的常用方法在模擬一個帶有隨機因素的實際系統(tǒng)時，究竟用什么樣的概率分布描述問題中的隨機變量，是我們總是要碰到的一個問題，下面簡單介紹確定分布的常用方法：1o根據(jù)一般知識和經(jīng)驗，可以假定其概率分布的形式，如顧客到達間隔服從指數(shù)分布；產(chǎn)品需求量服從正態(tài)分布；訂票后但未能按時前往機場登機的人數(shù)服從二項分布。然后由實際數(shù)據(jù)估計分布的參數(shù)等，參數(shù)估計可用極大似然估計、矩估計等方法。2o直接由大量的實際數(shù)據(jù)作直方圖，得到經(jīng)驗分布，再通過假設檢驗，擬合分布函數(shù)，可用檢驗等方法。3o既缺少先驗知識，又缺少數(shù)據(jù)時，對區(qū)間內(nèi)變化的隨機變量，可選用Beta分布（包括均勻分布）。先根據(jù)經(jīng)驗確定隨機變量的均值和頻率最高時的數(shù)值（即密度函數(shù)的最大值），則Beta分布中的參數(shù)可由以下關系求出：，.5.2計算機模擬當排隊系統(tǒng)的到達間隔時間和服務時間的概率分布很復雜時，或不能用公式給出時，那么就不能用解析法求解。這就需用隨機模擬法求解，現(xiàn)舉例說明。例1設某倉庫前有一卸貨場，貨車一般是夜間到達，白天卸貨，每天只能卸貨2車，若一天內(nèi)到達數(shù)超過2車，那么就推遲到次日卸貨。根據(jù)下表所示的數(shù)據(jù)，貨車到達數(shù)的概率分布（相對頻率）平均為1.5車/天，求每天推遲卸貨的平均車數(shù)。到達車數(shù)0123456概率0.230.300.300.10.050.020.00解這是單服務臺的排隊系統(tǒng)，可驗證到達車數(shù)不服從泊松分布，服務時間也不服從指數(shù)分布（這是定長服務時間）。隨機模擬法首先要求事件能按歷史的概率分布規(guī)律出現(xiàn)。模擬時產(chǎn)生的隨機數(shù)與事件的對應關系如下：到達車數(shù)概率累積概率對應的隨機數(shù)012345230.303010050.0223538393980000.230.230.530.530.830.830.930.930.980.981.001.00我們用a1表示產(chǎn)生的隨機數(shù)，a2表示到達的車數(shù)，a3表示需要卸貨車數(shù)，a4表示卸貨車數(shù)，a5表示推遲卸貨車數(shù)。編寫程序如下：clearrand('state',sum(100*clock));n=50000;m=2a1=rand(n,1);a2=a1;%a2初始化a2(find(a1<0.23))=0;a2(find(0.23<=a1&a1<0.53))=1;a2(find(0.53<=a1&a1<0.83))=2;a2(find(0.83<=a1&a1<0.93),1)=3;a2(find(0.93<=a1&a1<0.98),1)=4;a2(find(a1>=0.98))=5;a3=zeros(n,1);a4=zeros(n,1);a5=zeros(n,1);a3(1)=a2(1);ifa3(1)<=ma4(1)=a3(1);a5(1)=0;elsea4(1)=m;a5(1)=a2(1)-m;endfori=2:na3(i)=a2(i)+a5(i-1);ifa3(i)<=ma4(i)=a3(i);a5(i)=0;elsea4(i)=m;a5(i)=a3(i)-m;endenda=[a1,a2,a3,a4,a5];sum(a)/n例2銀行計劃安置自動取款機，已知型機的價格是型機的2倍，而型機的性能—平均服務率也是型機的2倍，問應該購置1臺型機還是2臺型機。為了通過模擬回答這類問題，作如下具體假設，顧客平均每分鐘到達1位，型機的平均服務時間為0.9，型機為1.8分鐘，顧客到達間隔和服務時間都服從指數(shù)分布，2臺型機采取模型（排一隊），用前100名顧客（第1位顧客到達時取款機前為空）的平均等待時間為指標，對型機和型機分別作1000次模擬，進行比較。理論上已經(jīng)得到，型機和型機前100名顧客的平均等待時間分別為，，即型機優(yōu)。對于模型，記第位顧客的到達時刻為，離開時刻為，等待時間為，它們很容易根據(jù)已有的到達間隔和服務時間按照以下的遞推關系得到（，設已知）：，，在模擬型機時，我們用cspan表示到達間隔時間，sspan表示服務時間，ctime表示到達時間，gtime表示離開時間，wtime表示等待時間。我們總共模擬了次，每次個顧客。程序如下：ticrand('state',sum(100*clock));n=100;m=1000;mu1=1;mu2=0.9;forj=1:mcspan=exprnd(mu1,1,n);sspan=exprnd(mu2,1,n);ctime(1)=cspan(1);gtime(1)=ctime(1)+sspan(1);wtime(1)=0;fori=2:nctime(i)=ctime(i-1)+cspan(i);gtime(i)=max(ctime(i),gtime(i-1))+sspan(i);wtime(i)=max(0,gtime(i-1)-ctime(i));endresult1(j)=sum(wtime)/n;endresult_1=sum(result1)/mtoc類似地，模擬型機的程序如下：ticrand('state',sum(100*clock));n=100;m=1000;mu1=1;mu2=1.8;forj=1:mcspan=exprnd(mu1,1,n);sspan=exprnd(mu2,1,n);ctime(1)=cspan(1);ctime(2)=ctime(1)+cspan(2);gtime(1:2)=ctime(1:2)+sspan(1:2);wtime(1:2)=0;flag=gtime(1:2);fori=3:nctime(i)=ctime(i-1)+cspan(i);gtime(i)=max(ctime(i),min(flag))+sspan(i);wtime(i)=max(0,min(flag)-ctime(i));flag=[max(flag),gtime(i)];endresult2(j)=sum(wtime)/n;endresult_2=sum(result2)/mtoc讀者可以用下面的程序與上面的程序比較了解編程的效率問題。ticclearrand('state',sum(100*clock));n=100;m=1000;mu1=1;mu2=0.9;forj=1:mctime(1)=exprnd(mu1);gtime(1)=ctime(1)+exprnd(mu2);wtime(1)=0;fori=2:nctime(i)=ctime(i-1)+exprnd(mu1);gtime(i)=max(ctime(i),gtime(i-1))+exprnd(mu2);wtime(i)=max(0,gtime(i-1)-ctime(i));endresult(j)=sum(wtime)/n;endresult=sum(result)/mtoc習題六1.一個車間內(nèi)有10臺相同的機器，每臺機器運行時每小時能創(chuàng)造4元的利潤，且平均每小時損壞一次。而一個修理工修復一臺機器平均需4小時。以上時間均服從指數(shù)分布。設一名修理工一小時工資為6元，試求：（=1\*romani）該車間應設多少名修理工，使總費用為最小；（=2\*romanii）若要求不能運轉的機器的期望數(shù)小于4臺，則應設多少名修理工；（=3\*romaniii）若要求損壞機器等待修理的時間少于4小時，又應設多少名修理工。到達某鐵路售票處顧客分兩類：一類買南方線路票，到達率為/小時，另一類買北方線路票，到達率為/小時，以上均服從泊松分布。該售票處設兩個窗口，各窗口服務一名顧客時間均服從參數(shù)的指數(shù)分布。試比較下列情況時顧客分別等待時間：（=1\*romani）兩個窗口分別售南方票和北方票；（=2\*romanii）每個窗口兩種票均出售。（分別比較時的情形）第七章對策論§1引言社會及經(jīng)濟的發(fā)展帶來了人與人之間或團體之間的競爭及矛盾，應用科學的方法來解決這樣的問題開始于17世紀的科學家，如C.，Huygens和W.，Leibnitz等?，F(xiàn)代對策論起源于1944年J.，VonNeumann和O.，Morgenstern的著作《TheoryofGamesandEconomicBehavior》。對策論亦稱競賽論或博弈論。是研究具有斗爭或競爭性質(zhì)現(xiàn)象的數(shù)學理論和方法。一般認為，它既是現(xiàn)代數(shù)學的一個新分支，也是運籌學中的一個重要學科。對策論發(fā)展的歷史并不長，但由于它所研究的現(xiàn)象與人們的政治、經(jīng)濟、軍事活動乃至一般的日常生活等有著密切的聯(lián)系，并且處理問題的方法又有明顯特色。所以日益引起廣泛的注意。在日常生活中，經(jīng)?？吹揭恍┚哂邢嗷ブg斗爭或競爭性質(zhì)的行為。具有競爭或?qū)剐再|(zhì)的行為稱為對策行為。在這類行為中。參加斗爭或競爭的各方各自具有不同的目標和利益。為了達到各自的目標和利益，各方必須考慮對手的各種可能的行動方案，并力圖選取對自己最為有利或最為合理的方案。對策論就是研究對策行為中斗爭各方是否存在著最合理的行動方案，以及如何找到這個合理的行動方案的數(shù)學理論和方法?！?對策問題對策問題的特征是參與者為利益相互沖突的各方，其結局不取決于其中任意一方的努力而是各方所采取的策略的綜合結果。先考察一個實際例子。例1警察同時逮捕了兩人并分開關押，逮捕的原因是他們持有大量偽幣，警方懷疑他們偽造錢幣，但沒有找到充分證據(jù)，希望他們能自己供認，這兩個人都知道：如果他們雙方都不供認，將被以持有大量偽幣罪被各判刑18個月；如果雙方都供認偽造了錢幣，將各被判刑3年；如果一方供認另一方不供認，則供認方將被從寬處理而免刑，但另一方面將被判刑7年。將嫌疑犯、被判刑的幾種可能情況列表如下：嫌疑犯供認不供認嫌疑犯供認（3，3）（0，7）不供認（7，0）（1.5，1.5）表中每對數(shù)字表示嫌疑犯被判刑的年數(shù)。如果兩名疑犯均擔心對方供認并希望受到最輕的懲罰，最保險的辦法自然是承認制造了偽幣。從這一簡單實例中可以看出對策現(xiàn)象中包含有的幾個基本要素。2.1對策的基本要素（=1\*romani）局中人在一個對策行為（或一局對策）中，有權決定自己行動方案的對策參加者，稱為局中人。通常用表示局中人的集合．如果有個局中人，則。一般要求一個對策中至少要有兩個局中人。在例1中，局中人是兩名疑犯。（=2\*romanii）策略集一局對策中，可供局中人選擇的一個實際可行的完整的行動方案稱為一個策略。參加對策的每一局中人，，都有自己的策略集。一般，每一局中人的策略集中至少應包括兩個策略。（=3\*romaniii）贏得函數(shù)（支付函數(shù)）在一局對策中，各局中人所選定的策略形成的策略組稱為一個局勢，即若是第個局中人的一個策略，則個局中人的策略組就是一個局勢。全體局勢的集合S可用各局中人策略集的笛卡爾積表示，即當局勢出現(xiàn)后，對策的結果也就確定了。也就是說，對任一局勢，，局中人可以得到一個贏得。顯然，是局勢的函數(shù)，稱之為第個局中人的贏得函數(shù)。這樣，就得到一個向量贏得函數(shù)。本節(jié)我們只討論有兩名局中人的對策問題，其結果可以推廣到一般的對策模型中去。2.2零和對策（矩陣對策）零和對策是一類特殊的對策問題。在這類對策中，只有兩名局中人，每個局中人都只有有限個策略可供選擇。在任一純局勢下，兩個局中人的贏得之和總是等于零，即雙方的利益是激烈對抗的。設局中人Ⅰ、Ⅱ的策略集分別為，當局中人Ⅰ選定策略和局中人Ⅱ選定策略后，就形成了一個局勢，可見這樣的局勢共有個。對任一局勢，記局中人Ⅰ的贏得值為，并稱為局中人Ⅰ的贏得矩陣（或為局中人Ⅱ的支付矩陣）。由于假定對策為零和的，故局中人Ⅱ的贏得矩陣就是。當局中人Ⅰ、Ⅱ和策略集、及局中人Ⅰ的贏得矩陣確定后，一個零和對策就給定了，零和對策又可稱為矩陣對策并可簡記成。例2設有一矩陣對策，其中，，從中可以看出，若局中人Ⅰ希望獲得最大贏利30，需采取策略，但此時若局中人Ⅱ采取策略，局中人Ⅰ非但得不到30，反而會失去22。為了穩(wěn)妥，雙方都應考慮到對方有使自己損失最大的動機，在最壞的可能中爭取最好的結果，局中人Ⅰ采取策略時，最壞的贏得結果分別為其中最好的可能為。如果局中人Ⅰ采取策略，無論局中人Ⅱ采取什么策略，局中人Ⅰ的贏得均不會少于2。局中人Ⅱ采取各方案的最大損失為，，，和。當局中人Ⅱ采取策略時，其損失不會超過2。注意到在贏得矩陣中，2既是所在行中的最小元素又是所在列中的最大元素。此時，只要對方不改變策略，任一局中人都不可能通過變換策略來增大贏得或減少損失，稱這樣的局勢為對策的一個穩(wěn)定點或穩(wěn)定解。定義1設為一個定義在及上的實值函數(shù)，如果存在，，使得對一切和，有則稱為函數(shù)的一個鞍點。定義2設為矩陣對策，其中，，。若等式（1）成立，記，則稱為對策的值，稱使（1）式成立的純局勢為對策的鞍點或穩(wěn)定解，贏得矩陣中與相對應的元素稱為贏得矩陣的鞍點，與分別稱為局中人Ⅰ與Ⅱ的最優(yōu)純策略。給定一個對策，如何判斷它是否具有鞍點呢？為了回答這一問題，先引入下面的極大極小原理。定理1設，記，，則必有。證明，易見為Ⅰ的最小贏得，為Ⅱ的最小贏得，由于是零和對策，故必成立。定理2零和對策具有穩(wěn)定解的充要條件為。證明：（充分性）由和的定義可知，存在一行（例如行）為行中的最小元素且存在一列（例如列）為列中的最大元素。故有且又因，所以，從而得出，為贏得矩陣的鞍點，為的穩(wěn)定解。（必要性）若具有穩(wěn)定解，則為贏得矩陣的鞍點。故有從而可得，但根據(jù)定理1，必成立，故必有。上述定理給出了對策問題有穩(wěn)定解（簡稱為解）的充要條件。當對策問題有解時，其解可以不唯一，當解不唯一時，解之間的關系具有下面兩條性質(zhì)：性質(zhì)1無差別性。即若與是對策的兩個解，則必有性質(zhì)2可交換性。即若和是對策的兩個解，則和也是解?！?零和對策的混合策略具有穩(wěn)定解的零和問題是一類特別簡單的對策問題，它所對應的贏得矩陣存在鞍點，任一局中人都不可能通過自己單方面的努力來改進結果。然而，在實際遇到的零和對策中更典型的是的情況。由于贏得矩陣中不存在鞍點，此時在只使用純策略的范圍內(nèi)，對策問題無解。下面我們引進零和對策的混合策略。設局中人Ⅰ用概率選用策略，局中人Ⅱ用概率選用策略，，記，，則局中人Ⅰ的期望贏得為。記：策略：策略概率概率分別稱與為局中人Ⅰ和Ⅱ的混合策略。定義4若存在維概率向量和維概率向量，使得對一切維概率向量和維概率向量有則稱為混合策略對策問題的鞍點。定理3任意混合策略對策問題必存在鞍點，即必存在概率向量和，使得：。使用純策略的對策問題（具有穩(wěn)定解的對策問題）可以看成使用混合策略的對策問題的特殊情況，相當于以概率1選取其中某一策略，以概率0選取其余策略。例3為作戰(zhàn)雙方，方擬派兩架轟炸機Ⅰ和Ⅱ去轟炸方的指揮部，轟炸機Ⅰ在前面飛行，Ⅱ隨后。兩架轟炸機中只有一架帶有炸彈，而另一架僅為護航。轟炸機飛至方上空，受到方戰(zhàn)斗機的阻擊。若戰(zhàn)斗機阻擊后面的轟炸機Ⅱ，它僅受Ⅱ的射擊，被擊中的概率為0.3(Ⅰ來不及返回攻擊它)。若戰(zhàn)斗機阻擊Ⅰ，它將同時受到兩架轟炸機的射擊，被擊中的概率為0.7。一旦戰(zhàn)斗機未被擊落，它將以0.6的概率擊毀其選中的轟炸機。請為雙方各選擇一個最優(yōu)策略，即：對于方應選擇哪一架轟炸機裝載炸彈？對于方戰(zhàn)斗機應阻擊哪一架轟炸機？解雙方可選擇的策略集分別是，：轟炸機Ⅰ裝炸彈，Ⅱ護航：轟炸機Ⅱ裝炸彈，Ⅰ護航，：阻擊轟炸機Ⅰ：阻擊轟炸機Ⅱ贏得矩陣，為方采取策略而方采取策略時，轟炸機轟炸方指揮部的概率，由題意可計算出：，即易求得，。由于，矩陣不存在鞍點，應當求最佳混合策略?，F(xiàn)設以概率取策略、概率取策略；以概率取策略、概率取策略。先從方來考慮問題。采用時，方轟炸機攻擊指揮部的概率期望值為，而采用時，方轟炸機攻擊指揮部的概率的期望值為。若，不妨設，則方必采用以減少指揮部被轟炸的概率。故對方選取的最佳概率和，必滿足：即由此解得，。同樣，可從方考慮問題，得即并解得，。方指揮部被轟炸的概率的期望值。記零和對策的解集為，下面三個定理是關于對策解集性質(zhì)的主要結果：定理4設有兩個零和對策，其中，，為任一常數(shù)。則（=1\*romani）（=2\*romanii）定理5設有兩個零和對策，其中為任一常數(shù)。則（=1\*romani）（=2\*romanii）定理6設為一零和對策，且為斜對稱矩陣。則（=1\*romani）（=2\*romanii）其中和為局中人Ⅰ和Ⅱ的最優(yōu)策略集。§4零和對策的線性規(guī)劃解法當且時，通常采用線性規(guī)劃方法求解零和對策問題。局中人Ⅰ選擇混合策略的目的是使得其中為只有第個分量為1而其余分量均為零的單位向量，。記，由于，在，時達到最小值，故應為線性規(guī)劃問題（2）的解。同理，應為線性規(guī)劃（3）的解。由線性規(guī)劃知識，（2）與（3）互為對偶線性規(guī)劃，它們具有相同的最優(yōu)目標函數(shù)值。不妨設，作變換，則線性規(guī)劃問題（2）化為：同理，作變換，則線性規(guī)劃問題（3）化為：例4在一場敵對的軍事行動中，甲方擁有三種進攻性武器，可分別用于摧毀乙方工事；而乙方有三種防御性武器來對付甲方。據(jù)平時演習得到的數(shù)據(jù)，各種武器間對抗時，相互取勝的可能如下：對2：1；對3：1；對1：2；對3：7；對3：2；對1：3；對3：1；對1：4；對2：1解先分別列出甲、乙雙方的贏得的可能性矩陣，將甲方矩陣減去乙方矩陣的對應元素，得零和對策時甲方的贏得矩陣如下：編寫程序如下：cleara=[1/3,1/2,-1/3;-2/5,1/5,-1/2;1/2,-3/5,1/3];b=10;a=a+b*ones(3);%把贏得矩陣的每個元素變成大于0的數(shù)[x0,u]=linprog(ones(3,1),-a',-ones(3,1),...[],[],zeros(3,1));x=x0/u,v1=1/u-b[y0,v]=linprog(-ones(3,1),a,ones(3,1),[],[],zeros(3,1));y=y0/abs(v),v2=1/v+b解得，，，故乙方有利。習題七1.有甲、乙兩支游泳隊舉行包括三個項目的對抗賽。這兩支游泳隊各有一名健將級運動員（甲隊為李，乙隊為王），在三個項目中成績都很突出，但規(guī)則準許他們每人只能參加兩項比賽，每隊的其他兩名運動員可參加全部三項比賽。已知各運動員平時成績（秒）見下表。甲隊乙隊李王100米蝶泳100米仰泳100米蛙泳59.767.274.163.268.475.557.163.270.358.661.572.661.464.773.464.866.576.9假定各運動員在比賽中都發(fā)揮正常水平，又比賽第一名得5分，第二名得3分，第三名得1分，問教練員應決定讓自己隊健將參加哪兩項比賽，使本隊得分最多？（各隊參加比賽名單互相保密，定下來后不準變動）2.有三張紙牌，點數(shù)分別為1，2，3，顯然按大小順序為。先由任抽一張，看過后反放在桌上，并任喊大（）或?。ǎ?。然后由從剩下紙牌中任抽一張，看過后，有兩種選擇：第一，棄權，付給1元；第二，翻的牌，當喊時，得點數(shù)小的牌者付給對方3元，當喊時，得點數(shù)大的牌者付給對方2元。要求：（=1\*romani）說明各有多少個純策略；（=2\*romanii）根據(jù)優(yōu)超原則淘汰具有劣勢的策略，并列出對的贏得矩陣；（=3\*romaniii）求解雙方各自的最優(yōu)策略和對策值。

咖啡店創(chuàng)業(yè)計劃書第一部分：背景在中國，人們越來越愛喝咖啡。隨之而來的咖啡文化充滿生活的每個時刻。無論在家里、還是在辦公室或各種社交場合，人們都在品著咖啡。咖啡逐漸與時尚、現(xiàn)代生活聯(lián)系在一齊。遍布各地的咖啡屋成為人們交談、聽音樂、休息的好地方，咖啡豐富著我們的生活，也縮短了你我之間的距離，咖啡逐漸發(fā)展為一種文化。隨著咖啡這一有著悠久歷史飲品的廣為人知，咖啡正在被越來越多的中國人所理解。第二部分：項目介紹第三部分：創(chuàng)業(yè)優(yōu)勢目前大學校園的這片市場還是空白，競爭壓力小。而且前期投資也不是很高，此刻國家鼓勵大學生畢業(yè)后自主創(chuàng)業(yè)，有一系列的優(yōu)惠政策以及貸款支持。再者大學生往往對未來充滿期望，他們有著年輕的血液、蓬勃的朝氣，以及初生牛犢不怕虎的精神，而這些都是一個創(chuàng)業(yè)者就應具備的素質(zhì)。大學生在學校里學到了很多理論性的東西，有著較高層次的技術優(yōu)勢，現(xiàn)代大學生有創(chuàng)新精神，有對傳統(tǒng)觀念和傳統(tǒng)行業(yè)挑戰(zhàn)的信心和欲望，而這種創(chuàng)新精神也往往造就了大學生創(chuàng)業(yè)的動力源泉，成為成功創(chuàng)業(yè)的精神基礎。大學生創(chuàng)業(yè)的最大好處在于能提高自己的潛力、增長經(jīng)驗，以及學以致用;最大的誘人之處是透過成功創(chuàng)業(yè)，能夠?qū)崿F(xiàn)自己的理想，證明自己的價值。第四部分：預算1、咖啡店店面費用咖啡店店面是租賃建筑物。與建筑物業(yè)主經(jīng)過協(xié)商，以合同形式達成房屋租賃協(xié)議。協(xié)議資料包括房屋地址、面積、結構、使用年限、租賃費用、支付費用方法等。租賃的優(yōu)點是投資少、回收期限短。預算10-15平米店面，啟動費用大約在9-12萬元。2、裝修設計費用咖啡店的滿座率、桌面的周轉率以及氣候、節(jié)日等因素對收益影響較大?？Х瑞^的消費卻相對較高，主要針對的也是學生人群，咖啡店布局、格調(diào)及采用何種材料和咖啡店效果圖、平面圖、施工圖的設計費用，大約6000元左右3、裝修、裝飾費用具體費用包括以下幾種。(1)外墻裝飾費用。包括招牌、墻面、裝飾費用。(2)店內(nèi)裝修費用。包括天花板、油漆、裝飾費用，木工、等費用。(3)其他裝修材料的費用。玻璃、地板、燈具、人工費用也應計算在內(nèi)。整體預算按標準裝修費用為360元/平米，裝修費用共360*15=5400元。4、設備設施購買費用具體設備主要有以下種類。(1)沙發(fā)、桌、椅、貨架。共計2250元(2)音響系統(tǒng)。共計450(3)吧臺所用的烹飪設備、儲存設備、洗滌設備、加工保溫設備。共計600(4)產(chǎn)品制造使用所需的吧臺、咖啡杯、沖茶器、各種小碟等。共計300凈水機，采用美的品牌，這種凈水器每一天能生產(chǎn)12l純凈水，每一天銷售咖啡及其他飲料100至200杯，價格大約在人民幣1200元上下?？Х葯C，咖啡機選取的是電控半自動咖啡機，咖啡機的報價此刻就應在人民幣350元左右，加上另外的附件也不會超過1200元。磨豆機，價格在330―480元之間。冰砂機，價格大約是400元一臺，有點要說明的是，最好是買兩臺，不然夏天也許會不夠用。制冰機，從制冰量上來說，一般是要留有富余?？钪票鶛C每一天的制冰量是12kg。價格稍高550元，質(zhì)量較好，所以能夠用很多年，這么算來也是比較合算的。5、首次備貨費用包括購買常用物品及低值易耗品，吧臺用各種咖啡豆、奶、茶、水果、冰淇淋等的費用。大約1000元6、開業(yè)費用開業(yè)費用主要包括以下幾種。(1)營業(yè)執(zhí)照辦理費、登記費、保險費;預計3000元(2)營銷廣告費用;預計450元7、周轉金開業(yè)初期，咖啡店要準備必須量的流動資金，主要用于咖啡店開業(yè)初期的正常運營。預計2000元共計： 120000+6000+5400+2250+450+600+300+1200+1200+480+400+550+1000+3000+450+2000=145280元第五部分：發(fā)展計劃1、營業(yè)額計劃那里的營業(yè)額是指咖啡店日常營業(yè)收入的多少。在擬定營業(yè)額目標時，必須要依據(jù)目前市場的狀況，再思考到咖啡店的經(jīng)營方向以及當前的物價情形，予以綜合衡量。按照目前流動人口以及人們對咖啡的喜好預計每一天的營業(yè)額為400-800，根據(jù)淡旺季的不同可能上下浮動2、采購計劃依據(jù)擬訂的商品計劃，實際展開采購作業(yè)時，為使采購資金得到有效運用以及商品構成達成平衡，務必針對設定的商品資料排定采購計劃。透過