运筹学课件全面系统ppt课件

《运筹学课件全面系统ppt课件》由会员分享，可在线阅读，更多相关《运筹学课件全面系统ppt课件（564页珍藏版）》请在金锄头文库上搜索。

1、1 1 运运 筹筹 学学 1.绪论 2.线性规划建模及单纯形法 3.线性规划问题的对偶与灵敏度分析 4.运输问题 5.动态规划 6.排队论 7.决策分析 8.图与网络分析 2 2第一章 绪 论3 3运筹学概况简述运筹学概况简述 运筹学(Operations Research) 直译为“运作研究”。 运筹学是运用科学的方法(如分析、试验、量化等)来决定如何最佳地运营和设计各种系统的一门学科。4 4运筹学概况简述运筹学概况简述 运筹学能够对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。 通常以最优、最佳等作为决策目标，避开最劣的方案。5 5运

2、筹学在工商管理中的应用运筹学在工商管理中的应用 生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等。 库存管理：多种物资库存量的管理，库存方式、库存量等。 运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等。6 6运筹学在工商管理中的应用运筹学在工商管理中的应用人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等。市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等。7 7运筹学在工商管理中的应用运筹学在工商管理中的应用 财务和会计：包括预测、贷款、成本分析、定价、证券管理、现金管理等。 其他： 设备维修、

