本文在研究體檢排隊(duì)問(wèn)

1、8/8摘要本文在研究體檢排隊(duì)問(wèn)題的同時(shí)，采用了M/M/1/S排隊(duì)論和抽象的迪克斯特拉（Dijkstra）算法，分別對(duì)科室抽血、內(nèi)科、外科等等進(jìn)行了有效地估計(jì)。通過(guò)顧客的到達(dá)時(shí)間、離開(kāi)時(shí)間、停留時(shí)間、等待時(shí)間反映了在研究體檢所用時(shí)間最短的相對(duì)優(yōu)化的時(shí)間模型 問(wèn)題1：為某個(gè)新來(lái)的客人安排他的體檢順序，使其完成需要的全部檢查的時(shí)間盡量少（在各個(gè)體檢項(xiàng)目處都可能有人排隊(duì)等待），通過(guò)對(duì)數(shù)據(jù)的處理，對(duì)于抽血A、內(nèi)科B、外科B、B超D、五官科E、胸透F、身高G和體重H八個(gè)科室排出耗費(fèi)時(shí)間相對(duì)最短的路徑的算法。 問(wèn)題2：通過(guò)表格一的數(shù)據(jù)和上述的算法思想，在有效的假設(shè)中，用MATLAB軟件得出了八個(gè)科室的有效地

2、相對(duì)最佳路徑AFHGBCED。推導(dǎo)所消耗的時(shí)間最短。問(wèn)題3： 關(guān)鍵詞：M/M/1/S排隊(duì)論 （Dijkstra）算法 1. 問(wèn)題重述醫(yī)院就醫(yī)排隊(duì)是大家都非常熟悉的現(xiàn)象，我們現(xiàn)通過(guò)考慮某醫(yī)院眼科病床的合理安排的數(shù)學(xué)建模問(wèn)題，提出安排策略，盡量減少病人排隊(duì)等待時(shí)間。 該醫(yī)院門診每天開(kāi)放，每天來(lái)的體檢人數(shù)都是同分布的，體檢項(xiàng)目包括抽血、內(nèi)科、外科、B超、五官科、胸透、身高和體重等八個(gè)項(xiàng)目 當(dāng)前醫(yī)院沒(méi)有完備的系統(tǒng)來(lái)確定來(lái)的人群的徑向流量，提高設(shè)備利用率、降低客人的等待時(shí)間，醫(yī)院要求完備的方案來(lái)對(duì)體檢的人進(jìn)行有效地指導(dǎo)就醫(yī)。問(wèn)題1：為某個(gè)新來(lái)的客人安排他的體檢順序，使其完成需要的全部檢查的時(shí)間盡量少（在

3、各個(gè)體檢項(xiàng)目處都可能有人排隊(duì)等待），求出時(shí)間最短的路徑問(wèn)題2：通過(guò)數(shù)據(jù)來(lái)驗(yàn)證問(wèn)題1的模型的優(yōu)劣。問(wèn)題3： 2.1 模型假設(shè)1)各個(gè)體檢項(xiàng)目之間相互獨(dú)立，互不影響。2)病人排隊(duì)體檢和體檢完畢到下一個(gè)科室之間沒(méi)有時(shí)間延遲。3)入院體檢的顧客單個(gè)到達(dá)，相繼到達(dá)時(shí)間間隔服從參數(shù)為的負(fù)指數(shù)分布。4)各個(gè)科室可以抽象一個(gè)點(diǎn)。5）每個(gè)服務(wù)臺(tái)的服務(wù)時(shí)間相互獨(dú)立，且服從參數(shù)為的負(fù)指數(shù)分布。6）在團(tuán)體病人來(lái)體檢時(shí)，假設(shè)每個(gè)科室的服務(wù)設(shè)施是空缺的。 2.2 符號(hào)說(shuō)明 1：抽血A1、內(nèi)科B1、外科C3、B超D4、五官科E5、胸透F6、身高G7、體重H82：（i）和lamuda(i) 表示單位時(shí)間平均到達(dá)的顧客數(shù), 稱

