运筹学通用课件--运筹学完整通用课件

《运筹学通用课件--运筹学完整通用课件》由会员分享，可在线阅读，更多相关《运筹学通用课件--运筹学完整通用课件（359页珍藏版）》请在金锄头文库上搜索。

1、2024/9/7运筹学运运 筹筹 学学( Operations Research )任课教师：黄得建任课教师：黄得建任课教师：黄得建任课教师：黄得建开课单位：开课单位：开课单位：开课单位：理工学院理工学院理工学院理工学院联系方式：联系方式：联系方式：联系方式：13876508165 13876508165 E-mail : E-mail : 经济学核心课程经济学核心课程经济学核心课程经济学核心课程2024/9/7运筹学绪绪 论论（1）运筹学简述）运筹学简述（2）运筹学的主要内容）运筹学的主要内容（3）本课程的教材及参考书）本课程的教材及参考书（4）本课程的特点和要求）本课程的特点和要求（5）本

2、课程授课方式与考核）本课程授课方式与考核 （6）运筹学在工商管理中的应用）运筹学在工商管理中的应用本章主要内容：本章主要内容：Page 32024/9/7运筹学运筹学简述运筹学简述运筹学（运筹学（Operations Research）系系统工程的最重要的理工程的最重要的理论基基础之一，在美国有人把运筹之一，在美国有人把运筹学称之学称之为管理科学管理科学(Management Science)。运筹学所研究的。运筹学所研究的问题，可，可简单地地归结为一句一句话：“依照依照给定条件和目定条件和目标，从众多方案中，从众多方案中选择最佳方案最佳方案”故有人称之故有人称之为最最优化技化技术。Page

3、42024/9/7运筹学运筹学简述运筹学简述运筹学的运筹学的历史史“运作研究运作研究(Operational Research)小组小组”:解决解决复杂的战略和战术问题。例如：复杂的战略和战术问题。例如：1.如何合理运用雷达有效地对付德军的空袭如何合理运用雷达有效地对付德军的空袭2.对商船如何进行编队护航，使船队遭受德国潜对商船如何进行编队护航，使船队遭受德国潜艇攻击时损失最少；艇攻击时损失最少；3.在各种情况下如何调整反潜深水炸弹的爆炸深在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等。度，才能增加对德国潜艇的杀伤力等。Page 52024/9/7运筹学运筹学的主要内

4、容运筹学的主要内容数学数学规划（划（线性性规划、整数划、整数规划、目划、目标规划划、动态规划等）划等）图论存存储论排排队论对策策论排序与排序与统筹方法筹方法决策分析决策分析Page 62024/9/7运筹学本课程的教材及参考书本课程的教材及参考书选用教材用教材 运筹学基础及应用胡运权主编（第5版） 高等教育出版社参考教材参考教材运筹学教程胡运权主编 （第2版）清华出版社管理运筹学韩伯棠主编 （第2版）高等教育出版社运筹学(修订版) 钱颂迪主编 清华出版社Page 72024/9/7运筹学 本课程的特点和要求本课程的特点和要求先修课：先修课：高等数学，基础概率、线性代数高等数学，基础概率、线性代

5、数特点：特点：系统整体优化；多学科的配合；模型方法的应用系统整体优化；多学科的配合；模型方法的应用运筹学的研究的主要步骤：运筹学的研究的主要步骤：真实系统真实系统系统分析系统分析问题描述问题描述模型建立模型建立与修改与修改模型求解模型求解与检验与检验结果分析与结果分析与实施实施数据准备数据准备Page 82024/9/7运筹学本课程授课方式与考核本课程授课方式与考核学科总成绩学科总成绩平时成绩平时成绩（4040）课堂考勤课堂考勤（5050）平时作业平时作业（5050）期末成绩期末成绩（6060）讲授为主，结合习题作业讲授为主，结合习题作业Page 92024/9/7运筹学运筹学在工商管理中的应

6、用运筹学在工商管理中的应用运筹学在工商管理中的运筹学在工商管理中的应用涉及几个方面：用涉及几个方面：1. 生产计划2. 运输问题3. 人事管理4. 库存管理5. 市场营销6. 财务和会计另外，另外，还应用于用于设备维修、更新和可靠性分析，修、更新和可靠性分析，项目的目的选择与与评价，工程价，工程优化化设计等。等。2024/9/7运筹学Chapter1 线性规划线性规划 (Linear Programming) LP的数学模型的数学模型 图解法图解法 单纯形法单纯形法 单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法 LP模型的应用模型的应用本章主要内容：本章主要内容：本章主要内容：

7、本章主要内容：Page 112024/9/7运筹学线性规划问题的数学模型线性规划问题的数学模型1. 规划划问题生产和经营管理中经常提出如何合理安排，使人力、生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。这就是规划问题。线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：（1 1）当任务或目标确定后，如何统筹兼顾，合理安排，用）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源最少的资源 （如资金、设备、原标材料、人工、

8、时间等）（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标去完成确定的任务或目标（2 2）在一定的资源条件限制下，如何组织安排生产获得最）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多好的经济效益（如产品量最多 、利润最大、利润最大. .）Page 122024/9/7运筹学线性规划问题的数学模型线性规划问题的数学模型例例1.1 如如图所示，如何截取所示，如何截取x使使铁皮所皮所围成的容成的容积最最大？大？ x xa aPage 132024/9/7运筹学线性规划问题的数学模型线性规划问题的数学模型例例1.2 某企业计划生产甲、乙两种产品。这些产品分某企业

9、计划生产甲、乙两种产品。这些产品分别要在别要在A、B、C、D、四种不同的设备上加工。按工、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？企业总的利润最大？ 设设 备备产产 品品 A B C D利润（元）利润（元） 甲甲 2 1 4 0 2 乙乙 2 2 0 4 3 有有 效效 台台 时时 12 8 16 12Page 142024/9/7运筹学线性规划问题的数学模型线性规划问题的数学模型解：解：设x1、x2分分别为

10、甲、乙两种甲、乙两种产品的品的产量，量，则数学模型数学模型为：max Z = 2xmax Z = 2x1 1 + 3x + 3x2 2 x x1 1 0 , x 0 , x2 2 0 0s.t.s.t. 2x 2x1 1 + 2x + 2x2 2 12 12 x x1 1 + 2x + 2x2 2 8 8 4x 4x1 1 16 16 4x 4x2 2 12 12Page 152024/9/7运筹学线性规划问题的数学模型线性规划问题的数学模型2. 2. 2. 2. 线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成决

11、策变量决策变量决策变量决策变量 Decision variables Decision variables 目标函数目标函数目标函数目标函数 Objective functionObjective function约束条件约束条件约束条件约束条件 ConstraintsConstraints其特征是：其特征是：其特征是：其特征是：（1 1 1 1）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的线性线性线性线性函数，函数，函数，函数，通常是求最大值或最小值；通常是求最大值或最小值；通常是求最大值或最小值；通常是求最大

12、值或最小值；（2 2 2 2）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的线性线性线性线性不不不不等式或等式。等式或等式。等式或等式。等式或等式。 怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？ Page 162024/9/7运筹学线性规划问题的数学模型线性规划问题的数学模型目标函数：目标函数：目标函数：目标函数：约束条件：约束条件：约束条件：约束条件：3. 3. 线性规划数学模型的一般形式线性规划数学模型的一般形式

13、线性规划数学模型的一般形式线性规划数学模型的一般形式简写为：简写为：Page 172024/9/7运筹学线性规划问题的数学模型线性规划问题的数学模型向量形式：向量形式：向量形式：向量形式：其中：其中：Page 182024/9/7运筹学线性规划问题的数学模型线性规划问题的数学模型矩阵形式：矩阵形式：矩阵形式：矩阵形式：其中：其中：Page 192024/9/7运筹学线性规划问题的数学模型线性规划问题的数学模型3. 线性性规划划问题的的标准形式准形式特点：特点：(1) 目标函数求最大值（有时求最小值）目标函数求最大值（有时求最小值）(2) 约束条件都为等式方程，且右端常数项约束条件都为等式方程，

14、且右端常数项bi都大于或等于零都大于或等于零(3) 决策变量决策变量xj为非负。为非负。Page 202024/9/7运筹学线性规划问题的数学模型线性规划问题的数学模型（2 2 2 2）如何化标准形式）如何化标准形式）如何化标准形式）如何化标准形式 目标函数的转目标函数的转换换 如果是求极小值即如果是求极小值即 ，则可将，则可将目标函数乘以目标函数乘以(-1)(-1)，可化为求极大值问题。，可化为求极大值问题。也就是：令也就是：令 ，可得到上式。，可得到上式。即即 若存在取值无约束的变量若存在取值无约束的变量 ，可令，可令 其中：其中： 变量的变变量的变换换Page 212024/9/7运筹学

15、线性规划问题的数学模型线性规划问题的数学模型 约束方程的转换：由不等式转换为等式。约束方程的转换：由不等式转换为等式。称为松弛变量称为松弛变量称为剩余变量称为剩余变量 变量变量 的的变换变换 可令可令 ，显然，显然Page 222024/9/7运筹学线性规划问题的数学模型线性规划问题的数学模型例例1.3 将下列线性规划问题化为标准形式将下列线性规划问题化为标准形式用用 替换替换 ，且，且 解解:（）因为（）因为x3无符号要求无符号要求 ，即，即x3取正值也可取负值，标准取正值也可取负值，标准型中要求变量非负，所以型中要求变量非负，所以Page 232024/9/7运筹学线性规划问题的数学模型线

16、性规划问题的数学模型(2) 第一个约束条件是第一个约束条件是“”号，在号，在“”左端加入松驰变左端加入松驰变量量x4，x40,化为等式；化为等式；(3) 第二个约束条件是第二个约束条件是“”号，在号，在“”左端减去剩余变左端减去剩余变量量x5，x50；(4) 第第3个约束方程右端常数项为个约束方程右端常数项为-5，方程两边同乘以，方程两边同乘以(-1),将将右端常数项化为正数；右端常数项化为正数； (5) 目标函数是最小值，为了化为求最大值，令目标函数是最小值，为了化为求最大值，令z=-z,得到得到max z=-z，即当，即当z达到最小值时达到最小值时z达到最大值，反之亦然达到最大值，反之亦然

17、;Page 242024/9/7运筹学线性规划问题的数学模型线性规划问题的数学模型标准形式如下：标准形式如下：Page 252024/9/7运筹学线性规划问题的数学模型线性规划问题的数学模型4. 4. 线性性规划划问题的解的解线性规划问题线性规划问题求解线性规划问题，就是从满足约束条件求解线性规划问题，就是从满足约束条件(2)、(3)的方程的方程组中找出一个解，使目标函数组中找出一个解，使目标函数(1)达到最大值。达到最大值。Page 262024/9/7运筹学线性规划问题的数学模型线性规划问题的数学模型 可行解可行解：满足约束条件：满足约束条件、的解为可行解。所有可行解的解为可行解。所有可行

