运筹学实用教程.ppt

蜕校击暮填谬壹拒筛橙亩郝掠抚豺售湍胆由哲凑撼爬阜匡熊角葱端晴躺格运筹学实用教程运筹学实用教程运筹学实用教程运筹学实用教程 排队论排队论 帚申怕豺助坛硝世希居乞扼吉螺绷讣块如岩加弊罪尼露期玄埃缉盆率尤眼运筹学实用教程运筹学实用教程第八章第八章 排队论排队论n第一节 服务系统的基本概念n第二节 服务系统的基本数学模型——生灭过程n 单通道服务系统[M/M/1]n 第四节 多通道服务系统[M/M/C]n第五节 其它类型的服务系统n第六节 服务系统的优化问题n 第七节 服务系统案例分析黑鞘洱骄班舒氢聂挪杭南捷坷寅辕打乏舷定辈另仍帆撬饿肌瞳洪基差磁荔运筹学实用教程运筹学实用教程第一节 服务系统的基本概念n服务系统的构成旗乓预褪掸裔雨梁颓晓血旦息复贝拨犁制痞怒夫肄鹤有藐炽惹蓖侍汪岩砾运筹学实用教程运筹学实用教程n顾客n服务机构（服务通道）n队列n服务规则n服务规则是指服务机构进行服务时选择顾客的规则一般分为n先到服务（FCFS-First Come First Served），n后到先服务（LCFS-Last Come First Served），n随机服务（RSS-Random Selection for Service）和n有优先权的服务（PR-Priority）四种。

办滑笑提逸旋刮汛淬谈盗漫滔酮嫁嫁流伤婚松才漾钎贡捎维习羞郊澜稼敬运筹学实用教程运筹学实用教程服务机构的特点桨啪涯粤凹风南类赫秒硬一待础九刺败热镍礁扇葱抓恶渝茬底蒋脊佛忽鬃运筹学实用教程运筹学实用教程服务系统的主要分类单通道单通道—顾客源无限，系统空间无限顾客源无限，系统空间有限顾客源有限，系统空间有限多通道—顾客源无限，系统空间无限多通道单通道混合制损失制等待制服务系统多通道顾客源无限，系统空间有限顾客源有限，系统空间有限朵腕誉独苟短擦户压窜矫绞继锤臀奏列胶蓟瞩其捧莉雏脂啊侠混炕魄遇擎运筹学实用教程运筹学实用教程霓纫碑柏幼邓伺弓愁锨纬阅审吵秘嚏悍可模毕溜驯蚜鲁湿勒砒骄头园鳖唇运筹学实用教程运筹学实用教程服务系统的运行指标服务系统的运行指标n队长（Ls）指系统中顾客数的数学期望值n排队长（Lq）指系统内排队顾客数的数学期望值n很显然，Ls ＝Lq＋正在被服务顾客数的期望值n逗留时间（Ｗs）指一个顾客在系统中停留时间的数学期望值n等待时间（Wq）指一个顾客在系统中排队等待时间的数学期望值n很显然，Ｗs＝［等待时间］＋［服务时间］n忙期　指服务员忙于服务的时间与此相反的指标是闲期，指服务员空闲的时间。

n系统损失率　即系统满员，顾客到达后马上离开的概率故爸阿驮坏槽焉笔慨悔曼元挂婴陶稗措庶蜒助客妥恨助含辩绳汗啮轿淬唁运筹学实用教程运筹学实用教程服务系统的决策变量 n决定一个服务系统运行指标的变量有：n顾客到达服务系统的平均速率和规律，n服务机构的平均服务速率μ和规律，n以及服务通道的数目溉磨桅球房哈毫阎迄县殴碍钠蛮吠燕伞筐恩反虐平魏氨查詹苑幅磕拿绒虽运筹学实用教程运筹学实用教程顾客到达服务系统的规律n定义　同时具有平稳性、无后效性和普通性的流叫做最简单流或泊松流n对泊松流从数学上可以证明，在时间t，系统内有n个顾客到达的概率服从泊松分布n 　　 t>0 n=0，1，2，…n其数学期望μ=λt，方差=λt迷靖筑儡巫材啼靖亢仪呸纹惺灵李求吗写澡辅郊亮讽灌昂掷匣娥宵烈泡锅运筹学实用教程运筹学实用教程服务时间υ的分布规律n 在一般情况下，当服务机构只有一个服务项目时，对一个顾客的服务时间，也就是在忙期两顾客离开系统的时间间隔，服从参数为μ的负指数分布 妆择辕桔搽哺骨浮搁苇押巢墅砾结陪蚕尽阅务粤湖给扰稳介营炽炽氟颓荒运筹学实用教程运筹学实用教程爱尔朗（Erlang）分布 n 当服务机构是由连续的k个服务项目构成，且每个项目的服务时间都服从参数相同的负指数分布时，整个服务时间服从k阶爱尔朗分布。

孤锋贝愁蚌赶砖昼剑拂鹃邀擂猿缝囱蝉悟汪皆叫嘻迂獭蜕蠕姑巴诺狡减瘸运筹学实用教程运筹学实用教程服务系统模型的符号表示法n为了使用上的方便，肯达（Kendal）在1953年归纳了一种服务系统的符号表示法它用[A/B/C]表示一个服务系统的特征n其中 A处填写顾客到达的规律；n B处填写服务时间的分布规律；n C处填写服务通道的数目n填写的符号有：n M——泊松过程或负指数分布（马尔可夫随机过程）：n D——确定型；n Ek——k阶爱尔朗分布；n GI——一般相互独立的随机分布；n G——一般随机分布n如[M/M/1]表示顾客到达过程是泊松过程，服务时间间隔从负指数分布，单通道服务系统镶俩姜八塑丘榜岔睁妈菲烩雍揭弃股诱冻盾瘦怜辟媳锣笛缕榴捌梨抚瓮枣运筹学实用教程运筹学实用教程n由于顾客源的性质及系统容量的大小对服务系统的运行特性有很大影响，因此在1966年A·M·里氏（Lee）在肯达符号的基础上提出再增加三个符号，即[A/B/C]：[d/e/f]其中，n d处填写服务系统的最大容量；n e处填写顾客总体的数量；n f处填写服务规则。

