管理运筹学 课件 田世海 第11、12章 有约束非线性规划、排队论

1OperationalResearch

运筹学2Chapter11第11章ConstrainedOptimization约束极值问题OperationalResearchNonlinearProgramming非线性规划3ConstrainedOptimization约束极值及最优性条件不等式约束一般约束问题主要内容等式约束约束极值问题的算法内点法乘子法外点法41、约束极值问题的表示一、约束极值问题的最优性条件562约束极值及最优性条件——Kuhn-Tucker条件（1）等式约束性问题的最优性条件

考虑minf(x)s.t.h(x)=0

回顾高等数学中所学的条件极值：

问题求z=f(x,y)极值，在ф(x,y)=0的条件下。即：minf(x,y)s.t.ф(x,y)=0

引入Lagrange乘子：λ

Lagrange函数L(x,y;λ)=f(x,y)+λф(x,y)7若x*是其的最优解,则存在υ*∈Rl

使8

几何意义：考虑一个约束的情况：x'

最优性条件即：9(2)不等式约束极值问题的最优性条件可行方向:①可行方向与积极约束:10积极约束:例:或起作用约束（紧约束\积极约束\有效约束）。11②如何判断一个方向是可行方向?12证明:定理1:可行下降方向:13定理2:定理3:证略③极值点的必要条件:1415161718定理4(K-T条件):192021222324252627282930313233作业:

求约束极值问题34353637（一）惩罚函数法（SUMT）二、约束极值问题的算法

将有约束优化问题转化为一系列无约束优化问题进行求解。（SequentialUnconstrainedMinimizationTechnique-SUMT）1、算法思想：2、算法类型：

外点法（外惩法）内点法（内惩法）383、问题：394、外点法（外部惩罚函数法）40414243（1）几何解释44（2）算法步骤（外点法）：45yesNo（3）外点法框图46（4）应注意的问题47例:

484950

（5）一般模型的外点法

算法步骤相同51例:

525354555、内点法（闸函数法、障碍函数法）（1）集合结构56（2）算法思想

内点法（障碍函数法）的迭代点是在可行域点集内部移动的，对接近可行域边界上的点施加越来越大的惩罚，对可行域边界上的点施加无限大的惩罚，这好比边界是一道障碍物，阻碍迭代点穿越边界。

内点法要求可行点集的内点集合非空，否则算法无法运行。这样一来内点法只对不等式约束的优化问题才可能有效。57（3）算法分析5859（4）算法步骤（内点法）：60内点法框图yesNo61例解6263例解6465例解66（5）罚函数法的缺点67(6)内、外点法的优缺点的比较1.x(0)∈S02.等式约束不适用3.障碍函数B(x)在S0的可微阶数与gi(x)相同(可选用的无约束最优化方法广)4.迭代中x（k）∈R

（随时可取x（k）≈x*）5.非凸规划适用1.任意x(0)∈Rn2.等式约束适用3.惩罚项的二阶偏导在S的边界上不存在4.5.非凸规划适用内点法外点法迭代中x（k）RÏ686.乘子法乘子罚函数:乘子罚函数与Langrange函数及惩罚函数的区别：多一项。

(1)等式约束69乘子罚函数:70(2)等式、不等式约束71算法步骤（乘子罚函数法）：72解：1.惩罚函数法。对于惩罚函数例：问题的最优解为x*=(0.25,0.75),分别用惩罚函数法和乘子法求它的迭代点列。

可求得最优解为：

2.乘子法。对于乘子罚函数73可求得最优解为：74

从表中可见，xk*比

xk近于x*的速度慢得多，用乘子法迭代6次就达到惩罚函数法迭代15次的效．这里，惩罚因子在惩罚函数法中要增大到u15＝3276.8，而在乘子法中只要增大到u6=6.4．相比之下，乘子法不需过分地增大惩罚因子，确实比惩罚函数法有效很多.OperationalResearch

运筹学

第三章

排队论本章要点：

1.排队系统的组成；

2.排队模型的研究方式；

3.典型排队系统模型结构及应用。

