2011数学建模排队论

数学建模之ChinaUndergraduateMathematicalContestinModeling建模群号：617711621.CUMCM的历年赛题浏览：1992年:(Ａ)作物生长的施肥效果问题(北理工：叶其孝）(B)化学试验室的实验数据分解问题（复旦：谭永基）1993年:(Ａ)通讯中非线性交调的频率设计问题（北大:谢衷洁）(Ｂ)足球甲级联赛排名问题（清华：蔡大用）1994年:(Ａ)山区修建公路的设计造价问题（西电大：何大可）(Ｂ)锁具的制造、销售和装箱问题（复旦:谭永基等）1995年:(Ａ)飞机的安全飞行管理调度问题（复旦:谭永基等）(Ｂ)天车与冶炼炉的作业调度问题（浙大:刘祥官等）一、CUMCM历年赛题的简析1.CUMCM的历年赛题浏览：1996年:(A)最优捕鱼策略问题（北师大：刘来福）(B)节水洗衣机的程序设计问题（重大：付鹂）1997年:(A)零件参数优化设计问题（清华：姜启源）(B)金刚石截断切割问题（复旦：谭永基等）1998年:(A)投资的收益和风险问题（浙大：陈淑平）(B)灾情的巡视路线问题（上海海运学院:丁颂康）1999年:(A)自动化机床控制管理问题（北大：孙山泽）(B)地质堪探钻井布局问题（郑州大学：林诒勋）一、CUMCM历年赛题的简析1.CUMCM的历年赛题浏览：2000年:(A)DNA序列的分类问题（北工大：孟大志）(B)钢管的订购和运输问题（武大：费甫生）2001年:(A)三维血管的重建问题（浙大：汪国昭）(B)公交车的优化调度问题（清华：谭泽光）2002年:(A)汽车车灯的优化设计问题（复旦:谭永基等）(B)彩票中的数学问题（信息工程大学：韩中庚）2003年:(A)SARS的传播问题（集体）(B)露天矿生产的车辆安排问题（吉林大：方沛辰）一、CUMCM历年赛题的简析1.CUMCM的历年赛题浏览2004年:(A)奥运会临时超市网点设计问题(北工大：孟大志)(B)电力市场的输电阻塞管理问题(浙大:刘康生）2005年:(A)长江水质的评价与预测问题（信息工大:韩中庚）(B)DVD在线租赁问题（清华大学：谢金星等）2006年:(A)出版社的资源管理问题（北工大:孟大志）(B)艾滋病疗法的评价及预测问题（天大：边馥萍）2007年:(A)中国人口增长预测问题（清华大学:唐云）(B)“乘公交，看奥运”问题（吉大：方沛辰，国防科大：吴孟达）一、CUMCM历年赛题的简析2、从问题的实际意义分析32个问题从实际意义分析大体上可分为：工业、农业、工程设计、交通运输、经济管理、生物医学和社会事业等七个大类。工业类：电子通信、机械加工与制造、机械设计与控制等行业,共有8个题，占25%。农业类：１个题，占3.1%。工程设计类:3个题，占9.4%。交通运输类：4个题，占12.5%经济管理类：5个题，占15.6%生物医学类：5个题，占15.6%社会事业类:6个题，占18.8%有的问题属于交叉的，或者是边缘的。一、CUMCM历年赛题的简析3、从问题的解决方法上分析从问题的解决方法上分析，涉及到的数学建模方法：几何理论、组合概率、统计(回归)分析、优化方法（规划）、图论与网络优化、层次分析、插值与拟合、差分方法、微分方程、排队论、模糊数学、随机决策、多目标决策、随机模拟、灰色系统理论、神经网络、时间序列、综合评价、机理分析等方法。一、CUMCM历年赛题的简析•用的最多的方法是优化方法和概率统计的方法.•用到优化方法的共有22个题，占总数的68.8%，其中整数规划4个，线性规划6个，非线性规划14个,多目标规划6个。•用到概率统计方法的有16个题，占50%，平均每年至少有一个题目用到概率统计的方法。•用到图论与网络优化方法的问题有6个；•用到层次分析方法的问题有３个；3、从问题的解决方法上分析一、CUMCM历年赛题的简析•用到插值拟合的问题有6个；•用到神经网络的4个；•用灰色系统理论的4个;•用到时间序列分析的至少2个;•用到综合评价方法的至少3个；•机理分析方法和随机模拟都多次用到;•其他的方法都至少用到一次。•大部分题目都可以用两种以上的方法来解决,即综合性较强的题目有26个，占81.3%。3、从问题的解决方法上分析一、CUMCM历年赛题的简析两个引例：问题1:校园网的设计和调节收费问题•随着计算机技术的飞速发展，校园信息网已经在全国高校中普及。•某高校拟建一个校园信息网，并与Internet连接，用户可以通过网络通信端口拨号上网。•因此，需要用户的数量，研究通信端口的设计规模。问题1:校园网的设计和调节收费问题•通常的通信端口分为16口，32口，64口，128口。•实际中，随着通信端口数量的增加，其成本费将成倍增加。•如何根据实际情况，在保证基本满足用户需求的条件下，确定合适的通信端口数，以减少费用的开支和资源的浪费。•当网络建成以后。为了保证用户有效的使用信息网，必须要通过适当的收取线路调节费，以控制上网时间。问题1:校园网的设计和调节收费问题•一般认为，采用分段计时收费比较合理，例如按上网时间长短分为“免费－半费－全费－2倍－3倍－4倍……”等时段。•现在的问题是：•（1）假设有m个用户，每个用户每天（按16h计算）平均上网1.5h，试确定通信端口数n与m的比例问题1:校园网的设计和调节收费问题•（2）假设m＝150，按所设定的通信端口数n，试讨论平均每天每个用户上网1h，2h，3h，4h，5h的可能性，出现因线路忙，导致用户想上网而上不去产生抱怨的可能性，以及通信端口的平均使用率；•（3）为了控制上网时间，学校要求适当收取线路调节费，试给出一种合理的分段计时收费方案。问题2:眼科病床的合理安排问题09B•医院是一个复杂的系统，病人从挂号、就诊、划价、取药需遍历每一个服务机构,当某项服务的现有需求超过提供该服务的现有能力时,排队现象就会发生,由于患者到达时间和诊治患者所需时间的随机性,可控性小,排队几乎不可避免。因此如何合理科学安排医护人员及医疗设备,使医院不会盲目增加医生和设备造成不必要的空闲,形成资源浪费,又使患者排队等待时间尽可能减少,如何在这两者之间取得平衡,以便提高服务质量,降低服务费用,这是现代医院管理者必须面对的课题。问题2:眼科病床的合理安排问题09B•本题给出了病床数与眼科手术类别及要求，附录中还提供了一段时间的统计数据，要求回答五个问题。•（1）确定合理的评价指标评价该问题的病床安排模型，即评价FCFS模型；•（2）建立合理的病床安排模型，确定第二天应该安排那些病人入院，并用上述指标进行检验；问题2:眼科病床的合理安排问题09B•(3)通过统计分析，求得病人的入住时间的区间；•（4）在周六、周日不手术时，重新计算评价指标，判断优劣后对手术时间安排做适当调整；•（5）固定各类病人占用病床的比例，使得所有病人在系统内的平均逗留时间（含等待入院及住院时间）最短。•CUMCM09年B题“眼科病床的合理安排”主要考点：1.分布拟合检验；2.合理的评价指标体系；3.仿真方法应用；4.满足一定置信度的统计预测模型的建立；5.排队论优化模型的建立。排队论(QueuingTheory)排队论（queuing),也称随机服务系统理论，是运筹学的一个主要分支。1909年，丹麦哥本哈根电子公司电话工程师A.K.Erlang的开创性论文“概率论和电话通讯理论”标志此理论的诞生。排队论的发展最早是与电话，通信中的问题相联系的，近年来在计算机通讯网络系统、交通运输、医疗卫生系统、库存管理、作战指挥等各领域中均得到应用。排队论•前言•基本概念•到达时间间隔分布和服务时间分布•M/M/1单服务台的排队系统•M/M/c多服务台的排队系统•校园网的设计和调节收费问题排队是我们在日常生活和生产中经常遇到的现象。例如，上、下班搭乘公共汽车；顾客到商店购买物品；病员到医院看病；旅客到售票处购买车票；学生去食堂就餐等就常常出现排队和等待现象。前言除了上述有形的排队之外，还有大量的所谓“无形”排队现象。如几个顾客打电话到出租汽车站要求派车，如果出租汽车站无足够车辆、则部分顾客只得在各自的要车处等待，他们分散在不同地方，却形成了一个无形队列在等待派车。前言排队的不一定是人，也可以是物：例如，通讯卫星与地面若干待传递的信息；生产线上原料、半成品等待加工；因故障停止运转的机器等待修理；码头的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋等等。前言上述各种问题虽互不相同，但却都有要求得到某种服务的人或物和提供服务的人或机构。排队论里把要求服务的对象统称为“顾客”,提供服务的人或机构称为“服务台”或“服务员”。前言图1单服务台排队系统（去代售点买火车票）前言不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图1至图5。图2单队列——S个服务台并联的排队系统（找工作）图3S个队列——S个服务台的并联排队系统（火车站买火车票）前言图4单队——多个服务台的串联排队系统（报名）图5多队——多服务台混联网络系统（体检）前言图6随机服务系统前言一般的排队系统，都可由下面图加以描述。通常称由图6表示的系统为一随机聚散服务系统。任一排队系统都是一个随机聚散服务系统。“聚”表示顾客的到达，“散”表示顾客的离去。面对拥挤现象，人们总是希望尽量设法减少排队，通常的做法是增加服务设施。但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费。如果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响。前言顾客排队时间的长短与服务设施规模的大小，就构成了设计随机服务系统中的一对矛盾。如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾。这就是随机服务系统理论——排队论所要研究解决的问题。前言排队结构服务机构顾客源顾客到达排队规则服务规则离去图1排队系统示意图一、排队系统的组成与特征排队系统一般有三个基本组成部分：1.输入过程；2.排队规则；3.服务机构。§1排队系统的基本概念输入即为顾客的到达，可能有下列情况：1）顾客源可能是有限的，也可能是无限的。2）顾客是成批到达或是单个到达。3）顾客到达间隔时间可能是随机的或确定的。4）顾客到达可能是相互独立或关联的。所谓独立就是以前顾客的到达对以后顾客的到达无影响。5）输入过程可以是平稳的（stationary）或说是对时间齐次的（Homogeneousintime），也可以是非平稳的。输入过程平稳的指顾客相继到达的间隔时间分布和参数（均值、方差）与时间无关；非平稳的则是与时间相关，非平稳的处理比较困难。1.输入过程排队规则指服务台从队列中选取顾客进行服务的顺序。可以分为损失制、等待制、混合制3大类。(1)损失制。这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为损失制。2.排队规则(2)等待制。指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。例如，排队等待售票，故障设备等待维修等。等待制中，服务台在选择顾客进行服务时，常有如下四种规则：①先到先服务（FCFS）。按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形。②后到先服务（LCFS）。仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。2.排队规则③随机服务（RAND）。即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。④优先权服务（PR）。如老人、儿童先进车站；危重病员先就诊；遇到重要数据需要处理计算机立即中断其他数据的处理等，均属于此种服务规则。2.排队规则(3)混合制．这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：①队长有限。当排队等待服务顾客人数超过规定数量时，后来顾客就自动离去，另求服务。如水库的库容、旅馆的