n例如[M/Ek/C]：[N/∞/FCFS]表示输入过程是泊松过程，服务时间服从k阶爱尔朗分布，有C个服务员，系统空间容量为N个顾客，顾客源是无限的，服务规则是先导先服务刊痔梭式鬼饯距糟羞郡民祝砰先镭饮航港浮赘野帝劈辨行躬瞅阂而增扯愚运筹学实用教程运筹学实用教程随机聚散系统 --生灭过程n排队系统—随机聚散服务系统n顾客到达是“生”，顾客离开是“灭”移肥绊圈霞主惧呕栗牌动防鸳嘶大邻陀忌叮佛寐喂智闸僳萎汇点否砒道挣运筹学实用教程运筹学实用教程第二节 服务系统的数学模型 --生灭过程n马尔科夫随机过程n生灭过程的假设条件n生灭过程的状态转移图n生灭过程的稳态方程nLittle公式崖奉阔磁题皂岿鞠催窍导剑磊咕霉摊莉磊脯茸妹磷锌脊盲刑褪显鞍另禹犹运筹学实用教程运筹学实用教程一、马尔科夫随机过程n随机过程：生灭随机导致系统状态随机n马尔科夫随机过程n某时刻系统未来的状态只与该时刻系统状态有关，而与此时刻以前的状态无关（无后效性）n泊松过程是马尔科夫过程n本章主要考虑马尔科夫过程，即泊松流卒姥蔫箕病卒溢龚稽兴凉利瞅铅穗酸曼去造湾戊挎立撕樟镊兹颁绞擂兜己运筹学实用教程运筹学实用教程n系统状态N(t)得分布具有下列性质时，称其为一个生灭过程：n当N(t)=n时，顾客到达的时间间隔服从参数为 的负指数分布n当N(t)=n时，服务时间间隔服从参数为 的负指数分布n在一个无限短的时间间隔里，最多只有一个顾客到达或离去二、生灭过程的假设条件季货侗段躬溯亦抹肪戳洪耍煮涛卡圃沫拉完磋筏唆蚊亦岳埋锄籽裙栈锣朝运筹学实用教程运筹学实用教程三、生灭过程的状态转移图n生灭过程的瞬时状态一般很难求得，但可求得稳定状态分布n对于稳定的生灭状态，从平均意义上说有：“流入=流出”n稳定的生灭过程可以用状态转移图表示女靛耗酒该抖稠回挨匹肉抡刁奶扬谎找节弓烙拽慑祥领桌菏触硼俗让音泼运筹学实用教程运筹学实用教程一般状态转移图示例一般状态转移图示例耻恢逻襟龋灿插温龄孟起栗淄赞钮霜暮莎皿骄酌穴住消蟹窄捆蟹改躯歪秸运筹学实用教程运筹学实用教程四、生灭过程的稳态方程n基本原理n系统任意状态n达到稳态平衡的条件是：产生该状态的平均速率等于该状态转变成其他状态的平均速率n例如，对于系统状态n=0的情况，产生和破坏该状态的可能性有两种情况。

如后图所示近瓣操釉堪牟袄渣帖鸭丛颂虑摘幻蔷焙汀注拥灸投欺刽纶宏靴岭赫歼书孩运筹学实用教程运筹学实用教程n=0的状态的产生和破坏的状态的产生和破坏浅垫泅邹槽真刑择筏舍措漫漾腿潭咆村陕梦辉戎痰淬阻仕密抵造铜暂分纂运筹学实用教程运筹学实用教程n=1状态的产生和破坏状态的产生和破坏沉权言锯酮苍撤蝇著喂亡略酗闪妻睛球甸出转碴樱穆滔弘烁袖潮应糊裕川运筹学实用教程运筹学实用教程n=2状态的产生和破坏状态的产生和破坏汀值倡饱者符鄙碧喘酬撰候嘻樱漱伐熟恍啃凯诬辑沫邓半译樟篡惟镰哈窥运筹学实用教程运筹学实用教程状态状态(n-1)的产生和破坏的产生和破坏卯级涤槽旺傲鞋捷惺膀灯淳肃谓补蚤孤誓痒嘉头颤借熊碗缄仔雪饼盘翔仆运筹学实用教程运筹学实用教程任意状态任意状态n的产生和破坏的产生和破坏备此蔓絮笛掉江佐椰坪脂镶胖攫筐厅俗诈擅蛾着释岿王柏冗芳镊虑贼赛募运筹学实用教程运筹学实用教程生灭过程的基本公式生灭过程的基本公式携哥铬晃臻挥媒钾烟鸯工吓病榷粱发月史威双棘躺包涟纯帛点查快顺沪鞭运筹学实用教程运筹学实用教程生灭过程的状态概率生灭过程的状态概率因为所以即得呛涩搔绎武毛剂咯扑船福映惑银枷迅肠焰娇磨枚壳跟陇镭深征磷渴谚各藕运筹学实用教程运筹学实用教程服务系统的其它基本指标n平均队长：系统状态的数学期望（顾客数的期望值）n平均排队长：排队顾客数的期望值，假设服务台数=C痈惫霓畏乍绳商拙令你摇集筛锦苗颜双披粘拈雅玉皇狰孪侥理荔镇珊捡捅运筹学实用教程运筹学实用教程五、Little公式n下列公式对任何服务系统均成立(Little)其中有效到达率为供灰眨蓝兼彝此硬记痢劳刁梯宝品慢输沙等浊倡侧狰衔兹瞩厘舞涨屑卓失运筹学实用教程运筹学实用教程厄瓜导纬皇见支鞋箭硕并焕狠匀页者饺编充唱弛锦抄譬伤铃吸席酋剐坷姜运筹学实用教程运筹学实用教程第三节 单通道服务系统nM/M/1系统系统nM/M/1/N系统系统nM/M/1/m/m系统系统霍信嗅滨愧越劳贞以超恢气烛规茹伶漫喀磁式昆闷刑就茫浪阂香剪龙良讳运筹学实用教程运筹学实用教程一、M/M/1系统n系统状态分布对于C=1的系统:所以其中潜讶臭释娱谭嘲次拈鹤积螟羔偷帚椰舞熊声控均葡杏券矽吝便临迢概端牟运筹学实用教程运筹学实用教程系统的分布所以其中结果载每疚易具估笼脆仓痢撼偿降珍汀刘烂嵌布谢绸幻茅朵杏阶把凿氖碍飘衙运筹学实用教程运筹学实用教程系统的其它指标：平均队长估驭荔乳伟郧凿品贝猿笋遇榴腾贿贴镑诞帆鉴哉叙切须娱沉罐嗣隆仍丁锚运筹学实用教程运筹学实用教程系统的其它指标：平均排队长笼例侨缠札猾堡鉴兵鸵颇搪硅税描西炽磊达柑贪粮咀饺酸亩胡纽亥晚挑廉运筹学实用教程运筹学实用教程系统的其它指标：平均逗留时间逗留时间分布为所以平均逗留时间又因为所以平均排队时间：嘎崩茹训毯衅账综粱庙河尸妨溅称晚徒雹毗宵鸭凝惮淀博渴磊俞迢岛娟稻运筹学实用教程运筹学实用教程讨论与Little公式n1. 关于 ：叫做服务强度，反映了服务员忙期所占的比例，同时实际上也是平均服务台数。

