运筹学(一)课件

1、运筹学(一),运 筹 学 （O.R.),运筹学(一),教材 胡运权主编，运筹学教程（第四版），清华大学出版社，2012。,课程说明,运筹学(一),课程说明,参考书 （1）胡运权主编，运筹学习题集（第四版），清华大学出版社，2010 （2）钱颂迪等，运筹学（第三版），清华大学出版社，2005,运筹学(一),课程说明,先修课程 微积分、线性代数、概率论 学习方式 课堂听课、课下习题、软件学习,运筹学(一),主要授课内容：,绪论 线性规划及单纯形法 线性规划的对偶理论与灵敏度分析 运输问题 目标规划 整数规划 动态规划 图与网络分析,运筹学(一),绪论,一、运筹学的起源与发展 二、运筹学研究的基本特

2、点与基本方法 三、运筹学研究的主要分支 四、运筹学在企业管理中的应用,运筹学(一),一、运筹学的起源与发展,1.什么是运筹学 英文：Operational Research(英国) Operations Research(美国) （直译为“作业研究”、“运用研究”） 中文：运筹学（来源于“夫运筹帷幄之中，决胜于千里之外”）,运筹学(一),运筹学是在实行管理的领域，运用数学方法，对需要进行管理的问题统筹规划，作出决策的一门应用科学 (P.M.Morse与G.E.Kimball )； 运筹学是用数学方法研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效运

3、行的技术科学，它可以用来预测发展趋势，制定行动规划或优化可行方案（中国大百科全书）； 运筹学是应用分析、试验、量化的方法，对经济管理系统中人、财、物等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理（中国企业管理百科全书） 。,运筹学(一),2.运筹学的发展历史 （1）二战以前：萌芽 齐王-田忌赛马、丁渭修皇宫等。 （2）二战期间：产生 1938年，英国某雷达站负责人罗伊提出整个防空作战系统运行的研究，并用到了operational research 来描述此研究。 1940年，英国军事部门成立了第一个由一些数学家、物理学家和工程专家等组成的OR小组，负责研究一些武器有效使用

4、的问题。 1942年，美国也成立了由17人组成的OR小组，研究反潜艇策略等问题。 （3）二战后：推广与发展 战时从事运筹学研究的许多专家转到了经济部门、民用企业、大学或研究所，继续从事决策的数量方法的研究，运筹学作为一门学科逐步形成并得以迅速发展。运筹学发展到今天，已成为分支学科众多的一个繁荣昌盛的大家族。随着电子计算机的发展和使用，运筹学处理复杂性问题的能力大大加强，成为解决实际问题的有力工具，广泛地应用于企业管理、交通运输、公共服务等领域。,运筹学(一),二、运筹学研究的基本特征与基本方法,1.运筹学研究的基本特征 （1）系统性特征 运筹学用系统的观点来分析一个组织（或系统），它着眼于整个

5、系统而不是一个局部，通过协调各组成部分之间的关系和利害冲突，使整个系统达到最优状态。 （2）综合性特征 运筹学是一门交叉学科，具有综合性，它的起源就是由不同学术背景的专家共同解决实际问题。它充分利用了数学、计算机科学、统计学及其它科学的成就，这决定了运筹学内容的跨学科性和综合性。 （3）模型方法的应用 运筹学研究建立在科学的研究方法之上，它研究的第一步就是根据实际问题和管理要求建立必要的数学或模拟模型。然后对模型进行求解、分析和检验。因此学习运筹学要掌握的重要技巧就是对运筹学模型的表达、运算和分析的能力。,运筹学(一),2.运筹学研究的基本方法 （1）分析和表述问题； （2）建立模型； （3）

