管理运筹学Ⅱ(研究生).ppt

《管理运筹学Ⅱ(研究生).ppt》由会员分享，可在线阅读，更多相关《管理运筹学Ⅱ(研究生).ppt（163页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、管理运筹学管理运筹学研究生课程研究生课程 陈鼎藩 工商管理教研室层次分析法（层次分析法（AHP）目标规划目标规划(Goal Programming)排队论（排队论（Queuing Theory）动态规划动态规划(Dynamic Programming)课程内容课程内容2参考教材参考教材（1 1）胡运权）胡运权.运筹学基础与应用（第运筹学基础与应用（第4 4版）版）.高等教育高等教育出版社出版社（2 2）胡运权）胡运权.运筹学教程（第运筹学教程（第2 2版）版）.清华大学出版社清华大学出版社.（3 3）运筹学教材编写组）运筹学教材编写组.运筹学（修订版）运筹学（修订版）.清华大学清华大学出版社出

2、版社.（4 4）吴祈宗）吴祈宗.运筹学与最优化方法运筹学与最优化方法.机械工业出版社机械工业出版社.3第一专题：层次分析法（第一专题：层次分析法（AHP）1 层次分析法概述层次分析法概述2 层次分析法计算过程层次分析法计算过程3 Yaahp0.4.1应用应用4 层次分析法是美国运筹学家萨第层次分析法是美国运筹学家萨第（T.L.SaatyT.L.Saaty）于于2020世纪世纪7070年代提出的一种定性分析和定量分析相年代提出的一种定性分析和定量分析相结合的结合的系统分析方法系统分析方法。这种方法合理地把定性和定。这种方法合理地把定性和定量的决策结合起来，按照思维、心理的规律把决策量的决策结合起

3、来，按照思维、心理的规律把决策过程层次化、数量化。特别适合于结构较为复杂、过程层次化、数量化。特别适合于结构较为复杂、决策准则较多而且不易量化的决策问题。决策准则较多而且不易量化的决策问题。1.1 The Analytic Hierarchy Process5定量分析方法的缺陷：定量分析方法的缺陷：（1 1）社会问题的复杂性决定了难以构造合适的模型。即使构）社会问题的复杂性决定了难以构造合适的模型。即使构造出数学模型，有时也难以准确说明问题或者难以执行。造出数学模型，有时也难以准确说明问题或者难以执行。（2 2）决策问题带有相当多的主观性，而这很难体现在最优化）决策问题带有相当多的主观性，而这

4、很难体现在最优化模型中。模型中。（3 3）庞大的模型难以理解，成本太高。）庞大的模型难以理解，成本太高。1.2 1.2 层次分析法产生背景层次分析法产生背景6 层次分析法的基本原理是排序的原理，即最终将各方法层次分析法的基本原理是排序的原理，即最终将各方法(或措施或措施)排出优劣次序，作为决策的依据。排出优劣次序，作为决策的依据。具体可描述为：层次分析法首先将决策的问题看作受多种具体可描述为：层次分析法首先将决策的问题看作受多种因素影响的大系统，这些相互关联、相互制约的因素可以按照因素影响的大系统，这些相互关联、相互制约的因素可以按照它们之问的隶属关系排成从高到低的若干层次，叫做构造递阶它们之

5、问的隶属关系排成从高到低的若干层次，叫做构造递阶层次结构。然后请专家、学者、权威人士对各因素两两比较重层次结构。然后请专家、学者、权威人士对各因素两两比较重要性，再利用数学方法，对各因素层层排序，最后对排序结果要性，再利用数学方法，对各因素层层排序，最后对排序结果进行分析，辅助进行决策。进行分析，辅助进行决策。1.3 1.3 层次分析法原理层次分析法原理71.4 层次分析法步骤层次分析法步骤(1)(1)建立递阶层次结构模型；建立递阶层次结构模型；(2)(2)构造出各层次中的所有判断矩阵；构造出各层次中的所有判断矩阵；(3)(3)层次单排序及一致性检验；层次单排序及一致性检验；(4)(4)层次总

6、排序及一致性检验。层次总排序及一致性检验。8确定开发比例确定开发比例国家投资国家投资运输运输电力需求电力需求前期准备前期准备煤炭储量煤炭储量开采条件开采条件发展露天煤矿发展露天煤矿发展统配煤矿发展统配煤矿吨吨煤煤投投资资投投资资后后效效益益投投资资后后水水平平中中等等需需求求远远距距离离坑坑口口运运输输高高需需求求低低需需求求人人才才准准备备时时间间准准备备现现有有储储备备物物资资准准备备远远景景储储备备自自然然条条件件作作业业条条件件层次结构模型层次结构模型9 首先根据问题的性质和要求，提出总首先根据问题的性质和要求，提出总的目标。然后将问题按层次分解，对同一的目标。然后将问题按层次分解，对