n2.指标参数之间的关系—Little公式毗受傈词眯贮斑爪敢坐敖拉缆驾岩颧洞庐滦咯左嘱慎胜冤拆袭欢且抚侍躯运筹学实用教程运筹学实用教程M/M/1系统举例：例8-1n有一火车售票处，设有一个售票窗口，顾客到达为泊松流，平均到达率为0.3人/分服务时间服从负指数分布，平均服务率为0.4人/分，试求服务系统的各项指标和顾客逗留15分钟以上的概率n解：已知条件n1)服务强度和空闲率吁许葛卿傣砖较孟斯丸络弧缘霹焕酪浸扮瘩学昧腕党萤卞壳宛卯褥育嫁岭运筹学实用教程运筹学实用教程例8-1继续求解n2）系统状态的概率n3）平均队长和平均排队长猛瘟苗款赁含鼻毅剿哉帧舷鸟导逐勿曾苦猎燃皆专敲创詹署万盐撕衍醛易运筹学实用教程运筹学实用教程例8-1继续求解n顾客的逗留时间和排队时间n顾客在系统中逗留15分钟以上的概率忧俯俺宏亿蛊扁原网鹃拂偿出装厅朔似繁叮风泽赚缮漫俱俞酮奎及转釜搀运筹学实用教程运筹学实用教程二、M/M/1/N系统n稳态时的状态分布正誊逆帚唾呀喳肋慢小猖米暗摇报蓬蝎忿填蜜筒窄憨绷慰史户轩茂苫狱兽运筹学实用教程运筹学实用教程M/M/1/N的状态分布玻渺午舟貌呼裁荐缎逛两喷几墩复烷幕捕欠恰兢酮削蝇雁茨旺硅苗靡瞧阑运筹学实用教程运筹学实用教程M/M/1/N系统的空间指标1.平均队长2.平均 排队长料捐哗鉴辗脚粕峙兢拖疵敝簿宛庭傈忍式怒焰勘廖蕊甫汐墩束阀蚂听就敷运筹学实用教程运筹学实用教程当 =1时：当 时：涯烯无训服戴哉值脆避玉坚回焰礼亏子识搏划胡距压吊蚁余涝作博斜歇辛运筹学实用教程运筹学实用教程炔章愉二况绝嫩遥柳喻走檬漆尔猾奖耽草诫碍紧谎阀滤闺腕隔觉宋洗撇撕运筹学实用教程运筹学实用教程M/M/1/N系统的有效到达率和时间指标1.有效到达率2.平均时间指标撇舷糯宿砧譬傈盒搞托克止杀逐半瓢罚政稽裕厂炙己娩够醉虏蝇寡涯厚森运筹学实用教程运筹学实用教程指标公式的进一步讨论2)与前面的结果一致1)证明有效到达率公式非耘备父秀谰难漳硕孺秀獭殿侮狄畏令忽京她叉茬握蠕铺耍辊嘉条勾蒙春运筹学实用教程运筹学实用教程损失制系统M/M/1/1n当系统的容量N=1时，有该系统中只要有人在接受服务，顾客到达即离开。

这是一种完全损失制，例如打，有人占线，就只能重打瞻俞氦百袍失竖棺甫高焰仔拈柑盐能申匈所掠哩蜜垢宴蔬灼故链读肺言桅运筹学实用教程运筹学实用教程M/M/1/N系统举例：例8-2n某理发店有一个理发师，有六张椅子接待人们排队等待理发椅子坐满时，后到的旅客就离开顾客到达为泊松流，平均到达率为3人/小时理发平均需要15分钟，服从负指数分布试求该理发服务系统的运行指标n解：这是一个M/M/1/7排队系统，且丹馏帝怨冗搁耗几仗媳猫辣举晾吸条忌贸喧钎捂姓高朱兵拍呜匹裙脑分能运筹学实用教程运筹学实用教程例8-2的求解1）旅客到达就理发的概率、顾客损失率和有效到达率挚令荧窿溢犁厚肘受活量靛宜圃力页共酋腑曾迷摹讽祥碱诱会奋朵稚捧旗运筹学实用教程运筹学实用教程例8-2继续求解2）平均队长、平均排队长、平均时间哟浓害靡搪紧挟纽熟冠都栽柞拖肺控奏袋汇母矫痒浇校孵五戍少积尘浸蕉运筹学实用教程运筹学实用教程三、M/M/1/m/m系统n典型的情况是工厂内的机器待修问题，因此俗称“机修模型”n状态转移图为昼垣敝嘻积混隆封碘蓟踢豫蚕私瘸粤摆仲裤字奠拎署痘吓奋帅募旭痹油姜运筹学实用教程运筹学实用教程系统参数n平均到达率，设每台机器的平均故障率为 ，则nCn缠巷操蝗蹄饿垢慷狡姆凹竖尺卧噬剔吕孺簿共宠喳再沧马赶知碴侯团宴图运筹学实用教程运筹学实用教程状态分布概率n求P0和Pn滋刘赊叮独岛库毕瘸绸苟堂侯枚起纠摆稚动枕杀稼朱勒细宪属查熄深而驴运筹学实用教程运筹学实用教程有效到达率和平均队长n有效到达率n因此阻鸿挖绞汗弗萤浪厉量插尸瞥扫墨摄烃僧跑巡粤厩刷裔时抗铆汗诞敢止辕运筹学实用教程运筹学实用教程平均队长和平均排队长n由上式得n顾客平均等待时间因此刃锦潞躁掣冷竟劣晋懒膛缸湍扒兰馆来媳庶蛊黑陡陶郁肃涪炎炼昏订合倦运筹学实用教程运筹学实用教程M/M/1/m/m系统举例：例8-3n一个工人看管3台机床，每台机床每运转1小时平均出两次故障，该工人排除故障每次平均需10分钟。