6、求解模型； （4）测试模型； （5）对模型进行必要的修正； （6）建立对解的有效控制； （7）方案的实施。,运筹学(一),三、运筹学研究的主要分支,线性规划（linear programming) 非线性规划 动态规划 图论与网络分析 存贮论 排队论 对策论 决策论,运筹学(一),四、运筹学在企业管理中的应用,生产计划。使用运筹学方法从总体上确定适应需求的生产、储存和劳动力安排等计划， 以谋求最大的利润或最小的成本。 库存管理。存储论应用于多种物资库存量的管理，确定某些设备的合理的能力或容量以及适当的库存方式和库存量 运输问题。用运筹学中运输问题的方法，可以确定最小成本的运输线路、物资的调拨、

7、运输工具的调度以及建厂地址的选择。 人事管理。可以用运筹学方法对人员的需求和获得情况进行预测；确定合适需要的人员编制；用指派问题对人员合理分配；用层次分析法等方法来确定一个人才评价体系等。 市场营销。可把运筹学方法用于广告预算和媒体的选择、竞争性的定价、新产品的开发、销售计划的制定等方面。 财务和会计。可以用运筹学方法进行预测、贷款、成本分析、定价、证券管理、现金管理。,运筹学(一),第一章,线性规划与单纯形法,运筹学(一),主要内容：,第一节 线性规划问题及其数学模型 第二节 图解法 第三节 单纯形法原理 第四节 单纯形法计算步骤 第五节 单纯形法的进一步讨论 第六节 线性规划在经济管理中的

8、应用例子,运筹学(一),第一节,线性规划问题及其数学模型,运筹学(一),一、线性规划问题举例,例1（生产计划问题） ：美佳公司计划制造，两种家电产品。已知各制造一件时分别占用的设备A,B的台时、调试时间、调试工序及每天可用于这两种家电的能力、各售出一件的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润为最大。,运筹学(一),表1-1,运筹学(一),设x1, x2 分别代表，两种家电的生产量，此问题的数学模型为： 目标函数 约束条件,运筹学(一),例2（仓库租借问题） ：某公司在下一年度的14月的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于表1-2.仓库租借费用随

9、合同期而定，期限越长，折扣越大，具体数字见表1-3.租借仓库的合同每月月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签订一份合同，也可签若干份租用面积和租用期限不同的合同，试确定该公司签订租借合同的最优策略，目的使所付租借费最小。,运筹学(一),表1-2,表1-3,运筹学(一),设xij公司在第i（i=1,2,3,4)个月初签订租借期为j（j=1,2,3,4)个月的合同的仓库面积，此问题的数学模型为：,运筹学(一),二、线性规划问题的数学模型,线性规划问题数学模型的三个组成要素,1.决策变量:是决策者为实现规划目标采取的方案、措施，是

10、问题中要确定的未知量。,2.目标函数:指问题要达到的目的要求，表示为决策变量的函数。,3.约束条件:指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。,运筹学(一),n:变量个数 m：约束个数 cj:价值系数 bi:资源拥有量 aij :工艺系数,线性规划问题数学模型的一般表示形式：,运筹学(一),该模型的简化表示：,运筹学(一),该模型的向量表示：,运筹学(一),该模型的矩阵表示：,运筹学(一),三、线性规划问题的标准形式,为了使线性规划问题的解法标准，就要把一般形式化为标准形式。标准形式如下：,标准形式特点：,4. 决策变量取值非负。,1. 目标函数为求极大值；,2

11、. 约束条件全为等式；,3. 约束条件右端常数项bi全为非负值；,运筹学(一),把非标准形式转化为标准形式的方法： （1）目标函数为min型，即 等价于求 ，令 ，即化为： ； （2）约束条件的右端项bi 为负值，则该行左右两端 同时乘以（-1），同时不等号也要反向； （3）第i 个约束为 型，在不等式左边增加一个非负的变量，称为松弛变量；同时该变量在目标函数中的系数为0；,运筹学(一),（4）第i 个约束为 型，在不等式左边减去一个非负的变量，称为剩余变量；同时令该变量在目标函数中的系数为0； （5）若 ，令 （6）若 无约束，令 ，其中，,运筹学(一),例3：将下述线性规划模型化为标准形式

