当前位置：文档之家 › 第11章 排队论

第11章 排队论

  • 格式：ppt
  • 大小：2.44 MB
  • 文档页数：60

下载文档原格式

  / 60

合集下载

第10章排队论随机服务系统(pdf 75)

第10章排队论随机服务系统(pdf 75)

4
随机服务过程
以单台服务系统、等待制、先到先服务为例讨论如下 顾客在系统中的总时长：逗留时间=等待时长+服务时长 等待时长与顾客到达率和服务时长有关
12 3
4
顾客 τ1 τ2 τ3
τ4
到达时刻
开始 服务时刻
w2 w3
服务
终结时刻
h1 h2 h3 空 h4
t
1 23
4
•τi , wi , hi 分别表示到达间隔时间，等待时间和服务时间
5
当服务台连续不断服务(即忙期）时，有如下关系：
wi+1+τi+1= wi+hi，（上图中τ4不属于这种情况）
wi+hi 表示了累计的未完成的服务时长，一般地有
w i+1
=
⎧ ⎨
w
i
⎩
+
hi − 0
τ i+1
if w i + hi − τ i + 1 > 0 if w i + hi − τ i + 1 ≤ 0
第十章 排队论—随机服务系统
随机服务系统 随机服务过程 服务时间与间隔时间 输入过程 生灭过程和纯增过程 M/M/n 损失制 M/M/n 等待制，无限源，无限容量 M/G/1 等待制，无限源，无限容量 特殊随机服务系统
1
随机服务系统
系统的输入与输出是随机变量
A.k.Erlang 于1909~1920年发表了一系列根据话务量计
• α(t) 代表时段(0, t)中累计到达顾客数
β(t) 代表时段(0, t)中累计接受服务的顾客数
γ(t) 代表时段(0, t)中累计服务完毕的顾客数（离去的顾客数）
运筹学课件第十章排队论

运筹学课件第十章排队论

第十章 排队论
第一节 引言
一、排队系统的特征及排队论 排队论研究排队系统的数学理论和方法， 是运筹学的一个重要分支。 排队问题表现：
到达的顾客 1、不能运转机器 2、病人 3、打电话 4、等待降落飞机 5、河水进入水库
要求的服务 修理 就诊 通话 降落 放水，调整水 位
服务机构 修理工人 医生 交换台 跑道指挥机构 水闸管理员
四、排队系统的主要数量指标和记号 描述一个排队系统运行状况的主要指标： 1、队长、排队长 队长：系统中的顾客数量（排队顾客+接受服务顾客）。
排队长：系统中的正在排队等待服务的顾客数量。
2、等待时间和逗留时间 等待时间：从顾客到达时刻起到他开始接受服务止这段时间 为等待时间。 逗留时间：从顾客到达时刻起到他接受服务完成这段时间为 逗留时间。
(i)队长有限：系统等待空间有限。 有限系统的空间为K, 顾客到达时的队长为L。若 L<K，则顾客进入队列等待服务，若L=K，则 顾客离去。 (ii) 等待时间有限： 顾客对等待时间具有不耐烦 性的系统。设最长等待时间是T0，某个顾客从 进入队列后的等待时间为 T。若T<T0，顾客继 续等待；若T=T0，则顾客脱离队列而离去。 (iii)逗留时间有限：等待时间与服务时间之和。
排队可以是人，也可以是物。 为了一致：将要求得到服务的对象统称为“顾客”，将提 供服务的服务者称为“服务员”或“服务机构”。
排队系统的一般描述; 顾客为了得到服务而到达系统，如果不能 立刻得到服务而又允许排队等待，则加入 等待队伍，待获得服务后离开系统。
顾客到达 队列 服务台 单服务台服务系统 服务完后离开

n 0
n ,n C 1 , 2 , 3 ,...... n u n p p , n 1 , 2 , 3 ,...... n 0
交通流理论排队论模型跟弛模型与交通波模型

交通流理论排队论模型跟弛模型与交通波模型


2.说明：排队等待的车辆从一开始起动,就产生了起 动波,该波以接近 的v f 速度向后传播。
交通运输与物流学院
29
交通流中观测的加速度
把速度简单地看成密度的函数v(k)，使得求解连续方程变得简单。 现实中交通流的平均速度v不可能瞬时地随密度发生变化，驾驶
员总是根据前方密度来调整车速
dv
k
dv
2
17
跟驰模型稳定性
多数个车辆在做跟驰运动时，一辆车状态的改变会导致其后续车 辆运行状态接二连三的改变，称为运行状态的传播
局部稳定 关注跟驰车对引导车运行波动的反应。如车头间距摆 动大则不稳定，摆动愈小则愈稳定
引导车向后面各车传播速度变化，如果速度振幅扩大，就是不稳 定，如果振幅衰减，就是渐近稳定
C T
Reuschel, Pipes
跟驰车辆的加速度与 两车速度差成比例
Chandler, Herman, Kometani and Sasaki
Gazis, Herman （跟驰模型一般形式）
m, l 的不同取值对应着不同的密度－速度关系模型
m=0, l=2, Greenshield; m=0, l=1, Grenberg 交通运输与物流学院
交通运输与物流学院
32
密度波模型
在交通流中存在密度不连续 的地方，密度在该处的移动
速度是C。单位时间内通过
断面A、B车辆数的差等于 断面内滞留的车辆数。
波阵面
(q q) q C(k k k)
C q k
C dq dk
交通运输与物流学院
33
密度波传播分析1
密度波描述了两种交通状态的转化过程，C代表转化的方向与进程
解这是一个M/M/1排队系统
第11章等候线模型

第11章等候线模型


泊松概率函数可以计算出在某个 时间段内，有x位顾客到达的概率。该 概率函数如下： (11-1) 式中， x----在此时间段内到达的人数; λ----每个时间段内到达的平均人数； e=2.718 28 e-λ的值可以利用计算器或通过书末附录B计 算得出。
假设伯格.度姆快餐店已经对相关的 顾客到达数据进行了分析，并得知平均每 小时到达的顾客人数为45人。也就是说， 平均1分钟内到达人数为λ =45名顾客/60 分钟=0.75名顾客/分钟。因此，我们可以 利用下面的泊松概率函数计算1分钟内有x 为顾客到达的概率：
11.2.1运行参数 我们可以用下述公式来计算到达服从 泊松分布、服务时间服从指数分布的单列 等候线的运行参数，其中， λ --每个时间段内到达的平均数（平 均到达率）； μ --每个时间段内服务的平均数（平 均服务率）； 1. 系统中没有任何个体的概率：
（11-4）
2等候线中个体的平均数：
(11-5)
• 11.1.4 排队原则 在描述等候线系统时，我们必须规定等待 中的个体按照什么方式等待服务。就伯格 度姆快餐店的等候线（推广到一般来讲，可 以是所有面向顾客的等候线）来说，我们是 以先到先服务的原则来安排等候服务的顾客 的，这种方式被称做FCFS排队原则。然而， 用些情况要求有不同的排队原则。如，人们 在等候电梯时，最后上电梯的人通常是最先 完成服务过程（即最先离开电梯）的人。还 有一些排队原则则是赋予等候个体优先次序， 然后为具有最高优先权的顾客最先提供服务。 在本章中，我们只讨论先到先服务的排队原 则为基础的等候线。
11.2.4改进等候线运作 等候线模型通常会显示出哪些运作参数需要改 善。然而，要就怎样改变等候线结构来改善运行参 数做出决策，必须依靠分析家的洞察力和创造力。 考察了等候线模型所提供的运行参数之后，伯 格.度姆快餐店的管理者认为有必要改善等候线的 运作从而减少顾客的等候时间。为了改善等候线的 运作，分析家们常常侧重于采用提高服务率的方法 。一般来讲，要提高服务率，需要做出下面一两种 改变： (1)通过创造性的设计变更或利用新技术来提 高平均服务率μ。 (2)增加服务渠道，这样能够使更多的顾客得 到即时服务。
运筹学排队论2

运筹学排队论2

现将上式参数 引入时间因素 t ,即将
换为 t ,得到
pn
(t)
(t)n
n!
et
,
t
0,
n
0,1,2,.
表示长为t的时间区间内到达n个顾客的概率为 pn (t) ,且服从泊松分布.这称为泊松流或泊松过 程或简单流. 设t时间内到达的顾客数为随机变量N(t),则有
E[N(t)] t, D[N(t)] t.
服务台
2.C个服务台,一个公共队伍
服务台1 服务台2 服务台C
3.C个服务台,C个队伍
服务台1 服务台2 服务台C
二.排队系统的三个组成部分
1.输入过程:指顾客按怎样的规律到达. ⑴顾客的总体数或顾客源:指可能到达服务机
构的顾客总数.顾客总体数可以是有限的,也可 以是无限的; ⑵顾客到达的类型:顾客是单个到达还是成批 到达; ⑶顾客相继到达时间间隔的分布,如按泊松 分布,定长分布还是负指数分布.
排队论的创始人是丹麦哥本哈根市电话局的 工程师爱尔朗(A.K.Erlang),他早期研究电话 理论,特别是电话的占线问题,就是早期排队 论的内容.
§2 排队论的基本概念
一.排队现象的共同特征:为了获得某种服务而 到达的顾客,如不能立即得到服务而又允许排 队等候,则加入等待的队伍,获得服务后离开.我 们把包含这些特征的系统称为排队系统. 排队系统的几种情况: 1.单服务台排队系统
例9.1 某仓库全天都可以进行发料业务，假设 顾客到达的时间间隔服从均值为1的负指数分 布现在有一位顾客正好中午12：00到达领料， 试求：
（1）下一个顾客将在下午1：00前到达的概率； （2）在下午1：00与2：00之间到达的概率： （3）在下午2：00以后到达的概率。
运筹学教材习题答案详解

运筹学教材习题答案详解

3
B1：2.0
3
需要量（套）
200
150
问怎样下料使得（1）用料最少；（2）余料最少．
【解】第一步：求下料方案，见下表。
方案
一
二
三
四
五
六
七
八
九
十
十一
十二
十三
十四
需要量
B1:2.7m
2
1
1
1
0
0
0
0
0
0
0
0
0
0
300
B2:2m
0
1
0
0
3
2
2
1
1
1
0
0
0
0
450
A1:1.7m
0
0
1
0
0
1
0
2
1
0
3
2
1
0
(2)
【解】最优解X＝（3/4，7/2）；最优值Z=－45/4
(3)
【解】最优解X＝（4，1）；最优值Z=－10
(4)
【解】最优解X＝（3/2，1/4）；最优值Z=7/4
(5) 【解】最优解X＝（3，0）；最优值Z=3
(6)
【解】无界解。
(7)
【解】无可行解。
(8)
【解】最优解X＝（2，4）；最优值Z=13
【解】设x1、x2、x3分别为产品A、B、C的产量，则数学模型为
1.3建筑公司需要用6m长的塑钢材料制作A、B两种型号的窗架．两种窗架所需材料规格及数量如表1－23所示：
表1－23窗架所需材料规格及数量
型号A
型号B
每套窗架需要材料
长度（m）
第十章 排队论(3)

第十章 排队论(3)


方案 将M/M/1模型应用于方案 计算 方案1 模型应用于方案1,计算 方案 模型应用于方案
方案 方案1 方案 分析: 服务代表的服务强度降至50%,使顾 分析 1. 服务代表的服务强度降至 使顾 客的平均等待时间达到0.25天(约2小时 顾客 小时). 客的平均等待时间达到 天 约 小时 需要等待1天方能得到维修的概率降至 天方能得到维修的概率降至6.7%. 需要等待 天方能得到维修的概率降至 可见,降低服务代表的工作强度能够很好地满 可见 降低服务代表的工作强度能够很好地满 足新标准. 足新标准
排队论的案例研究
Dupit公司的售后服务问题 公司的售后服务问题 具体的举措: 为达到新的服务标准,提出了四个 具体的举措 为达到新的服务标准 提出了四个 可选方案. 可选方案 1.降低服务代表的工作强度 这涉及简单地减 降低服务代表的工作强度,这涉及简单地减 降低服务代表的工作强度 少每个代表负责的设备台数及增加技术代表 的数量.从而提高服务水平 满足市场新需求 的数量 从而提高服务水平,满足市场新需求 从的案例研究
分析: 分析 1. 技术服务代表平均每天接到 个电话, 因此 技术服务代表平均每天接到3个电话 个电话 平均到达率 λ = 3. 2. 每个修理任务2小时 按一天 小时工作时算 每个修理任务 小时,按一天 小时工作时算, 小时 按一天8小时工作时算 平均服务率 即平均每天维修4 平均服务率 = 8/2 = 4. 即平均每天维修 台复印设备. 台复印设备 3. 服务强度ρ = λ/ = 75% 服务强度ρ 4. 一次维修一台设备 因此s = 1. 一次维修一台设备,因此 因此
方案 方案1 方案 分析: 分析 2. 降低服务代表的服务强度意味着需 要增加新雇员约 新雇员约5000名. 工资成本 要增加新雇员约 名 工资成本=2.7亿, 管 亿 理培训及设施配备所需费用=0.3亿. 总成本 理培训及设施配备所需费用 亿 总成本=3 亿. 总结: 方案1可很好地满足新标准的要求 可很好地满足新标准的要求,增加 总结 方案 可很好地满足新标准的要求 增加 成本3亿元 亿元. 成本 亿元
第11章制造业作业计划(2).

第11章制造业作业计划(2).

j
j 的紧后工序放入{
t }，使
t＝t＋1。
⑤ 若还有未安排的工序，转步骤②；否则，停止。
例 11.4 有一个 2/3/G/Fmax 问题，其加工描述矩阵 D 和加工时间矩阵 T 分别为：
1,1,1 1,2,3 1,3,2 D＝
2,1,3 2,2,1 2,3,2
241 T＝
345
试构成一个能动作业计划。
既然优先调度法则中的一些法则对一定的目标函数的效果明显地比其它法则好，我们为 什么不能运用这些法则来影响随机抽样呢？显然，如果我们把除 RANDOM 法则以外的某个法 则对一个问题使用多次，也只能得到一种作业计划。这样做毫无意义。但是， 我们可以给不 同的工序按某一优先调度法则分配不同的挑选概率， 这样就可以得到多个作业计划供比较。 例如，在构在无延迟作业计划的第③步有 3 道工序，A、B 和 C 可挑选，这 3 道工序所需的时 间分别为 3，4 和 7。如果按 RANDOM 法则，每道工序挑选上的概率都是 1／3；如果按 SPT 法则，则只能挑选工序 A，不可能产生多个作业计划。现按目标函数的要求，选择了 SPT 法 则。按概率调度法，将这 3 道工序按加工时间从小到大排列，然后给每道工序从大到小分配一 个被挑选的概率，比如 A、B 和 C 的挑选概率分别为 6／14、5／14 和 3／14。这样，既保证 了 SPT 法则起作用，又可产生多个作业计划供挑选。
作业计划(non-delay schedule)是没有任何延迟出现的能动作业计划。所谓“延迟”，指有工件
等待加工时，序。
能动作业计划和无延迟作业计划在研究一般单件作业排序问题时有重要作用。下面先介
绍它们的生成方法。为此，先作一些符号说明。
我们称每安排一道工序称作一“步”，设
第10章：排队论

第10章：排队论

泊松分布
⑴在不相重叠的时间区间内顾客到达数是相互独立的，即无后效性。 ⑵对充分小的∆t，在时间区间[t，t+∆t)内有1个顾客到达的概率与t无关 ，而与区间长∆t 成正比，即P1(t，t+∆t)=λ∆t+o(∆t)。 ⑶对充分小的∆t，在时间区间[t，t+∆t)内有2个或2个以上顾客到达的概 率极小，以致可以忽略，即∑P2(t，t+∆t)=o(∆t)。
⎧ Pn (0 ) = 0 ⎪ = − λ Pn (t ) + λ Pn − 1 (t ) ⎨ dP n (t ) ⎪ dt ⎩ (λ t )n e − λ t t Pn (t ) = n! n = 0 ,1, 2
n=0
⎧ P0 (0 ) = 1 ⎪ ⎨ dP 0 (t ) = − λ P0 (t ) ⎪ dt ⎩
– 队长没有限制，n=0, 1,2, … – 队长有限制，最大数为N时， n=0,1,2, …,N – 即时制，服务台个数为c时， n=0,1,2,…,c。
Pn(t)
在时刻t、系统状态为n的概率 表示为：Pn(t) Pn(t)与t、n的关系式是关于t的 微分方程，关于n的差分方程 Pn(t)与t、n的关系方程的解称 为瞬态（过渡状态） 我们通常求稳态概率Pn，即求 Pn(t)的极限或令Pn’(t)=0
2007-6-14 23
系统状态概率
Pn (t + Δt ) = PA (t + Δt ) + PB (t + Δt ) + PC (t + Δt ) + PD (t + Δt ) = Pn (t )(1 − λΔt )(1 − μΔt ) + Pn +1 (t ) μΔt + Pn −1 (t )λΔt + ο (Δt ) Pn (t + Δt ) − Pn (t ) ο (Δt ) = λPn −1 (t ) + μPn +1 (t ) − (λ + μ ) Pn (t ) + Δt Δt 令Δt → 0 dPn (t ) = λPn −1 (t ) + μPn +1 (t ) − (λ + μ ) Pn (t ) n = 1,2, dt 当n = 0时， dP0 (t ) = −λP0 (t ) + μP (t ) 1 dt
运筹学-第十章-排队论

运筹学-第十章-排队论

一般来说，排队论所研究的排队系统中，顾客到来的时 刻和服务台提供服务的时间长短都是随机的，因此这样 的服务系统被称为随机服务系统
小结
排队系统又称随机服务系统 ① 有请求服务的人或物； ② 有为顾客服务的人或物； ③ 顾客到达时间与接受服务时间是随机的。
结构： 顾客到达 ----- 排队 ------ 服务机构服务 ------ 顾客离去
类似地还可画出许多其他形式的排队系统，如串并混联的 系统，网络排队系统等
尽管各种排队系统的具体形式不同，但都可以由图10-5 加以描述
图10-5 随机服务系统
通常称上图表示的系统为一随机聚散服务系统，任一排队系 统都是一个随机聚散服务系统。 这里，“聚”表示顾客的到达，“散”表示顾客的离去。
所谓随机性则是排队系统的一个普遍特点，是指顾客的 到达情况(如相继到达时间间隔)与每个顾客接受服务的时 间往往是事先无法确切知道的，或者说是随机的。
II
在排队系统中，忙期和闲期总是交替出现的。
3、其他相关指标
(1)忙期服务量：指一个忙期内系统平均完成 服务的顾客数；
(2)损失率: 指顾客到达排队系统，未接受服务 而离去的概率;
（对损失制或系统容量有限而言） (3)服务强度： = /s ；
根据前面的约定，我们将主要分析系统的平稳分布。于是记： Pn ：当系统达到统计平衡时处于状态n的概率（pn(t)）
② 等待时间有限。即顾客在系统中的等待时间不超过 某一给定的长度T，当等待时间超过T 时，顾客将自动 离去，并不再回来。 如顾客到饭馆就餐，等了一定时间后不愿再等而自动 离去另找饭店用餐。
③ 逗留时间(等待时间与服务时间之和)有限。例如 用高射炮射击敌机，当敌机飞越高射炮射击有效区 域的时间为t 时，若在这个时间内未被击落，也就不 可能再被击落了。
第十章 物流运筹学——排队论

第十章 物流运筹学——排队论


2．排队问题解决 （1）排队问题分析。将每次到达的药品看作一 个客户，每次到达的药品可能有一个品规也可能 有多个品规，每个品规验收员都要进行验收。由 于国药集团医药控股沈阳有限公司物流中心的供 应商分布在全国各地，没有关联性药品到达相互 独立。验收的服务时间由于到达货物的品规数， 到货包装破损情况，药品剂型等的不同每个客户 的验收时间也不同，客户的服务时间可能服从负 指数分布。 （2）客户到达服务观察。从4月12日到7月12 日62个工作日中利用随机抽样原则随机抽取了10 天进行观察，记录每天9个时段内客户到达的数量。
c
ρ
P0
Pc
D
4 0.75 0.0377 0.1272 0.5090
5 0.6 0.0466 0.0945 0.2363
6 0.5 0.0489 0.0495 0.0990
7 0.43 0.0495 0.0215 0.0377
可见，应设置7个站台。
M / M / c / ∞ 排队系统模型（
λ
0 1
案例分析
以国药集团医药控股沈阳有限公司在验收服务 设施配置中的应用，给出排队模型，说明排队理论 在实际当中的应用情况。 • 国药集团医药控股沈阳有限公司物流中心每天 要验收大量的货物，货物到达后需要签收、验收、 入库。现验收组有两人，验收员和理货员各一人， 从2004年4月开始由于到货量增加，验收出现不及 时，经常被内部客户投诉。物流中心为提高客户服 务水平，需要增加验收服务能力，为此需要对验收 排队服务进行以下数量分析作为决策依据。 1．决策目标 （1）降低客户等待时间； （2）降低作业成本。 •
实训设计
• 【实训目标】 实训目标 掌握 M / M / c （包括 c =1）排队模型的各项系 统指标的求解方法。 • 【实训内容与要求 实训内容与要求】 在企业内或流通环节中调查数据，并以此建 立数学模型，利用排队模型计算得出的各项系统 指标来具体分析系统的结构，以获得更好的效益。 • 【成果与检验 成果与检验】 能够建立相应的排队模型，利用以给出的系 统指标公式，给出系统的量化结果。

第十章 排队论(2)


Poisson流（Poisson过程）
定义 满足以下四个条件的输入流称为 Poisson流（Poisson过程）
3、普通性：同一时刻只有一个顾客到达或 离去.
4、有限性：任意有限个区间内到达有限个 顾客的概率之和等于1。Poisson流与Poisson分布
定理 对于一个参数为的Poisson流，在[0， t]内到达k个顾客的概率为
[M/M/1]:[//FCFS]的系统指标

顾客在在系统中的逗留时间T,可说明它服 从参数为-的负指数分布*,即
P{ T > t } = e -(-)t

t0
顾客在在系统中的等待时间T’,有
P{ T’ > t } = e -(-)t
t0
例11-1 高速公路入口收费处设有一个收费通道，汽 车到达服从Poisson分布，平均到达速率为100辆／ 小时，收费时间服从负指数分布，平均收费时间为 15秒／辆。求 1.收费处空闲的概率P0；
k 1 k 1 k 1
ρ2 ρ2 λ2 (1 ρ) 2 (1 ρ) 1 ρ μ(μ λ)
[M/M/1]:[//FCFS]的系统指标
平均逗留时间W
N λW N q λWq
N 1 W λ μλ
平均等待时间Wq
λ Wq λ μμ λ Nq
第十章 排队论
顾客到达和服务的时间分布
Poisson流（Poisson过程）
定义 满足以下四个条件的输入流称为Poisson 流（Poisson过程）
1、平稳性：在时间区间[t, t+t)内到达k个顾 客的概率与t无关，只与t有关。记为pk(t）。
2、无后效性：不相交的时间区间内到达的顾 客数互相独立。

第10章 排队论 《运筹学》PPT课件全


WL
Wq
Lq
W
1
M/M/s 混 合 制 排 队 模 型
一、 单服务台混合制模型
M/M/1/K： 顾客的相继到达时间服从参数 为λ的负指数分布(即顾客的到达过程为 Poisson流)，服务台个数为1，服务时间V 服从参数为μ的负指数分布，系统的空间 为K。
单
平稳状态下队长N的分布pn=P{N=n},n=0,1,2,…。
服
由于所考虑的排队系统中最多只能容纳K个顾 客(等待位置只有K-1个)，因而有
务 台
n
0
n
n=0,1,2,...,K-1 n≥K n=1,2,...K
混 合
有
Cn
(
)n
n
n=0,1,2,...,K
0
n>K
制
故 pn n p0 n=1,2,…,K
模 型
1
其中，p0
1
1
K
n
1
K
1
1
n1
统
其分布函数为B(t)，密度函数为b(t)，则
的
常见的分布有： (1) 定长分布(D)
描
(2) 负指数分布(M)
述
(3) k阶爱尔朗分布(Ek)：
排
排队系统的符号表示
队
“Kendall记号”，其一般形式为：X/Y/Z/A/B/C，其中 XX：顾客到达时间间隔的分布
系
YY：服务时间的分布
统
Z Z：服务台个数
的
A ：系统容量 B B：顾客源数量
符
C C：服务规则
号
例 （M / M / 1 /
FCFS）表示：
表
到达间隔为负指数分布，服务时间也为负指数分 布，1个服务台，顾客源无限，系统容量也无限，

运筹学第3版熊伟编著习题答案

最优解X=<30000,0,66000,0,109200,0>；Z＝84720
1.5炼油厂计划生产三种成品油,不同的成品油由半成品油混合而成,例如高级汽油可以由中石脑油、重整汽油和裂化汽油混合,辛烷值不低于94,每桶利润5元,见表1－26.
表1－26
成品油
高级汽油
一般汽油
航空煤油
一般煤油
半成品油
中石脑油
基本最优解 ,最优解的通解可表示为 即
〔4〕
[解]单纯形表：
C<j>
3
2
1
0
0
R. H. S.
Ratio
Basis
C<i>
X1
X2
X3
X4
X5
X4
0
5
4
6
1
0
25
5
X5
0
[8]
6
3
0
1
24
3
C<j>-Z<j>
3
2
1
0
0
0
X4
0
0
1/4
33/8
1
-5/8
10
X1
3
1
3/4
3/8
0
1/8
3
C<j>-Z<j>
方案四：在三年内投资人应在第三年年初投资,一年结算一次,年收益率是30％,这种投资最多不超过1万元．
投资人应采用怎样的投资决策使三年的总收益最大,建立数学模型.
[解]是设xij为第i年投入第j项目的资金数,变量表如下
项目一
项目二
项目三
项目四
第1年
第2年

运筹学第3版熊伟编著习题答案（PDF版）

运筹学（第3版）习题答案第1章线性规划P36第2章线性规划的对偶理论P74第3章整数规划P88第4章目标规划P105第5章运输与指派问题P142第6章网络模型P173第7章网络计划P195第8章动态规划P218第9章排队论P248第10章存储论P277第11章决策论P304第12章多属性决策品P343第13章博弈论P371全书420页第1章线性规划1.1工厂每月生产A、B、C三种产品,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表1－23所示．表1－23产品资源材料(kg)设备(台时)利润(元/件)A1.5310B1.21.614C41.212资源限量25001400根据市场需求,预测三种产品最低月需求量分别是150、260和120,最高月需求是250、310和130.试建立该问题的数学模型,使每月利润最大．【解】设x1、x2、x3分别为产品A、B、C的产量，则数学模型为max Z=10x1+14x2+12x3⎧1.5x1+1.2x2+4x3≤2500⎪3x+1.6x+1.2x≤140023⎪1⎪⎪150≤x1≤250⎨⎪260≤x2≤310⎪120≤x3≤130⎪⎪⎩x1,x2,x3≥01.2建筑公司需要用5m长的塑钢材料制作A、B两种型号的窗架．两种窗架所需材料规格及数量如表1－24所示：每套窗架需要材料表1－24窗架所需材料规格及数量型号A型号B 长度（m）A1：2A2：1.5需要量（套）数量(根)23300长度(m)B1：2.5B2：2400数量(根)23问怎样下料使得（1）用料最少；（2）余料最少．【解】第一步：求下料方案，见下表。

方案B1B2A1A22.5221.5一2000二三四五六七八九十需要量110010101001020001100102002010012000030.58001200600900余料(m)00.50.51110第二步：建立线性规划数学模型设x j （j =1,2,…，10）为第j 种方案使用原材料的根数，则（1）用料最少数学模型为min Z =∑xjj =110⎧2x 1+x 2+x 3+x 4≥800⎪⎪x 2+2x 5+x 6+x 7≥1200⎪⎨x 3+x 6+2x 8+x 9≥600⎪x +2x +2x +3x ≥9007910⎪4⎪⎩x j ≥0,j =1,2,L ,10（2）余料最少数学模型为min Z =0.5x 2+0.5x 3+x 4+x 5+x 6+x 8+0.5x10⎧2x 1+x 2+x 3+x 4≥800⎪⎪x 2+2x 5+x 6+x 7≥1200⎪⎨x 3+x 6+2x 8+x 9≥600⎪x +2x +2x +3x ≥9007910⎪4⎪⎩x j≥0,j =1,2,L ,101.3某企业需要制定1～6月份产品A 的生产与销售计划。

运筹学教材习题答案详解

X(2)=( 0 ,450 ,0 ,0,0 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料650根
显然用料最少的方案最优。
1.4A、B两种产品，都需要经过前后两道工序加工，每一个单位产品A需要前道工序1小时和后道工序2小时，每一个单位产品B需要前道工序2小时和后道工序3小时．可供利用的前道工序有11小时，后道工序有17小时．
3
B1：2.0
3
需要量（套）
200
150
问怎样下料使得（1）用料最少；（2）余料最少．
【解】第一步：求下料方案，见下表。
方案
一
二
三
四
五
六
七
八
九
十
十一
十二
十三
十四
需要量
B1:2.7m
2
1
1
1
0
0
0
0
0
0
0
0
0
0
300
B2:2m
0
1
0
0
3
2
2
1
1
1
0
0
0
0
450
A1:1.7m
0
0
1
0
0
1
0
2
1
0
3
2
1
0
《运筹学》
第1章线性规划
第2章线性规划的对偶理论
第3章整数规划
第4章目标规划
第5章运输与指派问题
第6章网络模型
第7章网络计划
第8章动态规划
第9章排队论
第10章存储论
第11章决策论
第12章对策论
习题一
1.1讨论下列问题：
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

1.最简单流（泊松分布）
最简单流的一些性质： （1）参数λ代表单位时间内到达顾客的平均数 证 由于考虑单位时间，取t=1，其数学期望为： k k 1 e kPk (1) ke
k 0 k 0
k!
k 1
(k 1)!
（2）在[t,t+Δt] 没有顾客到达的概率为1-λΔt +o(Δt)
S3 S5
(d)单队多台串联
(e)多台混合
11.1.3 排队系统模型的分类
肯德尔（Kendall）于1953年提出了排队服务系统的分类记号 ： 输入/输出/并联的服务站数 1971年国际排队符号标准会上肯德尔将上述分类记号扩充到六项，记 为：输入/输出/并联的服务站数/系统容量（队长）/系统状态（顾客源数） /服务规则
t t 证 在 [t,t+Δt]内恰好有1个顾客到达的概率为 P ，将 e ( t ) e t 1 的麦克劳林级数代入，结论得证。
11.1.2 排队系统的三个特征
2．排队规则 排队规则指到达排队系统的顾客按怎样的规则排队等待。 （1）按顾客到达排队系统时发现服务设施已被占用是否离去可分为损失制， 等待制和混合制三种。当顾客到达时，所有的服务台均被占用，顾客随即 离去，称为损失制（或称即时制、消失制）；当顾客到达时，所有的服务 台均被占用，顾客就排队等待，直到接受完服务才离去，称为等待制，例 如出故障的机器排队等待维修就是这种情况；介于损失制和等待制之间的 是混合制。 对于等待制，有下列服务规则：先到先服务（FCFS） 、先到后服务 （LCFS） 、带优先服务权（PR） 、随机服务（SIRO）等。 在后面研究的问题中均假设采取FCFS服务规则。 （2）按队列长度是否有限，可分为队长有限和队长无限两种情况。在限度 以内就排队等待，超过一定限度就离去。 （3）按排队方式分为单列、多列。对于多列排队的顾客有的可以相互转移， 有的则不能（用栏杆等隔开）；有的排队顾客因等候时间过长而离开，有 的则不能（如在高速公路行驶的汽车必须坚持到高速出口）。我们所讨论 的问题限制在队列间不能相互转移，中途不能退出的情形。
11.1.4 排队系统的主要性能指标
求解排队问题的目的，是研究排队系统运行的效率，估计服务质量，确 定系统参数的最优值，以决定系统结构是否合理、研究设计改进措施等。 因此必须确定用以判断系统运行优劣的基本数量指标。 1．常用指标 （1）队长（Ls）和排队长（Lq）：队长指系统内顾客数，包括正在接 受服务的顾客与排队等待服务的顾客数（排队长），即 系统中的顾客数=排队等候服务的顾客数 + 正在接受服务的顾客数 （2）逗留时间（Ws）和等待时间（Wq）：逗留时间指顾客在排队服 务系统中从进入到服务完毕离去的平均逗留时间；等待时间指顾客排队 等待服务的平均等待时间。这对顾客来讲是最关心的，每个顾客希望逗 留时间或等待时间越短越好。 （3）服务机构工作强度：指服务机构累计的工作时间占全部时间的比 例，是衡量服务机构利用效率的指标。即： 服务机构 用于服务顾客的时间 服务设施总的空闲时间 1 工作强度 服务设施总的服务时间 服务设施总的服务时间
基本概念 系统、特征、分类、指标、输入输出
Kendall 标志：输入/输出/服务台数/队长/顾客源
单服务台排队系统 M/M/1/∞/∞：M/M/1/N/∞；M/M/1/∞/m 生死过程 (方法论) 多服务台排队系统 M/M/s/∞/∞：M/M/s/N/∞；M/M/s/∞/m 其他排队系统 M/G/1；M/D/1 系统运行指标 Ls,Lq,Ws,Wq
11.1.1 排队系统的一般表示
11.1.2 排队系统的三个特征
排除系统的三个特征是指：输入过程、排队规则、服务机构。 1．输入过程 输入是指顾客到达服务系统的情况。可能有下列情况，但并不相互排斥： （1）按顾客源总数划分为有限和无限两大类。如工厂需要检修的机器是有 限的，准备进京观光旅游的游客是无限的。 （2）按顾客到达的人数可以划分为单个到达和成批到达。如到超市购买商 品的顾客是单个的，到港国际航班等待安检的旅客是成批的。 （3）按顾客到达时间间隔是否固定可以划分为确定型和随机型。如定期运 行的班车、班轮、班机是确定的，到加油站加油的汽车是随机的。对随机 的顾客到达需要知道单位时间到达的顾客数或时间间隔的概率分布。 （4）按接受过服务的顾客对顾客到达数是否有影响，划分为相互独立到达 和非相互独立到达。如提供优质服务的餐饮业所产生了大量“回头客”， 就属于非相互独立到达。我们只讨论独立到达情况。 （5）按顾客相继到达间隔时间的分布及其数字特征是否与时间有关可分为 平稳与非平稳的。相继到达的间隔时间分布及其数学期望、方差等数字特 征都与时间无关，称为平稳的，否则是非平稳的。一般非平稳情况的数学 处理很困难，我们只讨论平稳状况。
导入案例：主任医师招聘问题
此类排队现象在日常生活中经常遇到，如客户到银行排队办理存贷款业 务，出纳员为客户提供服务；汽车到加油站排队，加注系统为汽车提供 加油服务；超市顾客到收银台前排队，收款员为顾客提供交款服务；旅 客到公交车站排队，公交车为旅客提供位移服务。 排队论的基本思想是1910年丹麦电话工程师A.K.埃尔朗在解决自动电 话设计问题时开始形成的，当时称为话务理论。他在热力学统计平衡理 论的启发下，成功地建立了电话统计平衡模型，并由此得到一组递推状 态方程，从而导出著名的埃尔朗电话损失率公式。 自20世纪初以来，电话系统的设计一直在应用这个公式。20世纪30年 代前苏联数学家欣钦把处于统计平衡的电话呼叫流称为最简单流；瑞典 数学家巴尔姆又引入有限后效流等概念和定义；美国数学家费勒 (W.Feller)关于生灭过程的研究；20世纪50年代初，英国数学家D.G.肯 德尔提出嵌入马尔可夫链理论，以及对排队队型的分类方法，为排队论 奠定了理论基础；20世纪70年代以来，人们开始研究排队网络和复杂 排队问题的渐近解等，成为研究现代排队论的新趋势。
第11章 排队论
重庆三峡学院 关文忠 /guanwenzhong
教学目标与要求
【教学目标】 1．理解下列基本概念：排队系统构成、特征、分类、主要性能指标及相互关系 2．掌握以下三种排队系统主要性能指标的计算：M/M/C/∞/∞；M/M/C/N/∞； M/M/C/∞/m。 3．了解M/G/1、M/D/1的主要指标计算公式 【知识结构】
11.1.2 排队系统的三个特征
3．服务机构 从机构形式和工作情况来看有以下几种： （1）服务机构可以没有服务员，也可以有一个或多个服务员 （服务台、窗口）。如超市的货架可以没有服务员，但交款时可 能有多个服务员。 （2）多个服务台的情况中，可以是平行排列的（并联），也可 以是前后排列的（串联），也可以是混合的。 （3）服务方式可以对单个顾客进行，也可成批进行。我们只讨 S1 S1 论单个服务情况。 S S2 S2 （4）服务时间可分为确定型的和随机型的。如旅客列车对乘客 S3 S3 的服务是按列车时刻表进行位移服务的，是确定型的；因患者病 (a)单台单队 (b)多队多台并联 (c)单队多台并联 情不同，医生诊断的时间不是确定的，是随机型的。 S1 S4 （5）服务时间的分布总假定是平稳的，即分布的期望值、方差 S1 S2 S2 等参数不受时间的影响。
本章主要内容
11.1 基本概念 11.1.1 排队系统的一般表示 11.1.2 排队系统的三个特征 11.1.3 排队系统模型的分类 11.1.4 排队系统的主要性能指标 11.1.5 排队系统的输入和输出 11.2 生死过程 11.3 单服务台排队系统模型 11.3.1 M/M/1/∞/∞（标准系统） 11.3.2 M/M/1/N/∞（系统容量有限） 11.3.3 M/M/1/∞/m（顾客源有限） 11.4 多服务台排队系统模型 11.4.1 M/M/s/∞/∞系统 11.4.2 M/M/s/N/∞系统 11.4.3 M/M/s/∞/m系统
模型的优化（目的）
导入案例：主任医师招聘问题
某三甲医院肝胆内科有主任医师1名，由于他的存在而使前来诊疗的患 者大增。根据一个月的统计，平均每h到达医院的患者6名，并对各时 间段统计，经回归符合泊松分布；该医生每h可诊疗4名，但患者病情 不同，分布也不是均匀的，对每位患者就诊时间的统计，经回归，符合 指数分布。 医院配备有电子回馈信息系统，及时观察到已挂号排队等候的患者数量。 当排队等候人数少于5人时，挂号系统可以挂号。当前来就诊的患者挂 上号若医生空闲则可直接就诊，否则排队等候。医生采取先到先服务的 规则。若前来就诊的患者挂不上号，则立即到邻近的一家医院就诊。 经统计，经该主任医师诊疗的患者，其诊疗费、检验费、医药费等医院 可获纯收入100元；主任医师可高薪聘请，其薪金及住房和各种福利年 均25万元，医院实行每周5天工作制，年工作日250天，平均每天支付 1000元的成本。当医生过少，由于患者得不到服务离去而产生的损失 增加；当医生过多，由于医生空闲时间的增加也使医院的成本增加。问： 医院应招聘多少名肝胆内科主任医师可使得盈利最大？
1.最简单流（泊松分布）
最简单流需要满足以下三个条件： （1）平稳性 指在一定时间间隔内，来到服务系统有k个顾客的概 率仅与这段时间间隔的长短有关，而与这段时间的起始时刻无关； （2）无后效性 指在不相交的时间区间内到达的顾客数是相互独 立的，或者说在区间[a, a+t]来到k个顾客的概率与时间a之前来到 多少个顾客无关； （3）普通性 指在足够小的时间区间内只能有一个顾客到达，不 可能有两个以上顾客同时到达。
11.5 其他排队系统模型 11.5.1 一般服务时间M/G/1模型 11.5.2 定长服务时间M/D/1模型 11.5.3 埃尔朗服务时间M/Ek/1 模型 11.5.3 具有优先服务权的排队 模型 11.6 排队系统的优化 11.6.1 M/M/1模型中的最优服务 率 11.6.2 M/M/s模型中的最优服务 台数 本章小结
Ls Ws , 或Ws Ls

Lq Wq ,
Ws Wq Βιβλιοθήκη 或Wq Lq