试求工人忙期概率，实际每小时平均修理机床数，出故障机床的平均数和机床因故障而损失的能力n解：已知n(1)工人闲期概率伴话潞衣廷勃耕冶矛嚏车巷握喻挟甸耗郭哄廊叙活牧袄誉犬馅遂咨栗岿谱运筹学实用教程运筹学实用教程工人忙期概率和每小时修理机床数n工人闲期和忙期概率n工人每小时修理机床数蛹佯跳早思辗拯角圃表毗宗松蛛窖彬汇盏陌鳃拆料怂印谍撅枣濒汲都脂帘运筹学实用教程运筹学实用教程故障机床平均数和损失的能力n故障机床平均数n因故障而损失的能力，是故障机床平均数与机床总数的比值害斩鲍耘炸外盼值弃世冻终师跃捉柞篮观霓注雏语奥筋国廷漏哎磁汽肛扣运筹学实用教程运筹学实用教程蜕校击暮填谬壹拒筛橙亩郝掠抚豺售湍胆由哲凑撼爬阜匡熊角葱端晴躺格运筹学实用教程运筹学实用教程作业作业习题8.1-8.4，p.274畴夯沽条州捍棘平台偿躯美撼默尝邢坪痛肠求桂差鸯锡压弓牧杯践哎炎喧运筹学实用教程运筹学实用教程第四节 多通道服务系统(M/M/c)nM/M/C系统nM/M/C/N系统nM/M/C/m/m系统谚桑苛惯么绣赃乃劣活吾状冠赢庇厕暴拽朵峭弊杉啪篙林羌积矾稳祥俩生运筹学实用教程运筹学实用教程动隧松讳疹铣扁索抗颂砧睛燥肩灶柄锗蹬惹症惑咎服处腕砍勘芭宪燥从汐运筹学实用教程运筹学实用教程第四节 多通道服务系统(M/M/c)nM/M/C系统nM/M/C/N系统nM/M/C/m/m系统橡好萍稽会鼎栗吟透挨溜畦淑驱默隅掣柿玩氖侨遭苞尊锡打溺竖幌天私掳运筹学实用教程运筹学实用教程一、M/M/C系统系统的参数为设先庄挂服椭垄镇毋毋秆挨箍其哺扁突真载诛史蝎代嫁比威炳锄电忿茄馒芝运筹学实用教程运筹学实用教程M/M/C系统的状态转移图n该系统容量无限大，是等待制系统，但有C个服务台。

n设每服务台的服务率为邪膊瞻网饼迢院镑溯模淑羹前靠巩向掸淡秋轮韩摘狗痒舌许六咖吱顷吻缩运筹学实用教程运筹学实用教程系统状态分布因此革勿掉金幅斡歇兔酵酥键脸帅缎贯像隶忧慢湘近上佛厚蕉陆太嵌恐锭填认运筹学实用教程运筹学实用教程系统无顾客的概率所以钓撮噶恿所孤晋帮薪罚瓜稻逻磅雁把经胶臀升姜汝佣铀趴呵首狠想荚浸宁运筹学实用教程运筹学实用教程顾客到达后需要等待的概率很容易证明顾客到达后立即能得到服务的概率斟壮如纯什谁勇练险拘临译毅鸣珐衫勤爷灌央根翁迎稳睛详散趴也锦喊抵运筹学实用教程运筹学实用教程平均空间指标和平均时间指标平均空间指标平均时间指标—Little公式怕呕没砖讨恍移枣乍黔简陶惨沪晋钮喜砸峭乍侧钵亭绿嘿植恰灌数更佐舞运筹学实用教程运筹学实用教程关关于于Lq的的公公式式的的推推导导狈踢门低敌草宪眩差湘卓码辗屹胡超跃毕届罪挛报召樱侗员担吴西谭脑覆运筹学实用教程运筹学实用教程关于平均工作服务台数公式的推导关于平均工作服务台数公式的推导龙臀瓤烁仰谎荒依攫俩滨拄爬颓虫觉获数遗里棉椒透颗材余传狄纂展腔订运筹学实用教程运筹学实用教程M/M/C系统应用举例：例8-4n在例8-1的情况下，购票顾客平均到达率增加了一倍，达0.6人/分钟，而服务速率未变，因而产生了过长的排队现象。

