本文在研究體檢排隊問

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

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

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

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

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

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

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

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

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

10、，則鄰接矩陣中對應(yīng)的元素為 1；否則為0?？梢钥闯?，這種表示法非常簡單、直接。但是，在鄰接矩陣的所有n2個元素中，只有m個為非零元。如果網(wǎng)絡(luò)比較稀疏，這種表示法浪費大量的存儲空間，從而增加了在網(wǎng)絡(luò)中查找弧的時間。 對于上述的問題，可以分別在A、B、C、D、E、F、G、H等各個體檢項目抽象成一個點，邊權(quán)近似等于時間和受檢比率的內(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同樣，對于網(wǎng)絡(luò)中的權(quán)，也可以用類似鄰接矩陣的88 矩陣

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

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

13、顧客個數(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個顧客，其標(biāo)志位置 0 if number = N+1 events(5,i) = 0; %如果系統(tǒng)為空，則第 i個顧客直接接受服務(wù) else if number = 0 %其等待時間為 0%PROGRAMLANGUAGEPROGRAMLANGUAGEevents(3,i) = 0; %其離開時刻等于到達時刻與服務(wù)時間之和 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)等待隊列未滿，則 第 i個顧客進入系統(tǒng) else len_mem = length(member); %其等待時間等于隊列中前一個顧客的離開時刻減去其到 達時刻 events(3,i)=events(4,member(len_mem)-events(1,i); %其離開時刻等于隊列中前一個顧客的離開時刻加上其服 %務(wù)時間 events(4,i)=events(4,member(len_mem)+events(2

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

16、); hold off; grid on; %繪制在仿真時間內(nèi)，進入系統(tǒng)的所有顧客的停留時間和等 %待時間曲線圖（plot：繪制二維線性圖） figure; plot(1:len_mem,events(3,member),r-*,1: len_mem,events(2,member)+events(3,member),k-); legend(等待時間 ,停留時間 ); 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)=