18、解的集合为可行域。的集合为可行域。 最优解最优解：使目标函数达到最大值的可行解。：使目标函数达到最大值的可行解。 基：基：设设A为约束条件为约束条件的的mn阶系数矩阵阶系数矩阵(m04010换换出出行行将将3化为化为15/311801/301/31011/3303005/304/3乘乘以以1/3后后得得到到103/51/518011/52/540011Page 462024/9/7运筹学单纯形法的计算步骤单纯形法的计算步骤例例1.9 用用单纯形法求解形法求解解：将数学模型化为标准形式：解：将数学模型化为标准形式：不难看出不难看出x4、x5可作为初始基变量，列单纯形表计算。可作为初始基变量，列单

19、纯形表计算。Page 472024/9/7运筹学单纯形法的计算步骤单纯形法的计算步骤cj12100icB基变量基变量bx1x2x3x4x50x4152-32100x5201/31501121000x42x220x x2 22 21/3150120753017131/309022560x x1 111017/31/31250128/9-1/92/335/300-98/9 -1/9 -7/3Page 482024/9/7运筹学单纯形法的计算步骤单纯形法的计算步骤学习要点：学习要点：1. 线性规划解的概念以及线性规划解的概念以及3个基本定理个基本定理2. 熟练掌握单纯形法的解题思路及求解步骤熟练掌握

20、单纯形法的解题思路及求解步骤Page 492024/9/7运筹学单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法人工人工变量法：量法：前面前面讨论了在了在标准型中系数矩准型中系数矩阵有有单位矩位矩阵，很容易，很容易确定一确定一组基可行解。在基可行解。在实际问题中有些模型并不含有中有些模型并不含有单位位矩矩阵，为了得到一了得到一组基向量和初基可行解，在基向量和初基可行解，在约束条件的束条件的等式左端加一等式左端加一组虚虚拟变量，得到一量，得到一组基基变量。量。这种人种人为加加的的变量称量称为人工人工变量，构成的可行基称量，构成的可行基称为人工基，用大人工基，用大M M法法或两或两阶段

21、法求解，段法求解，这种用人工种用人工变量作量作桥梁的求解方法称梁的求解方法称为人工人工变量法。量法。Page 502024/9/7运筹学单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法例例1.10 用大用大M法解下列法解下列线性性规划划解：首先将数学模型化为标准形式解：首先将数学模型化为标准形式系数矩阵中不存在系数矩阵中不存在单位矩阵，无法建单位矩阵，无法建立初始单纯形表。立初始单纯形表。Page 512024/9/7运筹学单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法故人故人为添加两个添加两个单位向量，得到人工位向量，得到人工变量量单纯形法数学模型：形法数学模型：其

22、其中中：M是是一一个个很很大大的的抽抽象象的的数数，不不需需要要给给出出具具体体的的数数值值，可可以以理理解解为为它它能能大大于于给给定定的的任任何何一一个个确确定定数数值值；再再用用前前面面介介绍的单纯形法求解该模型，计算结果见下表。绍的单纯形法求解该模型，计算结果见下表。 Page 522024/9/7运筹学单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7i-Mx64-431-101040x5101-1201005-Mx712-21000113-2M2+M-1+2M-M0x63-650-1013/5-Mx58-330

23、0108/3-1x312-210005-6M5M0-M002x23/56/5101/50-Mx531/53/5003/5131/3-1x311/52/5012/505 00002x213010123x131/310015/3-1x319/300102/3000-5-25/3Page 532024/9/7运筹学单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法解的判别：解的判别：1）唯一最优解判别：最优表中所有非基变量的检验数非零）唯一最优解判别：最优表中所有非基变量的检验数非零,则线则线 规划具有唯一最优解。规划具有唯一最优解。2）多重最优解判别：最优表中存在非基变量的检验数为零）多

24、重最优解判别：最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解（或无穷多最优解）。则线则性规划具有多重最优解（或无穷多最优解）。3）无界解判别：某个）无界解判别：某个k0且且aik（i=1，2,m）则线性）则线性规划具有无界解。规划具有无界解。4）无无可可行行解解的的判判断断：当当用用大大M单单纯纯形形法法计计算算得得到到最最优优解解并并且存在且存在Ri0时，则表明原线性规划无可行解。时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基本可行解。）退化解的判别：存在某个基变量为零的基本可行解。Page 542024/9/7运筹学单纯形法的进一步讨论人工变量法单纯形

25、法的进一步讨论人工变量法单纯性法小性法小结:建建立立模模型型个个 数数取取 值值右右 端端 项项等式或等式或不等式不等式极大或极小极大或极小新加变量新加变量系数系数两两个个三个三个以上以上xj0xj无无约束约束xj 0 bi 0bi mi 时，企业愿意时，企业愿意购进这种资源，单位纯利为购进这种资源，单位纯利为yi*mi ，则有利可图；如果，则有利可图；如果yi* mi 则购进资源则购进资源i，可获单位纯利，可获单位纯利yi*mi 若若yi* mi则转让资源则转让资源i ，可获单位纯利，可获单位纯利miyiPage 972024/9/7运筹学对偶问题的经济解释影子价格对偶问题的经济解释影子价格

26、3）影子价格在）影子价格在资源利用中的源利用中的应用用根据根据对偶理偶理论的互的互补松弛性定理松弛性定理:Y*Xs=0 , YsX*=0表明生表明生产过程中如果某种程中如果某种资源源bi未得到充分利用未得到充分利用时，该种种资源的影子价格源的影子价格为0；若当；若当资源源资源的影子价格不源的影子价格不为0时，表明，表明该种种资源在生源在生产中已耗中已耗费完。完。Page 982024/9/7运筹学对偶问题的经济解释影子价格对偶问题的经济解释影子价格4）影子价格）影子价格对单纯形表形表计算的解算的解释单纯形表中的检验数单纯形表中的检验数其中其中c cj j表示第表示第j j种产品的价格种产品的价

27、格; ; 表示生产该表示生产该种产品所消耗的各项资源的影子价格的总和种产品所消耗的各项资源的影子价格的总和, ,即产品的隐含即产品的隐含成本。成本。当产值大于隐含成本时，即当产值大于隐含成本时，即 ，表明生产该项产，表明生产该项产品有利，可在计划中安排；否则品有利，可在计划中安排；否则 ，用这些资源，用这些资源生产别的产品更有利，不在生产中安排该产品。生产别的产品更有利，不在生产中安排该产品。Page 992024/9/7运筹学对偶单纯形法对偶单纯形法 对偶单纯形法是求解线性规划的另一个基本方法。对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称它是

28、根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。形法。对偶单纯形法原理对偶单纯形法原理对偶单纯形法原理对偶单纯形法原理对偶单纯形法基本思路：对偶单纯形法基本思路：对偶单纯形法基本思路：对偶单纯形法基本思路： 找出一个对偶问题的可行基，保持对偶问题为可行解的找出一个对偶问题的可行基，保持对偶问题为可行解的条件下，判断条件下，判断XB是否可行（是否可行（XB为非负），若否，通过变换基为非负），若否，通过变换基解，直到找到原问题基可行解（即解，直到找到原问题基可行解（即XB为非负），这时原问题为非

29、负），这时原问题与对偶问题同时达到可行解，由定理与对偶问题同时达到可行解，由定理4可得最优解。可得最优解。Page 1002024/9/7运筹学对偶单纯形法对偶单纯形法找出一个找出一个DP的可行基的可行基LP是否可行是否可行（XB 0）保持保持DP为可行解情况下转移到为可行解情况下转移到LP的另一个基本解的另一个基本解最优解最优解是是否否循循环环结束结束Page 1012024/9/7运筹学对偶单纯形法对偶单纯形法例例2.9 用对偶单纯形法求解：用对偶单纯形法求解：解解:（1）将模型转化为求最大化问题，约束方程化为等式求将模型转化为求最大化问题，约束方程化为等式求出一组基本解，因为对偶问题可行

30、，即全部检验数出一组基本解，因为对偶问题可行，即全部检验数0（求（求max问题）。问题）。Page 1022024/9/7运筹学对偶单纯形法对偶单纯形法cj-9-12-15000bcBxBx1x2x3x4x5x60x4-2-2-1100-100x5-2-3-1010-120x6-1-1-5001-14(-9/-1.-12/-1. -15/-5)j-9-12-150000Page 1032024/9/7运筹学对偶单纯形法对偶单纯形法cj-9-12-15000bcBxBx1x2x3x4x5x60x4-9/5-9/5010-1/5-36/50x5-9/5-14/5001-1/5-46/5-15x31

31、/51/5100-1/514/5(-30/-9,-45/-14,-15/-1)-6-9000-342cj-9-12-15000bcBxBx1x2x3x4x5x60x4-9/14001-9/14-1/14-9/7-12x29/14100-5/141/1423/7(-3/-9,-45/-9,-33/-1)-15x31/140101/14-3/1415/7-3/14000-45/14-33/14Page 1042024/9/7运筹学对偶单纯形法对偶单纯形法cj-9-12-15000cBxBx1x2x3x4x5x6b-9x1100-14/911/92-12x20101-102-15x30011/90-

32、2/92000-1/3-3-7/3原问题的最优解为：原问题的最优解为：X*=（2 , 2 , 2 , 0 , 0 , 0），），Z* =72 其对偶问题的最优解为：其对偶问题的最优解为：Y*= （1/3 , 3 , 7/3），），W*= 72Page 1052024/9/7运筹学对偶单纯形法对偶单纯形法 对偶单纯形法应注意的问题：对偶单纯形法应注意的问题： 用用对对偶偶单单纯纯形形法法求求解解线线性性规规划划是是一一种种求求解解方方法法，而而不不是是去去求求对对偶问题的最优解偶问题的最优解 初初始始表表中中一一定定要要满满足足对对偶偶问问题题可可行行，也也就就是是说说检检验验数数满满足足最最优

33、优判别准则判别准则 最小比值中最小比值中 的绝对值是使得比值非负，在极小化问题的绝对值是使得比值非负，在极小化问题j j00，分母，分母a aijij0 0 这时必须取绝对值。在极大化问题中，这时必须取绝对值。在极大化问题中， j j00，分母，分母a aijij00， 总满足非负，这时绝对值符号不起作用，总满足非负，这时绝对值符号不起作用，可以去掉。如在本例中将目标函数写成可以去掉。如在本例中将目标函数写成这里这里j j 0 0在求在求k k时就可以不带绝对值符号。时就可以不带绝对值符号。Page 1062024/9/7运筹学对偶单纯形法对偶单纯形法 对对偶偶单单纯纯形形法法与与普普通通单单

34、纯纯形形法法的的换换基基顺顺序序不不一一样样，普普通通单单纯纯形形法法是是先先确确定定进进基基变变量量后后确确定定出出基基变变量量，对对偶偶单单纯纯形形法法是是先先确确定定出出基基变变量后确定进基变量；量后确定进基变量； 普通单纯形法的最小比值是普通单纯形法的最小比值是 其目的是保证下一个原问题的基本解可行，对偶单纯形法的最小比其目的是保证下一个原问题的基本解可行，对偶单纯形法的最小比值是值是其目的是保证下一个对偶问题的基本解可行其目的是保证下一个对偶问题的基本解可行 对偶单纯形法在确定出基变量时，若不遵循对偶单纯形法在确定出基变量时，若不遵循 规规则则，任任选选一一个个小小于于零零的的b b

35、i i对对应应的的基基变变量量出出基基，不不影影响响计计算算结结果果，只是迭代次数可能不一样。只是迭代次数可能不一样。Page 1072024/9/7运筹学本章小结本章小结学习要点：学习要点：1. 线性规划解的概念以及线性规划解的概念以及3个基本定理个基本定理2. 熟练掌握单纯形法的解题思路及求解步骤熟练掌握单纯形法的解题思路及求解步骤2024/9/7运筹学Chapter3 运输规划运输规划( Transportation Problem )( Transportation Problem )运输规划问题的数学模型运输规划问题的数学模型表上作业法表上作业法运输问题的应用运输问题的应用 本章主要

36、内容：本章主要内容：本章主要内容：本章主要内容：Page 1092024/9/7运筹学运输规划问题的数学模型运输规划问题的数学模型例例3.1 某公司从两个某公司从两个产地地A1、A2将物品运往三个将物品运往三个销地地B1, B2, B3，各，各产地的地的产量、各量、各销地的地的销量和各量和各产地运往各地运往各销地地每件物品的运每件物品的运费如下表所示，如下表所示，问：应如何如何调运可使运可使总运运输费用最小？用最小？B1B2B3产量产量A1646200A2655300销量销量150150200Page 1102024/9/7运筹学运输规划问题的数学模型运输规划问题的数学模型解：解：产销平衡平衡

37、问题：总产量量 = 总销量量500 设 xij 为从从产地地Ai运往运往销地地Bj的运的运输量，得到下列运量，得到下列运输量量表：表：B1B2B3产量产量A1x11x12x13200A2x21x22x23300销量销量150150200Min C = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. 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）Page 1112024/9/7运筹

38、学运输规划问题的数学模型运输规划问题的数学模型运运输问题的一般形式：的一般形式：产销平衡平衡A1、 A2、 Am 表示某物资的表示某物资的m个产地；个产地； B1、B2、Bn 表示表示某物质的某物质的n个销地；个销地；ai 表示产地表示产地Ai的产量；的产量； bj 表示销地表示销地Bj 的销量；的销量； cij 表示把物资从产地表示把物资从产地Ai运往销地运往销地Bj的单位运价。设的单位运价。设 xij 为从产地为从产地Ai运往销地运往销地Bj的运输量，得到下列一般运输量问题的模型：的运输量，得到下列一般运输量问题的模型：Page 1122024/9/7运筹学运输规划问题的数学模型运输规划问

39、题的数学模型变化：变化： 1）有时目标函数求最大。如求利润最大或营业额最大等；）有时目标函数求最大。如求利润最大或营业额最大等； 2）当某些运输线路上的能力有限制时，在模型中直接加入）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束约束条件（等式或不等式约束)； 3）产销不平衡时，可加入假想的产地（销大于产时）或销）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。地（产大于销时）。定理定理: 设有有m个个产地地n个个销地且地且产销平衡的运平衡的运输问题，则基基变量数量数为m+n-1。Page 1132024/9/7运筹学表上作业法表上作业法表上作表上

40、作业法是一种求解运法是一种求解运输问题的特殊方法，其的特殊方法，其实质是是单纯形法。形法。步骤步骤描述描述方法方法第一步第一步求初始基行可行解（初始调运方案）求初始基行可行解（初始调运方案）最小元素法、最小元素法、元素差额法、元素差额法、第二步第二步求检验数并判断是否得到最优解当非基变量的求检验数并判断是否得到最优解当非基变量的检验数检验数ijij全都非负时得到最优解，若存在检验全都非负时得到最优解，若存在检验数数ij ij 00，说明还没有达到最优，转第三步。，说明还没有达到最优，转第三步。闭回路法和位闭回路法和位势法势法第三步第三步调整运量，即换基，选一个变量出基，对原运调整运量，即换基，

41、选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步量进行调整得到新的基可行解，转入第二步Page 1142024/9/7运筹学表上作业法表上作业法例例3.2 3.2 某运输资料如下表所示：某运输资料如下表所示：单位单位 销地销地 运价运价 产地产地产量产量3 311113 310107 71 19 92 28 84 47 74 410105 59 9销量销量3 36 65 56 6问：应如何调运可使总运输费用最小？问：应如何调运可使总运输费用最小？Page 1152024/9/7运筹学表上作业法表上作业法解：第解：第1步步 求初始方案求初始方案方法方法1：最小元素法：最小元素法 基本

42、思想是就近供应，即从运价最小的地方开始供应（调运）基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。，然后次小，直到最后供完为止。B1B2B3B4产量产量A17A2 4A39销量销量3656311310192741058341633Page 1162024/9/7运筹学表上作业法表上作业法总的运输费总的运输费(31)+(64) +(43) +(12)+(310)+(35)=86元元元素差额法对最小元素法进行了改进，考虑到产地到销地元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小的最小运价和次小运价之间的差

43、额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案。运价先调运，否则会增加总运费。例如下面两种运输方案。85102120151515510总运费是总运费是z=108+52+151=105最小元素法：最小元素法：Page 1172024/9/7运筹学表上作业法表上作业法85102120151551510总运费总运费z=105+152+51=85后一种方案考虑到后一种方案考虑到C11与与C21之间之间的差额是的差额是82=6，如果不先调运，如果不先调运x21，到后来就有可能，到后来就有可能x110，这，这样会使总运费增加较大，从而先样会使总运费增加较大，从而先调运调运x2

44、1，再是，再是x22，其次是，其次是x12用元素差额法求得的基本可行解更接近最优解，所用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。以也称为近似方案。Page 1182024/9/7运筹学表上作业法表上作业法方法方法2：Vogel法法1）从运价表中分别计算出各行和各列的最小运费和次最小运）从运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。费的差额，并填入该表的最右列和最下行。B1B2B3B4产量产量行差额行差额行差额行差额A177 7A2 41 1A391 1销量销量3656列差额列差额列差额列差额2 25 51 13 3311310192

45、741058Page 1192024/9/7运筹学表上作业法表上作业法2）再从差值最大的行或列中找出最小运价确定供需关系和）再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量供应完毕或得到满足供需数量。当产地或销地中有一方数量供应完毕或得到满足时，划去运价表中对应的行或列。时，划去运价表中对应的行或列。重复重复1)和和2)，直到找出初始解为至。，直到找出初始解为至。B1B2B3B4产量产量行差额行差额行差额行差额A177 7A2 41 1A3 91 1销量销量3656列差额列差额列差额列差额2 25 51 13 33113101927410585 5Page 1