4、為平均到達(dá)率3：(i)和mu(i) 位時(shí)間能被服務(wù)完成的顧客數(shù)，稱為平均服務(wù)率4：t(i)：在ABCDEFGH各個(gè)科室檢查的時(shí)間5：(i):表示在ABCDEFGH各個(gè)科室的受檢比率3. 問(wèn)題一3.1 問(wèn)題分析 3.1.1 背景分析“三長(zhǎng)一短”（掛號(hào)時(shí)間長(zhǎng)、候診時(shí)間長(zhǎng)、交費(fèi)時(shí)間長(zhǎng)、看病時(shí)間短)一直是中國(guó)各大醫(yī)院的頑疾，也成為影響病人滿意度的主要因素。現(xiàn)有某醫(yī)院住院部采取了一些方案安排病人住院，卻使等待病人越來(lái)越多。為了使該醫(yī)院的體檢病人在最短的時(shí)間內(nèi)完成體檢項(xiàng)目，設(shè)計(jì)一個(gè)可以有效的解決的上述問(wèn)題的算法。3.1.2 評(píng)價(jià)分析 通常醫(yī)院的采取的各個(gè)方案按照大眾的顧客考慮的，在排隊(duì)體檢的過(guò)程中由于在各

5、個(gè)科室體檢時(shí)間不相等，同時(shí)在各個(gè)科室個(gè)的等待人數(shù)比率不同。 給出評(píng)價(jià)標(biāo)準(zhǔn)是體檢的時(shí)間最短 表格 SEQ 表格 * ARABIC 1抽血內(nèi)科外科B超五官科胸透身高體重時(shí)間222122111檢率0.950.20.20.70.21.00.50.73.1.3模型的闡述：泊松流與指數(shù)分布 設(shè)N(t)表示在時(shí)間區(qū)間0,t)內(nèi)到達(dá)的顧客數(shù)（t 0），令P( t1, t2) 1表示在時(shí)間區(qū)間 內(nèi)有n( 0)個(gè)顧客到達(dá)的概率.當(dāng)合于下列三個(gè)條件時(shí)，我們說(shuō)顧客的到達(dá)形成泊松流。這三個(gè)條件是：1o 在不相重疊的時(shí)間區(qū)間內(nèi)顧客到達(dá)數(shù)是相互獨(dú)立的，我們稱這性質(zhì)為無(wú)后效性。2o 對(duì)充分小的t，在時(shí)間區(qū)間t,t + t)內(nèi)

6、有一個(gè)顧客到達(dá)的概率與t無(wú)關(guān)，而約與區(qū)間長(zhǎng)t成正比，即 其中o(t)，當(dāng)t 0時(shí)，是關(guān)于t的高階無(wú)窮小。 0是常數(shù)，它表示單位時(shí)間有一個(gè)顧客到達(dá)的概率，稱為概率強(qiáng)度。3o 對(duì)于充分小的t，在時(shí)間區(qū)間t,t + t)內(nèi)有兩個(gè)或兩個(gè)以上顧客到達(dá)的概率極小，以致可以忽略，即在上述條件下，我們研究顧客到達(dá)數(shù)n 的概率分布。由條件2o，我們總可以取時(shí)間由0算起，并簡(jiǎn)記由條件1o 和2o，有由條件2o 和3o 得 因而有在以上兩式中，取t趨于零的極限，當(dāng)假設(shè)所涉及的函數(shù)可導(dǎo)時(shí)，得到以下微分方程組取初值，容易解出 。再令 ，可以得到 及其它U (t) n 所滿足的微分方程組，即 由此容易解得對(duì)于泊松流, 表

7、示單位時(shí)間平均到達(dá)的顧客數(shù),所以1/就表示相繼顧客到達(dá)平均間隔時(shí)間，而這正和ET 的意義相符。表示單位時(shí)間能被服務(wù)完成的顧客數(shù)，稱為平均服務(wù)率，而1/表示一個(gè)顧客的平均服務(wù)時(shí)間。 根據(jù)表格一的數(shù)據(jù)和實(shí)際情況，給出每個(gè)科室的和的表格表格 SEQ 表格 * ARABIC 2 lamuda130mu120 lamuda230 mu224 lamuda330mu325 Lamuda4 5mu43 lamuda530mu521 Lamuda6 60mu642 Lamuda7 60mu730 Lamuda8 60mu845 根據(jù)表格2的數(shù)據(jù)，用MATLAB編程得出了抽血科室的到達(dá)時(shí)間和離開(kāi)時(shí)間的圖，和等待