3、更新，项目选择、评价，工程优化设计与管理等。8 8运筹学的产生和发展运筹学的产生和发展 运筹学思想的出现可以追溯到很早“田忌齐王赛马”（对策论）、孙子兵法等都体现了优化的思想。 “Operational Research”这一名词最早出现在第二次世界大战期间 美、英等国家的作战研究小组为了解决作战中所遇到的许多错综复杂的战略、战术问题而提出的。9 9运筹学的产生和发展运筹学的产生和发展 战后这些研究成果被应用到生产、经济领域，并得到迅速发展有关理论和方法的研究、实践不断深入。 1947年美国数学家丹捷格(G.B.Dantzig）提出了求解线性规划的有效方法单纯形法。1010运筹学的产生和发展运

4、筹学的产生和发展数学对运筹学的作用是有关理论和方法的研究基础，是建立运筹学模型的工具。计算机的发展，促进运筹学的进一步发展高速、可靠的计算是运筹学解决问题的基本保障。1111运筹学的分支运筹学的分支线性规划非线性规划整数规划动态规划多目标规划随机规划模糊规划等1212运筹学的分支运筹学的分支图与网络理论存储论排队论决策论对策论排序与统筹方法可靠性理论等1313运筹学方法使用情况运筹学方法使用情况( (美美1983)1983)1414 运筹学方法在中国使用情况运筹学方法在中国使用情况 ( (随机抽样随机抽样) )1515运筹学的推广应用前景运筹学的推广应用前景 据美劳工局1992年统计预测:社会

5、对运筹学应用分析人员的需求从1990年到2005年，其增长百分比预测为73%,增长速度排到各项职业的前三位。1616运筹学的推广应用前景运筹学的推广应用前景结论:-运筹学在国内或国外的推广应用前景是非常广阔的。-工商企业对运筹学应用的需求是很大的。-在工商企业推广运筹学方面有大量的工作要做。1717运筹学解决问题的过程运筹学解决问题的过程 1）提出问题：认清问题。 2）寻求可行方案：建模、求解。 3）确定评估目标及方案的标准或方法、途径。 4）评估各个方案：解的检验、灵敏性分析等。1818运筹学解决问题的过程运筹学解决问题的过程 5）选择最优方案：决策。 6）方案实施：回到实践中。 7）后评估

6、：考察问题是否得到完满解决。 1）2）3）形成问题；4）5）分析问题：定性分析与定量分析相结合，构成决策。1919如何学习运筹学课程如何学习运筹学课程学习运筹学要把重点放在分析、理解有关的概念、思路上。在自学过程中，应该多向自己提问，例如一个方法的实质是什么，为什么这样进行，怎么进行等。 自学时要掌握三个重要环节：2020如何学习运筹学课程如何学习运筹学课程 1.认真阅读教材和参考资料，以指定教材为主，同时参考其他有关书籍。一般每一本运筹学教材都有自己的特点，但是基本原理、概念都是一致的。注意主从，参考资料会帮助你开阔思路，使学习深入。但是，把时间过多放在参考资料上，会导致思路分散，不利于学好

7、。2121 2.要在理解了基本概念和理论的基础上要在理解了基本概念和理论的基础上研究例题，注意例题是为了帮助理解概念、研究例题，注意例题是为了帮助理解概念、理论的。作业练习的主要作用也是这样，它理论的。作业练习的主要作用也是这样，它同时还有让你自己检查自己学习的作用。因同时还有让你自己检查自己学习的作用。因此，做题要有信心，要独立完成，不要怕出此，做题要有信心，要独立完成，不要怕出错。因为，整个课程是一个整体，各节内容错。因为，整个课程是一个整体，各节内容有内在联系，只要学到一定程度，知识融会有内在联系，只要学到一定程度，知识融会贯通起来，你自己就能够对所做题目的正确贯通起来，你自己就能够对所

8、做题目的正确性作出判断。性作出判断。如何学习运筹学课程如何学习运筹学课程2222 3、要学会做学习小结。每一节或一章学完后，必须学会用精炼的语言来概述该书所讲内容。这样，你才能够从较高的角度来看问题，更深刻地理解有关知识和内容。这就称作“把书读薄”，若能够结合相关参考文献并深入理解，把相关知识从更深入、广泛的角度进行论述，则称为“把书读厚”。如何学习运筹学课程如何学习运筹学课程2323 第二章 线性规划建模及单纯形法本章内容重点w线性规划模型与解的主要概念w线性规划的单纯形法，线性规划多解分析w线性规划应用建模24241.1.线性规划的概念线性规划的概念 例2.1:某工厂拥有A、B、C 三种类

9、型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：产品甲产品乙设备能力（h）设备A3 32 26565设备B2 21 14040设备C0 03 37575利润（元/件）15001500250025002525 问题：工厂应如何安排生产可获得最大的总利润？ 解：设变量 xi 为第 i 种（甲、乙）产品的生产件数（i1，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。对设备A：两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3 x1 + 2 x2 65； 对设备B：两种产品生产所占用的机

10、时数不能超过40，于是我们可以得到不等式：2 x1+ x2 40；1.1.线性规划的概念线性规划的概念2626 对设备C ：两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x2 75 ；另外，产品数不可能为负，即 x1 ,x2 0。 同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润： z = 1500x1 + 2500x2 综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型：1.1.线性规划的概念线性规划的概念2727目标函数 Max z =1500x1+2500

11、x2约束条件 s.t. 3x1 + 2x2 65 2x1 + x2 40 3x2 75 x1 ,x2 0 1.1.线性规划的概念线性规划的概念2828 这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最 大 化 ”； “s.t.”是 “subject to”的缩写，表示“满足于”。因此，上述模型的含义是：在给定条件限制下，求使目标函数 z 达到最大的x1 ,x2 的取值。1.1.线性规划的概念线性规划的概念2929一般形式 目标函数：Max(Min)z = c1x1+c2x2+cnxn 约束条件： a11x1+a12x2+a1nxn( =,

12、 )b1a21x1+a22x2+a2nxn( =, )b2 . . . am1x1+am2x2+amnxn( =, )bm x1 ，x2 ， ，xn 01.1.线性规划的概念线性规划的概念3030标准形式目标函数：Max z = c1x1 + c2x2 + +cnxn 约束条件：A11x1 + a12x2 + +a1nxn = b1a21x1 + a22x2 + + a2nxn = b2 . . .am1x1 + am2x2 + + amnxn = bm x1 ，x2 ， ，xn 01.1.线性规划的概念线性规划的概念3131 可以看出，线性规划的标准形式有如下四个特点：目标最大化、约束为等式

13、、决策变量均非负、右端项非负。 对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式: 1.1.线性规划的概念线性规划的概念3232 1.极小化目标函数的问题： 设目标函数为 Min f = c1x1+c2x2+cnxn 则可以令z -f ，该极小化问 题与下面的极大化问题有相同的最优 解，即 Max z = -c1x1- c2x2 - - cnxn 但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即 Min f - Max z1.1.线性规划的概念线性规划的概念3333 2、约束条件不是等式的问题： 设约束条件为 ai1 x1+ai2

14、 x2+ain xn bi 可以引进一个新的变量s ，使它等于约束右边与左边之差 s =bi(ai1 x1+ai2 x2+ain xn ) 显然，s 也具有非负约束，即s0， 这时新的约束条件成为 ai1 x1+ai2 x2+ain xn+s = bi1.1.线性规划的概念线性规划的概念3434 当约束条件为 ai1 x1+ai2 x2+ +ain xn bi 时，类似地令 s =(ai1 x1+ai2 x2+ain xn)- bi 显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn-s = bi 1.1.线性规划的概念线性规划的概念3535 为了

15、使约束由不等式成为等式而引进的变量 s 称为“松弛变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。1.1.线性规划的概念线性规划的概念3636 例2.2：将以下线性规划问题转化为标准形式 Min f = 3.6 x1 - 5.2 x2 + 1.8 x3 s. t. 2.3 x1 + 5.2 x2 - 6.1 x3 15.7 4.1 x1 + 3.3 x3 8.9 x1 + x2 + x3 = 38 x1 , x2 , x3 0 1.1.线性规划的概念线性规划的概念 解：首先,将目标函数转换成极大化：令 z= -f = -3.6x1+5.2x2-

16、1.8x3 3737其次考虑约束，有2个不等式约束，引进松弛变量x4，x5 0。于是，我们可以得到以下标准形式的线性规划问题： Max z = - 3.6 x1 + 5.2 x2 - 1.8 x3s.t. 2.3x1+5.2x2-6.1x3+x4= 15.7 4.1x1+3.3x3-x5= 8.9 x1+x2+x3= 38 x1 ,x2 ,x3 ,x4 ,x5 01.1.线性规划的概念线性规划的概念3838 3. 变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令 xj = xj- xj”其中 xj0，xj”0即用两个非负变量之差来表示一个无

17、符号限制的变量，当然xj的符号取决于xj和xj”的大小。1.1.线性规划的概念线性规划的概念3939 4.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bim，秩(A A) = m，b b Rm 。在约束等式中，令n维空间的解向量： x x = (x1，x2，xn)T 2.2.线性规划解的概念线性规划解的概念 7878 中n-m个变量为零，如果剩下的m个变量在线性方程组中有唯一解，则这n个变量的值组成的向量x x就对应于n维空间Rn中若干个超平面的一个交点。当这n个变量的值都是非负时，这个交点就是线性规划可行域的一个极点。 根据以上分析，我们建立

18、以下概念： （1）线性规划的基基：对于线性规划的约束条件 AxAx=b b， x x0 0 2.2.线性规划解的概念线性规划解的概念 7979 设B B是A A矩阵中的一个非奇异（可逆）的mm子矩阵，则称B B为线性规划的一个基基。用前文的记号，A A=( p p1 1 ，p p2 2 ，p pn n ) ，其中 p pj j=( a1j ，a2j ，amj )T Rm ，任取A A中的m个线性无关列向量 p pj j Rm 构成矩阵 B B=( p pj1 j1 ，p pj2 j2 ，p pjmjm )。那么B B为线性规划的一个基基。 我们称对应于基B B的变量xj1 ，xj2，xjm为基

19、基变变量量；而其他变量称为非非基基变量变量。2.2.线性规划解的概念线性规划解的概念 8080 可以用矩阵来描述这些概念。可以用矩阵来描述这些概念。 设设B B B B是线性规划的一个基，则是线性规划的一个基，则A A A A可以表示为可以表示为 A A A A= = = = B , NB , NB , NB , N x x x x也可相应地分成也可相应地分成 x x x xB B B B x x x x= = x x x xN N N N 其其中中x x x xB B为为m m维维列列向向量量，它它的的各各分分量量称称为为基基基基变变变变量量量量，与与基基B B B B的的列列向向量量对对应

20、应；x x x xN N为为n-mn-m列列向向量量，它它的的各各分分量量称称为为非非非非基基基基变变变变量量量量，与与非非基基矩矩阵阵N N N N的的列列向向量量对对应应。这时约束等式这时约束等式AxAxAxAx= =b b b b可表示为可表示为 2.2.线性规划解的概念线性规划解的概念 8181 x x x xB B B,NB,N = = b b b b x x x xN N 或 BxBxBxBxB + + NxNxNxNxN = = b b b b 如果对非基变量x xN取确定的值，则xB有唯一的值与之对应 x x x xB B = = B B B B-1-1b b b b - -

21、B B B B-1-1NxNxNxNxN N 特别，当取x xN = 0 0，这时有x xB=B B-1b b。关于这类特别的解，有以下概念。2.2.线性规划解的概念线性规划解的概念 8282 （2）线性规划问题的基本解基本解、基基本可行解本可行解和可行基可行基： 对于线性规划问题，设矩阵B B = ( p pj1j1，p pj2j2，p pjmjm ) 为一个基，令所有非基变量为零，可以得到m个关于基变量xj1 ，xj2 ，xjm的线性方程，解这个线性方程组得到基变量的值。我们称这个解为一个基基本本解解；若得到的基变量的值均非负，则称为基基本本可可行解行解，同时称这个基B B为可行基可行基。

22、2.2.线性规划解的概念线性规划解的概念 8383 矩阵描述为，对于线性规划的解 x xB B B-1b b x x= = x xN 0 称为线性规划与基B B对应的基本解。若其中B B-1b b0 0，则称以上的基本解为一基本可行解，相应的基B B称为可行基。 2.2.线性规划解的概念线性规划解的概念 8484 我们可以证明以下结论：线性规划的基本可行解就是可行域的极点。 这个结论被称为线性规划的基本定理，它的重要性在于把可行域的极点这一几何概念与基本可行解这一代数概念联系起来，因而可以通过求基本可行解的线性代数的方法来得到可行域的一切极点，从而有可能进一步获得最优极点。2.2.线性规划解的

23、概念线性规划解的概念 8585 例例2.9: 2.9: 考虑例考虑例2.82.8的线性规划模型的线性规划模型 Max Max z z = 1500 = 1500 x x1 1 + 2500 + 2500 x x2 2 s.t. 3 s.t. 3 x x1 1 + 2 + 2 x x2 2 + + x x3 3 = 65 = 65 2 2 x x1 1 + + x x2 2 + + x x4 4 = 40 = 40 3 3 x x2 2 + + x x5 5 = 75 = 75 x x1 1 , x, x2 2 , x, x3 3 , x , x4 4 , x, x5 5 0 0 注意，线性规划

24、的基本解、基本可行注意，线性规划的基本解、基本可行 解（极点）和可行基只与线性规划问解（极点）和可行基只与线性规划问 题标准形式的约束条件有关。题标准形式的约束条件有关。2.2.线性规划解的概念线性规划解的概念 8686 3 2 1 0 03 2 1 0 0A A A A = = = = P1 ,P2 ,P3 ,P4 ,P5P1 ,P2 ,P3 ,P4 ,P5P1 ,P2 ,P3 ,P4 ,P5P1 ,P2 ,P3 ,P4 ,P5 = = = = 2 1 0 1 02 1 0 1 0 0 3 0 0 1 0 3 0 0 1 A A A A矩阵包含以下矩阵包含以下1010个个3333的子矩阵：的

25、子矩阵： B B B B1 1 1 1=p p p p1 1 1 1 ，p p p p2 2 2 2 ，p p p p3 3 3 3 B B B B2 2 2 2=p p p p1 1 1 1 ，p p p p2 2 2 2 ，p p p p4 4 4 4 B B B B3 3 3 3=p p p p1 1 1 1 ，p p p p2 2 2 2 ，p p p p5 5 5 5 B B B B4 4 4 4=p p p p1 1 1 1 ，p p p p3 3 3 3 ，p p p p4 4 4 4 B B B B5 5 5 5=p p p p1 1 1 1 ，p p p p3 3 3 3 ，

26、p p p p5 5 5 5 B B B B6 6 6 6=p p p p1 1 1 1 ，p p p p4 4 4 4 ，p p p p5 5 5 5 B B B B7 7 7 7=p p p p2 2 2 2 ，p p p p3 3 3 3 ，p p p p4 4 4 4 B B B B8 8 8 8=p p p p2 2 2 2 ，p p p p3 3 3 3 ，p p p p5 5 5 5 B B B B9 9 9 9=p p p p2 2 2 2 ，p p p p4 4 4 4 ，p p p p5 5 5 5 B B B B10101010=p p p p3 3 3 3 ，p p p

27、 p4 4 4 4 ，p p p p5 5 5 5 2.2.线性规划解的概念线性规划解的概念 8787 其其中中 B B B B4 4 = = 0 0，因因而而B B B B4 4不不是是该该线线性性规规划划问问题题的的基基。其余均为非奇异方阵，因此该问题共有其余均为非奇异方阵，因此该问题共有9 9个基。个基。 对对于于基基B B B B3 3=p p p p1 1 1 1 ，p p p p2 2 2 2 ，p p p p5 5 5 5 ，令令非非基基变变量量x x3 3 3 3 = = 0 0， x x4 4 = = 0 0，在在等等式式约约束束中中令令x x3 3 = = 0 0，x x4

28、 4 = = 0 0，解解线线性性方程组：方程组： 3 3 x x1 1 + 2 + 2 x x2 2 + 0 + 0 x x5 5 = 65= 65 2 2 x x1 1 + + x x2 2 + 0 + 0 x x5 5 = 40= 40 0 0 x x1 1 + 3 + 3 x x2 2 + + x x5 5 = 75= 75 得得到到x x1 1 =15=15，x x2 2 = = 1010，x x5 5 = = 4545，对对应应的的基基本本可可行行解：解： x x x x=(=(x x1 1 ，x x2 2 ，x x3 3 ，x x4 4 ，x x5 5) )T T=(15=(15

29、，1010，0 0，0 0，45)45)T T。于是对应的基于是对应的基B B B B3 3是一个可行基。是一个可行基。2.2.线性规划解的概念线性规划解的概念 8888 类似可得到类似可得到 x x x x(2)(2) = (5,25,0,5,0) = (5,25,0,5,0)T T （对应对应B B B B2 2） x x x x(7)(7) = (20,0,5,0,75) = (20,0,5,0,75)T T （对应对应B B B B5 5） x x x x(8)(8) = (0,25,15,15,0) = (0,25,15,15,0)T T （对应对应B B B B7 7） x x x

30、 x(9)(9) = (0,0,65,40,75) = (0,0,65,40,75)T T （对应对应B B B B1010） 是基本可行解；是基本可行解； 而而x x x x(3)(3)= (0,32.5,0,7.5,-22.5)= (0,32.5,0,7.5,-22.5)T T（对应对应B B B B9 9） x x x x(4)(4)= (65/3,0,0,-10/3,75)= (65/3,0,0,-10/3,75)T T （对应对应B B B B6 6） x x x x(5)(5)= (7.5,25,-7.5,0,0)= (7.5,25,-7.5,0,0)T T （对应对应B B B

31、B1 1） x x x x(6)(6) = (0,40,-15,0,-45) = (0,40,-15,0,-45)T T （对应对应B B B B8 8） 是基本解。是基本解。2.2.线性规划解的概念线性规划解的概念 8989 因此，对应基本可行解（极点） 的B B2 B B3 B B5 B B7 B B10都是可行基。 这里指出了一种求解线性规划问题的可能途径，就是先确定线性规划问题的基，如果是可行基，则计算相应的基本可行解以及相应解的目标函数值。由于基的个数是有限的（最多个），因此必定可以从有限个基本可行解中找到最优解。2.2.线性规划解的概念线性规划解的概念 9090 利用求解线性规划问

32、题基本可行解（极点）的方法来求解较大规模的问题是不可行的。单纯形法的基本思路是有选择地取基本可行解，即是从可行域的一个极点出发，沿着可行域的边界移到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。 3.3.单单 纯纯 形形 法法9191 由上节的讨论可知，对于线性规划的一个基，当非基变量确定以后，基变量和目标函数的值也随之确定。因此，一个基本可行解向另一个基本可行解的移动，以及移动时基变量和目标函数值的变化，可以分别由基变量和目标函数用非基变量的表达式来表示。同时，当可行解从可行域的一个极点沿着可行域的边界移动到一个相邻的极点的过程中，所有非基变量中只有一个变量的值从0开始增加，而

33、其他非基变量的值都保持0不变。3.3.单单 纯纯 形形 法法92923.3.单单 纯纯 形形 法法初始基本可行解初始基本可行解是否最优解或是否最优解或无限最优解无限最优解? ?结束结束沿边界找新沿边界找新的基本可行解的基本可行解NY单纯形法的基本过程9393考虑标准形式的线性规划问题：Max z = c1x1 + c2x2 + + cnxn s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 . . . am1 x1 + am2 x2 + + amn xn = bm x1 , x2 , , xn 0 x1 c

34、1 b1 a11 a12.a1n x2 c2 b2 a21 a22.a2nx x= . C C= . B B= . A A= . . . . . . . . . xn cn bn am1 am2.amn 3.3.单单 纯纯 形形 法法9494这里，矩阵A A表示为：A A = ( p p1 1 ，p p2 2 ，p pn n ) ，其中 p pj j = ( a a1j 1j ，a a2j 2j ，a amjmj )T Rm。若找到一个可行基，无防设B B = ( p p1 1 ，p p2 2 ，p pm m ) ，则m个基变量为 x1 , x2 , , xm，n-m个非基变量为 xm+1 ，

35、xm+2 ，xn 。通过运算，所有的基变量都可以用非基变量来表示：3.3.单单 纯纯 形形 法法95953.3.单单 纯纯 形形 法法 x1=b1-（a1m+1xm+1+a1m+2xm+2+a1nxn） x2=b2-（a2m+1xm+1+a2m+2xm+2+a2nxn）( 2-11 ) . . . xm=bm-（amm+1xm+1+amm+2xm+2+amnxn） 把它们代入目标函数，得 z = z+m+1xm+1+m+2xm+2+nxn ( 2-12 )其中 j=cj-（c1a1j + c2a2j + + cm amj） 我们把由非基变量表示的目标函数形式称为基B B相应的目标函数典式典式。

36、9696单纯形法的基本步骤可描述如下： （1）寻找一个初始的可行基和相应基本可行解（极点），确定基变量、非基变量以及基变量、非基变量（全部等于0）和目标函数的值，并将目标函数和基变量分别用非基变量表示； 3.3.单单 纯纯 形形 法法9797 （2）在用非基变量表示的目标函数表达式（2-12）中，我们称非基变量xj的系数（或其负值）为检验数记为 j 。若 j 0，那么相应的非基变量xj，它的值从当前值0开始增加时，目标函数值随之增加。这个选定的非基变量xj称为“进基变量”，转（3）。如果任何一个非基变量的值增加都不能使目标函数值增加，即所有 j 非正，则当前的基本可行解就是最优解，计算结束；3

37、.3.单单 纯纯 形形 法法9898 （3）在用非基变量表示的基变量的表达式（2-11）中，观察进基变量增加时各基变量变化情况，确定基变量的值在进基变量增加过程中首先减少到0的变量xr ，满足，=minbi /aij aij 0 = br /arj这个基变量xr称为“出基变量”。当进基变量的值增加到 时，出基变量xr的值降为0时，可行解就移动到了相邻的基本可行解（极点），转（4）。3.3.单单 纯纯 形形 法法9999如果进基变量的值增加时，所有基变量的值都不减少，即所有aij 非正，则表示可行域是不封闭的，且目标函数值随进基变量的增加可以无限增加，此时，不存在有限最优解，计算结束； （4）将

38、进基变量作为新的基变量，出基变量作为新的非基变量，确定新的基、新的基本可行解和新的目标函数值。在新的基变量、非基变量的基础上重复（1）。3.3.单单 纯纯 形形 法法100100 例2.10：用单纯形法的基本思路解例2.8的线性规划问题 Max z = 1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 03.3.单单 纯纯 形形 法法101101第一次迭代：（1）取初始可行基B B10= (p p3 3 , , p p4 4 , , p p

39、5 5)，那么x3 ，x4 ，x5为基变量，x1 ，x2为非基变量。将基变量和目标函数用非基变量表示： z z=1500x1+2500x2 x3 = 65 - 3 x1 - 2 x2 x4 = 40 - 2 x1 - x2 x5 = 75 - 3 x2当非基变量x1，x2=0时，相应的基变量和目标函数值为x3=65，x4=40，x5= 75，z = 0，得到当前的基本可行解：x x=(0,0,65,40,75)T，z = 0 。这个解对应于图2-7的D、E交点。3.3.单单 纯纯 形形 法法102102 （2）选择进基变量。在目标函数z z = 1500 x1 + 2500 x2中，非基变量x

40、1，x2的系数都是正数，因此 x1 ，x2进基都可以使目标函数z增大，但x2的系数为2500，绝对值比x1的系数1500大，因此把x2作为进基变量可以使目标函数z增加更快。选择x2为进基变量，使x2的值从0开始增加，另一个非基变量x1保持零值不变。3.3.单单 纯纯 形形 法法103103 （3）确定出基变量。在约束条件 x3 = 65 - 3 x1 - 2 x2 x4 = 40 - 2 x1 - x2 x5 = 75 - 3 x2中，由于进基变量x2在3个约束条件中的系数都是负数，当x2的值从0开始增加时，基变量x3 、x4 、x5的值分别从当前的值65、40和75开始减少，当x2增加到25

41、时，x5首先下降为0成为非基变量。这时，新的基变量为x3 、x4 、x2 ，新的非基变量为x1 、x5 ，当前的基本可行解和目标函数值为：x x = (0，25，15，15，0)T，z = 62500。这个解对应于图中的C、D交点。3.3.单单 纯纯 形形 法法104104第二次迭代： （1）当前的可行基为B B7 = (p p2 2 , , p p3 3 , , p p4 4)，那么x2 ，x3 ，x4为基变量，x1 ，x5为非基变量。将基变量和目标函数用非基变量表示： z = 62500 + 1500 x1 (2500/3) x5 x2 = 25 (1/3) x5x3 = 15 - 3 x

42、1 + (2/3) x5 x4 = 15 - 2 x1 + (1/3) x5 3.3.单单 纯纯 形形 法法105105 （2）选择进基变量。在目标函数z = 62500 + 1500 x1 (2500/3) x5 中，非基变量x1的系数是正数，因此 x1进基可以使目标函数z增大，于是选择x1进基，使x1的值从0开始增加, 另一个非基变量x5保持零值不变。 (3)确定出基变量。在约束条件 x2 = 25 (1/3) x5x3 = 15 - 3 x1 + (2/3) x5 x4 = 15 - 2 x1 + (1/3) x53.3.单单 纯纯 形形 法法106106中，由于进基变量x1在两个约束条

43、件中的系数都是负数，当x1的值从0开始增加时，基变量x3 、x4的值分别从当前的值15、15开始减少，当x1增加到5时，x3首先下降为0成为非基变量。这时，新的基变量为x1 、x2 、x4 ，新的非基变量为x3 、x5 ，当前的基本可行解和目标函数值为：x x = (5，25，0，5，0)T，z = 70000。这个解对应于图中的A、C交点。3.3.单单 纯纯 形形 法法107107第三次迭代： （1）当前的可行基为B B2 = (p p1 1 , , p p2 2 , , p p4 4 )，那么x1 ，x2 ，x4为基变量，x3 ，x5为非基变量。将基变量和目标函数用非基变量表示： z =

44、70000 500 x3 500 x5x1 = 5 (1/3) x3 + (2/9) x5 x2 = 25 (1/3) x5x4 = 5 + (2/3) x3 (1/9) x5 3.3.单单 纯纯 形形 法法108108 （2）选择进基变量。在目标函数z = 70000 500 x3 500 x5 中，非基变量x3 、x5的系数均不是正数，因此进基都不可能使目标函数z增大，于是得到最优解，x x* * = (5，25，0，5，0)T，最优目标值为z* = 70000。这个解对应于图2-7的A、C交点。我们也称相应的基B B2 = (p p1 1 , , p p2 2 , , p p4 4)为最

45、最优优基基。计算结束。3.3.单单 纯纯 形形 法法1091093 3、 单单 纯纯 形形 法法表格单纯形法表格单纯形法考虑：考虑：考虑：考虑： b bi i 0 i = 1 , , m 0 i = 1 , , m Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn b1 a21 x1 + a22 x2 + + a2n xn b2 am1 x1 + am2 x2 + + amn xn bm x1 ，x2 ， ，xn 01101103 3、 单单 纯纯 形形 法法加入松弛变量：加入松弛变量： Max z = c1 x1

46、+ c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 am1 x1 + am2 x2 + + amn xn+ xn+m = bm x1 ，x2 ， ，xn ，xn+1 ， ，xn+m 0111111显然，显然，显然，显然，x xj j = 0 j = 1, , n ; = 0 j = 1, , n ; x xn+in+i = b = bi i i = 1 , , mi = 1 , , m 是基本可是基本可行解行解 对应的基是单位矩阵。对应的基是单位

47、矩阵。以下是初始单纯形表：以下是初始单纯形表： m mm m其中：其中：f = f = - - c cn+in+i b bi i j j = = c cj j - - c cn+in+i a aij ij 为检验数为检验数 c cn+in+i = = 0 i= 1,m0 i= 1,m i = 1 i = 1 i = 1 i = 1 a an+i,in+i,i = 1 , a = 1 , an+i,jn+i,j = 0 ( ji ) i , j = 1, , m = 0 ( ji ) i , j = 1, , m3 3、 单单 纯纯 形形 法法1121123 3、 单单 纯纯 形形 法法 例例2

48、.10。化标准形式：。化标准形式： Maxz=1500x1+2500x2s.t.3x1+2x2+x3=652x1+x2+x4=403x2+x5=75x1,x2,x3,x4,x50最优解x1=5x2=25x4=5（松弛标量，表示B设备有5个机时的剩余）最优值z*=70000113113注意：单纯形法中，注意：单纯形法中， 1、每一步运算只能用矩阵初等、每一步运算只能用矩阵初等行变换；行变换； 2、表中第、表中第3列的数总应保持非负列的数总应保持非负（ 0）；）； 3、当所有检验数均非正（、当所有检验数均非正（ 0）时，得到最优单纯形表。时，得到最优单纯形表。3 3、 线线 性性 规规 划划 11

49、4114 一般情况的处理及注意事项的强调：主要是讨论初始基本可行解不明显时，常用的方法。要弄清它的原理，并通过例题掌握这些方法，同时进一步熟悉用单纯形法解题。 考虑一般问题： bi 0 i = 1 , , m3.3.单单 纯纯 形形 法法115115Max z = c1x1 + c2x2 + + cnxn s.t. a11x1+a12x2 +a1nxn = b1 a21x1+a22x2 +a2nxn = b2 . . . am1x1+am2x2+amnxn = bm x1 ，x2 ， ，xn 03.3.单单 纯纯 形形 法法116116大大M M法：法： 引入人工变量引入人工变量 x xn+i

50、n+i 0 0 （i i = 1 , , = 1 , , m m）及充分大正数及充分大正数 M M 。得到：得到：Max Max Max Max z z = = c c1 1x x1 1 + +c c2 2x x2 2 + + +c cn nx xn n - -MxMxn+1 n+1 - - -MxMxn+mn+m s.t. s.t. s.t. s.t. a a1111 x x1 1 + + a a1212 x x2 2 + + + + a a1n1n x xn n + + x xn+1n+1 = = = = b b1 1 a a2121 x x1 1 + + a a2222 x x2 2 +

51、 + + + a a2n2n x xn n + + x xn+2 n+2 = = b b2 2 . . . . . . . . . . . . a am1m1 x x1 1 + + a am2m2 x x2 2 + + + + a amnmn x xn n + + x xn+mn+m = = b bm m x x1 1 ，x x2 2 ， ，x xn n ，x xn+1 n+1 ， ，x xn+mn+m 0 0 0 03.3.单单 纯纯 形形 法法117117显然，xj = 0 j=1, , n ; xn+i = bi i =1 , , m 是基本可行解。对应的基是单位矩阵。 结论：若得到的最

52、优解满足 xn+i = 0 i = 1 , , m 则是原问题的最优解；否则，原问题无可行解。3.3.单单 纯纯 形形 法法118118 两阶段法： 引入人工变量 xn+i 0，i = 1 , m； 构造: Max z = - xn+1 - xn+2 - - xn+m s.t. a11x1+a12x2+ +a1nxn+xn+1 = b1 a21x1+a22x2+ +a2nxn+xn+2 = b2 . . . am1x1+am2x2+ +amnxn+xn+m = bm x1,x2 . xn ,xn+1,xn+m 03.3.单单 纯纯 形形 法法119119 第一阶段求解上述问题： 显然，xj =

53、 0 j=1, , n ; xn+i = bi i =1 , , m 是基本可行解,它对应的基 是单位矩阵。 结论：若得到的最优解满足 xn+i=0 i=1 , , m 则是原问题的基本可行解;否则，原问题无可行解。 得到原问题的基本可行解后，第二阶段求解原问题。3.3.单单 纯纯 形形 法法120120例2.11：（LP）Max z = 5x1 + 2x2 + 3x3 - x4 s.t. x1 + 2x2 + 3x3 = 15 2x1 + x2 + 5x3 = 20 x1 + 2x2 + 4x3 + x4 = 26 x1 , x2 , x3 , x4 03.3.单单 纯纯 形形 法法1211

54、21 Max z = 5x1+2x2+3x3-x4-Mx5-Mx6 s.t. x1+2x2+3x3+x5 =15 2x1+x2+5x3+x6 =20 x1+2x2+4x3+x4 =26 x1 ,x2 ,x3 ,x4 ,x5 ,x6 03.3.单单 纯纯 形形 法法122122大大M M法法 （LP - M） 得到最优解：(25/3，10/3，0，11)T 最优目标值：112/33.3.单单 纯纯 形形 法法123123 第一阶段问题（LP - 1） Max z = - x5 - x6 s.t. x1 + 2x2 + 3x3 + x5 = 15 2x1 + x2 + 5x3 + x6 = 20

55、x1 + 2x2 + 4x3 + x4 = 26 x1 , x2 , x3 , x4 , x5 , x6 03.3.单单 纯纯 形形 法法124124第一阶段第一阶段 (LP - 1）得到原问题的基本可行解: (0，15/7，25/7，52/7)T 3.3.单单 纯纯 形形 法法125125第二阶段第二阶段 把基本可行解填入表中得到原问题的最优解:(25/3，10/3，0，11)T 最优目标值：112/33.3.单单 纯纯 形形 法法126126 注意：单纯形法中 1 1、每一步运算只能用矩阵初等行变换；、每一步运算只能用矩阵初等行变换； 2 2、表中第、表中第3 3列列( (b b列列) )

56、的数总应保持非负的数总应保持非负（0 0）；）； 3 3、当所有检验数均非正（、当所有检验数均非正（0 0）时，得到）时，得到最优单纯形表。若直接对目标求最最优单纯形表。若直接对目标求最h h，要求要求所有所有检验数均非负；检验数均非负； 4 4、当当最最优优单单纯纯形形表表存存在在非非基基变变量量对对应应的的检验数为零时，可能存在无穷多解；检验数为零时，可能存在无穷多解；3.3.单单 纯纯 形形 法法127127 5、关于退化和循环。如果在一个基本可行解的基变量中至少有一个分量xBi=0 (i=1,2,m)，则称此基本可行解是退化的基本可行解。一般情况下，退化的基本可行解（极点）是由若干个不

57、同的基本可行解（极点）在特殊情况下合并成一个基本可行解（极点）而形成的。退化的结构对单纯形迭代会造成不利的影响。3.3.单单 纯纯 形形 法法128128 可能出现以下情况： 进行进基、出基变换后，虽然改变了基，但没有改变基本可行解（极点），目标函数当然也不会改进。进行若干次基变换后，才脱离退化基本可行解（极点），进入其他基本可行解（极点）。这种情况会增加迭代次数，使单纯形法收敛的速度减慢。 在特殊情况下，退化会出现基的循环，一旦出现这样的情况，单纯形迭代将永远停留在同一极点上，因而无法求得最优解。3.3.单单 纯纯 形形 法法129129 在单纯形法求解线性规划问题时，一旦出现这种因退化而导

58、致的基的循环，单纯形法就无法求得最优解，这是一般单纯形法的一个缺陷。但是实际上，尽管退化的结构是经常遇到的，而循环现象在实际问题中出现得较少。尽管如此，人们还是对如何防止出现循环作了大量研究。19521952年CharnesCharnes提出了“摄动法”，19541954年DantzigDantzig，OrdenOrden和WolfeWolfe又提出了“字典序法”，3.3.单单 纯纯 形形 法法130130 这些方法都比较复杂，同时也降低了迭代的速度。1976年，Bland提出了一个避免循环的新方法，其原则十分简单。仅在选择进基变量和出基变量时作了以下规定： 在选择进基变量时，在所有 j 0的

59、非基变量中选取下标最小的进基； 当有多个变量同时可作为出基变量时，选择下标最小的那个变量出基。这样就可以避免出现循环,当然，这样可能使收敛速度降低。3.3.单单 纯纯 形形 法法131131 合理利用线材问题：合理利用线材问题：如何下如何下料使用材最少。料使用材最少。 配料问题：配料问题：在原料供应量的在原料供应量的限制下如何获取最大利润。限制下如何获取最大利润。 投资问题：投资问题：从投资项目中选从投资项目中选取方案，使投资回报最大。取方案，使投资回报最大。4.4.线性规划应用线性规划应用 一、线性规划一、线性规划-132132 产品生产计划：产品生产计划：合理利用人合理利用人力、物力、财力

60、等，使获利最力、物力、财力等，使获利最大。大。 劳动力安排：劳动力安排：用最少的劳动用最少的劳动力来满足工作的需要。力来满足工作的需要。 运输问题：运输问题：如何制定调运方如何制定调运方案，使总运费最小。案，使总运费最小。4.4.线性规划应用线性规划应用133133 数学规划的建模有许多共同点，要遵循下列原则： (1)容易理解。建立的模型不但要求建模者理解，还应当让有关人员理解。这样便于考察实际问题与模型的关系，使得到的结论能够更好地应用于解决实际问题。 (2)容易查找模型中的错误。这个原则的目的显然与(1)相关。常出现的错误有：书写错误和公式错误。4.4.线性规划应用线性规划应用134134

61、 (3)容易求解。对线性规划来说，容易求解问题主要是控制问题的规模，包括决策变量的个数和约束条件的个数。这条原则的实现往往会与(1)发生矛盾，在实现时需要对两条原则进行统筹考虑。4.4.线性规划应用线性规划应用135135 建立线性规划模型的过程可以分为四个步骤： (1)设立决策变量； (2)明确约束条件并用决策变量的线性等式或不等式表示； (3)用决策变量的线性函数表示目标，并确定是求极大（Max）还是极小（Min）； (4)根据决策变量的物理性质研究变量是否有非负性。4.4.线性规划应用线性规划应用136136 例2.12：某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下： 人力

62、资源分配的问题人力资源分配的问题设司机和乘务人员分别在各时间段一开始时上班，并连续工作8h，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?137137 解：设解：设 x xi i 表示第表示第i i班次时开始上班的司机和乘班次时开始上班的司机和乘务人员数务人员数, ,这样我们建立如下的数学模型。这样我们建立如下的数学模型。目标函数：目标函数：目标函数：目标函数：Min Min Min Min x x x x1 1 1 1 + + + + x x x x2 2 2 2 + + + + x x x x3 3 3 3 + + + + x x x x4 4 4 4 +

63、 + + + x x x x5 5 5 5 + + + + x x x x6 6 6 6 约束条件：约束条件：约束条件：约束条件：s.t.s.t.s.t.s.t. x x x x1 1 1 1 + + + + x x x x6 6 6 6 60 60 60 60 x x x x1 1 1 1 + + + + x x x x2 2 2 2 70 70 70 70 x x x x2 2 2 2 + + + + x x x x3 3 3 3 60 60 60 60 x x x x3 3 3 3 + + + + x x x x4 4 4 4 50 50 50 50 x x x x4 4 4 4 + +

64、 + + x x x x5 5 5 5 20 20 20 20 x x x x5 5 5 5 + + + + x x x x6 6 6 6 30 30 30 30 x x x x1 1 1 1, , , ,x x x x2 2 2 2, , , ,x x x x3 3 3 3, , , ,x x x x4 4 4 4, , , ,x x x x5 5 5 5, , , ,x x x x6 6 6 6 0 0 0 0 人力资源分配的问题人力资源分配的问题138138例例2.13:2.13:某工厂要做某工厂要做100100套钢架，每套用长为套钢架，每套用长为2.9 m, 2.9 m, 2.1m,

65、1.5m2.1m, 1.5m的圆钢各一根。已知原料每根长的圆钢各一根。已知原料每根长7.4 m7.4 m，问：应如何下料，可使所用原料最省？问：应如何下料，可使所用原料最省？套裁下料问题套裁下料问题解:考虑下列各种下料方案（按一种逻辑顺序给出）把各种下料方案按剩余料头从小到大顺序列出139139假设假设 x x1 1, ,x x2 2, ,x x3 3, ,x x4 4, ,x x5 5 分别为上面前分别为上面前 5 5 种方案下料的种方案下料的原材料根数。我们建立如下的数学模型。原材料根数。我们建立如下的数学模型。目标函数：目标函数： MinMin x x1 1 + + x x2 2 + +

66、 x x3 3 + + x x4 4 + + x x5 5 约束条件：约束条件： s.t.s.t. x x1 1 + 2 + 2x x2 2 + + x x4 4 100 100 2 2x x3 3 + 2+ 2x x4 4 + + x x5 5 100 100 3 3x x1 1 + + x x2 2 + 2 + 2x x3 3+ 3+ 3x x5 5 100 100 x x1 1, ,x x2 2, ,x x3 3, ,x x4 4, ,x x5 5 0 0套裁下料问题套裁下料问题140140 例2.14:明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配 三个车间。甲、乙两种产

67、品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如下表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？生产计划的问题生产计划的问题141141解：解：设 x1 ,x2 ,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4, x5 分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。 生产计划的问题生产计划的问题142142 求 xi 的利润:利润 = 售价 - 各成本之和可得到 xi（i=1,2,3,4,51,2,3,4,5）的利润分别为1515、1010、7 7、13

68、13、9 9元。 这样我们建立如下数学模型： 目标函数: Max 15x1+10x2+7x3+13x4+9x5 约束条件： s.t. 5x1+10x2+7x3 8000 6x1+4x2+8x3+6x4+4x5 12000 3x1+2x2+2x3+3x4+2x5 10000 x1,x2,x3,x4,x5 0 生产计划的问题生产计划的问题143143 例例2.15:2.15:永久机械厂生产、三种产品，均要经过 A、B 两道工序加工。假设有两种规格的设备A1、A2能完成 A 工序；有三种规格的设备B1、 B2 、B3能完成 B 工序。可在 A、B的任何规格的设备上加工； 可在任意规格的A设备上加工，

69、但对B工序,只能在B1设备上加工； 只能在A2与B2设备上加工；数据如下表。问：为使该厂获得最大利润，应如何制定产品加工方案？ 生产计划的问题生产计划的问题144144解：解：设 xijk 表示第 i 种产品，在第 j 种工序上的第 k 种设备上加工的数量. 利润利润 = = （销售单价（销售单价 - - 原料单价）原料单价） 产品件产品件数数 之和之和 - - （每台时的设备费用（每台时的设备费用设备实际使设备实际使用的总台时数）之和用的总台时数）之和。 生产计划的问题生产计划的问题145145这样我们建立如下的数学模型:Max 0.75x111+0.7753x112+1.15x211+1.

70、3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123 s.t 5x111+10x2116000 （ 设备 A1 ） 7x112+9x212+12x31210000（ 设备 A2 ） 6x121+ 8x221 4000 ( 设备 B1 ） 4x122+11x322700 ( 设备 B2 ） 7x123 4000 （ 设备 B3 ）生产计划的问题生产计划的问题146146x111+ x112- x121- x122- x123 = 0 (产品在A、B工序加工的数量相等）x211+ x212- x221 = 0 (产

71、品在A、B工序加工的数量相等）x312 - x322 = 0(产品在A、B工序加工的数量相等）xijk0, i=1,2,3; j=1,2; k=1,2,3 生产计划的问题生产计划的问题147147 例2.14:某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如下表。问：该厂应如何安排生产，使利润收入为最大？配料问题配料问题148148配料问题配料问题 解：设 xij 表示第 i 种（甲、乙、丙） 产品中原料 j 的含量。这样我们建立数学 模型时，要考虑： 对于甲： x11，x12，x13； 对于乙： x21，x22，x23； 对于丙： x31，x32，x33； 对于原料

72、1： x11，x21，x31； 对于原料2： x12，x22，x32； 对于原料3： x13，x23，x33；149149目标函数： 利润最大，利润 = 收入 - 原料支出 约束条件：规格要求 4 个； 供应量限制 3 个。 Max z z z z = -15= -15= -15= -15x x x x11111111+25+25+25+25x x x x12121212+15+15+15+15x x x x13131313-30-30-30-30x x x x21212121+10+10+10+10x x x x22222222-40-40-40-40x x x x31313131-10-1

73、0-10-10x x x x33333333 配料问题配料问题150150s.t.s.t. 0.5 x11-0.5 x12 -0.5 x13 0 （原材料1不少于50%） -0.25x11+0.75x12 -0.25x13 0 （原材料2不超过25%） 0.75x21-0.25x22 -0.25x23 0 （原材料1不少于25%） -0.5 x21+0.5 x22 -0.5 x23 0 （原材料2不超过50%） x11+x21+x31 100 (供应量限制） x12+x22+x32 100 (供应量限制） x13+x23+x33 60 (供应量限制） xij0 ,i = 1,2,3; j =

74、1,2,3配料问题配料问题151151 例2.17：某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A ：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资， 第五年末能收回本利155%，但规定最大投资额不能超过100万元。 投资问题投资问题152152 据测定每万元每次投资的风险指数如下表：投资问题投资问题153153 a）应如何确定这些项目的

75、每年投资额，使得第五年年末拥有资金的本利金额为最大？ b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？问：问：投资问题投资问题154154投资问题投资问题 解：解：1 1）确定决策变量：连续投资问题 设 xij ( i = 15，j = 1、2、3、4)表示第 i 年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下决策变量： A x11 x21 x31 x41 x51 B x12 x22 x32 x42 C x33 D x24155155 2 2 2 2）约束条件：）约束条件：）约束条件

76、：）约束条件： 第一年：第一年：A A当年末可收回投资，故第一年年初当年末可收回投资，故第一年年初应把全部资金投出去，于是：应把全部资金投出去，于是： x x1111+ + x x12 12 = 200= 200 第二年：第二年：B B次年末才可收回投资故第二年年初次年末才可收回投资故第二年年初的资金为的资金为1.11.1x x1111，于是：于是： x x21 21 + + x x2222+ + x x2424 = 1.1 = 1.1x x1111 第三年：第三年：年初的资金为年初的资金为1.11.1x x2121+1.25+1.25x x1212，于是于是 ： x x31 31 + + x

77、 x3232+ + x x3333 = 1.1 = 1.1x x2121+ 1.25+ 1.25x x1212 第四年：第四年：年初的资金为年初的资金为1.11.1x x3131+1.25+1.25x x2222，于是：于是： x x41 41 + + x x4242 = 1.1 = 1.1x x3131+ 1.25+ 1.25x x2222 第五年：第五年：年初的资金为年初的资金为1.11.1x x4141+1.25+1.25x x3232，于是：于是： x x51 51 = 1.1= 1.1x x4141+ 1.25+ 1.25x x3232 B B、C C、D D的投资限制：的投资限制：

78、 x xi i2 2 30 ( 30 ( i i=1=1，2 2，3 3，4 )4 )，x x3333 80 80，x x2424 100 100投资问题投资问题156156a)Max z=1.1x51+1.25x42+1.4x33+1.55x24s.t.x11+ x12 = 200 x21 + x22+ x24 = 1.1x11 x31 + x32+ x33 = 1.1x21+ 1.25x12 x41 + x42 = 1.1x31+ 1.25x22 x51 = 1.1x41+ 1.25x32 xi2 30 ( i =1、2、3、4 )， x33 80，x24 100 xij0(i=1,2,3

79、,4,5；j=1,2,3,4）3 3）目标函数及模型：目标函数及模型：投资问题投资问题157157b)b) MinMin f f = = （x x1111+ +x x2121+ +x x3131+ +x x4141+ +x x5151)+ )+ 3( 3(x x1212+ +x x2222+ +x x3232+ +x x4242)+4)+4x x3333+5.5+5.5x x24 24 s.t.s.t. x x1111+ + x x12 12 200 200 x x21 21 + + x x2222+ + x x2424 1.1 1.1x x1111 x x31 31 + + x x3232+

80、 + x x3333 1.1 1.1x x2121+ 1.25+ 1.25x x1212 x x41 41 + + x x4242 1.1 1.1x x3131+ 1.25+ 1.25x x2222 x x51 51 1.1 1.1x x4141+ 1.25+ 1.25x x3232 x xi i2 2 30 ( 30 ( i i =1 =1、2 2、3 3、4 )4 )， x x3333 80 80，x x2424 100 100 1.11.1x x51 51 + 1.25+ 1.25x x4242+ 1.4+ 1.4x x3333+ 1.55+ 1.55x x2424 330 330 x

81、xijij0(0(i i=1,2,3,4,5=1,2,3,4,5；j j = 1,2,3,4 = 1,2,3,4）投资问题投资问题158158第三章 线性规划问题的对偶与灵敏度分析线性规划的对偶问题概念、理论及经济意义线性规划的对偶单纯形法线性规划的灵敏度分析本章内容重点1591591.1.线性规划对偶问题线性规划对偶问题 对偶原理 对偶问题定义 线性规划问题写出其对偶问题，要掌握在对称形式和非对称情况下由原问题写出对偶问题的方法。 对偶定理 只需了解原问题与对偶问题解的关系，证明从略。160160 1.对偶问题： 若第二章例2.1问题的设备都用于外协加工，工厂收取加工费。试问：设备 A、B、

82、C 每工时各如何收费才最有竞争力？ 设 y1 ，y2 ，y3 分别为每工时设备 A、B、C 的收取费用。1.1.线性规划对偶问题线性规划对偶问题161161线性规划原问题线性规划原问题 例2.1:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。产品甲产品乙设备能力（h）设备A3 32 26565设备B2 21 14040设备C0 03 37575利润（元/件）1500150025002500162162 Max z = 1500x1 + 2500x2 s.t. 3x1 +

83、 2x2 65 2x1 + x2 40 原问题原问题 3x2 75 x1 ,x2 0 Min f = 65y1+ 40y2 + 75y3 s.t. 3y1+2y2 1500 （不少于甲产品的利润）不少于甲产品的利润） 2y1+y2+3y3 2500 对偶问题对偶问题 （不少于乙产品的利润）不少于乙产品的利润） y1, y2 , y3 01.1.线性规划对偶问题线性规划对偶问题163163 2、对偶定义 对称形式： 互为对偶 (LP) Max z = cT x (DP) Min f = bT y s.t. Ax b s.t. AT y c x 0 y 0 “Max - ” “Min- ”1.1.

84、线性规划对偶问题线性规划对偶问题164164 一对对称形式的对偶规划之间具有下面的对应关系。 (1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，”和“min，”相对应。1.1.线性规划对偶问题线性规划对偶问题165165 (2)从约束系数矩阵看：一个模型中为，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。 (3)从数据b、C的位置看：在两个规划模型中，b和C的位置对换。 (4)两个规划模型中的变量皆非负。1.1.线性规划对偶问题线性规划对偶问题166166 非对称形式非

85、对称形式的对偶规划的对偶规划 一一般般称称不不具具有有对对称称形形式式的的一一对对线线性性规规划划为为非对称形式的对偶规划。非对称形式的对偶规划。 对对于于非非对对称称形形式式的的规规划划，可可以以按按照照下下面面 的对应关系直接给出其对偶规划。的对应关系直接给出其对偶规划。 （1 1）将将模模型型统统一一为为“maxmax，”或或“minmin，” ” 的的形形式式，对对于于其其中中的的等等式式约约束束按按下下面面（2 2）、（）、（3 3）中的方法处理；）中的方法处理； （2 2）若若原原规规划划的的某某个个约约束束条条件件为为等等式式约约束束，则则在在对对偶偶规规划划中中与与此此约约束束

86、对对应应的的那那个个变变量量取取值值没有非负限制；没有非负限制；1.1.线性规划对偶问题线性规划对偶问题167167 （3 3）若原规划的某个变量的值没有非负限若原规划的某个变量的值没有非负限 制，则在对偶问题中与此变量对应的那个制，则在对偶问题中与此变量对应的那个 约束为等式。约束为等式。 下面对关系（下面对关系（2 2）作一说明。对于关系（）作一说明。对于关系（3 3） 可以给出类似的解释。可以给出类似的解释。 设原规划中第一个约束为等式：设原规划中第一个约束为等式： a a1111x x1 1 + + + + a a1n1nx xn n = = b b1 1 那么，这个等式与下面两个不等

87、式等价那么，这个等式与下面两个不等式等价1.1.线性规划对偶问题线性规划对偶问题1681681.1.线性规划对偶问题线性规划对偶问题这样，原规划模型可以写成1691691.1.线性规划对偶问题线性规划对偶问题 此时已转化为对称形式，直接写出对偶规划此时已转化为对称形式，直接写出对偶规划这里，把 y1 看作是 y1 = y1 - y1，于是 y1 没有非负限制，关系（2）的说明完毕。1701701.1.线性规划对偶问题线性规划对偶问题 例3.1 写出下面线性规划的对偶规划模型解 先将约束条件变形为“”形式1711711.1.线性规划对偶问题线性规划对偶问题再根据非对称形式的对应关系，直接写出对偶

88、规划1721721.1.线性规划对偶问题线性规划对偶问题173173 3.对偶定理(原问题与对偶问题解的关系）考虑（LP）和（DP） 定理3-1 (弱对偶定理） 若 x, y 分别为（LP) 和（DP）的可行解，那么cTx bTy。 推论 若（LP）可行，那么（LP）无有限最优解的充分必要条件是（LD）无可行解。1.1.线性规划对偶问题线性规划对偶问题174174 定理3-2 (最优性准则定理) 若x,y分别(LP),(DP)的可行解,且cTx=bTy ，那么x,y分别为(LP)和(DP)的最优解。 定理3-3 (主对偶定理) 若(LP)和(DP)均可行 那么(LP)和(DP)均有最优解,且最

89、优值相等。 以上定理、推论对任意形式的相应性规划的对偶均有效1.1.线性规划对偶问题线性规划对偶问题175175 4.4.影子价格影子价格 是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。 若x*,y* 分别为（LP）和（DP）的最优解， 那么， cT x* = bT y* 。 根据 f = bTy*=b1y1*+b2y2*+bmym* 可知 f / bi = yi* yi* 表示 bi 变化1个单位对目标 f 产生的影响，称 yi* 为 bi的影子价格。 注意：注意：若 B 是最优基， y* = (BT)-1 cB 为影子价格向量。1.1.线性规划对偶问题线性规划对偶问题176

90、176 影子价格的经济含义 (1)影子价格是对现有资源实现最大效益时的一种估价 企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。1.1.线性规划对偶问题线性规划对偶问题1771771.1.线性规划对偶问题线性规划对偶问题 （2 2） 影影子子价价格格表表明明资资源源增增加加对对总总效效益益产产生生的的影影响响。根根据据推推推推论论论论“设设x x0 0和和y y0 0分分别别为为原原规规划

91、划（P P）和和对对偶偶规规划划（D D）的的可可行行解解，当当cxcx0 0= =b bT Ty y0 0时时，x x0 0、y y0 0分分别别是是两两个个问问题题的的最最优优解解”可知，在最优解的情况下，有关系可知，在最优解的情况下，有关系 因因此此，可可以以将将z z* *看看作作是是b bi i, ,i i=1,2=1,2， , ,m m的的函数，对函数，对b bi i求偏导数可得到求偏导数可得到 这这说说明明，如如果果右右端端常常数数增增加加一一个个单单位位，则则目目标函数值的增量将是标函数值的增量将是178178 影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如

92、果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。1.1.线性规划对偶问题线性规划对偶问题179179 需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。另外，影子价格的经济含义（2），是指资源在一定范围内增加时的情况，当某种资源的增加超过了这个“一定的范围”时，总利润的增加量则不是按照影子价格给出的数值线性地增加。这个问题还将在灵敏度分析一节中讨论。1.1.线性规划对偶问题线性规划对偶问题180180 5.由最优单纯形表求对偶问题最优解 标准形式： Max z = 50 x1 + 100

93、x2 s.t. x1 + x2 + x3 = 300 2x1 + x2 + x4 = 400 x2 + x5 = 250 x1 ,x2 ,x3 ,x4 ,x5 01.1.线性规划对偶问题线性规划对偶问题181181-c-cB BT TB B-1-1I IB B=(p p1 1, p, p4 4,p,p2 2 )oTB B-1-1最优解 x1 = 50 x2 = 250 x4 = 50影子价格影子价格 y y1 1 = 50 = 50 y y2 2 = 0 = 0 y y3 3 = 50 , = 50 , B B-1-1对应的检验数对应的检验数 T T = = c cB BT TB B-1-1

94、。 1.1.线性规划对偶问题线性规划对偶问题182182 对偶单纯形法的基本思想 对偶单纯形法的基本思想是：从原规划的一个基基本本解解出发，此基本解不一定可行，但它对应着一个对对偶偶可可行行解解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。2.2.对偶单纯形法对偶单纯形法183183 如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同

95、时得到对偶规划与原 规划的可行解时，便 得到原规划的最优解。2.2.对偶单纯形法对偶单纯形法184184 对偶单纯形法在什么情况下使用 ： 应用前提：有一个基，其对应的基满足: 单纯形表的检验数行全部非正（对偶可行）； 变量取值可有负数（非可行解）。 注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。2.2.对偶单纯形法对偶单纯形法185185 1.1.建立初始对偶单纯形表建立初始对偶单纯形表, ,对应一个基本解对应一个基本解, ,所有检验数均非正所有检验数均非正, ,转转2 2； 2.2.若若b b0,0,则得到最优解则得到最优解, ,停止停止; ;否则否则, ,若有若

96、有b bk k00则选则选k k行的基变量为出基变量行的基变量为出基变量, ,转转3 3 3. 3.若所有若所有a akjkj0( 0( j j = 1,2, = 1,2,n n ) )，则原则原问题无可行解问题无可行解, ,停止停止; ;否则否则, ,若有若有a akjkj0 0 则选则选 =min=min j j / / a akjkja akjkj00= r r/a akrkr那么那么 x xr r为进基变量为进基变量, ,转转4 4； 4.4.以以a akrkr为转轴元为转轴元, ,作矩阵行变换使其变为作矩阵行变换使其变为1,1,该列其他元变为该列其他元变为0,0,转转2 2。 对偶单

97、纯形法求解线性规划问题对偶单纯形法求解线性规划问题过程：过程：2.2.对偶单纯形法对偶单纯形法186186例例3.23.2：求解线性规划问题：求解线性规划问题：求解线性规划问题：求解线性规划问题： 标准化：标准化： Max z = - 2x1 - 3x2 - 4x3 s.t. -x1-2x2-x3+x4= -3 -2x1+x2-3x3+x5= -4 x1,x2,x3,x4,x5 0Min f = 2x1 + 3x2 + 4x3 S.t. x1 + 2x2 + x3 3 2x1 - x2 + x3 4 x1 , x2 , x3 0 2.2.对偶单纯形法对偶单纯形法187187表格对偶单纯形法2.

98、2.对偶单纯形法对偶单纯形法188188单纯形法和对偶单纯形法步骤单纯形法和对偶单纯形法步骤是是是是否否否否所有所有得到最优解计算计算典式对应原规划的基本解是可行的典式对应原规划的基本解的检验数所有所有计算计算以为中心元素进行迭代以为中心元素进行迭代停没有最优解没有最优解单纯形法对偶单纯形法0csMinj/asjasj0brMin-bi/airair03.3.灵敏度分析灵敏度分析203203 例3.5: 上例最优单纯形表如下 3.3.灵敏度分析灵敏度分析204204 0 0.25 0 这里 B B-1 = -2 0.5 1 0.5 -0.125 0 各列分别对应 b1、b2、b3 的单一变化因

99、此，设 b1 增加 4，则 x1 ,x5 ,x2分别变为：4+04=4, 4+(-2)4=-4 dj 的运输问题，得到的数学模 i=1 j=1型为2.2.运输问题求解运输问题求解 表上作业法表上作业法 2692692.2.运输问题求解运输问题求解 表上作业法表上作业法 m n Min f = cij xij i=1 j=1 n s.t. xij si i = 1,2,m j=1 m xij =dj j = 1,2,n i=1 xij0(i=1,2,m;j=1,2,n) 270270 只要在模型中的产量限制约束（前m个不等式约束）中引入m个松弛变量xin+1 i= 1,2,m 即可，变为： n

100、xij+xin+1=si i=1,2,mj=1然后，需设一个销地B n+1,它的销量为： m n bn+1= si- d dj j i=1 j=12.2.运输问题求解运输问题求解 表上作业法表上作业法 271271 这里，松弛变量 x i n+1 可以视为从产地 A i 运往销地 B n+1 的运输量，由于实际并不运送，它们的运费为 c i n+1 = 0 i = 1,2,m。于是，这个运输问题就转化成了一个产销平衡的问题。2.2.运输问题求解运输问题求解 表上作业法表上作业法 272272 例4.2:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各

101、产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？2.2.运输问题求解运输问题求解 表上作业法表上作业法 273273 解：增加一个虚设的销地运输费用为02.2.运输问题求解运输问题求解 表上作业法表上作业法 274274 2.销量大于产量的情况 m n 考虑si0所以 d2(x2)=d2|13-x2d217-x2由此 f2(x2)=5(13-x2)-13x2+377 =-18x2+442, d2*=13-x2生生 产产 库库 存存 问问 题题415415对于k=1f1(x1)=minc1d1+f2(x2) d1D1(x1) =min11d1+442-18x2 d1D1

102、(x1) =min11d1+442-18(x1-r1+d1) d d1 1 D D1 1( (x x1 1) ) =min11d1+442-18(x1-0+d1) d d1 1 D D1 1( (x x1 1) ) =min-7d1-18x1+442 d d1 1 D D1 1( (x x1 1) ) D D1 1( (x x1 1)=)=d d1 1| |d d1 1 0,0,r r2 2 x x1 1- -r r1 1+ +d d1 1 H H = =d d1 1| |d d1 1 0,0,r r2 2+ +r r1 1- -x x1 1 d d1 1 H H+ +r r1 1- -x x

103、1 1 = =d d1 1| |d d1 1 0,8-0,8-x x1 1 d d1 1 9-9-x x1 1 生生 产产 库库 存存 问问 题题416416根据题意 x1=2所以 D1(x1)=d1| 6d17由此 d1=7f1(x1)=-7d1-18x1+442 =-77182442 =357将以上结果总结成下表：生生 产产 库库 存存 问问 题题417417设设 备备 更更 新新 问问 题题418418 一台设备的价格为P，运行寿命为n年，每年的维修费用是设备役龄的函数，记为C(t)，新设备的役龄为t=0。旧设备出售的价格是设备役龄的函数，记为S(t)。在n年末，役龄为t的设备残值为R(

104、t)。现有一台役龄为T的设备，在使用过程中，使用者每年都面临“继续使用”或“更新”的策略，设设 备备 更更 新新 问问 题题419419420420设设 备备 更更 新新 问问 题题421421例5.10：设具体数据如下：设设 备备 更更 新新 问问 题题4224224234234244244254254264264274274284284294294304309797431431 由以上计算可知，本问题有两个决策，它们对应的最小费用都是115。 这两个决策是 设设 备备 更更 新新 问问 题题432432第六章 排队论基本概念输入过程和服务时间分布泊松输入指数服务排队模型其他模型选介排队系统

105、的优化目标与最优化问题本章内容重点433433 排排队队论论(Queuing (Queuing Theory)Theory)，又又称称随随机机服服务务系系统统理理论论(Random (Random Service Service System System Theory),Theory),是是一一门门研研究究拥拥挤挤现现象象( (排排队队、等等待待) )的的科科学学。具具体体地地说说，它它是是在在研研究究各各种种排排队队系系统统概概率率规规律律性性的的基基础础上上，解解决决相相应应排排队队系系统统的的最最优优设设计计和和最优控制问题。最优控制问题。前前 言言434434 排排队队是是我我们们在

106、在日日常常生生活活和和生生产产中经常遇到的现象中经常遇到的现象:上、下班搭乘公共汽车；上、下班搭乘公共汽车；顾客到商店购买物品；顾客到商店购买物品；病员到医院看病；病员到医院看病；旅客到售票处购买车票；旅客到售票处购买车票；学学生生去去食食堂堂就就餐餐等等就就常常常常出出现现排排队队和等待现象。和等待现象。排队的不一定是人，也可以是物：排队的不一定是人，也可以是物：前前 言言435435通通讯讯卫卫星星与与地地面面若若干干待待传传递递的的信信息；息；生生产产线线上上的的原原料料、半半成成品品等等待待加加工；工；因因故故障障停停止止运运转转的的机机器器等等待待工工人人修理；修理；码头的船只等待装

107、卸货物；码头的船只等待装卸货物；要要降降落落的的飞飞机机因因跑跑道道不不空空而而在在空空中盘旋等等。中盘旋等等。前前 言言436436排队问题的共同特征排队问题的共同特征(1)(1)有有要要求求得得到到某某种种服服务务的的人人或或物物。排排队队论论里里把把要要求求服服务务的的对对象象统统称称为为“顾客顾客”(2)(2)有有提提供供服服务务的的人人或或机机构构。把把提提供供服服务务的的人人或或机机构构称称为为“服服务务台台”或或“服务员服务员”(3)(3)顾顾客客的的到到达达、服服务务的的时时间间至至少少有有一一个是个是随机的随机的，服从某种分布。，服从某种分布。前前 言言437437 不同的顾

108、客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图6-1至图6-5。图6-1 单服务台排队系统前前 言言438438图6-2 单队列S个服务台并联的排队系统图6-3 S个队列S个服务台的并联排队系统前前 言言439439图6-4 单队多个服务台的串联排队系统图6-5 多队多服务台混联、网络系统前前 言言440440图6-6 随机服务系统前前 言言一般的排队系统，都可由下面图6-6加以描述。441441面面对对拥拥挤挤现现象象，顾顾客客排排队队时时间间的的长长短短与与服服务务设设施施规规模模的的大大小小

109、，就就构构成成了了设设计计随随机机服服务务系系统统中中的的一一对矛盾。对矛盾。如如何何做做到到既既保保证证一一定定的的服服务务质质量量指指标标，又又使使服服务务设设施施费费用用经经济济合合理理，恰恰当当地地解解决决顾顾客客排排队队时时间间与与服服务务设设施施费费用用大大小小这这对对矛矛盾盾，这这就就是是排排队队论论所所要要研研究究解解决决的的问问题题之一。之一。前前 言言442442 排队论是1909年由丹麦工程师爱尔朗(A.KErlang)在研究电活系统时创立的，几十年来排队论的应用领域越来越广泛，理论也日渐完善。特别是自二十世纪60年代以来，由于计算机的飞速发展，更为排队论的应用开拓了宽阔

110、的前景。前前 言言443443一 排队系统的描述（一）系统特征和基本排队过程 任何一个排队问题的基本排队过程都可以用图6-6表示。从图6-6可知，每个顾客由顾客源按一定方式到达服务系统，首先加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务的顾客立即离开。1.1.基基 本本 概概 念念444444（二）排队系统的基本组成部分（二）排队系统的基本组成部分 通通常常，排排队队系系统统都都有有输输入入过过程程、服服务务规规则则和和服服务务台台等等3 3个个组组成成部分：部分： 1 1输输入入过过程程这这是是指指要要求求服服务务的的顾顾客客是是按按怎怎样样的的规规律律到到

111、达达排排队队系系统统的的过过程程，有有时时也也把把它它称称为为顾顾客客流流一一般般可可以以从从3 3个个方方面面来来描描述述个个输入过程。输入过程。 1.1.基基 本本 概概 念念4454451.1.基基 本本 概概 念念(1)、顾客总体数(又称顾客源、输入源)。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。例如，到售票处购票的顾客总数可以认为是无限的，而某个工厂因故障待修的机床则是有限的。446446(2)(2)顾顾客客到到达达方方式式。描描述述顾顾客客是是怎怎样样来来到到系系统统的的，他他们们是是单单个个到到达达，还还是是成成批批到到达达。病病人人到到医医院院看看病病是是顾顾客客单

112、单个个到到达达的的例例子子。在在库库存存问问题题中中如如将将生生产产器器材材进进货货或或产产品品入入库库看看作作是是顾顾客客，那那么么这这种种顾顾客客则是成批到达的。则是成批到达的。 1.1.基基 本本 概概 念念4474471.1.基基 本本 概概 念念(3)(3)顾顾客客流流的的概概率率分分布布，或或称称相相继继顾顾客客到到达达的的时时间间间间隔隔的的分分布布。这这是是求求解解排排队队系系统统有有关关运运行行指指标标问问题题时时，首首先先需需要要确确定定的的指指标标。这这也也可可以以理理解解为为在在一一定定的的时时间间间间隔隔内内到到达达K K个个顾顾客客( (K K=1=1、2 2、)

113、)的的概概率率是是多多大大。顾顾客客流流的的概概率率分分布布一一般般有有定定长长分分布布、二二项项分分布布、泊泊松松流流( (最最简简单单流流) )、爱爱尔尔朗朗分分布布等等若若干干种。种。448448 2.2.服服务务规规则则。这这是是指指服服务务台台从从队队列列中中选选取取顾顾客客进进行行服服务务的的顺顺序序。一一般般可可以以分分为为损损失失制制、等等待待制和混合制等制和混合制等3 3大类。大类。 (1)(1)损损失失制制。如如果果顾顾客客到到达达排排队队系系统统时时，所所有有服服务务台台都都已已被被占占用用，那那么么他他们们就就自自动动离离开开系系统统永永不再来。不再来。1.1.基基 本

114、本 概概 念念449449 (2)(2)等等待待制制。当当顾顾客客来来到到系系统统时时，所所有有服服务务台台都都不不空空，顾顾客客加加入入排排队队行行列列等等待待服服务务。等等待待制制中中，服服务务台台在在选选择择顾顾客客进进行行服服务务时时，常常有有如如下下四四种种规规则：则： 先先到到先先服服务务。按按顾顾客客到到达达的的先先后后顺顺序序对对顾顾客客进进行行服服务务，这这是是最最普普遍遍的情形。的情形。 后后到到先先服服务务。仓仓库库中中迭迭放放的的钢钢材材，后后迭迭放放上上去去的的都都先先被被领领走走，就就属属于这种情况。于这种情况。1.1.基基 本本 概概 念念450450 随随机机服

115、服务务。即即当当服服务务台台空空闲闲时时，不不按按照照排排队队序序列列而而随随意意指指定定某某个个顾顾客客去去接接受受服服务务，如如电电话话交换台接通呼叫电话就是一例。交换台接通呼叫电话就是一例。 优优先先权权服服务务。如如老老人人、儿儿童童先先进进车车站站；危危重重病病员员先先就就诊诊；遇遇到到重重要要数数据据需需要要处处理理计计算算机机立立即即中中断断其其他他数数据据的的处处理理等等，均均属属于于此种服务规则。此种服务规则。1.1.基基 本本 概概 念念451451 (3)(3)混混合合制制等等待待制制与与损损失失制制相相结结合合的的一一种种服服务务规规则则，一一般般是是指指允允许许排排队

116、队，但但又又不不允允许许队队列列无无限限长长下下去去。具具体体说说来来，大大致致有有三三种：种： 队队长长有有限限。当当排排队队等等待待服服务务的的顾顾客客人人数数超超过过规规定定数数量量时时，后后来来的的顾顾客客就就自自动动离离去去，另另求求服服务，即系统的等待空间是有限的。务，即系统的等待空间是有限的。1.1.基基 本本 概概 念念452452 等等待待时时间间有有限限。顾顾客客在在系系统统中中的的等等待待时时间间不不超超过过某某一一给给定定的的长长度度T T，当当等等待待时时间间超超过过T T时时，顾顾客客将将自自动动离离去去，并并不不再再回回来来。如如易易损损坏坏的的电电子子元元器器件

117、件的的库库存存问问题题，超超过过一一定定存存储储时时间间的的元元器器件件被被自自动动认认为为失失效效。又又如如顾顾客客到到饭饭馆馆就就餐餐，等等了了一一定定时时间间后后不不愿愿再再等而自动离去另找饭店用餐。等而自动离去另找饭店用餐。1.1.基基 本本 概概 念念453453 逗逗留留时时间间有有限限。例例如如用用高高射射炮炮射射击击敌敌机机，当当敌敌机机飞飞越越高高射射炮炮射射击击有有效效区区域域的的时时间间为为t t时时，若若在在这这个个时时间间内未被击落，也就不可能再被击落了。内未被击落，也就不可能再被击落了。 不难注意到，不难注意到，损失制和等待制可损失制和等待制可看成是混合制的特殊情形

118、，如记看成是混合制的特殊情形，如记s s为为系统中服务台的个数，则当系统中服务台的个数，则当K K= =s s时，时，混合制即成为损失制；当混合制即成为损失制；当K K=时，混时，混合制即成为等待制。合制即成为等待制。1.1.基基 本本 概概 念念454454 3 3服服务务台台情情况况。服服务务台台可可以以从从以以下下3 3方面来描述：方面来描述： (1) (1) 服务台数量及构成形式服务台数量及构成形式 单队单队单服务台式；单服务台式； 单队单队多服务台并联式；多服务台并联式； 多队多队多服务台并联式；多服务台并联式； 单队单队多服务台串联式；多服务台串联式； 单队单队多服务台并串联混合式

119、多服务台并串联混合式, , 多队多队多服务台并串联混合式多服务台并串联混合式等等。等等。1.1.基基 本本 概概 念念455455 (2) (2) 服服务务方方式式。这这是是指指在在某某一一时时刻刻接接受受服服务务的的顾顾客客数数，它它有有单单个个服服务和成批服务两种。务和成批服务两种。 (3) (3) 服服务务时时间间的的分分布布。在在多多数数情情况况下下，对对每每一一个个顾顾客客的的服服务务时时间间是是一一随随机机变变量量，其其概概率率分分布布有有定定长长分分布布、负负指指数数分分布布、K K级级爱爱尔尔朗朗分分布布、一一般般分分布布( (所所有有顾顾客客的的服服务务时时间间都都是是独立同

120、分布的独立同分布的) )等等。等等。1.1.基基 本本 概概 念念456456（三）排队系统的描述符号与分类（三）排队系统的描述符号与分类 为了区别各种排队系统，根据输入过程、排队规则和服务机制的变化对排队模型进行描述或分类，DGKendall提出了一种目前在排队论中被广泛采用的“Kendall记号”，完整的表达方式通常用到6个符号并取如下固定格式：A A/B/C/D/E/F/B/C/D/E/F 各符号的意义为：1.1.基基 本本 概概 念念457457A A表表示示顾顾客客相相继继到到达达间间隔隔时时间间分分布布，常用下列符号：常用下列符号：M表示到达过程为泊松过程或负指数分布；D表示定长输

121、入；Ek表示k阶爱尔朗分布；G表示一般相互独立的随机分布。1.1.基基 本本 概概 念念4584581.1.基基 本本 概概 念念B表示服务时间分布，所用符号与表示顾客到达间隔时间分布相同。M表示服务过程为泊松过程或负指数分布；D表示定长分布；Ek 表示k阶爱尔朗分布；G表示一般相互独立的随机分布。459459C C表示服务台表示服务台( (员员) )个数：个数： “1”1”则则表表示示单单个个服服务务台台，“s s”(”(s s1)1)表示多个服务台。表示多个服务台。D D表表示示系系统统中中顾顾客客容容量量限限额额，或或称称等等待待空空间间容容量量；如如系系统统有有K K个个等等待待位位子

122、子，则则 00K K00为为一一常常数数，表表示示单单位位时时间间内内到到达达顾顾客客的的平平均均数数，又又称称为为顾顾客客的平均到达率。的平均到达率。 对对于于泊泊松松流流，不不难难证证明明其其相相继继顾顾客客到到达达时时间间间间隔隔 i i，i i=1,2,=1,2,是是相相互互独独立立同同分分布布的的，其其分分布布函函数数为为负负指指数分布：数分布： （6-66-6）2.2.输入过程和服务时间分布输入过程和服务时间分布480480 3.爱爱尔尔朗朗输输入入. 这是指相继顾客到达时间间隔相互独立，具有相同的分布，其分布密度为 （6-7） 其中k为非负整数。 可以证明，在参数为的泊松输人中，

123、对任意的j与k,设第j与第j+k个顾客之间的到达间隔为 。则随机变量Tk的分布必遵从参数为的爱尔朗分布，其分布密度为：2.2.输入过程和服务时间分布输入过程和服务时间分布481481 例某排队系统有并联的例某排队系统有并联的k k个服务台，顾个服务台，顾 客客流流为为泊泊松松流流，规规定定第第i, K+i, 2K+i 个个顾顾客客排排入入第第i号号台台 ( i = 1,2,K )，则则第第K台台所所获获得得的的顾顾客客流流，即即为为爱爱尔尔朗朗输输入入流流，其其他他各各台台，从从它它的的第第一一个个顾顾客客到到达达以以后后开开始所获得的流也为爱尔朗输入流。始所获得的流也为爱尔朗输入流。 此此外

124、外，爱爱尔尔朗朗分分布布中中，当当K1时时将将化化为为负指数分布。负指数分布。2.2.输入过程和服务时间分布输入过程和服务时间分布482482 4.一般独立输入，即相继顾客到达时间间隔相互独立、同分布，分布函数F(t)是任意分布，因此，上面所述的所有输入都是一般独立分布的特例。 5.成批到达的输入。这时排队系统每次到达的顾客不一定是一个，而可能是一批，每批顾客的数目n是一个随机变量。其分布为： 到达时间间隔可能是上述几类输入中的一种。2.2.输入过程和服务时间分布输入过程和服务时间分布（6-8）483483 二、服务时间分布二、服务时间分布 1 1定定长长分分布布。每每一一个个顾顾客客的的服服

125、务务时时间间 都都是常数是常数，此时服务时间，此时服务时间t t的分布函数的分布函数 为：为： （6-96-9） 2 2负负指指数数分分布布。即即各各个个顾顾客客的的服服务务时时间间相互独立，具有相同的负指数分布：相互独立，具有相同的负指数分布： (6-10)(6-10) 其中其中 0 0为一常数，服务时间为一常数，服务时间t t的数学期望称为的数学期望称为平均服务时间。显然，对于负指数分布平均服务时间。显然，对于负指数分布2.2.输入过程和服务时间分布输入过程和服务时间分布484484 3.3.爱爱尔尔朗朗分分布布. . 即即每每个个顾顾客客的的服服务务时时间间相相互互独独立立，具具有有相相

126、同同的的爱爱尔尔朗朗分分布布。其其密密度度函数为函数为 其中其中 0 0为一常数，此种的平均服务时间为：为一常数，此种的平均服务时间为： K K=1=1时时爱爱尔尔朗朗分分布布化化归归为为负负指指数数分分布布当当K K时，得到长度为时，得到长度为1/1/ 的定长服务。的定长服务。2.2.输入过程和服务时间分布输入过程和服务时间分布 (6-11) (6-12) (6-13)485485 4.一般服务分布。所有顾客的服务时间都是相互独立具有相同分布的随机变量，其分布函数记B(X)，前面所述的各种服务分布都是一般服务分布的特例。 5.多个服务台的服务分布。可以假定各个服务台的服务分布参数不同或分布类

127、型不同。 6.服务时间依赖于队长的情况。指服务员排队的人愈多，服务的速度也就愈快。2.2.输入过程和服务时间分布输入过程和服务时间分布486486 三、排队论研究的基本问题 排队论研究的首要问题是排队系统主要数量指标的概率规律，即研究系统的整体性质，然后进一步研究系统的优化问题。与这两个问题相关的还包括排队系统的统计推断问题。 (1)通过研究主要数量指标在瞬时或平稳状态下的概率分布及其数字特征，了解系统运行的基本特征。 (2)统计推断问题，建立适当的排队模型是排队论研究的第一步，建立模型过程中经常会碰到如下问题：检验系统是否达到平稳状态；检验顾客相继到达时间间隔的相互独立性；确定服务时间的分布

128、及有关参数等。2.2.输入过程和服务时间分布输入过程和服务时间分布487487 (3)(3)系系统统优优化化问问题题，又又称称为为系系统统控控制制问问题题或或系系统统运运营营问问题题，其其基基本本目目的的是是使使系系统统处处于于最最优优或或最最合合理理的的状状态态。系系统统优优化化问问题题包包括括最最优优设设计计问问题题和和最最优优运运营营问问题题，其其内内容容很很多多，有有最最少少费费用用问问题题、服服务务率率的的控控制制问问题题、服服务务台台的的开开关关策策略略、顾顾客客( (或或服服务务) )根根据据优优先先权权的的最优排序等方面的问题。最优排序等方面的问题。 对对于于一一般般的的排排队

129、队系系统统运运行行情情况况的的分分析析，通通常常是是在在给给定定输输入入与与服服务务条条件件下下，通通过过求求解解系系统统状状态态为为n n( (有有n n个个顾顾客客) )的的概概率率P Pn n( (t t) )，再再进进行计算其主要的运行指标行计算其主要的运行指标: : 2.2.输入过程和服务时间分布输入过程和服务时间分布488488 系统中顾客数系统中顾客数( (队长队长) )的期望值的期望值L L或或L Ls s； 排排队队等等待待的的顾顾客客数数( (排排队队长长) )的的期期望望值值L Lq q； 顾顾客客在在系系统统中中全全部部时时间间( (逗逗留留时时间间) )的的期期望值望

130、值W W或或W Ws s； 顾客排队等待时间的期望值顾客排队等待时间的期望值W Wq q。 排排队队系系统统中中，由由于于顾顾客客到到达达分分布布和和服服务务时时间间分分布布是是多多种种多多样样的的，加加之之服服务务台台数数。顾顾客客源源有有限限无无限限，排排队队容容量量有有限限无无限限等等的的不不同同组组合合，就就会会有有不不胜胜枚枚举举的的不不同同排排队队模模型型，若若对对所所有有排排队队模模型型都都进进行行分分析析与与计计算算，不不但但十十分分繁繁杂杂而而且且也也没没有有必必要要。下下面面拟拟分分析析几几种种常常见见排排队队系系统统模模型。型。2.2.输入过程和服务时间分布输入过程和服务

131、时间分布489489 对于泊松输入负指数分布服务的排队系统的一般决策过程： 根据已知条件绘制状态转移速度图。 依据状态转移速度图写出各稳态概率之间的关系。 求出 P0 及 Pn 。3.3.泊松输入泊松输入指数服务排队模型指数服务排队模型490490 计算各项数量运行指标。 用系统运行指标构造目标 函数，对系统进行优化。 典型分布 泊松分布及其 性质，负指数分布及其性质泊松 分布 (平稳状态） 0 为单位 时间平均到达的顾客数 P I = n = n e- / n! (n=0,1,2,)3.3.泊松输入泊松输入指数服务排队模型指数服务排队模型491491 负指数分布 为平均服务率，即 单位时间服

132、务的顾客数。 P（服务时间 t ) = 1- e- t t 0 系统状态概率分布及状态转移速 度图 基本的概率分布推导 3.3.泊松输入泊松输入指数服务排队模型指数服务排队模型492492 系统状态概率分布： n：系统状态为n时，顾客进入系统的平均速度。 n：系统状态为n时，顾客离开系统的平均速度。 Pn(t):t时刻，系统内有几个顾客的概率。 (t,t+t)有一个顾客到达概率nt， 无顾客到达的概率1-nt（近似）3.3.泊松输入泊松输入指数服务排队模型指数服务排队模型493493各种方式发生概率表 3.3.泊松输入泊松输入指数服务排队模型指数服务排队模型494494Pn(t+t)=Pn(t

133、)(1-nt)(1-nt) +Pn-1(t)n-1 1t(1-n-1 1t)+Pn+1(t)(1- n+1 1t)n+1 1t+Pn(t)ntnt(dPn(t)/dt)=limt-0(Pn(t+t)-Pn(t)/t) (t2项都变为零) =Pn-1(t)n-1-Pn(t)(n+n)+Pn-1(t)n-13.3.泊松输入泊松输入指数服务排队模型指数服务排队模型方式1，2，3，4互不相容且完备，于是：495495 当当n n=0=0时时，只只有有方方式式1 1和和3 3，4 4发发生生，且且方方式式1 1中中无离去的概率为无离去的概率为1 1，则，则 d dP P0 0( (t t)/d)/dt

134、t=-=-P P0 0( (t t) )0 0+ +P P1 1( (t t) )1 1 我我们们假假设设系系统统是是稳稳态态的的，即即与与时时刻刻无无关关，于于是是可可得：得：d dPnPn( (t t)/d)/dt t=0=0；- -0 0P P0 0+ +1 1P P1 1=0=0 nn- -1 1P Pn n-1-1-(-(n n+ +n n) )P Pn n+ +n n+1+1P Pn n+1+1=0 =0 n n=1,2,3=1,2,3 0 0P P0 0= =1 1P P1 1, ,P P1 1= =0 0/ /1 1P P0 0 0 0P P0 0-(-(1 1+ +1 1)

135、)P P1 1+ +2 2P P2 2=0=0 1 1 P P1 1-(-(1 1+ +1 1) )P P1 1+ +2 2P P2 2=0=0 P P2 2=(=(1 1/2 2) )P P1 1=(=(0 01 1/ /1 12 2) )P P0 0 P Pn n=(=(n n-1-1/ /n n) )P Pn n-1-1=(=(i i=0=0n n-1-1i i/ /j j=1=1n n j j ) )p p0 03.3.泊松输入泊松输入指数服务排队模型指数服务排队模型4964960P0-(1+1)P1+2P2=01 P1-(1+1)P1+2P2=0P2=(1/2)P1=(01/12)P

136、0 n n-1 -1 n nPn=(n-1/n)Pn-1=(i / j)p0 i=0 j=1又知：Pn=1 (各事件两两不相容，且完备）P0+(0/1)P0+(10/2 1)P0+ n n-1 -1 n n(i / j )p0=1 i i=0 =0 j j=1=13 3、泊松输入泊松输入指数服务排队模型指数服务排队模型497497状态转移速度图由此图易得：转入率=转出率n=0时，0P0=1P1n一般，n-1Pn-1+n+1Pn+1=(n+n)Pn同样可得下列公式: n = 1,2, n n-1 -1 n nPn=(n-1/n)Pn-1=(i / j )p0 i=0 j=10n123021n-1

137、n1n32n+13 3、泊松输入泊松输入指数服务排队模型指数服务排队模型498498系统的运行指标：(稳态时）1.系统中顾客数的期望值： L=KPk k k=0=0 2.排队等待的顾客数的期望值：Lq q=(K-C) Pk kckc3 3、泊松输入泊松输入指数服务排队模型指数服务排队模型499499 3.有效到达率e: 稳态情况下，单位时间内进入系统的顾客数的期望值等于单位时间内离开系统的顾客数的期望值 即： e=e 当系统中有n个顾客时，每单位时间进入系统的顾客平均数为n，每单位时间离开系统的顾客平均数为n e=nPn e=nPn3 3、泊松输入泊松输入指数服务排队模型指数服务排队模型500

138、500 4.L ,L q,e ,W ,Wq之间的关系：Little证明了：W=L/e , Wq=Lq/e 几何解释： 稳态时，一个顾客，进入系统后，每单位时间，平均到达e顾客。 eeeee进入时刻离开时刻总时间Ws队长Ls由时间段内个e组成的Ls=eWs3 3、泊松输入泊松输入指数服务排队模型指数服务排队模型501501同理：Lq=eWq又 W=Wq+（1/）-W与Wq只相差一段平均服务时间1/ L=Lq+(e/)3 3、泊松输入泊松输入指数服务排队模型指数服务排队模型502502M/M/1 无限源系统无限源系统稳态概率方程：Pn= (/)Pn-1= (/)nP0 1n N0N-112N-2N

139、1M/M/1/N/ 参数 ，系统状态转移速度：503503 由 M/M/1 无限源系统无限源系统504504 N NL=nPn n n= =0 0 M/M/1 无限源系统无限源系统 各计算公式：e=nPn=(1-PN)+0PN (只有Pn不再进人，故n=0，其余均为)e =nPn=0P0+(1-P0)（同理）W =L/e , Wq=W -(1/), Lq=Wqe505505 其他指标：其他指标： 损损=-e=PN P闲闲=P0 （只有一个服务台）只有一个服务台） P忙忙=1-P0 ,M/M/1 无限源系统无限源系统506506 2.M/M/1/: M/M/1 无限源系统无限源系统 稳态概率方程

140、： Pn=（/）Pn-1=(/)nP0 令=/0n12n-1 当 1时, n不收敛，故应1, n=0 n=0即 k ) = k+1顾客逗留时间超过t的概率 P( U t ) = e-()t M/M/1 无限源系无限源系统统510510P1=/（+）P损=P忙=P1= /（+）P闲=P0= /（+）M/M/1 无限源系无限源系统统3.损失制M/M/1/1: 顾客到达若服务台被占用立即离开。直接可得： P0= (1-) / (1-)2 = 1 / (1+) = / (+) P0+P1=1 511511 1.M/M/C/NM/M/C 无限源系无限源系统统0N-112N-2c2cNCC-1ccC+13

141、(c-1)cc 稳态概率应满足的关系：当nc时， Pn=/(n) Pn-1当nc时， Pn =/(c) Pn-1 令=/（c） 系统负荷强度系数512512 c/nPn-1=cn/nnP0 n的情形=/(c)1时，不收敛，设1, M/M/C 无限源系无限源系统统 c c-1-1 P0=c n /nn+c c /c(c /1-)-1 n n=0=0515515 ( (c cn n / n/ n!) !) n nP P0 0 ncnc ( (c cc c/c/c!) !) n nP P0 0 n n c c M/M/C 无限源系统无限源系统Pn= Lq = ccc+1P0 / c! (1-)2e

142、= Wq = Lq/ W = Wq+ 1/ L=W = Lq+/516516 3.M/M/C 损 失 制 系 统（M/M/C/C/） 此即M/M/C/N中 N=C 的情形 M/M/C 无限源系统无限源系统 c c P0= cn / n!n-1 n n=0=0 Pn= cn / n!nP0e=(1-Pc) Lq=0, Wq=0(不等待) W=1/ L=eW=e/=(/) (1-Pc) 损=-e=Pc517517 例6.1:某火车站售票处有三个窗口，同时售各车次的车票。顾客到达服从泊松分布，平均每分钟到达=0.9（人），服务时间服从负指数分布，平均服务率=24（人/h），分两种情况：1. 顾客排成

143、一队，依次购票；2.顾客在每个窗口排一队，不准串队。 求:（1）售票处空闲的概率。 （2）平均等待时间和逗留时间。 （3）队长和队列长。例例 题题 解解 析析518518例例 题题 解解 析析稳态概率：稳态概率：当当当当n n n n3333时时时时 P P P Pn n n n=/ / / /（nnnn） P P P Pn n n n-1-1-1-1=(=(=(=(n n n n/n/n/n/n!)!)!)!)n n n nP P P P0 0 0 0 =3=3=3=3n n n n/n/n/n/n! ! ! !n n n nP P P P0 0 0 0 当当当当n n n n3 3 3 3

144、时时时时 P P P Pn n n n=/ / / /（cccc） P P P Pn n n n-1-1-1-1=(3=(3=(3=(33 3 3 3/3!)/3!)/3!)/3!)n n n nP P P P0 0 0 0 =4.5=4.5=4.5=4.5n n n nP P P P0 0 0 0 解：解：1. M/M/3/031232343单位应相同：单位应相同：=0.4（人/分钟） 记记= /（3）=0.9/(0.4*3)=0.75=0.9/(0.4*3)=0.75519519例例 题题 解解 析析 P0+3*0.75 P0+4.5*0.752 P0+4.5n P0 =1 n n= =3

145、 3 由Pn=1 n n= =0 0 P0= 1/(1+2.25+2.53125+4.53/(1-) =1/13.375 =0.0748P1=0.1683P2=0.1893 Lq=(n-c)Pn=33/3!4 P0 (n-3)n-3-1 n n = =c c+1 +1 n n = 4= 4 520520例例 题题 解解 析析S S= dF/ d=(1-)+/(1-)2于是：Lq=4.54P0/(1-)2=1.704 e=Wq=Lq/e=1.704/0.9=1.893分钟 F= S d=(n-3)n-3-1d= n-3 n n=4 =4 n n=4=4 =/(1-) S= (n-3)n-3-1

146、n n=4 =4 521521例例 题题 解解 析析Ws=Wq+ 1/=1.893+2.5=4.393分钟Ls=Ws=3.954故：售票处的空闲的概率为0.0748平均等待时间 Wq=1.893分钟， 平均逗留时间 W=4.393分钟队长 Ls=3.954(人) Lq=1.704(人)522522 2.M/M/1/ 三个系统并联：=0.3 =0.4 =/=0.75P0=1-=0.25 三 个 服 务 台 都 有 空 的 时 候 ，P03=0.0156Ls=/(1-)=3 e=0.3Lq=Ls-/=2.25Ws=Ls/=10Wq=Ws-1/=7.5例例 题题 解解 析析523523故售票处空闲的

147、概率为 0.0156例例 题题 解解 析析平均等待时间 Wq=7.5分钟 平均逗留时间 Ws=10分钟队长 Ls=3 三个队 共3+3+3=9队列长 Lq=2.25 共6.75（人）相比之下，排一队共享三个服务台效率好。524524顾客源有限的排队系统顾客源有限的排队系统 1.M/M/1/m/m系统 顾客源是m个，那么系统容量实质上 最多有m个足够。0m-112m-2m(m-1)2m(m-2)3顾客源中剩余的顾客数乘以每个顾客到达的概率525525顾客源有限的排队系统顾客源有限的排队系统Pn= m-(n-1)/Pn-1 1nm反复推得：Pn=m!/(m-n)!(/)nP0 1nm mm 代入P

148、n=1 n n= =0 0 mm m!/(m-n)!(/)nP0 =1 n n= =0 0 mm P0= m!/(m-n)!(/)n-1 n n= =0 0526526顾客源有限的排队系统顾客源有限的排队系统 mmPn=m!/(m-n)!(/)nm!/(m-k)!(/)k k-1-1 k k=0=0由(m-L)=(1-P0)得 L=m-/(1-P0)W=L/eWq=W-1/Lq=Wqee=(m-L) m mee=nPnnPn= =(m-nm-n) )P Pn n n n=0 =0 n n=0=0 m mm m = =(m Pm Pn n-n Pn Pn n) n n=0 =0 n n=0=0e

149、= (1-P0)527527 2. M/M/c/m/m系统顾客源有限的排队系统顾客源有限的排队系统0m-112m-2m(m-1)2c2cmCC-1(m(c-1)c顾客源还有顾客源还有mm-( -(c c-1)-1)个顾客每个顾客可个顾客每个顾客可到达的概率到达的概率 稳态概率方程Pn=(m-n+1)/nPn-1nc(m-n+1)/cPn-1cn m528528 m代入 Pn=1 得(整理后) n n=0=0顾客源有限的排队系统顾客源有限的排队系统反复代入得：Pn=m!/n!(m-n)!(/)nP0ncm!/c!(m-n)!cn-c(/)nP0cnm c c mm P0= m!/(m-n)!(/

150、)n+ m!/(c!(m-n)! n n= =0 0 n n= =c c+1+1 cn-c)(/)n-1529529于是可得 ： mmLq=(n-c)Pn n=cn=c+1+1e=(m-L)顾客源有限的排队系统顾客源有限的排队系统又 L=Lq+e/=Lq+/(m-L) 整理得：L=(L+/m)/(1+/)Wq=Lq/e , W=L/e530530应应 用用 举举 例例 例6.2:某汽车加油站有两台加油泵为汽车加油，加油站内最多能容纳6辆汽车。已知顾客到达的时间间隔服从负指数分布，平均每小时到达18辆汽车。若加油站中已有K辆车，当K2时，有K/6的顾客将自动离去。加油时间服从负指数分布，平均每辆

151、车需要5分钟。试求：非标准的M/M/2/N模型531531应应 用用 举举 例例 （1）系统空闲的概率为多少？ P0 （2）求系统满的概率是多少？ P6 6 （3）求系统服务台不空的概率 P2+P3+P4+P5+P6=1- P0-P1 （4）若服务一个顾客,加油站可以获 得利润10元,问平均每小时可获 得利润为多少元？ 10e （5）求每小时损失掉的顾客数？ 损=-e （6）加油站平均有多少辆车在等待加 油？ Lq 平均有多少个车位被占用？ L （7）进入加油站的顾客需要等多长的 时间才能开始加油？ Wq 进入加油站的顾 客需要多长时间才能离去？ W 532532稳态概率关系：P1=/P0=1

152、.5P0 =(3/2)P0P2=/(2)P1=0.75*1.5P0 =(9/8)P0应应 用用 举举 例例 解：状态转移速度图 以小时为单位=18 =60/5=12222205124632(1-2/6)(1-3/6)(1-4/6)(1-5/6)533533应应 用用 举举 例例P3=(4/6)/(2)P2=(1/2)(9/8)P0= (9/16)P P4=(3/6)/(3)P3=(3/8)(9/16)P0= (27/128)P0P5=(2/6)/(2)P4=(1/4)(27/512)P0 = (27/2048)P0P6=(1/6)/(2)P5=(1/8)(27/512)P0= (27/4096

153、)P0由 P0=P1+P2+P3+P4+P5+P6=1解得：P0=0.22433 P1 P2 P3 P4 P5 P60.33649 0.25237 0.12618 0.04732 0.01183 0.001480.33649 0.25237 0.12618 0.04732 0.01183 0.00148534534运行指标：(1) P0=0.22433(2) P6=0.00148(3) P忙=1-P0-P1=0.43918(4)e=0P0+P1+2(P2+P3+P4+P5+P6) = 14.578（辆/h） 10e= 145.78(元/小时）应应 用用 举举 例例535535(5)损=-e =

154、18-14.5782 =3.4218（辆/h）应应 用用 举举 例例(6)Lq=(3-2)P3+(4-2)P4+(5-2)P5+(6-2)P6 = 0.26223 L=Lq+e/ =0.26223+1.21485 =1.47708536536应应 用用 举举 例例(7)Wq=Lq/e =0.018h =1.08分钟 W=Wq+1/ =0.101h =6.08分钟537537 例6.3:某车站候车室在某段时间旅客到达服从泊松流分布，平均速度为50人/h，每位旅客在候车室内停留的时间服从负指数分布，平均停留时间为0.5h，问候车室内平均人数为多少？（L)应应 用用 举举 例例解：把旅客停留在候车室

155、看做服务，于是系统为M/M/=50=1/0.5=2538538稳态概率关系：Pn=/(n)Pn-1=.=1/n!(/)nP0 记 =/=50/2 =25 应应 用用 举举 例例0n12n-1n2(n+1)n+13 (n-1)(n+2)状态转移速度图: 539539应应 用用 举举 例例 P0=(1/n!n)-1= e- n n=0=0 L=nPn n n=1 =1 = e-1/(n-1)!n n n=1=1 =e-1/n!n=25(人) n n=0=0 代入 Pn=1 n n=0=0540540其他模型选介M/G/1排队系统 设顾客单位时间到达数为，服务时间为随机变量V，且 E(V) = 1

156、/ D(V) = 2 那么，服务强度 ，当 1时 P0 = 1 - 根据波拉切克-欣钦（Pollaczek-KhinchinePollaczek-Khinchine）公式可导出 Lq = (2+) / 2(1- )其它量的计算同前。541541其他模型选介M/D/1排队系统 设顾客单位时间到达数为，服务时间为一个常数v，则 E( v ) = v = 1 / D( v ) = 0那么，服务强度 ，当 1时 P0 = 1 - 根据上一模型的公式可直接得到 Lq = 2 / 2(1- )其它量的计算同前。542542 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题 从从经经济

157、济角角度度考考虑虑，排排队队系系统统的的费费用用应应该该包包含含以以下下两两个个方方面面：一一个个是是服服务务费费用用，它它是是服服务务水水平平的的递递增增函函数数；另另一一个个是是顾顾客客等等待待的的机机会会损损失失( (费费用用) )，它它是是服服务务水水平平的的递递减减函函数数。两两者者的的总和呈一条总和呈一条U U形曲线。形曲线。543543 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题 系统最优化的目标就是寻求上述合成费用曲线的最小点。在这种意义下，排队系统的最优化问题通常分为两类：一类称之系统的静态最优设计，目的在于使设备达到最大效益，或者说，在保证一定服

158、务质量指标的前题下，要求机构最为经济；另一类叫作系统动态最优运营，是指一个给定排队系统，如何运营可使某个目标函数得到最优。归纳起来，排队系统常见的优化问题在于：544544 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题 (1)确定最优服务率*； (2)确定最佳服务台数量c*； (3)选择最为合适的服务规则； (4)或是确定上述几个量的最优组合。 研究排队系统的根本目的在于以最少的设备得到最大的效益，或者说，在一定的服务质量的指标下要求机构最为经济。排队系统的最优化问题分为两大类：545545 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题 系统

159、的静态最优设计问题和系统的动态最优控制问题。由于系统动态最优控制问题涉及更多的数学知识，因此，本章只讨论系统静态的最优设计问题。这类问题一般可以借助于前面所得到的一些表达式来解决。 本节仅就，c 这两个决策变量的分别单独优化，介绍两个较简单的模型，以便读者了解排队系统优化设计的基本思想。546546 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题 一、一、M MM M1 1 系统的最优平均服务率系统的最优平均服务率 * * 设设C C1 1当当 =1=1时服务系统单位时间的平均费时服务系统单位时间的平均费C CW W平均每个顾客在系统逗留单位时间的损失；平均每个顾客在系

160、统逗留单位时间的损失；y y整个系统单位时间的平均总费用。整个系统单位时间的平均总费用。其中其中C C1 1，C C2 2 均为可知均为可知( (下同下同) )。则目标函数为。则目标函数为 (6-52)(6-52)547547 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题将将L L= = ( ( - - ) )，代入上式，得代入上式，得易见易见y y是关于决策变量是关于决策变量 的一元非线性函数的一元非线性函数由一阶条件由一阶条件解得驻点解得驻点 (6-53)(6-53)548548 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题 根号前取正号

161、是为了保证 ，这样，系统才能达到稳态。又由二阶条件 (因 ）可知(6-53)给出的*为(,)上的全局唯一最小点。将*代入 (6-52)中，可得最小总平均费用（6-54）549549 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题 另外，若设cw为平均每个顾客在队列中等待单位时间的损失，则需用式(6-26(6-26) )给出的 取代式(6-52)(6-52)中的，这时类似可得一阶条件： 这是一个关于的四次方程，尽管它有求根公式，但由于形式太复杂，实际并不应用。一般采用数值法(如牛顿法)确定其根*。550550 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最

162、优化问题 二、二、二、二、M M M MM M M Ms s s s 系统的最优服务台数系统的最优服务台数系统的最优服务台数系统的最优服务台数s s s s* * * *设目标函数为设目标函数为 (6-55)(6-55)其中：其中：s s并联服务台的个数并联服务台的个数( (待定待定) )；f f( (s s)整整个个系系统统单单位位时时间间的的平平均均总总费费用用，它它是是 关于服务台数关于服务台数s s的函数；的函数；c c2 2单位时间内平均每个服务台的费用；单位时间内平均每个服务台的费用；551551 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题c cw w平

163、均每个顾客在系统中逗留平均每个顾客在系统中逗留( (或等待或等待) )单位单位 时间的损失；时间的损失；L L( (s s)平均队长平均队长( (或平均等待队长或平均等待队长) )，它是关于，它是关于 服务台数服务台数s s的函数；的函数； 我我们们要要确确定定最最优优服服务务台台数数s s* *11，2 2，使使 由由于于s s取取值值离离散散，不不能能采采用用微微分分法法或或非非线线性性规划的方法，因此我们采用差分法。显然有规划的方法，因此我们采用差分法。显然有 （6-566-56）552552 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题把式（把式（6-556-

164、55）代人式）代人式(6-56) (6-56) 中，得中，得由此可得由此可得令令 (6-57)(6-57) 依依次次计计算算s s=1=1，2 2，时时的的L L( (s s) )值值及及每每一一差差值值L L( (s s)-)-L L( (s s+1) +1) ，根根据据 落落在在哪哪两两个个差差值值之之间间就可确定就可确定s s* *。553553 例6.4:兴建一座港口码头，只有一个装卸船只的泊位。要求设计装卸能力。装卸能力单位为（只/日）船数。已知：单位装卸能力的平均生产费用a=2千元，船只逗留每日损失b=1.5千元。船只到达服从泊松分布，平均速率=3只/日。船只装卸时间服从负指数分布

165、。目标是每日总支出最少。应应 用用 举举 例例554554 解： =3 待定 模型 M/M/1/队长 Ls =/(-)总费用 C=a+bLs=a+b/(-) 求极值（最小值） 应应 用用 举举 例例 求导 dc/du=a+(-b)/(-)2 = 0得: -=+ - (b/a)1/2（根据题意舍负）所以 =+(b/a)1/2=3+(2.25)1/2=4.5(只/日)555555 例6.4: 建造一口码头，要求设计装卸船只的泊位数。已知:预计到达=3只/天，泊松流；装卸=2只/天，负指数分布。装卸费每泊位每天a=2千元，停留损失费b=1.5千元/日。目标是总费用最少。应应 用用 举举 例例 解:模

166、型 M/M/c/ c待定总费用：F=ac+bLs（c）离散，无法用求导来解。556556应应 用用 举举 例例考虑: M/M/c/ 要求: =/(c) (/)=1.5讨论 c=2,3,4 c c- -1 1 P0=cn/nn+cc/c!c/(1- )-1 n n=0=0 Lq= ccc+1/c!(1-)2 P0L=Lq+/ 557557应应 用用 举举 例例 结论：c=3 即设计三个装卸泊位可使每天的总费用最少为8.60526千元。 =1/2 =3/4 =3/8558558 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题 例例6.6:6.6:某市政府的上访接待室每天平均

167、接待来访48次，来访者为泊松流，每天上访所造成的损失为平均每次20元。该室每设置一名接待员的服务成本为平均每天8元，接待时间为指数分布，平均每天可接待25次。问应设置几名接待员能使平均总费用为最小? 解:由题意知，这是一个MMs系统，有559559 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题c28元人天，cw20元天次， 48次天，25次天， 则按式(6-57)得 0.4另有560560 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题把 代入式(6-15)，得又由式(6-17)、式(6-18) 得把 ， P0代入上式，整理可得561561 4

168、.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题而当S=1时，=1.921，不满足系统达到稳态的条件1，故这时L(1)=。依次计算当s2，3，时的值及其差值L(s)-L(s+1)上，如表6-3所示。由表6-3及所落位置，对应可知：S*4(人)562562据此按据此按(6-55)(6-55)式可得最小总平均费用：式可得最小总平均费用： ( (元天元天) )故该室应设置故该室应设置4 4名接待员可使每天总平均名接待员可使每天总平均费用达到最小，为费用达到最小，为73732626元。元。表表6-3 6-3 s s2 2，3 3，时的时的L L( (s s) )值及其差值值及其差值上上L L( (s s)-)-L L( (s s+1)+1)( (下页）下页） 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题563563 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题S1234524.4902.6452.0631.95221.8450.5820.111 564564