数学建模排队论2课件

定义：定义：设设 为一个随机过程，若为一个随机过程，若N(tN(t)的概率分的概率分布具有以下性质：布具有以下性质：(1)(1)假设假设N(tN(t)=n)=n，则从时刻则从时刻t t到下一个顾客到下一个顾客到达到达时刻止的时间服从参数为时刻止的时间服从参数为 的负指数分布；的负指数分布；(2)(2)假设假设N(tN(t)=n)=n，则从时刻则从时刻t t到下一个顾客到下一个顾客离开离开时刻止的时间服从参数为时刻止的时间服从参数为 的负指数分布；的负指数分布；(3)(3)同一时刻是只有一个同一时刻是只有一个 顾客到达或离去。顾客到达或离去。则称则称 为一个为一个生灭过程生灭过程。二、生灭二、生灭过程过程1 10 0nn-1n+1平稳生灭过程系统状态平稳生灭过程系统状态n n平衡方程：平衡方程：“流入流入=流出流出”系统达到平稳状态时：系统达到平稳状态时：的分布的分布系统达到平稳状态时：系统达到平稳状态时：其中其中平衡方程：平衡方程：当当 收敛时才有意义收敛时才有意义 已知已知:顾客到达间隔时间分布顾客到达间隔时间分布,服务时间分布服务时间分布.求求:队长队长:Ls-系统中的顾客数系统中的顾客数.排队长排队长(队列长队列长):Lq-队列中的顾客数队列中的顾客数.Ls=Lq +正在接受服务的顾客数正在接受服务的顾客数逗留时间逗留时间:W s-顾客在系统中的停留时间顾客在系统中的停留时间 等待时间等待时间:Wq-顾客在队列中的等待时间顾客在队列中的等待时间.Ws=Wq+服务时间服务时间忙期忙期,损失率损失率,服务强度服务强度.排队问题的求解排队问题的求解三三.单服务台负指数分布单服务台负指数分布排队系统分析排队系统分析 1 1、M/M/1M/M/1模型模型2 2、M/M/1/N/M/M/1/N/模型模型(即系统的容量有限即系统的容量有限)3 3、M/M/1/m M/M/1/m 模型（即顾客源为有限）模型（即顾客源为有限）顾客源顾客源排队系统排队系统排队排队结构结构服务服务机构机构排队规则服务规则服务规则接受接受服务服务后离去后离去1 1、M/M/1M/M/1模型模型无无限限输入过程服从输入过程服从参数为参数为 的的负指数分布负指数分布单队单队队长无限队长无限先到先服务先到先服务服务时间服从服务时间服从参数为参数为 的的负指数分布负指数分布生灭过程生灭过程7 1、标准型：、标准型：M/M/1(M/M/1/）8 1、标准型：、标准型：M/M/1(M/M/1/）n关于 的几点说明：顾客平均到达率顾客平均到达率顾客平均服务率顾客平均服务率一个顾客服务时间一个顾客服务时间一个顾客到达时间一个顾客到达时间服务强度服务强度即顾客的顾客平均到达率即顾客的顾客平均到达率小于顾客平均服务率时，小于顾客平均服务率时，系统才能达到统计平稳。系统才能达到统计平稳。系统中至少有系统中至少有一个顾客的概一个顾客的概率；率；服务台处于忙服务台处于忙的状态的概率；的状态的概率；反映系统繁忙反映系统繁忙程度程度（2 2）系统的运行指标）系统的运行指标 1、标准型：、标准型：M/M/1(M/M/1/）10（2 2）系统的运行指标）系统的运行指标 1、标准型：、标准型：M/M/1(M/M/1/）11（3）运行指标之间的关系这公式很重要，一定要记清楚！1、标准型：、标准型：M/M/1(M/M/1/）12n平均忙期 B,忙期出现的概率n平均闲期 I,闲期出现的概率(1-)n忙期 B:闲期 I=:(1-)n平均闲期 I=1/闲期的分布与顾客到闲期的分布与顾客到达时间间隔的相同达时间间隔的相同-服从参数为服从参数为 的负的负指数分布指数分布计算有关指标计算有关指标n忙期与闲期忙期与闲期 1-P0=n平均忙期平均忙期 B,忙期出现的概率忙期出现的概率 n平均闲期平均闲期 I,闲期出现的概率闲期出现的概率(1-)n忙期忙期 B:闲期闲期 I=:(1-)n平均闲期平均闲期 I=1/n平均忙期平均忙期 B=(/(1-)/=1/(-)计算有关指标计算有关指标n忙期与闲期忙期与闲期 与逗留时间与逗留时间WsWs相同相同!?例：某医院手术室每小时就诊病人数和手术例：某医院手术室每小时就诊病人数和手术 时间的记录如下：时间的记录如下：到达的病人数到达的病人数 出现次数出现次数 n un 0 10 1 28 2 29 3 16 4 10 5 6 6 以上以上 1 合计合计 100完成手术时间完成手术时间 出现次数出现次数 r vr 0.00.2 38 0.20.4 25 0.40.6 17 0.60.8 9 0.81.0 6 1.01.2 5 1.2 以上以上 0 合计合计 100n解：到达的病人数 出现次数 n un 0 10 1 28 2 29 3 16 4 10 5 6 6 以上 1 合计 100每小时病人平均到达率每小时病人平均到达率（人（人/小时）小时）n解：到达的病人数 出现次数 n un 0 10 1 28 2 29 3 16 4 10 5 6 6 以上 1 合计 100每小时病人平均到达率每小时病人平均到达率（人（人/小时）小时）每次手术平均时间每次手术平均时间（小时（小时/人）人）每小时完成手术人数每小时完成手术人数（平均服务率）（平均服务率）（人（人/小时）小时）完成手术时间完成手术时间 出现次数出现次数 r vr 0.00.2 38 0.20.4 25 0.40.6 17 0.60.8 9 0.81.0 6 1.01.2 5 1.2 以上以上 0 合计合计 100解：N321顾客源顾客源.队列离去离去（容量有限的单服务台的排队系统）（容量有限的单服务台的排队系统）被拒绝被拒绝2、系统的容量有限制：、系统的容量有限制：M/M/1/N/192024年年6月月25日日2 2 系统容量有限制的情形系统容量有限制的情形 (M/M/1/N/FCFSM/M/1/N/FCFS）n状态转移图n状态转移方程N-1N2、系统的容量有限制：、系统的容量有限制：M/M/1/N/212024年年6月月25日日2、系统的容量有限制：、系统的容量有限制：M/M/1/N/系统的运行指标系统的运行指标:222024年年6月月25日日2、系统的容量有限制：、系统的容量有限制：M/M/1/N/系统的运行指标系统的运行指标:232024年年6月月25日日 顾客总体有顾客总体有m个顾客，实际上系统中顾客数永个顾客，实际上系统中顾客数永不会超过不会超过m，即与模型即与模型M/M/1/m/m的意义相同。的意义相同。321顾客源顾客源队列离去离去顾客源有限的单服务台的排队系统顾客源有限的单服务台的排队系统m个3、顾客源为有限的：、顾客源为有限的：M/M/1/m242024年年6月月25日日3、顾客源为有限的：、顾客源为有限的：M/M/1/m系统状系统状态概率态概率的平衡的平衡方程：方程：252024年年6月月25日日3、顾客源为有限的：、顾客源为有限的：M/M/1/m262024年年6月月25日日 等待时间等待时间正常运转的平均设备台数正常运转的平均设备台数计算有关指标计算有关指标282024年年6月月25日日 研究单队、并列的研究单队、并列的c 个服务台的情形，主要有个服务台的情形，主要有三种形式：三种形式：（1）标准型：）标准型：M/M/c/（2）系统容量有限的：）系统容量有限的：M/M/c/N/（3）顾客源有限的）顾客源有限的：M/M/c/m321顾客源顾客源离离去去标准的标准的c个服务台的排队系统个服务台的排队系统 C个队列四、多服务台负指数分布排队系统四、多服务台负指数分布排队系统292024年年6月月25日日四、多服务台负指数分布排队系统四、多服务台负指数分布排队系统1、标准型：、标准型：M/M/c/302024年年6月月25日日（1 1）系统的各状态转移关系图：）系统的各状态转移关系图：系统状态系统状态概率平衡概率平衡方程：方程：1、标准型：、标准型：M/M/c/312024年年6月月25日日思考题：思考题：一个一个M/M/c/系系统与统与c个个M/M/1/系统比系统比较哪一个效率高？较哪一个效率高？1、标准型：、标准型：M/M/c/322024年年6月月25日日1、标准型：、标准型：M/M/c/（2）系统的运行指标）系统的运行指标332024年年6月月25日日2、系统容量有限制：、系统容量有限制：M/M/c/N/N321顾客源顾客源离离去去容量有限的容量有限的c个服务台的排队系统个服务台的排队系统 C个队列客满拒客满拒绝进入绝进入342024年年6月月25日日2、系统容量有限制：、系统容量有限制：M/M/c/N/系统状态系统状态概率平衡概率平衡方程：方程：352024年年6月月25日日2、系统容量有限制：、系统容量有限制：M/M/c/N/362024年年6月月25日日3、顾客源为有限的：、顾客源为有限的：M/M/c/m321顾客源顾客源离开顾客源有限顾客源有限c个服务台的排队系统个服务台的排队系统 C个队列m个372024年年6月月25日日3、顾客源为有限的：、顾客源为有限的：M/M/c/m 类似地还有类似地还有M/M/M/M/c/N/mc/N/m,M/M/,M/M/c/m/mc/m/m,M/M/M/M/c/c/mc/c/m 等等情况，可作相应的讨论。情况，可作相应的讨论。3、顾客源为有限的：、顾客源为有限的：M/M/c/m382024年年6月月25日日 某售票所有三某售票所有三个窗口，顾客到达个窗口，顾客到达服从服从Poisson过程，过程，到达到达 =0.9 人人/分分钟，服务钟，服务 =0.4人人/分钟。设顾客到分钟。设顾客到达后依次排成一队达后依次排成一队向空闲的窗口购票，向空闲的窗口购票，如图如图 a.图图 a 窗口窗口1 =0.4 窗口窗口2 =0.4 窗口窗口3 =0.4 =0.9M/M/cM/M/c型系统和型系统和型系统和型系统和c c个个个个M/M/1M/M/1型系统的比较型系统的比较型系统的比较型系统的比较图图 aM/M/cM/M/c型系统和型系统和型系统和型系统和c c个个个个M/M/1M/M/1型系统的比较型系统的比较型系统的比较型系统的比较 窗口窗口1 =0.4 窗口窗口2 =0.4 窗口窗口3 =0.4 =0.3 =0.3 =0.3 =0.9图图 b 窗口窗口1 =0.4 窗口窗口2 =0.4 窗口窗口3 =0.4 =0.9 以上例说明以上例说明,设顾客设顾客到达后在每个窗口前各到达后在每个窗口前各排一队排一队(其它条件不变其它条件不变),),共三队共三队,每队平均到每队平均到达率为达率为:窗口窗口1 =0.4 窗口窗口2 =0.4 窗口窗口3 =0.4 =0.3 =0.3 =0.3 =0.9图图 bM/M/cM/M/c型系统和型系统和型系统和型系统和c c个个个个M/M/1M/M/1型系统的比较型系统的比较型系统的比较型系统的比较 模模模模型型型型指标指标指标指标 M/M/3 M/M/33 3个个个个(M/M/1)M/M/1)P P0 0L Lq qL Ls sWWs sWWq q必须等待概率必须等待概率必须等待概率必须等待概率0.07480.07481.701.703.953.954.39 4.39(分钟分钟分钟分钟)1.89 1.89(分钟分钟分钟分钟)0.570.570.25 0.25(子系统子系统子系统子系统)2.25 2.25(子子子子)9.00 9.00(整整整整)10 10(分钟分钟分钟分钟)7.5 7.5(分钟分钟分钟分钟)0.750.75结果比较结果比较M/M/cM/M/c型系统和型系统和型系统和型系统和c c个个个个M/M/1M/M/1型系统的比较型系统的比较型系统的比较型系统的比较2 标准的标准的 M/M/c/N/模型模型n状态图是多服务台和容量有限的综合状态图是多服务台和容量有限的综合n平衡方程平衡方程你会你会吗吗?1 1 排队系统最优化问题排队系统最优化问题排队系统最优化问题排队系统最优化问题2 2 M/M/1M/M/1模型中最优服务率模型中最优服务率模型中最优服务率模型中最优服务率3 3 M/M/c M/M/c 模型中最优服务台数模型中最优服务台数模型中最优服务台数模型中最优服务台数c c四四.经济分析经济分析排队系统的最优化排队系统的最优化n系统设计最优化：系统设计最优化：(静态优化问题静态优化问题)设备达到最大效益设备达到最大效益n系统控制最优化：系统控制最优化：(动态优化问题动态优化问题)如何运营使某个目如何运营使某个目标函数最优。标函数最优。1 排队系统最优化问题服务水平服务水平总费用总费用等待费用等待费用服务费用服务费用费费用用极小点极小点2 M/M/1模型中最优服务率模型中最优服务率单位时间的费用单位时间的费用Cs：当 时服务机构单位时间费用Cw：每个顾客在系统停留单位时间的费用标准的标准的标准的标准的/M/M/1M/M/1模型模型模型模型单位时间的纯利润单位时间的纯利润G：每服务每服务1人可得的收入（已知）人可得的收入（已知）标准的标准的标准的标准的/M/M/1/NM/M/1/N模型模型模型模型2 M/M/1模型中最优服务率模型中最优服务率2 M/M/1模型中最优服务率模型中最优服务率单位时间的纯利润单位时间的纯利润G：单位时间每台机器运转可得的收入单位时间每台机器运转可得的收入标准的标准的标准的标准的/M/M/1/M/M/1/m/m模模模模型型型型3 M/M/c 模型中最优服务台数模型中最优服务台数c边际分析法：因为边际分析法：因为 z(c*)最小，所以有：最小，所以有：每：每服务台单位时间成本服务台单位时间成本 ：顾客在系统停留单位时间的费用顾客在系统停留单位时间的费用单位时间总成本单位时间总成本3 M/M/c 模型中最优服务台数模型中最优服务台数c代入代入 z 表达式中得：表达式中得：依次求依次求c 1、2、3、的的L值，并作两相邻的值，并作两相邻的值之差，根据这个差落在哪个不等式区间里就可值之差，根据这个差落在哪个不等式区间里就可定出定出最优最优 c 值。值。化简得：化简得：