7、同一层次内诸要素通过两两比较的方法确定相层次内诸要素通过两两比较的方法确定相对于上一层目标的各自权系数，这样层层对于上一层目标的各自权系数，这样层层分析下去，直到最后一层，即可给出所有分析下去，直到最后一层，即可给出所有因素（或方案）相对于总目标而言按重要因素（或方案）相对于总目标而言按重要性（偏好）程度的排序。性（偏好）程度的排序。102.1 2.1 层次分析法计算过程层次分析法计算过程例：张老师要购买一套住房，他考虑的主要因素有：价格适中，例：张老师要购买一套住房，他考虑的主要因素有：价格适中，上下班要方便，小区对应的中小学较好，居住环境相对较好。上下班要方便，小区对应的中小学较好，居住环

8、境相对较好。经房地产中介商介绍，他初步选择了经房地产中介商介绍，他初步选择了A A、B B、C C 三套住房，情三套住房，情况如下表况如下表2-12-1所示：所示：A B C A B C价格价格/(/(万元万元)上下班上下班对应的学校对应的学校居住环境居住环境 35 28 22 35 28 22 不太方便不太方便 较方便较方便 方便方便 名校名校 较好较好 一般一般 较好较好 好好 稍差稍差11第一步：构建层次分析模型第一步：构建层次分析模型购买一套满意住房购买一套满意住房价格价格上下班方便上下班方便中小学情况中小学情况居住环境居住环境ABC准则层准则层目标层目标层方案层方案层12第二步：求本

9、层次要素相对于上一层要素的权第二步：求本层次要素相对于上一层要素的权 （构造两两比较判断矩阵）（构造两两比较判断矩阵）aij定义定义aij定义定义13579Ai和和Aj同等重要同等重要Ai较较Aj略微重要略微重要Ai较较Aj明显重要明显重要Ai较较Aj十分明显重要十分明显重要Ai较较Aj绝对重要绝对重要2468介于同等和略微之间介于同等和略微之间介于略微与明显之间介于略微与明显之间介于明显和十分重要之间介于明显和十分重要之间介于十分明显与绝对重要之间介于十分明显与绝对重要之间13(1)(1)各准则相对于目标的判断矩阵：各准则相对于目标的判断矩阵：价格价格上下班上下班学校学校居住环境居住环境价格

10、价格上下班上下班 学校学校居住环境居住环境14(2)(2)各方案相对于准则的判断矩阵：各方案相对于准则的判断矩阵：对价格对价格ABCA B C上下班上下班ABCA B C学校学校ABCA B C居住环境居住环境ABCA B C15第三步：求各判断矩阵的特征向量第三步：求各判断矩阵的特征向量(1)(1)和法和法先对判断矩阵的各列求和得先对判断矩阵的各列求和得并计算得到并计算得到(2)(2)根法根法先计算先计算归一化处理归一化处理16第四步：判断矩阵一致性检验第四步：判断矩阵一致性检验17矩阵阶数矩阵阶数 3 4 5 6 7 8 9修正系数修正系数RIRI取值取值 0.52 0.89 1.12 1

11、.26 1.36 1.41 1.4618第五步：综合计算结果，对方案排序选优第五步：综合计算结果，对方案排序选优 价格 上下班方便 中小学情况 居住环境AB C0.123 0.062 0.593 0.2830.320 0.212 0.341 0.6430.557 0.726 0.066 0.074193 3 Yaahp0.4.1应用应用(见软件见软件)20第二专题：目标规划第二专题：目标规划1 目标规划问题及数学模型目标规划问题及数学模型2 目标规划的求解目标规划的求解3 目标规划应用举例目标规划应用举例211 1 目标规划问题及数学模型目标规划问题及数学模型1.1 1.1 线性规划模型的缺陷

12、线性规划模型的缺陷ex1.1 甲企业计划生产两种产品甲企业计划生产两种产品、，这两种产品都要分，这两种产品都要分别在别在A A、B B、C C、D D四种不同设备上加工，已知每生产一件产四种不同设备上加工，已知每生产一件产品的设备加工工时、设备生产能力、产品单位利润如下表，品的设备加工工时、设备生产能力、产品单位利润如下表，问问、各生产多少使利润达到最大？各生产多少使利润达到最大？生产能力生产能力 A 2 2 12 B 4 0 16 C 0 5 15获利获利 2元元/件件 3元元/件件22线性规划的缺陷：线性规划的缺陷：（1）要求所有解必须严格满足约束条件；）要求所有解必须严格满足约束条件；（

13、2）只能处理单目标的优化问题；）只能处理单目标的优化问题；（3）线性规划中各个约束条件都处于同等重要位置，）线性规划中各个约束条件都处于同等重要位置，但现实问题中，各目标的重要性既有层次上的差别，同但现实问题中，各目标的重要性既有层次上的差别，同一层次中又有权重上的区分；一层次中又有权重上的区分；（4）线性规划寻求最优解，但很多实际问题中只需找出）线性规划寻求最优解，但很多实际问题中只需找出满意解就可以。满意解就可以。23 19611961年，美国学者年，美国学者A.A.查恩斯和查恩斯和W.W.库伯库伯管理模型和线管理模型和线性规划的工业应用性规划的工业应用一书首次提出目标规划，以后此模型一书

14、首次提出目标规划，以后此模型经优吉经优吉.艾吉里、杰斯基莱恩和桑艾吉里、杰斯基莱恩和桑.李不断完善改进。李不断完善改进。1976 1976年伊格尼奇奥发表年伊格尼奇奥发表目标规划极其扩展目标规划极其扩展一书，一书，系统归纳总结了目标规划的理论和方法。系统归纳总结了目标规划的理论和方法。241.2 1.2 目标规划问题目标规划问题ex1.2 假定在假定在ex1.1ex1.1中企业不仅仅考虑利润，还要考虑以下几中企业不仅仅考虑利润，还要考虑以下几点目标（按重要程度由高到底）：点目标（按重要程度由高到底）：.力求使利润目标不低于力求使利润目标不低于1515元；元；.考虑到市场需求，考虑到市场需求，、

15、两种产品的生产量保持两种产品的生产量保持1:2的比例；的比例；.A A为贵重，严格禁止超时使用；为贵重，严格禁止超时使用；.设备设备C C可以适当加班，但要控制；设备可以适当加班，但要控制；设备B B既要充分利用，既要充分利用，又尽可能不加班，又在重要性上又尽可能不加班，又在重要性上B B是是C C的的3 3倍。倍。251.2.1 1.2.1 设置偏差变量，表明实际值与目标值之差设置偏差变量，表明实际值与目标值之差d d+表示正偏差变量，实际值超出目标值；表示正偏差变量，实际值超出目标值；d d-表示负偏差变量表示负偏差变量 ，未达到目标的差值，未达到目标的差值d+d-=0 ，当实际值恰好等于

16、目标值时，当实际值恰好等于目标值时，d d-=0 =0，d d+=0.=0.1.2.2 1.2.2 绝对约束和目标约束（软约束）绝对约束和目标约束（软约束）（1 1）绝对约束是指必须严格满足的约束，如线性规划中的约）绝对约束是指必须严格满足的约束，如线性规划中的约束都是束都是 刚性约束，对它的满足与否决定了解的可行性。刚性约束，对它的满足与否决定了解的可行性。例：例：.A A为贵重设备，严格禁止超时使用；为贵重设备，严格禁止超时使用；26 （2 2）对那些不严格限定的约束，连同原线性规划建模时的目）对那些不严格限定的约束，连同原线性规划建模时的目标，均通过目标约束来表达，需引进偏差变量。标，均

17、通过目标约束来表达，需引进偏差变量。例：考虑到市场需求，例：考虑到市场需求，、两种产品的生产量保持两种产品的生产量保持1:21:2的比例；的比例；例：假定希望例：假定希望的的2 2倍产量不低于倍产量不低于的产量；的产量；例：假定希望例：假定希望的的2 2倍产量低于倍产量低于的产量；的产量；例：假定希望例：假定希望的的2 2倍产量恰好倍产量恰好的产量；的产量；27目标函数用法：目标函数用法：目标函数目标函数含义含义min d+d-要求恰好达到目标值，决策值超过或不足目标要求恰好达到目标值，决策值超过或不足目标值都是不希望的。值都是不希望的。min d+要求不超过目标值，但允许不足目标值，这时要求

18、不超过目标值，但允许不足目标值，这时不希望决策值超过目标值。不希望决策值超过目标值。min d-要求不低于目标值，但允许超过目标值，这时要求不低于目标值，但允许超过目标值，这时不希望决策值低于目标值。不希望决策值低于目标值。281.2.2 1.2.2 目标的优先级与权系数目标的优先级与权系数 不同目标的主次轻重有两种差别，绝对的差别用优不同目标的主次轻重有两种差别，绝对的差别用优先因子先因子 来表示，且来表示，且 。用权系数来表示同一优先级上各个目标的相对差别。用权系数来表示同一优先级上各个目标的相对差别。29Ex1.2Ex1.2的数学模型的数学模型301.2.3 1.2.3 目标规划的一般数

19、学模型目标规划的一般数学模型311.2.4 1.2.4 目标规划求解问题的步骤：目标规划求解问题的步骤：明确问题，列出明确问题，列出（或修改）目标的（或修改）目标的优先级和权系数优先级和权系数构造目标规划的模型构造目标规划的模型求出满意解求出满意解分析各项目分析各项目标完成情况标完成情况满意否？满意否？是是否否据此制定决策方案据此制定决策方案322 2 目标规划的解法目标规划的解法2.1 2.1 目标规划的求解（管理运筹学目标规划的求解（管理运筹学2.02.0）333 3 目标规划应用举例目标规划应用举例 ex3.1 ex3.1 某电子厂生产录音机和电视机两种产品，分别经甲、某电子厂生产录音机

20、和电视机两种产品，分别经甲、乙两个车间生产已知除外购件外，生产一台录音机需甲车间乙两个车间生产已知除外购件外，生产一台录音机需甲车间加工加工2 h2 h，乙车间装配，乙车间装配1h1h；生产一台电视机需甲车间加工；生产一台电视机需甲车间加工1h1h，乙车间装配乙车间装配3h3h这两种产品生产出来后均需经检验、销售等环这两种产品生产出来后均需经检验、销售等环节已知每台录音机检验销售费用需节已知每台录音机检验销售费用需5050元，每台电视机检验销元，每台电视机检验销售费用需售费用需3030元又甲车间每月可用的生产工时为元又甲车间每月可用的生产工时为120 h120 h，车间，车间管理费用为管理费用

21、为8080元元h h；乙车间每月可用的生产工时；乙车间每月可用的生产工时150h150h，车间，车间管理费用为管理费用为2020元元h h估计每台录音机利润为估计每台录音机利润为100100元，每台电视元，每台电视机利润为机利润为7575元，又估计下一年度内平均每月可销售录音机元，又估计下一年度内平均每月可销售录音机5050台，台，电视机电视机8080台。台。34甲车间甲车间乙车间乙车间检验销检验销售费用售费用单台单台利润利润预计月平均预计月平均销售量销售量电视机电视机1h3h30元元75元元80台台录音机录音机2h1h50元元100元元50台台每月可每月可用工时用工时120h150h车间管车

22、间管理费理费80元元/h20元元/h35工厂确定制订月度计划的目标如下：工厂确定制订月度计划的目标如下：第一优先级：检验和销售费每月不超过第一优先级：检验和销售费每月不超过46004600元：元：第二优先级：每月售出录音机不少于第二优先级：每月售出录音机不少于5050台；台；第三优先级：甲、乙两车间的生产工时得到充分利用第三优先级：甲、乙两车间的生产工时得到充分利用(重要性权系数按两个车间每小时费用的比例确定重要性权系数按两个车间每小时费用的比例确定)；第四优先级：甲车间加班不超过第四优先级：甲车间加班不超过2020小时；小时；第五优先级：每月销售电视机不少于第五优先级：每月销售电视机不少于8

23、080台；台；第六优先级：两个车间加班总时间要有控制第六优先级：两个车间加班总时间要有控制(权系数分权系数分配与第三优先级相同配与第三优先级相同)。试确定该厂为达到以上目标的最优月度计划生产数字。试确定该厂为达到以上目标的最优月度计划生产数字。36ex3.2 ex3.2 已知三个工厂生产的产品供应四个用户需要，各工厂已知三个工厂生产的产品供应四个用户需要，各工厂生产量、用户需求量及从各工厂到用户的单位产品的运输费生产量、用户需求量及从各工厂到用户的单位产品的运输费用如表用如表1 1所示：所示：用表上作业法求得最优调配方案如表用表上作业法求得最优调配方案如表2 2，总运费为，总运费为295029

24、50元但元但上述方案只考虑了运费为最少，没有考虑到很多具体情况和上述方案只考虑了运费为最少，没有考虑到很多具体情况和条件故上级部门研究后确定了制订调配方案时要考虑的七条件故上级部门研究后确定了制订调配方案时要考虑的七项目标，并规定重要性次序为：项目标，并规定重要性次序为：用户用户工厂工厂 1 2 3 4 1 2 3 4生产量生产量 1 12 23 3 5 2 6 7 5 2 6 7 3 5 4 6 3 5 4 6 4 5 2 3 4 5 2 3300300200200400400需求量需求量 200 100 450 250 200 100 450 250表表1 137 用表上作业法求得最优调配

25、方案如表用表上作业法求得最优调配方案如表2 2，总运费为，总运费为29502950元元但上述方案只考虑了运费为最少，没有考虑到很多具体情但上述方案只考虑了运费为最少，没有考虑到很多具体情况和条件故上级部门研究后确定了制订调配方案时要考虑况和条件故上级部门研究后确定了制订调配方案时要考虑的七项目标，并规定重要性次序为：的七项目标，并规定重要性次序为：用户用户工厂工厂 1 2 3 4 1 2 3 4生产量生产量 1 12 23 3虚设虚设 200 100 200 100 0 200 0 200 250 150 250 150 100 100 300300200200400400100100需求量需

26、求量 200 100 450 250 200 100 450 250表表2 238第一目标：第第一目标：第4 4用户为重要部门，需要量必须全部满足；用户为重要部门，需要量必须全部满足；第二目标：供应用户第二目标：供应用户1 1的产品中，工厂的产品中，工厂3 3的产品不少于的产品不少于100100单位；单位；第三目标：为兼顾一般，每个用户满足率不低于第三目标：为兼顾一般，每个用户满足率不低于8080；第四目标：新方案总运费不超过原方案的第四目标：新方案总运费不超过原方案的1010；第五目标：因道路限制，从工厂第五目标：因道路限制，从工厂2 2到用户到用户4 4的路线应尽量避免分的路线应尽量避免分

27、配运输任务；配运输任务；第六目标：用户第六目标：用户1 1和用户和用户3 3的满足率应尽量保持平衡；的满足率应尽量保持平衡；第七目标：力求减少总运费第七目标：力求减少总运费39第三专题：排队论第三专题：排队论（Queuing Theory）1 排队服务系统的基本概念排队服务系统的基本概念2 输入与服务时间的分布输入与服务时间的分布3 生灭过程生灭过程4 M/M/s等待制排队模型等待制排队模型5 M/M/s混合制排队模型混合制排队模型6 排队系统的优化排队系统的优化401 1 排队服务系统的基本概念排队服务系统的基本概念1.1 1.1 排队系统排队系统输入输入来源来源队队 列列服务机构服务机构排

28、队系统排队系统顾客顾客服务完离开服务完离开服务台服务台顾客到达顾客到达服务完离开服务完离开1 1个队列个队列1 1个服务台排队系统个服务台排队系统41服务台服务台1顾客到达顾客到达服务台服务台2服务台服务台s 服务完离开服务完离开1 1个队列个队列s s个服务台排队系统个服务台排队系统42服务台服务台1顾客到达顾客到达s s个队列个队列s s个服务台排队系统个服务台排队系统服务台服务台2服务台服务台s 服务完离开服务完离开43服务台服务台1顾客到达顾客到达服务完离开服务完离开多个服务台串联排队系统多个服务台串联排队系统服务台服务台2服务台服务台s44排队系统的三个基本组成部分排队系统的三个基本

29、组成部分.输入过程输入过程 (顾客按照怎样的规律到达顾客按照怎样的规律到达););排队及排队规则排队及排队规则 (顾客按照一定规则排队等待服务顾客按照一定规则排队等待服务););服务机制服务机制 (服务机构的设置服务机构的设置,服务台的数量及连接服务台的数量及连接形式（串或并）形式（串或并）,服务的方式（单个或成批接受服务）服务的方式（单个或成批接受服务）,服务时间分布等服务时间分布等)1.2 1.2 排队系统的描述排队系统的描述451.2.1 1.2.1 输入过程输入过程（1 1）顾客总体）顾客总体有限有限无限无限（2 2）达到方式）达到方式单个到达单个到达成批到达成批到达（3 3）顾客到达

