运筹学课件排队论

《运筹学课件排队论》由会员分享，可在线阅读，更多相关《运筹学课件排队论（78页珍藏版）》请在金锄头文库上搜索。

1、Page:1QSC 华东理工大学 工商经济学院运筹学运 筹 学排 队 论Page:2QSC 华东理工大学 工商经济学院运筹学Where the Time Goes美国人一生中平均要花费- 6年 吃5年 排队等待4年 做家务2年 回电话不成功 1年 寻找放置不当的物品8个月 打开邮寄广告6个月 停在红灯前Page:3QSC 华东理工大学 工商经济学院运筹学排队系统的基本特征离开排队规则到达过程排队结构服务过程退出离开需求 群体Page:4QSC 华东理工大学 工商经济学院运筹学商业服务系统系统类型顾客服务台理发店人理发师银行出纳服务人出纳ATM机服务人ATM机商店收银台人收银员管道服务阻塞的管道

2、管道工电影院售票窗口人售票员机场检票处人航空公司代理人经纪人服务人股票经纪人Page:5QSC 华东理工大学 工商经济学院运筹学内部服务系统系统类型顾客服务台秘书服务雇员秘书复印服务雇员复印机计算机编程服务雇员程序员大型计算机雇员计算机急救中心雇员护士传真服务雇员传真机物料处理系统货物物料处理单元维护系统设备维修工人质检站物件质检员Page:6QSC 华东理工大学 工商经济学院运筹学运输服务系统系统类型顾客服务台公路收费站汽车收费员卡车装货地卡车装货工人港口卸货区轮船卸货工人等待起飞的飞机飞机跑道航班服务人飞机出租车服务人出租车电梯服务人电梯消防部门火灾消防车停车场汽车停车空间急救车服务人急救

3、车Page:7QSC 华东理工大学 工商经济学院运筹学到达过程静态动态预约定价接受/拒绝不加入排队退出排队恒定到达率 的随机到达变动到达率 的随机到达由设施控制顾客控制到达过程Page:8QSC 华东理工大学 工商经济学院运筹学到达过程的内容顾客总体数或顾客源数有限或无限顾客的到达类型单个或成批顾客的到达间隔时间间隔时间分布Page:9QSC 华东理工大学 工商经济学院运筹学排队结构领号多条队列有限队长有限队长有限或 无限队长快速通道排队结构单一队列允许或 不允许移动Page:10QSC 华东理工大学 工商经济学院运筹学排队结构-例多队多服务台领号 348261012 1157 9单队多服务台

4、入口 Page:11QSC 华东理工大学 工商经济学院运筹学排队规则排队规则静态 (FCFS 规则) (LCFS 规则) .动态基于排队 状况选择即与特定顾 客特征选择等待的 顾客数协商优先级强占顾客服务时间 (SPT 规则)Page:12QSC 华东理工大学 工商经济学院运筹学排队规则的内容损失制系统 服务台被占用时新到的顾客将离开等待制系统 FCFS LCFS RS PR混合制系统损失制与等待制的混合Page:13QSC 华东理工大学 工商经济学院运筹学服务过程服务过程静态服务过程动态服务过程自我服务机械速度不同的服务率开关服务通道Page:14QSC 华东理工大学 工商经济学院运筹学服务

5、过程的内容服务台数量单个或多个每次服务顾客的数量单个或成批服务顾客的时间分布时间分布Page:15QSC 华东理工大学 工商经济学院运筹学常用的记号n 系统中的顾客数 平均到达率，即单位时间内平均到达的顾客数 平均服务率，即单位时间内服务完毕的顾客数Sn(t) 时刻t系统中有n个顾客Pn(t) 时刻t系统状态Sn(t) 的概率C 服务台的个数M 顾客相继到达的时间间隔服从负指数分布D 顾客相继到达的时间间隔服从定长分布Ek 顾客相继到达的时间间隔服从k阶Erlang分布Page:16QSC 华东理工大学 工商经济学院运筹学排队系统的符号表示 一个排队系统的特征可以用六个参数表示， 形式为：AB