46、202024/9/7运筹学表上作业法表上作业法单位单位 销地销地 运价运价 产地产地产量产量行差额行差额311310719284741059销量销量3656列差额列差额71135215Page 1212024/9/7运筹学表上作业法表上作业法单位单位 销地销地 运价运价 产地产地产量产量行差额行差额311310719284741059销量销量3656列差额列差额71352753Page 1222024/9/7运筹学表上作业法表上作业法单位单位 销地销地 运价运价 产地产地产量产量行差额行差额311310719284741059销量销量3656列差额列差额11351536312该方案的总运费该方

47、案的总运费:(13)(46)(35)(210)(18)(35)85元元Page 1232024/9/7运筹学表上作业法表上作业法第第第第2 2步步步步 最优解的判别（检验数的求法）最优解的判别（检验数的求法）最优解的判别（检验数的求法）最优解的判别（检验数的求法）求求出出一一组组基基可可行行解解后后，判判断断是是否否为为最最优优解解，仍仍然然是是用用检检验验数数来来判判断断，记记xij的的检检验验数数为为ij由由第第一一章章知知，求求最最小小值值的的运运输问题的最优判别准则是：输问题的最优判别准则是：所有非基变量的检验数都非负，则运输方案最优所有非基变量的检验数都非负，则运输方案最优求检验数的

48、方法有两种：求检验数的方法有两种： 闭回路法闭回路法 位势法（位势法（）Page 1242024/9/7运筹学表上作业法表上作业法闭回路的概念回路的概念为一个闭回路为一个闭回路 ，集合中的变量称为回路的顶点，相邻两个变，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。如下表量的连线为闭回路的边。如下表Page 1252024/9/7运筹学表上作业法表上作业法例下表中例下表中闭回路的回路的变量集合是量集合是x11,x12,x42,x43,x23,x25,x35, x31共有共有8个个顶点，点，这8个个顶点点间用水平或垂直用水平或垂直线段段连接起来，接起来，组成一条封成一条封闭的回路。

49、的回路。 B1B2B3B4B5A1X11X12A2X23X25A3X31X35A4X42X43 一条回路中的顶点数一定是偶数，回路遇到顶点必须转一条回路中的顶点数一定是偶数，回路遇到顶点必须转90度与另一顶点连接，表度与另一顶点连接，表33中的变量中的变量x 32及及x33不是闭回路的顶不是闭回路的顶点，只是连线的交点。点，只是连线的交点。 Page 1262024/9/7运筹学表上作业法表上作业法闭回路回路B1B2B3A1X11X12A2A3X32X33A4X41X43例如变量组例如变量组 不能构成一条闭回路，不能构成一条闭回路，但但A中包含有闭回路中包含有闭回路 变量组变量组 变量数是奇数

50、，显然不变量数是奇数，显然不是闭回路，也不含有闭回路；是闭回路，也不含有闭回路； Page 1272024/9/7运筹学表上作业法表上作业法用位势法对初始方案进行最优性检验：用位势法对初始方案进行最优性检验：1）由）由 ij=Cij-（Ui+Vj）计算位势）计算位势Ui ， Vj ，因对基变量而言有，因对基变量而言有 ij=0，即，即Cij-（Ui+Vj） = 0，令，令U1=02）再由）再由 ij=Cij-（Ui+Vj）计算非基变量的检验数）计算非基变量的检验数 ijB1B2B3B4UiA1A2A3Vj3113101927410584363130 0-1-1-5-53 310102 29 9

51、（1 1）（2 2）（1 1）（-1-1）（1010）（1212）当存在非基当存在非基变量的检验变量的检验数数 kl 0，说，说明现行方案明现行方案为最优方案，为最优方案，否则目标成否则目标成本还可以进本还可以进一步减小。一步减小。Page 1282024/9/7运筹学表上作业法表上作业法当存在非基当存在非基变量的量的检验数数 kl 0 且且 kl =min ij时，令，令Xkl 进基。从表中知可基。从表中知可选X24进基。基。第第3步步 确定换入基的变量确定换入基的变量第第4步步 确定换出基的变量确定换出基的变量以进基变量以进基变量xik为起点的闭回路中，标有负号的最小运量作为为起点的闭回路

52、中，标有负号的最小运量作为调整量调整量，对应的基变量为出基变量，并打上对应的基变量为出基变量，并打上“”以示换以示换出作为非基变量。出作为非基变量。Page 1292024/9/7运筹学表上作业法表上作业法B1B2B3B4UiA1A2A3Vj3113 31010192 27410105 58 84 4363 31 13 3( () )( () )( () )( () )调整步骤为：调整步骤为：在进基变量的闭回路中标有正号的变量加上调整量在进基变量的闭回路中标有正号的变量加上调整量，标有负号的变量减去调整量，标有负号的变量减去调整量，其余变量不变，得到一组新的，其余变量不变，得到一组新的基可行解

53、。然后求所有非基变量的检验数重新检验。基可行解。然后求所有非基变量的检验数重新检验。1 12 25 5Page 1302024/9/7运筹学表上作业法表上作业法当所有非基变量的检验数均非负时，则当前调运方案即为最当所有非基变量的检验数均非负时，则当前调运方案即为最优方案，如表此时最小总运费：优方案，如表此时最小总运费：Z =(13)(46)(35)(210)(18)(35)85元元B1B2B3B4UiA1A2A3Vj3113101927410585363120 0-2-2-5-53 310103 39 9（0 0）（2 2）（2 2）（1 1）（1212）（9 9）Page 1312024/9

54、/7运筹学表上作业法表上作业法表上作表上作业法的法的计算步算步骤：分析实际问题列出产销平分析实际问题列出产销平衡表及单位运价表衡表及单位运价表确定初始调运方案（最小确定初始调运方案（最小元素法或元素法或Vogel法）法）求检验数（位势法）求检验数（位势法）所有检验数所有检验数0找出绝对值最大的负检验数，用闭合找出绝对值最大的负检验数，用闭合回路调整，得到新的调运方案回路调整，得到新的调运方案得到最优方案，得到最优方案，算出总运价算出总运价Page 1322024/9/7运筹学表上作业法表上作业法表上作业法计算中的问题：表上作业法计算中的问题：表上作业法计算中的问题：表上作业法计算中的问题：（1

55、）若运输问题的某一基可行解有多个非基变量的检验数）若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中任一变量为换入变量均可使为负，在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取目标函数值得到改善，但通常取ij0中最小者对应的变量为中最小者对应的变量为换入变量。换入变量。（2）无穷多最优解）无穷多最优解产销平衡的运输问题必定存最优解。如果非基变量的产销平衡的运输问题必定存最优解。如果非基变量的ij0，则该问题有无穷多最优解。，则该问题有无穷多最优解。Page 1332024/9/7运筹学表上作业法表上作业法 退化解：退化解： 表格中一般要有表格

56、中一般要有(m+n-1)个数字格。但有时在分配运量个数字格。但有时在分配运量时则需要同时划去一行和一列，这时需要补一个时则需要同时划去一行和一列，这时需要补一个0，以保证，以保证有有(m+n-1)个数字格作为基变量。一般可在划去的行和列的任个数字格作为基变量。一般可在划去的行和列的任意空格处加一个意空格处加一个0即可。即可。 利用进基变量的闭回路对解进行调整时，标有负号的利用进基变量的闭回路对解进行调整时，标有负号的最小运量（超过最小运量（超过2个最小值）作为调整量个最小值）作为调整量，选择任意一个最，选择任意一个最小运量对应的基变量作为出基变量，并打上小运量对应的基变量作为出基变量，并打上“

57、”以示作为以示作为非基变量。非基变量。Page 1342024/9/7运筹学表上作业法表上作业法 销地销地产地产地B1B2B3B4产量产量A116A210A322销量销量81412141241148310295116(0)(2)(9)(2)(1)(12)8 812124 42 28 81414如下例中如下例中11检验数是检验数是 0，经过调整，可得到另一个最优解。，经过调整，可得到另一个最优解。 Page 1352024/9/7运筹学表上作业法表上作业法 销地销地产地产地B1B2B3B4产量产量A17A24A39销量销量365620114431377821063 34 41 16 6 06 6

58、在在x12、x22、x33、x34中任选一个变量作为基变量，例如选中任选一个变量作为基变量，例如选x34例：用最小元素法求初始可行解例：用最小元素法求初始可行解Page 1362024/9/7运筹学运输问题的应用运输问题的应用1. 1. 求极大求极大求极大求极大值问题值问题目目标函数求利函数求利润最大或最大或营业额最大等最大等问题。Page 1372024/9/7运筹学运输问题的应用运输问题的应用求解方法：求解方法：将极大化将极大化问题转化化为极小化极小化问题。设极大化极大化问题的运价的运价表表为C ，用一个，用一个较大的数大的数M（Mmaxcij）去减每一个）去减每一个cij得得到矩到矩阵C

59、，其中，其中C=（Mcij）0,将将C作作为极小化极小化问题的运的运价表，用表上用价表，用表上用业法求出最法求出最优解。解。Page 1382024/9/7运筹学运输问题的应用运输问题的应用例例3.3 下下列列矩矩阵C是是Ai（I=1，2，3）到到Bj的的吨吨公公里里利利润,运运输部部门如何安排运如何安排运输方案使方案使总利利润最大最大. 销地销地产地产地B1B2B3产量产量A12 25 58 89 9A29 910107 71010A36 65 54 41212销量销量8 814149 9Page 1392024/9/7运筹学运输问题的应用运输问题的应用 销地销地产地产地B1B2B3产量产量

60、A12 25 58 89 9A29 910107 71010A36 65 54 41212销量销量8 814149 9得到新的最小化运输问题，用表上作业法求解即可。得到新的最小化运输问题，用表上作业法求解即可。Page 1402024/9/7运筹学运输问题的应用运输问题的应用2. 2. 产销产销不平衡的运不平衡的运不平衡的运不平衡的运输问题输问题当当总产量与量与总销量不相等量不相等时,称称为不平衡运不平衡运输问题.这类运运输问题在在实际中常常碰到中常常碰到,它的求解方法是将不平衡它的求解方法是将不平衡问题化化为平衡平衡问题再按平衡再按平衡问题求解。求解。 当产大于销时，即：当产大于销时，即：数

61、学模型为：数学模型为：Page 1412024/9/7运筹学运输问题的应用运输问题的应用由于由于总产量大于量大于总销量，必有部分量，必有部分产地的地的产量不能全部运送完，量不能全部运送完，必必须就地就地库存，即每个存，即每个产地地设一个一个仓库，假，假设该仓库为一个虚一个虚拟销地地Bn+1， bn+1作作为一个虚一个虚设销地地Bn+1的的销量量(即即库存量存量)。各。各产地地Ai到到Bn+1的运价的运价为零，即零，即Ci,n+1=0,（i=1，m）。）。则平衡平衡问题的的数学模型数学模型为：具体求解时具体求解时, ,只在只在运价表右端增加运价表右端增加一列一列B Bn n+1+1，运价为，运价

62、为零零, ,销量为销量为b bn n+1+1即即可可Page 1422024/9/7运筹学运输问题的应用运输问题的应用 当当销大于大于产时，即：，即：数学模型为：数学模型为：由于总销量大于总产由于总销量大于总产量量,故一定有些需求故一定有些需求地不完全满足地不完全满足,这时这时虚设一个产地虚设一个产地Am+1，产量为：产量为：Page 1432024/9/7运筹学运输问题的应用运输问题的应用销大于产化为平衡问题的数学模型为销大于产化为平衡问题的数学模型为 ：具体计算时，在运价表的下方增加一行具体计算时，在运价表的下方增加一行Am+1，运价为零。产，运价为零。产量为量为am+1即可。即可。 Pa

63、ge 1442024/9/7运筹学运输问题的应用运输问题的应用例例3.4 求下列表中极小化运求下列表中极小化运输问题的最的最优解。解。 B1B2B3B4aiA1592360A2-47840A3364230A448101150bj20603545180160因为有：因为有：Page 1452024/9/7运筹学运输问题的应用运输问题的应用所以是一个所以是一个产大于大于销的运的运输问题。表中。表中A2不可达不可达B1，用一个，用一个很大的正数很大的正数M表示运价表示运价C21。虚。虚设一个一个销量量为b5=180-160=20，Ci5=0，i=1,2,3,4，表的右，表的右边增添一列增添一列 ，得

64、到新的运价表。，得到新的运价表。B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj2060354520180Page 1462024/9/7运筹学运输问题的应用运输问题的应用下表下表为计算算结果。可看出：果。可看出：产地地A4还有有20个个单位没有运出。位没有运出。B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180Page 1472024/9/7运筹学运输问题的应用运输问题的应用3. 生生产与与储存存问题例例3.5 某厂按合同规定须于当年每个季度末分别提供某厂按合同规定须于

65、当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用每积压一个季度需储存、维护等费用0.15万元。试求在完成合同万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。的情况下，使该厂全年生产总费用为最小的决策方案。季度季度生产能力生产能力/台台单位成本单位成本/万元万元2510.83511.130111011.3Page 1482024/9

66、/7运筹学运输问题的应用运输问题的应用解：解： 设 xij为第第 i 季度生季度生产的第的第 j 季度交季度交货的柴油机数目，那的柴油机数目，那么么应满足：足：交交货： x11 = 10 生生产：x11 + x12 + x13 + x14 25 x12 + x22 = 15 x22 + x23 + x24 35 x13 + x23 + x33 = 25 x33 + x34 30 x14 + x24 + x34 + x44 = 20 x44 10把第把第 i 季度生产的柴油机数目看作第季度生产的柴油机数目看作第 i 个生产厂的产量；把第个生产厂的产量；把第 j 季季度交货的柴油机数目看作第度交货

67、的柴油机数目看作第 j 个销售点的销量；设个销售点的销量；设cij是第是第i季度生季度生产的第产的第j季度交货的每台柴油机的实际成本，应该等于该季度单位季度交货的每台柴油机的实际成本，应该等于该季度单位成本加上储存、维护等费用。可构造下列产销平衡问题：成本加上储存、维护等费用。可构造下列产销平衡问题：Page 1492024/9/7运筹学运输问题的应用运输问题的应用 ji产量产量10.810.9511.111.2525M11.1011.2511.4035MM11.0011.1530MMM11.3010销量销量10152520 10070由于产大于销，加上一个虚拟的销地由于产大于销，加上一个虚拟

68、的销地D，化为平衡问题，化为平衡问题，即可应用表上作业法求解。即可应用表上作业法求解。Page 1502024/9/7运筹学运输问题的应用运输问题的应用该问题的数学模型：该问题的数学模型：Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44 jiD产量产量10.810.9511.111.25025M11.1011.2511.40035MM11.0011.15030MMM11.30010销量销量1015252030 100100P