30、时间）顾客到达时间 间隔的分布间隔的分布定长分布（定长分布（D D）:为确定值为确定值最简流（最简流（PoissonPoisson流）（流）（M M）:X:Xn n 独独立同负指数分布立同负指数分布461.2.2 1.2.2 排队及排队规则排队及排队规则（1 1）排队）排队有限排队有限排队无限排队：系统中空间无限，队列可以无限无限排队：系统中空间无限，队列可以无限 长，又称等待制排队系统。长，又称等待制排队系统。损失制排队系统：不允许排队损失制排队系统：不允许排队混合制排队系统：混合制排队系统：允许排队但不允许允许排队但不允许队列无限长队列无限长队长有限队长有限等待时间有限等待时间有限逗留时间

31、有限逗留时间有限47（2 2）排队）排队规则规则先来先服务（先来先服务（FCFSFCFS）后来先服务（后来先服务（LCFSLCFS）具有优先权服务（具有优先权服务（PSPS）481.2.3 1.2.3 服务机制服务机制（1 1）定长分布（）定长分布（D D）：每个顾客接受服务的时间是确定常数。）：每个顾客接受服务的时间是确定常数。（2 2）负指数分布（）负指数分布（M M）：每个顾客接受服务的时间相互独立，）：每个顾客接受服务的时间相互独立，具有相同的负指数分布。具有相同的负指数分布。（3 3）k k阶爱尔朗分布（阶爱尔朗分布（E Ek k）：每个顾客接受服务的时间相互独）：每个顾客接受服务的