12、：,运筹学(一),第二节,图解法,运筹学(一),一、图解法的步骤,1.画出直角平面坐标系； 2.图示约束条件，找出可行域； 3.图示目标函数； 4.最优解的确定。,运筹学(一),最优解在Q2处获得，此时x1=3.5, x2=1.5,目标函数值为8.5,例4：用图解法求解以下线性规划问题,运筹学(一),二、由图解法得到的启示,（2）无穷多最优解（若上例中目标函数变为max z=3x1+x2)；,( 3 )无界解（若去掉例子中第2、3个约束）；,1.求解线性规划问题时，解的情况有四种类型。,（1）惟一最优解（如上例）；,( 4 )无可行解。,目标函数为max z=3x1+x2，约束条件为,运筹学(

13、一),2.若线性规划问题的可行域存在，则可行域一定是个凸集。 3.线性规划问题的最优解若存在，则最优解或最优解之一一定是可行域的凸集的某个顶点。 4 .解题思路是，先找凸集的任一顶点，计算其目标函数值。比较其相邻顶点函数值，若更优，则逐点转移，直到找到最优解。,运筹学(一),第三节,单纯形法原理,运筹学(一),可行解：满足约束条件的解称为可行解，可行解的集合称为可行域。,最优解：使目标函数达到最大值的可行解。,基：约束方程组的一个满秩子矩阵称为规划问题的一个基，基中的每一个列向量称为基向量，与基向量对应的变量称为基变量，其他变量称为非基变量。,基解：在约束方程组中，令所有非基变量为0，可以解出

14、基变量的唯一解，这组解与非基变量的0共同构成基解。,基可行解：满足变量非负的基解称为基可行解,可行基：对应于基可行解的基称为可行基,一、线性规划问题的解,运筹学(一),化为标准形式,运筹学(一),O,是,5,24,15,0,0,x3,x4,x5,Q4,是,2,18,0,3,0,x2,x4,x5,P3,否,-7,0,-45,12,0,x2,x3,x5,P4,否,0,20,-10,5,0,x2,x3,x4,Q1,是,1,0,15,0,4,x1,x3,x5,P1,否,0,-6,15,0,5,x1,x3,x4,P2,否,-1,0,0,3,3,x1,x2,x5,Q3,是,0,6,0,3,2,x1,x2,

15、x4,Q2,是,0,0,7.5,1.5,3.5,x1,x2,x3,对应点,是否为基可行解,x5,x4,x3,x2,x1,基变量,序号,运筹学(一),二、凸集和顶点,凸集：如果集合 C 中任意两个点X1 ,X2,其连线上的所有点也都是集合C 中的点。,上图中（1）（2）是凸集，（3）（4）不是凸集,顶点：如果对于凸集 C 中的点 X ，不存在C 中的任意其它两个不同的点X1 ,X2，使得 X 在它们的连线上，这时称 X 为凸集的顶点。,运筹学(一),三、线性规划问题基本定理,定理一 若线性规划问题存在可行解，则问题的可行 域是凸集。,定理二 线性规划问题的基本可行解 X 对应线性规划 问题可行域

16、（凸集）的顶点。,定理三 若线性规划问题有最优解，一定存在一个基 可行解是最优解。,从上述三个定理可以看出，要求线性规划问题的最优解，只要比较可行域（凸集）各个顶点对应的目标函数值即可，最大的就是我们所要求的最优解。,运筹学(一),定理一证明：,X1和X2连线上的点也在可行域内，因此可行域是凸集。,运筹学(一),定理二证明：,X是可行域的顶点,X是基可行解,即证明：,相当于证明：,X不是可行域的顶点,X不是基可行解,1、证明：,X不是基可行解,X不是可行域的顶点,运筹学(一),由于X不是基可行解，因此P1,P2,Pr线性相关。,运筹学(一),所以X不是可行域的顶点。,令：,运筹学(一),2、证