8、時(shí)間與停留時(shí)間。 根據(jù)對(duì)抽血科室的時(shí)間和表格一的數(shù)據(jù)處理，通過(guò)上面的圖可以看出：當(dāng)人數(shù)呈數(shù)據(jù)流的泊松分布，與現(xiàn)實(shí)相符。 把每個(gè)科室抽象成一個(gè)點(diǎn)，時(shí)間與檢比的積根當(dāng)做權(quán)重。據(jù)迪克斯特拉（Dijkstra）算法，其基本思想是按距 從近到遠(yuǎn)為順序，依次求得A到G 的各頂點(diǎn)的最短路和距離，直至（或直至G 的所有頂點(diǎn)），算法結(jié)束。為避免重復(fù)并保留每一步的計(jì)算信息，采用了標(biāo)號(hào)算法把達(dá)到這個(gè)最小值的一個(gè)頂點(diǎn)記為，令 。|,停止。算法結(jié)束后，可以知道遍歷的最短路徑。通過(guò)數(shù)據(jù)的處理：網(wǎng)絡(luò)優(yōu)化研究的是網(wǎng)絡(luò)上的各種優(yōu)化模型與算法。為了在計(jì)算機(jī)上實(shí)現(xiàn)網(wǎng)絡(luò)優(yōu)化的算法，首先我們必須有一種方法（即數(shù)據(jù)結(jié)構(gòu)）在計(jì)算機(jī)上來(lái)描述

9、圖與網(wǎng)絡(luò)。一般來(lái)說(shuō)，算法的好壞與網(wǎng)絡(luò)的具體表示方法，以及中間結(jié)果的操作方案是有關(guān)系的。這里我們介紹計(jì)算機(jī)上用來(lái)描述圖與網(wǎng)絡(luò)的5 種常用表示方法：鄰接矩陣表示法、關(guān)聯(lián)矩陣表示法、弧表表示法、鄰接表表示法和星形表示法 ，在下面數(shù)據(jù)結(jié)構(gòu)的討論中，我們首先假設(shè)是一個(gè)簡(jiǎn)單有向圖。m，并假設(shè)V 中的頂點(diǎn)用自然數(shù)1,2,L,n表示或編號(hào)， A中的弧用自然數(shù)1,2,L,m表示或編號(hào)。對(duì)于有多重邊或無(wú)向網(wǎng)絡(luò)的情況，我們只是在討論完簡(jiǎn)單有向圖的表示方法之后，給出一些說(shuō)明。鄰接矩陣表示法是將圖以鄰接矩陣（adjacency matrix）的形式存儲(chǔ)在計(jì)算機(jī)中。的鄰接矩陣是如下定義： 也就是說(shuō)，如果兩節(jié)點(diǎn)之間有一條弧

10、，則鄰接矩陣中對(duì)應(yīng)的元素為 1；否則為0?？梢钥闯?，這種表示法非常簡(jiǎn)單、直接。但是，在鄰接矩陣的所有n2個(gè)元素中，只有m個(gè)為非零元。如果網(wǎng)絡(luò)比較稀疏，這種表示法浪費(fèi)大量的存儲(chǔ)空間，從而增加了在網(wǎng)絡(luò)中查找弧的時(shí)間。 對(duì)于上述的問(wèn)題，可以分別在A、B、C、D、E、F、G、H等各個(gè)體檢項(xiàng)目抽象成一個(gè)點(diǎn)，邊權(quán)近似等于時(shí)間和受檢比率的內(nèi)積?？梢缘玫洁徑泳仃? A BCDEFGHA01.51.57.71.50.51.41.2B00800.60.10.3C0800.60.10.3D087.47.97.7E00.60.10.3F00.50.3G00.2H0同樣，對(duì)于網(wǎng)絡(luò)中的權(quán)，也可以用類似鄰接矩陣的88 矩陣

11、表示。只是此時(shí)一條弧所對(duì)應(yīng)的元素不再是1，而是相應(yīng)的權(quán)而已。如果網(wǎng)絡(luò)中每條弧賦有多種權(quán)，則可以用多個(gè)矩陣表示這些權(quán)。用矩陣A88來(lái)存放各邊權(quán)的鄰接矩陣，行向量pb,index1，index2，d分別表示存放P 標(biāo)號(hào)信息、標(biāo)號(hào)頂點(diǎn)順序、標(biāo)號(hào)頂點(diǎn)索引、最短通路的值。其中分量index2(i)存放始點(diǎn)到第i各點(diǎn)最短路徑的第i個(gè)頂點(diǎn)的序號(hào) d(i):存放由始點(diǎn)到i個(gè)點(diǎn)的最短路徑。用MATLAB算出最短路徑AFHGBCED.附錄：程序代碼：clear clc %* %初始化顧客源 %* %總仿真時(shí)間 Total_time = 10; %隊(duì)列最大長(zhǎng)度 N = 10000000000; %到達(dá)率與服務(wù)率 l