69、age 1512024/9/7运筹学运输问题的应用运输问题的应用 jiD产量产量1015025053035255301010销量销量1015252030 100100最优生产决策如下表，最小费用最优生产决策如下表，最小费用z773万元。万元。2024/9/7运筹学Chapter4 整数规划整数规划( Integer Programming )( Integer Programming )整数规划的特点及应用整数规划的特点及应用分支定界法分支定界法分配问题与匈牙利法分配问题与匈牙利法本章主要内容：本章主要内容：本章主要内容：本章主要内容：Page 1532024/9/7运筹学整数规划的特点及应用

70、整数规划的特点及应用整数整数整数整数规规划（划（划（划（简简称：称：称：称：IPIP）要求一部分或全部决策要求一部分或全部决策变量取整数量取整数值的的规划划问题称称为整整数数规划。不考划。不考虑整数条件，由余下的目整数条件，由余下的目标函数和函数和约束条件构束条件构成的成的规划划问题称称为该整数整数规划划问题的松弛的松弛问题。若。若该松弛松弛问题是一个是一个线性性规划，划，则称称该整数整数规划划为整数整数线性性规划。划。整数线性规划数学模型的一般形式：整数线性规划数学模型的一般形式：Page 1542024/9/7运筹学整数规划的特点及应用整数规划的特点及应用整数整数整数整数线线性性性性规规划

71、划划划问题问题的种的种的种的种类类： 纯整数线性规划：指全部决策变量都必须取整数值的整数纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划。线性规划。 混合整数线性规划：决策变量中有一部分必须取整数值，混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。另一部分可以不取整数值的整数线性规划。 0-1型整数线性规划：决策变量只能取值型整数线性规划：决策变量只能取值0或或1的整数线性的整数线性规划。规划。Page 1552024/9/7运筹学整数规划的特点及应用整数规划的特点及应用整数整数整数整数规规划的典型例子划的典型例子划的典型例子划的典型例子例例4

72、.1 工厂工厂A1和和A2生产某种物资。由于该种物资供不应求，故需要生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有再建一家工厂。相应的建厂方案有A3和和A4两个。这种物资的需求地两个。这种物资的需求地有有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费需求地的单位物资运费cij，见下表：，见下表：B1B2B3B4年生产能力年生产能力A12934400A28357600A37612200A44525200年需求量年需求量350400300150工厂工厂A3或或A4开工后，每年的生产费用

73、估计分别为开工后，每年的生产费用估计分别为1200万或万或1500万万元。现要决定应该建设工厂元。现要决定应该建设工厂A3还是还是A4，才能使今后每年的总费用，才能使今后每年的总费用最少。最少。Page 1562024/9/7运筹学整数规划的特点及应用整数规划的特点及应用解：解：这是一个物是一个物资运运输问题，特点是事先不能确定，特点是事先不能确定应该建建A3还是是A4中哪一个，因而不知道新厂投中哪一个，因而不知道新厂投产后的后的实际生生产物物资。为此，引入此，引入0-1变量：量：再设再设xij为由为由Ai运往运往Bj的物资数量，单位为千吨；的物资数量，单位为千吨；z表示总费用，表示总费用，单

74、位万元。单位万元。则该规划问题的数学模型可以表示为：则该规划问题的数学模型可以表示为：Page 1572024/9/7运筹学整数规划的特点及应用整数规划的特点及应用混合整数规划问题混合整数规划问题Page 1582024/9/7运筹学整数规划的特点及应用整数规划的特点及应用例例4.2 现有有资金金总额为B。可供。可供选择的投的投资项目有目有n个，个，项目目j所需投所需投资额和和预期收益分期收益分别为aj和和cj（j1,2,.,n），此外由），此外由于种种原因，有三个附加条件：于种种原因，有三个附加条件：若选择项目1，就必须同时选择项目2。反之不一定项目3和4中至少选择一个；项目5,6,7中恰好

75、选择2个。应该怎怎样选择投投资项目，才能使目，才能使总预期收益最大。期收益最大。Page 1592024/9/7运筹学整数规划的特点及应用整数规划的特点及应用解：解：对每个投每个投资项目都有被目都有被选择和不被和不被选择两种可能，因此两种可能，因此分分别用用0和和1表示，令表示，令xj表示第表示第j个个项目的决策目的决策选择，记为：投资问题可以表示为：投资问题可以表示为：Page 1602024/9/7运筹学整数规划的特点及应用整数规划的特点及应用例例4.3 4.3 指派指派问题或分配或分配问题。人事部。人事部门欲安排四人到四个不欲安排四人到四个不同同岗位工作，每个位工作，每个岗位一个人。位一

76、个人。经考核四人在不同考核四人在不同岗位的成位的成绩（百分制）如表所示，如何安排他（百分制）如表所示，如何安排他们的工作使的工作使总成成绩最好。最好。 工作工作人员人员ABCD甲甲85927390乙乙95877895丙丙82837990丁丁86908088Page 1612024/9/7运筹学整数规划的特点及应用整数规划的特点及应用设设 数学模型如下：数学模型如下：要求每人做一项工作，约束条件为：要求每人做一项工作，约束条件为：Page 1622024/9/7运筹学整数规划的特点及应用整数规划的特点及应用每每项工作只能安排一人，工作只能安排一人，约束条件束条件为：变量约束：变量约束：Page

77、1632024/9/7运筹学整数规划的特点及应用整数规划的特点及应用整数整数整数整数规规划划划划问题问题解的特征：解的特征：解的特征：解的特征： 整数规划问题的可行解集合是它松弛问题可行解集合的一整数规划问题的可行解集合是它松弛问题可行解集合的一个子集，任意两个可行解的凸组合不一定满足整数约束条件，个子集，任意两个可行解的凸组合不一定满足整数约束条件，因而不一定仍为可行解。因而不一定仍为可行解。 整数规划问题的可行解一定是它的松弛问题的可行解（反整数规划问题的可行解一定是它的松弛问题的可行解（反之不一定），但其最优解的目标函数值不会优于后者最优解之不一定），但其最优解的目标函数值不会优于后者最

78、优解的目标函数值。的目标函数值。Page 1642024/9/7运筹学整数规划的特点及应用整数规划的特点及应用例例4.3 设整数整数规划划问题如下如下首先不考虑整数约束，得到线性规划问题（一般称为松弛问首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。题）。Page 1652024/9/7运筹学整数规划的特点及应用整数规划的特点及应用用用图解法求出最解法求出最优解解为：x13/2, x2 = 10/3，且有，且有Z = 29/6现求整数解现求整数解(最优解最优解):如用舍如用舍入取整法可得到入取整法可得到4个点即个点即(1，3),(2，3),(1，4),(2，4)。显然，它。显然，它们

79、都不可能是整数规划的最优解。们都不可能是整数规划的最优解。x1x233(3/2,10/3)按整数规划约束条件，其可行按整数规划约束条件，其可行解肯定在线性规划问题的可行域解肯定在线性规划问题的可行域内且为整数点。故整数规划问题内且为整数点。故整数规划问题的可行解集是一个有限集，如右的可行解集是一个有限集，如右图所示。图所示。其中其中(2,2),(3,1)点点的目标函数值最大，即为的目标函数值最大，即为Z=4。Page 1662024/9/7运筹学整数规划的特点及应用整数规划的特点及应用整数整数规划划问题的求解方法：的求解方法： 分支定界法和割平面法分支定界法和割平面法 匈牙利法（指派问题）匈牙

80、利法（指派问题）Page 1672024/9/7运筹学分支定界法分支定界法1）求整数）求整数规划的松弛划的松弛问题最最优解；解；若松弛若松弛问题的最的最优解解满足整数要求，得到整数足整数要求，得到整数规划的最划的最优解解,否否则转下一步；下一步；2）分支与定界：）分支与定界：任意任意选一个非整数解的一个非整数解的变量量xi，在松弛，在松弛问题中加上中加上约束：束：xixi 和和 xixi+1组成两个新的松弛成两个新的松弛问题，称，称为分枝。新的松弛分枝。新的松弛问题具有特征：当原具有特征：当原问题是求最大是求最大值时，目，目标值是分枝是分枝问题的上界；当原的上界；当原问题是求最小是求最小值时，

81、目，目标值是分枝是分枝问题的下界。的下界。检查所有分枝的解及目所有分枝的解及目标函数函数值，若某分枝的解是整数并且目，若某分枝的解是整数并且目标函数函数值大于（大于（max）等于其它分枝的目）等于其它分枝的目标值，则将其它分枝剪去不再将其它分枝剪去不再计算，算，若若还存在非整数解并且目存在非整数解并且目标值大于大于(max)整数解的目整数解的目标值，需要，需要继续分枝，分枝，再再检查，直到得到最，直到得到最优解。解。分支定界法的解题步骤：分支定界法的解题步骤：分支定界法的解题步骤：分支定界法的解题步骤：Page 1682024/9/7运筹学分支定界法分支定界法例例4.4 用分枝定界法求解整数用

82、分枝定界法求解整数规划划问题解：首先去掉整数约束，变成一般线性规划问题解：首先去掉整数约束，变成一般线性规划问题( (原整数规原整数规划问题的松驰问题划问题的松驰问题) )LPIPPage 1692024/9/7运筹学分支定界法分支定界法用用图解法求松弛解法求松弛问题的最的最优解，如解，如图所示。所示。x1x23(18/11,40/11)21123x118/11, x2 =40/11Z=218/11(19.8)即即Z 也是也是IP最小值的下限。最小值的下限。对于对于x118/111.64，取值取值x1 1， x1 2对于对于x2 =40/11 3.64，取值，取值x2 3 ，x2 4先将（先将

83、（LP）划分为（）划分为（LP1）和（和（LP2）,取取x1 1, x1 2Page 1702024/9/7运筹学分支定界法分支定界法分支：分支：分别求出（分别求出（LP1）和（）和（LP2）的最优解。）的最优解。Page 1712024/9/7运筹学分支定界法分支定界法先求先求LP1,如如图所示。此所示。此时在在B点取得最点取得最优解。解。x11, x2 =3, Z(1)16找到整数解，找到整数解，问题已探明，此已探明，此枝停止枝停止计算。算。x1x233(18/11,40/11)11BAC同理求同理求LP2,如图所示。在如图所示。在C 点点取得最优解。即取得最优解。即:x12, x2 =1

84、0/3, Z(2)56/318.7 Z(2) Z(1)16 原问题有比原问题有比16更小的最优更小的最优解，但解，但 x2 不是整数，故继续不是整数，故继续分支。分支。Page 1722024/9/7运筹学分支定界法分支定界法在在IP2中分中分别再加入条件：再加入条件： x23, x24 得下式两支：得下式两支：分别求出分别求出LP21和和LP22的最优解的最优解Page 1732024/9/7运筹学分支定界法分支定界法x1x233(18/11,40/11)11BACD先求先求LP21,如图所示。此时如图所示。此时D 在点取得最优解。在点取得最优解。即即 x112/52.4, x2 =3, Z

85、(21)-87/5-17.4 Z(211) 如对如对LP212继续分解，其最小值继续分解，其最小值也不会低于也不会低于15.5 ，问题探明，问题探明,剪枝。剪枝。Page 1762024/9/7运筹学分支定界法分支定界法原整数原整数规划划问题的最的最优解解为: x1=2, x2 =3, Z* =17以上的求解以上的求解过程可以程可以用一个用一个树形形图表示如表示如右：右：LP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x2=10/3Z(2) 18.5LP21x1=12/5, x2=3Z(21) 17.4LP22无可无可行解行解

86、LP211x1=2, x2=3Z(211) 17LP212x1=3, x2=5/2Z(212) 15.5x11x12x23x24x12x13Page 1772024/9/7运筹学分支定界法分支定界法例例4.5 用分枝定界法求解用分枝定界法求解解解: 先求对应的松弛问题（记为先求对应的松弛问题（记为LP0）用图解法得到最优解用图解法得到最优解X(3.57,7.14),Z0=35.7,如下图所如下图所示。示。Page 1782024/9/7运筹学分支定界法分支定界法1010松弛问题松弛问题LP0的最优解的最优解X=(3.57,7.14),Z0=35.7x1x2oABCPage 1792024/9/

87、7运筹学分支定界法分支定界法10x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.5Page 1802024/9/7运筹学分支定界法分支定界法10x1x2oABCLP1LP2134LP21:X=(4.33,6),Z21=35.336Page 1812024/9/7运筹学分支定界法分支定界法10x1x2oACLP1346LP211:X=(4,6),Z211=34LP212:X=(5,5),Z212=355LP212Page 1822024/9/7运筹学分支定界法分支定界法上述分枝上述分枝上述分枝上述分枝过过程可用下程可用下程可用下程可用

88、下图图表示：表示：表示：表示：LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6) Z1=34.8LP2:X=(4,6.5) Z2=35.5x13x14LP21:X=(4.33,6) Z21=35.33x26LP211:X=(4,6) Z211=34LP212:X=(5,5) Z212=35x14x15LP22无可行解无可行解x27Page 1832024/9/7运筹学小结小结学习要点：学习要点： 掌握一般整数规划问题概念及模型结构掌握一般整数规划问题概念及模型结构 掌握分支定界法原理掌握分支定界法原理 能够用分支定界法求解一般整数规划问题能够用分支定界法求解一般整数规

89、划问题课后练习：课后练习：Page 1842024/9/7运筹学分配问题与匈牙利法分配问题与匈牙利法指派指派指派指派问题问题的数学模型的的数学模型的的数学模型的的数学模型的标标准形式：准形式：准形式：准形式：设设n 个人被分配去做个人被分配去做n 件工作，规定每个人只做一件工作，件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第每件工作只有一个人去做。已知第i个人去做第个人去做第j 件工作的效率件工作的效率（ 时间或费用）为时间或费用）为Cij(i=1.2n;j=1.2n)并假设并假设Cij 0。问。问应如何分配才能使总效率（应如何分配才能使总效率（ 时间或费用）最高？时间或费用）