32、时间相互独立，具有相同的负指数分布。立，具有相同的负指数分布。49ServerQueueArrivalKendallKendall记号记号X/Y/Z/A/B/C:X/Y/Z/A/B/C:顾客到达时间间隔分布顾客到达时间间隔分布/服务时间服务时间分布分布/服务台数目服务台数目/排队系统允许的最大顾客容量排队系统允许的最大顾客容量/顾客总体数顾客总体数量量/排队规则排队规则 1.3 1.3 排队系统的符号表示（排队系统的符号表示（KendallKendall记号）记号）M/M/1/M/M/1/FCFS/FCFS M/M/1 M/M/1/M:M:负指数分布负指数分布 (Markovian)(Mark

33、ovian)D:D:定长分布定长分布 (常数时间常数时间)E Ek k:k:k级级Erlang Erlang 分布分布G:G:普通的概率分布普通的概率分布 (任意概率分布任意概率分布)501.4 1.4 排队系统的主要数量指标和记号排队系统的主要数量指标和记号(1)(1)队长与排队长队长与排队长队长：系统中的顾客数队长：系统中的顾客数(排队等待的顾客数与正在接受服务排队等待的顾客数与正在接受服务 的顾客数之和的顾客数之和)。排队长：是指系统中正在排队等待服务的顾客数。排队长：是指系统中正在排队等待服务的顾客数。(2)(2)等待时间和逗留时间等待时间和逗留时间等待时间等待时间：从顾客到达时刻起到