内容框架：输入过程排队规则服

务

台排队系统符号表示研究方式

明确系统意义

画状态转移速度图→

状态概率方程

计算基本数量指标

应用举例分

类典型模型及其应用

3.1排队系统的特征与基本排队系统一、引言1、排队服务系统

在生产和日常生活中，经常可以碰到各种各样的服务系统。比如：（1）到商店买东西，顾客和售货员构成一个服务系统，服务的对象是顾客，服务机构是售货员；（2）病人到医院看病也构成一个服务系统，服务的对象是病人，服务机构是医生。这些服务系统都有一个共同的特征——排队等候服务。这是因为，在某时刻要求服务的数量超过服务机构（售货员，医生等）的容量时，也就是说，到达的顾客不能立即得到服务时，这时（若情况允许排队等候的话）有的必须等候，因而出现排队现象，称这种排队等候服务系统为排队服务系统。

定义1称排队等候服务系统为排队服务系统。说明：（1）排队服务系统远不仅在个人日常生活中出现。例如，电话局的占线问题，车站、码头等交通枢纽的车船堵塞和疏通，故障机器的停机待修，水库的存贮调节等都是排队服务系统。在一个服务系统中，若到达服务系统的顾客完全按固定的间隔时间到达，又服务设施用在每个顾客身上的服务时间也是固定的，就象工厂流水生产线的生产那样，有固定的节拍，那么这类服务系统的设计计算是比较方便的。（2）在大多数服务系统中顾客到达是随机的，服务设施用于每个顾客身上的服务时间也是随机的。

定义2若一个排队服务系统中顾客到达是随机的，服务设施用于每个顾客身上的服务时间也是随机的，则称此排队服务系统为随机服务系统。

对于随机服务系统，我们应开设多少服务设施比较合适呢？如果开设多了，就要增加服务人员及相应的设施，增加服务费用；如果开设少了排队现象就会严重，对顾客个人和对社会都会带来不利影响，到底怎样才能做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾，这就是研究随机服务系统的理论——排队论所要研究解决的问题。（3）排队系统的统计推断，即判断一个给定的排队系统符合那种类型，以便根据排队理论进行分析研究。本章着重研究性态问题。排队论研究的内容有下列三部分：（1）性态问题：即研究各种随机服务系统的概率规律性。如研究队长分布、等待时间分布和忙期分布等。（2）最优化问题：分静态最优和动态最优，前者指最优设计；后者指现有排队系统的最优运营；2、什么是排队论？

排队论是研究拥挤现象的一门学科。

它是在研究各种排队系统概率规律性的基础上，解决有关排队系统的最优设计（静态）和最优控制（动态）问题。3、排队论的起源与应用领域

20世纪初——Bell电话公司为减少用户呼叫，研究电话线路合理配置问题；

1909年丹麦工程师A.K.Erlang

受热力学统计平衡概念启发

论文“概率论与电话交换”，解决了上述问题；

应用于：通讯系统、交通运输、机器维修、库存控制、计算机设计……

二、排队系统的特征及其组成1、排队系统的特征即拥挤现象的共性:

有请求服务的人或物

；

有为顾客服务的人或物

；

具有随机性

；（各种排队系统中，顾客相继到达的间隔时间以及对每一位顾客的服务时间是随机的）

随机性是排队系统的一个重要特征

。2、排队系统的基本组成

顾客源等待队列顾客离去（输出）服务机构排队规则？（1）输入过程

：

刻划顾客到达排队系统的规律。排队系统123顾客到达（输入）服务机构

顾客总体数（顾客源）有限或无限；

顾客到达方式是单个到达或成批到达；

顾客相继到达的间隔时间服从什麽样的概率分布；（2）服务规则

：描述顾客到达排队系统后接受服务的先后次序，一般可分为即时制或损失制、等待制和混合制三类：

损失制(Losingsystem)——当顾客到达排队系统时，若所有的服务台均被占用(正在进行服务)，则离开系统，永不再来

；