6、C：def其中 A 顾客到达的概率分布，可取M、D、Ek等； B 服务时间的概率分布，可取M、D、Ek等； C 服务台个数，取正整数； d 排队系统的最大容量，可取正整数或； e 顾客源的最大容量，可取正整数或； f 排队规则，可取FCFS、LCFS等。Page:17QSC 华东理工大学 工商经济学院运筹学M/M/1：/FCFS表示：顾客到达的时间间隔是负指数分布服务时间是负指数分布一个服务台排队系统和顾客源的容量都是无限实行先到先服务的一个服务系统 Page:18QSC 华东理工大学 工商经济学院运筹学顾客到达和服务的时间分布 Page:19QSC 华东理工大学 工商经济学院运筹学Poiss

7、on流（Poisson过程 ） 定义 满足以下四个条件的输入流称为Poisson流（Poisson过程）1、平稳性：在时间区间t, t+t)内到达k个顾客的概率与t无关，只与t有 关。记为pk(t）。2、无后效性：不相交的时间区间内到达的顾客数互相独立。3、普通性：设在t, t+t）内到达多于一个顾客的概率为q(t），则q(t)=o(t)即4、有限性：任意有限个区间内到达有限个顾客的概率等于一。即Page:20QSC 华东理工大学 工商经济学院运筹学Poisson流与Poisson分布定理 对于一个参数为的Poisson流，在0，t内 到达k个顾客的概率为即服从以为参数的Poisson分布。

8、= 1= 3= 7Pk(1)x.4.3.2.10Page:21QSC 华东理工大学 工商经济学院运筹学Poisson流与负指数分布之间的关系 定理 在排队系统中，如果单位时间内顾客到达数服从以为参数的Poisson分布，则顾客相继到达的时间间隔服从以为参数的负指数分布。 =0.41/为平均到达间隔时间Page:22QSC 华东理工大学 工商经济学院运筹学k阶Erlang分布 定理 设v1，v2，vk是k个互相独立的，具有相同参数的负指数分布随机变量，则随机变量S=v1+v2+vk服从k阶Erlang分布，S的密度函数为=1k=1k=2k=4k=8Page:23QSC 华东理工大学 工商经济学院

9、运筹学系统绩效度量 系统总的平均顾客数L 平均等待顾客个数Lq 包括服务的平均等待时间W 平均顾客等待时间Wq 系统利用率rPage:24QSC 华东理工大学 工商经济学院运筹学基本排队模型 M/M/1:/FCFS 顾客到达的时间间隔是负指数分布服务时间是负指数分布一个服务台排队系统和顾客源的容量都是无限实行先到先服务的一个服务系统Page:25QSC 华东理工大学 工商经济学院运筹学M/M/1:/FCFS的分析假设在t+t时刻系统中顾客数为n的概率Pn(t+t) SnSnSn+1Sn-1 SnPn(t)Pn-1(t)Pn+1(t)Pn(t)t时刻t +t时刻无到达，无离开无到达，离开一个到达

10、一个，无离开到达一个，离开一个Page:26QSC 华东理工大学 工商经济学院运筹学Page:27QSC 华东理工大学 工商经济学院运筹学系统的过渡状态与稳定状态过渡稳定Page:28QSC 华东理工大学 工商经济学院运筹学稳定状态下的状态概率Page:29QSC 华东理工大学 工商经济学院运筹学得到 令称为服务强度，则得Page:30QSC 华东理工大学 工商经济学院运筹学M/M/1:/FCFS的状态转移分析 012n-1nn+1Page:31QSC 华东理工大学 工商经济学院运筹学例高速公路入口收费处设有一个收费通道，汽车到 达服从Poisson分布，平均到达速率为100辆小时 ，收费时间

11、服从负指数分布，平均收费时间为15 秒辆。求1、收费处空闲的概率；2、收费处忙的概率；3、系统中分别有1，2，3辆车的概率。Page:32QSC 华东理工大学 工商经济学院运筹学解根据题意, =100辆/小时,1/=15秒=1/240（小时/辆）,即240（辆/小时） 。因此，=/=100/240=5/12。系统空闲的概率为：P0=1-=1-(5/12)=7/12=0.583系统忙的概率为：1-P0=1-(1-)=5/12=0.417系统中有1辆车的概率为：P1=(1-)=0.4170.583=0.243系统中有2辆车的概率为：P2=2(1-)=0.417 20.583=0.101系统中有3辆

12、车的概率为：P3=3(1-)=0.417 30.583=0.0421Page:33QSC 华东理工大学 工商经济学院运筹学Little公式 Page:34QSC 华东理工大学 工商经济学院运筹学M/M/1:/FCFS的系统指标系统中的平均顾客数L 队列中的平均顾客数Lq Page:35QSC 华东理工大学 工商经济学院运筹学顾客在系统中的平均逗留时间W 顾客在队列中的平均逗留时间Wq Page:36QSC 华东理工大学 工商经济学院运筹学例高速公路入口收费处设有一个收费通道，汽车到 达服从Poisson分布，平均到达速率为200辆/小时 ，收费时间服从负指数分布，平均收费时间为15 秒/辆。求

13、L、Lq、W和Wq。Page:37QSC 华东理工大学 工商经济学院运筹学解根据题意，=200辆/小时，=240辆/小时， =/=5/6。Page:38QSC 华东理工大学 工商经济学院运筹学有限队列模型 M/M/1:N/FCFS 当队列的容量从无限值变为有限值N时， M/M/1:/FCFS就转化成为M/M/1:N/FCFS Page:39QSC 华东理工大学 工商经济学院运筹学系统的状态转移图 012n-1nPage:40QSC 华东理工大学 工商经济学院运筹学系统的状态概率平衡方程对于状态0：P0=P1对于状态k：Pk-1+Pk+1=(+)Pk 0kN对于状态N：PN-1=PNPage:4

14、1QSC 华东理工大学 工商经济学院运筹学系统的状态概率由得到 Page:42QSC 华东理工大学 工商经济学院运筹学系统的运行指标 对于1有Page:43QSC 华东理工大学 工商经济学院运筹学有效到达率 Page:44QSC 华东理工大学 工商经济学院运筹学Little公式Page:45QSC 华东理工大学 工商经济学院运筹学例一个单人理发店，除理发椅外，还有4把椅子可供顾客等候。顾客到达发现没有座位空闲，就不再等待而离去。顾客到达的平均速率为4人/小时，理发的平均时间为10分钟/人。顾客到达服从Poisson流，理发时间服从负指数分布。求：1、顾客到达不用等待就可理发的概率；2、理发店里

15、的平均顾客数以及等待理发的平均顾客数；3、顾客来店理发一次平均花费的时间及平均等待的时间；4、顾客到达后因客满而离去的概率；5、增加一张椅子可以减少的顾客损失率。Page:46QSC 华东理工大学 工商经济学院运筹学解这是一个M/M/1:N/FCFS系统，其中 N=4+1=5，=4人/小时，=6人/小时，=2/3。 Page:47QSC 华东理工大学 工商经济学院运筹学因客满而离去的概率为0.0048 Page:48QSC 华东理工大学 工商经济学院运筹学当N=6时 P5-P6=0.0480-0.0311=0.0169=1.69% 即增加一张椅子可以减少顾客损失率1.69% Page:49QSC 华东理工大学 工商经济学院运筹学M/M/1:/m/FCFS模型设顾客总数为m。当顾客需要服务时，就进入队列等待；服务完毕后，重新回到顾客源中。如此循环往复 。服务台.顾客源需要服务服务完毕队列Page:50QSC 华东理工大学 工商经济学院运筹学分析假定每一个顾客在单位时间内