34、他开始接受服务止这段时间。从顾客到达时刻起到他开始接受服务止这段时间。逗留时间逗留时间：从顾客到达时刻起到他接受服务完成止这段时间。从顾客到达时刻起到他接受服务完成止这段时间。51(3)(3)忙期、闲期和稳定状态忙期、闲期和稳定状态 忙期：指从顾客到达空闲着的服务机构起，到服务机构再忙期：指从顾客到达空闲着的服务机构起，到服务机构再次成为空闲止的这段时间。次成为空闲止的这段时间。稳定状态：当一个排队服务系统开始运转时，系统状态很稳定状态：当一个排队服务系统开始运转时，系统状态很大程度上取决于系统的初始状态和运转经历的时间，但过了一大程度上取决于系统的初始状态和运转经历的时间，但过了一段时间以后

35、，系统状态将独立于初始状态和经历的时间，此时段时间以后，系统状态将独立于初始状态和经历的时间，此时称系统处于稳定状态。称系统处于稳定状态。闲期：服务机构连续保持空闲的时间。闲期：服务机构连续保持空闲的时间。52N N：系统处于平稳状态时的队长：系统处于平稳状态时的队长,其均值为其均值为L L，称为平均队长；，称为平均队长；N Nq q：系统处于平稳状态时的排队长，其均值为：系统处于平稳状态时的排队长，其均值为L Lq q，称为平均排队，称为平均排队长；长；T T：系统处于平稳状态时顾客的逗留时间，其均值记为：系统处于平稳状态时顾客的逗留时间，其均值记为w w，称为，称为平均逗留时间；平均逗留时