等待制(Waitingsystem)——顾客到达系统时，所有的服务台均被占用（正在进行服务），顾客就加入排队行列等待服务，服务台可按照下面的规则进行排序服务：①

先到先服务（FCFS）FirstComeFirstserve②

后到先服务（LCFS）Last

ComeFirstserve③

随机服务（SIRO）ServeInRandomOrder④

有优先权的服务（PR）Preference

混合制(LosingsystemandWaitingsystem)——损失制和等待制的结合，一般是指允许排队，但又不允许队列无限长下去。主要有以下3种情况：①队长有限。当等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。②等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过时间T时，顾客将自动离去，并不再回来。③逗留时间（等待时间与服务时间之和）有限。（3）服务机构（服务台）：

数量及布置形式——见下页图

某一时刻接受服务的顾客数——单个服务还是成批服务；

服务时间的分布——最常见的有定常分布、负指数分布、k阶爱尔朗分布、一般分布等

；

。。。。。。12┇n。。。。。。。。。12┇n（a）单队单台。。。。。。12312(d)混合多服务台。。。。。。。。。12…n(e)串联多服务台排队系统服务台布置形式

(b)多队多台(c)单队多台三、排队模型的符号表示——

肯道尔分类方法(D.G.kendall)

表示为：

A/B/C/D/E/F或

[A/B/C]：[d/e/f]A

表示输入过程——顾客相继到达的间隔时间的分布；B

表示服务时间服从的分布；C

表示服务台的个数；D

表示系统容量；E

表示顾客源包含的全部个体数量；F表示服务规则

；举例：

M/M/1/∞/∞/FCFS表示泊松输入、服务时间服从负指数分布、1个服务台、系统容量无限制（即等待制）、顾客源无限、先到先服务的排队系统

；

GI/EK/1/N/∞/FCFS表示一般独立输入（顾客到达的间隔时间服从一般独立分布）、服务时间服从K阶爱尔朗分布、1个服务台、系统容量为N、顾客源无限、先到先服务的排队系统。

常用的各种分布符号：M——负指数分布(兼指泊松输入)；D——定长分布；EK

——

K阶爱尔朗分布；GI——

一般独立随机分布；G——

一般随机分布；四、排队系统研究的问题

1、排队系统的数量指标(特征量

)（1）

研究的目的是：了解系统的基本特征和性态，揭示其表现的概率规律性，以便对系统作出评价。（2）主要的数量指标：*

队长（Ls）——排队系统中顾客的平均数（期望值），包括正在接受服务和等待接受服务的顾客总数期望值。

已知队长分布，就能计算队长超过某个数量的概率，据此可以考虑是否应改变服务方式、设计合理的等待空间等；*

队列长（排队长Lq）——系统中排队等待接受服务的顾客数期望值；*

逗留时间（Ws）——顾客在系统内停留时间（包括排队等待时间和接受服务的时间）的期望值；*

等待时间（Wq）——顾客从到达系统的时刻到开始接受服务的时刻止的时间段；

*忙期和闲期分布——忙期指从有顾客到达空闲服务台接受服务开始到服务台再度空闲为止的这段时间，即服务台连续工作的时间。“忙期”是一个随机变量，可以表征服务台的工作强度；

服务台连续保持空闲的时间长度称为闲期。

在排队系统中忙期和闲期是交替出现的。*

服务设备利用率——指服务设备工作时间占总时间的比例。

该指标可以衡量服务设备的工作强度、磨损和疲劳程度。*顾客损失率——由于服务能力不足而造成的顾客流失的概率称为顾客损失率。

该指标过高会造成服务系统利润减少，因此损失制和混合制排队系统均会重视对该指标的研究。

2、统计推断问题的研究

对实际问题建立排队模型时，必须判断该系统适合建立何种排队模型，从而进一步用排队理论进行分析研究。

首先必须进行现实数据的收集、处理；

进而研究相继到达的间隔时间是否独立分布、确定其分布类型和有关参数，研究服务时间与相继到达的间隔时间之间的独立性以及服务时间的分布等；

判断该系统适合建立何种类型的排队模型，再用排队理论进行分析研究。