90、最高？设决策变量设决策变量 Page 1852024/9/7运筹学分配问题与匈牙利法分配问题与匈牙利法指派指派问题的数学模型的数学模型为：Page 1862024/9/7运筹学分配问题与匈牙利法分配问题与匈牙利法克尼格定理克尼格定理克尼格定理克尼格定理 : :如果从分配如果从分配问题效率矩效率矩阵aij的每一行元素中分的每一行元素中分别减去减去(或加上或加上)一个常数一个常数ui，从每一列中分，从每一列中分别减去减去(或加上或加上)一个常一个常数数vj，得到一个新的效率矩，得到一个新的效率矩阵bij，则以以bij为效率矩效率矩阵的的分配分配问题与以与以aij为效率矩效率矩阵的分配的分配问题具有

91、相同的最具有相同的最优解。解。Page 1872024/9/7运筹学分配问题与匈牙利法分配问题与匈牙利法指派指派指派指派问题问题的求解步的求解步的求解步的求解步骤骤：1) 变变换换指指派派问问题题的的系系数数矩矩阵阵(cij)为为(bij)，使使在在(bij)的的各各行行各各列中都出现列中都出现0元素，即元素，即 从从(cij)的每行元素都减去该行的最小元素；的每行元素都减去该行的最小元素； 再从所得新系数矩阵的每列元素中减去该列的最小元素。再从所得新系数矩阵的每列元素中减去该列的最小元素。2) 进行试指派，以寻求最优解。进行试指派，以寻求最优解。 在在(bij)中中找找尽尽可可能能多多的的独

92、独立立0元元素素，若若能能找找出出n个个独独立立0元元素素，就就以以这这n个个独独立立0元元素素对对应应解解矩矩阵阵(xij)中中的的元元素素为为1，其其余余为为0，这就得到最优解。，这就得到最优解。Page 1882024/9/7运筹学分配问题与匈牙利法分配问题与匈牙利法找独立找独立0元素，常用的步元素，常用的步骤为： 从只有一个从只有一个0元素的行开始，给该行中的元素的行开始，给该行中的0元素加圈，记作元素加圈，记作 。然后划去。然后划去 所在列的其它所在列的其它0元素，记作元素，记作 ；这表示该列所代表；这表示该列所代表的任务已指派完，不必再考虑别人了。依次进行到最后一行。的任务已指派完

93、，不必再考虑别人了。依次进行到最后一行。 从只有一个从只有一个0元素的列开始（画元素的列开始（画 的不计在内），给该列中的的不计在内），给该列中的0元素加圈，记作元素加圈，记作；然后划去；然后划去 所在行的所在行的0元素，记作元素，记作 ，表示，表示此人已有任务，不再为其指派其他任务了。依次进行到最后一列。此人已有任务，不再为其指派其他任务了。依次进行到最后一列。 若仍有没有划圈的若仍有没有划圈的0元素，且同行元素，且同行(列列)的的0元素至少有两个，比元素至少有两个，比较这行各较这行各0元素所在列中元素所在列中0元素的数目，选择元素的数目，选择0元素少这个元素少这个0元素加元素加圈圈(表示选

94、择性多的要表示选择性多的要“礼让礼让”选择性少的选择性少的)。然后划掉同行同列。然后划掉同行同列的其它的其它0元素。可反复进行，直到所有元素。可反复进行，直到所有0元素都已圈出和划掉为止。元素都已圈出和划掉为止。Page 1892024/9/7运筹学分配问题与匈牙利法分配问题与匈牙利法 若若 元素的数目元素的数目m 等于矩阵的阶数等于矩阵的阶数n（即：（即：mn），那么这指，那么这指派问题的最优解已得到。若派问题的最优解已得到。若m n, 则转入下一步。则转入下一步。3) 用最少的直线通过所有用最少的直线通过所有0元素。其方法：元素。其方法： 对没有对没有的行打的行打“”； 对已打对已打“”

95、的行中所有含的行中所有含 元素的列打元素的列打“” ； 再对打有再对打有“”的列中含的列中含 元素的行打元素的行打“” ； 重复重复、直到得不出新的打直到得不出新的打号的行、列为止；号的行、列为止； 对没有打对没有打号的行画横线，有打号的行画横线，有打号的列画纵线，这就得到覆盖号的列画纵线，这就得到覆盖所有所有0元素的最少直线数元素的最少直线数 l 。注注：l 应应等等于于m，若若不不相相等等，说说明明试试指指派派过过程程有有误误，回回到到第第2步步，另另行行试试指指派派；若若 lm n，表表示示还还不不能能确确定定最最优优指指派派方方案案，须须再再变变换换当当前前的的系系数矩阵，以找到数矩阵

96、，以找到n个独立的个独立的0元素，为此转第元素，为此转第4步。步。Page 1902024/9/7运筹学分配问题与匈牙利法分配问题与匈牙利法4) 变换矩矩阵(bij)以增加以增加0元素元素在没有被直在没有被直线通通过的所有元素中找出最小的所有元素中找出最小值，没有被直，没有被直线通通过的所有元素减去的所有元素减去这个最小元素；直个最小元素；直线交点交点处的元素加上的元素加上这个最小个最小值。新系数矩。新系数矩阵的最的最优解和原解和原问题仍相同。仍相同。转回第回第2步。步。Page 1912024/9/7运筹学分配问题与匈牙利法分配问题与匈牙利法例例4.6 有一份中文有一份中文说明明书，需，需译

97、成英、日、德、俄四种文字，成英、日、德、俄四种文字，分分别记作作A、B、C、D。现有甲、乙、丙、丁四人，他有甲、乙、丙、丁四人，他们将将中文中文说明明书译成不同成不同语种的种的说明明书所需所需时间如下表所示，如下表所示，问如何分派任如何分派任务，可使，可使总时间最少？最少？ 任务任务人员人员ABCD甲甲67112乙乙4598丙丙31104丁丁5982Page 1922024/9/7运筹学分配问题与匈牙利法分配问题与匈牙利法解：解：1）变换系数矩系数矩阵，增加，增加0元素。元素。52）试指派（找独立）试指派（找独立0元素）元素） 找到找到 3 个独立零元素个独立零元素 但但 m = 3 n =

98、4Page 1932024/9/7运筹学分配问题与匈牙利法分配问题与匈牙利法3）作最少的直作最少的直线覆盖所有覆盖所有0元素元素 独立零元素的个数独立零元素的个数m等于最少等于最少直线数直线数l，即，即lm=3n=4；4）没有被直线通过的元素中选择最小值为）没有被直线通过的元素中选择最小值为1，变换系数矩，变换系数矩阵，将没有被直线通过的所有元素减去这个最小元素；直阵，将没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。得到新的矩阵，重复线交点处的元素加上这个最小值。得到新的矩阵，重复2）步进行试指派步进行试指派Page 1942024/9/7运筹学分配问题与匈牙利法分

99、配问题与匈牙利法000 0 00试指派试指派得到得到4个独立零元素，个独立零元素， 所以最优解矩阵为：所以最优解矩阵为： 即完成即完成4个任务的总时间最少个任务的总时间最少为：为：241+8=15Page 1952024/9/7运筹学分配问题与匈牙利法分配问题与匈牙利法例例4.7 已知四人分已知四人分别完成四完成四项工作所需工作所需时间如下表，求最如下表，求最优分配方案。分配方案。 任务任务人员人员ABCD甲甲215134乙乙1041415丙丙9141613丁丁78119Page 1962024/9/7运筹学分配问题与匈牙利法分配问题与匈牙利法解：解：1）变换系数矩系数矩阵，增加，增加0元素。

100、元素。2）试指派（找独立）试指派（找独立0元素）元素） 独立独立0元素的个数为元素的个数为4 , 指派问题的最优指指派问题的最优指派方案即为甲负责派方案即为甲负责D工作，乙负责工作，乙负责B工作，工作，丙负责丙负责A工作，丁负责工作，丁负责C工作。这样安排工作。这样安排能使总的工作时间最少，为能使总的工作时间最少，为4491128。Page 1972024/9/7运筹学分配问题与匈牙利法分配问题与匈牙利法例例4.8 已知五人分已知五人分别完成五完成五项工作耗工作耗费如下表，求最如下表，求最优分配分配方案。方案。 任务任务人员人员ABCDE甲甲759811乙乙9127119丙丙85468丁丁73

101、696戊戊467511Page 1982024/9/7运筹学分配问题与匈牙利法分配问题与匈牙利法-1 -2解：解：1）变换系数矩系数矩阵，增加，增加0元素。元素。Page 1992024/9/7运筹学分配问题与匈牙利法分配问题与匈牙利法2）试指派（找独立）试指派（找独立0元素）元素） 独立独立0元素的个数元素的个数l45，故画直线调整矩阵。，故画直线调整矩阵。Page 2002024/9/7运筹学分配问题与匈牙利法分配问题与匈牙利法选择直线外的最小元素选择直线外的最小元素为为1；直线外元素减；直线外元素减1，直线交点元素加直线交点元素加1，其，其他保持不变。他保持不变。Page 2012024

102、/9/7运筹学分配问题与匈牙利法分配问题与匈牙利法l =m=4 0, d-=0; 当实际值未达到目标值时：当实际值未达到目标值时： d+=0, d-0; 当实际值同目标值恰好一致时：当实际值同目标值恰好一致时： d+=0, d-=0;故恒有故恒有d+d-=0Page 2222024/9/7运筹学目标规划问题及其数学模型目标规划问题及其数学模型2. 统一处理目标和约束。统一处理目标和约束。 对有严格限制的资源使用建立系统约束，数学形式同线性规划对有严格限制的资源使用建立系统约束，数学形式同线性规划中的约束条件。如中的约束条件。如C和和D设备的使用限制。设备的使用限制。 对不严格限制的约束，连同原

103、线性规划建模时的目标，均通过对不严格限制的约束，连同原线性规划建模时的目标，均通过目标约束来表达。目标约束来表达。1）例如要求甲、乙两种产品保持）例如要求甲、乙两种产品保持1:1的比例，系统约束表达为：的比例，系统约束表达为：x1=x2。由于这个比例允许有偏差，。由于这个比例允许有偏差，当当x1x2时，出现正偏差时，出现正偏差d+，即：，即： x1-d+ =x2或或x1x2-d+ =0Page 2232024/9/7运筹学目标规划问题及其数学模型目标规划问题及其数学模型正正负偏差不可能同偏差不可能同时出出现，故，故总有：有：x1x2+d-d+ =0 若希望甲的产量不低于乙的产量，即不希望若希望

104、甲的产量不低于乙的产量，即不希望d-0,用目标约束可用目标约束可表为表为: 若希望甲的产量低于乙的产量，即不希望若希望甲的产量低于乙的产量，即不希望d0,用目标约束可用目标约束可表为表为: 若希望甲的产量恰好等于乙的产量，即不希望若希望甲的产量恰好等于乙的产量，即不希望d0,也不希望也不希望d-0用目标约束可表为用目标约束可表为:Page 2242024/9/7运筹学目标规划问题及其数学模型目标规划问题及其数学模型3）设备B必要必要时可加班及加班可加班及加班时间要控制，目要控制，目标约束表示束表示为：2）力求使利润指标不低于）力求使利润指标不低于12元，目标约束表示为：元，目标约束表示为：4）

105、设备）设备A既要求充分利用，又尽可能不加班，目标约束表示为：既要求充分利用，又尽可能不加班，目标约束表示为：Page 2252024/9/7运筹学目标规划问题及其数学模型目标规划问题及其数学模型3. 目标的优先级与权系数目标的优先级与权系数在一个目标规划的模型中，为达到某一目标可牺牲其他一些在一个目标规划的模型中，为达到某一目标可牺牲其他一些目标，称这些目标是属于不同层次的优先级。优先级层次的高低目标，称这些目标是属于不同层次的优先级。优先级层次的高低可分别通过优先因子可分别通过优先因子P1,P2,表示。对于同一层次优先级的不同表示。对于同一层次优先级的不同目标，按其重要程度可分别乘上不同的权

106、系数。权系数是一个个目标，按其重要程度可分别乘上不同的权系数。权系数是一个个具体数字，乘上的权系数越大，表明该目标越重要。具体数字，乘上的权系数越大，表明该目标越重要。现假定：现假定： 第第1优先级优先级P1企业利润；企业利润； 第第2优先级优先级P2甲乙产品的产量保持甲乙产品的产量保持1:1的比例的比例 第第3优先级优先级P3设备设备A,B尽量不超负荷工作。其中设备尽量不超负荷工作。其中设备A的重要性的重要性比设备比设备B大三倍。大三倍。Page 2262024/9/7运筹学目标规划问题及其数学模型目标规划问题及其数学模型上述目上述目标规划模型可以表示划模型可以表示为：Page 227202

107、4/9/7运筹学目标规划问题及其数学模型目标规划问题及其数学模型目标规划数学模型的一般形式目标规划数学模型的一般形式达成函数达成函数目标约束目标约束其中：其中：g gk k为第为第k k个目标约束的预期目标值，个目标约束的预期目标值， 和和 为为p pl l 优先因子对应各目标的权系数。优先因子对应各目标的权系数。Page 2282024/9/7运筹学目标规划问题及其数学模型目标规划问题及其数学模型用目用目用目用目标规标规划求解划求解划求解划求解问题问题的的的的过过程：程：程：程：明确问题，列出明确问题，列出目标的优先级和目标的优先级和权系数权系数构造目标规构造目标规划模型划模型求出满意解求出

108、满意解满意否？满意否？分析各项目标分析各项目标完成情况完成情况据此制定出决策方案据此制定出决策方案NYPage 2292024/9/7运筹学目标规划的图解分析法目标规划的图解分析法目标规划的图解法：目标规划的图解法：目标规划的图解法：目标规划的图解法：适用两个变量的目标规划问题，但其操作简单，适用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于理解一般目标规划原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。的求解原理和过程。图解法解题步骤：图解法解题步骤：图解法解题步骤：图解法解题步骤：1. 将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏将所有约束条件（

109、包括目标约束和绝对约束，暂不考虑正负偏差变量）的直线方程分别标示于坐标平面上。差变量）的直线方程分别标示于坐标平面上。2. 确定系统约束的可行域。确定系统约束的可行域。3. 在目标约束所代表的边界线上，用箭头标出正、负偏差变量值在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向增大的方向Page 2302024/9/7运筹学目标规划的图解分析法目标规划的图解分析法3. 求求满足最高足最高优先等先等级目目标的解的解4. 转到下一个到下一个优先等先等级的目的目标，再不破坏所有，再不破坏所有较高高优先等先等级目目标的前提下，求出的前提下，求出该优先等先等级目目标的解的解5. 重复重复4