17、明：,X不是基可行解,X不是可行域的顶点,运筹学(一),因此X不是基可行解,运筹学(一),四、确定初始基可行解,线性规划问题的最优解一定会在基可行解中取得，我们先找到一个初始基可行解。然后设法转换到另一个基可行解，直到找到最优解为止。,设给定线性规划问题：,运筹学(一),其标准形为：,因此约束方程组的系数矩阵为：,由于该矩阵含有一个单位子矩阵，因此，一这个单位阵做基，就可以求出一个基可行解：,运筹学(一),五、从一个基可行解转换为相邻基可行解,相邻基可行解： 如果两个基可行解，它们有且只有一个基变量不同，则称它们为相邻基可行解。,运筹学(一),六、最优性检验和解的判别,当所有 时，现有顶点对应

18、的基可行解即为最优解。 当所有 时，又对某个非基变量 有 且可以找到 ，则该线性规划问题有无穷多最优解。 3. 如果存在某个 ，又 向量的所有分量 ，对任意 ，恒有 ，则存在无界解。,运筹学(一),第四节,单纯形法计算步骤,运筹学(一),第一步：求初始可行解，列初始单纯形表,运筹学(一),第二步：进行最优性检验,如果表中，所有检验数 ，则表中的基可行解就是问题的最优解，计算到此为止，否则转入下一步。,运筹学(一),第三步：转换到新的基可行解，构造新单纯形表,1.确定换入变量,2.确定换出变量,运筹学(一),3.用换入变量替换换出变量，做新单纯形表,（1）,（2）,（3）检验数 的求法与初始单纯

19、形表中求法相同,运筹学(一),第四步：,重复第二、三步直到计算结束。,运筹学(一),例5：用单纯形法求解如下线性规划问题,运筹学(一),解：将原线性规划问题化为标准形式有,运筹学(一),第一步：取系数矩阵中单位阵部分为基，得初始基可行解。,列出初始单纯形表：,0,0,0,1,2,1,0,0,1,1,5,0,0,1,0,2,6,24,0,0,0,1,5,0,15,0,0,0,0,1,2,6,0,运筹学(一),运筹学(一),第三步：,1. 确定换入变量,2. 确定换出变量,运筹学(一),3. 作新单纯形表,第四步：由于还存在检验数 ，因此重复上述步骤。,运筹学(一),由于上表中所有检验数都小于等于

20、零，因此已经得到最优解，最优解为：,代入目标函数得最优值：,运筹学(一),第五节,单纯形法的进一步讨论,运筹学(一),一、人工变量法,例6：求如下线性规划问题,运筹学(一),解：化为标准型,运筹学(一),约束条件的系数矩阵为：,这个矩阵中不含有单位矩阵，因此很难找到初始基。,对于这种线性规划问题的系数矩阵不含有单位矩阵的情况，我们往往采用添加人工变量 的方法，来认为构造一个单位矩阵。这样的方法就是人工变量法。,运筹学(一),为了构造出单位矩阵，在系数矩阵中添加两列单位列向量，系数矩阵变为：,线性规划问题的约束条件就变为：,运筹学(一),因为 、 是人为添加的，因此其对应的变量 、 称为人工变量

21、。,目标函数中人工变量的系数：,添加人工变量前，在线性规划问题的标准形中，各约束条件已经是等式约束了，因此为了保证等式约束满足不变，在最优解中，人工变量的取值必须为0。 为此，令目标函数中人工变量的系数为任意大的一个负值，用“ ”来表示，这样，只要人工变量取值不为零，则目标函数就不能达到极大化。,目标函数变为：,添加 M 来处理人工变量的方法，称为大M 法,运筹学(一),求解过程：,运筹学(一),因此最优解为：,运筹学(一),二、两阶段法,用大 M 处理人工变量时，用计算机求解会出现错误，由此产生了两阶段法。,运筹学(一),第一阶段：先求解一个目标函数中只含有人工变量的线性规划问题。,即令目标