3、排队系统的优化

研究排队系统最优设计的静态优化和研究排队系统最优控制的动态优化。

最优设计：通常是在输入和服务参数给定的条件下，确定系统的设计参数（如服务台数量），以求系统运行指标达到最优。

最优控制：在系统运行的参数可以随时间或状态而变化的情况下（如服务率随顾客数的变化而改变）根据系统的实际情况假设一个合理或实际可行的控制策略，然后分析确定系统运行的最佳参数或者是对一个具体系统研究一个最佳的控制策略。

研究排队系统的目的就是通过对该系统概率规律的研究，达到系统的最优设计和最优控制，以最少的费用实现系统的最大效益。即使服务系统既能在适当的程度上满足顾客需求，同时又使所需费用达到最小。

服务费用等待费用费用服务水平总费用费用优化示意图

1、

泊松分布（Poisson）也称为泊松流，在排队论中常称为最简单流

。

概率分布

：其中，λ>0为一常数，t≥0。求N(t)的数学期望得:则λ=E[N(t)]/t。因此，λ表示单位时间内到达系统的平均顾客数,又称平均到达率

。五、排队系统中常见的几种典型理论分布

最简单流的4个基本性质：

平稳性：在时间段t内，恰有n个顾客到达系统的概率P{N(t)=n}仅与t的长短有关,而与该时间段的起始时刻无关；

无后效性：在不相交的时间区间内到达的顾客数是相互独立的。如：在[a，a+t]时段内到达K个顾客的概率与时刻a之前到达多少顾客无关；

普通性：在充分小的间隔时间内至少到达两个顾客的概率ψ(Δt)=o(t),t→0,即

有限性：在任意有限的时间区间内，到达有限个顾客的概率为1，即

泊松流在排队论中的意义：

实际问题中最常见；

数字处理简单；

当实际流与泊松流有较大出入时，经过一定的变换，结果也可达到一定的精度；

2、

负指数分布

密度函数和分布函数

：

数学期望和方差：

定理6-1

顾客到达服从参数为λ的泊松分布等价于顾客相继到达的间隔时间是独立的且同为负指数分布。参数μ>0表示单位时间内完成服务的顾客平均数,称为平均服务率。

3、

爱尔朗分布

当顾客在系统内所接受的服务可以分为K个阶段，每个阶段的服务时间T1，T2，…，Tk为服从同一分布

（参数为kμ的负指数分布）的k个相互独立的随机变量，顾客在完成全部服务内容并离开系统后，另一个顾客才能进入服务系统，则顾客在系统内接受服务时间之和T=T1+T2+…+Tk服从k阶爱尔朗分布Ek，其分布密度函数为：相应的数学期望和方差为：

当k=1时，爱尔朗分布归结为负指数分布，当k增大时，图形逐渐变为对称的，当k≥30时，近似于正态分布，当k→∞，由D(T)=0可知,爱尔朗分布归结为定长分布。因此，爱尔朗分布类可以看成完全随机与完全确定的中间型，能对现实问题提供更广泛的模型类。k=∞k=3k=2k=1

3.2单服务台负指数分布排队系统

一、标准的M/M/1模型，即M/M/1/∞

/∞

二、系统容量有限制，即M/M/1/N

/∞

三、顾客源为有限制，即M/M/1/∞/m

一、标准的M/M/1模型1、系统的特点：顾客按泊松流输入、平均到达率为λ，服务时间服从负指数分布、平均服务率为μ，1个服务台，系统容量和顾客源均为无限。当顾客来到系统时，若服务台忙，则顾客排队等待服务，排队规则为先到先服务的排队系统。由于是单服务台，单位时间到达系统的顾客数为λ，单位时间被服务完的顾客数为μ。且顾客源无限，因此，在各种状态的情况下，系统的“出生率”为λ，系统的“死亡率”为μ。系统在稳态情况下的状态转移如下图所示

0

1

2n-1

nn+1…P0

P1P2Pn-1