36、间；T Tq q：系统处于平稳状态时顾客的等待时间，其均值记为：系统处于平稳状态时顾客的等待时间，其均值记为w wq q称为平称为平均等待时问；均等待时问；(4)(4)主要数量指标的常用符号主要数量指标的常用符号N(t)：时刻：时刻t t系统中的顾客数系统中的顾客数(又称为系统的状态又称为系统的状态)，即队长；，即队长；Nq(t):时刻时刻t t系统中排队的顾客数，即排队长；系统中排队的顾客数，即排队长；T(t)：时刻：时刻t t到达系统的顾客在系统中的逗留时间；到达系统的顾客在系统中的逗留时间；Tq(t):时刻时刻t t到达系统的顾客在系统中的等待时间。到达系统的顾客在系统中的等待时间。53

37、 当当n n为常数时，记为为常数时，记为；当每个服务台的平均服务率为常；当每个服务台的平均服务率为常数时，记为数时，记为，则当，则当n n s,有有n n=s。因此顾客相继到达的时。因此顾客相继到达的时间间隔为间间隔为1/1/,平均服务时间为平均服务时间为1/1/,令令=/s,为系统的为系统的服务强度。服务强度。n n:当系统处于状态当系统处于状态n n时，新来顾客的平均到达率时，新来顾客的平均到达率(单位时间内单位时间内来到系统的平均顾客数来到系统的平均顾客数)；n n:当系统处于状态当系统处于状态n n时，整个系统的平均服务率时，整个系统的平均服务率(单位时间内单位时间内可以服务完的顾客数

38、可以服务完的顾客数)；541.5 1.5 排队论研究的基本问题排队论研究的基本问题（1 1）通过研究排队系统主要数量指标在瞬时或平稳状态下的）通过研究排队系统主要数量指标在瞬时或平稳状态下的概率分布及其数字特征，了解系统运行的基本特征；概率分布及其数字特征，了解系统运行的基本特征；（2 2）统计推断问题，建立适当的排队模型是排队论研究的第）统计推断问题，建立适当的排队模型是排队论研究的第一步，建立模型过程经常会遇到如下问题：系统是否会达到一步，建立模型过程经常会遇到如下问题：系统是否会达到平稳状态；检验顾客相继到达时间间隔的相互独立性；确定平稳状态；检验顾客相继到达时间间隔的相互独立性；确定服