22、函数中其它变量的系数取零，人工变量的系数取某个正的常数（一般取1），在保持原问题约束条件不变的情况下求这个目标函数极小化时的解。,第二阶段：从第一阶段的最终单纯形表出发，去掉人工变量，按原问题的目标函数，继续寻找原问题的最优解。,若最优解对应的目标函数为0，则转入第二阶段；若最优解对应的目标函数不为0，即最优解的基变量中含非0的人工变量，则说明原问题无可行解。,运筹学(一),例7：用两阶段法求解例6,第一阶段：,运筹学(一),化成标准形式：,运筹学(一),-1,0,0,4,-2,0,0,1,3,0,9,-1,-1,0,-1,1,-2,1,-1,0,1,1,1,1,4,0,0,0,0,0,0,0

23、,1,0,0,0,1,-1,-1,0,0,1,3,0,4,0,6,3,0,4,0,6,6,-1,-1,0,-1,1,-2,1,0,1,1,2,0,3,3,0,1,-3,0,1,-4,0,-1,0,6,运筹学(一),0,0,0,0,0,1/2,0,2/3,0,1,1,0,0,0,-1/3,1,0,3,0,-1/2,1,0,0,0,0,0,0,0,0,0,0,1/2,0,-1/2,-1/2,1/3,1/6,-1,-1,-1,-1,该模型最优解为X=（1，3，0，0，0，0，0）T，其基变量不含人工变量，说明原问题的一个基可行解为X=（1，3，0，0，0）T，转入第二阶段。,运筹学(一),第二阶段：

24、,3/2,0,3,0,0,1/2,0,2/3,0,1,1,-3,0,0,1/3,1,1,3,0,-1/2,1,0,0,0,0,0,-3/4,0,0,0,-9/2,3/4,0,1,0,3/2,3/2,1,-1/4,0,0,1,-1/2,5/2,0,-1/2,1,0,0,0,0,0,2/3,该问题的最优解为X=（5/2，0，0，0，3/2）T，对应的目标函数值为z*=3/2。,运筹学(一),三、关于解的判断,当所有 时，基变量中不含非零的人工变量，且对于所有非基变量 的 ，则该线性规划问题有惟一最优解。,2. 当所有 时，基变量中不含非零的人工变量，又对某个非基变量 有 ，且可以找到 ，则该线性规

25、划问题有无穷多最优解。,3. 当存在某个 ，且其对应的 ，则 取值可以无限大，该线性规划问题有无界解。,运筹学(一),4. 当所有 时，如基变量中含非零的人工变量（两阶段法求解时第一阶段目标函数值不等于零），则该线性规划问题无可行解。,运筹学(一),例7：求解线性规划问题,运筹学(一),解：在图解法中，我们知道这个问题有无穷多解。,它的标准形为：,运筹学(一),列出初始单纯形表：,把 作为换入变量， 作为换出变量，作出新的单纯形表：,运筹学(一),运筹学(一),7/2,若把 作为换入变量， 作为换出变量，得到新的单纯形表：,0,-1/2,0,0,0,1,-1/4,0,1,0,3/2,1,-1/3,1/4,0,0,1,3,-5,5/4,1,0,0,15/2,0,0,0,0,1,3,从表中可以得到另一个最优解：,X1,X2连线上的所有点都是最优解，因此存在无穷多最优解。,运筹学(一),例8：求解线性规划问题,解：利用图解法，我们可以知道该问题具有无界解。,将其化为标准形：,运筹学(一),该问题单纯形法求解如下：,但P1=(-1,-2)T0,故该问题具有无界解。,运筹学(一),例9：求解线性规划问题,解：利用图解法，我们可以知道该问题无可行解。,将其化为标准形：,运筹学(一),该问题单纯形法求解如下：,当所