1、运 筹 学,1.绪论 2.线性规划建模及单纯形法 3.线性规划问题的对偶与灵敏度分析 4.运输问题 5.动态规划 6.排队论 7.决策分析 8.图与网络分析,第一章 绪 论,运筹学概况简述,运筹学(Operations Research) 直译为“运作研究”。 运筹学是运用科学的方法(如分析、试验、量化等)来决定如何最佳地运营和设计各种系统的一门学科。,运筹学概况简述,运筹学能够对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。 通常以最优、最佳等作为决策目标，避开最劣的方案。,运筹学在工商管理中的应用,生产计划：生产作业的计划、日程表的编
2、排、合理下料、配料问题、物料管理等。 库存管理：多种物资库存量的管理，库存方式、库存量等。 运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等。,运筹学在工商管理中的应用,人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等。 市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等。,运筹学在工商管理中的应用,财务和会计：包括预测、贷款、成本分析、定价、证券管理、现金管理等。 其他： 设备维修、更新，项目选择、评价，工程优化设计与管理等。,运筹学的产生和发展,运筹学思想的出现可以追溯到很早“田忌齐王赛马”（对策论）、孙子兵法等都
3、体现了优化的思想。 “Operational Research”这一名词最早出现在第二次世界大战期间 美、英等国家的作战研究小组为了解决作战中所遇到的许多错综复杂的战略、战术问题而提出的。,运筹学的产生和发展,战后这些研究成果被应用到生产、经济领域，并得到迅速发展有关理论和方法的研究、实践不断深入。 1947年美国数学家丹捷格(G.B.Dantzig）提出了求解线性规划的有效方法单纯形法。,运筹学的产生和发展,数学对运筹学的作用是有关理论和方法的研究基础，是建立运筹学模型的工具。 计算机的发展，促进运筹学的进一步发展高速、可靠的计算是运筹学解决问题的基本保障。,运筹学的分支,线性规划非线性规划
4、整数规划动态规划,多目标规划随机规划模糊规划等,运筹学的分支,图与网络理论存储论排队论决策论,对策论排序与统筹方法可靠性理论等,运筹学方法使用情况(美1983),运筹学方法在中国使用情况 (随机抽样),运筹学的推广应用前景,据美劳工局1992年统计预测:社会对运筹学应用分析人员的需求从1990年到2005年，其增长百分比预测为73%,增长速度排到各项职业的前三位。,运筹学的推广应用前景,结论:-运筹学在国内或国外的推广应用前景是非常广阔的。-工商企业对运筹学应用的需求是很大的。-在工商企业推广运筹学方面有大量的工作要做。,运筹学解决问题的过程,1）提出问题：认清问题。 2）寻求可行方案：建模、
5、求解。 3）确定评估目标及方案的标准或方法、途径。 4）评估各个方案：解的检验、灵敏性分析等。,运筹学解决问题的过程,5）选择最优方案：决策。 6）方案实施：回到实践中。 7）后评估：考察问题是否得到完满解决。 1）2）3）形成问题；4）5）分析问题：定性分析与定量分析相结合，构成决策。,如何学习运筹学课程,学习运筹学要把重点放在分析、理解有关的概念、思路上。在自学过程中，应该多向自己提问，例如一个方法的实质是什么，为什么这样进行，怎么进行等。 自学时要掌握三个重要环节：,如何学习运筹学课程,1.认真阅读教材和参考资料，以指定教材为主，同时参考其他有关书籍。一般每一本运筹学教材都有自己的特点，
6、但是基本原理、概念都是一致的。注意主从，参考资料会帮助你开阔思路，使学习深入。但是，把时间过多放在参考资料上，会导致思路分散，不利于学好。,2.要在理解了基本概念和理论的基础上研究例题，注意例题是为了帮助理解概念、理论的。作业练习的主要作用也是这样，它同时还有让你自己检查自己学习的作用。因此，做题要有信心，要独立完成，不要怕出错。因为，整个课程是一个整体，各节内容有内在联系，只要学到一定程度，知识融会贯通起来，你自己就能够对所做题目的正确性作出判断。,如何学习运筹学课程,3、要学会做学习小结。每一节或一章学完后，必须学会用精炼的语言来概述该书所讲内容。这样，你才能够从较高的角度来看问题，更深刻
7、地理解有关知识和内容。这就称作“把书读薄”，若能够结合相关参考文献并深入理解，把相关知识从更深入、广泛的角度进行论述，则称为“把书读厚”。,如何学习运筹学课程,24,第二章 线性规划建模及单纯形法,本章内容重点,线性规划模型与解的主要概念线性规划的单纯形法，线性规划多解分析线性规划应用建模,25,1.线性规划的概念,例2.1:某工厂拥有A、B、C 三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：,26,问题：工厂应如何安排生产可获得最大的总利润？ 解：设变量 xi 为第 i 种（甲、乙）产品的生产件数（i1，2
8、）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。对设备A：两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3 x1 + 2 x2 65； 对设备B：两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2 x1 + x2 40；,1.线性规划的概念,27,对设备C ：两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x2 75 ；另外，产品数不可能为负，即 x1 ,x2 0。 同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润： z = 1500x1 + 2500x2 综合上述讨论，在加工时
9、间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型：,1.线性规划的概念,28,目标函数 Max z =1500x1+2500x2约束条件 s.t. 3x1 + 2x2 65 2x1 + x2 40 3x2 75 x1 ,x2 0,1.线性规划的概念,29,这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subject to”的缩写，表示“满足于”。因此，上述模型的含义是：在给定条件限制下，求使目标函数 z 达到最大的x1 ,x2 的取值。,1.线性规划的概念,30,一
10、般形式 目标函数：Max(Min)z = c1x1 + c2x2 + + cnxn,约束条件： a11x1+a12x2+a1nxn( =, )b1a21x1+a22x2+a2nxn( =, )b2 . . . am1x1+am2x2 +amnxn( =, )bm x1 ，x2 ， ，xn 0,1.线性规划的概念,31,标准形式目标函数：Max z = c1x1 + c2x2 + + cnxn,约束条件：A11x1 + a12x2 + + a1nxn = b1a21x1 + a22x2 + + a2nxn = b2 . . .am1x1 + am2x2 + + amnxn = bm x1 ，x2
11、 ， ，xn 0,1.线性规划的概念,32,可以看出，线性规划的标准形式有如下四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。 对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:,1.线性规划的概念,33,1.极小化目标函数的问题： 设目标函数为 Min f = c1x1 + c2x2 + + cnxn 则可以令z -f ，该极小化问 题与下面的极大化问题有相同的最优 解，即 Max z = -c1x1 - c2x2 - - cnxn 但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即 Min f - Max z,1.
12、线性规划的概念,34,2、约束条件不是等式的问题： 设约束条件为 ai1 x1+ai2 x2+ +ain xn bi 可以引进一个新的变量s ，使它等于约束右边与左边之差 s =bi(ai1 x1 + ai2 x2 + + ain xn ) 显然，s 也具有非负约束，即s0， 这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn+s = bi,1.线性规划的概念,35,当约束条件为 ai1 x1+ai2 x2+ +ain xn bi 时，类似地令 s =(ai1 x1+ai2 x2+ +ain xn)- bi 显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+
13、ai2 x2+ +ain xn-s = bi,1.线性规划的概念,36,为了使约束由不等式成为等式而引进的变量 s 称为“松弛变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。,1.线性规划的概念,37,例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.线性规划的概念,解：首先,将目标函数转换成极大化：令 z
14、= -f = -3.6x1+5.2x2-1.8x3,38,其次考虑约束，有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 0,1.线性规划的概念,39,3. 变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令 xj = xj- xj”其中 xj0，xj”0即用两个非负
15、变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj”的大小。,1.线性规划的概念,40,4.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bim，秩(A) = m，b Rm 。在约束等式中，令n维空间的解向量： x = (x1，x2，xn)T,2.线性规划解的概念,79,中n-m个变量为零，如果剩下的m个变量在线性方程组中有唯一解，则这n个变量的值组成的向量x就对应于n维空间Rn中若干个超平面的一个交点。当这n个变量的值都是非负时，这个交点就是线性规划可行域的一个极点。 根据以上分析，我们建立以下概念： （1）线性规划的基：对于线
16、性规划的约束条件 Ax=b， x0,2.线性规划解的概念,80,设B是A矩阵中的一个非奇异（可逆）的mm子矩阵，则称B为线性规划的一个基。用前文的记号，A=( p1 ，p2 ，pn ) ，其中 pj=( a1j ，a2j ，amj )T Rm ，任取A中的m个线性无关列向量 pj Rm 构成矩阵 B=( pj1 ，pj2 ，pjm )。那么B为线性规划的一个基。 我们称对应于基B的变量xj1 ，xj2，xjm为基变量；而其他变量称为非基变量。,2.线性规划解的概念,81,可以用矩阵来描述这些概念。 设B是线性规划的一个基，则A可以表示为 A= B , N x也可相应地分成 xB x= xN 其
17、中xB为m维列向量，它的各分量称为基变量，与基B的列向量对应；xN为n-m列向量，它的各分量称为非基变量，与非基矩阵N的列向量对应。这时约束等式Ax=b可表示为,2.线性规划解的概念,82,xB B,N = b xN 或 BxB + NxN = b 如果对非基变量xN取确定的值，则xB有唯一的值与之对应 xB = B-1b - B-1NxN 特别，当取xN = 0，这时有xB=B-1b。关于这类特别的解，有以下概念。,2.线性规划解的概念,83,（2）线性规划问题的基本解、基本可行解和可行基： 对于线性规划问题，设矩阵B = ( pj1，pj2，pjm ) 为一个基，令所有非基变量为零，可以得
18、到m个关于基变量xj1 ，xj2 ，xjm的线性方程，解这个线性方程组得到基变量的值。我们称这个解为一个基本解；若得到的基变量的值均非负，则称为基本可行解，同时称这个基B为可行基。,2.线性规划解的概念,84,矩阵描述为，对于线性规划的解 xB B-1b x= = xN 0 称为线性规划与基B对应的基本解。若其中B-1b0，则称以上的基本解为一基本可行解，相应的基B称为可行基。,2.线性规划解的概念,85,我们可以证明以下结论：线性规划的基本可行解就是可行域的极点。 这个结论被称为线性规划的基本定理，它的重要性在于把可行域的极点这一几何概念与基本可行解这一代数概念联系起来，因而可以通过求基本可
19、行解的线性代数的方法来得到可行域的一切极点，从而有可能进一步获得最优极点。,2.线性规划解的概念,86,例2.9: 考虑例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 0 注意，线性规划的基本解、基本可行 解（极点）和可行基只与线性规划问 题标准形式的约束条件有关。,2.线性规划解的概念,87,3 2 1 0 0A = P1 ,P2 ,P3 ,P4 ,P5 = 2 1 0 1 0 0 3 0 0 1
20、 A矩阵包含以下10个33的子矩阵： B1=p1 ，p2 ，p3 B2=p1 ，p2 ，p4 B3=p1 ，p2 ，p5 B4=p1 ，p3 ，p4 B5=p1 ，p3 ，p5 B6=p1 ，p4 ，p5 B7=p2 ，p3 ，p4 B8=p2 ，p3 ，p5 B9=p2 ，p4 ，p5 B10=p3 ，p4 ，p5,2.线性规划解的概念,88,其中B4= 0，因而B4不是该线性规划问题的基。其余均为非奇异方阵，因此该问题共有9个基。 对于基B3=p1 ，p2 ，p5，令非基变量x3 = 0， x4 = 0，在等式约束中令x3 = 0，x4 = 0，解线性方程组： 3 x1 + 2 x2 +
21、0 x5 = 65 2 x1 + x2 + 0 x5 = 40 0 x1 + 3 x2 + x5 = 75 得到x1 =15，x2 = 10，x5 = 45，对应的基本可行解： x=(x1 ，x2 ，x3 ，x4 ，x5)T=(15，10，0，0，45)T。于是对应的基B3是一个可行基。,2.线性规划解的概念,89,类似可得到 x(2) = (5,25,0,5,0)T （对应B2） x(7) = (20,0,5,0,75)T （对应B5） x(8) = (0,25,15,15,0)T （对应B7） x(9) = (0,0,65,40,75)T （对应B10） 是基本可行解； 而x(3)= (0
22、,32.5,0,7.5,-22.5)T（对应B9） x(4)= (65/3,0,0,-10/3,75)T （对应B6） x(5)= (7.5,25,-7.5,0,0)T （对应B1） x(6) = (0,40,-15,0,-45)T （对应B8） 是基本解。,2.线性规划解的概念,90,因此，对应基本可行解（极点） 的B2 B3 B5 B7 B10都是可行基。 这里指出了一种求解线性规划问题的可能途径，就是先确定线性规划问题的基，如果是可行基，则计算相应的基本可行解以及相应解的目标函数值。由于基的个数是有限的（最多个），因此必定可以从有限个基本可行解中找到最优解。,2.线性规划解的概念,91,
23、利用求解线性规划问题基本可行解（极点）的方法来求解较大规模的问题是不可行的。单纯形法的基本思路是有选择地取基本可行解，即是从可行域的一个极点出发，沿着可行域的边界移到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。,3.单 纯 形 法,92,由上节的讨论可知，对于线性规划的一个基，当非基变量确定以后，基变量和目标函数的值也随之确定。因此，一个基本可行解向另一个基本可行解的移动，以及移动时基变量和目标函数值的变化，可以分别由基变量和目标函数用非基变量的表达式来表示。同时，当可行解从可行域的一个极点沿着可行域的边界移动到一个相邻的极点的过程中，所有非基变量中只有一个变量的值从0开始增加
24、，而其他非基变量的值都保持0不变。,3.单 纯 形 法,93,3.单 纯 形 法,单纯形法的基本过程,94,考虑标准形式的线性规划问题：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 c1 b1 a11 a12.a1n x2 c2 b2 a21 a22.a2nx= . C= . B= . A= . . . . . . . . . xn
25、 cn bn am1 am2.amn,3.单 纯 形 法,95,这里，矩阵A表示为：A = ( p1 ，p2 ，pn ) ，其中 pj = ( a1j ，a2j ，amj )T Rm。若找到一个可行基，无防设B = ( p1 ，p2 ，pm ) ，则m个基变量为 x1 , x2 , , xm，n-m个非基变量为 xm+1 ，xm+2 ，xn 。通过运算，所有的基变量都可以用非基变量来表示：,3.单 纯 形 法,96,3.单 纯 形 法,x1=b1-（a1m+1xm+1+a1m+2xm+2+a1nxn） x2=b2-（a2m+1xm+1+a2m+2xm+2+a2nxn）( 2-11 ) . .
26、. 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相应的目标函数典式。,97,单纯形法的基本步骤可描述如下： （1）寻找一个初始的可行基和相应基本可行解（极点），确定基变量、非基变量以及基变量、非基变量（全部等于0）和目标函数的值，并将目标函数和基变量分别用非基变量表示；,3.单 纯 形 法,98,（2）在用非基变量表示的目标函数表达式（2-12）中，我们称非基变量xj的
27、系数（或其负值）为检验数记为 j 。若 j 0，那么相应的非基变量xj，它的值从当前值0开始增加时，目标函数值随之增加。这个选定的非基变量xj称为“进基变量”，转（3）。如果任何一个非基变量的值增加都不能使目标函数值增加，即所有 j 非正，则当前的基本可行解就是最优解，计算结束；,3.单 纯 形 法,99,（3）在用非基变量表示的基变量的表达式（2-11）中，观察进基变量增加时各基变量变化情况，确定基变量的值在进基变量增加过程中首先减少到0的变量xr ，满足，=minbi /aij aij 0 = br /arj这个基变量xr称为“出基变量”。当进基变量的值增加到 时，出基变量xr的值降为0时，可行解就移动到了相邻的基本可行解（极点），转（4）。,3.单 纯 形 法,100,如果进基变量的值增加时，所有基变量的值都不减少，即所有aij 非正，则表示可行域是不封闭的，且目标函数值随进基变量的增加可以无限增加，此时，不存在有限最优解，计算结束； （4）将进基变量作为新的基变量，出基变量作为新的非基变量，确定新的基、新的基本可行解和新的目标函数值。在新的基变量、非基变量的基础上重复（1）。,