12、ambda =30; mu =20; %平均到達(dá)時(shí)間與平均服務(wù)時(shí)間 arr_mean = 1/lambda; ser_mean = 1/mu; arr_num = round(Total_time*lambda*2); events = ; %按負(fù)指數(shù)分布產(chǎn)生各顧客達(dá)到時(shí)間間隔 events(1,:) = exprnd(arr_mean,1,arr_num); %各顧客的到達(dá)時(shí)刻等于時(shí)間間隔的累積和 events(1,:) = cumsum(events(1,:); %按負(fù)指數(shù)分布產(chǎn)生各顧客服務(wù)時(shí)間 events(2,:) = exprnd(ser_mean,1,arr_num); %計(jì)算仿真

13、顧客個(gè)數(shù)，即到達(dá)時(shí)刻在仿真時(shí)間內(nèi)的顧客數(shù) len_sim = sum(events(1,:)Total_time break; else number = sum(events(4,member) events(1,i); %如果系統(tǒng)已滿，則系統(tǒng)拒絕第 i個(gè)顧客，其標(biāo)志位置 0 if number = N+1 events(5,i) = 0; %如果系統(tǒng)為空，則第 i個(gè)顧客直接接受服務(wù) else if number = 0 %其等待時(shí)間為 0%PROGRAMLANGUAGEPROGRAMLANGUAGEevents(3,i) = 0; %其離開(kāi)時(shí)刻等于到達(dá)時(shí)刻與服務(wù)時(shí)間之和 events(4,

14、i) = events(1,i)+events(2,i); %其標(biāo)志位置 1 events(5,i) = 1; member = member,i; %如果系統(tǒng)有顧客正在接受服務(wù)，且系統(tǒng)等待隊(duì)列未滿，則 第 i個(gè)顧客進(jìn)入系統(tǒng) else len_mem = length(member); %其等待時(shí)間等于隊(duì)列中前一個(gè)顧客的離開(kāi)時(shí)刻減去其到 達(dá)時(shí)刻 events(3,i)=events(4,member(len_mem)-events(1,i); %其離開(kāi)時(shí)刻等于隊(duì)列中前一個(gè)顧客的離開(kāi)時(shí)刻加上其服 %務(wù)時(shí)間 events(4,i)=events(4,member(len_mem)+events(2

15、,i); %標(biāo)識(shí)位表示其進(jìn)入系統(tǒng)后，系統(tǒng)內(nèi)共有的顧客數(shù) events(5,i) = number+1; member = member,i; end end end end %仿真結(jié)束時(shí)，進(jìn)入系統(tǒng)的總顧客數(shù) len_mem = length(member); %* %輸出結(jié)果 %* %繪制在仿真時(shí)間內(nèi)，進(jìn)入系統(tǒng)的所有顧客的到達(dá)時(shí)刻和離 %開(kāi)時(shí)刻曲線圖（stairs：繪制二維階梯圖） stairs(0 events(1,member),0:len_mem); hold on; stairs(0 events(4,member),0:len_mem,.-r); legend(到達(dá)時(shí)間 ,離開(kāi)時(shí)間

16、); hold off; grid on; %繪制在仿真時(shí)間內(nèi)，進(jìn)入系統(tǒng)的所有顧客的停留時(shí)間和等 %待時(shí)間曲線圖（plot：繪制二維線性圖） figure; plot(1:len_mem,events(3,member),r-*,1: len_mem,events(2,member)+events(3,member),k-); legend(等待時(shí)間 ,停留時(shí)間 ); grid on;其余的圖改一下lamuda和mu值。程序2：clear;clc;n=8; a=zeros(n);a(1,2)=1.5;a(1,3)=1.5;a(1,4)=7.7;a(1,5)=1.5;a(1,6)=0.5;a(1,7)=1.4;a(1,8)=1.2;a(2,4)=8;a(2,6)=0.6;a(2,7)=0.1;a(2,8)=0.3;a(3,4)=8;a(3,6)=0.6;a(3,7)=0.1;a(3,8)=0.3;a(4,5)=8;a(4,6)=7.4;a(4,7)=7.9;a(4,8)=