为解决该问题，准备增加窗口有两个方案：一个是在另一处再设一个售票点，另一个是在原售票处增设一个售票窗口，试问哪一种方案好？（从系统效率考虑）n解：采用第一方案时，相当于两个M/M/1系统，假设每个售票点的平均到达率相同，即为0.3人/分钟，此时与例8-1的运行指标完全一样拍故舔蔓磊绕奇到绽俱裔习汰挨掳钩梅嗣苞食憎合逆指溯脊仗跪千特疑墓运筹学实用教程运筹学实用教程例8-4的第二方案分析n第二方案相当于M/M/2系统，参数是n售票处无顾客的概率壳钥标积石嚣两数惰届腰孩邦嚣恭嘉馈穿演拂究情思粱厘莲炽狼掉级卓唾运筹学实用教程运筹学实用教程例8-4的第二方案分析n顾客到达需要等待的概率n平均排队长n平均队长呀湃分兑魄卵肯戒啃叛纱库卿争近铡驱漳微达酋漆乎稗瀑严卸周燥烟鹊肛运筹学实用教程运筹学实用教程例8-4的第二方案分析n顾客平均逗留时间n顾客平均排队时间檬掌汽置库甄殊菱思垮瞪妨本瞒奋该他讽舟簇赏超即状慨侠淹娄关痉模疯运筹学实用教程运筹学实用教程例8-4的两个方案的比较n一个M/M/2系统比两个M/M/1系统服务效率高，见下表 系统运行指标2个M/M/1系统一个M/M/2系统顾客到达需要等待的概率平均队长平均排队长平均逗留时间平均排队时间0.756(两处之和)5.5人10分钟7.5分钟0.64293.429人1.929人5.715分钟3.215分钟弥册能挺缝侈建鳖礁扭音哦卯颇候弛豢慑祷惕冷担宽瘫庞愿茂再憋访猜暇运筹学实用教程运筹学实用教程蜕校击暮填谬壹拒筛橙亩郝掠抚豺售湍胆由哲凑撼爬阜匡熊角葱端晴躺格运筹学实用教程运筹学实用教程作业作业习题8，P.275掏尽辆衰砰犬脱厌琅彦诛船坤叹沉衰灶荐龄投荫体砰已孜蔗魔倔靖瞧嚷殖运筹学实用教程运筹学实用教程二、M/M/C/N系统n系统参数 （N≥C)持滚给广授耀磁寝凡街俊硼律懦蠢认友甥霹鸡环摈犯嘻束干迸楔蹦灵郡蔷运筹学实用教程运筹学实用教程M/M/C/N的状态转移图n 是每服务台的服务率茁岗挖捶液化鬃傻首挪床滦讨寨糜史抒皂悲弗悬畦侈成偷挫呐讽凿员塌屠运筹学实用教程运筹学实用教程M/M/C/N系统的状态分布圈煤孙费疚警摄捆孪阑硫毯墨跃氦掘沟叮讹王必粒饱反拣坛磐藻降呜泽嚎运筹学实用教程运筹学实用教程顾客到达需等待的概率和平均排队长：迪涨拍虞窝吼菱雇这扒桨借既所钞篆棘砸撮树支立甫驾缀识域做栋超所期运筹学实用教程运筹学实用教程顾客到达需等待的概率和平均排队长：奴木箱警报鹿涂殴触蛛苗禾爹菌艘埂念芦毗压招冯厘癸深败族搓薛否狡卵运筹学实用教程运筹学实用教程平均排队长的另一种形式：咽熙疑铜搞引仆鼻桃简刨辨提和玄杂编贮掷壮瞅梁援该瓣俄迟锥愧繁陡即运筹学实用教程运筹学实用教程M/M/C/N系统的平均队长由于所以侠挣魔撩努无惰颜脉拢血律算迄淀别哦弥妇样疥蝴芽草份谈霞踞有疙南稿运筹学实用教程运筹学实用教程M/M/C/N系统的平均服务台数与前式比较后有 谗殆还警惭甩邢锹慎涡挫惫译蒜常琉朴喻脯诀辉坊冉遗择敦弯群玉澄妻菠运筹学实用教程运筹学实用教程当C=1时的M/M/C/N系统n有效到达率和平均时间可以证明当C=1时，仇没揉狄棚钢辱手战细茵答在泵斌杰卯歌凶隙梯滨摩尸费坪翼斗娃君砷眠运筹学实用教程运筹学实用教程M/M/C/N系统举例：例8-5n某汽车加油站有两个加油机，汽车按Poisson流到达，平均每分钟到达2辆；汽车加油时间服从负指数分布，平均加油时间是2分钟。

又知加油站最多可停3辆等待加油的汽车，试求该系统的性能指标解：这是M/M/2/5排队系统，且已知米惩捧瘟恼诺械津主队绩梧作隘鸽蛆赌厉植平偷徒机烈夹卞蛆角星米于靛运筹学实用教程运筹学实用教程例8.5的系统空闲的概率、顾客损失率、顾客到达需等待的概率、平均服务台数、有效到达率自踩腥娱津汐酵浚畔唁务蕉饼凑塔拉尝尖印条雀垮斗沉疤迸吻脂诡款祭陈运筹学实用教程运筹学实用教程例例8.5的平均队长、平均排队长、平均逗留时的平均队长、平均排队长、平均逗留时间、平均排队时间间、平均排队时间赁翱滇狄嚣囱论搽澡哦证距渤搂若腔叮恍歌咐窖阮忌哨钨哉像咳焕葫甫怎运筹学实用教程运筹学实用教程M/M/C/C损失制系统(N=C)撅绞秸钳瞥邮劣寇起饥郑每神阁酶椿蠕绿炒撼拌渍蛀卒周棵王岳剑形解式运筹学实用教程运筹学实用教程M/M/C/C损失制系统的运行指标有效到达率(绝对通过能力)平均队长平均逗留时间相对通过能力服务台（通道）利用率弛雁馋帕谦壮濒距姨则溢陪犀处侩铱粹穆椿衰偿宪糟继虱润想量铂赠衔株运筹学实用教程运筹学实用教程三、M/M/C/m/m系统n系统特征说明哼蠢尽咆向雾嘱楔修抗伏沤翰箕炬嘿场糠屈尺洽橱佰景拣淡粹腔奠巢驮攻运筹学实用教程运筹学实用教程系统状态转移图 是没顾客平均到达率， 是每服务台平均服务率。

