运筹学-排队论

nullnullWhere the Time GoesWhere the Time Goes美国人一生中平均要花费-- 6年 吃5年 排队等待4年 做家务2年 回电话不成功 1年 寻找放置不当的物品8个月 打开邮寄广告6个月 停在红灯前排队系统的基本特征排队系统的基本特征离开排队规则到达过程排队结构服务过程退出离开需求群体商业服务系统商业服务系统系统类型 顾客 服务台 理发店 人 理发师 银行出纳服务 人 出纳 ATM机服务 人 ATM机 商店收银台 人 收银员 管道服务 阻塞的管道 管道工 电影院售票窗口 人 售票员 机场检票处 人 航空公司代理人 经纪人服务 人 股票经纪人内部服务系统内部服务系统系统类型 顾客 服务台 秘书服务 雇员 秘书 复印服务 雇员 复印机 计算机编程服务 雇员 程序员 大型计算机 雇员 计算机 急救中心 雇员 护士 传真服务 雇员 传真机 物料处理系统 货物 物料处理单元 维护系统 设备 维修工人 质检站 物件 质检员运输服务系统运输服务系统系统类型 顾客 服务台 公路收费站 汽车 收费员 卡车装货地 卡车 装货工人 港口卸货区 轮船 卸货工人 等待起飞的飞机 飞机 跑道 航班服务 人 飞机 出租车服务 人 出租车 电梯服务 人 电梯 消防部门 火灾 消防车 停车场 汽车 停车空间 急救车服务 人 急救车到达过程到达过程到达过程的内容到达过程的内容顾客总体数或顾客源数 有限或无限 顾客的到达类型 单个或成批 顾客的到达间隔时间 间隔时间分布排队结构排队结构排队结构-例排队结构-例排队规则排队规则排队规则的内容排队规则的内容损失制系统 服务台被占用时新到的顾客将离开 等待制系统 FCFS LCFS RS PR 混合制系统 损失制与等待制的混合服务过程服务过程服务过程静态服务过程动态服务过程 自我服务机械速度不同的服务率开关服务通道服务过程的内容服务过程的内容服务台数量 单个或多个 每次服务顾客的数量 单个或成批 服务顾客的时间分布 时间分布常用的记号常用的记号n –– 系统中的顾客数  ––平均到达率，即单位时间内平均到达的顾客数  –– 平均服务率，即单位时间内服务完毕的顾客数 Sn(t) ––时刻t系统中有n个顾客 Pn(t) –– 时刻t系统状态Sn(t) 的概率 C –– 服务台的个数 M –– 顾客相继到达的时间间隔服从负指数分布 D –– 顾客相继到达的时间间隔服从定长分布 Ek –– 顾客相继到达的时间间隔服从k阶Erlang分布排队系统的符号 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示 排队系统的符号表示 一个排队系统的特征可以用六个参数表示，形式为： [A／B／C]：[d／e／f]其中 A–– 顾客到达的概率分布，可取M、D、Ek等； B–– 服务时间的概率分布，可取M、D、Ek等； C –– 服务台个数，取正整数； d–– 排队系统的最大容量，可取正整数或； e –– 顾客源的最大容量，可取正整数或； f –– 排队规则，可取FCFS、LCFS等。null[M/M/1]：[//FCFS] 表示： 顾客到达的时间间隔是负指数分布 服务时间是负指数分布 一个服务台 排队系统和顾客源的容量都是无限 实行先到先服务的一个服务系统 顾客到达和服务的时间分布 顾客到达和服务的时间分布 Poisson流（Poisson过程） Poisson流（Poisson过程） 定义 满足以下四个条件的输入流称为Poisson流（Poisson过程） 1、平稳性：在时间区间[t, t+t)内到达k个顾客的概率与t无关，只与t有关。记为pk(t）。 2、无后效性：不相交的时间区间内到达的顾客数互相独立。 3、普通性：设在[t, t+t）内到达多于一个顾客的概率为q(t），则 q(t)=o(t) 即 4、有限性：任意有限个区间内到达有限个顾客的概率等于一。即Poisson流与Poisson分布Poisson流与Poisson分布定理 对于一个参数为的Poisson流，在[0，t]内到达k个顾客的概率为 即服从以为参数的Poisson分布。 Poisson流与负指数分布之间的关系 Poisson流与负指数分布之间的关系 定理 在排队系统中，如果单位时间内顾客到达数服从以为参数的Poisson分布，则顾客相继到达的时间间隔服从以为参数的负指数分布。 l=0.41/为平均到达间隔时间k阶Erlang分布 k阶Erlang分布 定理 设v1，v2，…，vk是k个互相独立的，具有相同参数的负指数分布随机变量，则随机变量 S=v1+v2+…+vk 服从k阶Erlang分布，S的密度函数为系统绩效度量系统绩效度量 系统总的平均顾客数L 平均等待顾客个数Lq 包括服务的平均等待时间W 平均顾客等待时间Wq 系统利用率r基本排队模型 [M/M/1]:[//FCFS] 基本排队模型 [M/M/1]:[//FCFS] 顾客到达的时间间隔是负指数分布 服务时间是负指数分布 一个服务台 排队系统和顾客源的容量都是无限 实行先到先服务的一个服务系统[M/M/1]:[//FCFS]的分析[M/M/1]:[//FCFS]的分析 假设在t+t时刻系统中顾客数为n的概率Pn(t+t) SnSnSn+1Sn-1SnPn(t)Pn-1(t)Pn+1(t)Pn(t)t时刻t +t时刻无到达，无离开无到达，离开一个到达一个，无离开到达一个，离开一个null系统的过渡状态与稳定状态系统的过渡状态与稳定状态稳定状态下的状态概率稳定状态下的状态概率null得到 令 称为服务强度，则得[M/M/1]:[//FCFS]的状态转移分析[M/M/1]:[//FCFS]的状态转移分析例例高速公路入口收费处设有一个收费通道，汽车到达服从Poisson分布，平均到达速率为100辆／小时，收费时间服从负指数分布，平均收费时间为15秒／辆。求 1、收费处空闲的概率； 2、收费处忙的概率； 3、系统中分别有1，2，3辆车的概率。 解解根据题意, =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.417×0.583=0.243 系统中有2辆车的概率为： P2=2(1-)=0.417 2×0.583=0.101 系统中有3辆车的概率为： P3=3(1-)=0.417 3×0.583=0.0421Little公式 Little公式 [M/M/1]:[//FCFS]的系统指标[M/M/1]:[//FCFS]的系统指标系统中的平均顾客数L 队列中的平均顾客数Lq null顾客在系统中的平均逗留时间W 顾客在队列中的平均逗留时间Wq 例例 高速公路入口收费处设有一个收费通道，汽车到达服从Poisson分布，平均到达速率为200辆/小时，收费时间服从负指数分布，平均收费时间为15秒/辆。求L、Lq、W和Wq。 解解根据题意，=200辆/小时，=240辆/小时，=/=5/6。有限队列模型 [M/M/1]:[N//FCFS] 有限队列模型 [M/M/1]:[N//FCFS] 当队列的容量从无限值变为有限值N时，[M/M/1]:[//FCFS]就转化成为[M/M/1]:[N//FCFS] 系统的状态转移图 系统的状态转移图 系统的状态概率平衡方程系统的状态概率平衡方程对于状态0： P0=P1 … … 对于状态k： Pk-1+Pk+1=(+)Pk 0 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 的[M/M/c]:[∞/∞/FCFS]模型 系统容量有限的[M/M/c]:[N/∞/FCFS]模型 有限顾客源的[M/M/c]:[∞/m/FCFS]模型 [M/M/c]:[∞/∞/FCFS]模型 [M/M/c]:[∞/∞/FCFS]模型 顾客到达后，进入队列尾端；当某一个服务台空闲时，队列中的第一个顾客即到该服务台接收服务；服务完毕后随即离去。各服务台互相独立且服务速率相同，即μ1=μ2=…=μc 分析分析系统的服务速率与系统中的顾客数有关。当系统中的顾客数k不大于服务台个数，即1≤k≤c时，系统中的顾客全部在服务台中，这时系统的服务速率为kμ；当系统中的顾客数k＞c时，服务台中正在接受服务的顾客数仍为c个，其余顾客在队列中等待服务，这时系统的服务速率为cμ。 则当ρ＜1时系统才不会排成无限的队列 状态转移图与状态转移方程状态转移图与状态转移方程对状态0: λP0=μP1 对状态1: λP0+2μP2=(λ+μ)P1 ………… 对状态c： λPc-1+cμPc+1=(λ+cμ)Pc ………… 对状态n λPn-1+cμPn+1=(λ+cμ)Pn ………状态概率状态概率运行指标 运行指标 例例某售票处有三个窗口，顾客到达服从Poisson流，到达速率为0.9人／分，售票时间服从负指数分布，每个窗口的平均售票速率为0.4人／分。顾客到达后排成一队，依次到空闲窗口购票。求： (1)所有窗口都空闲的概率； (2)平均队长； (3)平均等待时间及逗留时间； (4)顾客到达后必须等待的概率。解解λ/μ=2.25，ρ=λ/cμ=0.75 (1)所有窗口都空闲的概率，即求P0的值 (2)平均队长，即求L的值，必须先求Lq null(3)平均等待时间和平均逗留时间，即求Wq和W和的值 (4)顾客到达后必须等待，即n≥3 [M/M/c]:[N/∞/FCFS]模型 [M/M/c]:[N/∞/FCFS]模型 分析分析设系统容量为N(N≥c)，当系统中的顾数n＜N时，到达的顾客就进入系统；当n=N时，到达的顾客就被拒绝。设顾客到达的速率为λ，m每个服务台服务的速率为μ，ρ=λ/cμ。由于系统不会无限止地接纳顾客，对ρ不必加以限制。 状态转移图与状态转移方程状态转移图与状态转移方程对状态0: λP0=μP1 对状态1: λP0+2μP2=(λ+μ)P1 ………… 对状态c： λPc-1+cμPc+1=(λ+cμ)Pc ………… 对状态N λPN-1=cμPN ………状态概率状态概率运行指标 运行指标 例例某旅馆有8个单人房间，旅客到达服从Poisson流，平均速率为6人／天，旅客平均逗留时间为2天，求： (1)每天客房平均占用数； (2)旅馆客满的概率。 解解旅馆8个房间全满的概率为0.423 平均占用客房数为6.9间。客房占用率为86.6% [M/M/c]:[∞/m/FCFS]模型 [M/M/c]:[∞/m/FCFS]模型 状态概率 状态概率 其中 运行指标运行指标效到达速率λe为单位时间内出现故障的机器数，有 λe=λ(m-L) 例例车间有5台机器，每台机器的故障率为1次／小时，有2个修理工负责修理这5台机器，工作效率相同，为4台／小时。求： (1)等待修理的平均机器数； (2)等待修理及正在修理的平均机器数； (3)每小时发生故障的平均机器数； (4)平均等待修理的时间； (5)平均停工时间。解 解 可以计算得到（算式略）： P1=0.394，P2=0.197，P3=0.074，P4=0.018，P5=0.002 null由此，计算系统的各项运行指标如下：排队系统的优化排队系统的优化一般排队系统的总费用构成：总费用=服务能力费+顾客损失费[M/M/1]:[∞ /∞/FCFS]模型的μ[M/M/1]:[∞ /∞/FCFS]模型的μnull[M/M/c]:[∞ /∞/FCFS]模型的c[M/M/c]:[∞ /∞/FCFS]模型的cnull排队系统的优化排队系统的优化一般排队系统的总费用构成：总费用=服务能力费+顾客损失费[M/M/1]:[∞ /∞/FCFS]模型的μ[M/M/1]:[∞ /∞/FCFS]模型的μnull[M/M/c]:[∞ /∞/FCFS]模型的c[M/M/c]:[∞ /∞/FCFS]模型的cnull