2011数学建模排队论知识讲稿.ppt

数学建模之;1. CUMCM 的历年赛题浏览：;1. CUMCM 的历年赛题浏览：;1. CUMCM 的历年赛题浏览：;1. CUMCM 的历年赛题浏览;2、从问题的实际意义分析;3、从问题的解决方法上分析; 用的最多的方法是优化方法和概率统计的方法. 用到优化方法的共有22个题，占总数的68.8%，其中整数规划4个，线性规划6个，非线性规划14个,多目标规划6个。 用到概率统计方法的有16个题，占50%，平均每年至少有一个题目用到概率统计的方法。 用到图论与网络优化方法的问题有6个； 用到层次分析方法的问题有３个；;两个引例：问题1:校园网的设计和调节收费问题;问题1:校园网的设计和调节收费问题;问题1:校园网的设计和调节收费问题;问题1:校园网的设计和调节收费问题;问题2:眼科病床的合理安排问题 09B;问题2:眼科病床的合理安排问题 09B;问题2:眼科病床的合理安排问题 09B;;排队论(Queuing Theory);排队论; 排队是我们在日常生活和生产中经常遇到的现象。 例如，上、下班搭乘公共汽车；顾客到商店购买物品；病员到医院看病；旅客到售票处购买车票；学生去食堂就餐等就常常出现排队和等待现象。; 除了上述有形的排队之外，还有大量的所谓“无形”排队现象。 如几个顾客打电话到出租汽车站要求派车，如果出租汽车站无足够车辆、则部分顾客只得在各自的要车处等待，他们分散在不同地方，却形成了一个无形队列在等待派车。 ; 排队的不一定是人，也可以是物： 例如，通讯卫星与地面若干待传递的信息； 生产线上原料、半成品等待加工； 因故障停止运转的机器等待修理；码头的船只等待装卸货物； 要降落的飞机因跑道不空而在空中盘旋等等。; 上述各种问题虽互不相同，但却都有要求得到某种服务的人或物和提供服务的人或机构。 排队论里把要求服务的对象统称为“顾客”, 提供服务的人或机构称为“服务台”或“服务员”。;图1 单服务台排队系统（去代售点买火车票）;图2 单队列——S个服务台并联的排队系统（找工作）;图4 单队——多个服务台的串联排队系统（报名）;图6 随机服务系统; 面对拥挤现象，人们总是希望尽量设法减少排队，通常的做法是增加服务设施。 但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费。 如果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响。; 顾客排队时间的长短与服务设施规模的大小，就构成了设计随机服务系统中的一对矛盾。 如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾。 这就是随机服务系统理论——排队论所要研究解决的问题。;一、排队系统的组成与特征 排队系统一般有三个基本组成部分：1.输入过程；2.排队规则；3.服务机构。; 输入即为顾客的到达，可能有下列情况： 1）顾客源可能是有限的，也可能是无限的。 2）顾客是成批到达或是单个到达。 3）顾客到达间隔时间可能是随机的或确定的。 4）顾客到达可能是相互独立或关联的。所谓独立就是以前顾客的到达对以后顾客的到达无影响。 5）输入过程可以是平稳的（stationary）或说是对时间齐次的（Homogeneous in time），也可以是非平稳的。输入过程平稳的指顾客相继到达的间隔时间分布和参数（均值、方差）与时间无关；非平稳的则是与时间相关，非平稳的处理比较困难。;排队规则指服务台从队列中选取顾客进行服务的顺序。 可以分为损失制、等待制、混合制3大类。 (1)损失制。这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。 典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为损失制。; (2)等待制。指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。 例如，排队等待售票，故障设备等待维修等。 等待制中，服务台在选择顾客进行服务时，常有如下四种规则： ①先到先服务（FCFS ）。按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形。 ②后到先服务（LCFS）。仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。; ③随机服务（RAND） 。即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。