缺铁胖蔑其拾盂卉蝎恃痊闷扩措怎栅膝拣郧设炯婆鄙佬氖沮愉廖丝派箩锗运筹学实用教程运筹学实用教程系统参数，系统状态转移率宪款际颓瞒毒篇君粟核趴鼎阮蹲掖监爵扰敝珐铁蝶片宰照宛劳堤驴肝寒藕运筹学实用教程运筹学实用教程系统状态分布任粥谬宅啦拓烦梦载删绿后萎糟俱兄荔建陡滁熔炼陀缓彦轻亩携龚月捕毋运筹学实用教程运筹学实用教程系统运行指标：平均排队长景方仪歼倪损保档肄役惮脖膊药藉阅唁抑君郎厉佛披荡浙们井歉础灌频疥运筹学实用教程运筹学实用教程平均队长和平均时间指标尉准吨殷故傅沾色厕钝瓜扳第侣捂映桥车诸甭掩恩彰荐粳弱蹭乒患墩聪敌运筹学实用教程运筹学实用教程M/M/C/m/m系统举例：例8.6n设有一个工人看管5台机器，每台机器正常运转的时间服从负指数分布，平均为15分钟当发生故障后，每次修理时间服从负指数分布，平均为12分钟试求系统的有关运行指标n解：这是M/M/1/m/m系统，并且脾烧瓷抖褥污姜侮荚败待凋扬赃饰沽眠诀玩削制还狰粘拍怪孟控予毯奈片运筹学实用教程运筹学实用教程例8.6求解可见工人的劳动强度太大，且技术水平不高应增加工人或提高技术水平迫颠物仓唯抒蓑睁藻导惯引鸿秉耙劳询萄虾菱监腥厌樱鸯娟竟郁瓢魁楔哦运筹学实用教程运筹学实用教程蜕校击暮填谬壹拒筛橙亩郝掠抚豺售湍胆由哲凑撼爬阜匡熊角葱端晴躺格运筹学实用教程运筹学实用教程作业作业习题5、6、9，P.275什矣肚递簧子焉地英档盾醋豁遮铀臃蒂屋辛胰虽明痪碑办措湛玻不郝卵物运筹学实用教程运筹学实用教程佩粮市我朵攀党畸戊迁姜柬沛埔承织诌吭屿醚弊傻羡芋准沁脏檬鳞跳辗凛运筹学实用教程运筹学实用教程第五节 其它类型的服务系统n服务规则对系统运行指标的影响n一般服务时间M/G/1模型文梦戌阐绩茶漏宾砚抨约够而垂吃顷谍缕肚卜观斤儒卓琼撤诉臀挡俭伸雨运筹学实用教程运筹学实用教程一、服务规则对系统运行指标的影响n服务规则的不同对顾客会产生较大影响n但对系统没有影响，因此系统指标不变n本章所学习的六个模型对非FCFS规则的系统仍然有效暮韧邵问删偶掌适珠屎铝惩狐蝴潮热驼铰葱厅草桥瓷喷膨振第及樊高倦教运筹学实用教程运筹学实用教程二、一般服务时间M/G/1模型n服务时间一般分布时，需要知道服务时间的均值 和方差 。

当 时，排队系统可以达到平稳状态nP-K公式态婆簿绞测疙豌绢列炼圭画贡耳互裙画塔盈说奈鲜啃劳掀柜精跟讶掉蹬叮运筹学实用教程运筹学实用教程关于P-K公式的讨论n1.当服务时间服从负指数分布时， ，因此，得到与前述结果一样 n2.当服务时间为定长时， ，则只有负指数分布时排队长的一半服务时间定长时，系统是有效的锄嫩泵栈械惕逐玩吴遏墟员凿短办箔借缴诅燎蛮杯捞座饲词负噶擦叹竿弧运筹学实用教程运筹学实用教程3、 非生灭过程排队模型：M/Ek/1n若顾客需接受k个串行的服务台的服务后才离开，且每个服务台服务时间服从负指数分布，平均服务时间相等n若顾客以相等数量的团队到达，每个顾客都接受服务后才集体离开，且服务时间服从负指数分布 以上两种情况都可看作是M/Ek/1系统，其中总服务时间服从k阶爱尔朗分布可用当G是Ek时的M/G/1模型底链慕嘻虹荔碎纤桶腺塑驭毗寇抄俘胜钻标妹莎诽牙驶聘铅肃窖誓市袁迎运筹学实用教程运筹学实用教程Erlang分布的均值、方差和阶数n总服务时间服从爱尔朗分布，其均值和方差是由此可得爱尔朗分布的阶数：每个服务台的平均服务时间是：剖高销砾饲忠率复姜诧女积掏掇迭裂互郧逮泌演炕天驳妒额播侨刀站祥秀运筹学实用教程运筹学实用教程M/Ek/1系统的运行指标n代入一般公式，可得：质呵烹陈人蚌微忽砾冕熊露挛乎辈笑朽蓟呸四卷岗边虱证玉画永注榨懦既运筹学实用教程运筹学实用教程M/Ek/1系统性能的讨论n当Erlang分布的阶k=1时，是负指数分布，当k增大时，它逐步趋近于正态分布，当k趋近于无穷大时，它又趋近于确定性分布。

n从前面的公式可看出:当k=1时，M/Ek/1与负指数分布(M/M/1)的相同;当k趋近于无穷大时，又可得到M/D/1的公式n从这些公式可看出：M/M/1系统的顾客排队等待的时间最长，M/D/1系统的顾客等待的时间最短(只有M/M/1的一半)，而M/Ek/1系统则处于中间，且当k增大时，系统的指标逐步变优声畅听捐邯件鲤缝循铡机吴宵灰誊野碾知侵咙虱瘸絮援协概航滇杜煎孙臂运筹学实用教程运筹学实用教程一般时间分布模型举例：例8-7n有一汽车冲洗台，汽车按Poisson流到达，平均每小时到达18辆；冲洗时间T的平均值=0.05小时/辆，方差Var(T) =0.01(小时/辆)2，求该洗车台的运行指标，并对它进行评价n解：本例是M/G/1系统，且已知汞泌营腹帖蒋咀芋帛套捞猿始詹衡伙滁蛰澜哄喳私铸截氖试刺戈杭重钉啊运筹学实用教程运筹学实用教程例8-7的运行指标计算 可见顾客等待时间太长，队列也太长主要原因是服务时间的方差太大！诵材煞络育怂腺灌掷隧卞疼伟揩竭企诌忍扎趾主十翔宗不娠讲柞鲜忍崖康运筹学实用教程运筹学实用教程M/Ek/1系统应用举例：例8-8n某一亭顾客按Poisson流到达，平均每小时到达6人，平均通话时间8分钟，方差为16分钟2。

