智库文档所有分类

运筹学.ppt

下载

黄国梁

575页 | 8.62MB | 5次下载 |

5.0

(1人评价)

我要评价：

投诉举报

用手机看文档

扫一扫,手机看文档

下载

开通VIP

运筹学 ( Operations Research ) 经济管理学核心课程梁伟河海大学商学院（常州） liangw@ 运筹帷幄之中决胜千里之外绪论 Introduction 第一章绪论（1）运筹学简述（2）运筹学的主要内容（3）本课程的教材及参考书（4）本课程的特点和要求（5）本课程授课方式与考核（6）运筹学在经济管理中的应用本章主要内容：绪论绪论运筹学简述运筹学（Operations Research,简写OR ）系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学(Management Science)。运筹学所研究的问题，可简单地归结为一句话： “依照给定条件和目标，从众多方案中选择最佳方案” 故有人称之为最优化技术。绪论运筹学的历史与发展 “运筹学思想的出现可以追溯到很早—“田忌赛马” 。齐王要与大臣田忌赛马，双方各出上、中、下马各一匹，对局三次，每次胜负1000金。田忌在好友、著名的军事谋略家孙膑的指导下，以以下安排：齐王上中下田忌下上中绪论丁谓的皇宫修复工程北宋年间，丁谓负责修复火毁的开封皇宫。他的施工方案是：先将皇宫前的一条大街挖成一条大沟，将大沟与汴水相通。使用挖出的土就地制砖，令与汴水相连形成的河道承担繁重的运输任务；修复工程完成后，实施大沟排水，并将原废墟物回填，修复成原来的大街。丁谓将取材、运输及清废用“一沟三用”巧妙地解决了，体现了系统规划的思想。绪论国际上运筹学的思想可追溯到1914年，当时的兰彻斯特提出了军事运筹学的作战模型。1917年，丹麦工程师埃尔朗在研究自动电话系统中通话线路与用户呼叫的数量关系问题时，提出了埃尔朗公式，研究了随机服务系统中的系统排队与系统拥挤问题。存储论的最优批量公式是在20世纪20年代初提出的。运筹学简述 “运作研究(Operational Research)小组”:解决复杂的战略和战术问题。例如：如何合理运用雷达有效地对付德军德空袭对商船如何进行编队护航，使船队遭受德国潜艇攻击时损失最少；在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等。绪论在生产管理方面的应用，最早是1939年前苏联的康特洛为奇提出了生产组织与计划中的线性规划问题，并给出解乘数法的求解方法，出版了第一部关于线性规划的著作《生产组织与计划中的数学方法》。但当时并没有引起重视，直到1960年康特洛为奇再次出版了《最佳资源利用的经济计算》，才受到国内外的一致重视，为此康特洛为奇获得了诺贝尔经济学奖。线性规划提出后很快受到经济学家的重视，如：二次世界大战中从事运输模型研究的美国经济学家库普曼斯（），他很快看到了线性规划在经济中应用的意义，并呼吁年轻的经济学家要关注线性规划。其中阿罗、萨谬尔逊、西蒙、多夫曼和胡尔威茨等都获得了诺贝尔奖。绪论 20世纪50年代中期，钱学森、许国志等教授在国内全面介绍和推广运筹学知识，1956年，中国科学院成立第一个运筹学研究室，1957年运筹学运用到建筑和纺织业中，1958年提出了图上作业法，山东大学的管梅谷教授提出了“中国邮递员问题”，1970年，在华罗庚教授的直接指导下，在全国范围内推广统筹方法和优选法。 1978年11月，在成都召开了全国数学年会，对运筹学的理论与应用研究进行了一次检阅，1980年4月在山东济南正式成立了“中国数学会运筹学会”，1984年在上海召开了“中国数学会运筹学会第二届代表大会暨学术交流会”，并将学会改名为“中国运筹学会”。绪论成熟的学科分支向纵深发展新的研究领域产生与新的技术结合与其他学科的结合加强传统优化观念不断变化运筹学的发展趋势运筹学的主要内容数学规划（线性规划、整数规划、目标规划、动态规划等）图论存储论排队论对策论排序与统筹方法决策分析运筹学的主要内容 1. 线性规划（Linear Program）是一个成熟的分支，它有效的算法——单纯形法，主要解决生产计划问题，合理下料问题，最优投资问题。 2. 整数规划(Integrate Program)：在线性规划的基础上，变量加上整数约束。 3. 非线性规划(Nonlinear Program)：目标函数和约束条件是非线性函数，如证券投资组合优化:如何合理投资使风险最小。 4. 动态规划(Dynamic Program)：多阶段决策问题。是美国贝尔曼于1951年提出的。运筹学的主要内容 5、图与网络(Graph Theory and Network)：中国邮递员问题、哥尼斯堡城问题、最短路、最大流问题。 6、存储论（Inventory Theory)：主要解决生产中的库存问题，订货周期和订货量等问题。 7、排队论(Queue Theory)：主要研究排队系统中的系统排队和系统拥挤现象，从而评估系统的服务质量。 8、对策论(Game Theory)：主要研究具有斗争性质的优化问题。 9、决策分析(Decision Analysis) ：主要研究定量化决策。本课程的教材及参考书选用教材《运筹学教程》胡运权主编（第3版）清华出版社参考教材《运筹学基础及应用》胡运权主编哈工大出版社《管理运筹学》韩伯棠主编（第2版）高等教育出版社《运筹学》(修订版) 钱颂迪主编清华出版社本课程的特点和要求先修课：高等数学，基础概率、线性代数特点：系统整体优化；多学科的配合；模型方法的应用运筹学的研究的主要步骤：真实系统系统分析问题描述模型建立与修改模型求解与检验结果分析与实施数据准备本课程授课方式与考核学科总成绩平时成绩（40％）课堂考勤（50％）平时作业（50％）期末成绩（60％）讲授为主，结合习题作业运筹学在经济管理中的应用运筹学在经济管理中的应用涉及的方面：生产计划运输问题人事管理库存管理市场营销财务和会计物流配送另外，还应用于设备维修、更新和可靠性分析，项目的选择与评价，工程优化设计等。 “管理运筹学”软件介绍 “管理运筹学”版包括：线性规划、运输问题、整数规划（0-1整数规划、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、决策分析、预测问题和层次分析法，共15个子模块。第一章运筹帷幄之中决胜千里之外线性规划及单纯形法 Linear Programming Chapter1 线性规划 (Linear Programming) LP的数学模型图解法单纯形法单纯形法的进一步讨论－人工变量法 LP模型的应用本章主要内容：线性规划问题的数学模型 1. 规划问题生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。线性规划通常解决下列两类问题：（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大.）线性规划问题的数学模型例如图所示，如何截取x使铁皮所围成的容积最大？ x a 线性规划问题的数学模型例某厂生产两种产品，下表给出了单位产品所需资源及单位产品利润问：应如何安排生产计划，才能使总利润最大？解： 1.决策变量：设产品I、II的产量分别为 x1、x2 2.目标函数：设总利润为z，则有： max z = 2 x1 + x2 3.约束条件： 5x2 ≤ 15 6x1+ 2x2 ≤ 24 x1+ x2 ≤ 5 x1， x2≥0 线性规划问题的数学模型例已知资料如下表所示，问如何安排生产才能使利润最大？或如何考虑利润大，产品好销。 12 16 8 12 有效台时 3 4 0 2 2 Ⅱ 2 0 4 1 2 Ⅰ 利润（元） D C B A 设备产品解： 1.决策变量：设产品I、II的产量分别为 x1、x2 2.目标函数：设总利润为z，则有： max z = 2 x1 + x2 3.约束条件： x1 ≥ 0 , x2 ≥ 0 2x1 + 2x2 ≤ 12 x1 + 2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12 线性规划问题的数学模型例某厂生产三种药物，这些药物可以从四种不同的原料中提取。下表给出了单位原料可提取的药物量解：要求：生产A种药物至少160单位；B种药物恰好200单位，C种药物不超过180单位，且使原料总成本最小。 1.决策变量：设四种原料的使用量分别为：x1、x2 、x3 、x4 2.目标函数：设总成本为z min z = 5 x1 + 6 x2 + 7 x3 + 8 x4 3.约束条件： x1 + 2x2 + x3 + x4 ≥160 2x1 +4 x3 +2 x4 ＝200 3x1 ＋x2 +x3 +2 x4 ≤180 x1、x2 、x3 、x4 ≥0 例某航运局现有船只种类、数量以及计划期内各条航线的货运量、货运成本如下表所示： 20 27 4 — 1 4 40 72 4 2 2 3 2 20 36 4 — 1 2 25 36 — 2 1 1 1 B型驳船 A型驳船拖轮货运量（千吨）货运成本（千元／队）编队形式船队类型航线号 52 B型驳船 34 A型驳船 30 拖轮船只数船只种类 400 2 200 1 合同货运量航线号问：应如何编队，才能既完成合同任务，又使总货运成本为最小？线性规划问题的数学模型解：设：xj为第j号类型船队的队数（j = 1，2，3，4）， z 为总货运成本则： min z = 36x1 + 36x2 + 72x3 + 27x4 x1 + x2 + 2x3 + x4 ≤ 30 2x1 + 2x3 ≤ 34 4x2 + 4x3 + 4x4 ≤ 52 25x1+20x2 ＝200 40x3+20x4 ＝400 xj ≥ 0 （ j = 1,2,3,4）线性规划问题的数学模型线性规划问题的数学模型 2. 线性规划的数学模型由三个要素构成决策变量 Decision variables 目标函数 Objective function 约束条件 Constraints 其特征是：（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；（2）问题的约束条件是一组多个决策变量的线性不等式或等式。怎样辨别一个模型是线性规划模型？线性规划问题的数学模型 3. 建模条件 (1) 优化条件：问题所要达到的目标能用线型函数描述，且能够用极值（max 或 min）来表示； (2) 限定条件：达到目标受到一定的限制，且这些限制能够用决策变量的线性等式或线性不等式表示； (3) 选择条件：有多种可选择的方案供决策者选择，以便找出最优方案。线性规划问题的数学模型 4. 建模步骤 (1) 确定决策变量：即需要我们作出决策或选择的量。一般情况下，题目问什么就设什么为决策变量； (2) 找出所有限定条件：即决策变量受到的所有的约束； (3) 写出目标函数：即问题所要达到的目标，并明确是max 还是 min。线性规划问题的数学模型目标函数：约束条件： 5. 线性规划数学模型的一般形式简写为：线性规划问题的数学模型向量形式：其中：线性规划问题的数学模型矩阵形式：其中：线性规划问题的数学模型 6. 线性规划问题的标准形式特点： (1) 目标函数求最大值（有时求最小值） (2) 约束条件都为等式方程，且右端常数项bi都大于或等于零 (3) 决策变量xj为非负。线性规划问题的数学模型（2）如何化标准形式目标函数的转换如果是求极小值即，则可将目标函数乘以 (-1)，可化为求极大值问题。也就是：令，可得到上式。即若存在取值无约束的变量，可令其中：变量的变换线性规划问题的数学模型约束方程的转换：由不等式转换为等式。称为松弛变量称为剩余变量常量 bi＜0 的变换:约束方程两边乘以（－1）线性规划问题的数学模型例将下列线性规划问题化为标准形式用替换，且解:（１）因为x3无符号要求，即x3取正值也可取负值，标准型中要求变量非负，所以线性规划问题的数学模型 (2) 第一个约束条件是“≤”号，在“≤”左端加入松驰变量x4，x4≥0,化为等式； (3) 第二个约束条件是“≥”号，在“≥”左端减去剩余变量x5，x5≥0； (4) 第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右端常数项化为正数； (5) 目标函数是最小值，为了化为求最大值，令z′=-z,得到max z′=-z，即当z达到最小值时z′达到最大值，反之亦然; 线性规划问题的数学模型标准形式如下：例将下列线性规划问题化为标准形式为无约束（无非负限制）线性规划问题的数学模型解: 用替换，且，将第3个约束方程两边乘以（－1）将极小值问题反号，变为求极大值标准形式如下：引入变量线性规划问题的数学模型例将线性规划问题化为标准型解：线性规划问题的数学模型例将线性规划问题化为标准型解： Min f= -3 x1 + 5 x2 + 8 x3 - 7 x4 . 2 x1 - 3 x2 + 5 x3 + 6 x4 ≤ 28 4 x1 + 2 x2 + 3 x3 - 9 x4 ≥ 39 6 x2 + 2 x3 + 3 x4 ≤ - 58 x1 , x3 , x4 ≥ 0； x2无约束 Max z = 3x1–5x2’+5x2”–8x3 +7x4 . 2x1–3x2’+3x2”+5x3+6x4+x5= 28 4x1+2x2’-2x2”+3x3-9x4-x6= 39 -6x2’+6x2”-2x3-3x4-x7 = 58 x1 ,x2’,x2”,x3 ,x4 ,x5 ,x6 ,x7 ≥ 0 线性规划问题的数学模型线性规划问题的数学模型 7. 线性规划问题的解线性规划问题求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。线性规划问题的数学模型可行解：满足约束条件②、③的解为可行解。所有可行解的集合为可行域。最优解：使目标函数达到最大值的可行解。基：设A为约束条件②的m×n阶系数矩阵(m<n)，其秩为m，B是矩阵A中m阶满秩子矩阵（∣B∣≠0），称B是规划问题的一个基。设：称 B中每个列向量Pj ( j = 1 2 … … m) 为基向量。与基向量Pj 对应的变量xj 为基变量。除基变量以外的变量为非基变量。线性规划问题的数学模型基解：某一确定的基B，令非基变量等于零，由约束条件方程②解出基变量，称这组解为基解。在基解中变量取非0值的个数不大于方程数m，基解的总数不超过基可行解：满足变量非负约束条件的基本解，简称基可行解。可行基：对应于基可行解的基称为可行基。非可行解可行解基解基可行解线性规划问题的数学模型例求线性规划问题的所有基矩阵。解: 约束方程的系数矩阵为2×5矩阵 r(A)=2，2阶子矩阵有10个，其中基矩阵只有9个，即图解法线性规划问题的求解方法一般有两种方法图解法单纯形法两个变量、直角坐标三个变量、立体坐标适用于任意变量、但必需将一般形式变成标准形式下面我们分析一下简单的情况—— 只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。图解法解题步骤 4 将最优解代入目标函数，求出最优值。 1 在直角平面坐标系中画出所有的约束等式，并找出所有约束条件的公共部分，称为可行域，可行域中的点称为可行解。 2 标出目标函数值增加或者减小的方向。 3 若求最大（小）值，则令目标函数等值线沿（逆）目标函数值增加的方向平行移动，找与可行域最后相交的点，该点就是最优解。图解法 max Z = 2X1 + X2 X1 + ≥ X1 - ≤ . X1 + ≤ X1 - ≥ X1 ，X2 ≥ 0 例用图解法求解线性规划问题图解法 x1 x2 o X1 - = (≤) X1 + = (≥) X1 - = (≥) X1 + = (≤) 4 = 2X1 + X2 20 = 2X1 + X2 = 2X1 + X2 11 = 2X1 + X2 Lo： 0 = 2X1 + X2 （，2） D max Z min Z 此点是唯一最优解，且最优目标函数值 max Z= 可行域 max Z = 2X1 + X2 图解法 max Z=3X1+ x1 x2 o X1 - = (≤) X1 + = (≥) X1 - = (≥) X1 + = (≤) （，2） D L0： 0=3X1+ max Z （，4） = 3X1+ 蓝色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值 max Z=是唯一的。可行域图解法 min Z=5X1+4X2 x1 x2 o X1 - = (≤) X1 + = (≥) X1 + = (≤) D L0： 0=5X1+4X2 max Z min Z 8=5X1+4X2 43=5X1+4X2 （0，2）可行域此点是唯一最优解图解法 2 4 6 x1 x2 2 4 6 无界解(无最优解) max Z=x1+2x2 例 x1+x2=4(≥) x1+3x2=6(≥) 3x1+x2=6(≥) max Z min Z x1 x2 O 10 20 30 40 10 20 30 40 50 50 无可行解(即无最优解) max Z=3x1+4x2 例图解法由图解法得到的几种情况根据以上例题，进一步分析讨论可知线性规划的可行域和最优解有以下几种可能的情况： 1.可行域为封闭的有界区域 (a)有唯一的最优解； (b)有无穷多个最优解； 2.可行域为封闭的无界区域 (c)有唯一的最优解； (d)有无穷多个最优解； (e)目标函数无界(即虽有可行解，但在可行域中，目标函数可以无限增大或无限减少)，因而没有有限最优解。 3.可行域为空集 (f)没有可行解，原问题无最优解图解法由图解法得到的启示 (1) 线性规划问题解的情况：唯一最优解；无穷多最优解；无界解；无可行解 (3) 最优解一定是在凸集的某个顶点 (2) 线性规划问题的可行域是凸集（凸多边形） (4) 解题思路是，先找出凸集的任一顶点，计算其目标函数值，再与周围顶点的目标函数值比较，如不是最大，继续比较，直到找出最大为止。图解法学习要点： 1. 通过图解法了解线性规划有几种解的形式（唯一最优解；无穷多最优解；无界解；无可行解） 2. 作图的关键有三点： (1) 可行解区域要画正确 (2) 目标函数增加的方向不能画错 (3) 目标函数的直线怎样平行移动单纯形法基本原理连接几何形体中任意两点的线段仍完全在该几何形体之中。有限个凸集的交集仍然是凸集。单纯形法基本原理凸集：如果集合C中任意两个点X1、X2，其连线上的所有点也都是集合C中的点，称C为凸集。凸集凸集不是凸集顶点顶点：如果凸集C中不存在任何两个不同的点X1，X2，使X成为这两个点连线上的一个点单纯形法基本原理定理1：若线性规划问题存在可行解，则该问题的可行域是凸集。定理2：线性规划问题的基可行解X对应可行域(凸集)的顶点。定理3：若问题存在最优解，一定存在一个基可行解是最优解。（或在某个顶点取得）单纯形法的计算步骤单纯形法的思路找出一个初始可行解是否最优转移到另一个基本可行解（找出更大的目标函数值）最优解是否循环核心是：变量迭代结束单纯形法的计算步骤单纯形表单纯形法的计算步骤例用单纯形法求下列线性规划的最优解解：1）将问题化为标准型，加入松驰变量x3、x4则标准型为: 单纯形法的计算步骤 2）求出线性规划的初始基可行解，列出初始单纯形表。 b 30 40 θi 0 0 cB 0 0 4 3 cj 0 0 4 3 1 0 3 1 x4 0 1 1 2 x3 x4 x3 x2 x1 基检验数单纯形法的计算步骤 3）进行最优性检验如果表中所有检验数，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。 4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表确定换入基的变量。选择，对应的变量xj作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即：，其对应的xk作为换入变量。确定换出变量。根据下式计算并选择θ ，选最小的θ对应基变量作为换出变量。单纯形法的计算步骤用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。 5）重复3）、4）步直到计算结束为止。单纯形法的计算步骤 x2 x1 x2 x3 4 3 0 0 0 4 3 b 30 40 θi 0 0 cB 0 0 4 3 cj 4 1 0 3 1 x4 0 1 1 2 x3 x4 x3 x2 x1 基变量换入列 bi /ai2，ai2>0 40 10 换出行将3化为1 5/3 1 18 0 1/3 0 1/3 10 1 －1/3 30 30 0 5/3 0 －4/3 乘以1/3后得到 1 0 3/5 －1/5 18 0 1 －1/5 －2/5 4 0 0 －1 －1 单纯形法的计算步骤例用单纯形法求解解：将数学模型化为标准形式：不难看出x4、x5可作为初始基变量，列单纯形表计算。单纯形法的计算步骤 x2 2 x4 0 0 0 1 2 1 1 0 5 1 1/3 20 x5 0 0 1 2 -3 2 15 x4 0 x5 x4 x3 x2 x1 b 基变量 cB θi 0 0 1 2 1 cj 20 － x2 2 1/3 1 5 0 1 20 75 3 0 17 1 3 1/3 0 －9 0 －2 25 60 x1 1 1 0 17/3 1/3 1 25 0 1 28/9 -1/9 2/3 35/3 0 0 -98/9 -1/9 -7/3 单纯形法的计算步骤例用单纯形法求解变成标准型约束方程的系数矩阵为基变量为非基变量 I 为单位矩阵且线性独立单纯形法的计算步骤单纯形法的计算步骤－ x2 2 12 8 16 12 x3 x4 x5 x6 0 0 0 0 b xB cB cj 单纯形法的计算步骤学习要点： 1. 线性规划解的概念以及3个基本定理 2. 熟练掌握线性规划问题的标准化 3.熟练掌握单纯形法的解题思路及求解步骤单纯形法的进一步讨论－人工变量法人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。单纯形法的进一步讨论－人工变量法例用大M法解下列线性规划解：首先将数学模型化为标准形式系数矩阵中不存在单位矩阵，无法建立初始单纯形表。单纯形法的进一步讨论－人工变量法故人为添加两个单位向量，得到人工变量单纯形法数学模型：其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。单纯形法的进一步讨论－人工变量法 -25/3 -5 0 0 0 2/3 0 1 0 0 19/3 x3 -1 5/3 1 0 0 1 31/3 x1 3 2 1 0 1 0 13 x2 2 0 0 0 0 5 ↑ 31/3 1 3/5 0 0 3/5 31/5 x5 0 —— 0 －2/5 1 0 －2/5 11/5 x3 -1 —— 0 －1/5 0 1 －6/5 3/5 x2 2 0 0 -M 0 5M↑ 5-6M —— 0 0 0 1 -2 2 1 x3 -1 8/3 0 1 0 0 3 -3 8 x5 0 3/5 1 0 -1 0 5 -6 3 x6 -M -M -1+2M↑ 2+M 3-2M 1 1 0 0 0 1 -2 2 1 x7 -M 5 0 0 1 0 2 -1 1 10 x5 0 4 0 1 0 -1 1 3 -4 4 x6 -M θi x7 x6 x5 x4 x3 x2 x1 b XB CB -M -M 0 0 -1 2 3 cj → → → 单纯形法的进一步讨论－人工变量法例用大M法解下列线性规划解：首先将数学模型化为标准形式系数矩阵中不存在单位矩阵，无法建立初始单纯形表。单纯形法的进一步讨论－人工变量法故人为添加两个单位向量，得到人工变量单纯形法数学模型：其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。单纯形法的进一步讨论－人工变量法 -M-1 -4M -3M+1 0 -M 0 0 -1+M 1 Z － 1 0 0 0 1 0 -2 1 x3 -1 1 -2 1 -1 0 0 1 0 1 x6 -M － -1 0 0 1 0 -2 3 10 x4 0 0 0 -M 0 -1+3M -1+M 3-6M Z 1 1 0 0 0 1 0 -2 1 x7 -M 3/2 0 1 -1 0 2 1 -4 3 x6 -M 11 0 0 0 1 1 -2 1 11 x4 0 x7 x6 x5 x4 x3 x2 x1 b XB CB -M -M 0 0 -1 -1 3 Cj → → 单纯形法的进一步讨论－人工变量法 2 -2 -M+2/3 -M+1/3 -1/3 -1/3 0 0 0 Z -7/3 4/3 -4/3 2/3 1 0 0 9 x3 -1 -2 1 -1 0 0 1 0 1 x2 -1 -5/3 2/3 -2/3 1/3 0 0 1 4 x1 3 -M-1 -M+1 -1 0 0 0 1 Z － 1 0 0 0 1 0 -2 1 x3 -1 － -2 1 -1 0 0 1 0 1 x2 -1 4 -5 2 -2 1 0 0 3 12 x4 0 x7 x6 x5 x4 x3 x2 x1 b XB CB -M -M 0 0 -1 -1 3 Cj → 单纯形法的进一步讨论－两阶段法用计算机处理数据时，只能用很大的数代替M,可能造成计算机上的错误，故多采用两阶段法。第一阶段：在原线性规划问题中加入人工变量，构造如下模型：对上述模型求解（单纯形法），若ω=0,说明问题存在基可行解，可以进行第二个阶段；否则，原问题无可行解，停止运算。单纯形法的进一步讨论－两阶段法第一阶段的线性规划问题可写为：第一阶段单纯形法迭代的过程见下表（注意：没有化为极大化问题）单纯形法的进一步讨论－两阶段法 x3 x2 x4 0 0 0 0 1 0 -2 1 0 3 0 1 0 0 -1 0 1 ω -5 2 -2 1 0 0 3 12 0 -2 1 -1 0 0 1 0 1 0 0 4 1 1 0 0 0 0 0 ω － 1 0 0 0 1 0 -2 1 x3 0 1 -2 1 -1 0 0 1 0 1 x6 1 － -1 0 0 1 0 -2 3 10 x4 0 0 0 1 0 -3 -1 6 ω 1 1 0 0 0 1 0 -2 1 x7 1 3/2 0 1 -1 0 2 1 -4 3 x6 1 11 0 0 0 1 1 -2 1 11 x4 0 x7 x6 x5 x4 x3 x2 x1 b XB CB -M -M 0 0 -1 -1 3 Cj → → 单纯形法的进一步讨论－两阶段法第二阶段：在第一阶段的最终表中，去掉人工变量，将目标函数的系数换成原问题的目标函数系数，作为第二阶段计算的初始表（用单纯形法计算）。例：单纯形法的进一步讨论－两阶段法 -1/3 -1/3 0 0 0 2 Z -2 -4/3 2/3 1 0 0 9 x3 -1 -1 0 0 1 0 1 x2 -1 -2/3 1/3 0 0 1 4 x1 3 -1 0 0 0 1 Z － 0 0 1 0 -2 1 x3 -1 － -1 0 0 1 0 1 x2 -1 4 -2 1 0 0 3 12 x4 0 x5 x4 x3 x2 x1 b xB cB 0 0 -1 -1 3 cj → 第二阶段： ∴最优解为（4 1 9 0 0），目标函数 Z = 2 单纯形法的进一步讨论通过大Ｍ法或两阶段法求初始的基本可行解。但是如果在大Ｍ法的最优单纯形表的基变量中仍含有人工变量，或者两阶段法的辅助线性规划的目标函数的极小值大于零，那么该线性规划就不存在可行解。无可行解 C -3 -2 -1 0 0 0 -M -M CB XB b x1 x2 x3 x4 x5 x6 x7 x8 θ 0 -M -M x4 x7 x8 6 4 3 1 1 1 1 0 0 0 0 1 0 -1 0 -1 0 1 0 0 1 -1 0 0 -1 0 1 6/1 - 3/1 Z -7M -6-4M -15-M -3+M -2+M -1-2M 0 -M -M 0 0 0 -M -2 x4 x7 x2 3 4 3 1 0 2 1 0 1 0 -1 1 0 -1 0 -1 0 1 0 0 1 -1 0 0 -1 0 1 3/1 4/1 - Z Z -3+M 0 -3-M 0 -M -2 0 2-M -3 -M -2 x1 x7 x2 3 1 3 1 0 2 1 0 1 0 -1 0 0 -3 -1 -1 -1 1 1 0 1 -1 0 0 -1 0 1 0 0 3-3M 3-M -M 1-M 0 -1 例单纯形法的进一步讨论运算到检验数全负为止，仍含有人工变量，无可行解。单纯形法的进一步讨论无最优解与无可行解时两个不同的概念。无可行解是指原规划不存在可行解，从几何的角度解释是指线性规划问题的可行域为空集；无最优解则是指线性规划问题存在可行解，但是可行解的目标函数达不到最优值，即目标函数在可行域内可以趋于无穷大（或者无穷小）。无最优解也称为有限最优解，或无界解。判别方法：无最优解判别定理　　在求解极大化的线性规划问题过程中，若某单纯形表的检验行存在某个大于零的检验数，但是该检验数所对应的非基变量的系数列向量的全部系数都为负数或零，则该线性规划问题无最优解无最优解 0 0 2 2 0 Z 1 0 1 -1/2 2 X4 0 0 1 1 -1 1 X3 0 x4 x3 x2 x1 B XB C θ 2 2 0 0 C 因但所以原问题无最优解单纯形法的进一步讨论退化　　即计算出的 θ（用于确定换出变量）存在有两个以上相同的最小比值，会造成下一次迭代中由一个或几个基变量等于零，这就是退化（会产生退化解）。为避免出现计算的循环，勃兰特(Bland)提出一个简便有效的规则（摄动法原理）： ⑴ 当存在多个时，选下标最小的非基变量为换入变量； (2) 当θ值出现两个以上相同的最小值时，选下标最小的基变量为换出变量。单纯形法的进一步讨论 0 0 0 -24 2 -80 3 0 Z -5 -6 0 -42 0 -8 0 5 Z 1 0 0 0 1 0 0 1 x3 2 1 2 0 6 0 -24 1 1 x1 3 3 2 1 30 0 -8 0 3 x5 0 0 -3 0 -42 5 -8 0 0 Z 1 1 0 0 1 0 0 1 x7 0 0 1 0 6 -1 -24 1 0 x1 3 0 -1 1 30 -3 -8 0 0 x5 0 - 1 1 0 0 1 0 0 1 x7 0 0 0 1 0 6 -1 -24 1 0 x6 0 0 0 0 1 36 -4 -32 1 0 x5 0 x7 x6 x5 x4 x3 x2 x1 b XB CB 0 0 0 -24 2 -80 3 C θ 第一次迭代中使用了摄动法原理，选择下标为6的基变量x6离基。可得最优解 maxZ=５，单纯形法的进一步讨论无穷多最优解　　若线性规划问题某个基本可行解所有的非基变量检验数都小于等于零，但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。例３：最优表：非基变量检验数　　　，所以有无穷多最优解。 0 0 0 0 -1 8 Z’ 2/2 3/1 - 0 0 1 2 -1 0 1 0 1 0 1 0 0 -2 1 2 3 2 x3 x2 x1 0 2 1 x1 x2 x3 x4 x5 b XB CB θ 1 2 0 0 0 C 单纯形法的进一步讨论单纯形法的进一步讨论解的判别： 1）唯一最优解判别：最优表中所有非基变量的检验数非零,则线性规划具有唯一最优解。 2）多重最优解判别：最优表中存在非基变量的检验数为零,则线性规划具有多重最优解（或无穷多最优解）。 3）无界解判别：某个λk>0且aik≤０（i=1，2,…,m）则线性规划具有无界解。 4）无可行解的判断：当用大M单纯形法计算得到最优解并且存在Ri>0时，则表明原线性规划无可行解。 5）退化解的判别：存在某个基变量为零的基本可行解。单纯形法的进一步讨论单纯性法小结: -M 0 令 z′=- Z minZ =－ max z′ 不处理减去 xs 加入 xa 加入人工变量xa 加松弛变量xs 约束条件两端同乘以-1 不处理令 xj’ = - xj 令xj = xj′ - xj″ xj′ ≥0 xj″ ≥0 不处理单纯形法图解法、单纯形法求解 xa xs min Z max Z ≥ = ≤ bi < 0 bi ≥0 xj ≤ 0 xj无约束 xj≥0 三个以上两个新加变量系数极大或极小等式或不等式右端项取值个数建立模型 A 线性规划模型的应用一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。要求解问题的目标函数能用数值指标来反映，且为线性函数存在着多种方案要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述线性规划模型的应用常见问题合理利用线材问题：如何下料使用材最少。配料问题：在原料供应量的限制下如何获取最大利润。投资问题：从投资项目中选取方案，使投资回报最大。产品生产计划：合理利用人力、物力、财力等，使获利最大。劳动力安排：用最少的劳动力来满足工作的需要。运输问题：如何制定调运方案，使总运费最小。线性规划模型的应用 (1)设立决策变量； (2)明确约束条件并用决策变量的线性等式或不等式表示； (3)用决策变量的线性函数表示目标，并确定是求极大（Max）还是极小（Min）； (4)根据决策变量的物理性质研究变量是否有非负性。建立线性规划模型的过程可以分为四个步骤：线性规划在经济管理中的应用 1. 资源的合理利用某厂计划在下一生产周期内生产B1,B2, … Bn种产品，要消耗A1,A2, … Am种资源，已知每件产品所消耗的资源数、每种资源的数量限制以及每件产品可获得的利润如表所示，问如何安排生产计划，才能充分利用现有的资源，使获得的总利润最大？单件利润资源限制单件产消耗品资源线性规划在经济管理中的应用 2. 生产组织与计划问题某工厂用机床A1,A2, … Am 加工B1,B2, … Bn 种零件。在一个周期内，各机床可能工作的机时（台时），工厂必须完成各种零件的数量、各机床加工每个零件的时间（机时/个）和加工每个零件的成本（元/个）如表所示，问如何安排各机床的生产任务，才能完成加工任务，又使总成本最低？必须零件数机时限制加工零时间件机床加工零成本件机床线性规划在经济管理中的应用某厂生产Ⅰ、Ⅱ、Ⅲ三种产品，都分别经A、B两道工序加工。设A工序可分别在设备A1和A2上完成，有B1、B2、B3三种设备可用于完成B工序。已知产品Ⅰ可在A、B任何一种设备上加工；产品Ⅱ可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品Ⅲ只能在A2与B2设备上加工。加工单位产品所需工序时间及其他各项数据如下表，试安排最优生产计划，使该厂获利最大。线性规划在经济管理中的应用线性规划在经济管理中的应用售价（每件）原料费（每件） 200 4000 11 7 B3 783 7000 4 B2 250 4000 12 8 6 B1 321 10 000 9 7 A2 300 6000 10 5 A1 Ⅲ Ⅱ Ⅰ 设备加工费（单位小时）设备有效台时产品设备解：设xijk表示产品i在工序j的设备k上加工的数量。约束条件有：线性规划在经济管理中的应用线性规划在管理中的应用目标是利润最大化，即利润的计算公式如下：带入数据整理得到：线性规划在管理中的应用因此该规划问题的模型为：线性规划在经济管理中的应用 3. 合理下料问题例：现有一批某种型号的圆钢长8米，需要截取米长的毛坯100根，长米的毛坯200根。问如何才能既满足需要，又能使总的用料最少？解：为了找到一个省料的套裁方案，必须先设计出较好的几个下料方案。其次要求这些方案的总体能裁下所有各种规格的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目的，为此可以设计出4种下料方案以供套裁用。料头 6 0 Ⅳ 4 2 0 1 2 3 Ⅲ Ⅱ Ⅰ 线性规划在管理中的应用设按方案Ⅰ、Ⅱ、Ⅲ、Ⅳ下料的原材料根数分别为xj (j=1，2,3,4)，可列出下面的数学模型：线性规划在经济管理中的应用 4. 合理配料问题某饲养场用n种饲料B1,B2, … Bn配置成含有m种营养成分A1,A2, … Am的混合饲料，其余资料如表所示。问应如何配料，才能既满足需要，又使混合饲料的总成本最低？解：线性规划在管理中的应用例：某人每天食用甲、乙两种食物（如猪肉、鸡蛋），其资料如下：问两种食物各食用多少，才能既满足需要、又使总费用最省？ 2 原料单价 A1 A2 A3 最低需要量甲乙含量食物成分线性规划在管理中的应用解：设Xj 表示Bj 种食物用量线性规划在管理中的应用 5.人力资源分配问题例某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示： 30 2:00——6:00 6 20 22:00——2:00 5 50 18:00——22:00 4 60 14:00——18:00 3 70 10:00——14:00 2 60 6:00——10:00 1 所需人员时间班次设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少? 线性规划在管理中的应用解：设xi表示第i班次时开始上班的司机和乘务人员人数。此问题最优解：x1＝50， x2＝20， x3＝50， x4＝0， x5＝20， x6＝10，一共需要司机和乘务员150人。 Chapter2 对偶理论 ( Duality Theory ) 线性规划的对偶模型对偶性质对偶问题的经济解释－影子价格对偶单纯形法灵敏度分析本章主要内容：线性规划的对偶模型设某工厂生产两种产品甲和乙，生产中需4种设备按A，B，C，D顺序加工，每件产品加工所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表：产品数据表 12 16 8 12 设备可利用机时数（时） 3 4 0 2 2 乙 2 0 4 1 2 甲产品利润（元／件） D C B A 设备产品问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能获得最大利润？ 1. 对偶问题的提出线性规划的对偶模型解：设甲、乙型产品各生产x1及x2件，则数学模型为：反过来问：若厂长决定不生产甲和乙型产品，决定出租机器用于接受外加工，只收加工费，那么４种机器的机时如何定价才是最佳决策？线性规划的对偶模型在市场竞争的时代，厂长的最佳决策显然应符合两条：（1）不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型产品所获利润。由此原则，便构成了新规划的不等式约束条件。（2）竞争性原则。即在上述不吃亏原则下，尽量降低机时总收费，以便争取更多用户。设A、B、C、D设备的机时价分别为y1、y2、y3、y4，则新的线性规划数学模型为：线性规划的对偶模型把同种问题的两种提法所获得的数学模型用表2表示，将会发现一个有趣的现象。原问题与对偶问题对比表 minω max z 12 16 8 12 3 4 0 2 2 乙（x2） 2 0 4 1 2 甲（x1） D（y4） C（y3） B（y2） A（y1）对偶性是线性规划问题的最重要的内容之一。每一个线性规划（ LP ）必然有与之相伴而生的另一个线性规划问题，即任何一个求 maxZ 的LP都有一个求 minZ 的LP。其中的一个问题叫“原问题”，记为“P”，另一个称为“对偶问题”，记为“D”。线性规划的对偶模型 2. 原问题与对偶问题的对应关系原问题-P 对偶问题-D 线性规划的对偶模型 3 2 对偶问题 12 ≤ 4 0 y4 12 16 ≤ 0 4 y3 16 8 ≤ 2 1 y2 8 12 ≤ 2 2 y1 12 原问题 x2 x1 3 2 线性规划的对偶模型（1）对称形式特点：目标函数求极大值时，所有约束条件为≤号，变量非负;目标函数求极小值时，所有约束条件为≥号，变量非负. 变量数量约束条件个数约束条件个数变量数量 ≥ ≤ 约束条件 min max 目标函数对偶问题原问题线性规划的对偶模型例写出线性规划问题的对偶问题解：首先将原问题变形为对称形式注意：以后不强调等式右段项 b≥0，原因在对偶单纯型表中只保证而不保证，故 b可以是负数。线性规划的对偶模型线性规划的对偶模型 (2) 非对称型对偶问题若给出的线性规划不是对称形式，可以先化成对称形式再写对偶问题。也可直接按教材表2-2中的对应关系写出非对称形式的对偶问题。线性规划的对偶模型 ≥ ≥0 约束条件右端项目标函数变量的系数 C 目标函数变量的系数约束条件右端项 b = 无约束 ≤ ≤0 约束条件 n个 n个变量无约束 = ≤0 ≥ ≥0 ≤ 变量 m个 m个约束条件目标函数 min 目标函数 max 对偶问题（或原问题）原问题（或对偶问题）线性规划的对偶模型例写出下列线性规划问题的对偶问题. 解：原问题的对偶问题为无约束线性规划的对偶模型例写出下列线性规划问题的对偶问题. 解：原问题的对偶问题为线性规划的对偶模型例线性规划的对偶模型对偶性质性质1 对称性定理：对偶问题的对偶是原问题 min Z’= - CX . - AX≤- b X ≥0 min W= Y b . YA ≥ C Y ≤ 0 max Z=C X . AX≥b X ≥0 对偶的定义对偶的定义 max W’ = -Yb . YA≥ C Y ≤ 0 对偶性质性质2 弱对偶原理(弱对偶性)：设和分别是问题(P)和(D)的可行解，则必有推论1: 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。推论2: 在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；反之不成立。这也是对偶问题的无界性。对偶性质例无界（原）无可行解（对）关于无界性有如下结论：问题无界无可行解无可行解问题无界对偶问题原问题对偶性质推论3：在一对对偶问题（P）和（D）中，若一个可行（如P），而另一个不可行（如D），则该可行的问题目标函数值无界。试估计它们目标函数的界，并验证弱对偶性原理。（P）例对偶性质解：（D）由观察可知： =（）， =（），分别是（P）和（D）的可行解。Z=10 ，W=40，故有，弱对偶定理成立。由推论⑴可知，W 的最小值不能小于10，Z 的最大值不能超过40。＜对偶性质性质3 最优性定理：如果是原问题的可行解，是其对偶问题的可行解，并且: 则是原问题的最优解，是其对偶问题的最优解。例如:在一对对偶问题（P）和（D）中，可找到 X*=（）， Y*=（，）,且Z=W28 ，则X*，Y*分别是 P和D 的最优解。对偶性质性质4 强对偶性：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。还可推出另一结论：若（LP）与（DP）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。性质5 互补松弛性：设X0和Y0分别是P问题和 D问题的可行解，则它们分别是最优解的充要条件是：其中：Xs、Ys为松弛变量对偶性质性质5的应用：该性质给出了已知一个问题最优解求另一个问题最优解的方法，即已知Y＊求X＊或已知X＊求Y＊互补松弛条件由于松弛变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：若Y＊≠0，则Xs必为0；若X＊≠0，则Ys必为0 利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。对偶性质例已知线性规划的最优解是X＊=(6,2,0)T,求其对偶问题的最优解Y＊。解：写出原问题的对偶问题，即标准化对偶性质设对偶问题最优解为Y＊＝(y1，y2),由互补松弛性定理可知，X＊和 Y＊满足：即：因为X1=6≠0，X2=2≠0，所以对偶问题的第一、二个约束的松弛变量等于零，即y3＝0，y4＝0，带入方程中：解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为： Y＊=(1,1)，最优值w=26。对偶性质例已知线性规划的对偶问题的最优解为Y＊=(0,-2)，求原问题的最优解。解: 对偶问题是标准化无约束对偶性质设对偶问题最优解为X＊＝(x1，x2 ，x3)T ,由互补松弛性定理可知，X＊和 Y＊满足：将Y＊ =(0,-2)带入由方程可知，y3＝y5＝0，y4＝1。 ∵y2=-2≠0 ∴x5＝0 又∵y4=1≠0 ∴x2＝0 将x2，x5分别带入原问题约束方程中，得：解方程组得：x1=-5,x3=-1, 所以原问题的最优解为 X＊=(-5,0,-1)，最优值z=-12 对偶性质原问题与对偶问题解的对应关系小结无可行解无界解最优解无法判断 (Y,Y) —— 无可行解 (Y,Y) —— —— 无界解 —— —— (Y,Y) (N,N) 最优解对偶问题原问题对应关系对偶问题的经济解释－影子价格 1. 影子价格的数学分析：定义：在一对 P 和 D 中，若 P 的某个约束条件的右端项常数bi （第i种资源的拥有量）增加一个单位时，所引起目标函数最优值z* 的改变量称为第 i 种资源的影子价格，其值等于D问题中对偶变量yi*。由对偶问题得基本性质可得：对偶问题的经济解释－影子价格 2. 影子价格的经济意义 1）影子价格是一种边际价格在其它条件不变的情况下，单位资源数量的变化所引起的目标函数最优值的变化。即对偶变量yi 就是第 i 种资源的影子价格。即：对偶问题的经济解释－影子价格 2）影子价格是一种机会成本影子价格是在资源最优利用条件下对单位资源的估价，这种估价不是资源实际的市场价格。因此，从另一个角度说，它是一种机会成本。若第i 种资源的单位市场价格为mi ，则有当yi* > mi 时，企业愿意购进这种资源，单位纯利为yi*－mi ，则有利可图；如果yi* < mi ，则企业有偿转让这种资源，可获单位纯利mi－yi * ，否则，企业无利可图，甚至亏损。结论：若yi* > mi 则购进资源i，可获单位纯利yi*－mi 若yi* < mi则转让资源i ，可获单位纯利mi－yi 对偶问题的经济解释－影子价格 3）影子价格在资源利用中的应用根据对偶理论的互补松弛性定理: Y*Xs=0 , YsX*=0 表明生产过程中如果某种资源bi未得到充分利用时，该种资源的影子价格为0；若当资源资源的影子价格不为0时，表明该种资源在生产中已耗费完。对偶问题的经济解释－影子价格 4）影子价格对单纯形表计算的解释单纯形表中的检验数其中cj表示第j种产品的价格; 表示生产该种产品所消耗的各项资源的影子价格的总和,即产品的隐含成本。当产值大于隐含成本时，即，表明生产该项产品有利，可在计划中安排；否则，用这些资源生产别的产品更有利，不在生产中安排该产品。对偶单纯形法对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。对偶单纯形法原理对偶单纯形法基本思路：找出一个对偶问题的可行基，保持对偶问题为可行解的条件下，判断XB是否可行（XB=b为非负），有最优解。否则，通过变换基解，直到找到原问题基可行解（即XB为非负），这时原问题与对偶问题同时达到可行解，由定理4可得。对偶单纯形法找出一个DP的可行基 LP是否可行（XB ≥0）保持DP为可行解情况下转移到LP的另一个基本解最优解是否循环结束对偶单纯形法例用对偶单纯形法求解：解:（1）将模型转化为求最大化问题，约束方程化为等式求出一组基本解，因为对偶问题可行（求max问题）。对偶单纯形法 0 -14 -12 -10 b 0 0 1 0 x5 0 0 1 0 0 x6 0 0 -15 -12 -9 λj 0 -5 -1 -1 x6 0 0 -1 -3 -2 x5 0 1 -1 -2 -2 x4 0 x4 x3 x2 x1 xB cB 0 -15 -12 -9 cj 对偶单纯形法 42 14/5 -46/5 -36/5 b 0 0 1 0 x5 0 -3 -1/5 -1/5 -1/5 x6 0 (-30/-9,-45/-14, -15/-1) 0 0 -9 -6 0 1 1/5 1/5 x3 -15 0 0 -14/5 -9/5 x5 0 1 0 -9/5 -9/5 x4 0 x4 x3 x2 x1 xB cB 0 -15 -12 -9 cj 15/7 23/7 -9/7 b -45/14 1/14 -5/14 -9/14 x5 0 -33/14 -3/14 1/14 -1/14 x6 0 (-3/-9,-45/-9, -33/-1) 0 0 0 -3/14 0 1 0 1/14 x3 -15 0 0 1 9/14 x2 -12 1 0 0 -9/14 x4 0 x4 x3 x2 x1 xB cB 0 -15 -12 -9 cj 对偶单纯形法 2 2 2 b -3 0 -1 1 x5 0 -7/3 -2/9 0 1/9 x6 0 -1/3 0 0 0 1/9 1 0 0 x3 -15 1 0 1 0 x2 -12 -14/9 0 0 1 x1 -9 x4 x3 x2 x1 xB cB 0 -15 -12 -9 cj 原问题的最优解为：X*=（2 , 2 , 2 , 0 , 0 , 0），Z* =72 由定理4，其对偶问题的最优解为：Y*= （1/3 , 3 , 7/3），W*= 72 对偶单纯形法对偶单纯形法应注意的问题：用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶问题的最优解初始表中一定要满足对偶问题可行，也就是说检验数满足最优判别准则最小比值中的绝对值是使得比值非负，在极小化问题σj≥0，分母aij<0 这时必须取绝对值。在极大化问题中， σ j≤0，分母aij<0，总满足非负，这时绝对值符号不起作用，可以去掉。如在本例中将目标函数写成这里σj ≤0在求θk时就可以不带绝对值符号。对偶单纯形法对偶单纯形法与普通单纯形法的换基顺序不一样，普通单纯形法是先确定进基变量后确定出基变量，对偶单纯形法是先确定出基变量后确定进基变量；普通单纯形法的最小比值是其目的是保证下一个原问题的基本解可行，对偶单纯形法的最小比值是其目的是保证下一个对偶问题的基本解可行对偶单纯形法在确定出基变量时，若不遵循规则，任选一个小于零的bi对应的基变量出基，不影响计算结果，只是迭代次数可能不一样。灵敏度分析线性规划问题的标准形式令：灵敏度分析一、价值系数cj的变化分析例1：某企业利用三种资源生产两种产品的最优计划问题归结为下列线性规划问题：（1）确定x2的系数c2的变化范围，使原最优解保持最优；（2）若c2=6，求新的最优计划。灵敏度分析 -3 2 -1 -5 x5 0 -1 0 0 0 σj -1 0 1 0 10 x2 4 1 0 0 1 35 x1 5 2 1 0 0 25 x3 0 x4 x3 x2 x1 b XB CB 0 0 4 5 cj 最优表如下：灵敏度分析 σ4 = c2－5 ≤ 0 σ5 = 5－2c2 ≤ 0 5/2 ≤ c2 ≤ 5 5 - 2c2 2 -1 -5 x5 0 c2 - 5 0 0 0 σj -1 0 1 0 10 x2 c2 1 0 0 1 35 x1 5 2 1 0 0 25 x3 0 x4 x3 x2 x1 b XB CB 0 0 c2 5 cj 最优解X*=（35，10，25，0，0）保持不变。（1）灵敏度分析（2） x2 x1 x4 -9/2 0 -1/2 0 0 σj -1/2 0 1/2 1 0 45/2 6 3/2 0 -1/2 0 1 45/2 5 -5/2 1 1/2 0 0 25/2 0 -7 2 -1 -5 x5 0 1 0 0 0 σj -1 0 1 0 10 x2 6 1 0 0 1 35 x1 5 [2] 1 0 0 25 x3 0 x4 x3 x2 x1 b XB CB 0 0 6 5 Cj 用对偶单纯形法是求解得。 x1*=45/2，x2*=45/2，x4*=25/2，x3*= x5*=0，z*=495/2 灵敏度分析二、右端常数bi的变化分析 XB= B－1b 例2：对于上例中的线性规划作下列分析：（1）b3在什么范围内变化，原最优基不变？（2）若b3=55，求出新的最优解。灵敏度分析 -3 2 -1 -5 x5 0 -1 0 0 0 -1 0 1 0 10 x2 4 1 0 0 1 35 x1 5 2 1 0 0 25 x3 0 x4 x3 x2 x1 b XB CB 0 0 4 5 cj 最优基： B=I=（P3，P1，P2） B－1= 最优解： X*=（35，10，25，0，0）灵敏度分析（1） XB=B－1b= = = ≥0 B－1 解得40≤b3≤50，即当b3∈[40，50] 时，最优基B 不变 z*=5×（80－b3）+4×（－80+2b3） =80+3b3 = 灵敏度分析（2）当 b3= 55 时 = x2 x1 x5 0 -11/5 -3/5 0 0 σj 0 -1/5 2/5 1 0 20 4 0 3/5 -1/5 0 1 30 5 1 -2/5 -1/5 0 0 5 0 -3 2 -1 [-5] x5 0 -1 0 0 0 σj -1 0 1 0 30 x2 4 1 0 0 1 25 x1 5 2 1 0 0 -25 x3 0 x4 x3 x2 x1 b XB CB 0 0 4 5 Cj 最优解：X*=（30，20，0，0，5）灵敏度分析三、增加一个变量的分析例3：（续例1）设企业研制了一种新产品，对三种资源的消耗系数列向量以P6表示P6= 。问它的价值系数c6符合什么条件才必须安排它的生产？设c6=3，新的最优生产计划是什么？ σ6=c6－CBB－1P6 =c6－（0，5，4） = c6－5/2 =B－1P6 = = 灵敏度分析 0 0 0 1 1/2 0 1/2 [1] x6 3 x2 x1 x6 -1/2 -2 -1/2 0 0 σj 2 -1 0 1 0 10 4 3/2 0 -1/2 0 1 45/2 5 -5 2 1 0 0 25 3 -3 2 -1 -5 x5 0 -1 0 0 0 σj -1 0 1 0 10 x2 6 1 0 0 1 35 x1 5 2 1 0 0 25 x3 0 x4 x3 x2 x1 b XB CB 0 0 4 5 Cj 灵敏度分析四、增加新的约束条件的分析例4: 假设在例1中，还要考虑一个新的资源约束： 4x1+2x2≤150 标准化灵敏度分析 1 0 0 0 2 4 150 x6 0 0 0 0 0 x6 0 -3 2 -1 -5 x5 0 -1 0 0 0 -1 0 1 0 10 x2 4 1 0 0 1 35 x1 5 2 1 0 0 25 x3 0 x4 x3 x2 x1 b XB CB 0 0 4 5 cj 1/2 -1 0 0 0 1 30 x1 5 0 2 -1 0 1 0 10 x2 4 1 0 0 0 2 4 150 x6 0 x4 x2 x3 x6 x1 x3 -1/2 -3 0 0 0 0 σj -1/2 0 1 0 0 0 5 0 -1/2 2 0 0 1 0 15 4 1 -5 0 1 0 0 15 0 0 -3 -3 0 0 0 σj 1 0 [-2] 0 0 0 -10 0 0 -1 1 0 0 1 35 5 0 -5 2 1 0 0 25 0 -3 2 -1 -5 x5 0 0 0 0 0 x6 0 -1 0 0 0 σj -1 0 1 0 10 x2 4 1 0 0 1 35 x1 5 2 1 0 0 25 x3 0 x4 x3 x2 x1 b XB CB 0 0 4 5 Cj 灵敏度分析 1. cj和bi同时变化的情况五、其它变化情况的分析例5: 在例1中，假定c2由4上升为6，b3增加到55，试问最优解将会发生什么变化？ B－1= B－ = = 代替最优表的b列，并把c2改为6 灵敏度分析 -7 2 -1 -5 x5 0 1 0 0 0 σj -1 0 1 0 30 x2 6 1 0 0 1 25 x1 5 2 1 0 0 -25 x3 0 x4 x3 x2 x1 b XB CB 0 0 6 5 cj 原问题与对偶问题均非可行解，表中第一方程是:x3+2x4－5x5=－25，两边乘以（-1），得－x3－2x4 + 5x5= 25，再引入人工变量x6：－x3－2x4+5x5+x6=25 以x6为基变量，增添第6列，应用大M法继续求解。 -M+7/5 -2/5 1/5 0 0 0 0 1 x6 -M x2 x1 x5 0 -9/5 -7/5 0 0 σj 0 -1/5 2/5 1 0 20 6 0 3/5 -1/5 0 1 30 5 1 -2/5 -1/5 0 0 5 0 5M-7 2 -1 [5] x5 0 -2M+1 -M 0 0 σj -1 0 1 0 30 x2 6 1 0 0 1 25 x1 5 -2 -1 0 0 25 x6 -M x4 x3 x2 x1 b XB CB 0 0 6 5 Cj 新的最优计划产量为x1*=30，x2*=20，z*=270。－x3－2x4+5x5+x6=25 灵敏度分析 2. 技术系数aij的变化例6:在例1中，第一种产品的消耗系数改变为 ,价值系数不变，求新的最优解。 B－1= 灵敏度分析 -3 2 -1 -5 x5 0 -1 0 0 0 σj -1 0 1 -1/2 10 x2 4 1 0 0 1 35 x1 5 2 1 0 2 25 x3 0 x4 x3 x2 x1 b XB CB 0 0 4 5 Cj 5 x2 50 x1 15 x5 -1 -3 0 0 0 σj 1 0 -1/3 0 0 0 0 1 -1/3 0 1 5 0 -1/2 1/2 1 0 4 x2 x1 x3 0 -3 -1/3 0 0 σj 3/2 -1/2 0 1 0 4 -1 1 0 0 1 35 5 [-3] 0 1 0 0 -45 0 -3 2 -1 -5 x5 0 -1 0 0 0 σj -1 0 1 -1/2 10 x2 4 1 0 0 [1] 35 x1 5 2 1 0 2 25 x3 0 x4 x3 x2 x1 b XB CB 0 0 4 5 Cj 思考题判断下列结论是否正确，如果不正确，应该怎样改正？ 1）任何线性规划都存在一个对应的对偶线性规划. 2）原问题第i个约束是“≤”约束，则对偶变量yi≥0. 3）互为对偶问题，或者同时都有最优解，或者同时都无最优解. 4）对偶问题有可行解，则原问题也有可行解. 5）原问题有多重解，对偶问题也有多重解. 6）对偶问题有可行解，原问题无可行解，则对偶问题具有无界解. 7）原问题无最优解，则对偶问题无可行解. 8）对偶问题不可行，原问题可能无界解. 9）原问题与对偶问题都可行，则都有最优解. 10）原问题具有无界解，则对偶问题不可行. 11）对偶问题具有无界解，则原问题无最优解. 12）若X*、Y*是原问题与对偶问题的最优解，则X*=Y*. 本章小结学习要点： 1. 线性规划解的概念以及3个基本定理 2. 熟练掌握单纯形法的解题思路及求解步骤 3. 熟练掌握对偶问题的转换 4. 掌握对偶问题的5个性质 5. 熟练掌握对偶单纯形法的解题思路及求解步骤 Chapter3 运输规划 ( Transportation Problem ) 运输规划问题的数学模型表上作业法运输问题的应用本章主要内容：运输规划问题的数学模型例某公司从两个产地A1、A2将物品运往三个销地B1, B2, B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？ 200 150 150 销量 300 5 5 6 A2 200 6 4 6 A1 产量 B3 B2 B1 运输规划问题的数学模型解：产销平衡问题：总产量 = 总销量＝500 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表： 200 150 150 销量 300 x23 x22 x21 A2 200 x13 x12 x11 A1 产量 B3 B2 B1 Min C = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 . x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij ≥ 0 ( i = 1、2；j = 1、2、3）运输规划问题的数学模型运输问题的一般形式：产销平衡 A1、 A2、…、 Am 表示某物资的m个产地； B1、B2、…、Bn 表示某物质的n个销地；ai 表示产地Ai的产量； bj 表示销地Bj 的销量； cij 表示把物资从产地Ai运往销地Bj的单位运价。设 xij 为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型：运输规划问题的数学模型已知资料如下：产量销产地地产销平衡销量运价运输规划问题的数学模型当产销平衡时，其模型如下：运输规划问题的数学模型当产大于销时，其模型如下：运输规划问题的数学模型当产小于销时，其模型如下：运输规划问题的数学模型特征： 1、平衡运输问题必有可行解，也必有最优解； 2、运输问题的基本可行解中应包括 m+n－1 个基变量。运输规划问题的数学模型运输问题约束条件的系数矩阵 m n 运输规划问题的数学模型基本可行解是否最优解结束换基是否运输问题的求解思路运输规划问题的数学模型计算步骤： (1) 找出初始调运方案。即在(m×n)产销平衡表上给出m+n-1个数字格。(最小元素法、西北角法或伏格尔法） (2) 求检验数。（闭回路法或位势法）判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。 (3) 对方案进行改善，找出新的调运方案。（表上闭回路法调整）确定m+n-1个基变量 (4) 重复（2）、（3），直到求得最优调运方案。空格二、表上作业法表上作业法表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。方法描述步骤第三步第二步第一步调整运量，即换基，选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步闭回路法和位势法求检验数并判断是否得到最优解当非基变量的检验数σi j全都非负(求min)时得到最优解，若存在检验数σi j <0，说明还没有达到最优，转第三步。最小元素法、西北角法、伏格尔法求初始基行可行解（初始调运方案）表上作业法例某运输资料如下表所示： 6 5 6 3 销量 9 5 10 4 7 4 8 2 9 1 7 10 3 11 3 产量单位销地运价产地问：应如何调运可使总运输费用最小？ 1、求初始方案：最小元素法、西北角法、伏格尔法表上作业法基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。 6 5 6 3 销量 9 A3 4 A2 7 A1 产量 B4 B3 B2 B1 3 11 3 10 1 9 2 7 4 10 5 8 总的运输费＝(3×1)+(6×4) +(4×3) +(1×2)+(3×10)+(3×5)=86元方法1：最小元素法 3 4 1 6 3 3 表上作业法练习 13 12 13 22 销量 19 6 10 9 5 A3 27 7 2 4 8 A2 14 3 5 7 6 A1 产量 B4 B3 B2 B1 销地产地 12 13 13 19 1 2 表上作业法（2）西北角法（或左上角法）此法是纯粹的人为的规定，没有理论依据和实际背景，但它易操作，特别适合在计算机上编程计算，因而受欢迎。方法如下： 3 6 5 6 7 4 9 3 4 4 9 0 6 5 6 4 0 4 9 0 2 5 6 2 0 2 9 0 0 5 6 2 0 0 9 0 0 3 6 3 6 0 0 0 0 0 0 0 3 4 0 0 0 2 2 0 0 0 3 6 表上作业法在满足约束条件下尽可能的给最左上角的变量最大值. 48 14 12 14 8 销量 22 6 11 5 8 A3 10 9 3 10 2 A2 16 11 4 12 4 A1 产量 B4 B3 B2 B1 销地产地 8 8 6 4 8 14 所以，初始基可行解为：(8,8,4,8,14)目标函数值Z＝372 例某运输资料如下表所示：表上作业法练习 13 12 13 22 销量 19 6 10 9 5 A3 27 7 2 4 8 A2 14 3 5 7 6 A1 产量 B4 B3 B2 B1 销地产地 8 13 13 14 6 6 表上作业法最小元素法的缺点是：为了节省一处的费用，有时造成在其他处要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。例如下面两种运输方案。最小元素法： 15 15 20 1 2 10 5 8 15 5 10 总运费是z=10×8 +5×2+15×1=105 15 15 20 1 2 10 5 8 5 15 10 另一种方法：总运费z=10×5 +15×2+5×1=85 表上作业法方法2：Vogel法 1）从运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。 3 1 5 2 列差额 1 1 7 行差额 6 5 6 3 销量 9 A3 4 A2 7 A1 产量 B4 B3 B2 B1 3 11 3 10 1 9 2 7 4 10 5 8 10-3=7 2-1=1 5-4=1 3-1=2 9-4=5 3-2=1 8-5=3 表上作业法 2）再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量供应完毕或得到满足时，划去运价表中对应的行或列。重复1)和2)，直到找出初始解为至。 3 1 5 2 列差额 1 1 7 行差额 6 5 6 3 销量 9 A3 4 A2 7 A1 产量 B4 B3 B2 B1 3 11 3 10 1 9 2 7 4 10 5 8 5 表上作业法 6 5 6 3 销量行差额列差额 9 5 10 4 7 4 8 2 9 1 7 10 3 11 3 产量单位销地运价产地 7 1 3 5 2 7 5 × × × 3 × 表上作业法 6 5 6 3 销量行差额列差额 9 5 10 4 7 4 8 2 9 1 7 10 3 11 3 产量单位销地运价产地 1 1 3 5 1 5 × × × 3 × 6 3 1 × × 2 该方案的总运费: (1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元表上作业法 48 22 10 16 产量 14 12 14 8 销量 3 1 5 2 列差额 1 6 11 5 8 A3 1 9 3 10 2 A2 0 11 4 12 4 A1 行差额 B4 B3 B2 B1 销地产地 14 所以，初始基可行解为：……目标函数值Z＝244 例某运输资料如下表所示：表上作业法 48 22 10 16 产量 14 12 14 8 销量 3 1 2 列差额 1 6 11 5 8 A3 1 9 3 10 2 A2 0 11 4 12 4 A1 行差额 B4 B3 B2 B1 销地产地 14 所以，初始基可行解为：……目标函数值Z＝244 8 例某运输资料如下表所示：表上作业法 48 22 10 16 产量 14 12 14 8 销量 3 1 2 列差额 1 6 11 5 8 A3 1 9 3 10 2 A2 0 11 4 12 4 A1 行差额 B4 B3 B2 B1 销地产地 14 所以，初始基可行解为：……目标函数值Z＝244 8 8 例某运输资料如下表所示：表上作业法 48 22 10 16 产量 14 12 14 8 销量 3 1 列差额 6 11 5 8 A3 1 9 3 10 2 A2 0 11 4 12 4 A1 行差额 B4 B3 B2 B1 销地产地 14 所以，初始基可行解为：……目标函数值Z＝244 8 8 例某运输资料如下表所示： 12 表上作业法 48 22 10 16 产量 14 12 14 8 销量 3 列差额 6 11 5 8 A3 1 9 3 10 2 A2 0 11 4 12 4 A1 行差额 B4 B3 B2 B1 销地产地 14 所以，初始基可行解为：……目标函数值Z＝244 8 8 例某运输资料如下表所示： 12 2 4 表上作业法练习 13 12 13 22 销量 19 6 10 9 5 A3 27 7 2 4 8 A2 14 3 5 7 6 A1 产量 B4 B3 B2 B1 销地产地 1 2 13 12 13 19 表上作业法 2、最优解的判别（检验数的求法）求检验数的方法有两种：闭回路法对偶变量法（位势法）（1）闭合回路法： σij≥0 （因为目标函数要求最小化）表格中有调运量的地方为基变量，空格处为非基变量。基变量的检验数σij＝0，非基变量的检验数σij≥0。 σij< 0 表示运费减少， σij> 0 表示运费增加。闭回路：从空格出发顺时针(或逆时针)画水平(或垂直)直线，遇到填有运量的方格可转90°，然后继续前进，直到到达出发的空格所形成的闭合回路。调运方案的任意空格存在唯一闭回路。表上作业法注：1.每一空格有且仅有一条闭回路； 2.如果某数字格有闭回路，则此解不是可行解。若令则 —运费的增量分析：表上作业法以最小元素法的初始解为例。假设产地A1供应1个单位的物品给销地B1。则解的变化和目标函数的变化如何。 48 14 12 14 8 销量 8 14 22 6 11 5 8 A3 2 8 10 9 3 10 2 A2 6 10 16 11 4 12 4 A1 产量 B4 B3 B2 B1 销地产地表上作业法要保证产销平衡，则称为闭回路 48 14 12 14 8 销量 8 14 22 6 11 5 8 A3 2 8 10 9 3 10 2 A2 6 10 16 11 4 12 4 A1 产量 B4 B3 B2 B1 销地产地 1 表上作业法 48 14 12 14 8 销量 8 14 22 6 11 5 8 A3 2 8 10 9 3 10 2 A2 6 10 16 11 4 12 4 A1 产量 B4 B3 B2 B1 销地产地 1 2 表上作业法 48 14 12 14 8 销量 8 14 22 6 11 5 8 A3 2 8 10 9 3 10 2 A2 6 10 16 11 4 12 4 A1 产量 B4 B3 B2 B1 销地产地 1 2 1 表上作业法 48 14 12 14 8 销量 8 14 22 6 11 5 8 A3 2 8 10 9 3 10 2 A2 6 10 16 11 4 12 4 A1 产量 B4 B3 B2 B1 销地产地 10 2 1 1 表上作业法 48 14 12 14 8 销量 8 14 22 6 11 5 8 A3 2 8 10 9 3 10 2 A2 6 10 16 11 4 12 4 A1 产量 B4 B3 B2 B1 销地产地 1 2 1 12 10 表上作业法 48 14 12 14 8 销量 8 14 22 6 11 5 8 A3 2 8 10 9 3 10 2 A2 6 10 16 11 4 12 4 A1 产量 B4 B3 B2 B1 销地产地 1 2 1 -1 12 10 检验数中有负数，说明原方案不是最优解。表上作业法练习 13 12 13 22 销量 13 6 19 6 10 9 5 A3 6 13 8 27 7 2 4 8 A2 14 14 3 5 7 6 A1 产量 B4 B3 B2 B1 销地产地 5 5 7 9 -3 -11 ui vj m个 n个（2）对偶变量法（位势法）表上作业法设其对偶变量为： ui‚vj无约束（i=1,2, …,m;j=1,2, …,n) 标准型运输问题的对偶问题模型为：表上作业法则运输问题变量xij的检验数为：表上作业法用位势法对初始方案进行最优性检验的方法： 1）在给定初始解的表上增加一行和一列，在列中填入ui，在行中填入vj。 2）令u1＝0，再按cij-(ui+vj)=0（基变量的cij求出其余的ui与vj。 3）由i j=Ci j -（ui+vj），求出非基变量的检验数。表上作业法 vj A3 A2 A1 ui B4 B3 B2 B1 3 11 3 10 1 9 2 7 4 10 5 8 u1 u2 u3 v3 v4 v1 v2 注意：基变量的检验数i j=Ci j -（ui+vj）=0 4 3 6 3 1 3 表上作业法 vj A3 A2 A1 ui B4 B3 B2 B1 3 11 3 10 1 9 2 7 4 10 5 8 0 -1 -5 3 10 2 9 令u1=0 u1+v3=3 u1+ v4 =10 u2+ v3=2 u2+v1=1 u3+v2=4 u3+ v4=5 4 3 6 3 1 3 表上作业法 2 10 3 9 vj -5 A3 -1 A2 0 A1 ui B4 B3 B2 B1 4 3 6 3 1 3 （1）（2）（1）（-1）（10）（12）当存在非基变量的检验数ij ≥0，说明现行方案为最优方案，否则目标成本还可以进一步减小。注意：非基变量的检验数i j=ci j -（ui+vj） 11=c11 -（u1+v1）=3-(0+2)=1 31=c31 -（u3+v1）=7-(2-5)=10 24=c24 -（u2+v4）=8-(10-1)=-1 22=c22 -（u2+v2）=9-(9-1)=1 12=c12 -（u1+v2）=11-(0+9)=2 33=c33 -（u3+v3）=10-(3-5)=12 3 11 3 10 1 9 2 7 4 10 5 8 表上作业法 3、解的改进 ——闭合回路调整法（原理同单纯形法一样）当在表中空格处出现负检验数时，表明未得最优解。若有两个或两个以上的负检验数时，一般选用其中最小的负检验数，以它对应的空格为调入格，即以它对应的非基变量为换入变量。做一闭合回路。 ( 1 ) 确定换入基的变量：当存在非基变量的检验数kl < 0 且kl =min{ij}时，以Xkl为换入变量，找出它在运输表中的闭合回路。接上例： pq ij j , i ) ( min σ σ = < 0 Xpq=X24 为换入变量解的改进的具体步骤：表上作业法 2 10 3 9 vj -5 A3 -1 A2 0 A1 ui B4 B3 B2 B1 4 3 6 3 1 3 3 11 3 10 1 9 2 7 4 10 5 8 （1）（2）（1）（-1）（10）（12） ( 2 ) 顶点编号：以空格(Ak,Bl)(或进基变量xik）为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的顶点依次编号。 1 3 2 4 表上作业法 2 10 3 9 vj -5 A3 -1 A2 0 A1 ui B4 B3 B2 B1 4 3 6 3 1 3 3 11 3 10 1 9 2 7 4 10 5 8 （1）（2）（1）（-1）（10）（12） ( 2 ) 顶点编号：以空格(Ak,Bl)(或进基变量xik）为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的顶点依次编号。 1 3 2 4 换出变量X23 表上作业法 ( 3 ) 确定换出基的变量：在该闭回路上，从所有偶数号格点的调运量中选出最小值的顶点（格子），以该格子中的变量为换出变量。 ( 4 ) 确定新的运输方案：以换出变量的运输量为调整量θ ，将该闭回路上所有奇数号格的调运量加上调整量 θ ，所有偶数号格的调运量减去 θ ，其余的不变，这样就得到一个新的调运方案。该运输方案的总运费比原运输方案减少，改变量等于换出变量的检验数。 ( 5 )然后，再对得到的新解进行最优性检验，加不是最优解，就重复以上步骤继续进行调整，一直到得出最优解为止。表上作业法 2 10 3 9 vj -5 A3 -1 A2 0 A1 ui B4 B3 B2 B1 3 6 3 1 (＋1) (＋1) (－1) (－1) 3 11 3 10 1 9 2 7 4 10 5 8 4 3 表上作业法 3 10 3 9 vj -5 A3 -2 A2 0 A1 ui B4 B3 B2 B1 5 3 6 3 1 2 3 11 3 10 1 9 2 7 4 10 5 8 重新求所有非基变量的检验数：表上作业法 3 10 3 9 vj -5 A3 -2 A2 0 A1 ui B4 B3 B2 B1 5 3 6 3 1 2 （2）（2）（1）（12）（9）（0）当所有非基变量的检验数均非负时，则当前调运方案即为最优方案，如表此时最小总运费： Z =(1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元 3 11 3 10 1 9 2 7 4 10 5 8 表上作业法表上作业法的计算步骤：分析实际问题列出产销平衡表及单位运价表确定初始调运方案（最小元素法或Vogel法）求检验数（位势法）所有检验数≥0 找出绝对值最大的负检验数，用闭合回路调整，得到新的调运方案得到最优方案，算出总运价表上作业法表上作业法计算中的问题：（1）若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取σij<0中最小者对应的变量为换入变量。（2）无穷多最优解产销平衡的运输问题必定存最优解。如果非基变量的σij＝0，则该问题有无穷多最优解。如上例： σ11的检验数是 0，经过调整，可得到另一个最优解。表上作业法 ⑵ 退化解： ※ 表格中一般要有(m+n-1)个数字格。但有时在分配运量时则需要同时划去一行和一列，这时需要补一个0，以保证有(m+n-1)个数字格作为基变量。一般可在划去的行和列的任意空格处加一个0即可。 ※ 利用进基变量的闭回路对解进行调整时，标有负号的最小运量（超过2个最小值）作为调整量θ，选择任意一个最小运量对应的基变量作为出基变量，并打上“×”以示作为非基变量。表上作业法 14 12 14 8 销量 22 A3 10 A2 16 A1 产量 B4 B3 B2 B1 销地产地 12 4 11 4 8 3 10 2 9 5 11 6 (0) (2) (9) (2) (1) (12) 8 12 4 2 8 14 如下例中σ11检验数是 0，经过调整，可得到另一个最优解。表上作业法 20 6 5 6 3 销量 9 A3 4 A2 7 A1 产量 B4 B3 B2 B1 销地产地 11 4 4 3 1 3 7 7 8 2 10 6 × 3 × 4 1 6 × 0 6 × × × 在x12、x22、x33、x34中任选一个变量作为基变量，例如选x34 例：用最小元素法求初始可行解运输问题的进一步讨论一、产销不平衡的运输问题当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。当产大于销时，即：数学模型为：运输问题的进一步讨论由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，假设该仓库为一个虚拟销地Bn+1， bn+1作为一个虚设销地Bn+1的销量(即库存量)。各产地Ai到Bn+1的运价为零，即Ci,n+1=0,（i=1，…，m）。则平衡问题的数学模型为：具体求解时,只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可运输问题的进一步讨论当销大于产时，即：数学模型为：由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1，产量为：运输问题的进一步讨论销大于产化为平衡问题的数学模型为：具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1即可。运输问题的进一步讨论例求下列表中极小化运输问题的最优解。 180 160 45 35 60 20 bj 50 11 10 8 4 A4 30 2 4 6 3 A3 40 8 7 4 -- A2 60 3 2 9 5 A1 ai B4 B3 B2 B1 因为有：运输问题的进一步讨论所以是一个产大于销的运输问题。表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180-160=20，Ci5=0，i=1,2,3,4，表的右边增添一列，得到新的运价表。 180 20 45 35 60 20 bj 50 0 11 10 8 4 A4 30 0 2 4 6 3 A3 40 0 8 7 4 M A2 60 0 3 2 9 5 A1 ai B5 B4 B3 B2 B1 运输问题的进一步讨论下表为计算结果。可看出：产地A4还有20个单位没有运出。 180 20 45 35 60 20 Bj 50 20 10 20 A4 30 20 10 A3 40 40 A2 60 25 35 A1 Ai B5 B4 B3 B2 B1 用前面的方法求运输方案：运输问题的进一步讨论例某市有三个造纸厂A1，A2，A3，其纸的产量分别为8，5和9个单位，有4个集中用户B1，B2，B3，B4，其需用量分别为4，3，5和6个单位。由各造纸厂到各用户的单位运价如表3—14所示，请确定总运费最少的调运方案。 6 5 3 4 销量 9 5 1 7 6 A3 5 9 5 2 11 A2 8 4 3 12 3 A1 产量 B4 B3 B2 B1 销地产地运输问题的进一步讨论解：由于总产量22大于总销量18，故本问题是个产销不平衡运输问题。增加一假想销地B5，用表上作业法求解。 4 B5(贮存) 0 0 0 6 5 3 4 销量 9 5 1 7 6 A3 5 9 5 2 11 A2 8 4 3 12 3 A1 产量 B4 B3 B2 B1 销地产地运输问题的进一步讨论 -4 -8 4 4 B5(贮存) 0 0 0 6 5 3 4 销量 4 5 9 -2 9 5 1 7 6 A3 2 0 3 0 5 9 5 2 11 A2 3 6 18 4 8 4 3 12 3 A1 产量 B4 B3 B2 B1 销地产地应用问题举例例由n个地区需要某种物资，需要量分别不少于bj（j=1,…,n）。这些物资均由某公司分设在m个地区的工厂供应，各工厂的产量分别不大于ai（i=1,…,m）,已知从第i个地区至第j个需求地区单位物资的运价为cij，又，试写出其对偶问题，并解释对偶变量的经济意义。由于在变量相等的情况下，表上作业法的计算远比单纯形法简单得多。所以在解决实际问题时，人们常常尽可能把某些线性规划的问题化为运输问题的数学模型。应用问题举例解：由题给出的条件，数学模型可写为: 对偶问题可写为：应用问题举例对偶变量ui的经济意义为在i产地单位物资的价格，vj的经济意义为在第j销地单位物资的价格。对偶问题的经济意义为：如该公司欲自己将该种物资运至各地销售，其差价不能超过两地之间的运价（否则买主将在i地购买自己运至j地），在此条件下，希望获利为最大。应用问题举例已知资料如下表所示，问如何供电能使总的输电费用为最小？ 150 100 250 500 需电量 B4 B3 B2 B1 城市 100 200 700 发电量 A3 A2 A1 发电厂电力供需表 4 3 6 5 A3 2 1 3 4 A2 3 2 5 10 A1 B4 B3 B2 B1 单位输电费用练习： 400 A3 100 100 A2 50 250 400 A1 B4 B3 B2 B1 初始方案单位输电费用电力供需表应用问题举例 150 100 250 500 需电量 B4 B3 B2 B1 城市 100 200 700 发电量 A3 A2 A1 发电厂 4 3 6 5 A3 2 1 3 4 A2 3 2 5 10 A1 B4 B3 B2 B1 5 A3 2 1 A2 3 5 10 A1 B4 B3 B2 B1 3 2 5 10 vj -5 -2 -3 0 5 A3 -1 2 1 4 9 A2 0 3 2 5 10 A1 ui B4 B3 B2 B1 vj 6 6 6 0 A3 0 0 -1 -5 A2 0 0 0 0 A1 ui B4 B3 B2 B1 σij - (ui+vj) = cij (ui+vj) 400 A3 100 100 A2 50 250 400 A1 B4 B3 B2 B1 应用问题举例 100 A3 100 100 A2 50 250 400 A1 B4 B3 B2 B1 100 A3 100 100 A2 150 250 300 A1 B4 B3 B2 B1 5 A3 1 4 A2 3 5 10 A1 B4 B3 B2 B1 成本表 3 7 5 10 vj -5 -2 2 0 5 A3 -6 -3 1 -1 4 A2 0 3 7 5 10 A1 ui B4 B3 B2 B1 (ui+vj) 调运方案应用问题举例 vj 6 1 6 0 A3 5 0 4 0 A2 0 -5 0 0 A1 ui B4 B3 B2 B1 σij =cij-(ui+vj) 100 A3 100 100 A2 150 250 300 A1 B4 B3 B2 B1 100 A3 200 A2 150 100 250 200 A1 B4 B3 B2 B1 5 A3 4 A2 3 2 5 10 A1 B4 B3 B2 B1 成本表调运方案应用问题举例 3 2 5 10 vj -5 -2 -3 0 5 A3 -6 -3 -4 -1 4 A2 0 3 2 5 10 A1 ui B4 B3 B2 B1 (ui+vj) vj 6 6 6 0 A3 5 5 4 0 A2 0 0 0 0 A1 ui B4 B3 B2 B1 100 A3 200 A2 150 100 250 200 A1 B4 B3 B2 B1 C=5200 σij =cij-(ui+vj) 应用问题举例 75 8 7 7 9 A3 60 4 6 B4 200 55 45 40 销量 70 6 3 5 A2 55 2 6 3 A1 产量 B3 B2 B1 试用表上作业法求最优解应用问题举例 200 60 55 45 40 销量 75 35 40 A3 70 25 45 A2 55 15 40 A1 产量 B4 B3 B2 B1 最小总费用为945。应用问题举例 Chapter4 目标规划 (Goal Programming ) 目标规划问题及其数学模型目标规划的图解法目标规划的单纯形法目标规划应用举例本章主要内容：目标规划问题及其数学模型 1、问题的提出：目标规划是在线性规划的基础上，为适应经济管理多目标决策的需要而由线性规划逐步发展起来的一个分支。由于现代化企业内专业分工越来越细，组织机构日益复杂，为了统一协调企业各部门围绕一个整体的目标工作，产生了目标管理这种先进的管理技术。目标规划是实行目标管理的有效工具，它根据企业制定的经营目标以及这些目标的轻重缓急次序，考虑现有资源情况，分析如何达到规定目标或从总体上离规定目标的差距为最小。目标规划问题及其数学模型例某企业计划生产甲，乙两种产品，这些产品分别要在A,B,C,D四种不同设备上加工。按工艺文件规定，如表所示。 3 2 单件利润 12 16 8 12 最大负荷 4 0 2 2 乙 0 4 1 1 甲 D C B A 问该企业应如何安排计划，使得计划期内的总利润收入为最大？目标规划问题及其数学模型解：设甲、乙产品的产量分别为x1，x2，建立线性规划模型：其最优解为x1＝4，x2＝2，z＊＝14元目标规划问题及其数学模型但企业的经营目标不仅仅是利润，而且要考虑多个方面，如：力求使利润指标不低于12元；考虑到市场需求，甲、乙两种产品的生产量需保持1:1的比例； C和D为贵重设备，严格禁止超时使用；设备B必要时可以加班，但加班时间要控制；设备A即要求充分利用，又尽可能不加班。要考虑上述多方面的目标，需要借助目标规划的方法。目标规划问题及其数学模型线性规划模型存在的局限性： 1）要求问题的解必须满足全部约束条件，实际问题中并非所有约束都需要严格满足。 2）只能处理单目标的优化问题。实际问题中，目标和约束可以相互转化。 3）线性规划中各个约束条件都处于同等重要地位，但现实问题中，各目标的重要性即有层次上的差别，同一层次中又可以有权重上的区分。 4）线性规划寻求最优解，但很多实际问题中只需找出满意解就可以。目标规划问题及其数学模型目标规划怎样解决上述线性规划模型建模中的局限性？ 1. 设置偏差变量，用来表明实际值同目标值之间的差异偏差变量用下列符号表示： d+——超出目标的偏差，称正偏差变量 d-——未达到目标的偏差，称负偏差变量正负偏差变量两者必有一个为0。当实际值超出目标值时： d+>0, d-=0; 当实际值未达到目标值时： d+=0, d->0; 当实际值同目标值恰好一致时： d+=0, d-=0; 故恒有d+×d-=0 目标规划问题及其数学模型 2. 统一处理目标和约束对有严格限制的资源使用建立系统约束，数学形式同线性规划中的约束条件。如C和D设备的使用限制。对不严格限制的约束，连同原线性规划建模时的目标，均通过目标约束来表达。 1）例如要求甲、乙两种产品保持1:1的比例，系统约束表达为： x1=x2。由于这个比例允许有偏差，当x1<x2时，出现负偏差d-，即： x1+d- =x2或x1－x2+d- =0 当x1>x2时，出现正偏差d+，即： x1-d+ =x2或x1－x2-d+ =0 目标规划问题及其数学模型 ∵正负偏差不可能同时出现，故总有： x1－x2+d--d+ =0 若希望甲的产量不低于乙的产量，即不希望d->0,用目标约束可表为: 若希望甲的产量低于乙的产量，即不希望d＋>0,用目标约束可表为: 若希望甲的产量恰好等于乙的产量，即不希望d＋>0,也不希望d->0用目标约束可表为: 目标规划问题及其数学模型 3）设备B必要时可加班及加班时间要控制，目标约束表示为： 2）力求使利润指标不低于12元，目标约束表示为： 4）设备A既要求充分利用，又尽可能不加班，目标约束表示为：目标规划问题及其数学模型 3. 目标的优先级与权系数在一个目标规划的模型中，为达到某一目标可牺牲其他一些目标，称这些目标是属于不同层次的优先级。优先级层次的高低可分别通过优先因子P1,P2,…表示。对于同一层次优先级的不同目标，按其重要程度可分别乘上不同的权系数。权系数是一个个具体数字，乘上的权系数越大，表明该目标越重要。现假定：第1优先级P1——企业利润；第2优先级P2——甲乙产品的产量保持1:1的比例第3优先级P3——设备A,B尽量不超负荷工作。其中设备A的重要性比设备B大三倍。目标规划问题及其数学模型上述目标规划模型可以表示为：目标规划问题及其数学模型 5. 目标规划的目标函数由各目标约束的正、负偏差变量及相应的优先因子和权系数构成。从决策者的要求来分析，总希望得到的结果与规定的指标值之间的偏差量愈小愈好。由此可构造一个使总偏差量为最小化的目标函数，min Z = f（d +，d -）其基本形式有三种： 4. 满意解对于这种解来说，前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。目标规划问题及其数学模型（1）要求恰好达到目标值，即正、负偏差变量都要尽可能地小。构造的目标函数是 min Z = f（ d ++ d - ）（2）要求不超过目标值，但允许达不到目标值，即只有使正偏差量要尽可能地小（实现最少或为零） min Z = f（ d +）（3）要求超过目标值，即超过量不限。要求超额完成规定目标，要实现负偏差量为零或为最小 min Z = f（ d -）目标规划问题及其数学模型建模的步骤 1、根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束； 4、对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数。 3、给各目标赋予相应的优先因子 Pi（i=…L）。 2、可根据决策者的需要，将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可。目标规划问题及其数学模型目标规划数学模型的一般形式达成函数目标约束其中：gk为第k个目标约束的预期目标值，和为pl 优先因子对应各目标的权系数。目标规划问题及其数学模型用目标规划求解问题的过程：明确问题，列出目标的优先级和权系数构造目标规划模型求出满意解满意否？分析各项目标完成情况据此制定出决策方案 N Y 目标规划问题及其数学模型例某厂生产Ⅰ、Ⅱ两种产品，有关数据如表所示。试求获利最大的生产方案？ 10 8 单件利润 10 2 1 设备(台时) 11 1 2 原材料拥有量 Ⅱ Ⅰ 在此基础上考虑： 1、产品Ⅱ的产量不低于产品Ⅰ的产量； 2、充分利用设备有效台时，不加班； 3、利润不小于 56 元。解: 分析第二目标P2 ：第三目标P3 ：第一目标P1: 目标规划问题及其数学模型 10 8 单件利润 10 2 1 设备(台时) 11 1 2 原材料拥有量 Ⅱ Ⅰ 1、产品Ⅱ的产量不低于产品Ⅰ的产量； 2、充分利用设备有效台时，不加班； 3、利润不小于 56 元。 2x1 +x2 ≤11 （在绝对约束基础上进行目标规划） x1 - x2 + d1- - d1+ = 0 　　　　　　　(要求： d1+ 尽可能小，最好是0才能满足 ≤ ) x1 +2x2 + d2- - d2+ =10 　　　　　　（要求：d2- 和 d2+ 都尽可能小，最好等于0） 8x1 +10x2 + d3- - d3+ =56 （要求：d3- 尽可能小，最好是0才能满足≥） x1 , x2 , di- ,di+ ≥0 目标规划问题及其数学模型规划模型：目标规划的图解法目标规划的图解法：适用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。图解法解题步骤： 1. 将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏差变量）的直线方程分别标示于坐标平面上。 2. 确定系统约束的可行域。 3. 在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向目标规划的图解法 3. 求满足最高优先等级目标的解 4. 转到下一个优先等级的目标，再不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解 5. 重复4，直到所有优先等级的目标都已审查完毕为止 6. 确定最优解和满意解。目标规划的图解分析法例用图解法求解下列目标规划问题目标规划的图解分析法 (a) (b) (c) (d ) x2 x1 (e) (f) d1- d1+ d2+ d2- d3- d3+ d4- d4+ 满意解(3,3) 0 4 6 8 3 4 6 2 2 目标规划的图解分析法 x1 x2 (a) (b) d1+ d1- (c) d2- d2+ (d) d3- d3+ G D 满意解是线段GD上任意点其中G点X＝(2,4),D点X＝(10/3,10/3) 0 10 5 11 2,4 10/3,10/3 5 10 7 例目标规划的图解分析法 O x1 x2 20 40 60 50 20 40 60 50 a b d1- d1+ d2- d2+ c d d3- d3+ d4- d4+ (24,26) 满意解X=(24，26) 例目标规划的单纯形法（一）、一般形式： σmn+2m σm2 σm1 αK PK σ2n+2m σ22 σ21 α2 P2 σ1n+2m σ12 σ11 α1 P1 σkj emn+2m em2 em1 bom xjm cjm e2n+2m e22 e21 bo2 xj2 cj2 e1n+2m e12 e11 bo1 xj1 cj1 xn+2m x2 x1 b XB CB cn+2m c2 c1 Cj 目标规划的单纯形法 1．目标函数：min 2．最优性判断：σj ≥0 时为最优 3．非基变量检验数的特殊性：含有不同等级的优先因子 P1, P2 ,…, Pk ; 又因 P1 >> P2 >> P3 >> … >> Pk ，所以检验数的正负首先取决于P1 的系数的正负，若P1 的系数为0，再由P2 的系数的正负决定检验数的正负，然后依次类推。一、特点目标规划的单纯形法 (1) 建立初始单纯形表．在表中将检验数行按优先因子个数分别列成K行。初始的检验数需根据初始可行解计算出来，方法同基本单纯形法。当不含绝对约束时，di- （i=1,2,… ,K）构成了一组基本可行解，这时只需利用相应单位向量把各级目标行中对应di- （i=1,2,… ,K）的量消成0即可得到初始单纯形表。置k ＝ 1；解目标规划问题的单纯形法的计算步骤 (2) 检查当前第k行中是否存在大于0，且对应的前k-1行的同列检验数为零的检验数。若有取其中最大者对应的变量为换入变量，转(3)。若无这样的检验数，则转(5)；目标规划的单纯形法 (5) 当k ＝ K 时，计算结束。表中的解即为满意解。否则置k = k+1，返回（2）。 (4) 按单纯形法进行基变换运算，建立新的单纯形表，（注意：要对所有的行进行转轴运算）返回(2)； (3) 按单纯形法中的最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量，转（4）；目标规划的单纯形法例：用单纯形法求解下列目标规划问题解：将上述目标规划问题化为标准型：目标规划的单纯形法建立初始单纯形表：目标规划的单纯形法 θ= min｛－，10/2，56/10，11/1｝= 5 进基变量x2 0 1 0 0 0 0 0 －10 －8 P3 0 0 0 2 0 0 0 －2 －1 P2 0 0 0 0 0 1 0 0 0 P1 σj 1 0 0 0 0 0 0 1 2 11 x3 0 0 －1 1 0 0 0 0 10 8 56 P3 0 0 0 －1 1 0 0 2 1 10 P2 0 0 0 0 0 －1 1 －1 1 0 0 x3 x2 x1 b XB CB 0 0 P3 P2 P2 P1 0 0 0 Cj 换出变量d2- 目标规划的单纯形法 0 1 0 -5 5 0 0 0 －3 P3 0 0 0 1 1 0 0 0 0 P2 0 0 0 0 0 1 0 0 0 P1 σj 1 0 0 1/2 -1/2 0 0 0 3/2 6 x3 0 0 －1 1 5 -5 0 0 0 3 6 P3 0 0 0 -1/2 1/2 0 0 1 1/2 5 x2 0 0 0 0 -1/2 1/2 －1 1 0 3/2 5 0 x3 x2 x1 b XB CB 0 0 P3 P2 P2 P1 0 0 0 Cj θ= min｛10/3,10,6/3,12/3｝= 2, 进基变量x1 换出变量d3- 目标规划的单纯形法 0 0 1 0 0 0 0 0 0 P3 0 0 0 1 1 0 0 0 0 P2 0 0 0 0 0 1 0 0 0 P1 σj 1 1/2 -1/2 -2 2 0 0 0 0 3 x3 0 0 -1/3 1/3 5/3 -5/3 0 0 0 1 2 x1 0 0 1/6 -1/6 -4/3 4/3 0 0 1 0 4 x2 0 0 1/2 -1/2 -3 3 －1 1 0 0 2 0 x3 x2 x1 b XB CB 0 0 P3 P2 P2 P1 0 0 0 Cj 最优解为x1＝2， x2 ＝4。但非基变量d3+的检验数为零，故此题有无穷多最优解。目标规划的单纯形法 0 0 1 0 0 0 0 0 0 P3 0 0 0 1 1 0 0 0 0 P2 0 0 0 0 0 1 0 0 0 P1 σj 1 1/2 -1/2 -2 2 0 0 0 0 3 x3 0 0 -1/3 1/3 5/3 -5/3 0 0 0 1 2 x1 0 0 1/6 -1/6 -4/3 4/3 0 0 1 0 4 x2 0 0 1/2 -1/2 -3 3 －1 1 0 0 2 0 x3 x2 x1 b XB CB 0 0 P3 P2 P2 P1 0 0 0 Cj θ= min｛4 , 24 ,－, 6｝= 4 进基变量d3+ 换出变量d1- 目标规划的单纯形法 0 0 1 0 0 0 0 0 0 P3 0 0 0 1 1 0 0 0 0 P2 0 0 0 0 0 1 0 0 0 P1 σj 1 0 0 1 -1 －1 -1 0 0 1 x3 0 0 0 0 -1/3 1/3 -2/3 2/3 0 1 10/3 x1 0 0 0 0 -1/3 1/3 1/3 -1/3 1 0 10/3 x2 0 0 1 -1 -6 6 -2 2 0 0 4 0 x3 x2 x1 b XB CB 0 0 P3 P2 P2 P1 0 0 0 Cj 最优解为x1＝10/3， x2 ＝10/3。目标规划的单纯形法例、用单纯形法求解下列目标规划问题目标规划的单纯形法 P2 0 0 P3 0 0 P1 0 0 Cj 0 0 0 0 1 0 0 0 0 0 P3 1 0 0 0 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 －12 －30 P1 σj －1 1 0 0 0 0 0 0 1 0 100 0 0 0 －1 1 0 0 0 0 0 1 60 0 0 0 0 0 －1 1 0 0 1 2 140 0 0 0 0 0 0 0 －1 1 12 30 2500 P1 x2 x1 b XB CB θ= min｛2500/30,140/2,60/1, -｝= 60, 进基变量x1 换出变量d3- 目标规划的单纯形法 0 0 0 0 1 0 0 0 0 0 P3 1 0 0 0 0 0 0 0 0 P2 0 0 －30 30 0 0 1 0 －12 0 P1 σj －1 1 0 0 0 0 0 0 1 0 100 0 0 0 －1 1 0 0 0 0 0 1 60 x1 0 0 0 2 －2 －1 1 0 0 1 0 20 0 0 0 30 －30 0 0 －1 1 12 0 700 P1 x2 x1 b XB CB P2 0 0 P3 0 0 P1 0 0 Cj θ= min｛700/30,20/2,－, －｝=10 进基变量d3+ 换出变量d2- 目标规划的单纯形法 0 0 0 0 1 0 0 0 0 0 P3 1 0 0 5/2 5/4 -5/4 0 0 -5/4 0 P2 0 0 0 0 -15 15 1 0 3 0 P1 σj -1 1 0 0 0 0 0 0 1 0 100 0 0 0 0 0 -1/2 1/2 0 0 1/2 1 70 x1 0 0 0 1 -1 -1/2 1/2 0 0 1/2 0 10 0 0 0 0 15 -15 -1 1 -3 0 400 P1 x2 x1 b XB CB P2 0 0 P3 0 0 P1 0 0 Cj θ= min｛400/15,－,－, －｝=10 进基变量d2+ 换出变量d1- 目标规划的单纯形法 0 0 0 0 0 1 1/15 -1/15 1/5 0 P3 1 0 0 2/5 0 0 1/12 -1/12 -1 0 P2 0 0 0 0 0 0 0 1 0 0 P1 σj －1 1 0 0 0 0 0 0 1 0 100 0 0 0 0 0 0 0 -1/30 1/30 2/5 1 250/3 x1 0 0 0 1 -1 0 0 -1/30 1/30 2/5 0 70/3 0 0 0 0 1 -1 -1/15 1/15 -1/5 0 80/3 P3 x2 x1 b XB CB P2 0 0 P3 0 0 P1 0 0 Cj θ= min｛－,350/6,1250/6,100/1｝=75 进基变量x2 换出变量d3+ 目标规划的单纯形法 0 0 -1/2 1/2 0 1 1/12 -1/12 0 0 P3 1 0 5/2 0 0 0 0 0 0 0 P2 0 0 0 0 0 0 0 1 0 0 P1 σj －1 1 -5/2 5/2 0 0 1/12 -1/12 0 0 125/3 0 0 0 1 -1 0 0 0 0 0 1 60 x1 0 0 0 5/2 -5/2 0 0 -1/12 1/12 1 0 175/3 x2 0 0 0 1/2 -1/2 1 -1 -1/12 1/12 0 0 115/3 P3 x2 x1 b XB CB P2 0 0 P3 0 0 P1 0 0 Cj P3 优先等级目标没有实现，但已无法改进，得到满意解 x1 ＝60， x2 ＝175/3， d2+＝115/3，d4-＝125/3 目标规划应用举例例已知一个生产计划的线性规划模型如下，其中目标函数为总利润，x1,x2 为产品A、B产量。现有下列目标： 1. 要求总利润必须超过 2500 元； 2. 考虑产品受市场影响，为避免积压，A、B的生产量不超过 60 件和 100 件； 3. 由于甲资源供应比较紧张，不要超过现有量140。试建立目标规划模型，并用图解法求解。目标规划应用举例解：以产品 A,B 的单件利润比 :1 为权系数，模型如下：目标规划应用举例 0 x2 0 ⑴ x1 140 120 100 80 60 40 20 20 40 60 80 100 ⑵ ⑶ ⑷ A B C D C(60 ,)为所求的满意解。 (24,26) 目标规划应用举例例某厂生产A、B、C三种产品，装配工作在同一生产线上完成，三种产品时的工时消耗分别为6、8、10小时，生产线每月正常工作时间为200小时；三种产品销售后，每台可获利分别为500、650和800元；每月销售量预计为12、10和6台。该厂经营目标如下：1、利润指标为每月16000元，争取超额完成；2、充分利用现有生产能力；3、可以适当加班，但加班时间不得超过24小时；4、产量以预计销售量为准。试建立目标规划模型。目标规划应用举例已知条件如表所示 450 300 利润（元/台） 150 70 6 2 4 3 Ⅰ（小时/台） Ⅱ（小时/台） B A 每周最大加工能力型号工序如果工厂经营目标的期望值和优先等级如下： p1: 每周总利润不得低于10000元； p2: 因合同要求，A型机每周至少生产10台，B型机每周至少生产15台； p3: 希望工序Ⅰ的每周生产时间正好为150小时，工序Ⅱ的生产时间最好用足，甚至可适当加班。目标规划应用举例这个问题的目标规划模型为：目标规划问题及其数学模型小结最满意最优解目标约束、绝对约束绝对约束约束条件 xi xs xa d xi, xs xa 变量 min , 偏差变量系数≥0 min , max 系数可正负目标函数目标规划GP 线性规划LP Chapter5 整数规划 ( Integer Programming ) 整数规划的特点及应用分支定界法 0－1 整数规划指派问题本章主要内容：在很多场合，我们建立最优化模型时，实际问题要求决策变量只能取整数值而非连续取值。此时，这类最优化模型就称为整数规划（离散最优化）模型。整数规划的求解往往比线性规划求解困难得多，而且，一般来说不能简单地将相应的线性规划的解取整来获得。整数规划的特点及应用整数规划（简称：IP）要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为整数线性规划。整数线性规划数学模型的一般形式：整数规划的特点及应用整数线性规划问题的种类：纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划。混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。 0-1型整数线性规划：决策变量只能取值0或1的整数线性规划。整数规划的特点及应用整数规划的典型例子例工厂A1和A2生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij，见下表： 150 300 400 350 年需求量 200 5 2 5 4 A4 200 2 1 6 7 A3 600 7 5 3 8 A2 400 4 3 9 2 A1 年生产能力 B4 B3 B2 B1 工厂A3或A4开工后，每年的生产费用估计分别为1200万或1500万元。现要决定应该建设工厂A3还是A4，才能使今后每年的总费用最少。整数规划的特点及应用解：这是一个物资运输问题，特点是事先不能确定应该建A3还是A4中哪一个，因而不知道新厂投产后的实际生产物资。为此，引入0-1变量：再设xij为由Ai运往Bj的物资数量，单位为千吨；z表示总费用，单位万元。则该规划问题的数学模型可以表示为：整数规划的特点及应用混合整数规划问题整数规划的特点及应用例现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj（j＝1,2,..,n），此外由于种种原因，有三个附加条件：若选择项目1，就必须同时选择项目2。反之不一定; 项目3和4中至少选择一个；项目5,6,7中恰好选择2个。应该怎样选择投资项目，才能使总预期收益最大。整数规划的特点及应用解：对每个投资项目都有被选择和不被选择两种可能，因此分别用0和1表示，令xj表示第j个项目的决策选择，记为：投资问题可以表示为：整数规划的特点及应用例指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。 88 80 90 86 丁 90 79 83 82 丙 95 78 87 95 乙 90 73 92 85 甲 D C B A 工作人员整数规划的特点及应用设数学模型如下：要求每人做一项工作，约束条件为：整数规划的特点及应用每项工作只能安排一人，约束条件为：变量约束：整数规划的特点及应用整数规划问题解的特征：整数规划问题的可行解集合是它松弛问题可行解集合的一个子集，任意两个可行解的凸组合不一定满足整数约束条件，因而不一定仍为可行解。整数规划问题的可行解一定是它的松弛问题的可行解（反之不一定），但其最优解的目标函数值不会优于后者最优解的目标函数值。整数规划的特点及应用例设整数规划问题如下首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。整数规划的特点及应用用图解法求出最优解为：x1＝3/2, x2 = 10/3，且有Z = 29/6 现求整数解(最优解):如用舍入取整法可得到4个点即(1，3),(2，3),(1，4),(2，4)。显然，它们都不可能是整数规划的最优解。 x1 x2 ⑴ ⑵ 3 3 (3/2,10/3) 按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如右图所示。其中(2,2),(3,1)点的目标函数值最大，即为Z=4。整数规划的特点及应用整数规划问题的求解方法：分支定界法和割平面法匈牙利法（指派问题）分支定界法 1）求整数规划的松弛问题最优解；若松弛问题的最优解满足整数要求，得到整数规划的最优解,否则转下一步； 2）分支与定界：任意选一个非整数解的变量xi，在松弛问题中加上约束： xi≤[xi] 和 xi≥[xi]+1 组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界。检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数解并且目标值大于(max)整数解的目标值，需要继续分枝，再检查，直到得到最优解。分支定界法的解题步骤：分支定界法例用分枝定界法求解整数规划问题解：首先去掉整数约束，变成一般线性规划问题(原整数规划问题的松驰问题) LP IP 分支定界法用图解法求松弛问题的最优解，如图所示。 x1 x2 ⑴ ⑵ 3 (18/11,40/11) ⑶ 2 1 1 2 3 x1＝18/11, x2 =40/11 Z=－218/11≈(－) 即Z 也是IP最小值的下限。对于x1＝18/11≈，取值x1 ≤1， x1 ≥2 对于x2 =40/11 ≈，取值x2 ≤3 ，x2 ≥4 先将（LP）划分为（LP1）和（LP2）,取x1 ≤1, x1 ≥2 分支定界法分支：分别求出（LP1）和（LP2）的最优解。分支定界法先求LP1,如图所示。此时在B点取得最优解。 x1＝1, x2 =3, Z(1)＝－16 找到整数解，问题已探明，此枝停止计算。 x1 x2 ⑴ ⑵ 3 3 (18/11,40/11) ⑶ 1 1 B A C 同理求LP2,如图所示。在C 点取得最优解。即: x1＝2, x2 =10/3, Z(2)＝－56/3≈－ ∵Z(2)< Z(1)＝－16 ∴原问题有比－16更小的最优解，但 x2 不是整数，故继续分支。分支定界法在IP2中分别再加入条件： x2≤3, x2≥4 得下式两支：分别求出LP21和LP22的最优解分支定界法 x1 x2 ⑴ ⑵ 3 3 (18/11,40/11) ⑶ 1 1 B A C D 先求LP21,如图所示。此时D 在点取得最优解。即 x1＝12/5≈, x2 =3, Z(21)＝-87/5≈ < Z(1)=-16 但x1＝12/5不是整数，可继续分枝。即 3≤x1≤2。求LP22，如图所示。无可行解，故不再分枝。分支定界法在（LP21）的基础上继续分枝。加入条件3≤x1≤2有下式：分别求出（LP211）和（LP212）的最优解分支定界法 x1 x2 ⑴ ⑵ 3 3 (18/11,40/11) ⑶ 1 1 B A C D E F 先求（LP211）,如图所示。此时在E点取得最优解。即 x1＝2, x2 =3, Z(211)＝－17 找到整数解，问题已探明，此枝停止计算。求（LP212），如图所示。此时 F在点取得最优解。即x1＝3, x2 =, Z(212)＝－31/2≈－ > Z(211) 如对LP212继续分解，其最小值也不会低于－，问题探明,剪枝。分支定界法原整数规划问题的最优解为: x1=2, x2 =3, Z* =－17 以上的求解过程可以用一个树形图表示如右： LP1 x1=1, x2=3 Z(1) ＝－16 LP x1=18/11, x2=40/11 Z(0) ＝－ LP2 x1=2, x2=10/3 Z(2) ＝－ LP21 x1=12/5, x2=3 Z(21) ＝－ LP22 无可行解 LP211 x1=2, x2=3 Z(211) ＝－17 LP212 x1=3, x2=5/2 Z(212) ＝－ x1≤1 x1≥2 x2≤3 x2≥4 x1≤2 x1≥3 ＃＃＃＃分支定界法例用分枝定界法求解解: 先求对应的松弛问题（记为LP0）用图解法得到最优解X＝(,),Z0=,如下图所示。分支定界法 10 10 松弛问题LP0的最优解X=(,),Z0= x1 x2 o A B C 分支定界法 10 x2 o A B C LP1 LP2 3 4 LP1:X=(3,),Z1= ① ② LP2:X=(4,),Z2= 分支定界法 10 x1 x2 o A B C LP1 LP21 3 4 LP21:X=(,6),Z21= 6 分支定界法 10 x1 x2 o A C LP1 3 4 6 LP211:X=(4,6), Z211=34 LP212:X=(5,5),Z212=35 5 LP212 分支定界法上述分枝过程可用下图表示： LP0:X=(,),Z0= LP1:X=(3,) Z1= LP2:X=(4,) Z2= x1≤3 x1≥4 LP21:X=(,6) Z21= x2≤6 LP211:X=(4,6) Z211=34 LP212:X=(5,5) Z212=35 x1≤4 x1≥5 LP22 无可行解 x2≥7 小结学习要点：掌握一般整数规划问题概念及模型结构掌握分支定界法原理能够用分支定界法求解一般整数规划问题课后练习： 0－1 整数规划一、0－1变量及其应用 0－1变量常被用来表示系统是否处于某个特定状态，或者决策时是否取某个特定方案。例如: 当问题有多项要素，每项要素皆有两种选择时，可用一组0－1变量来描述。设问题有有限项要素E1， E2，┉，En,其中每项Ej有两种选择Aj和不选择Aj（j=1,2,┉,n）,则令 0－1 整数规划在应用中，有时会遇到变量可以取多个整数值的问题。如果用0－1变量来表示，也可以用一组0－1变量来取代。如x取0－9之间的任意整数时。 x=20x0+ 21x1 + 22x2 + 23x3  9 0－1 整数规划例含有相互排斥的约束条件的问题（1）两个约束中，只有一个起作用。例：a11x1+a12x2<B1 a21x1+a22x2<B2 解：引入0-1变量Y1, Y2和足够大的正数M，则 a11x1+a12x2<B1+M1Y1 a21x1+a22x2<B2+M2Y2 Y1+Y2=1 0－1 整数规划（2）互相排斥的多个约束中，只有一个起作用 ai1x1+ai2x2 +…+ainxn  bi (i=1,…,m) 互相排斥m个约束，只有一个起作用: ai1x1+…+ainxn  bi+yi M (i=1,…,m) y1 +…+ ym =m-1 yi为0或1 M>0 （3）若a个约束条件中只能有b个起作用。则令0－1变量之和为a-b。注意：可用统一M，但M的取值必须足够的大。 0－1 整数规划例固定费用问题解：设Xj是第j种产品的产量。Yj是0－1变量，表示是（Yj=1）否（Yj=0）生产第j种产品。 12 10 8 单件售价 200 150 100 固定费用 6 5 4 单件可变费用 100 3 2 1 C 300 4 3 2 B 500 8 4 2 A 资源量 III II I 单耗量产品资源 0－1 整数规划 maxZ=4X1 +5X2 +6X3 –100Y1 –150Y2 –200Y3 2X1+4X2 +8X3 500 2X1+3X2 +4X3 300 X1+2X2 +3X3 100 X1  M1Y1 X2 M2Y2 X3  M3 Y3 X1 , X2 , X3  0 整数Y1 ,Y2 ,Y3为0－1变量。 . 0－1 整数规划例工件排序问题用4台机床加工3件产品。各产品的机床加工顺序，以及产品I在机床j上加工工时aij见表。由于某种原因，产品2的加工总时间不得超过d，现要求确定各件产品在机床上的加工方案，使在最短的时间内加工完全部产品。产品1 产品2 产品3 a11 机床1 a21 机床1 a13 机床3 a22 机床2 a23 机床2 a33 机床3 a14 机床4 a24 机床4 0－1 整数规划机床1 ： x11+a11  x21+ My1 及 x21+a21 x11 + M(1-y1 ) 机床2 ： x22+a22  x32 + My2 及 x32+a32  x22 + M(1-y2) 机床3 ： x13+a13 x33 + My3 及 x33+a33  x13 + M(1-y3) 机床4： x14+a14  x24 + My4 及 x24+a24  x14 + M(1-y4) 解：设产品i在机床j上开始加工的时间为xij （1）同一件产品在不同机床上的加工顺序约束（2）每一台机床对不同产品上的加工顺序约束产品1 ： x11+a11  x13 及 x13+a13  x14 产品2 ： x21+a21  x22 及 x22+a22  x24 产品3 ： x32+a32  x33 0－1 整数规划（4）目标函数的建立 x24+ a24 -x21  d （3）产品2的加工时间总约束 w  x14+a14 w  x24+a24 w  x33+a33 min z=w min z=max(x14+a14 , x24+a24 , x33+a33) 0－1 整数规划隐枚举法(max) 原则： 1、用试探法，求出一个可行解，以它的目标值作为当前最好值Z0 2、增加过滤条件Z Z0 3、将xi 按ci由小大排列（min 大小） 0－1 整数规划是一种特殊形式的整数规划，这时的决策变量xi 只取两个值0或1，一般的解法为隐枚举法。 0－1 整数规划例：maxZ = 3x1 -2x2+5x3 x1 +2x2 - x3 2 ① x1 +4x2 +x3 4 ② x1 + x2  3 ③ 4x2+x3 6 ④ x1 , x2 , x3为0或1 解：观察得解(x1 , x2 , x3 )=(1 ,0 ,0) Z0 =3 过滤条件：3x1 - 2x2+5x3  3 将(x1 ， x2 ，x3 )  (x2 ，x1 ，x3 ) 0－1 整数规划解(x2 x1 x3 ) 目标值 Z0 ① ② ③ ④ 当前最好值 (0 ,0 ,0) 0 < 3 (0 ,0 ,1) 5 > √ √ √ √ 5 (0 ,1 ,0) 3 < (0 ,1 ,1) 8 > √ √ √ √ 8 (1 ,0 ,0) -2 < (1 ,0 ,1) 3 < (1 ,1 ,0) 1 < (1 ,1 ,1) 6 < 最优解 x = (1 ,0 ,1 )T Z=8 指派问题一、指派问题的数学模型的标准形式：设n 个人被分配去做n 件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第i个人去做第j 件工作的效率（时间或费用）为Cij(i=…n;j=…n)并假设Cij ≥0。问应如何分配才能使总效率（时间或费用）最高？设决策变量指派问题指派问题的数学模型为：指派问题克尼格定理 : 如果从分配问题效率矩阵[aij]的每一行元素中分别减去(或加上)一个常数ui，从每一列中分别减去(或加上)一个常数vj，得到一个新的效率矩阵[bij]，则以[bij]为效率矩阵的分配问题与以[aij]为效率矩阵的分配问题具有相同的最优解。二、匈牙利法指派问题指派问题的匈牙利法求解步骤： 1) 变换指派问题的系数矩阵(cij)为(bij)，使在(bij)的各行各列中都出现0元素，即从(cij)的每行元素都减去该行的最小元素；再从所得新系数矩阵的每列元素中减去该列的最小元素。 2) 进行试指派，以寻求最优解。在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。指派问题找独立0元素，常用的步骤为：从只有一个0元素的行开始，给该行中的0元素加圈，记作◎ 。然后划去◎ 所在列的其它0元素，记作Ø ；这表示该列所代表的任务已指派完，不必再考虑别人了。依次进行到最后一行。从只有一个0元素的列开始（画Ø的不计在内），给该列中的0元素加圈，记作◎；然后划去◎ 所在行的0元素，记作Ø ，表示此人已有任务，不再为其指派其他任务了。依次进行到最后一列。若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，比较这行各0元素所在列中0元素的数目，选择0元素少这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。指派问题若◎ 元素的数目m 等于矩阵的阶数n（即：m＝n），那么这指派问题的最优解已得到。若m < n, 则转入下一步。 3) 用最少的直线通过所有0元素。其方法：对没有◎的行打“√”；对已打“√” 的行中所有含Ø元素的列打“√” ；再对打有“√”的列中含◎ 元素的行打“√” ；重复①、②直到得不出新的打√号的行、列为止；对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有0元素的最少直线数 l 。注：l 应等于m，若不相等，说明试指派过程有误，回到第2步，另行试指派；若 l＝m < n，表示还不能确定最优指派方案，须再变换当前的系数矩阵，以找到n个独立的0元素，为此转第4步。指派问题 4) 变换矩阵(bij)以增加0元素在没有被直线通过的所有元素中找出最小值，没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。新系数矩阵的最优解和原问题仍相同。转回第2步。匈牙利法例有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？ 2 8 9 5 丁 4 10 1 3 丙 8 9 5 4 乙 2 11 7 6 甲 D C B A 任务人员匈牙利法解：1）变换系数矩阵，增加0元素。－5 2）试指派（找独立0元素） ◎ ◎ ◎ Ø Ø 找到 3 个独立零元素但 m = 3 < n = 4 匈牙利法 3）作最少的直线覆盖所有0元素 ◎ ◎ ◎ Ø Ø √ √ √ 独立零元素的个数m等于最少直线数l，即l＝m=3<n=4； 4）没有被直线通过的元素中选择最小值为1，变换系数矩阵，将没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。得到新的矩阵，重复2）步进行试指派匈牙利法 0 0 0 0 0 0 ◎ ◎ ◎ Ø Ø ◎ 得到4个独立零元素，所以最优解矩阵为：即完成4个任务的总时间最少为：2＋4＋1+8=15 匈牙利法例已知四人分别完成四项工作所需时间如下表，求最优分配方案。 9 11 8 7 丁 13 16 14 9 丙 15 14 4 10 乙 4 13 15 2 甲 D C B A 任务人员匈牙利法解：1）变换系数矩阵，增加0元素。 ◎ Ø ◎ Ø Ø ◎ ◎ 2）试指派（找独立0元素）独立0元素的个数为4 , 指派问题的最优指派方案即为甲负责D工作，乙负责B工作，丙负责A工作，丁负责C工作。这样安排能使总的工作时间最少，为4＋4＋9＋11＝28。匈牙利法例已知五人分别完成五项工作耗费如下表，求最优分配方案。 11 5 7 6 4 戊 6 8 9 11 E 9 6 3 7 丁 6 4 5 8 丙 11 7 12 9 乙 8 9 5 7 甲 D C B A 任务人员匈牙利法解：1）变换系数矩阵，增加0元素。 -1 -2 匈牙利法 ◎ Ø ◎ ◎ ◎ Ø Ø 2）试指派（找独立0元素）独立0元素的个数l＝4<5，故画直线调整矩阵。匈牙利法 ◎ Ø ◎ ◎ ◎ Ø Ø √ √ √ 选择直线外的最小元素为1；直线外元素减1，直线交点元素加1，其他保持不变。匈牙利法 ◎ Ø ◎ Ø ◎ Ø ◎ Ø √ √ √ √ √ √ √ l =m=4 < n=5 选择直线外最小元素为1，直线外元素减1，直线交点元素加1，其他保持不变，得到新的系数矩阵。匈牙利法 ◎ Ø Ø ◎ Ø Ø ◎ Ø ◎ Ø ◎ 总费用为=5+7+6+6+4=28 注：此问题有多个最优解匈牙利法 ◎ Ø Ø ◎ Ø Ø ◎ Ø ◎ Ø ◎ 总费用为=7+9+4+3+5=28 匈牙利法 ◎ Ø Ø ◎ Ø Ø ◎ Ø ◎ Ø ◎ 总费用为=8+9+4+3+4=28 匈牙利法课堂练习：用匈牙利法求解下列指派问题。练习1：练习2：匈牙利法 48 21 答案：指派问题非标准型的指派问题：匈牙利法的条件是：模型求最小值、效率cij≥0。当遇到各种非标准形式的指派问题时，处理方法是先将其转化为标准形式，然后用匈牙利法来求解。 1. 最大化指派问题处理方法：设m为最大化指派问题系数矩阵C中最大元素。令矩阵B＝（m-cij）nn则以B为系数矩阵的最小化指派问题和原问题有相同的最优解。例某人事部门拟招聘4人任职4项工作，对他们综合考评的得分如下表（满分100分），如何安排工作使总分最多。指派问题指派问题解: M＝95，令用匈牙利法求解C’，最优解为：即甲安排做第二项工作、乙做第三项、丙做第四项、丁做第三项, 最高总分Z＝92＋95＋90＋80＝357 指派问题 2. 不平衡的指派问题当人数m大于工作数n时，加上m－n项虚拟工作，例如：当人数m小于工作数n时，加上n－m个人，例如指派问题 3. 一个人可做几件事的指派问题若某人可做几件事，则将该人化作相同的几个“人”来接受指派，且费用系数取值相同。例如：丙可以同时任职A和C工作，求最优指派方案。指派问题 4. 某事一定不能由某人做的指派问题将该人做此事的效率系数取做足够大的数，可用M表示。例分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务。每个人完成各项任务的时间如表所示。由于任务数多于人数，考虑任务E必须完成，其他4项中可任选3项完成。试确定最优分配方案，使完成任务的总时间最少。 45 32 33 37 E 23 36 42 24 丁 40 28 27 34 丙 20 26 38 39 乙 42 31 29 25 甲 D C B A 任务人员指派问题解: 1) 这是不平衡的指派问题，首先转换为标准型，再用匈牙利法求解。 2) 由于任务数多于人数，所以假定一名虚拟人，设为戊。因为工作E必须完成，故设戊完成E的时间为M（M为非常大的数），其余效率系数为0，则标准型的效率矩阵表示为： M 0 0 0 0 戊 45 32 33 37 E 23 36 42 24 丁 40 28 27 34 丙 20 26 38 39 乙 42 31 29 25 甲 D C B A 任务人员指派问题用匈牙利法求出最优指派方案为：即甲－B，乙－D，丙－E，丁－A, 任务C放弃。最少时间为105。运筹帷幄之中决胜千里之外图与网络分析 Graph Theory and Network Analysis 图与网络分析图与网络的基本知识中国邮路问题最短路问题最大流问题本章主要内容：图与网络的基本知识图论起源——哥尼斯堡七桥问题问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？结论：不能。每个结点关联的边数要均为偶数。 B D A C A B C D 一笔画问题图与网络的基本知识环球旅行问题：图与网络的基本知识环球旅行问题的解另一个著名的问题: 中国邮路问题图与网络的基本知识图论中图是由点和边构成，可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。图的定义：若用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点(顶点)和边的集合，记作：其中: V——点集 E——边集 ※ 图G区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。图与网络的基本知识 (v1) 赵 (v2)钱孙(v3) 李(v4) 周(v5) 吴(v6) 陈(v7) e2 e1 e3 e4 e5 (v1) 赵 (v2)钱 (v3)孙 (v4)李 (v5) 周 (v6)吴 (v7)陈 e2 e1 e3 e4 e5 可见图论中的图与几何图、工程图是不一样的。例如：在一个人群中，对相互认识这个关系我们可以用图来表示。图与网络的基本知识定义: 图中的点用v表示，边用e表示。对每条边可用它所连接的点表示，记作：e1=[v1,v1]; e2=[v1,v2]; v3 e7 e4 e8 e5 e6 e1 e2 e3 v1 v2 v4 v5 端点,关联边,相邻若有边e可表示为e=[vi,vj]，称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。若点vi、vj与同一条边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei和ej相邻。 V = {v1 , v2 , v3 , v4 , v5}， E = {e1 , e2 , e3 , e4 , e5 , e6 , e7, e8}，边数：m(G)=|E|=m 顶点数：n(G)=|V|=n 无向边与无向图：若图中任一条边的端点无序，即(vi, vj)与(vj, vi)是同一条边，则称它为无向边，此时图称为无向图。有向图：若图中边(vi, vj)的端点是有序的，则称它是有向边（或弧），vi与vj分别称为这条有向边的始点和终点，相应的图称为有向图。有向图无向图图与网络的基本知识无向图,有向图图与网络的基本知识环, 多重边, 简单图如果边e的两个端点相重，称该边为环。如右图中边e1为环。如果两个点之间多于一条，称为多重边，如右图中的e4和e5，对无环、无多重边的图称作简单图。含多重边的图称为多重图。 v3 e7 e4 e8 e5 e6 e1 e2 e3 v1 v2 v4 v5 简单图多重图环多重边图与网络的基本知识完全图每一对顶点间都有边相连的无向简单图称为无向完全图；有向完全图是指每一对顶点间有且仅有一条有向边的简单图。完全图顶点数n与边数m间成立如下关系: m=n(n-1)/2 图与网络的基本知识二部图（偶图）图G=(V,E)的点集V可以分为两各非空子集X，Y，集X∪Y=V,X∩Y=Ø,使得同一集合中任意两个顶点均不相邻，称这样的图为二部图（偶图）。 v1 v3 v5 v2 v4 v6 v1 v2 v3 v4 v1 v4 v2 v3 (a) (b) (c) (a)明显为二部图，(b)也是二部图，但不明显，改画为(c)时可以清楚看出。图与网络的基本知识次，奇点，偶点，孤立点与某一个点vi相关联的边的数目称为点vi的次（也叫做度），记作d(vi)。右图中d(v1)＝４,d(v3)=5,d(v5)=1。次为奇数的点称作奇点，次为偶数的点称作偶点，次为1的点称为悬挂点，次为0的点称作孤立点。 v3 e7 e4 e8 e5 e6 e1 e2 e3 v1 v2 v4 v5 图的次: 一个图的次等于各点的次之和。图与网络的基本知识 v2 v1 v5 v3 v4 e2 e1 e3 e4 e5 e6 d(v1)=4 d(v2)=3 悬挂点孤立点悬挂边偶点奇点图与网络的基本知识图中顶点次的性质定理1 任何图中顶点次数的总和等于边数的2倍。定理2 任何图中次为奇数的顶点必有偶数个。定义6 在有向图中，以顶点v为始点的边数称为顶点v的出次，记为d+(v)；以v为终点的边数称为v的入次，记为d-(v)。顶点v的出次与入次的和称为点v的次。定义7 图G=(V, E), 若E'是E的子集，若V'是V的子集，且E'中的边仅与V'中的顶点相关联，则称G' = (V', E')为图G的一个子图，特别地，若V' =V, 则称G'为G的一个生成子图（支撑子图）。图与网络的基本知识子图，生成子图(支撑子图) 图G1={V1、E1}和图G2={V2，E2}如果有称G1是G2的一个子图。若有，则称G1是G2的一个生成子图(支撑子图)。 v3 e7 e4 e8 e5 e6 e1 e2 e3 v1 v2 v4 v5 v3 e4 e8 e5 e6 v2 v4 v5 v3 e7 e4 e8 e6 e2 e3 v1 v2 v4 v5 (a) (b) （G图）图与网络的基本知识网络（赋权图）设图G＝（V，E），对G的每一条边(vi,vj)相应赋予数量指标wij，wij称为边(vi,vj)的权,赋予权的图G称为网络(或赋权图）。权可以代表距离、费用、通过能力(容量)等等。端点无序的赋权图称为无向网络，端点有序的赋权图称为有向网络。 ① ② ③ ④ ⑤ ⑥ 9 10 20 15 7 14 19 25 6 图与网络的基本知识链，圈，连通图定义8 无向图中一个点、边交错的序列，序列中的第一个和最后一个元素都是点，若其中每条边以序列中位于它之前和之后的点为端点，则称这个点边序列为图中连接其第一个点与最后一个点的称为链。链中所含的边数称为链长。链，但只是简单链而非初等链简单链：没有重复边；初等链：既无重复边也无重复点。对有向图可类似定义链，如果各边方向一致，则称为道路。图与网络的基本知识链，圈，连通图定义9 若在无向图中，一条链的第一个点与最后一个点重合，则称这条链为圈。只有重复点而无重复边的圈为简单圈，既无重复点又无重复边的圈为初等圈。初等圈非简单的圈图与网络的基本知识圈（或回路）回路链（或道路）道路无向图有向图道路(边的方向一致) 图与网络的基本知识连通图定义10 一个图中任意两点间至少有一条链相连，则称此图为连通图。任何一个不连通图总可以分为若干个连通子图，每一个称为原图的一个分图（连通分支）。连通图非连通图图的基本概念与模型图的基本性质：定理1 任何图中，顶点次数之和等于所有边数的2倍。定理2 任何图中，次为奇数的顶点必为偶数个。证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的2倍。证明：设V1和V2分别为图G中奇点与偶点的集合。由定理1可得： 2m为偶数，且偶点的次之和也为偶数，所以必为偶数，即奇数点的个数必为偶数。图的基本概念与模型图的矩阵表示：如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有：邻接矩阵、关联矩阵、权矩阵等。 1. 邻接矩阵对于图G=（V，E），| V |=n， | E |=m，有nn阶方矩阵A=(aij) nn，其中图的基本概念与模型 v5 v1 v2 v3 v4 v6 4 3 3 2 2 5 6 4 3 7 例下图所表示的图可以构造邻接矩阵A如下图的基本概念与模型 2. 关联矩阵对于图G=(V,E), | V |=n, | E |=m, 有mn阶矩阵M=(mij) mn，其中: 对于赋权图G=(V,E), 其中边有权 , 构造矩阵B=(bij) nn 其中： 3. 权矩阵图的基本概念与模型 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 v1 v2 v3 v4 v5 v6 v7 v8 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 v1 v2 v3 v5 v8 v7 e1 e2 e3 e4 e6 e5 e7 e9 e12 e10 e11 e8 v6 v4 例下图所表示的图可以构造邻接矩阵M如下: M=（mij）= 图的基本概念与模型 v5 v1 v2 v3 v4 v6 4 3 3 2 2 5 6 4 3 7 例下图所表示的图可以构造权矩阵B如下: 欧拉回路定义13 连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条道路为欧拉道路。若存在一条回路经过每边一次也仅一次，则称这条回路为欧拉回路。具有欧拉回路的图称为欧拉图（E图）。定理3 无向连通图G是欧拉图，当且仅当G中无奇点欧拉回路推论1 无向连通图G为欧拉图，当且仅当G的边集可以划分为若干个初等回路。推论2 无向连通图G中有欧拉道路，当且仅当G中恰好有两个奇点。中国邮路问题一个邮递员，负责某一地区的信件投递，他每天要走邮局出发，走遍该地区所有街道，再返回邮局，问应如何安排送信的路线可以使所走的总路程最短？用图论的语言描述就是：给定一个连通图G，每边有非负权l(e)，要求一条回路过每边至少一次，且满足总权最小。中国邮路问题解法（1）若G是欧拉图，则按欧拉回路走，就是满足要求的经过每边至少一次且总权最小的走法。 a b c d e f 若G中有奇点，则G不是欧拉图，因此要连续地走过每边至少一次，则必然有某些边不止一次走过。这相当于在G中添加一些重复的边，使得到的新图G*没有奇点且满足总路程最短。中国邮路问题解法（2） a b c d e f a b c d e f 对增加了重复边后得到的新图G*，很明显其总权的大小取决于增加的重复边权的大小。因此中国邮路问题转化为如下问题：在连通图G=(V, E)中，求一个边的集合E1E，将E1中所有边都变成重复边得到新图G*，使得G*中无奇点，且最小中国邮路问题解法（3）上述问题的解决依赖于以下结果：定理5 已知图G*=G+E1无奇点，则最小的充分必要条件为：（1）每条边最多重复一次；（2）对图G中的每个初等圈来说，重复边的长度不超过圈长的一半。中国邮路问题解法（4）下面直观地说明，若定理5的条件不成立，则可以得到总权比E1的更小的重复边集。 1 2 2 2 5 4 1 2 2 2 5 4 重复两次或以上的去掉其中两条将原来的重复边变成非重复边，原来的非重复边变成重复边中国邮路问题解法（5）解法第一步：确定初始可行方案。若图中没有奇点，则它已经是欧拉图，按欧拉回路走即可。否则，若有奇点，奇点必有偶数个，将奇点两两配对，然后找出每对奇点间的一条道路，将此道路中的每条边都变成重复边。 5 2 4 3 6 3 4 5 9 4 4 4 l12+2 l23+2 l36+ l89+2 l78+l69+l14+2 l47=51 中国邮路问题解法（6） 5 2 4 3 6 3 4 5 9 4 4 4 第二步：调整可行方案。使重复边最多重复一次 5 2 4 3 6 3 4 5 9 4 4 4 l12+l69+l14+ l98=21 中国邮路问题解法（7） 5 2 4 3 6 3 4 5 9 4 4 4 第三步：检查图中每个初等圈是否满足定理条件（2），若不满足则进行调整。 5 2 4 3 6 3 4 5 9 4 4 4 5 2 4 3 6 3 4 5 9 4 4 4 第三步要求检查每个初等圈，这一步可能是相当繁琐的。例如上例中的图就包括下图所示的初等圈。最短路问题如何用最短的线路将三部电话连起来？此问题可抽象为设△ABC为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如AB∪AC）。 A B C 最短路问题 A B C P 但若增加一个周转站（新点P），连接4点的新网络的最短路线为PA＋PB＋PC。最短新路径之长N比原来只连三点的最短路径O要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。最短路问题问题描述：就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路 . 有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。最短路问题例渡河游戏一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。最短路问题定义： 1）人—M（Man），狼—W（Wolf），羊—G（Goat），草—H（Hay） 2）点—— vi 表示河岸的状态 3）边—— ek 表示由状态 vi 经一次渡河到状态 vj 4）权——边 ek 上的权定为 1 我们可以得到下面的加权有向图最短路问题状态说明： v1,u1 =( M,W,G,H ); v2,u2 =(M,W,G); v3,u3 =(M,W,H); v4,u4=(M,G,H); v5,u5 =(M,G) 此游戏转化为在下面的二部图中求从 v1 到 u1 的最短路问题。 v1 v2 v3 v4 v5 u5 u4 u3 u2 u1 最短路问题求最短路有两种算法: 狄克斯屈拉(Dijkstra)标号算法逐次逼近算法最短路问题狄克斯屈拉(Dijkstra)标号算法的基本思路：若序列{ vs,v1…..vn-1,vn }是从vs到vt间的最短路，则序列{ vs,v1…..vn-1 } 必为从vs 到vn-1的最短路。假定v1→v2 →v3 →v4是v1 →v4的最短路，则v1 →v2 →v3一定是v1 →v3的最短路，v2 →v3 →v4也一定是v2 →v4的最短路。 v1 v2 v3 v4 v5 最短路问题求网络图的最短路，设图的起点是vs,终点是vt ,以vi为起点vj为终点的弧记为 (i, j) 距离为dij P标号(点标号)：b(j) —起点vs到点vj的最短路长； T标号(边标号)： k(i,j)=b(i)+dij，步骤： 1. 令起点的标号；b(s)＝0。 2. 找出所有vi已标号vj未标号的弧集合 B={(i, j)} 如果这样的弧不存在或vt已标号则计算结束； 3. 计算集合B中弧k(i，j)=b(i)+dij的标号 4. 选一个点标号在终点vl处标号b(l), 返回到第2步。最短路问题例求下图v1到v7的最短路长及最短路线 ① ② ③ ④ ⑤ ⑥ ⑦ 8 6 2 5 2 3 5 3 4 2 10 5 7 0 8 6 2 2 5 4 4 11 14 7 5 10 7 11 P标号 T标号 9 最短路问题 v1到v7的最短路长及最短路线如图所示： ① ② ③ ④ ⑤ ⑥ ⑦ 8 6 2 5 2 3 5 3 4 2 10 5 7 v7已标号，计算结束。从v1到v7的最短路长是 11, 最短路线： v1→ v4 → v6 → v7 0 2 4 11 最短路问题从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj 。注：无向图最短路的求法只将上述步骤2将弧改成边即可。最短路问题例求下图v1到各点的最短距离及最短路线。 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 4 5 2 6 1 7 8 3 9 3 2 6 12 16 18 0 4 5 2 2 3 10 3 9 6 12 6 4 11 6 6 18 8 12 24 8 24 18 最短路问题 v1到各点的最短距离及最短路线如图所示： ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 4 5 2 6 1 7 8 3 9 3 2 6 12 16 18 0 2 6 18 所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 例求从1到8的最短路径最短路问题 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1}, w1=0 min {c12,c14,c16}=min {0+2,0+1,0+3}=min {2,1,3}=1 X={1,4}, p4=1 p4=1 p1=0 最短路问题 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,4} min {c12,c16,c42,c47}=min {0+2,0+3,1+10,1+2}=min {2,3,11,3}=2 X={1,2,4}, p2=2 p1=0 p4=1 p2=2 最短路问题 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,4} min {c16,c23,c25,c47}=min {0+3,2+6,2+5,1+2}=min {3,8,7,3}=3 X={1,2,4,6}, p6=3 p2=2 p4=1 p1=0 p6=3 最短路问题 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,4,6} min {c23,c25,c47,c67}=min {2+6,2+5,1+2,3+4}=min {8,7,3,7}=3 X={1,2,4,6,7}, p7=3 p2=2 p4=1 p1=0 p6=3 p7=3 最短路问题 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,4,6,7} min {c23,c25,c75,c78}=min {2+6,2+5,3+3,3+8}=min {8,7,6,11}=6 X={1,2,4,5,6,7}, p5=6 p2=2 p4=1 p1=0 p6=3 p7=3 p5=6 最短路问题 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,4,6,7} min {c23,c53,c58,c78}=min {2+6,6+9,6+4,3+8}=min {8,15,10,11}=8 X={1,2,3,4,5,6,7}, p3=8 p2=2 p4=1 p1=0 p6=3 p7=3 p5=6 p3=8 最短路问题 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,3,4,6,7} min {c38,c58,c78}=min {8+6,6+4,3+7}=min {14,10,11}=10 X={1,2,3,4,5,6,7,8}, p8=10 p2=2 p4=1 p1=0 p6=3 p7=3 p5=6 p3=8 p8=10 最短路问题 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,3,4,6,7,8} 1到8的最短路径为{1，4，7，5，8}，长度为10。 p2=2 p4=1 p1=0 p6=3 p7=3 p5=6 p3=8 p8=10 最短路问题最短路问题课堂练习： 1. 用Dijkstra算法求下图从v1到v6的最短距离及路线。 v3 v5 4 v1 v2 v4 v6 3 5 2 2 2 4 2 1 v1到v6的最短路为：最短路问题 2. 求下图中v1点到另外任意一点的最短路径 v1 v2 v3 v4 v6 v5 3 2 2 7 6 2 1 3 3 最短路问题 v1 V2 V3 V4 V6 V5 3 2 2 7 6 2 1 3 3 0 2 4 7 1 4 最短路问题 v1 V2 V3 V4 V6 V5 3 2 2 7 6 2 1 3 3 0 2 4 7 1 4 最短路问题算法适用条件： Dijkstra算法只适用于全部权为非负情况，如果某边上权为负的，算法失效。此时可采用逐次逼近算法。例如右图所示中按dijkstra算法可得P(v1)=5为从vs→v1的最短路长显然是错误的，从vs→v2→v1路长只有3。 v2 vs v1 5 -5 8 最短路问题例设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表 13 12 12 11 11 年初价格 5 4 3 2 1 年份最短路问题设备维修费如下表 18 11 8 6 5 每年维修费用 4-5 3-4 2-3 1-2 0-1 使用年数解：将问题转化为最短路问题，如下图：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。 v1 v2 v3 v4 v5 v6 最短路问题把所有弧的权数计算如下表，把权数赋到图中，再用Dijkstra算法求最短路。 6 18 5 23 17 4 31 23 17 3 41 30 22 16 2 59 41 30 22 16 1 6 5 4 3 2 1 v1 v2 v3 v4 v5 v6 16 22 30 41 59 16 22 30 41 31 23 17 18 17 23 W12 =11+5=16 W13 =11+5+6=22 W14 =11+5+6+8=30 W15 =11+5+6+8+11=41 W16 =11+5+6++8+11+18=59 W23 =11+5=16 W24 =11+5+6=22 W25 =11+5+6+8=30 W26 =11+5+6+8+11=41 W34 =12+5=17 W35 =12+5+6=23 W36 =12+5+6+8=31 W45 =12+5=17 W46 =12+5+6=23 W56 =13+5=18 最短路问题最终得到下图，可知，v1到v6的距离是53，最短路径有两条： v1→v3→v6和 v1→v4→v6 V1 （0,s） v3 v4 (41,1) v5 v6 22 30 41 59 16 (22,1) 30 41 31 23 17 18 17 23 V2 （16,1） 16 (30,1) (53,3) (53,4) 最大流问题如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。最大流问题基本概念： 1. 容量网络：队网络上的每条弧(vi,vj)都给出一个最大的通过能力，称为该弧的容量，简记为cij。容量网络中通常规定一个发点(也称源点，记为vs)和一个收点(也称汇点，记为vt)，网络中其他点称为中间点。 vs ① ② ③ ④ vt 4 8 4 4 1 2 2 6 7 9 最大流问题 2. 网络的最大流是指网络中从发点到收点之间允许通过的最大流量。 3. 流与可行流流是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上的载量记为fij。若fij=0，称为零流。满足以下条件的一组流称为可行流。容量限制条件。容量网络上所有的弧满足：0≤fij≤cij 中间点平衡条件。若以v(f)表示网络中从vs→vt的流量，则有：最大流问题结论：任何网络上一定存在可行流。（零流即是可行流）网络最大流问题：指满足容量限制条件和中间点平衡的条件下，使v(f)值达到最大。 3,1 5,2 1,0 1,0 4,1 2(2) 3,1 5(2) 2,1 vs v2 v1 v3 v4 vt 标示方式：每条边上标示两个数字，第一个是容量，第二是流量最大流问题割集容量网络G =（V，E，C），vs为始点，vt为终点。如果把V分成两个非空集合，使，则所有始点属于S，而终点属于的弧的集合，称为由S决定的割集,记作。割集中由S到所有弧的容量之和，称为这个割集的容量，记为 vs v1 v2 v4 v3 vt 3 7 4 5 5 6 3 7 8 S 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5 (2) 5 (2) 5 (0) 4 (2) 4 (1) 9 (5) 10 (1) 设则割集容量为24 最大流问题 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5 (2) 5 (2) 5 (0) 4 (2) 4 (1) 9 (5) 10 (1) 设则容量为20 割集最大流问题最大流—最小割定理网络理论中著名的最大流最小割定理：对于任一容量网络，从发点到收点的最大流量等于最小割量。由发点vs到收点vt任一可行流量W显然必须受割集容量的限制，即有：容量最小的割集称为最小割集最大流问题 v3 vs v2 v1 v4 vt 若μ是联结发点vs和收点vt的一条链，我们规定链的方向是从vs到vt，则链上的弧被分成两类：前向弧、后向弧。 μ1: vs→ v2 → v4→ vt μ2: vs→ v2 → v3→ vt μ3: vs→ v2 → v1→ v3→ vt μ4: vs → v1 → v2 → v3→ vt 最大流问题 v3 vs v2 v1 v4 vt 2,1 2,2 3,1 5,2 1,0 1,0 4,1 3,1 5,2 设 f 是一个可行流，μ是从vs到vt 的一条链，若μ满足前向弧都是非饱和弧,后向弧都是非零流弧,则称μ是（可行流 f 的）一条增广链。 μ1: vs→ v2 → v4→ vt √ μ2: vs→ v2 → v3→ vt × μ3: vs→ v2 → v1→ v3→ vt √ μ4: vs → v1 → v2 → v3→ vt × μ5: vs → v2 → v4 → v3→ vt √ 最大流问题求最大流的标号法标号法思想是：先找一个可行流。对于一个可行流，经过标号过程得到从发点vs 到收点vt 的增广链；经过调整过程沿增广链增加可行流的流量，得新的可行流。重复这一过程，直到可行流无增广链，得到最大流。标号过程—用来找增广链的过程调整过程—用来增大增广链流量的过程从任一个可行流 f 出发（若网络中没有给定初始可行流f ，可从零流开始），经历如下两过程：最大流问题最大流问题求网络最大流的标号算法： [基本方法] 找出第一个可行流，（例如所有弧的流量fij =0。）用标号的方法找一条增广链首先给发点s标号(∞),标号中的数字表示允许的最大调整量。选择一个点 vi 已标号并且另一端未标号的弧沿着某条链向收点检查：最大流问题如果弧的起点为vi，并且有fij<Cij，则给vj标号为(Cij－fij) 如果弧的方向指向vi，并且有fji>0，则vj标号(fji) (3) 重复第(2)步，可能出现两种结局：标号过程中断，t 无法标号，说明网络中不存在增广链，目前流量为最大流。同时可以确定最小割集，记已标号的点集为V,未标号的点集合为V′,(V,V′)为网络的最小割。 t 得到标号，反向追踪在网络中找到一条从s到t得由标号点及相应的弧连接而成的增广链。继续第(4)步最大流问题 (4) 修改流量。设原图可行流为f，令得到网络上一个新的可行流f’。 (5) 擦除图上所有标号，重复(1)-(4)步，直到图中找不到任何增广链，计算结束。最大流问题例用标号算法求下图中s→t 的最大流量，并找出最小割。 ● s t v1 v3 v2 v4 8(7) 9(3) 5(4) 10(8) 6(1) 2(0) 9(9) 5(4) 7(5) 最大流问题解：(1) 先给s标号(∞) ● s t v1 v3 v2 v4 8(7) 9(3) 5(4) 10(8) 6(1) 2(0) 9(9) 5(4) 7(5) (∞) 最大流问题 ● s t v1 v3 v2 v4 8(7) 9(3) 5(4) 10(8) 6(1) 2(0) 9(9) 5(4) 7(5) (∞) (2) 检查与s点相邻的未标号的点，因fs1<cs1，故对v1标号=min{∞, cs1-fs1}=1, (1) 最大流问题 ● s t v1 v3 v2 v4 8(7) 9(3) 5(4) 10(8) 6(1) 2(0) 9(9) 5(4) 7(6) (∞) (1) (2) 检查与v1点相邻的未标号的点，因f13<c13，故对v3标号=min{1, c13-f13}= min{1, 6}= 1 (1) 最大流问题 ● s t v1 v3 v2 v4 8(7) 9(3) 5(4) 10(8) 6(1) 2(0) 9(9) 5(4) 7(5) (∞) (1) (1) (3) 检查与v3点相邻的未标号的点，因f3t<c3t，故对vt标号=min{1, c3t-f3t}= min{1, 1}= 1 (1) 找到一条增广链s→v1→v3→t 最大流问题 (4) 修改增广链上的流量，非增广链上的流量不变，得到新的可行流。 ● s t v1 v3 v2 v4 8(7) 9(3) 5(4) 10(8) 6(1) 2(0) 9(9) 5(3) 7(5) (∞) (1) (1) (1) 最大流问题 (5) 擦除所有标号，重复上述标号过程，寻找另外的增广链。 ● s t v1 v3 v2 v4 8(8) 9(4) 5(5) 10(8) 6(0) 2(0) 9(9) 5(3) 7(5) (∞) (1) (1) (1) 最大流问题 (5) 擦除所有标号，重复上述标号过程，寻找另外的增广链。 ● s t v1 v3 v2 v4 8(8) 9(4) 5(5) 10(8) 6(1) 2(0) 9(9) 5(3) 7(5) (∞) (2) ε(2)=min{∞,2}=2 (2) ε(1)=min{2,3}=2 ε(3)=min{2,5}=2 (2) (1) ε(4)=min{2,1}=1 (1) ε(t)=min{1,2}=1 最大流问题 (6) 修改增广链上的流量，非增广链上的流量不变，得到新的可行流。 ● s t v1 v3 v2 v4 8(8) 9(4) 5(5) 10(8) 6(1) 2(0) 9(9) 5(3) 7(5) (∞) (2) (2) (2) (1) (1) 最大流问题 ● s t v1 v3 v2 v4 8(8) 9(5) 5(5) 10(9) 6(0) 2(0) 9(9) 5(2) 7(6) (7) 擦除所有标号，重复上述标号过程，寻找另外的增广链。最大流问题 ● s t v1 v3 v2 v4 8(8) 9(5) 5(5) 10(9) 6(0) 2(0) 9(9) 5(2) 7(6) (∞) (1) (1) (1) (7) 重复上述标号过程，寻找另外的增广链。 ε(2)=min{∞,1}=1 ε(1)=min{1,2}=1 ε(3)=min{1,4}=1 最大流问题例求下图s→t的最大流，并找出最小割 s t v1 v2 v3 v4 v5 4(3) 3(2) 10(4) 3(2) 1(1) 4(3) 3(2) 5(3) 4(2) 2(2) 7(6) 8(3) ● 最大流问题 s t v1 v2 v3 v4 v5 4(3) 3(2) 10(4) 3(2) 1(1) 4(3) 3(2) 5(3) 4(2) 2(2) 7(6) 8(3) ● 解: (1) 在已知可行流的基础上，通过标号寻找增广链。 (∞) ε(2)=min{∞,6}=6 (6) ε(3)=min{6,2}=2 (2) ε(t)=min{2,5}=2 (2) 存在增广链s→v2→v3→ t 最大流问题 (2) 修改增广链上的流量，非增广链上的流量不变，得到新的可行流。 s t v1 v2 v3 v4 v5 4(3) 3(2) 10(4) 3(2) 1(1) 4(3) 3(2) 5(3) 4(2) 2(2) 7(6) 8(3) ● (∞) (6) (2) (2) 最大流问题 (3) 擦除原标号，重新搜寻增广链。 s t v1 v2 v3 v4 v5 4(3) 3(2) 10(6) 3(2) 1(1) 4(3) 3(2) 5(3) 4(4) 2(2) 7(6) 8(5) ● (∞) (6) (2) (2) 最大流问题 (4) 重新搜寻增广链。 s t v1 v2 v3 v4 v5 4(3) 3(2) 10(6) 3(2) 1(1) 4(3) 3(2) 5(3) 4(4) 2(2) 7(6) 8(5) ● (∞) ε(2)=min{∞,4}=4 (4) (1) ε(5)=min{4,1}=1 ε(3)=min{1,2}=1 (1) (1) ε(t)=min{1,3}=1 存在增广链：s→v2→v5→v3→ t 最大流问题 (5) 修改增广链上的流量，非增广链上的流量不变，得到新的可行流。 s t v1 v2 v3 v4 v5 4(3) 3(2) 10(6) 3(2) 1(1) 4(3) 3(2) 5(3) 4(4) 2(2) 7(6) 8(5) ● (∞) (4) (1) (1) (1) 最大流问题 (6) 擦除原标号 s t v1 v2 v3 v4 v5 4(3) 3(2) 10(7) 3(2) 1(1) 4(3) 3(3) 5(4) 4(4) 2(2) 7(6) 8(6) ● (∞) (4) (1) (1) (1) 最大流问题 s t v1 v2 v3 v4 v5 4(3) 3(2) 10(7) 3(2) 1(1) 4(3) 3(3) 5(4) 4(4) 2(2) 7(6) 8(6) ● (∞) (1) (1) (1) ε(5)=min{∞,1}=1 ε(5)=min{1,1}=1 ε(5)=min{1,2}=1 (7) 重新搜寻增广链。存在增广链：s→v5→v3→ t 最大流问题 (8) 调整增广链上的流量，非增广链流量不变，得到新的可行流 s t v1 v2 v3 v4 v5 4(3) 3(2) 10(7) 3(2) 1(1) 4(3) 3(3) 5(4) 4(4) 2(2) 7(6) 8(6) ● (∞) (1) (1) (1) 最大流问题 s t v1 v2 v3 v4 v5 4(3) 3(3) 10(7) 3(2) 1(1) 4(3) 3(3) 5(5) 4(4) 2(2) 7(6) 8(7) ● (∞) (1) (1) (1) (9) 擦除原标号最大流问题 s t v1 v2 v3 v4 v5 4(3) 3(3) 10(7) 3(2) 1(1) 4(3) 3(3) 5(5) 4(4) 2(2) 7(6) 8(7) ● (10) 重新标号，搜索增广链 (∞) ε(1)=min{∞,1}=1 (1) ε(5)=min{1,1}=1 (1) ε(4)=min{1,1}=1 (1) ε(t)=min{1,1}=1 (1) 存在增广链：s→v1→v5→v4→t 最大流问题 s t v1 v2 v3 v4 v5 4(3) 3(3) 10(7) 3(2) 1(1) 4(3) 3(3) 5(5) 4(4) 2(2) 7(6) 8(7) ● (∞) (1) (1) (1) (1) (11) 调整增广链上的流量，非增广链流量不变，得到新的可行流最大流问题 s t v1 v2 v3 v4 v5 4(4) 3(3) 10(7) 3(3) 1(1) 4(4) 3(3) 5(5) 4(4) 2(2) 7(7) 8(7) ● (∞) (1) (1) (1) (1) (11) 擦除标号，在新的可行流上重新标号。最大流问题 s t v1 v2 v3 v4 v5 4(4) 3(3) 10(7) 3(3) 1(1) 4(4) 3(3) 5(5) 4(4) 2(2) 7(7) 8(7) ● (∞) (11) 擦除标号，在新的可行流上重新标号。 (3) ε(1)=min{∞,3}=1 无法标号，不存在增广链，此可行流已为最大流。最大流量为14。运筹帷幄之中决胜千里之外网络计划 Introduction 网络计划（1）网络图（2）时间参数的计算（3）网络计划的优化本章主要内容： 20世纪50年代计划管理的新方法：关键路线法（CPM）计划评审方法（PERT） ——建立在网络模型基础上，称为网络计划技术 20世纪60年初代数学家华罗庚先生统筹方法网络计划统筹方法的基本原理网络计划 2．通过对网络图时间参数的计算，找出关键工作、关键线路； 3．利用优化原理，改善网络计划的初始方案，以选择最优方案； 4．在网络计划的执行过程中进行有效的控制和监督，保证合理地利用资源，力求以最少的消耗获取最佳的经济效益和社会效益. 1．利用网络图的形式表达一项工程中各项工作的先后顺序及逻辑关系；网络图（箭头图） ——带箭头的线和节点组成箭线：工作（或工序、活动）a:(i,j) 节点：事项 i，j 工作需要一定的时间与资源事项不需时间或很少（可忽略）网络图一、网络图 i j 工作名称或代号持续时间工时为零，不消耗任何资源表明工作间的逻辑关系虚工作： i j 双代号法（箭杆式）：清理现场 8（天） a 8（天）或（i ,j ） tij i j i ＜j 工作a：(i，j) 事项：i，j 画网络图的规则网络图工作间的基本逻辑关系对工作（i, j）：紧前工序、紧后工序、平行工序。 i j 平行紧前紧后网络图网络图：一个总起点事项、一个总终点事项。网络图是有向图，不允许有回路。网络图 1 3 4 2 5 6 7 2 1 3 节点i，j之间不允许有两个或两个以上的工作。 j b a i × a i j i’ b √ 工序c，d，e是平行工序，它们的紧前工序都是a与b。 a b e d c 网络图网络图需正确表示工序之间的前行后继关系，工序之间的逻辑关系的分解图归纳如下：（1）a完成后进行b和c a b c (2) a,b均完成后进行c a b c 网络图（3）a，b均完成后进行c和d a b c d (4) a完成后进行c，a,b完成后进行d a c b d 网络图 a d c b e (5) a完成后进行b， c完成后进行e; a,c完成后进行d 虚工序：只表示相邻工作之间的逻辑关系，不占用资源的虚设工序。网络图 (6) a,b 均完成后进行c ；b,d 均完成后进行e a c b d e 由工序、事项及标有完成各道工序所需时间等参数所构成的图称为网络图（又称为工序流线图）。一般地，建立网络图分三步。第一步，任务的分解(建立工序明细表) ；第二步，绘制网络图；第三步，顺序编号。网络图实例例建造一座汽车库及引道的工程项目，从施工开始到全部结束需要多少时间？把整个工程分解成若干个环节-----工作；估算出每个环节所需要的时间-----工时；确定各个环节之间的相互联系，先做什么，后做什么，哪些可以同时施工------紧前、紧后、平行关系；汇总上述各点予以具体分析，计算，得总工期。将工作及所需要时间、各工作之间的关系整理成表----工作清单。网络图第一步工作，需要熟悉工程的人员与统筹工作人员一道才能完成，不在本书的讨论之列。下面举例说明后两步工作。 k ,m 4 清理现场，交工验收 n l 24 引道混凝土保养 m c 8 引道混凝土施工 l h , i , j 16 油漆 k g 12 装天花板 j f 4 装门 i f 10 装窗及边墙 h f 4 立房顶桁架 g d , e 4 立墙架 f c 24 车库混凝土地面保养 e b 16 预制墙及房顶的桁架 d a , b 6 车库地面施工 c ---- 10 备料 b --- 8 清理现场 a 紧前工序工时（天）工序名称代号网络图 a d c b e f l g i j k m n h 10 10 4 4 4 24 8 24 16 6 8 3 2 1 4 16 12 6 5 4 7 9 8 10 11 12 网络图 8 4 7 9 5 7 6 6 4 工序时间 G E、F C、D C、D B B A -- -- 紧前工序 I H G F E D C B A 工序例工序明细表如下图：网络图 D,7        A,4 B,6 C,6 E,5 G,7 F,9 H,4 I,8 1 2 3 4 5 6 A B C D E F G 作业代号 A B D E C F G 后续作业 BC DE F G F G -- 网络图例工序明细表如下图：代码 A B C D E F G 紧前工作 - - A C BC D EF 1 4 2 A B 3 5 6 7 C D E F G 2 8 3 12 4 4 3 例工序明细表如下图：网络图网络图分类按工时估计的性质分类：确定型网络图 ——每一工作的工时估计一个值概率型网络图 ——每一工作的工时估计三个值：最快可能完成工时、最可能完成工时、最慢可能完成工时网络图按网络图的综合程度分：总网络图多级网络图其它有时间坐标网络图无时间坐标网络图网络图关键路线 ——网络图中需时最长的路图中用红线或粗线、双线画出 1 4 2 A B 3 5 6 7 C D E F G 2 8 3 12 4 4 3 关键工作关键路线上的工作时间参数的计算工作所需时间事项最早、最迟时间工作的最早、最迟时间及时差等时间参数：时间参数的计算二、时间参数的计算工作时间t(i,j)的确定确定型：根据定额资料或统计资料确定工时概率型：三点时间估计法 a — 最快可能完成时间（最乐观时间） m — 最可能完成时间 b — 最慢可能完成时间（最悲观时间）方差估计时间参数的计算确定型：以前多次执行过的、有可靠的生产定额值的，可以一个确定的时间作为它的工时概率型：初次执行，无资料可循时间参数的计算事项的最早时间事项的最迟时间事项时间参数时间参数的计算 tE(i)—与事项j相邻的各紧前事项的最早时间 tL(j)—与事项i 相邻的各紧后事项的最迟时间工作的最早可能开工时间、最早可能完工时间工作的时间参数时间参数的计算工作的最迟必须开工时间、最迟必须完工时间时间参数的计算时差：工作的机动时间或富裕时间在不影响其紧后工作最迟必须开工时间的前提下，本工作可以推迟的时间时差工作的总时差时间参数的计算工作的单时差在不影响其紧后工作最早可能开工时间的前提下，本工作可以推迟的时间时间参数的计算时间参数的表上计算法 . 0 0 28 20 28 20 8   I 2 2 28 24 26 22 4   H 0 0 20 13 20 13 7   G 0 2 24 15 22 13 9   F 11 13 24 19 11 6 5   E 0 0 13 6 13 6 7   D 3 3 13 7 10 4 6   C 0 0 6 0 6 0 6   B 0 3 7 3 4 0 4   A r R LF LS EF ES t(i,j) j i 工序时间参数的计算三、网络计划的优化优化方法把串联工作改为平行工作或平行交叉工作利用时差有限资源的合理分配最低成本日程自学网络计划的优化运筹帷幄之中决胜千里之外存贮论 Introduction 存贮论（1）存贮问题及其基本概念（2）确定型存贮模型（3）单周期的随机型存贮模型本章主要内容：一、问题的提出存贮论水库蓄水问题生产用料问题商店存货问题 ………… ？？？存储是解决供需不协调的一种措施. 存贮论两方面的矛盾：短缺造成的损失和存储形成的费用作用：协调供需关系，平抑波动，保障供给问题：对于特定的需求模型，如何确定最佳补充周期和补充量。费用分析是基本的衡量标准 1915年美国经济学家哈里斯(Harris F.）对商业中的库存问题建立了一个简单模型，并求得了最优解，但未被人们注意。1918年威尔逊（Wilson )建立确定性库存模型，并重新得出了哈里斯的公式，被称为威尔逊公式。二次大战后开始研究随机性库存模型。50年代美国的经济学家们研究了最优存储策略... 二、发展概况存储论是研究最优存储策略的理论和方法。研究在不同需求、供货及到达等情况下，确定在什么时间点及一次提出多大批量的订货，使用于订购、存储和可能发生短缺的费用的总和为最少。存贮论存贮论三、存贮问题及其基本概念存贮系统是一个由补充、存贮、需求三个环节紧密构成的运行系统。存贮由于需求（输出）而减少，通过补充（输入）而增加，其中心可视为仓库。仓库 (库存量) 供给需求定购进货输出输入存贮论需求: 由于需求，从存贮中取出一定数量的存货，使存贮量减少，即存贮的输出。需求类型：间断的, 连续的; 确定性的, 随机性的连续需求 Q T W S 间断需求 Q T W S t0 存贮论补充(订货和生产)：由需求存货减少，必须加以补充，这是存贮的输入。拖后时间(订货时间): 补充存贮的时间或备货时间订货时间：可长，可短，确定性的, 随机性的存贮费用  存储费：占用资金利息\货物损坏支出等  订货费:  生产费: 生产准备费、材料费用与加工费  缺货费：缺货损失固定费用: 手续费\电信往来可变费用: 货物本身价格,运费 How Much? When ? 存贮策略存贮论存贮论主要解决存贮策略问题，即如下两个问题： 1．补充存贮物资时，每次补充数量(Q)是多少？ 2．应该间隔多长时间( T )来补充这些存贮物资？存贮策略存贮论库存策略：库存策略是指决定在什么情况下对存贮进行补充以及补充数量是多少。分类 t－循环策略（t，S）策略（s，S）策略存贮论 t－循环策略：不论现在库存数量为多少，每隔一个固定时间补充一个固定的存贮量Q。（t，S）策略：每隔一个固定的时间t补充一次，补充的数量以补足一个固定的贮存量S为准。（s，S）策略：库存余额为I，若I＞s，则不对库存进行补充；若I≤s，则对库存进行补充，数量Q＝s－I。存贮论存贮类型存储模型确定性存储模型随机性存储模型确定型存贮摸型: 如果存贮模型被模型中的需求、补充等一些数据为确定的数值时，称为确定型存贮摸型。随机型存贮模型：如果含有随机变量，称为随机型存贮模型。存贮论模型Ⅰ：不允许缺货，补充时间极短（经济订购批量 or ) 假设：需求是连续均匀的，即单位时间的需求量R为常数补充可以瞬时实现，即补充时间近似为零单位存贮费C1，单位缺货费C2=∞，订购费用C3；货物单价K 二、确定型存贮模型存贮论主要参数有：需求率： R 单位货物单位时间的存贮费： c1 每次订货费： c3 每次订货量： Q 这些量都是确定的、不变的数值。各参量之间的关系：订货量 Q 单位存贮费 c1 每次订购费 c3 越小存贮费用越小订货费用越大越大存贮费用越大订货费用越小存贮论研究目的： 1．补充存贮物资时，每次补充数量(Q)是多少？ 2．应该间隔多长时间( t )来补充这些存贮物资？使得总费用最少时间 t 0 t Q/2 存贮量 Q 存贮状态图 t t 采用t - 循环策略经济订货批量公式，简称EOQ 存贮论模型Ⅱ：允许缺货，补充时间较长需求是连续均匀的，即单位时间的需求量R为常数。补充需要一定时间。只考虑生产时间，生产连续均匀的，即生产速度P为常数。设P＞R 单位存贮费C1，单位缺货费C2，订购费C3。不考虑货物价值。存贮论模型Ⅱ的最优存贮策略各参数值最优存贮周期经济生产批量平均总费用存贮论缺货补足时间开始生产时间结束生产时间最大存贮量最大缺货量模型Ⅱ的最优存贮策略各参数值存贮论最优存贮周期经济生产批量结束生产时间最大存贮量平均总费用模型Ⅲ：不允许缺货，补充时间较长存贮论最优存贮周期经济生产批量生产时间模型Ⅳ：允许缺货，补充时间极短存贮论最大存贮量最大缺货量平均总费用模型Ⅳ：允许缺货，补充时间极短存贮论在前面讨论的模型中，我们把需求看成是固定不变的已知常量。但是，在现实世界中，更多的情况却是需求为一个随机变量。为此，在本节中我们将介绍需求是随机变量，特别是需求服从均匀分布和正态分布这两种简单情况的存贮模型。典型的单周期存储模型是“报童问题”（Newsboy Problem），它是由报童卖报演变而来的，在存储论和供应链的研究中有广泛地应用。三、单周期的随机性存贮模型存贮论基本的订货策略按决定是否订货的条件划分：订购点订货法、定期订货法按订货量的决定方法划分：定量订货法、补充订货法存贮论单周期的存贮模型：周期中只能提出一次订货发生短缺时也不允许再提出订货周期结束后，剩余货可以处理存贮策略的优劣，通常以赢利的期望值的大小作为衡量标准存贮论例：某商店拟出售一批日历画片，每售出一千张可赢利700元。如果在新年期间不能售出，必须削价处理。由于削价，一定可以售完，此时每千张赔损400元。根据以往经验，市场需求的概率见表：每年只能订货一次，问应订购日历画片几千张才能使获利的期望值最大？存贮论概率P(r) 5 4 3 2 1 0 需求量(千张) 解：如果该店订货4千张，可能获利的数值存贮论 (-400)×0+700×4=2800 5 (-400)×0+700×4=2800 4 (-400)×1+700×3=1700 3 (-400)×2+700×2=600 2 (-400)×3+700=-500 1 (-400)×4=-1600 0 获利 (元) 市场需求(千张) 订购量为4千张时获利的期望值 E［C(4)］=(-16) × + (-5) × + 6× + 17× + 28 × +28 ×=（元）存贮论 1025 3500 2400 1300 200 -900 -2000 5 1315 2800 2800 1700 600 -500 -1600 4 1440* 2100 2100 2100 1000 -100 -1200 3 1180 1400 1400 1400 1400 300 -800 2 645 700 700 700 700 700 -400 1 0 0 0 0 0 0 0 0 获利期望值 5 4 3 2 1 0 需求量获利订货量存贮论该店订购3千张日历画片获利期望值最大本例也可从相反的角度考虑求解，即计算损失期望值最小的办法求解当订货量为Q时，可能发生滞销赔损（供大于求）缺货损失（供小于求）因缺货而失去销售机会的损失存贮论当该店订购量为2千张时，损失的可能值供货大于需求时滞销损失市场需求量为0时滞销损失 (-400)×2=-800 (元) 市场需求量为1时滞销损失 (-400)×1=-400 (元) 市场需求量为2时滞销损失 0 (元) 供货小于需求时缺货损失市场需求量为3时缺货损失 (-700)×1=-700 (元) 市场需求量为4时缺货损失 (-700)×2=-1400 (元) 市场需求量为5时缺货损失 (-700)×3=-2100 (元) 存贮论当订购量为2千张时，滞销和缺货两种损失之和的期望值 E［C(2)］=(-800) × + (-400) ×+ 0× + (-700)× + (-1400) ×+(-2100)×=-745（元）存贮论 -900 -610 -485* -745 -1280 -1925 损失的期望值 5 4 3 2 1 0 订货量（千张）该店订购3千张可使损失的期望值最小。结论同前说明对同一问题可从两个不同的角度考虑：获利最大、损失最小存贮论典型例—报童问题：报童每天售出的报纸份数r是一个离散随机变量，每天售出 r 份报纸的概率为P(r) (根据经验已知) ，且  p(r)=1；每售出一份报纸能赚K元；如售剩报纸，每剩一份赔h元。问报童每天应准备多少份报纸？模型Ⅵ：需求是离散随机变量存贮论设报童每天准备Q份报纸。采用损失期望值最小准则确定Q 供过于求(r≤Q),因售剩而遭到的损失期望值供不应求(r＞Q),因失去销售机会而少赚钱的损失期望值总的损失期望值存贮论边际分析法（略）记 N称为损益转折概率如采用获利期望值最大准则，确定最佳订购量Q*，结果同上。（略）最佳订购量Q*的确定：存贮论利用公式解上例应订购日历画片3千张存贮论一般情况下有 P(r<Q*) ≤ k/(k+h) ≤ P(r≤Q*) 可以推出： P(r≤Q*) ＝ k/(k+h) 均匀分布 U[a, b] 情况: P(r≤Q*) = (Q*-a)/(b-a) = k/(k+h) 正态分布 N( ) 情况： P(r≤Q*) = Q* = k/(k+h) 存贮论例：某种报纸出售：k=15元／百张，未售赔付：h=20元／百张，销售概率：问题：每日订购多少张报纸可使赚钱的期望值最高？最优订货量 Q*=8百张，赚钱的期望值最大。存贮论概率 P(r) 5 6 7 8 9 10 11 销售量(r) 解： k/(k+h) = 15/(15+20) = ，Q = 8 时例：新年挂历，出售赢利：k = 20／本，年前未售出赔付：h = 16元／本，市场需求近似服从均匀分布 U[550, 1100]。问：该书店应订购多少本新年挂历，可使损失期望值最小？存贮论解：均匀分布 U[a, b] 情况: P(r≤Q*) = (Q*-a)/(b-a) =(Q*-550) / 550 = k/(k+h) = 20 / (20+16) 所以，Q* = 856(本)，且挂历有剩余的概率为5／9，挂历脱销的概率为4／9。例液体化工产品，需求近似服从正态分布 N(1000, 1002)。有关数据如下：售价 20元／kg，生产成本15元／kg；需求不足时高价购买19元／kg；多余处理价5元／kg。问生产量为多少时，可使获利期望值最大？解 k=(20-15)-(20-19)=4元/kg(需求不足时损失） h = 15 - 5 = 10元／kg(生产过剩时的损失) 存贮论正态分布 N( ) 情况： P(d≤Q*) = Q* = k/(k+h)= 查表得 (Q*-1000)/100 = 所以，Q* = 944(kg)，且产品有剩余的概率为，缺货的概率为。存贮论（3）在第二张中x7已出基，故没有计算第七列的数值，同理，第三、四张表中x6、x7都已出基，故第六、七列没有计算；（4）第三、四张表中的基变量没有人工变量x6、x7，因而检验数中不含M；（5）可以看出，人工变量是帮助我们寻求原问题的可行基，第三张表就找到了原问题的一组基变量x2、x5、x3，此时人工变量就可以从模型中退出，也说明原规划有可行解，但不能肯定有最优解。（3）在第二张中x7已出基，故没有计算第七列的数值，同理，第三、四张表中x6、x7都已出基，故第六、七列没有计算；（4）第三、四张表中的基变量没有人工变量x6、x7，因而检验数中不含M；（5）可以看出，人工变量是帮助我们寻求原问题的可行基，第三张表就找到了原问题的一组基变量x2、x5、x3，此时人工变量就可以从模型中退出，也说明原规划有可行解，但不能肯定有最优解。（3）在第二张中x7已出基，故没有计算第七列的数值，同理，第三、四张表中x6、x7都已出基，故第六、七列没有计算；（4）第三、四张表中的基变量没有人工变量x6、x7，因而检验数中不含M；（5）可以看出，人工变量是帮助我们寻求原问题的可行基，第三张表就找到了原问题的一组基变量x2、x5、x3，此时人工变量就可以从模型中退出，也说明原规划有可行解，但不能肯定有最优解。（3）在第二张中x7已出基，故没有计算第七列的数值，同理，第三、四张表中x6、x7都已出基，故第六、七列没有计算；（4）第三、四张表中的基变量没有人工变量x6、x7，因而检验数中不含M；（5）可以看出，人工变量是帮助我们寻求原问题的可行基，第三张表就找到了原问题的一组基变量x2、x5、x3，此时人工变量就可以从模型中退出，也说明原规划有可行解，但不能肯定有最优解。（3）在第二张中x7已出基，故没有计算第七列的数值，同理，第三、四张表中x6、x7都已出基，故第六、七列没有计算；（4）第三、四张表中的基变量没有人工变量x6、x7，因而检验数中不含M；（5）可以看出，人工变量是帮助我们寻求原问题的可行基，第三张表就找到了原问题的一组基变量x2、x5、x3，此时人工变量就可以从模型中退出，也说明原规划有可行解，但不能肯定有最优解。为了找到一个省料的套裁方案，必须先设计出较好的几个下料方案。设xi表示第i班次时开始上班的司机和乘务人员人数。因为这样可以知道在第i班工作的人数应包括第i－1班次时开始上班的人数和第i班次开始上班的人数。如有x1＋x2>=70。也许有人会马上回答，定价愈高，收益愈大，故必是最佳决策。然而这是错误的，因为定价太高，势必失去顾客，从而也必减少收益，在市场竞争的时代，厂长的最佳决策显然应符合两条：直接去看是原问题，将它转900看便是对偶问题。当然，对偶是相互的，若把表转900看成是问题，则原表亦可看成是相应的对偶问题。运输问题的数学模型，包含有m×n个变量，（m＋n）个约束条件。由于∑ai＝ ∑bj，所以系数矩阵中线性独立的列向量的最大个数为m+n-1个，即运输问题的解中基变量的个数一般为m+n-1。运输问题的数学模型，包含有m×n个变量，（m＋n）个约束条件。由于∑ai＝ ∑bj，所以系数矩阵中线性独立的列向量的最大个数为m+n-1个，即运输问题的解中基变量的个数一般为m+n-1。运输问题的数学模型，包含有m×n个变量，（m＋n）个约束条件。由于∑ai＝ ∑bj，所以系数矩阵中线性独立的列向量的最大个数为m+n-1个，即运输问题的解中基变量的个数一般为m+n-1。运输问题的数学模型，包含有m×n个变量，（m＋n）个约束条件。由于∑ai＝ ∑bj，所以系数矩阵中线性独立的列向量的最大个数为m+n-1个，即运输问题的解中基变量的个数一般为m+n-1。运输问题的数学模型，包含有m×n个变量，（m＋n）个约束条件。由于∑ai＝ ∑bj，所以系数矩阵中线性独立的列向量的最大个数为m+n-1个，即运输问题的解中基变量的个数一般为m+n-1。运输问题的数学模型，包含有m×n个变量，（m＋n）个约束条件。由于∑ai＝ ∑bj，所以系数矩阵中线性独立的列向量的最大个数为m+n-1个，即运输问题的解中基变量的个数一般为m+n-1。运输问题的数学模型，包含有m×n个变量，（m＋n）个约束条件。由于∑ai＝ ∑bj，所以系数矩阵中线性独立的列向量的最大个数为m+n-1个，即运输问题的解中基变量的个数一般为m+n-1。当一个运输问题的产地和销地数量很多时，用位势法计算检验数比较简单。目标约束是将目标和约束结合在一起的表达式。对各目标约束中的正负偏差变量按顺序编号。 “哥尼斯堡 7 桥”难题最终在 1736 年由数学家 Euler 的一篇论文给予了完满的解决，这是图论的第一篇论文。在后来的两百年间图论的发展是缓慢的，直到 1936 年匈牙利数学家 önig写出了图论的第一本专著《有限图与无限图的理论》。图论的历史上最具有传奇色彩的问题也许要数著名的“四色猜想”了——历史上许许多多数学猜想之一。世界近代三大数学难题：费马最后猜想、哥德巴赫猜想和“四色”猜想。它描述对一张地图着色的问题，在一维直线上用两种颜色可以区分任意多不同线段，在二维平面内至少需要四种颜色可以区分任意多区域（当然最简单的情况是二色，如国际象棋棋盘）；在三维空间内至少需要八种颜色可以区分任意多的立体，（最简单的情况还是二色，如NaCl） “哥尼斯堡 7 桥”难题最终在 1736 年由数学家 Euler 的一篇论文给予了完满的解决，这是图论的第一篇论文。在后来的两百年间图论的发展是缓慢的，直到 1936 年匈牙利数学家 önig写出了图论的第一本专著《有限图与无限图的理论》。图论的历史上最具有传奇色彩的问题也许要数著名的“四色猜想”了——历史上许许多多数学猜想之一。世界近代三大数学难题：费马最后猜想、哥德巴赫猜想和“四色”猜想。它描述对一张地图着色的问题，在一维直线上用两种颜色可以区分任意多不同线段，在二维平面内至少需要四种颜色可以区分任意多区域（当然最简单的情况是二色，如国际象棋棋盘）；在三维空间内至少需要八种颜色可以区分任意多的立体，（最简单的情况还是二色，如NaCl） “哥尼斯堡 7 桥”难题最终在 1736 年由数学家 Euler 的一篇论文给予了完满的解决，这是图论的第一篇论文。在后来的两百年间图论的发展是缓慢的，直到 1936 年匈牙利数学家 önig写出了图论的第一本专著《有限图与无限图的理论》。图论的历史上最具有传奇色彩的问题也许要数著名的“四色猜想”了——历史上许许多多数学猜想之一。世界近代三大数学难题：费马最后猜想、哥德巴赫猜想和“四色”猜想。它描述对一张地图着色的问题，在一维直线上用两种颜色可以区分任意多不同线段，在二维平面内至少需要四种颜色可以区分任意多区域（当然最简单的情况是二色，如国际象棋棋盘）；在三维空间内至少需要八种颜色可以区分任意多的立体，（最简单的情况还是二色，如NaCl）在图与网络分析的应用中，将面临一个问题——如何分析、计算一个较大型的网络，这当然需借助快速的计算工具——计算机。那么，如何将一个图表示在计算机中。

联系我们

智库文档公众号

客服微信

运筹学.ppt

下载

标签

联系我们

意见反馈