39、务时间的分布及有关参数。服务时间的分布及有关参数。（3 3）系统优化问题，又称为系统控制问题或系统运营问题，）系统优化问题，又称为系统控制问题或系统运营问题，其目的是使系统处于最优或最合理的状态。包括最少费用问其目的是使系统处于最优或最合理的状态。包括最少费用问题、服务率的控制问题、服务台的开关策略、顾客（或服务）题、服务率的控制问题、服务台的开关策略、顾客（或服务）根据优先权的最优排序问题。根据优先权的最优排序问题。552 2 输入与服务时间的分布输入与服务时间的分布2.1 2.1 最简单流（泊松流）最简单流（泊松流）最简单流：是指在最简单流：是指在t这段时间内有这段时间内有k个顾客到服务系

40、统的概率个顾客到服务系统的概率k k(t)(t)服从泊松分布服从泊松分布56(2)(2)无后效性：即在不相交的时间区间内到达的顾客数是相互无后效性：即在不相交的时间区间内到达的顾客数是相互独立的；独立的；(3)(3)普通性：指在足够小的时间区间内只能有一个顾客到达，普通性：指在足够小的时间区间内只能有一个顾客到达，不可能有两个以上的顾客到达。不可能有两个以上的顾客到达。(1)(1)平稳性：指在一定时间间隔内，来到服务系统有平稳性：指在一定时间间隔内，来到服务系统有k k个顾客的个顾客的概率仅与这段时间间隔长短有关，而与这段时间的起始时刻无概率仅与这段时间间隔长短有关，而与这段时间的起始时刻无关

41、；关；572.2 2.2 最简单流的性质最简单流的性质（1 1）参数）参数代表单位时间内到达顾客的平均数代表单位时间内到达顾客的平均数(数学期望数学期望)（2 2）在）在t,t+t,t+tt时间内没有顾客到达的概率为（时间内没有顾客到达的概率为（1-1-t t）（3 3）在）在t,t+t,t+tt时间内只有时间内只有1 1顾客到达的概率为（顾客到达的概率为（t t）58随机变量随机变量 T T：依次服务完毕离去的两个顾客的间隔时间：依次服务完毕离去的两个顾客的间隔时间f T(t)t2.3 2.3 负指数分布的服务时间负指数分布的服务时间59（1 1）负指数分布性质）负指数分布性质1 1若服务设

42、施对每个顾客的服务时间服从独立同负指数分布：若服务设施对每个顾客的服务时间服从独立同负指数分布：对每个顾客的平均服务时间为对每个顾客的平均服务时间为1/;在在t,t+t,t+tt时间内没有顾客离去的概率为（时间内没有顾客离去的概率为（1-1-t t）;在在t,t+t,t+tt时间内有时间内有1 1顾客离去的概率为（顾客离去的概率为（t t）;如果如果t t足够小的话，在时间足够小的话，在时间t,t+t,t+tt内有多于两个以内有多于两个以 上顾客离去的概率为上顾客离去的概率为0 0（t t）;60fT(t)tttf fT T(t)(t)是一个严格下降函数是一个严格下降函数（2 2）负指数分布性

43、质）负指数分布性质2 261如果服务设施对顾客服务时间服从负指数分布，则不管如果服务设施对顾客服务时间服从负指数分布，则不管对某一个顾客的服务进行了多久，剩下来的服务时间的对某一个顾客的服务进行了多久，剩下来的服务时间的概率分布仍同原先一样的负指数分布。概率分布仍同原先一样的负指数分布。（3 3）负指数分布性质）负指数分布性质3 362若干独立的负指数分布的随机变量的最小值是负指数分布若干独立的负指数分布的随机变量的最小值是负指数分布T1(1)Tn(n)（4 4）负指数分布性质）负指数分布性质4 4 如果来到服务机构的有如果来到服务机构的有n类不同类型的顾客，每类顾客类不同类型的顾客，每类顾客

44、来到服务站间隔时间为具有参数来到服务站间隔时间为具有参数i i的负指数分布，则作为的负指数分布，则作为总体来讲，到达服务机构的顾客时间间隔仍为负指数分布总体来讲，到达服务机构的顾客时间间隔仍为负指数分布;如果一个服务机构中有如果一个服务机构中有S S个并联的服务设施，如各服务设个并联的服务设施，如各服务设施对顾客服务时间为具有施对顾客服务时间为具有的负指数分布，于是整个服务机的负指数分布，于是整个服务机构的输出就是一个具有参数构的输出就是一个具有参数S S的负指数分布。的负指数分布。63（5 5）负指数分布性质）负指数分布性质5 5 若按依次到达的时间间隔统计，顾客流服从负指数分布，若按依次到

