2009年全国大学生数学建模B题
- 格式:doc
- 大小:206.50 KB
- 文档页数:10
B题公交车调度
公共交通是城市交通的重要组成部分,作好公交车的调度对于完善城市交通环境、改进市民出行状况、提高公交公司的经济和社会效益,都具有重要意义。
下面考虑一条公交线路上公交车的调度问题,其数据来自我国一座特大城市某条公交线路的客流调查和运营资料。
该条公交线路上行方向共14站,下行方向共13站,第3-4页给出的是典型的一个工作日两个运行方向各站上下车的乘客数量统计。
公交公司配给该线路同一型号的大客车,每辆标准载客100 人,据统计客车在该线路上运行的平均速度为20公里/小时。
运营调度要求,乘客候车时间一般不要超过10分钟,早高峰时一般不要超过5分钟,车辆满载率不应超过120%,一般也不要低于50%。
试根据这些资料和要求,为该线路设计一个便于操作的全天(工作日)的公交车调度方案,包括两个起点站的发车时刻表;一共需要多少辆车;这个方案以怎样的程度照顾到了乘客和公交公司双方的利益;等等。
如何将这个调度问题抽象成一个明确、完整的数学模型,指出求解模型的方法;根据实际问题的要求,如果要设计更好的调度方案,应如何采集运营数据。
眼科病床安排的优化模型摘要本文主要针对眼科医院病床的合理安排问题,以排队论,优先级理论和优化理论为基础,依据实际的情况,建立不同的眼科病床安排模型,并解得了评价指标和具体方案,较好地解决了病床安排的问题,提高了医院对资源的有效利用率.对于问题一,综合各方面的因素,确定三个评价指标,分别是病人的平均等待时间q W ,病人的平均住院时间h W 和病床的有效使用率B .以这三个指标建立评价指标体系,对文中不同模型的结果做出评价分析.对于问题二,首先,用问题一中建立的评价指标体系对医院的FCFS 模型的各指标进行计算,得到q W =12.3,h W =9.0,B =58.4%.接着,考虑到每种眼病在一周内手术安排时间不同,引入优先级概念,对一周内不同种类的眼病进行分级排序,按照优先级从高到低对病人的床位进行安排,对于同等级别的眼病采取FCFS 原则,建立一个基于优先级和FCFS 原则的床位安排模型.利用该模型,对附录中的数据进行仿真模拟,将表格填齐,最后统计出各指标的数据:q W =11.8,h W =9.0,B =83.0%,对比分析两个模型的各指标数据,可知基于优先级和FCFS 原则的床位安排模型要优于FCFS 模型.对于问题三,利用基于优先级和FCFS 原则的床位安排模型,对附录中等待住院的102位病人进行仿真模拟,统计模拟的结果,分析每种眼病平均等待时间的分布情况.由于每天某种眼病优先等级会影响到该眼病的等待时间,因此统计出周一至周五不同眼病的平均等待时间,并分析其与每种眼病平均等待时间的分布之间的联系,从而根据病人门诊的时间和眼病的种类估算出大概的等待入院时间.对于问题四,在周六,周日不安排手术的情况下,考虑不改变手术时间和改变手术时间两种方案,分别分析各种眼病的手术时间,对问题二中模型的优先级进行改进,以附录中的数据进行仿真模拟,分别计算出各项评价指标,进行对比分析.在不改变手术时间的方案中,q W =12.0,h W =8.6,B =36.1%;在改变手术时间的方案中,通过对各眼病患者的门诊时间进行分析,将白内障手术时间改为周二和周四,算出的指标为q W =12.5,h W =9.2,B =29.0%.对比分析后可得不改变手术时间而只改变模型优先级的方案更为合理.对于问题五, 对于问题五,首先,将病床按照眼病的种类分为5个区域,假设每个区域内病人的排队系统都为///M M S ∞排队论模型.接着,统计附录中的数据,计算出每种眼病的平均到达率i λ和平均服务率i μ,再通过///M M S ∞排队论模型中的运行指标公式,可得到各类眼病的平均逗留时间。
眼科病床的合理安排摘要本文主要是对当前的门诊入院安排给予合理评价,并建立模型解决不同情况下的最合理的门诊入院安排问题。
首先,我们根据层次分析法对当前的入院安排进行合理评价,其入院是否合理主要看病人在手术前的总的等待时间,病人总的平均等待时间越短对医院和病人来说也越合理,而病人手术前的等待时间是由入院前等待时间1t ,手术前等待时间2t 这两部分时间构成,所以入院前等待时间1t ,手术前等待时间2t 决定了入院安排的合理性。
针对问题二,多个病人等待有限的病床,对医院来说病人流动频率越快越好,首先我们考虑SJF 算法,这种算法固然可以加快医院的病人流通率和病床的使用率,但不能达到公平平等的对待看病的病人,使得需要较长住院时间的病人特别时视网膜疾病的病人不能有效及时的得到解决,很可能会出现长时间更甚至是永远也得不到治疗。
所以,我们实际生活中医院不会考虑这种模型来安排给病人看病。
所以我们考虑用HRN 算法,根据,1rλσ+=决定每天的入院病人。
其中,λ为入院前等待时间,r 为住院到手术前的时间。
在每天知晓病床数的情况下,由响应比高的等待入院的病人入院。
对于问题四,由于周六周日不做手术,其r (i)住院到手术前的时间可能发生变化,同样用此模型对问题二中的病人安排做更改。
而问题三,由非线性规划求解第K 个门诊未入院的病人入院时间,Si 为从九月十二号起第i 天的门诊总人数,由表知平均每天外伤门诊人数为1,其决策变量:i ;约束条件:01≥--∑=K i Si ni ;)()()()()(54321i l i l i l i l i l Si ++++=;i p k k q i l j j j +=+=∑28),()(目标函数:K i Si Min ni --∑=1。
对此模型最后运行的见附录中表3。
最后,对于按比例分配各种疾病的病床数,建立使得病人平均逗留时间最短的病床比例分配模型,我们采用排队论的服务排队分析方法,建立多服务台多种类的服务排队数学模型。
基于M/M/S排队论的病床安排模型(获2009年大学生数学建模赛全国二等奖)数学与计算科学学院雷蕾信息科学与计算学院黄缨宁信息科学与计算学院丁炜杰指导老师:王其如教授摘要就医排队是一种我们非常熟悉的现象。
在眼科医院的病床安排中,主要从医院高效工作和患者满意度两方面来考虑安排方法。
本文通过确定两方面的权重,确立评价标准。
针对问题二,本文确定了从医院和患者两方面综合考虑的目标函数,医院各种诊疗规则的限制下进行线性规划,使得目标函数值(背离度)最小,得到问题二的解决方案。
用问题一的标准评价,确实优于医院的FCFS模型。
问题三中对每一类病人术后恢复时间做统计,由计算机按照概率给出术后恢复的时间,运用第二问模型的选择方式,对近一段时间内的出入院人数作出合理预测,并根据M的排序确定患者入院的时间区间。
对于问题四,先确立白内障双眼手术的方案(调查支持可以任意不同两天手术),按照问题二的算法,先算出周二四做白内障手术的最小M值及入院前等待时间和术前等待时间。
用计算机模拟出在手术时间可调整情况下M可能的最小值,得到周三五为最佳手术时间。
尤其术前人均等待时间的优化减少使医院病床的有效使用率增加。
模型改进率达到18.11%。
问题五要求确定病床固定分配使人均等待时间最短。
病床的分配使整个排队系统变成了五个M/M/N模型,N为各类病床的数量。
根据排队论中M/M/1模型的条件演化得到服务强度小于1及病床数固定不变。
采取整数规划,在此限制条件下使得平均等待时间最小。
从而算出各类病床的分配比例。
关键词:M/M/S模型泊松(Poisson)分布非线性规划优化模型病人满意度病床有效利用率一.问题的重述有某医院眼科门诊每天开放,住院部有病床79张。
眼科手术主要分四大类:白内障、视网膜疾病、青光眼和外伤。
白内障手术较简单且没有急症。
目前只在周一、三做白内障手术,此类病人的术前准备时间只需1、2天。
如果要做双眼是周一先做一只,周三再做另一只。
2009高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。
我们知道,抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺,严格遵守竞赛规则,以保证竞赛的公正、公平性。
如有违反竞赛规则的行为,我们将受到严肃处理。
我们参赛选择的题号是(从A/B/C/D中选择一项填写): B我们的参赛报名号为(如果赛区设置报名号的话):所属学校(请填写完整的全名):参赛队员(打印并签名) :1.2.3.指导教师或指导教师组负责人(打印并签名):日期: 2010 年 7 月 20 日赛区评阅编号(由赛区组委会评阅前进行编号):2009高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号(由赛区组委会评阅前进行编号):全国统一编号(由赛区组委会送交全国前编号):全国评阅编号(由全国组委会评阅前进行编号):眼科病床的合理安排摘要医疗服务质量的改善关系到民生,也是我国构建“和谐社会”的重要基础。
病床作为一种重要的医疗资源,其合理的安排和有效的使用能很大程度上改善医疗服务的质量和解决“看病难”的问题。
确立诊前延误指标、手术延误指标、就医水平指标和医务效率指标四个构成因素,建立综合指标评价模型;通过对所给数据的处理,预测不同病症住院时间的周期,测定出患者从门诊到住院等待的时间区间即为病人门诊时即告知其大致住院时间的区间:果。
关键词:综合指标评价模型;病床合理分配一、问题重述与分析1.1问题的重述医院就医排队是大家熟悉的一个生活现象。
例如,患者到门诊就诊、到收费处划价、到药房取药、到注射室打针、等待住院等,往往需要排队等待接受某种服务。
我们需要对某医院眼科病床的合理安排建立数学建模。
眼科病床的合理配置优化模型摘要:本文将眼科患者中除外伤(一般作为急症处理)外的三种患者以平均等待时间(从门诊就诊到入院的时间 + 手术准备时间)最短衡量病床安排方案合理程度,并以此为基础建立合理的评价指标体系;利用Matlab软件对医院所提供的有关数据进行了详细的分析处理,运用排队论建立了该医院病床安排模型,将分配床位的结果(等待时间)与原来等待时间做了比较,说明运用此模式分配床位更合理;根据每个窗口最大接收病人的能力以及住院病人及等待住院的病人的统计情况,可以在门诊就诊时告诉需要住院的病人大致入院时间;同时,在周六、周日不安排手术的情况下,对该医院病床安排模型进行了相应的调整;建立了使得病人在系统内的平均逗留时间(含等待入院及住院时间)最短的病床比例分配模型。
关键词:眼科医院;病床;安排;模型;排队论一、问题重述医院就医排队是大家都非常熟悉的现象,由于眼科病人的病情严重程度存在差异,有的只需要一次手术就可以治愈,有的需要二次手术(比如白内障患者分一只眼和两只眼患病两种情况),并且在入院前和术前一般都有等待时间,在术后都有不同长度康复时间(这里指需要留院观察的时间),会有很多患者为就诊治病而等待比较长的时间,为解决这种问题,如果医院增添服务人员和设备,就需要增加人力和物力的投资,若处理不当,很有可能对医院造成资源的浪费;不采取相应的措施,则排队等待时间太长的现象很难得到改善,对患者和社会都会带来不良影响。
为此,采用排队论的有关理论[2],利用计算机对一个客观复杂的排队系统的结构和行为进行动态模拟,以获得反映其系统本质特征的数量指标结果,进而预测、分析或评价该系统的行为效果,为决策者提供决策依据。
因此,医院管理人员要考虑如何在这两者之间取得平衡,以便提高服务质量,降低服务费用.。
二、问题假设1、假设就医患者在某段时间区间内到达的患者数的概率与这段时间的长度和患者数有关;2、在不相同的时间区间内到达的患者数是相互独立的;3、在同时间点上就诊或手术最多到达1个患者,不存在同时到达2个以上患者的情况;4、在有限的时间区间内只能到达有限个患者,不可能有无限个患者到达;5、假定医院急诊窗口属于标准型:即急症病人不需要等待,病人一到即可就诊,并且对于需要住院、手术时均可及时得到满足。
三、问题分析病人在就诊时,医院的医疗器件、医生人数的限制,或是由于病人就诊规则的不合理,会导致一些资源的浪费,甚至会导致一些病人得不到及时就诊而错过最佳的治疗时机。
因此,医院想办法解决这种问题,增加医务人员和设备会增加投资或发生空闲浪费;如果减少服务设备, 排队等待时间太长, 对患者和医院都会带来不良影响. 通过对问题的分析,可以结合排队论原理,将这个问题转变为排队论问题去讨论。
衡量指标确定为:平均等待时间(从门诊就诊到入院的时间+ 手术准备时间)最短,根据排队论原理,通过对所给数据进行了分类统计,对该医院的病人入住设置了不同的窗口,并对分类结果进行了详细的分析,建立了排队论模型,根据所建立的模型对该医院两个月时间内就诊病人的平均等待时间进行了计算,并与未采取这种措施的平均等待时间进行了比较,说明所采取的措施是可行的,为改善该眼科医院目前病床安排现状提供了比较合理的依据。
四、模型的建立(一)、模型的初步建立如M/M/1即表达到达过程服从泊松分布,服务时间服从负指数分布,服务台为一个,系统容量和顾客源无限,服务规则为FCFS的情况。
另外需要指出的是排队规则通常有标准型、顾客源有限型和服务系统容量有限型三种。
由于一个城市或任何地区的所有人都被认为是医院的可能“顾客”,这样到达的“顾客”数目可以认为是无限的,因此顾客源为有限的情况通常在医院服务中心是不存在的。
有些服务系统的容量是有限的,医院存在这种情形,如规定一天门诊挂50个号,那么第51个病人就会被拒绝。
对于医院急诊来说病人来源是无限的,系统容量也是无限的。
因此我们也可假定医院急诊排队系统就属于标准型:即急症病人不需要等待,病人一到即可就诊,并且对于需要住院、手术时均可及时得到满足。
1、排队系统的数量指标研究排队系统的目的是通过了解系统状态,对系统进行调整和改进,使系统达到最优化的运行状态,取得最大的经济效益和社会效益。
从这一出发点,我们必须确定用以判断系统运行优劣的指标。
队长:指在系统中的顾客数,包括正在排队的顾客和正在接受服务的顾客,它的期望值记作Ls;队列长:指在系统中排队等待服务的顾客数,它的期望值记作Lq;队长=队列长+正被服务的顾客数。
Ls(或Lq)越大,说明服务率越低。
逗留时间:指一个顾客在系统中的停留时间,它的期望值记作Ws;等待时间:指一个顾客在系统中排队等待的时间,它的期望值记作Wq。
逗留时间=等待时间+服务时间据调查显示,医院就诊排队问题中“顾客”常常只需关心等待时间的长短。
2、排队模型简介M/M/1模型即指顾客到达服从泊松分布[3],服务时间服从负指数分布,单服务台的情形,是实际中使用最广,数学处理最简单的模型,在排队论中有重要的作用。
标准的M/M/1模型是适合下列条件的排队系统:输入过程——病人源是无限的,单个到来且相互独立,一定时间的到达数服从泊松分布,到达过程已是平稳的(到达间隔时间及期望值、方差均不受时间影响)。
排队规则——单队,且对队长设有限制,先到先服务。
服务机构——单服务台,各病人的诊治时间时相互独立的,服从相同的负指数分布。
此外,还假定病人到达间隔时间和诊治时间是相互独立的。
M/M/1模型要求到达规律服从参数为λ的泊松过程,服务时间服从参数为μ的负指数分布。
λ即平均到达率,表示单位时间平均到达的病人数。
μ即平均服务率,表示单位时间能被服务完的病人数(期望值),而1/μ就表示一个病人的平均服务时间。
在排队论中“平均”指概率论中的数学期望,这两个参数都需要对实测的数据经过统计学检验来确定。
/λμ有着重要意义,它是相同时间区间内病人到达的期望值与能被服务的期望值之比,这个比是刻划服务效率和服务机构利用程度的重要标志。
令/ρλμ=我们称ρ为服务强度。
在解排队论问题时,需要求出系统在任意时间的状态为n (系统中有几个病人数)的概率n P ,它决定了系统运行的特征,在本标准模型中,(1)n n P ρρ=-。
由此推断,当0P =时,011/P ρλμ=-=-,即系统内病人为0的概率,即空闲概率或病人不必等待的概率。
因此,可以得出排队论的各个运行指标:多服务台标准模型M/M/S 在计算上与M/M/1相似,其平均服务率's μμ=,或平均到达率's λλ=,即平均服务率是单服务台模型的s 倍,到达率是平均到达率的1/s 。
由此引出另一个问题,s 个M/M/1与1个M/M/S 模型相比谁的效率更高,在实际中即体现为分别在服务台排队还是统一排队安排进入服务台的问题。
计算证实,在服务台个数和服务率不变的条件下,联合服务(单队排队)比分散服务(多排队模式)效率更高,这是在实际使用中需要主要的问题。
因此,我们可以计算排队理论的各个指标,进行系统运行的评价。
在实际运用中,只要选择适当的模型,并提供输入数据,包括到达率λ,服务率μ和服务台数量,即可得出所有需要的评价指标。
3、使用排队模型中需要注意的问题研究对象的数据分布律问题派对系统中研究对象的数据分布通常需要经过假设检验验证(1-Sample K-S Test),通常来说,K-S检验比2χ[1]检验更具有优越性,因为其避免了2χ检验对于数据分类的依赖。
等待时间和服务能力的权衡顾客等待和服务能力之间的权衡随处可见。
能力规划决策包含了对于提供服务的成本和顾客等待的成本(或者说是给顾客造成的不便)二者之间的权衡。
服务能力的成本由提供服务的服务台的数量决定,而顾客的不便是由等待时间来衡量的。
假设等待可以用货币成本来表示,那么,增加服务能力会导致等待成本降低而服务成本提高。
也就是我们在实际中看到的增加诊间或服务设备成本必然增加,而病人等待时间降低,这是决策者必须权衡的矛盾。
在排队理论中也提供了费用模型来解决这部分问题,但是必须计算出病人等待费用和我们的服务费用,其中病人等待的费用可能包括队列过长病人流失和病人等待病情恶化等潜在的损失,这在实际工作在很难估计。
稳态或统计平衡状态计算上述所有指标的基础时系统状态的概率,这些状态概率与时刻t有关,但是当t充分大的时候,一个系统在t时刻的状态概率就接近于一个常数Pn.这时候就称为稳态或统计平衡状态。
我们所计算得出的概率都是在稳态的假设下得出的。
另外,根据以上的公式可以发现,当λμ>时,即平均到达率大于平均服务率,系P将成负值,这显然是不符合统中病人到达率大于了能够容纳的病人数,那么空闲概率实际的。
我们可以解释为系统服务没有空闲的时间,而病人的队长将无限延长,也就是λμ<说,这一系统永远无法达到稳态,所以在运用排队理论时还有一个重要条件,即/1或λμ<。
排队理论在医院各项服务中都有广泛的运用前景,使用科学的方法进行科学的决策,也是现代管理所要求的。
在运用时必须注意运用的几个必要条件,否则将得出错误的结论。
在现实中,一般地随机到达规律都服从泊松过程。
病人到达医院的过程一般也是泊松过程,因此这有些情况下计算平均到独立时可不进行检验,以减少计算量。
图1. M|M|n多服务窗口等待制排队模型(二)、原病床安排模型的优劣分析问题一:我们对各种病人的就诊情况进行了统计,并求了相关的平均值,具体结果如表1所示:表1中,平均占床时间指该病人从住院到出院所用的时间的平均值;人数为该种病人在1个月到门诊看病人数;入院与门诊的相差天数指门诊就诊时间与入院时间之间的等待天数;于是,目前该医院住院部对全体非急症病人按照FCFS规则安排住院,计算出其平均等待时间在床位满的情况下青光眼、白内障单眼手术、白内障双眼手术以及视网膜病人的需要就诊所需要平均等待时间依次分别为,14.41;15.40;15.52;15.4天,而从平均占床时间可以看出,该种病人的在床位时间一般小于等待时间,因此在这种情况下,一些病人可能会得不到就诊而错过最佳的治疗时间,因此目前该医院的采取的入住方式不合理。
(三)、新模型的确立由于在遇到急症病人需住院治疗时,必须立即为急症病人分配床位,而在不能分配床位的情况下,必须告知病人,让其在其他医院就诊,鉴于此,通过对急诊病人所占比例数据的统计分析,算得急症患者占床位时间基本为7天,而急症患者的平均入住时间占比例为0.089(见表2),在所给定79张床位的情况下,为急症病人分配7张床位,在以一周为7天为周期时,可以满足急症病人的要求。
因此在为其分配床位的情况下,该种患者的就诊不会对其他类病人产生影响。
本模型中参数c可通过现场获得,λ和μ分别表示该模型当中泊松流得参数,μ表示负值数分布得参数,c表示窗口的数目。