110、，直到所有，直到所有优先等先等级的目的目标都已都已审查完完毕为止止6. 确定最确定最优解和解和满意解。意解。Page 2312024/9/7运筹学目标规划的图解分析法目标规划的图解分析法例例5.2 用用图解法求解下列目解法求解下列目标规划划问题Page 2322024/9/7运筹学目标规划的图解分析法目标规划的图解分析法(a)(b)(c)(d )x2x1(e)(f)d1-d1+d2+d2-d3-d3+d4-d4+满意解满意解(3,3)04683462 2Page 2332024/9/7运筹学目标规划的图解分析法目标规划的图解分析法x1x2(a)(b)d1+d1-(c)d2-d2+(d)d3-d

111、3+GD满意解是线段满意解是线段GD上任意点上任意点其中其中G点点X(2,4),D点点X(10/3,10/3)05.51055.6112,410/3,10/35107例例5.3Page 2342024/9/7运筹学目标规划的图解分析法目标规划的图解分析法Ox1x22040605020406050abd1-d1+d2-d2+cdd3-d3+d4-d4+(24,26)满意解满意解X=(24，26)例例5.4Page 2352024/9/7运筹学目标规划应用举例目标规划应用举例例例5.5 已知一个生已知一个生产计划的划的线性性规划模型如下，其中目划模型如下，其中目标函函数数为总利利润，x1,x2 为

112、产品品A、B产量。量。现有下列目标：现有下列目标：1. 要求总利润必须超过要求总利润必须超过 2500 元；元；2. 考虑产品受市场影响，为避免积压，考虑产品受市场影响，为避免积压，A、B的生产量不超过生产量不超过 60 件件和和 100 件；件；3. 由于甲资源供应比较紧张，不要超过现有量由于甲资源供应比较紧张，不要超过现有量140。试建立目标规划模型，并用图解法求解。试建立目标规划模型，并用图解法求解。Page 2362024/9/7运筹学目标规划应用举例目标规划应用举例解：以产品解：以产品 A,B 的单件利润比的单件利润比 2.5 :1 为权系数，模型如下：为权系数，模型如下：Page

113、2372024/9/7运筹学目标规划应用举例目标规划应用举例0x2 0x114012010080604020 20 40 60 80 100ABCDC(60 ,58.3)为所求的满意解。为所求的满意解。(24,26)2024/9/7运筹学Chapter6 图与网络分析图与网络分析( Graph Theory and Network Analysis )( Graph Theory and Network Analysis )图的基本概念与模型图的基本概念与模型树与图的最小树树与图的最小树最短路问题最短路问题网络的最大流网络的最大流本章主要内容：本章主要内容：本章主要内容：本章主要内容：Page

114、 2392024/9/7运筹学图的基本概念与模型图的基本概念与模型 长长江江汉汉江江武昌武昌武昌武昌汉口汉口汉口汉口汉阳汉阳汉阳汉阳您能从武汉理工大学出发走过您能从武汉理工大学出发走过每座桥且只走一次然后回到学每座桥且只走一次然后回到学校吗校吗?Page 2402024/9/7运筹学近代图论的历史可追溯到近代图论的历史可追溯到18世纪的七桥问题世纪的七桥问题穿过穿过K nigsberg城的七座桥，要求每座桥通过一次且仅通过一次。城的七座桥，要求每座桥通过一次且仅通过一次。 这就是著名的这就是著名的“哥尼斯堡哥尼斯堡 7 桥桥”难题。难题。Euler1736年证明了不年证明了不可能存在这样的路线

115、。可能存在这样的路线。图的基本概念与模型图的基本概念与模型KnigsbergKnigsberg桥对应的图桥对应的图Page 2412024/9/7运筹学图的基本概念与模型图的基本概念与模型图论中中图是由点和是由点和边构成，可以反映一些构成，可以反映一些对象之象之间的关系。的关系。一般情况下一般情况下图中点的相中点的相对位置如何、点与点之位置如何、点与点之间联线的的长短短曲直，曲直，对于反映于反映对象之象之间的关系并不是重要的。的关系并不是重要的。图的定义：图的定义：图的定义：图的定义：若用点表示研究的对象，用边表示这些对象之间的联系，若用点表示研究的对象，用边表示这些对象之间的联系，则图则图G

116、可以定义为点和边的集合，记作：可以定义为点和边的集合，记作：其中其中: V点集点集 E边集边集 图图G区别于几何学中的图。这里只关心图中有多少个点以区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。及哪些点之间有连线。Page 2422024/9/7运筹学图的基本概念与模型图的基本概念与模型(v1)赵赵(v2)钱钱孙孙(v3) 李李(v4)周周(v5)吴吴(v6)陈陈(v7)e2e1e3e4e5(v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。可见图论中的图与几何图、工程图是不一样的

117、。例如：在一个人群中，对相互认识这个关系我们可以用图来例如：在一个人群中，对相互认识这个关系我们可以用图来表示。表示。Page 2432024/9/7运筹学图的基本概念与模型图的基本概念与模型定定义: 图中的点用中的点用v表示，表示，边用用e表示。表示。对每条每条边可用它所可用它所连接的点表示，接的点表示，记作：作：e1=v1,v1; e2=v1,v2; v3e7e4e8e5e6e1e2e3v1v2v4v5 端点端点,关联边关联边,相邻相邻若有边若有边e可表示为可表示为e=vi,vj，称，称vi和和vj是边是边e的的端点端点，反之称边，反之称边e为点为点vi或或vj的的关联边关联边。若点。若点

118、vi、vj与同一条边关与同一条边关联，称点联，称点vi和和vj相邻；若边相邻；若边ei和和ej具具有公共的端点，称边有公共的端点，称边ei和和ej相邻相邻。Page 2442024/9/7运筹学图的基本概念与模型图的基本概念与模型 环环, 多重边多重边, 简单图简单图如果边如果边e的两个端点相重，称该边为的两个端点相重，称该边为环环。如右图中边。如右图中边e1为环。如果两个点为环。如果两个点之间多于一条，称为之间多于一条，称为多重边多重边，如右图，如右图中的中的e4和和e5，对无环、无多重边的图，对无环、无多重边的图称作称作简单图简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5Pa

119、ge 2452024/9/7运筹学图的基本概念与模型图的基本概念与模型 次，奇点，偶点，孤立点次，奇点，偶点，孤立点与某一个点与某一个点vi相关联的边的数目称为相关联的边的数目称为点点vi的的次次（也叫做度），记作（也叫做度），记作d(vi)。右图中右图中d(v1),d(v3)=5,d(v5)=1。次为奇数的点称作次为奇数的点称作奇点奇点，次为偶数，次为偶数的点称作的点称作偶点偶点，次为，次为1的点称为的点称为悬挂悬挂点点，次为，次为0的点称作的点称作孤立点孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次图的次: 一个图的次等于各点的次之和。一个图的次等于各点的次之和。Pag

120、e 2462024/9/7运筹学图的基本概念与模型图的基本概念与模型 链，圈，连通图链，圈，连通图图中某些点和边的交替序列，若其图中某些点和边的交替序列，若其中各边互不相同，且对任意中各边互不相同，且对任意vi,t-1和和vit均相邻称为均相邻称为链链。用。用表示：表示：v3e7e4e8e5e6e1e2e3v1v2v4v5起点与终点重合的链称作起点与终点重合的链称作圈圈。如。如果每一对顶点之间至少存在一条果每一对顶点之间至少存在一条链，称这样的图为链，称这样的图为连通图连通图，否则，否则称图不连通。称图不连通。Page 2472024/9/7运筹学图的基本概念与模型图的基本概念与模型 二部图（

121、偶图）二部图（偶图）图图G=(V,E)的点集的点集V可以分为两各非空子集可以分为两各非空子集X，Y，集，集XY=V,XY=,使得同一集合中任意两个顶点均不使得同一集合中任意两个顶点均不相邻，称这样的图为偶图。相邻，称这样的图为偶图。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为二部图，明显为二部图，(b)也是二部图，但不明显，改画为也是二部图，但不明显，改画为(c)时可以清楚看出。时可以清楚看出。Page 2482024/9/7运筹学图的基本概念与模型图的基本概念与模型 子图，部分图子图，部分图(支撑子图支撑子图)图图G1=V1、E1和图和图G2=V2，

122、E2如果有如果有 称称G1是是G2的一个的一个子图子图。若有若有 ，则称，则称G1是是G2的的一个一个部分图部分图(支撑子图支撑子图)。v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（G图）图）Page 2492024/9/7运筹学图的基本概念与模型图的基本概念与模型 网络（赋权图）网络（赋权图）设图设图G（V，E），对），对G的每一条边的每一条边(vi,vj)相应赋予数量指标相应赋予数量指标wij，wij称为边称为边(vi,vj)的的权权,赋予权的图赋予权的图G称为网络称为网络(或或赋权图）赋权图）

123、。权可以代表距离、费用、通过能力权可以代表距离、费用、通过能力(容量容量)等等。等等。端点无序的赋权图称为端点无序的赋权图称为无向网络无向网络，端点有序的赋权图称为，端点有序的赋权图称为有有向网络。向网络。910201571419256Page 2502024/9/7运筹学图的基本概念与模型图的基本概念与模型 出次与入次出次与入次 有有向向图图中中，以以vi为为始始点点的的边边数数称称为为点点vi的的出出次次，用用d+(vi)表表示示；以以vi为为终终点点的的边边数数称称为为点点vi 的的入入次次，用用表表示示d-(vi) ；vi 点点的出次和入次之和就是该点的次。的出次和入次之和就是该点的次

124、。 有向图中，所有顶点的入次之和等于所有顶点的出次之有向图中，所有顶点的入次之和等于所有顶点的出次之和。和。Page 2512024/9/7运筹学图的基本概念与模型图的基本概念与模型图图的模型的模型的模型的模型应应用用用用例例6.1 有甲有甲,乙乙,丙丙,丁丁,戊戊,己己6名运动员报名参加名运动员报名参加A,B,C,D,E,F 6个项目的比赛。下表中打个项目的比赛。下表中打的是各运动员报告参加的比赛项的是各运动员报告参加的比赛项目。问目。问6个项目的比赛顺序应如何安排，做到每名运动员都个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。不连续地参加两项比赛。ABCDEF甲甲乙乙丙

125、丙丁丁戊戊己己Page 2522024/9/7运筹学图的基本概念与模型图的基本概念与模型解：用解：用图来建模。把比来建模。把比赛项目作目作为研究研究对象，用点表示。如象，用点表示。如果果2个个项目有同一名运目有同一名运动员参加，在代表参加，在代表这两个两个项目的点之目的点之间连一条一条线，可得下，可得下图。ABCDEF在图中找到一个点序在图中找到一个点序列，使得依次排列的列，使得依次排列的两点不相邻，即能满两点不相邻，即能满足要求。如：足要求。如：1) A,C,B,F,E,D2) D,E,F,B,C,APage 2532024/9/7运筹学图的基本概念与模型图的基本概念与模型一一个个班班级的的

126、学学生生共共计选修修A、B、C、D、E、F六六门课程程，其其中中一一部部分分人人同同时选修修D、C、A，一一部部分分人人同同时选修修B、C、F，一一部部分分人人同同时选修修B、E，还有有一一部部分分人人同同时选修修A、B，期期终考考试要要求求每每天天考考一一门课，六六天天内内考考完完，为了了减减轻学学生生负担担，要要求求每每人人都都不不会会连续参参加加考考试，试设计一个考一个考试日程表。日程表。思考题思考题思考题思考题Page 2542024/9/7运筹学图的基本概念与模型图的基本概念与模型思考思考思考思考题题解答：解答：解答：解答：以每以每门课程程为一个一个顶点，共同被点，共同被选修的修的课

127、程之程之间用用边相相连，得，得图，按，按题意，相意，相邻顶点点对应课程不能程不能连续考考试，不相，不相邻顶点点对应课程允程允许连续考考试，因此，作，因此，作图的的补图，问题是是在在图中中寻找一条哈密找一条哈密顿道路，如道路，如C CE EA AF FD DB B，就，就是一个符合要求的考是一个符合要求的考试课程表。程表。Page 2552024/9/7运筹学图的基本概念与模型图的基本概念与模型A AF FE ED DC CB BPage 2562024/9/7运筹学图的基本概念与模型图的基本概念与模型A AF FE ED DC CB BPage 2572024/9/7运筹学图的基本概念与模型图

128、的基本概念与模型图图的基本性的基本性的基本性的基本性质质：定理定理1 任何图中，顶点次数之和等于所有边数的任何图中，顶点次数之和等于所有边数的2倍。倍。定理定理2 任何图中，次为奇数的顶点必为偶数个。任何图中，次为奇数的顶点必为偶数个。证明：由于每条边必与两个顶点关联，在计算点的次时，每条边证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的均被计算了两次，所以顶点次数的总和等于边数的2倍。倍。证明：设证明：设V1和和V2分别为图分别为图G中奇点与偶点的集合。由定理中奇点与偶点的集合。由定理1可得：可得：2m为偶数，且偶点的次之和为偶数，且偶点的

129、次之和 也为偶数，所以也为偶数，所以 必为偶必为偶数，即奇数点的个数必为偶数。数，即奇数点的个数必为偶数。Page 2582024/9/7运筹学图的基本概念与模型图的基本概念与模型图的矩的矩阵描述：描述：如何在如何在计算机中存算机中存储一个一个图呢？呢？现在已有很多存在已有很多存储的方法，的方法，但最基本的方法就是采用矩但最基本的方法就是采用矩阵来表示一个来表示一个图，图的矩的矩阵表示表示也根据所关心的也根据所关心的问题不同而有：不同而有：邻接矩接矩阵、关、关联矩矩阵、权矩矩阵等。等。1. 邻接矩阵邻接矩阵对于图对于图G=（V，E），），| V |=n， | E |=m，有，有n n阶方矩阵阶

130、方矩阵A=(aij) n n，其中，其中Page 2592024/9/7运筹学图的基本概念与模型图的基本概念与模型v5v1v2v3v4v64332256437例例6.2 下图所表示的图可以构造邻接矩阵下图所表示的图可以构造邻接矩阵A如下如下Page 2602024/9/7运筹学对于赋权图对于赋权图G=(V,E), 其中边其中边 有权有权 , 构造矩阵构造矩阵B=(bij) n n 其中：其中：图的基本概念与模型图的基本概念与模型2. 2. 关关关关联联矩矩矩矩阵阵对于于图G=(V,E), | V |=n, | E |=m, 有有m n阶矩矩阵M=(mij) m n，其中其中:3. 3. 权矩阵