45、达的时间间隔统计，顾客流服从负指数分布，则对同一顾客流若按单位时间到达的数量统计，它服从泊松则对同一顾客流若按单位时间到达的数量统计，它服从泊松分布。分布。当依次到达的顾客服从负指数分布时，则当依次到达的顾客服从负指数分布时，则t t时间区间内时间区间内无顾客到达的概率为：无顾客到达的概率为：所以泊松分布和负指数分布是对同一顾客流（无论到达所以泊松分布和负指数分布是对同一顾客流（无论到达或服务完毕离去）按不同方式进行统计得到的两种不同分布。或服务完毕离去）按不同方式进行统计得到的两种不同分布。642.4 K2.4 K阶阶ErlangErlang分布分布 k k个相互独立具有相同参数的负指数分布

46、的和的分布称个相互独立具有相同参数的负指数分布的和的分布称为为k k阶阶ErlangErlang分布。分布。一般假定组成一般假定组成k k阶阶ErlangErlang分布的分布的k k个负指数的参数均为个负指数的参数均为k,k,即对每个负指数分布的期望值均为即对每个负指数分布的期望值均为1/1/k,k,因而因而k k阶阶ErlangErlang分布的概率密度可表示为：分布的概率密度可表示为：653 3 生灭过程生灭过程3.1 3.1 生灭过程简介生灭过程简介 生灭过程是用来处理输入是最简单流，服务时间为负指生灭过程是用来处理输入是最简单流，服务时间为负指数分布这样一类最简单排队模型的方法。数分

47、布这样一类最简单排队模型的方法。设设N(t),tN(t),t0 为一个随机过程，若为一个随机过程，若N(t)N(t)的概率分布具有的概率分布具有以下性质：以下性质：(1)(1)假设假设N(t)=n,N(t)=n,则从时刻则从时刻t t起到下一个顾客到达时刻止的起到下一个顾客到达时刻止的时间服从参数为时间服从参数为n n 的负指数分布，的负指数分布，n=0,1,2,n=0,1,2,(2)(2)假设假设N(t)=n,N(t)=n,则从时刻则从时刻t t起到下一个顾客离去时刻止的起到下一个顾客离去时刻止的时间服从参数为时间服从参数为n n 的负指数分布，的负指数分布，n=0,1,2,n=0,1,2,

48、(3)(3)同一时刻只有一个顾客到达或离去。同一时刻只有一个顾客到达或离去。660213n-1n状态状态1 12 23 3n n0 01 12 2n-1n-1 n n就是系统处于就是系统处于N(t)N(t)时单位时间内顾客的平均到达率，时单位时间内顾客的平均到达率，n n则是单位时间内顾客平均离去率。则是单位时间内顾客平均离去率。生灭过程发生率图生灭过程发生率图67 稳定状态时稳定状态时 输入输入 =输出（状态平衡方程）输出（状态平衡方程）状态状态 平衡方程平衡方程 0 1P1=0P0 1 0P0+2P2=（1+1 1）P1 2 1P1+3P3 =（2+2 2）P2 n-1 n-2Pn-2+n

49、Pn =（n-1+n-1n-1）Pn-1 n n-1Pn-1+n+1Pn+1 =（n+n n）Pn 68可以推出：可以推出：如果令：如果令：则以上各式可以写为通式：则以上各式可以写为通式：因为：因为：故故694 4 M/M/s等待制排队等待制排队模型模型4.1 4.1 单服务台模型单服务台模型M/M/1/M/M/1/顾客相继到达时间服从参数为顾客相继到达时间服从参数为的负指数分布，服务时间的负指数分布，服务时间服从参数为服从参数为的负指数分布，系统空间无限，允许无限排队。的负指数分布，系统空间无限，允许无限排队。p pn n=PN=n(n=1,2,=PN=n(n=1,2,)为系统到达稳定状态后

50、队长为系统到达稳定状态后队长N N的概率的概率分布。分布。4.1.1 4.1.1 队长的分布队长的分布 是系统中至少有一个顾客的概率，也叫服务强度，反映是系统中至少有一个顾客的概率，也叫服务强度，反映系统繁忙程度。系统繁忙程度。704.1.2 4.1.2 几个主要数量指标几个主要数量指标(2)(2)排队长排队长(1)(1)队长队长71(3)(3)逗留时间逗留时间T T 可以证明可以证明顾客在系统中的停留时间顾客在系统中的停留时间T T服从参数为服从参数为（-）的负指数分布的负指数分布：顾客在系统中停留时间超过顾客在系统中停留时间超过t t 的概率为：的概率为：顾客在系统中停留时间少于顾客在系统