,*,單擊此處編輯母版標題樣式,解題思路,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,CUMCM09,年,B,題,“眼科病床的合理安排,”,命題、解題思路解析及論文點評,國防科技大學 吳孟達,河南 鄭州,2010,年,4,月,8,日,1,解題思路,目 錄,命題思路,解題思路,論文點評,綜合評述,2,解題思路,命 題 思 路,來自于人們司空見慣的日常生活現(xiàn)象,醫(yī)院住院排隊現(xiàn)象,的一道題目，問題本身非常淺顯明白，專業(yè)門檻低，但解決問題中卻涉及較深刻的排隊論理論問題，當無法通過理論方法獲得最優(yōu)解時，可以通過仿真優(yōu)化方法獲得實用效果令人滿意的可行解，以上構成該道題目的特點。,3,解題思路,這一類以排隊論及仿真優(yōu)化方法為主要解決方法的題目，在,CUMCM,的歷年競賽題目中，還不多見。而這一類隨機服務系統(tǒng)優(yōu)化的問題，在現(xiàn)實實際中卻是大量存在的，因此，在以反映現(xiàn)實生活中的數(shù)學建模問題為己任的大學生數(shù)學建模競賽中，出現(xiàn)這一類題目，也是很自然的事情，,MCM,中如,04,年,B,題“游樂場快速通道問題”，,05,年,B,題“高速公路收費站問題”，就是兩個這類問題的實例。,4,解題思路,與我國龐大的人口總量相比較，好的醫(yī)院與好的醫(yī)生目前還是一種稀缺資源，題目中提到的醫(yī)院住院排隊現(xiàn)象及其嚴重程度是確實存在的，本問題提出的初衷，就是要得到對現(xiàn)有的病床安排,FCFS,方案的一個現(xiàn)實、合理的改進方案，所以，能得到最優(yōu)解固然好，否則得到一個實用效果令人滿意的可行解，也是可以的。,5,解題思路,主要考點：,1.,分布擬合檢驗；,2.,合理的評價指標體系；,3.,仿真方法應用；,4.,滿足一定置信度的統(tǒng)計預測模型的建立；,5.,排隊論優(yōu)化模型的建立。,6,解題思路,評閱原則,本題解題方法比較多，結果也未必一致，評閱時主要以解題過程中體現(xiàn)出的對問題的理解程度與建模能力為依據(jù)。,7,解題思路,解 題 思 路,數(shù)據(jù)分析與檢驗,在著手解決問題前首先應對所給數(shù)據(jù)進行分析，從中獲得對解題有用的信息，這是一種基本素質，是一種具有良好工程素養(yǎng)的表現(xiàn)。在本問題中，這一過程尤其重要，因為如果對病人到達規(guī)律及病人住院時間規(guī)律都不了解，問題癥結就抓不準，解題將缺乏方向感，仿真計算就更無法進行了。,8,解題思路,在本題所給數(shù)據(jù)中，各類病人到達人數(shù)分別服從不同參數(shù)的,Poisson,分布，需要進行分布擬合檢驗及分布參數(shù)提取。,由所給數(shù)據(jù)可以看出，病人術前住院時間是確定的，依入院時間而定，所以病人住院時間中只有術后住院時間是隨機的，要做擬合檢驗的也是這一部分時間分布。,各類病人術后住院時間分別服從正態(tài)分布、,分布 或埃爾朗分布，由于檢驗方法或檢驗細節(jié)處理不相同，可能得到以上不同的分布，這是允許的，但若得出服從負指數(shù)分布的結論，則是錯誤的。也有一些同學不做擬合分布檢驗，而是畫出直方圖，然后以此經驗分布作仿真依據(jù)，這樣處理也是可以的。,9,解題思路,數(shù)據(jù)分析做得比較深入的同學，會發(fā)現(xiàn)一條隱含在數(shù)據(jù)中的關鍵信息：術前住院時間過長是當前病床使用效率不高的主要因素。這樣一個關鍵信息的獲得，會使得建模更有方向感。,10,解題思路,第 一 問,主要考核對問題的考慮是否全面，對問題實質的理解是否到位。評價指標分兩類：效率指標和公平性指標。,兩類指標可以有各種不同的定義，其合理性是評分依據(jù),。,效率指標,平均,術前住院時間，或病床有效利用率。,非外傷病人入院第,2,日（白內障）或第,3,日（其他眼?。┖蟮却中g的時間稱為病床無效時間，病床有效利用率定義為,病床有效利用率,=1-,病床無效時間,/,該病人住院時間,11,解題思路,公平性指標,從公平性考慮，希望盡量做到,FCFS,（,First come,First serve,）,公平度具體如何確定，是一個小考點。這個指標必須考慮，否則會出現(xiàn)盡量收白內障病人入院，以改善效率指標的現(xiàn)象。,一種比較具操作性的指標是,用“延期住院”病人人數(shù)占總出院人數(shù)的比例來度量不公平度。,注意到，上述公平度只考慮了“延期日子”，而沒有將“插隊人數(shù)”度量在內，對此可以有不同的理解與定義，不必苛求一致。,12,解題思路,第 二 問,本問主要考核能否給出一個相對合理的病床安排模型，主要目標為：提高病床有效利用率以及提高公平度。,就提高病床有效利用率而言，病人術后住院時間是一個不可優(yōu)化的量，所以只能在術前等待時間上作文章。經對題目所給數(shù)據(jù)的分析可知：,對白內障病人的入院時間加以限制成為提高效率的必然選擇。,13,解題思路,本問主要解決方法是仿真方法，大致可分為“先仿真，再優(yōu)化”與“邊仿真，邊優(yōu)化”兩類，前者是先確定若干種住院規(guī)則，然后根據(jù)仿真統(tǒng)計結果選出較優(yōu)規(guī)則；后者是先確定一個優(yōu)化原則，然后在仿真時，對每一個排隊病人按照該優(yōu)化原則決定住院先后。顯然后者要更好一些。,14,解題思路,一種比較典型的仿真優(yōu)化方法是：對每一位等待入院病人，以該病人當日入院的公平性（以到達先后計）與病床使用效率（分類考慮）兩方面綜合排序（例如求兩個指標的加權和），然后按排序結果安排當日入院病人，由此得到公平合理的住院方案。按此方案進行仿真，再統(tǒng)計各項評價指標值，并與,FCFS,方案作比較，此問即告完成。,15,解題思路,值得一提的是，解法的多樣性在本問題求解中得到了較充分的體現(xiàn)，例如有的參賽隊引入了計算機操作系統(tǒng)進程調度中的最佳響應比算法，使公平性與效率同時得到了體現(xiàn)，是一種好的創(chuàng)意。,本問中存在的主要問題是公平性考慮不足，有的隊甚至完全不考慮公平性，未免過于脫離實際，而脫離實際是建模最大的忌諱。還有較普遍存在的問題是主要優(yōu)化目標不清晰，羅列了一堆目標，卻未抓住提高病床使用效率這個要害，其根源還是對題目的理解以及對數(shù)據(jù)的分析不夠透徹。,16,解題思路,第 三,問,此問希望學生給出一個滿足一定置信度（例如：,90%,）的預約住院時間區(qū)間，區(qū)間長度越短越好。,一種自然的想法是通過同類病人術后住院時間的概率分布從理論上得到這一區(qū)間，如果能通過此種理論方法解決此問題，自然是最理想的。但這樣做的一個困難是已處于術后住院狀態(tài)的該類病人的繼續(xù)住院時間不服從同一分布，從而將該類病人（含已住院與未住院）的預計住院時間求和后的隨機變量的分布不知道。,17,解題思路,設當前時刻為,T,0,，當前排隊人數(shù)為,P,，預計住院時刻為,T,，該類病人每日出院人數(shù)的統(tǒng)計平均值為,，則,設一個已出院病人實際住院時刻為,T,1,，通過仿真統(tǒng)計一段時間內所有病人的,根據(jù),90%,的置信度確定兩個閾值,從而得到當前病人的預計住院時間區(qū)間為,。,18,解題思路,第 四,問,若仍采用“一三方案”，效率較低，通過分析可以發(fā)現(xiàn)主要原因是對視網膜與青光眼病人而言，會造成病床使用效率降低。,通過有限種方案的仿真計算比較可知，采用“二四方案”或“三五方案”可使病床使用效率有所提高。前者效率公平總體效果較好，后者效率較高，但公平性較差。,19,解題思路,第 五,問,主要有三種模型：,一、仿真計算模型：床位分配只有有限種組合情形，可以通過窮舉仿真方法得到各種組合的評價指標統(tǒng)計值，再比較得到最佳組合方案。此方案計算量較大，且模型通用性有一定局限。,二、服務強度平衡模型：當各分類系統(tǒng)的服務強度相等時，效果最佳?？梢酝ㄟ^建立條件極值模型，利用拉格朗日方法證明這一結論。,三、排隊論近似模型：通過經驗公式將,M/G/K,系統(tǒng)近似為,M/M/K,系統(tǒng)，然后利用排隊論的現(xiàn)成結論寫出優(yōu)化模型。,20,解題思路,論 文點 評,21,解題思路,綜 合 評 述,數(shù)據(jù)檢驗是本問題中必須做的，但被許多參賽隊所忽略，從而意外成為區(qū)分點之一。,公平性指標被許多人忽略，反映出對問題本質認識不到位。效率指標也可以適當精簡。,優(yōu)化模型的多樣性是本題目最大的亮點，涌現(xiàn)許多意料之外的解法。,22,解題思路,入院時間的預測區(qū)間完成不好，大部分隊沒有置信度概念，不少隊給出的區(qū)間與當前隊長無關。,第五問理論深度較深，完成得好的不多，拉格朗日條件極值方法的運用是一種有趣的方法。,存在模型與求解“兩張皮”的現(xiàn)象，以及捏造數(shù)據(jù)結果的現(xiàn)象，反映出一些學風問題，計算能力的欠缺也是一個原因。,23,解題思路,總體上說，競賽論文完成得很好的不多，而在一些基本問題上也做得不理想的論文卻不在少數(shù)，反映出學生對此類問題的生疏。另外，對問題本質的理解不到位的也大有人在。,抽象來看，本問題可歸類于一個通道分類服務臺共享的多通道隨機服務問題，對這樣的問題，排隊論中還沒有現(xiàn)成的解決方法，可以作為一個排隊論問題加以繼續(xù)研究。,24,解題思路,謝謝！,25,解題思路,