131、权矩阵权矩阵权矩阵Page 2612024/9/7运筹学图的基本概念与模型图的基本概念与模型1 0 1 0 0 0 0 0 0 0 0 01 1 0 0 1 0 0 0 0 0 0 00 1 0 0 0 1 1 1 0 0 0 00 0 0 0 0 0 0 0 1 0 0 10 0 1 1 1 1 0 0 0 0 0 00 0 0 0 0 0 0 0 1 1 0 00 0 0 0 0 0 0 0 0 1 1 10 0 0 1 0 0 1 1 0 0 0 0v1v2v3v4v5v6v7v8e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 v1v2v3v5v8v7e1e

132、2e3e4e6e5e7e9e12e10e11e8v6v4例例6.3 下图所表示的图可以构造邻接矩阵下图所表示的图可以构造邻接矩阵M如下如下:M=（mij）=Page 2622024/9/7运筹学图的基本概念与模型图的基本概念与模型v5v1v2v3v4v64332256437例例6.4 下图所表示的图可以构造权矩阵下图所表示的图可以构造权矩阵B如下如下:Page 2632024/9/7运筹学树与图的最小树树与图的最小树树是图论中结构最简单但又十分重要的图。在自然和社会领树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。域应用极为广泛。例例6.2 乒乓求单打比赛抽签后，可用图来表

133、示相遇情况，如乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。下图所示。AB CDEF GH运动员运动员Page 2642024/9/7运筹学树与图的最小树树与图的最小树例例6.3 某企某企业的的组织机构机构图也可用也可用树图表示。表示。厂长厂长人事科人事科财务科财务科总工总工程师程师生产副生产副厂长厂长经营副经营副厂长厂长开发科开发科技术科技术科生产科生产科设备科设备科供应科供应科销售科销售科检验科检验科动力科动力科Page 2652024/9/7运筹学树与图的最小树树与图的最小树 树：无圈的连通图即为树树：无圈的连通图即为树性质性质1：任何树中必存在次为：任何树中必存在次为1的点。

134、的点。性质性质2：n 个顶点的树必有个顶点的树必有n-1 条边。条边。性质性质3：树中任意两个顶点之间，恰有且仅有一条链。：树中任意两个顶点之间，恰有且仅有一条链。性质性质4：树连通，但去掉任一条边，必变为不连通。：树连通，但去掉任一条边，必变为不连通。性质性质5：树无回圈，但不相邻的两个点之间加一条边，恰：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。得到一个圈。v1v2v3v4v5v6Page 2662024/9/7运筹学树与图的最小树树与图的最小树 图的最小部分树图的最小部分树(支撑树支撑树)如果如果G2是是G1的部分图，又是树图，则称的部分图，又是树图，则称G2是是G1的部分树

135、的部分树（或支撑树）。树图的各条边称为树枝，一般图（或支撑树）。树图的各条边称为树枝，一般图G1含有多含有多个部分树，其中树枝总长最小的部分树，称为该图的最小个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。部分树（或最小支撑树）。v1v2v3v4v5v1v2v3v4v5G1G2Page 2672024/9/7运筹学树与图的最小树树与图的最小树a ab bc cf fe ed dh hg gb bf fe ed dPage 2682024/9/7运筹学树与图的最小树树与图的最小树a ab bc cf fe ed dh hg gb bf fd dg gPage 26920

136、24/9/7运筹学树与图的最小树树与图的最小树b bc ce ed da ab bc cf fe ed dh hg gPage 2702024/9/7运筹学树与图的最小树树与图的最小树a ab bc ch ha ab bc cf fe ed dh hg gPage 2712024/9/7运筹学树与图的最小树树与图的最小树a af fd dg ga ab bc cf fe ed dh hg gPage 2722024/9/7运筹学树与图的最小树树与图的最小树求求求求树树的方法：破圈法和避圈法的方法：破圈法和避圈法的方法：破圈法和避圈法的方法：破圈法和避圈法破圈法破圈法破圈法破圈法Page 273

137、2024/9/7运筹学树与图的最小树树与图的最小树部分树部分树Page 2742024/9/7运筹学树与图的最小树树与图的最小树避圈法避圈法避圈法避圈法v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5Page 2752024/9/7运筹学树与图的最小树树与图的最小树赋权图赋权图中求最小中求最小中求最小中求最小树树的方法：破圈法和避圈法的方法：破圈法和避圈法的方法：破圈法和避圈法的方法：破圈法和避圈法破圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v1v2v

138、3v4v5v643521边数边数n-1=5Page 2762024/9/7运筹学树与图的最小树树与图的最小树v1v2v3v4v5v643521得到最小树：得到最小树：Min C(T)=15Page 2772024/9/7运筹学树与图的最小树树与图的最小树避圈法避圈法:去掉去掉G中所有中所有边，得到，得到n个孤立点；然后加个孤立点；然后加边。加加边的原的原则为：从最短：从最短边开始添加，加开始添加，加边的的过程中不能形成程中不能形成圈，直到点点圈，直到点点连通通(即即:n-1条条边)。5v1v2v3v4v5v6843752618Page 2782024/9/7运筹学树与图的最小树树与图的最小树v

139、1v2v3v4v5v6435215v1v2v3v4v5v6843752618Min C(T)=15Page 2792024/9/7运筹学树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636练习：练习：练习：练习：应用破圈法求最小树应用破圈法求最小树应用破圈法求最小树应用破圈法求最小树Page 2802024/9/7运筹学树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12

140、3233636Page 2812024/9/7运筹学树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323Page 2822024/9/7运筹学树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323Page 2832024/9/7运筹学树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41

141、 12323Page 2842024/9/7运筹学树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323Page 2852024/9/7运筹学树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 9161625253 3282817174 41 12323Page 2862024/9/7运筹学树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 9161625253 3282817174 41 12323Page 287202

142、4/9/7运筹学树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323Page 2882024/9/7运筹学树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323Page 2892024/9/7运筹学树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323Page 2902024/9/7运筹学树与图的最小树树与图的最小树v1v1v7v7v4v4v3v

143、3v2v2v5v5v6v69 93 3282817174 41 12323Page 2912024/9/7运筹学树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 317174 41 12323min=1+4+9+3+17+23=57Page 2922024/9/7运筹学树与图的最小树树与图的最小树练习：练习：练习：练习：应用避圈法求最小树应用避圈法求最小树应用避圈法求最小树应用避圈法求最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636Page 2932

144、024/9/7运筹学树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636Page 2942024/9/7运筹学树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636Page 2952024/9/7运筹学树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123

145、233636Page 2962024/9/7运筹学树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636Page 2972024/9/7运筹学树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636Page 2982024/9/7运筹学树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 32

146、82817174 41 123233636min=1+4+9+3+17+23=57min=1+4+9+3+17+23=57Page 2992024/9/7运筹学树与图的最小树树与图的最小树课课堂堂堂堂练习练习：3749346321Min C(T)=12Min C(T)=15254173314475答案：答案：Page 3002024/9/7运筹学树与图的最小树树与图的最小树34122323242Min C(T)=12213638534567454321Min C(T)=18Page 3012024/9/7运筹学最短路问题最短路问题如何用最短的如何用最短的线路将三部路将三部电话连起来？起来？此此

147、问题可抽象可抽象为设ABC为等等边三角形，三角形，连接三接三顶点的点的路路线（称（称为网网络）。）。这种网种网络有有许多个，其中最短路多个，其中最短路线者者显然是二然是二边之和（如之和（如ABAC）。）。ABCPage 3022024/9/7运筹学最短路问题最短路问题ABCP但若增加一个周转站（新点但若增加一个周转站（新点P），连接），连接4点的新网络的最短路点的新网络的最短路线为线为PAPBPC。最短新路径之长。最短新路径之长N比原来只连三点的最比原来只连三点的最短路径短路径O要短。这样得到的网络不仅比原来节省材料，而且要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。稳定性也更好。

148、Page 3032024/9/7运筹学最短路问题最短路问题问题描述：描述：就是从就是从给定的网定的网络图中找出一点到各点或任意两点之中找出一点到各点或任意两点之间距离最短的一条路距离最短的一条路 .有些有些问题，如，如选址、管道址、管道铺设时的的选线、设备更新、投更新、投资、某些整数、某些整数规划和划和动态规划的划的问题，也可以，也可以归结为求最短求最短路的路的问题。因此。因此这类问题在生在生产实际中得到广泛中得到广泛应用。用。Page 3042024/9/7运筹学最短路问题最短路问题例例例例6.4 6.4 渡河游渡河游渡河游渡河游戏戏一老一老汉带了一只狼、一只羊、一棵白菜想要从南岸了一只狼、

149、一只羊、一棵白菜想要从南岸过河河到北岸，河上只有一条独木舟，每次除了人以外，只能到北岸，河上只有一条独木舟，每次除了人以外，只能带一一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎怎样安排渡河，才能做到既把所有安排渡河，才能做到既把所有东西都运西都运过河去，河去，并且在河上来回次数最少？并且在河上来回次数最少？这个个问题就可以用求最短路方法就可以用求最短路方法解决。解决。Page 3052024/9/7运筹学最短路问题最短路问题定定义：1）人）人M（Man），狼），狼W（Wolf），）， 羊羊G（Goat），）， 草草H（Hay）2

150、） 点点 vi 表示河岸的状表示河岸的状态3） 边 ek 表示由状表示由状态 vi 经一次渡河到状一次渡河到状态 vj 4） 权边 ek 上的上的权定定为 1我们可以得到下面的加权有向图我们可以得到下面的加权有向图Page 3062024/9/7运筹学最短路问题最短路问题状状态说明：明：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 的最短路问题。的最短路问题。v1v2v3v4v5u5u4u3u2u1P

151、age 3072024/9/7运筹学最短路问题最短路问题求最短路有两种算法求最短路有两种算法: 狄克斯屈拉狄克斯屈拉(Dijkstra)标号算法标号算法 逐次逼近算法逐次逼近算法Page 3082024/9/7运筹学最短路问题最短路问题狄克斯屈拉狄克斯屈拉狄克斯屈拉狄克斯屈拉(Dijkstra)(Dijkstra)标标号算法的基本思路：号算法的基本思路：号算法的基本思路：号算法的基本思路：若序列若序列 vs,v1.vn-1,vn 是从是从vs到到vt间的最短路，的最短路，则序列序列 vs,v1.vn-1 必必为从从vs 到到vn-1的最短路。的最短路。假定假定v1v2 v3 v4是是v1 v4

152、的最短路，则的最短路，则v1 v2 v3一定是一定是v1 v3的最短路，的最短路，v2 v3 v4也一定是也一定是v2 v4的最短路。的最短路。v1v2v3v4v5Page 3092024/9/7运筹学最短路问题最短路问题求网求网络图的最短路，的最短路，设图的起点是的起点是vs,终点是点是vt ,以以vi为起点起点vj为终点的弧点的弧记为 (i, j) 距离距离为dijP P标号标号标号标号( (点标号点标号点标号点标号) )：b(j) 起点起点vs到点到点vj的最短路长；的最短路长；T T标号标号标号标号( (边标号边标号边标号边标号) )： k(i,j)=b(i)+dij，步骤：步骤： 1

153、. 令起点的标号；令起点的标号；b(s)0。 2. 找出所有找出所有vi已标号已标号vj未标号的弧集合未标号的弧集合 B=(i, j) 如果这样的如果这样的弧不存在或弧不存在或vt已标号则计算结束；已标号则计算结束；3. 计算集合计算集合B中弧中弧k(i，j)=b(i)+dij的标号的标号4. 选一个点标号选一个点标号 在终点在终点vl处处标号标号b(l), 返回到第返回到第2步。步。Page 3102024/9/7运筹学最短路问题最短路问题例例6.5 求下求下图v1到到v7的最短路的最短路长及最短路及最短路线86252353421057086225441114751071211v7已标号，计

154、算结束。从已标号，计算结束。从v1到到v7的最短路长是的最短路长是 11,最短路线：最短路线： v1 v4 v6 v7P标号标号T标号标号Page 3112024/9/7运筹学最短路问题最短路问题从上例知，只要某点已从上例知，只要某点已标号，号，说明已找到起点明已找到起点vs到到该点的最短路点的最短路线及最短距离，因此可以将每个点及最短距离，因此可以将每个点标号，求出号，求出vs到任意点的最短路到任意点的最短路线，如果某个点，如果某个点vj不能不能标号，号，说明明vs不可达不可达vj 。注：无向图最短路的求法只将上述步骤注：无向图最短路的求法只将上述步骤2将弧改成边即可。将弧改成边即可。Pag

155、e 3122024/9/7运筹学最短路问题最短路问题例例6.6 求下求下图v1到各点的最短距离及最短路到各点的最短距离及最短路线。4526178393261216180452231039612641166188122482418所有点都已标号，点上的标号就是所有点都已标号，点上的标号就是v1到该点的最短距离，最短到该点的最短距离，最短路线就是红色的链。路线就是红色的链。Page 3132024/9/7运筹学最短路问题最短路问题课堂堂练习：1. 用用Dijkstra算法求下算法求下图从从v1到到v6的最短距离及路的最短距离及路线。v3v54v1v2v4v635222421v1到到v6的最短路为：

156、的最短路为：Page 3142024/9/7运筹学最短路问题最短路问题2. 求从求从v1到到v8的最短路径的最短路径237184566134105275934682Page 3152024/9/7运筹学最短路问题最短路问题237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到到v8的最短路径为的最短路径为v1v4v7v5v8，最短距离为，最短距离为10Page 3162024/9/7运筹学最短路问题最短路问题3. 求下求下图中中v1点到另外任意一点的最短路径点到另外任意一点的最短路径v1v2v3v4v6v5322762133Pa

157、ge 3172024/9/7运筹学最短路问题最短路问题v1V2V3V4 V6V5322762133024714Page 3182024/9/7运筹学最短路问题最短路问题v1V2V3V4 V6V5322762133024714Page 3192024/9/7运筹学最短路问题最短路问题算法适用条件：算法适用条件：Dijkstra算法只适用于全部算法只适用于全部权为非非负情况，如果某情况，如果某边上上权为负的，算法失效。此的，算法失效。此时可采用逐次逼近可采用逐次逼近算法。算法。例例6.7 如右图所示中按如右图所示中按dijkstra算算法可得法可得P(v1)=5为从为从vsv1的最短的最短路长显然