PnPn+12、系统的状态转移速度图：3、状态概率方程：根据以上状态转移图，可以得出如下平衡方程…………递推求解P1，P2，…，Pn，…，得ρ表示平均到达率与平均服务率之比，称为服务强度要求λ/μ<1,否则系统将是超负荷的,不能达到稳态而无法讨论。【例1】高速公路收费处设有一个收费通道，汽车到达服从泊松分布，平均到达速率为150辆／小时，收费时间服从负指数分布，平均收费时间为15秒／辆。求(1)收费处空闲的概率；(2)收费处忙的概率；(3)系统中分别有1，2，3辆车的概率。【解】根据题意,

=150辆/小时,1/μ=15秒/辆=1/240（小时/辆）,即μ＝240（辆/小时）。ρ＝λ/μ=150/240=5/8，则有(1)系统空闲的概率为：P0=1－ρ=1－(5/8)=3/8=0.375(2)系统忙的概率为：1-P0=5/8=0.625(3)系统中有1辆车的概率为：P1=ρ(1－ρ)=0.625×0.375=0.234系统中有2辆车的概率为：P2=ρ2(1－ρ)=0.234×0.625=0.146系统中有3辆车的概率为：P3=ρ3(1－ρ)==0.146×0.625=0.0914、系统的运行指标：（1）在系统中的平均顾客数队长期望值（2）在队列中等待的平均顾客数（队列长期望值）（3）在系统中顾客逗留时间的期望值（4）在系统中顾客等待时间的期望值（5）系统处于空闲状态的概率（6）系统处于忙期的概率（7）系统处于忙期时队列中顾客平均数（8）系统处于忙期时顾客平均等待时间Little公式:【例2】轻轨进站口售票处设有一个售票窗口，乘客到达服从泊松分布，平均到达速率为200人/小时，售票时间服从负指数分布，平均售票时间为15秒/人。求L、Lq、W和Wq。【解】根据题意，λ=200人/小时，μ=240人/小时，ρ=5/6。1、系统的特征

顾客按泊松流输入,平均到达率为λ；

服务时间服从负指数分布,平均服务率为μ；

1个服务台；

系统容量为N,顾客源无限,排队规则为先到先服务的混合制排队系统。

当顾客来到系统时,若系统中的顾客已经等于N，则自动离去,另求服务

。

二、系统容量有限制，即M/M/1/N

/∞顾客到达因队列满而离去进入队列接受服务服务完毕后离去2、状态转移速度图（1）系统状态

：系统中的顾客数。（2）状态转移速度图：N-1

NN-2

2

1

0……μμμμλλλλ

M/M/1/N/∞/FCFS系统状态转移速度图

圆圈表示状态符号

，箭头表示从一个状态到另一个状态的转移；

3、状态概率方程：…4、系统的运行指标：(1)系统中的平均顾客数Ls(2)队列中的平均顾客数Lq

λe称为有效到达率，即单位时间内到达并能进入队列的平均顾客数。ρe称为有效服务强度在研究顾客在系统中平均逗留时间和在队列中平均等待时间时，虽然可用公式：但要注意平均到达率是在系统中有空时的平均到达率，当系统已满时，则到达率为0，因此需求出有效到达率。(3)顾客在系统中的平均逗留时间W(4)顾客在队列中的平均逗留时间(5)有效到达率的另一种计算公式λe=λ（1-PN）+0PN

(系统不满时顾客以λ的速度进入系统）

=μ（1-P0）+0P0

（系统不空时顾客以μ的速度离开系统）(6)

系统平均每单位时间损失的顾客数λ损=λ-λe=λPN(7)

系统平均每单位时间损失的顾客数

从服务台闲到下一个顾客来到的平均间隔时间是1/λ，因此平均闲期长为

T闲=1/λ由于服务台忙闲间隔出现，故有：平均忙期长T忙/平均闲期长T闲=P忙/P闲=(1-P0)/P0，于是

T忙=T闲[(1-P0)/P0]=1/λ[(1-P0)/P0]【例3】咨询中心有一位咨询工作人员，每次只能咨询一人，另外有4个座位供前来咨询