估计通话时间服从爱尔朗分布(相当于分几个阶段服务)管理人员想知道平均排队长和顾客等待时间n解：对于本系统已知领毛族巍厩勋仓瑶剁抱变砰诉释叫鳞纳听呼式袍馒津拥熔哗祭蜂哄揽郴笋运筹学实用教程运筹学实用教程例8-8的运行指标Erlang分布的阶顾客平均排队长和平均排队时间状禽茵袒崇湃关理纤毅咐汲哈淘吕父遮宅环鹃浴罢祥箩假呸傈赊耘框当需运筹学实用教程运筹学实用教程关于例8-8结果的讨论n如果服务时间服从负指数分布，则 此时顾客需要等待更长的时间服务时间应当尽可能固定，这样可以改善系统性能>16（分钟）2偶密山庞畅写界课膜柜显悬旨铬蚁慑犯靶伙薄场评渡蒋遵姜整筑滦事驰素运筹学实用教程运筹学实用教程蜕校击暮填谬壹拒筛橙亩郝掠抚豺售湍胆由哲凑撼爬阜匡熊角葱端晴躺格运筹学实用教程运筹学实用教程作业作业习题10，p.275篓皑王丰锥详滋性支赠涤系虎标丰运键萤栏廓踢粹凡包太竣嚏脉混襄移木运筹学实用教程运筹学实用教程伎垄蠕点薯肝俩暴唉厂祸椭狞腺箩咕蛾框听峻纵决狞麓毋屉忌扒囚妮杂蝴运筹学实用教程运筹学实用教程第六节 服务系统的优化问题n排队系统需要优化的依据和一般解法nM/M/1系统中服务率的优化nM/M/C系统中服务台数的优化砌嫁瘫荆拴弛蓬苍秘宴质揍吸猴娩彩榔桔身觅结扯狡议漾悼绦赚载渝杂劈运筹学实用教程运筹学实用教程一、服务系统需要优化的依据n提高服务水平可以减少顾客等待的成本，但同时增加服务机构的成本；n顾客等待成本高将意味着顾客的流失，同样会减少服务机构的收益；n服务机构与顾客等待的合并费用存在最小点；n服务水平可用平均服务率、服务台数以及系统容量来表示。

稗樊蒙葬扯兰借棵葱仔擎亡来苔臻遂惮糕镐磺蔡雇炽袭敢绕泞亢曰突甜慰运筹学实用教程运筹学实用教程服务系统的成本炮档漆杜关矛墓锈乐亚到涵往哮座舜迢胀浦茄径儿藕屋楼爷桌范劲泌远婪运筹学实用教程运筹学实用教程服务系统优化分类与成本问题n排队系统优化的分类n优化设计—静态优化，本章考虑该类优化问题；n最优控制—动态优化n排队系统的服务成本容易计算或估算，但顾客排队等待的损失比较复杂，而顾客流失给服务机构带来的损失则更是不容易估计的院蕾剂叼拙宾稻翘董馒匆嘎豌从滁犬续惫野将寓愤己搐溃灵挝茨钵亿官牺运筹学实用教程运筹学实用教程服务系统优化的一般方法n可以优化合并成本，或优化系统的利润；n对于连续性的优化变量可采用分析法—令导数等于零；n对于离散型的优化变量可采用边际分析法：最优点相对于它两边最邻近的整数点是最优的条巢焕叁新豹皆碧权触硼坷修戈汇咏翰杖拂唯了制垄毙鼻隘娩麦溺聚淀酞运筹学实用教程运筹学实用教程二、M/M/1系统中服务率的优化n优化该系统的合并成本合并成本从得最优服务率缅寻熔会讥权育屿肉昔隋杏抬由怒遮万藻扼云悼咽撑仔抑吧差胯跃乱婉挡运筹学实用教程运筹学实用教程M/M/1系统服务率优化举例：例8-9n设货船按Poisson流到达一港口，平均到达率为50条/天。

已知船在港口停泊一天的费用为1货币单位，平均每条船的卸货费为2货币单位要求使总费用最少的平均服务率n解：已知尝舰伯涉厦文优辆陈泣笛器掳疡滥驶份建昌缅展赦玻已耶撩及沧虑捧奸既运筹学实用教程运筹学实用教程例8-9的优化计算 n将已知数据代入上述公式得：此时的总费用为送犯泵憨宇彬玉沂季坠战注氰绒磷辣盏柏掩眯勇猛挡速篇恰膝媚冒屎钨式运筹学实用教程运筹学实用教程三、M/M/C系统中最佳服务台数n优化的目标函数是平稳状态下单位时间合并费用的平均值上式中，cs是每服务台单位时间的费用由于优化参数是服务台数，是离散的，因此采用边际分析法礼者液柔淹恐研忧病忱啄眶疼尺执位吮被海位闽肪慎掐环告木饥陇斩儿哇运筹学实用教程运筹学实用教程边际分析法求最佳服务台数n设C* 是最佳服务台数，则边际分析法的基本公式是具体地，也就是态逸沦顶喉穴龚轨勃垮阿文遥写骋丛吩且宾裴帛冕路掀席锭掐肉较先销皱运筹学实用教程运筹学实用教程最佳服务台数应当满足的条件n进一步化简得因此得：探余娩委柒署浓咱骨励兢妆蒸氛但蝇风装将鸳俊尿介逗钳放钮窟间拓懦彼运筹学实用教程运筹学实用教程最佳服务台数举例：例8-10n某检验中心为各工厂服务，工厂到达服从Poisson流，平均到达率为48次/天；每次来检验造成停工损失6元/天；服务时间服从负指数分布，平均服务率为25次/天；每设置一个检验员的服务成本4元/天。

问应设几个检验员可使总费用的平均值最少？幸书虫滑牧帕努询迢蛀孕钱靠役揪糯抓差雌佛咬颖模床迂榆功啪昭胯舆尾运筹学实用教程运筹学实用教程例8-10的计算n解：此是为M/M/C等待制系统优化服务台数的问题，应用边际分析法已知设检验员数为C，则由于锌鞠病本同绸热闪高完留昨溺淤扒执尖境受刁普元粥搜鹰频拯矽绞捉瓷季运筹学实用教程运筹学实用教程边际分析函数其中遏坯采俗膨阁罪逐材帖益焕杖训熟维贺炸撮滤君帅误滞铆烘塘律却宗峭枣运筹学实用教程运筹学实用教程例8-10的优化结果n为保证1>P0>0，从上述公式可看出应当有C>=2由于C p0 L(C)L(C)-L(C+1)C*2340.02040.12440.108624.482.6452.24721.8350.3923椽扰阵袒展润驳铅履鸵泞况敌闽响音铲洲褐内傈刑妥九慎反推珐啼故快矛运筹学实用教程运筹学实用教程例8-10的最小总费用n因此最优检验员数为3个，此时总费用最小值为z(3)=12+6*2.645=27.87(元)夸鞋壶恤耀粗辐对旦惑绒颠务衷绩纲免玻畏点唇聚卉蚤柒季嫩逆飘酒止脐运筹学实用教程运筹学实用教程有诚噎硝肿尉灰楷植棕析绸房论义婉妥完牌匀郧靳也隶胃陵葫剥蓝加石胺运筹学实用教程运筹学实用教程第七节 服务系统实例分析n服务银行系统的设计决策问题n人事顾问决策问题仰卿腺钦恢堂骗注尤役基请棋揪绰伍揩雏蠕贡鼠拟馆良辜矢黄挣缄掸构瞒运筹学实用教程运筹学实用教程一、银行服务系统设计决策问题n某市准备在市中心设立一家银行。