158、是错误的，从路长显然是错误的，从vsv2v1路长只有路长只有3。v2vsv15-58Page 3202024/9/7运筹学最短路问题最短路问题最短路最短路问题的的应用：用：例例6.7 电信公司准信公司准备准准备在甲、乙两地沿路架在甲、乙两地沿路架设一条光一条光缆线，问如何架如何架设使其光使其光缆线路最短？下路最短？下图给出了甲乙两地出了甲乙两地间的交的交通通图。权数表示两地数表示两地间公路的公路的长度（度（单位：公里）。位：公里）。 v1 （甲地）（甲地）1517624431065v2v7 (乙地乙地)v3v4v5v6Page 3212024/9/7运筹学最短路问题最短路问题解：解：这是一个求

159、无向是一个求无向图的最短路的的最短路的问题。Page 3222024/9/7运筹学最短路问题最短路问题例例6.8 设备更新更新问题。某公司使用一台。某公司使用一台设备，在每年年初，在每年年初，公司就要决定是公司就要决定是购买新的新的设备还是是继续使用旧使用旧设备。如果。如果购置新置新设备，就要支付一定的，就要支付一定的购置置费，当然新，当然新设备的的维修修费用用就低。如果就低。如果继续使用旧使用旧设备，可以省去，可以省去购置置费，但，但维修修费用用就高了。就高了。请设计一个五年之内的更新一个五年之内的更新设备的的计划，使得五年划，使得五年内内购置置费用和用和维修修费用用总的支付的支付费用最小。

160、已知：用最小。已知：设备每年年初的价格表每年年初的价格表年份年份12345年初价格年初价格1111121213Page 3232024/9/7运筹学最短路问题最短路问题设备维修修费如下表如下表使用年数使用年数0-11-22-33-44-5每年维修费用每年维修费用5681118解：解：将问题转化为最短路问题，如下图：用将问题转化为最短路问题，如下图：用vi表示表示“第第i年年年年初购进一台新设备初购进一台新设备”,弧（弧（vi,vj）表示第）表示第i年年初购进的设备年年初购进的设备一直使用到第一直使用到第j年年初。年年初。v1v2v3v4v5v6Page 3242024/9/7运筹学最短路问题最

161、短路问题把所有弧的把所有弧的权数数计算如下表，算如下表，把把权数数赋到到图中，再用中，再用Dijkstra算法求最短路。算法求最短路。123456116223041592162230413172331417235186v1v2v3v4v5v6162230415916223041312317181723Page 3252024/9/7运筹学最短路问题最短路问题 最最终得到下得到下图，可知，可知，v1到到v6的距离是的距离是53，最短路径有两条：，最短路径有两条： v1v3v6和和 v1v4v6 V1（0,s）v3v4(41,1) v5v62230415916(22,1)3041312317181

162、723 V2（16,1）16(30,1)(53,3)(53,4)Page 3262024/9/7运筹学网络的最大流网络的最大流如何制定一个运如何制定一个运输计划使生划使生产地到地到销售地的售地的产品品输送量最大。送量最大。这就是一个网就是一个网络最大流最大流问题。Page 3272024/9/7运筹学网络的最大流网络的最大流基本概念：基本概念：1. 1. 容量网容量网容量网容量网络络：队网网络上的每条弧上的每条弧(vi,vj)都都给出一个最大的出一个最大的通通过能力，称能力，称为该弧的弧的容量容量容量容量，简记为cij。容量网。容量网络中通常中通常规定一个定一个发发点点点点(也称源点，也称源点

163、，记为s)和一个和一个收点收点收点收点(也称也称汇点，点，记为t)，网，网络中其他点称中其他点称为中中中中间间点点点点。st4844122679Page 3282024/9/7运筹学网络的最大流网络的最大流2. 网网络的最大流的最大流是指网是指网络中从中从发点到收点之点到收点之间允允许通通过的最大流量。的最大流量。3. 流与可行流流与可行流 流流是指加在网络各条弧上的实际流量，对加在弧是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上上的负载量记为的负载量记为fij。若。若fij=0，称为零流。，称为零流。满足以下条件的一组流称为满足以下条件的一组流称为可行流可行流。 容量限制条件。容量

164、网络上所有的弧满足：容量限制条件。容量网络上所有的弧满足：0fijcij 中间点平衡条件。中间点平衡条件。 若以若以v(f)表示网络中从表示网络中从st的流量，则有：的流量，则有：Page 3292024/9/7运筹学网络的最大流网络的最大流结论：任何网络上一定存在可行流。（零流即是结论：任何网络上一定存在可行流。（零流即是可行流）可行流）网络最大流问题：网络最大流问题：指满足容量限制条件和中间点平衡的条件下，使指满足容量限制条件和中间点平衡的条件下，使v(f)值值达到最大。达到最大。Page 3302024/9/7运筹学网络的最大流网络的最大流 割与割集割与割集割是指容量网络中的发点和收点分

165、割开，并使割是指容量网络中的发点和收点分割开，并使st的流中断的流中断的一组弧的集合。割容量是组成割集合中的各条弧的容量之的一组弧的集合。割容量是组成割集合中的各条弧的容量之和，用和，用 表示。表示。如下图中，如下图中，AA将网络上的点分割成将网络上的点分割成 两个集合。并有两个集合。并有 ，称弧的集合，称弧的集合(v1,v3),(v2,v4)是一个割，且是一个割，且 的流量为的流量为18。 Page 3312024/9/7运筹学网络的最大流网络的最大流stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(3)7(6)AABBPage 3322024/9/7运筹学网

166、络的最大流网络的最大流定理定理定理定理1 1 设网络设网络N中一个从中一个从 s 到到 t 的流的流 f 的流量为的流量为v(f )， (V, V)为任意一个割集，则为任意一个割集，则 v(f ) = f(V, V) f(V, V) 推论推论推论推论1 1 对网络对网络 N中任意流量中任意流量v(f )和割集和割集 (V, V)，有，有v(f ) c(V, V)证明证明 w= f(V, V) f(V, V) f(V, V) c(V, V)推论推论推论推论2 2 最大流量最大流量v (f )不大于最小割集的容量，即：不大于最小割集的容量，即：v (f ) minc(V, V) 定理定理定理定理2

167、 2 在网在网络中中st的最大流量等于它的最小割集的容量，的最大流量等于它的最小割集的容量，即：即： v (f ) = c (V, V) Page 3332024/9/7运筹学网络的最大流网络的最大流增广增广增广增广链链在网在网络的的发点和收点之点和收点之间能找到一条能找到一条链，在，在该链上所有上所有指向指向为st的弧，称的弧，称为前向弧，前向弧，记作作+,存在存在f0，则称称这样的的链为增广增广链。例如下。例如下图中，中，sv2v1v3v4t。定理定理定理定理3 3 网络网络N中的流中的流 f 是最大流当且仅当是最大流当且仅当N中不包含任何增广中不包含任何增广链链Page 3342024/

168、9/7运筹学网络的最大流网络的最大流stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(4)7(5)Page 3352024/9/7运筹学网络的最大流网络的最大流求网求网络最大流的最大流的标号算法：号算法： 基本思想基本思想基本思想基本思想 由一个流开始，系由一个流开始，系统地搜地搜寻增广增广链，然后在此，然后在此链上增流，上增流，继续这个增流个增流过程，直至不存在增广程，直至不存在增广链。 基本方法基本方法基本方法基本方法 (1)找出第一个可行流，（例如所有弧的流量找出第一个可行流，（例如所有弧的流量fij =0。）。）(2)用标号的方法找一条增广链用标号的方法

169、找一条增广链 首先给发点首先给发点s标号标号(),标号中的数字表示允许的最大调整标号中的数字表示允许的最大调整量。量。 选择一个点选择一个点 vi 已标号并且另一端未标号的弧沿着某条链已标号并且另一端未标号的弧沿着某条链向收点检查：向收点检查：Page 3362024/9/7运筹学网络的最大流网络的最大流 如果弧的起点为如果弧的起点为vi，并且有，并且有fij0，则，则vj标号标号(fji)(3) 重复第重复第(2)步，可能出现两种结局：步，可能出现两种结局： 标号过程中断，标号过程中断，t无法标号，说明网络中不存在增广链，无法标号，说明网络中不存在增广链，目前流量为最大流。同时可以确定最小割

170、集，目前流量为最大流。同时可以确定最小割集，记已标号的点记已标号的点集为集为V,未标号的点集合为未标号的点集合为V,(V,V)为网络的最小割。为网络的最小割。 t得到标号，反向追踪在网络中找到一条从得到标号，反向追踪在网络中找到一条从s到到t得由标号得由标号点及相应的弧连接而成的增广链。继续第点及相应的弧连接而成的增广链。继续第(4)步步Page 3372024/9/7运筹学网络的最大流网络的最大流(4) 修改流量。设原图可行流为修改流量。设原图可行流为f，令，令得到网络上一个新的可行流得到网络上一个新的可行流f。(5) 擦除图上所有标号，重复擦除图上所有标号，重复(1)-(4)步，直到图中找

171、不到任步，直到图中找不到任何增广链，计算结束。何增广链，计算结束。Page 3382024/9/7运筹学网络的最大流网络的最大流例例6.10 用标号算法求下图中用标号算法求下图中st的最大流量，并找出最小割。的最大流量，并找出最小割。stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)Page 3392024/9/7运筹学网络的最大流网络的最大流解：解：(1) 先先给s标号号()stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()Page 3402024/9/7运筹学网络的最大流网络的最大流stv1v3v2

172、v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()(2) 检查与检查与s点相邻的未标号的点，因点相邻的未标号的点，因fs1cs1，故对，故对v1标号标号=min, cs1-fs1=1,(1)Page 3412024/9/7运筹学网络的最大流网络的最大流stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(6)()(1)(2) 检查与检查与v1点相邻的未标号的点，因点相邻的未标号的点，因f13c13，故对，故对v3标号标号=min1, c13-f13= min1, 6= 1(1)Page 3422024/9/7运筹学网络的最大流

173、网络的最大流stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()(1)(1)(3) 检查与检查与v3点相邻的未标号的点，因点相邻的未标号的点，因f3tc3t，故对，故对vt标号标号=min1, c3t-f3t= min1, 1= 1(1)找到一条增广链找到一条增广链sv1v3tPage 3432024/9/7运筹学网络的最大流网络的最大流(4) 修改增广链上的流量，非增广链上的流量不变，得到新修改增广链上的流量，非增广链上的流量不变，得到新的可行流。的可行流。stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(3)7(

174、5)()(1)(1)(1)Page 3442024/9/7运筹学网络的最大流网络的最大流(5) 擦除所有标号，重复上述标号过程，寻找另外的增广链。擦除所有标号，重复上述标号过程，寻找另外的增广链。stv1v3v2v48(8)9(4)5(5)10(8)6(0)2(0)9(9)5(3)7(5)()(1)(1)(1)Page 3452024/9/7运筹学网络的最大流网络的最大流(5) 擦除所有标号，重复上述标号过程，寻找另外的增广链。擦除所有标号，重复上述标号过程，寻找另外的增广链。stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)()(2)(2)=min

175、,2=2(2)(1)=min2,3=2(3)=min2,5=2(2)(1)(4)=min2,1=1(1)(t)=min1,2=1Page 3462024/9/7运筹学网络的最大流网络的最大流(6) 修改增广链上的流量，非增广链上的流量不变，得到新修改增广链上的流量，非增广链上的流量不变，得到新的可行流。的可行流。stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)()(2)(2)(2)(1)(1)Page 3472024/9/7运筹学网络的最大流网络的最大流stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)(

176、)(2)(2)(2)(1)(1)(7) 擦除所有标号，重复上述标号过程，寻找另外的增广链。擦除所有标号，重复上述标号过程，寻找另外的增广链。Page 3482024/9/7运筹学网络的最大流网络的最大流stv1v3v2v48(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)=min1,2=1(3)=min1,4=1Page 3492024/9/7运筹学网络的最大流网络的最大流例例6.9 求下图求下图st的最大流，并找

177、出最小割的最大流，并找出最小割stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)Page 3502024/9/7运筹学网络的最大流网络的最大流stv1v2v3v4v54(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)=min6,2=2(2)(t)=min2,5=2(2)存在增广链存在增广链存在增广链存在增广链svsv2 2vv3 3 t t

178、Page 3512024/9/7运筹学网络的最大流网络的最大流(2) 修改增广链上的流量，非增广链上的流量不变，得到新修改增广链上的流量，非增广链上的流量不变，得到新的可行流。的可行流。stv1v2v3v4v54(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)Page 3522024/9/7运筹学网络的最大流网络的最大流(3) 擦除原标号，重新搜寻增广链。擦除原标号，重新搜寻增广链。stv1v2v3v4v54(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)

179、Page 3532024/9/7运筹学网络的最大流网络的最大流(4) 重新搜寻增广链。重新搜寻增广链。stv1v2v3v4v54(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)=min4,1=1(3)=min1,2=1(1)(1)(t)=min1,3=1存在增广链：存在增广链：存在增广链：存在增广链：svsv2 2vv5 5vv3 3 t tPage 3542024/9/7运筹学网络的最大流网络的最大流(5) 修改增广链上的流量，非增广链上的流量不变，得到新的可修改增广链上的流量，非增广链上的流量不变，

180、得到新的可行流。行流。stv1v2v3v4v54(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)Page 3552024/9/7运筹学网络的最大流网络的最大流(6) 擦除原标号擦除原标号stv1v2v3v4v54(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)Page 3562024/9/7运筹学网络的最大流网络的最大流stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)()

181、(1)(1)(1)(5)=min,1=1(5)=min1,1=1(5)=min1,2=1(7) 重新搜寻增广链。重新搜寻增广链。存在增广链：存在增广链：存在增广链：存在增广链：svsv5 5vv3 3 t tPage 3572024/9/7运筹学网络的最大流网络的最大流(8) 调整增广链上的流量，非增广链流量不变，得到新的可行流调整增广链上的流量，非增广链流量不变，得到新的可行流stv1v2v3v4v54(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)Page 3582024/9/7运筹学网络的最大流网络的最大流stv1v2

182、v3v4v54(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) 擦除原标号擦除原标号Page 3592024/9/7运筹学网络的最大流网络的最大流stv1v2v3v4v54(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)=min1,1=1(1)(4)=min1,1=1(1)(t)=min1,1=1(1)存在增广链：存在增广链：存在增广链：存在增广链：svsv1 1vv5 5vv4 4tt