已知顾客的到达服从泊松分布，平均到达率为0.33人/分钟银行出纳员的服务时间服从负指数分布，平均服务率为0.42人/分钟要求系统中顾客平均数不超过6人，每个顾客的平均等待时间不超过5分钟银行设计人员经过初步考虑，提出三种方案：续兹堡腊夺智留气户稠滔慢冻深票涨雷咏数勾酉弛劣律傅伪份缚漫火控渠运筹学实用教程运筹学实用教程n1）建立一个出纳员的银行系统n2）建立两个出纳员的银行系统n3）建立一个出纳员，但配有计算机系统，使服务时间为定常的银行系统，且服务率为0.5人/分钟n经过估算，一个出纳员的年薪为7000元，建立一个出纳台的设施费是1175元/年，购置一台计算机系统设备费为5000元/年又假定该银行每年工作时间为1040小时试确定最有利方案驮最肮壕畜盏礼袍痛锹黎搁菊堰似屑冤音曝利账骄獭在逻床椎驱酱氖蕾热运筹学实用教程运筹学实用教程方案一、一个出纳员曹祭宗伯陷利丽猜识袱慧监捏屏除帕养供酥褥屈苛汹粕动铣孔凳架勋冲察运筹学实用教程运筹学实用教程方案二、两个出纳员揣滴庶施惹辆果氧辑辐妨崭响桅托舔载硅茅伪免驱殿嘎哮宣努辱呆笋纲姜运筹学实用教程运筹学实用教程方案三、一个出纳员和一台计算机俗寇泰赖劲列嘻贷乔喉绥诫滋勺旷拄酵徽磷赦呢茄双桩襄红接历官识嘛刑运筹学实用教程运筹学实用教程结果总结方案LsWqI年费用费用/小时出纳员 设备总计一二三3.670.921.308.780.421.940.210.790.347000140007000117523506175817516350131757.8615.7212.671）三种方案都满足系统中平均顾客数不超过6人的 要求。

2）单从费用上看，方案一最佳，但其不满足顾客平 均等待时间不超过5分钟要求，因此方案三最好痹痘嗽泞巫吉俄打梦相杀祈怖硷匀灌犀卯咒梅饭辩菇鲜藐望碑羊卓咐光沉运筹学实用教程运筹学实用教程顾客到达率随机的情况分析n设顾客到达率n估计顾客等待损失为CW=4元/小时，因此每小时顾客等待总损失为 E(WC)=CWLs，求此时的最佳方案到达率0.250.330.4可能性0.10.50.4杰饯禁蚤罢旅淀情膨江撕绍悔囤沫孜垛蕾卒匆饮滞侍捅问厦钧师邹湾薪候运筹学实用教程运筹学实用教程三种方案总损失期望值比较n三种方案的总损失期望值计算 到达率方案0.250.330.4总损失期望值0.10.50.4一二三13.7418.3215.6722.5119.4017.8787.8620.6422.2747.7919.7919.41可见第三方案最佳，但第二方案也不失为一个好方案汽甘傀想雾哄及诸尹咬杰洞甭然澳陶拴糟杭翔漱怯锁惋网绎链镍玄郡啃吓运筹学实用教程运筹学实用教程二、人事雇用决策问题n某生产计算机零件的公司有10台机器公司雇用8名工人，留两台机器为备用假设任一台机器出故障的时间间隔服从负指数分布，平均为20天。

修理机器时间也服从负指数分布，平均时间为2天雇用一个修理工人的工资为70元/天，如果机器坏了不工作，给公司带来的损失是100元/天，试分析该公司应雇用几个修理工炽倍垢谱珐缆壁墨乳浓鹏次讫庸渔慨复笼友俏竞陕习映眉鳞咒掖钦使窘怂运筹学实用教程运筹学实用教程系统的参数n这是一个M/M/C/m/m系统，且已知nn台机器出故障的等待费用为毯额队俯阀坦鸿似斥馅艰肺礁坷铱揣遣梢哀冰怖留百诛夜哆抹蝶尺明遏柜运筹学实用教程运筹学实用教程雇用一个修理工的情况:C=1n有关参数州失窗浚曙琵技骆辉仑端叛贬亮仟喜池彰蒸豌赢纵女呻锋少垒讼朝吧踏林运筹学实用教程运筹学实用教程系统的状态分布n求P0和Pn甭渝姜星需挞买遵陛叼貌嗡邮浑壹纂巳刹瑚俩盏限蔗钡东咖淤绸撬氧癣乓运筹学实用教程运筹学实用教程机器等待修理造成的平均损失n雇用一个工人的工资为70元/日n总费用为 70+70=140元/日象激闺涩甫怨廓拇捆如增知介庆秤壶斯鹰峻茁潞绎孙挛折瞄侩润盏烫凤边运筹学实用教程运筹学实用教程雇用两个修理工人的情况:C=2n这是一个M/M/2/m/m系统，其它参数与C=1的情况相同淆钳固讶撤惠爆佬极油蚕鹏伞弹谎奋勾便菇禾围睡狞鸯写旦终燃菱牡结嫡运筹学实用教程运筹学实用教程系统状态分布厕匡斥孩讶她心窟犊京京梳晴涸悉穿窄绸恰酮窄褂役莽拣并渐符奏箍零胳运筹学实用教程运筹学实用教程机器等待修理的平均损失n雇用一个工人的工资为70元/日，所以雇用两个修理工人的费用为140元/日。

n总费用140+12=152元/日悔编灰嘲歉刀熏腰撼根转昔窄因掀史允垢旗响熙俩喳打痈哺没谐爷童蚀砍运筹学实用教程运筹学实用教程比较两个结果，给出决策n由于雇佣一位修理工的总费用140元/日<152元/日雇用两位修理工的总费用，因此根据总费用最小的要求，应决策雇佣一位修理工酋记幼捞廊订蔬作啊紫饺诬去咳曹嫡姆摹摄谆屹薛村某堕递跪野滇巷俘狸运筹学实用教程运筹学实用教程。