运运筹筹学学(OperationsResearch)经济学核心课程经济学核心课程经济学核心课程经济学核心课程绪绪论论（1）运筹学简述）运筹学简述（2）运筹学的主要内容）运筹学的主要内容（3）本课程的教材及参考书）本课程的教材及参考书（4）本课程的特点和要求）本课程的特点和要求（5）本课程授课方式与考核）本课程授课方式与考核（6）运筹学在工商管理中的应用）运筹学在工商管理中的应用本章主要内容：本章主要内容：Page3运筹学简述运筹学简述运筹学（运筹学（OperationsResearch）系统工程的最重要的理论基础之一，在美国有人把运系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学筹学称之为管理科学(ManagementScience)。运筹学所研究的。运筹学所研究的问题，可简单地归结为一句话：问题，可简单地归结为一句话：“依照给定条件和目标，从众多方案中选择最佳方案依照给定条件和目标，从众多方案中选择最佳方案”故有人称之为最优化技术。故有人称之为最优化技术。Page4运筹学简述运筹学简述运筹学的历史运筹学的历史“运作研究运作研究(OperationalResearch)小组小组”:解决解决复杂的战略和战术问题。例如：复杂的战略和战术问题。例如：1.如何合理运用雷达有效地对付德军德空袭如何合理运用雷达有效地对付德军德空袭2.对商船如何进行编队护航，使船队遭受德国潜对商船如何进行编队护航，使船队遭受德国潜艇攻击时损失最少；艇攻击时损失最少；3.在各种情况下如何调整反潜深水炸弹的爆炸深在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等。度，才能增加对德国潜艇的杀伤力等。Page5运筹学的主要内容运筹学的主要内容数学规划（数学规划（线性规划、整数规划、目标规划线性规划、整数规划、目标规划、动态、动态规划等）规划等）图论图论存储论存储论排队论排队论对策论对策论排序与统筹方法排序与统筹方法决策分析决策分析Page6本课程的教材及参考书本课程的教材及参考书选用教材选用教材 运筹学基础及应用运筹学基础及应用胡运权主编胡运权主编 哈工大出版社哈工大出版社参考教材参考教材运筹学教程运筹学教程胡运权主编胡运权主编 （第（第2 2版）清华出版社版）清华出版社管理运筹学管理运筹学韩伯棠主编韩伯棠主编 （第（第2 2版）高等教育出版版）高等教育出版社社运筹学运筹学( (修订版修订版) ) 钱颂迪主编钱颂迪主编 清华出版社清华出版社Page7本课程的特点和要求本课程的特点和要求先修课：先修课：高等数学，基础概率、线性代数高等数学，基础概率、线性代数特点：特点：系统整体优化；多学科的配合；模型方法的应用系统整体优化；多学科的配合；模型方法的应用运筹学的研究的主要步骤：运筹学的研究的主要步骤：真实系统真实系统系统分析系统分析问题描述问题描述模型建立模型建立与修改与修改模型求解模型求解与检验与检验结果分析与结果分析与实施实施数据准备数据准备Page8本课程授课方式与考核本课程授课方式与考核学科总成绩学科总成绩平时成绩平时成绩（4040）课堂考勤课堂考勤（5050）平时作业平时作业（5050）期末成绩期末成绩（6060）讲授为主，结合习题作业讲授为主，结合习题作业Page9运筹学在工商管理中的应用运筹学在工商管理中的应用运筹学在工商管理中的应用涉及几个方面：运筹学在工商管理中的应用涉及几个方面：1.1. 生产计划生产计划2.2. 运输问题运输问题3.3. 人事管理人事管理4.4. 库存管理库存管理5.5. 市场营销市场营销6.6. 财务和会计财务和会计另外，还应用于设备维修、更新和可靠性分析，项目的选择另外，还应用于设备维修、更新和可靠性分析，项目的选择与评价，工程优化设计等。与评价，工程优化设计等。Page10运筹学在工商管理中的应用运筹学在工商管理中的应用Interface上发表的部分获奖项目上发表的部分获奖项目组织组织应用应用效果效果联合航空公司联合航空公司在满足乘客需求的前提下，以最低成本进在满足乘客需求的前提下，以最低成本进行订票及机场工作班次安排行订票及机场工作班次安排每年节约成本每年节约成本600600万美元万美元CitgoCitgo石油公司石油公司优化炼油程序及产品供应、配送和营销优化炼油程序及产品供应、配送和营销每年节约成本每年节约成本70007000万万AT&TAT&T优化商业用户的电话销售中心选址优化商业用户的电话销售中心选址每年节约成本每年节约成本4.064.06亿美元，销亿美元，销售额大幅增加售额大幅增加标准品牌公司标准品牌公司控制成本库存（制定最优再定购点和定购控制成本库存（制定最优再定购点和定购量确保安全库存）量确保安全库存）每年节约成本每年节约成本380380万美元万美元法国国家铁路公司法国国家铁路公司制定最优铁路时刻表并调整铁路日运营量制定最优铁路时刻表并调整铁路日运营量每年节约成本每年节约成本15001500万美元，年万美元，年收入大幅增加。收入大幅增加。Taco BellTaco Bell优化员工安排，以最低成本服务客户优化员工安排，以最低成本服务客户每年节约成本每年节约成本13001300万美元万美元DeltaDelta航空公司航空公司优化配置上千个国内航线航班来实现利润优化配置上千个国内航线航班来实现利润最大化最大化每年节约成本每年节约成本1 1亿美元亿美元Page11“管理运筹学管理运筹学”软件介绍软件介绍“管理运筹学管理运筹学”2.02.0版包括：线性规划、运输问题、整数规划（版包括：线性规划、运输问题、整数规划（0-10-1整数整数规划、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、规划、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、决策分析、预测问题和层次分析法，共决策分析、预测问题和层次分析法，共1515个子模块。个子模块。Chapter1线性规划线性规划(LinearProgramming)LP的数学模型的数学模型图解法图解法单纯形法单纯形法单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法LP模型的应用模型的应用本章主要内容：本章主要内容：本章主要内容：本章主要内容：Page13线性规划问题的数学模型线性规划问题的数学模型1.规划问题规划问题生产和经营管理中经常提出如何合理安排，使人力、生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。这就是规划问题。线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：（1 1）当任务或目标确定后，如何统筹兼顾，合理安排，用）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源最少的资源 （如资金、设备、原标材料、人工、时间等）（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标去完成确定的任务或目标（2 2）在一定的资源条件限制下，如何组织安排生产获得最）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多好的经济效益（如产品量最多 、利润最大、利润最大. .）Page14线性规划问题的数学模型线性规划问题的数学模型例例1.1如图所示，如何截取如图所示，如何截取x使铁皮所围成的容积最使铁皮所围成的容积最大？大？x xa aPage15线性规划问题的数学模型线性规划问题的数学模型例例1.2某企业计划生产甲、乙两种产品。这些产品分某企业计划生产甲、乙两种产品。这些产品分别要在别要在A、B、C、D、四种不同的设备上加工。按工四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？企业总的利润最大？设设备备产产品品ABCD利润（元）利润（元）甲甲21402乙乙22043有有效效台台时时1281612Page16线性规划问题的数学模型线性规划问题的数学模型解：设解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：分别为甲、乙两种产品的产量，则数学模型为：maxZ=2xmaxZ=2x1 1+3x+3x2 2 xx1 10,x0,x2 200s.t.s.t.2x2x1 1+2x+2x2 21212xx1 1+2x+2x2 2884x4x1 116164x4x2 21212Page17线性规划问题的数学模型线性规划问题的数学模型2. 2. 2. 2. 线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成决策变量决策变量决策变量决策变量DecisionvariablesDecisionvariables目标函数目标函数目标函数目标函数ObjectivefunctionObjectivefunction约束条件约束条件约束条件约束条件ConstraintsConstraints其特征是：其特征是：其特征是：其特征是：（1 1 1 1）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的线性线性线性线性函数，函数，函数，函数，通常是求最大值或最小值；通常是求最大值或最小值；通常是求最大值或最小值；通常是求最大值或最小值；（2 2 2 2）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的线性线性线性线性不不不不等式或等式。等式或等式。等式或等式。等式或等式。 怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？ Page18线性规划问题的数学模型线性规划问题的数学模型目标函数：目标函数：目标函数：目标函数：约束条件：约束条件：约束条件：约束条件：3.3.线性规划数学模型的一般形式线性规划数学模型的一般形式线性规划数学模型的一般形式线性规划数学模型的一般形式简写为：简写为：Page19线性规划问题的数学模型线性规划问题的数学模型向量形式：向量形式：向量形式：向量形式：其中：其中：Page20线性规划问题的数学模型线性规划问题的数学模型矩阵形式：矩阵形式：矩阵形式：矩阵形式：其中：其中：Page21线性规划问题的数学模型线性规划问题的数学模型3.线性规划问题的标准形式线性规划问题的标准形式特点：特点：(1)目标函数求最大值（有时求最小值）目标函数求最大值（有时求最小值）(2)约束条件都为等式方程，且右端常数项约束条件都为等式方程，且右端常数项bi都大于或等于零都大于或等于零(3)决策变量决策变量xj为非负。为非负。Page22线性规划问题的数学模型线性规划问题的数学模型（2 2 2 2）如何化标准形式）如何化标准形式）如何化标准形式）如何化标准形式 目标函数的转换目标函数的转换 如果是求极小值即如果是求极小值即 ，则可将目标函数，则可将目标函数乘以乘以(-1)(-1)，可化为求极大值问题。，可化为求极大值问题。也就是：令也就是：令 ，可得到上式。，可得到上式。即即 若存在取值无约束的变量若存在取值无约束的变量 ，可令，可令 其中：其中： 变量的变换变量的变换Page23线性规划问题的数学模型线性规划问题的数学模型 约束方程的转换：由不等式转换为等式。约束方程的转换：由不等式转换为等式。称为松弛变量称为松弛变量称为剩余变量称为剩余变量 变量变量 的变换的变换 可令可令 ，显然，显然Page24线性规划问题的数学模型线性规划问题的数学模型例例1.3将下列线性规划问题化为标准形式将下列线性规划问题化为标准形式用用 替换替换 ，且，且 解解:（）因为（）因为x3无符号要求无符号要求，即，即x3取正值也可取负值，标准取正值也可取负值，标准型中要求变量非负，所以型中要求变量非负，所以Page25线性规划问题的数学模型线性规划问题的数学模型(2)第一个约束条件是第一个约束条件是“”号，在号，在“”左端加入松驰变左端加入松驰变量量x4，x40,化为等式；化为等式；(3)第二个约束条件是第二个约束条件是“”号，在号，在“”左端减去剩余变左端减去剩余变量量x5，x50；(4)第第3个约束方程右端常数项为个约束方程右端常数项为-5，方程两边同乘以，方程两边同乘以(-1),将将右端常数项化为正数；右端常数项化为正数；(5)目标函数是最小值，为了化为求最大值，令目标函数是最小值，为了化为求最大值，令z=-z,得到得到maxz=-z，即当，即当z达到最小值时达到最小值时z达到最大值，反之亦然达到最大值，反之亦然;Page26线性规划问题的数学模型线性规划问题的数学模型标准形式如下：标准形式如下：Page27线性规划问题的数学模型线性规划问题的数学模型4. 4. 线性规划问题的解线性规划问题的解线性规划问题线性规划问题求解线性规划问题，就是从满足约束条件求解线性规划问题，就是从满足约束条件(2)、(3)的方程的方程组中找出一个解，使目标函数组中找出一个解，使目标函数(1)达到最大值。达到最大值。Page28线性规划问题的数学模型线性规划问题的数学模型 可行解可行解：满足：满足约束条件约束条件、的解为可行解。所有可行解的解为可行解。所有可行解的集合为可行域。的集合为可行域。 最优解最优解：使目标函数达到最大值的可行解。：使目标函数达到最大值的可行解。基：基：设设A为为约束条件约束条件的的mn阶系数矩阵阶系数矩阵(m04010换换出出行行将将3化为化为15/311801/301/31011/3303005/304/3乘乘以以1/3后后得得到到103/51/518011/52/540011Page48单纯形法的计算步骤单纯形法的计算步骤例例1.9用单纯形法求解用单纯形法求解解：将数学模型化为标准形式：解：将数学模型化为标准形式：不难看出不难看出x4、x5可作为初始基变量，列单纯形表计算。可作为初始基变量，列单纯形表计算。Page49单纯形法的计算步骤单纯形法的计算步骤cj12100icB基变量基变量bx1x2x3x4x50x4152-32100x5201/31501121000x42x220x x2 22 21/3150120753017131/309022560x x1 111017/31/31250128/9-1/92/335/300-98/9 -1/9 -7/3Page50单纯形法的计算步骤单纯形法的计算步骤学习要点：学习要点：1.线性规划解的概念以及线性规划解的概念以及3个基本定理个基本定理2.熟练掌握单纯形法的解题思路及求解步骤熟练掌握单纯形法的解题思路及求解步骤Page51单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法人工变量法：人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大加的变量称为人工变量，构成的可行基称为人工基，用大M M法或两阶段法求解，这种用人工变量作桥梁的求解方法称法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。为人工变量法。Page52单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法例例1.10用大用大M法解下列线性规划法解下列线性规划解：首先将数学模型化为标准形式解：首先将数学模型化为标准形式系数矩阵中不存在系数矩阵中不存在单位矩阵，无法建单位矩阵，无法建立初始单纯形表。立初始单纯形表。Page53单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法故人为添加两个单位向量，得到人工变量单纯形法数学模型：故人为添加两个单位向量，得到人工变量单纯形法数学模型：其其中中：M是是一一个个很很大大的的抽抽象象的的数数，不不需需要要给给出出具具体体的的数数值值，可可以以理理解解为为它它能能大大于于给给定定的的任任何何一一个个确确定定数数值值；再再用用前前面面介介绍的单纯形法求解该模型，计算结果见下表。绍的单纯形法求解该模型，计算结果见下表。Page54单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7i0x64-431-10104-Mx5101-1201005-Mx712-21000113-2M2+M-1+2M-M0x63-650-1013/5-Mx58-3300108/3-1x312-210005-6M5M0-M002x23/56/5101/50-Mx531/53/5003/5131/3-1x311/52/5012/50500002x213010123x131/310015/3-1x319/300102/3000-5-25/3Page55单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法解的判别：解的判别：1）唯一最优解判别：最优表中所有非基变量的检验数非零）唯一最优解判别：最优表中所有非基变量的检验数非零,则线则线规划具有唯一最优解。规划具有唯一最优解。2）多重最优解判别：最优表中存在非基变量的检验数为零）多重最优解判别：最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解（或无穷多最优解）。则线则性规划具有多重最优解（或无穷多最优解）。3）无界解判别：某个）无界解判别：某个k0且且aik（i=1，2,m）则线性）则线性规划具有无界解。规划具有无界解。4）无无可可行行解解的的判判断断：当当用用大大M单单纯纯形形法法计计算算得得到到最最优优解解并并且存在且存在Ri0时，则表明原线性规划无可行解。时，则表明原线性规划无可行解。5）退化解的判别：）退化解的判别：存在某个基变量为零的基本可行解。存在某个基变量为零的基本可行解。Page56单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法单纯性法小结单纯性法小结:建建立立模模型型个个数数取取值值右右端端项项等式或等式或不等式不等式极大或极小极大或极小新加变量新加变量系数系数两两个个三个三个以上以上xj0xj无无约束约束xj 0bi 0bi mi时，企业愿意时，企业愿意购进这种资源，单位纯利为购进这种资源，单位纯利为yi*mi，则有利可图；如果，则有利可图；如果yi*mi则购进资源则购进资源i，可，可获单位纯利获单位纯利yi*mi若若yi*mi则转让资源则转让资源i，可获单位纯利，可获单位纯利miyiPage99对偶问题的经济解释影子价格对偶问题的经济解释影子价格3）影子价格在资源利用中的应用）影子价格在资源利用中的应用根据对偶理论的互补松弛性定理根据对偶理论的互补松弛性定理:Y*Xs=0,YsX*=0表明生产过程中如果某种资源表明生产过程中如果某种资源bi未得到充分利用时，该种资未得到充分利用时，该种资源的影子价格为源的影子价格为0；若当资源资源的影子价格不为；若当资源资源的影子价格不为0时，表明时，表明该种资源在生产中已耗费完。该种资源在生产中已耗费完。Page100对偶问题的经济解释影子价格对偶问题的经济解释影子价格4）影子价格对单纯形表计算的解释）影子价格对单纯形表计算的解释单纯形表中的检验数单纯形表中的检验数其中其中c cj j表示第表示第j j种产品的价格种产品的价格; ; 表示生产该表示生产该种产品所消耗的各项资源的影子价格的总和种产品所消耗的各项资源的影子价格的总和, ,即产品的隐含即产品的隐含成本。成本。当产值大于隐含成本时，即当产值大于隐含成本时，即 ，表明生产该项产，表明生产该项产品有利，可在计划中安排；否则品有利，可在计划中安排；否则 ，用这些资源，用这些资源生产别的产品更有利，不在生产中安排该产品。生产别的产品更有利，不在生产中安排该产品。Page101对偶单纯形法对偶单纯形法 对偶单纯形法是求解线性规划的另一个基本方法。对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称它是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。形法。对偶单纯形法原理对偶单纯形法原理对偶单纯形法原理对偶单纯形法原理对偶单纯形法基本思路：对偶单纯形法基本思路：对偶单纯形法基本思路：对偶单纯形法基本思路： 找出一个对偶问题的可行基，保持对偶问题为可行解的找出一个对偶问题的可行基，保持对偶问题为可行解的条件下，判断条件下，判断XB是否可行（是否可行（XB为非负），若否，通过变换基为非负），若否，通过变换基解，直到找到原问题基可行解（即解，直到找到原问题基可行解（即XB为非负），这时原问题为非负），这时原问题与对偶问题同时达到可行解，由定理与对偶问题同时达到可行解，由定理4可得最优解。可得最优解。Page102对偶单纯形法对偶单纯形法找出一个找出一个DP的可行基的可行基LP是否可行是否可行（XB0）保持保持DP为可行解情况下转移到为可行解情况下转移到LP的另一个基本解的另一个基本解最优解最优解是是否否循循环环结束结束Page103对偶单纯形法对偶单纯形法例例2.9用对偶单纯形法求解：用对偶单纯形法求解：解解:（1）将模型转化为求最大化问题，约束方程化为等式求将模型转化为求最大化问题，约束方程化为等式求出一组基本解，因为对偶问题可行，即全部检验数出一组基本解，因为对偶问题可行，即全部检验数0（求（求max问题）。问题）。Page104对偶单纯形法对偶单纯形法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-150000Page105对偶单纯形法对偶单纯形法cj-9-12-15000bcBxBx1x2x3x4x5x60x4-9/5-9/5010-1/5-36/50x5-9/5-14/5001-1/5-46/5-15x31/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/14Page106对偶单纯形法对偶单纯形法cj-9-12-15000cBxBx1x2x3x4x5x6b-9x1100-14/911/92-12x20101-102-15x30011/90-2/92000-1/3-3-7/3原问题的最优解为：原问题的最优解为：X*=（2,2,2,0,0,0），），Z*=72其对偶问题的最优解为：其对偶问题的最优解为：Y*=（1/3,3,7/3），），W*=72Page107对偶单纯形法对偶单纯形法 对偶单纯形法应注意的问题：对偶单纯形法应注意的问题： 用用对对偶偶单单纯纯形形法法求求解解线线性性规规划划是是一一种种求求解解方方法法，而而不不是是去去求求对对偶问题的最优解偶问题的最优解 初初始始表表中中一一定定要要满满足足对对偶偶问问题题可可行行，也也就就是是说说检检验验数数满满足足最最优优判别准则判别准则 最小比值中最小比值中 的绝对值是使得比值非负，在极小化问题的绝对值是使得比值非负，在极小化问题j j00，分母分母a aijij0 0 这时必须取绝对值。在极大化问题中，这时必须取绝对值。在极大化问题中， j j00，分母分母a aijij00， 总满足非负，这时绝对值符号不起作用，总满足非负，这时绝对值符号不起作用，可以去掉。如在本例中将目标函数写成可以去掉。如在本例中将目标函数写成这里这里j j 0 0在求在求k k时就可以不带绝对值符号。时就可以不带绝对值符号。Page108对偶单纯形法对偶单纯形法 对对偶偶单单纯纯形形法法与与普普通通单单纯纯形形法法的的换换基基顺顺序序不不一一样样，普普通通单单纯纯形形法法是是先先确确定定进进基基变变量量后后确确定定出出基基变变量量，对对偶偶单单纯纯形形法法是是先先确确定定出出基基变变量后确定进基变量；量后确定进基变量； 普通单纯形法的最小比值是普通单纯形法的最小比值是 其目的是保证下一个原问题的基本解可行，对偶单纯形法的最小比其目的是保证下一个原问题的基本解可行，对偶单纯形法的最小比值是值是其目的是保证下一个对偶问题的基本解可行其目的是保证下一个对偶问题的基本解可行 对偶单纯形法在确定出基变量时，若不遵循对偶单纯形法在确定出基变量时，若不遵循 规规则则，任任选选一一个个小小于于零零的的b bi i对对应应的的基基变变量量出出基基，不不影影响响计计算算结结果果，只是迭代次数可能不一样。只是迭代次数可能不一样。Page109本章小结本章小结学习要点：学习要点：1.线性规划解的概念以及线性规划解的概念以及3个基本定理个基本定理2.熟练掌握单纯形法的解题思路及求解步骤熟练掌握单纯形法的解题思路及求解步骤Chapter3运输规划运输规划(TransportationProblem)(TransportationProblem)运输规划问题的数学模型运输规划问题的数学模型表上作业法表上作业法运输问题的应用运输问题的应用本章主要内容：本章主要内容：本章主要内容：本章主要内容：Page111运输规划问题的数学模型运输规划问题的数学模型例例3.1某公司从两个产地某公司从两个产地A1、A2将物品运往三个销地将物品运往三个销地B1,B2,B3，各产地的产量、各销地的销量和各产地运往各销地，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？用最小？B1B2B3产量产量A1646200A2655300销量销量150150200Page112运输规划问题的数学模型运输规划问题的数学模型解：产销平衡问题：总产量解：产销平衡问题：总产量=总销量总销量500设设xij为从产地为从产地Ai运往销地运往销地Bj的运输量，得到下列运输量的运输量，得到下列运输量表：表：B1B2B3产量产量A1x11x12x13200A2x21x22x23300销量销量150150200MinC=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200 xij0(i=1、2；j=1、2、3）Page113运输规划问题的数学模型运输规划问题的数学模型运输问题的一般形式：产销平衡运输问题的一般形式：产销平衡A1、A2、Am表示某物资的表示某物资的m个产地；个产地；B1、B2、Bn表示表示某物质的某物质的n个销地；个销地；ai表示产地表示产地Ai的产量；的产量；bj表示销地表示销地Bj的销量；的销量；cij表示把物资从产地表示把物资从产地Ai运往销地运往销地Bj的单位运价。设的单位运价。设xij为从产地为从产地Ai运往销地运往销地Bj的运输量，得到下列一般运输量问题的模型：的运输量，得到下列一般运输量问题的模型：Page114运输规划问题的数学模型运输规划问题的数学模型变化：变化：1）有时目标函数求最大。如求利润最大或营业额最大等；）有时目标函数求最大。如求利润最大或营业额最大等；2）当某些运输线路上的能力有限制时，在模型中直接加入）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束约束条件（等式或不等式约束)；3）产销不平衡时，可加入假想的产地（销大于产时）或销）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。地（产大于销时）。定理定理:设有设有m个产地个产地n个销地且产销平衡的运输问题，则基个销地且产销平衡的运输问题，则基变量数为变量数为m+n-1。Page115表上作业法表上作业法表上作业法是一种求解运输问题的特殊方法，其表上作业法是一种求解运输问题的特殊方法，其实质是单纯实质是单纯形法。形法。步骤步骤描述描述方法方法第一步第一步求初始基行可行解（初始调运方案）求初始基行可行解（初始调运方案）最小元素法、最小元素法、元素差额法、元素差额法、第二步第二步求检验数并判断是否得到最优解当非基变量的求检验数并判断是否得到最优解当非基变量的检验数检验数ijij全都非负时得到最优解，若存在检验全都非负时得到最优解，若存在检验数数ijij 00，说明还没有达到最优，转第三步。说明还没有达到最优，转第三步。闭回路法和位闭回路法和位势法势法第三步第三步调整运量，即换基，选一个变量出基，对原运调整运量，即换基，选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步量进行调整得到新的基可行解，转入第二步Page116表上作业法表上作业法例例3.2 3.2 某运输资料如下表所示：某运输资料如下表所示：单位单位 销地销地 运价运价 产地产地产量产量3 311113 310107 71 19 92 28 84 47 74 410105 59 9销量销量3 36 65 56 6问：应如何调运可使总运输费用最小？问：应如何调运可使总运输费用最小？Page117表上作业法表上作业法解：第解：第1步步求初始方案求初始方案方法方法1：最小元素法：最小元素法基本思想是就近供应，即从运价最小的地方开始供应（调运）基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。，然后次小，直到最后供完为止。B1B2B3B4产量产量A17A24A39销量销量3656311310192741058341633Page118表上作业法表上作业法总的运输费总的运输费(31)+(64)+(43)+(12)+(310)+(35)=86元元元素差额法对最小元素法进行了改进，考虑到产地到销地元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案。运价先调运，否则会增加总运费。例如下面两种运输方案。85102120151515510总运费是总运费是z=108+52+151=105最小元素法：最小元素法：Page119表上作业法表上作业法85102120151551510总运费总运费z=105+152+51=85后一种方案考虑到后一种方案考虑到C11与与C21之间之间的差额是的差额是82=6，如果不先调运，如果不先调运x21，到后来就有可能，到后来就有可能x110，这，这样会使总运费增加较大，从而先样会使总运费增加较大，从而先调运调运x21，再是，再是x22，其次是，其次是x12用元素差额法求得的基本可行解更接近最优解，所用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。以也称为近似方案。Page120表上作业法表上作业法方法方法2：Vogel法法1）从运价表中分别计算出各行和各列的最小运费和次最小运）从运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。费的差额，并填入该表的最右列和最下行。B1B2B3B4产量产量行差额行差额行差额行差额A177 7A241 1A391 1销量销量3656列差额列差额列差额列差额2 25 51 13 3311310192741058Page121表上作业法表上作业法2）再从差值最大的行或列中找出最小运价确定供需关系和）再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量供应完毕或得到满足供需数量。当产地或销地中有一方数量供应完毕或得到满足时，划去运价表中对应的行或列。时，划去运价表中对应的行或列。重复重复1)和和2)，直到找出初始解为至。，直到找出初始解为至。B1B2B3B4产量产量行差额行差额行差额行差额A177 7A241 1A391 1销量销量3656列差额列差额列差额列差额2 25 51 13 33113101927410585 5Page122表上作业法表上作业法单位单位销地销地运价运价产地产地产量产量行差额行差额311310719284741059销量销量3656列差额列差额71135215Page123表上作业法表上作业法单位单位销地销地运价运价产地产地产量产量行差额行差额311310719284741059销量销量3656列差额列差额71352753Page124表上作业法表上作业法单位单位销地销地运价运价产地产地产量产量行差额行差额311310719284741059销量销量3656列差额列差额11351536312该方案的总运费该方案的总运费:(13)(46)(35)(210)(18)(35)85元元Page125表上作业法表上作业法第第第第2 2步步步步 最优解的判别（检验数的求法）最优解的判别（检验数的求法）最优解的判别（检验数的求法）最优解的判别（检验数的求法）求求出出一一组组基基可可行行解解后后，判判断断是是否否为为最最优优解解，仍仍然然是是用用检检验验数数来来判判断断，记记xij的的检检验验数数为为ij由由第第一一章章知知，求求最最小小值值的的运运输问题的最优判别准则是：输问题的最优判别准则是：所有非基变量的检验数都非负，则运输方案最优所有非基变量的检验数都非负，则运输方案最优求检验数的方法有两种：求检验数的方法有两种： 闭回路法闭回路法 位势法（位势法（）Page126表上作业法表上作业法闭回路的概念闭回路的概念为一个闭回路为一个闭回路，集合中的变量称为回路的顶点，相邻两个变，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。如下表量的连线为闭回路的边。如下表Page127表上作业法表上作业法例下表中闭回路的变量集合是例下表中闭回路的变量集合是x11,x12,x42,x43,x23,x25,x35, x31共有共有8个顶点，这个顶点，这8个顶点间用水平或垂直线段连接起来，个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。组成一条封闭的回路。B1B2B3B4B5A1X11X12A2X23X25A3X31X35A4X42X43一条回路中的顶点数一定是偶数，回路遇到顶点必须转一条回路中的顶点数一定是偶数，回路遇到顶点必须转90度与另一顶点连接，表度与另一顶点连接，表33中的变量中的变量x32及及x33不是闭回路的顶不是闭回路的顶点，只是连线的交点。点，只是连线的交点。Page128表上作业法表上作业法闭回路闭回路B1B2B3A1X11X12A2A3X32X33A4X41X43例如变量组例如变量组不能构成一条闭回路，不能构成一条闭回路，但但A中包含有闭回路中包含有闭回路 变量组变量组变量数是奇数，显然不变量数是奇数，显然不是闭回路，也不含有闭回路；是闭回路，也不含有闭回路；Page129表上作业法表上作业法用位势法对初始方案进行最优性检验：用位势法对初始方案进行最优性检验：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（1 1）（2 2）（1 1）（-1-1）（1010）（1212）当存在非基当存在非基变量的检验变量的检验数数 kl0，说，说明现行方案明现行方案为最优方案，为最优方案，否则目标成否则目标成本还可以进本还可以进一步减小。一步减小。Page130表上作业法表上作业法当存在非基变量的检验数当存在非基变量的检验数 kl0且且 kl=min ij时，令时，令Xkl进进基。从表中知可选基。从表中知可选X24进基。进基。第第3步步确定换入基的变量确定换入基的变量第第4步步确定换出基的变量确定换出基的变量以进基变量以进基变量xik为起点的闭回路中，标有负号的最小运量作为为起点的闭回路中，标有负号的最小运量作为调整量调整量，对应的基变量为出基变量，并打上对应的基变量为出基变量，并打上“”以示换以示换出作为非基变量。出作为非基变量。Page131表上作业法表上作业法B1B2B3B4UiA1A2A3Vj3113 31010192 27410105 58 84 4363 31 13 3( () )( () )( () )( () )调整步骤为：调整步骤为：在进基变量的闭回路中标有正号的变量加上调整量在进基变量的闭回路中标有正号的变量加上调整量，标有负号的变量减去调整量，标有负号的变量减去调整量，其余变量不变，得到一组新的，其余变量不变，得到一组新的基可行解。然后求所有非基变量的检验数重新检验。基可行解。然后求所有非基变量的检验数重新检验。1 12 25 5Page132表上作业法表上作业法当所有非基变量的检验数均非负时，则当前调运方案即为最当所有非基变量的检验数均非负时，则当前调运方案即为最优方案，如表此时最小总运费：优方案，如表此时最小总运费：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）Page133表上作业法表上作业法表上作业法的计算步骤：表上作业法的计算步骤：分析实际问题列出产销平分析实际问题列出产销平衡表及单位运价表衡表及单位运价表确定初始调运方案（最小确定初始调运方案（最小元素法或元素法或Vogel法）法）求检验数（位势法）求检验数（位势法）所有检验数所有检验数0找出绝对值最大的负检验数，用闭合找出绝对值最大的负检验数，用闭合回路调整，得到新的调运方案回路调整，得到新的调运方案得到最优方案，得到最优方案，算出总运价算出总运价Page134表上作业法表上作业法表上作业法计算中的问题：表上作业法计算中的问题：表上作业法计算中的问题：表上作业法计算中的问题：（1）若运输问题的某一基可行解有多个非基变量的检验数）若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中任一变量为换入变量均可使为负，在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取目标函数值得到改善，但通常取ij0中最小者对应的变量为中最小者对应的变量为换入变量。换入变量。（2）无穷多最优解）无穷多最优解产销平衡的运输问题必定存最优解。如果非基变量的产销平衡的运输问题必定存最优解。如果非基变量的ij0，则该问题有无穷多最优解。，则该问题有无穷多最优解。Page135表上作业法表上作业法退化解：退化解：表格中一般要有表格中一般要有(m+n-1)个数字格。但有时在分配运量个数字格。但有时在分配运量时则需要同时划去一行和一列，这时需要补一个时则需要同时划去一行和一列，这时需要补一个0，以保证，以保证有有(m+n-1)个数字格作为基变量。一般可在划去的行和列的任个数字格作为基变量。一般可在划去的行和列的任意空格处加一个意空格处加一个0即可。即可。利用进基变量的闭回路对解进行调整时，标有负号的利用进基变量的闭回路对解进行调整时，标有负号的最小运量（超过最小运量（超过2个最小值）作为调整量个最小值）作为调整量，选择任意一个最，选择任意一个最小运量对应的基变量作为出基变量，并打上小运量对应的基变量作为出基变量，并打上“”以示作为以示作为非基变量。非基变量。Page136表上作业法表上作业法销地销地产地产地B1B2B3B4产量产量A116A210A322销量销量81412141241148310295116(0)(2)(9)(2)(1)(12)8 812124 42 28 81414如下例中如下例中11检验数是检验数是0，经过调整，可得到另一个最优解。，经过调整，可得到另一个最优解。Page137表上作业法表上作业法销地销地产地产地B1B2B3B4产量产量A17A24A39销量销量365620114431377821063 34 41 16 6 06 6在在x12、x22、x33、x34中任选一个变量作为基变量，例如选中任选一个变量作为基变量，例如选x34例：用最小元素法求初始可行解例：用最小元素法求初始可行解Page138运输问题的应用运输问题的应用1. 1. 求极大值问题求极大值问题求极大值问题求极大值问题2.目标函数求利润最大或营业额最大等问题。目标函数求利润最大或营业额最大等问题。Page139运输问题的应用运输问题的应用求解方法：求解方法：将极大化问题转化为极小化问题。设极大化问题的运将极大化问题转化为极小化问题。设极大化问题的运价表为价表为C ，用一个较大的数，用一个较大的数M（Mmaxcij）去减每一个）去减每一个cij得到矩阵得到矩阵C，其中，其中C=（Mcij）0,将将C作为极小化问题的作为极小化问题的运价表，用表上用业法求出最优解。运价表，用表上用业法求出最优解。Page140运输问题的应用运输问题的应用例例3.3下下列列矩矩阵阵C是是Ai（I=1，2，3）到到Bj的的吨吨公公里里利利润润,运运输输部门如何安排运输方案使总利润最大部门如何安排运输方案使总利润最大.销地销地产地产地B1B2B3产量产量A12 25 58 89 9A29 910107 71010A36 65 54 41212销量销量8 814149 9Page141运输问题的应用运输问题的应用销地销地产地产地B1B2B3产量产量A12 25 58 89 9A29 910107 71010A36 65 54 41212销量销量8 814149 9得到新的最小化运输问题，用表上作业法求解即可。得到新的最小化运输问题，用表上作业法求解即可。Page142运输问题的应用运输问题的应用2. 2. 产销不平衡的运输问题产销不平衡的运输问题产销不平衡的运输问题产销不平衡的运输问题3.当总产量与总销量不相等时当总产量与总销量不相等时,称为不平衡运输问题称为不平衡运输问题.这这类运输问题在实际中常常碰到类运输问题在实际中常常碰到,它的求解方法是将不平衡问它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。题化为平衡问题再按平衡问题求解。当产大于销时，即：当产大于销时，即：数学模型为：数学模型为：Page143运输问题的应用运输问题的应用由于总产量大于总销量，必有部分产地的产量不能全部运送完，由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，必须就地库存，即每个产地设一个仓库，假设该仓库为一个虚拟假设该仓库为一个虚拟销地销地Bn+1，bn+1作为一个虚设销地作为一个虚设销地Bn+1的销量的销量(即库存量即库存量)。各产地。各产地Ai到到Bn+1的运价为零，即的运价为零，即Ci,n+1=0,（i=1，m）。则平衡问题的）。则平衡问题的数学模型为：数学模型为：具体求解时具体求解时, ,只在只在运价表右端增加运价表右端增加一列一列B Bn n+1+1，运价为，运价为零零, ,销量为销量为b bn n+1+1即即可可Page144运输问题的应用运输问题的应用当销大于产时，即：当销大于产时，即：数学模型为：数学模型为：由于总销量大于总产由于总销量大于总产量量,故一定有些需求故一定有些需求地不完全满足地不完全满足,这时这时虚设一个产地虚设一个产地Am+1，产量为：产量为：Page145运输问题的应用运输问题的应用销大于产化为平衡问题的数学模型为销大于产化为平衡问题的数学模型为：具体计算时，在运价表的下方增加一行具体计算时，在运价表的下方增加一行Am+1，运价为零。产，运价为零。产量为量为am+1即可。即可。Page146运输问题的应用运输问题的应用例例3.4求下列表中极小化运输问题的最优解。求下列表中极小化运输问题的最优解。B1B2B3B4aiA1592360A2-47840A3364230A448101150bj20603545180160因为有：因为有：Page147运输问题的应用运输问题的应用所以是一个产大于销的运输问题。表中所以是一个产大于销的运输问题。表中A2不可达不可达B1，用一个，用一个很大的正数很大的正数M表示运价表示运价C21。虚设一个销量为。虚设一个销量为b5=180-160=20，Ci5=0，i=1,2,3,4，表的右边增添一列，表的右边增添一列，得到新的运价表。，得到新的运价表。B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj2060354520180Page148运输问题的应用运输问题的应用下表为计算结果。可看出：产地下表为计算结果。可看出：产地A4还有还有20个单位没有运出。个单位没有运出。B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180Page149运输问题的应用运输问题的应用3.生产与储存问题生产与储存问题例例3.5某厂按合同规定须于当年每个季度末分别提供某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用每积压一个季度需储存、维护等费用0.15万元。试求在完成合同万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。的情况下，使该厂全年生产总费用为最小的决策方案。季度季度生产能力生产能力/台台单位成本单位成本/万元万元2510.83511.130111011.3Page150运输问题的应用运输问题的应用解：解：设设xij为第为第i季度生产的第季度生产的第j季度交货的柴油机数目，那季度交货的柴油机数目，那么应满足：么应满足：交货：交货：x11=10生产：生产：x11+x12+x13+x1425x12+x22=15x22+x23+x2435 x13+x23+x33=25x33+x3430 x14+x24+x34+x44=20x4410把第把第i季度生产的柴油机数目看作第季度生产的柴油机数目看作第i个生产厂的产量；把第个生产厂的产量；把第j季季度交货的柴油机数目看作第度交货的柴油机数目看作第j个销售点的销量；设个销售点的销量；设cij是第是第i季度生季度生产的第产的第j季度交货的每台柴油机的实际成本，应该等于该季度单位季度交货的每台柴油机的实际成本，应该等于该季度单位成本加上储存、维护等费用。可构造下列产销平衡问题：成本加上储存、维护等费用。可构造下列产销平衡问题：Page151运输问题的应用运输问题的应用ji产量产量10.810.9511.111.2525M11.1011.2511.4035MM11.0011.1530MMM11.3010销量销量1015252010070由于产大于销，加上一个虚拟的销地由于产大于销，加上一个虚拟的销地D，化为平衡问题，化为平衡问题，即可应用表上作业法求解。即可应用表上作业法求解。Page152运输问题的应用运输问题的应用该问题的数学模型：该问题的数学模型：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x44jiD产量产量10.810.9511.111.25025M11.1011.2511.40035MM11.0011.15030MMM11.30010销量销量1015252030100100Page153运输问题的应用运输问题的应用jiD产量产量1015025053035255301010销量销量1015252030100100最优生产决策如下表，最小费用最优生产决策如下表，最小费用z773万元。万元。Chapter4整数规划整数规划(IntegerProgramming)(IntegerProgramming)整数规划的特点及应用整数规划的特点及应用分支定界法分支定界法分配问题与匈牙利法分配问题与匈牙利法本章主要内容：本章主要内容：本章主要内容：本章主要内容：Page155整数规划的特点及应用整数规划的特点及应用整数规划（简称：整数规划（简称：整数规划（简称：整数规划（简称：IPIP）要求一部分或全部决策变量取整数值的规划问题称为要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为整数线性规划。问题是一个线性规划，则称该整数规划为整数线性规划。整数线性规划数学模型的一般形式：整数线性规划数学模型的一般形式：Page156整数规划的特点及应用整数规划的特点及应用整数线性规划问题的种类：整数线性规划问题的种类：整数线性规划问题的种类：整数线性规划问题的种类：纯整数线性规划：指全部决策变量都必须取整数值的整数纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划。线性规划。混合整数线性规划：决策变量中有一部分必须取整数值，混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。另一部分可以不取整数值的整数线性规划。0-1型整数线性规划：决策变量只能取值型整数线性规划：决策变量只能取值0或或1的整数线性的整数线性规划。规划。Page157整数规划的特点及应用整数规划的特点及应用整数规划的典型例子整数规划的典型例子整数规划的典型例子整数规划的典型例子例例4.1工厂工厂A1和和A2生产某种物资。由于该种物资供不应求，故需要生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有再建一家工厂。相应的建厂方案有A3和和A4两个。这种物资的需求地两个。这种物资的需求地有有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费需求地的单位物资运费cij，见下表：，见下表：B1B2B3B4年生产能力年生产能力A12934400A28357600A37612200A44525200年需求量年需求量350400300150工厂工厂A3或或A4开工后，每年的生产费用估计分别为开工后，每年的生产费用估计分别为1200万或万或1500万万元。现要决定应该建设工厂元。现要决定应该建设工厂A3还是还是A4，才能使今后每年的总费用，才能使今后每年的总费用最少。最少。Page158整数规划的特点及应用整数规划的特点及应用解：这是一个物资运输问题，特点是事先不能确定应该建解：这是一个物资运输问题，特点是事先不能确定应该建A3还是还是A4中哪一个，因而不知道新厂投产后的实际生产物资。中哪一个，因而不知道新厂投产后的实际生产物资。为此，引入为此，引入0-1变量：变量：再设再设xij为由为由Ai运往运往Bj的物资数量，单位为千吨；的物资数量，单位为千吨；z表示总费用，表示总费用，单位万元。单位万元。则该规划问题的数学模型可以表示为：则该规划问题的数学模型可以表示为：Page159整数规划的特点及应用整数规划的特点及应用混合整数规划问题混合整数规划问题Page160整数规划的特点及应用整数规划的特点及应用例例4.2现有资金总额为现有资金总额为B。可供选择的投资项目有。可供选择的投资项目有n个，项目个，项目j所需投资额和预期收益分别为所需投资额和预期收益分别为aj和和cj（j1,2,.,n），此外由），此外由于种种原因，有三个附加条件：于种种原因，有三个附加条件：若选择项目若选择项目1，就必须同时选择项目，就必须同时选择项目2。反之不一定。反之不一定项目项目3和和4中至少选择一个；中至少选择一个；项目项目5,6,7中恰好选择中恰好选择2个。个。应该怎样选择投资项目，才能使总预期收益最大。应该怎样选择投资项目，才能使总预期收益最大。Page161整数规划的特点及应用整数规划的特点及应用解：对每个投资项目都有被选择和不被选择两种可能，因此解：对每个投资项目都有被选择和不被选择两种可能，因此分别用分别用0和和1表示，令表示，令xj表示第表示第j个项目的决策选择，记为：个项目的决策选择，记为：投资问题可以表示为：投资问题可以表示为：Page162整数规划的特点及应用整数规划的特点及应用例例4.3 4.3 指派问题或分配问题。人事部门欲安排四人到四个不指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。绩（百分制）如表所示，如何安排他们的工作使总成绩最好。工作工作人员人员ABCD甲甲85927390乙乙95877895丙丙82837990丁丁86908088Page163整数规划的特点及应用整数规划的特点及应用设设 数学模型如下：数学模型如下：要求每人做一项工作，约束条件为：要求每人做一项工作，约束条件为：Page164整数规划的特点及应用整数规划的特点及应用每项工作只能安排一人，约束条件为：每项工作只能安排一人，约束条件为：变量约束：变量约束：Page165整数规划的特点及应用整数规划的特点及应用整数规划问题解的特征：整数规划问题解的特征：整数规划问题解的特征：整数规划问题解的特征：整数规划问题的可行解集合是它松弛问题可行解集合的一整数规划问题的可行解集合是它松弛问题可行解集合的一个子集，任意两个可行解的凸组合不一定满足整数约束条件，个子集，任意两个可行解的凸组合不一定满足整数约束条件，因而不一定仍为可行解。因而不一定仍为可行解。整数规划问题的可行解一定是它的松弛问题的可行解（反整数规划问题的可行解一定是它的松弛问题的可行解（反之不一定），但其最优解的目标函数值不会优于后者最优解之不一定），但其最优解的目标函数值不会优于后者最优解的目标函数值。的目标函数值。Page166整数规划的特点及应用整数规划的特点及应用例例4.3设整数规划问题如下设整数规划问题如下首先不考虑整数约束，得到线性规划问题（一般称为松弛问首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。题）。Page167整数规划的特点及应用整数规划的特点及应用用图解法求出最优解为：用图解法求出最优解为：x13/2,x2=10/3，且有且有Z=29/6现求整数解现求整数解(最优解最优解):如用舍如用舍入取整法可得到入取整法可得到4个点即个点即(1，3),(2，3),(1，4),(2，4)。显然，它。显然，它们都不可能是整数规划的最优解。们都不可能是整数规划的最优解。x1x233(3/2,10/3)按整数规划约束条件，其可行按整数规划约束条件，其可行解肯定在线性规划问题的可行域解肯定在线性规划问题的可行域内且为整数点。故整数规划问题内且为整数点。故整数规划问题的可行解集是一个有限集，如右的可行解集是一个有限集，如右图所示。图所示。其中其中(2,2),(3,1)点点的目标函数值最大，即为的目标函数值最大，即为Z=4。Page168整数规划的特点及应用整数规划的特点及应用整数规划问题的求解方法：整数规划问题的求解方法：分支定界法和割平面法分支定界法和割平面法匈牙利法（指派问题）匈牙利法（指派问题）Page169分支定界法分支定界法1）求整数规划的松弛问题最优解；）求整数规划的松弛问题最优解；若松弛问题的最优解满足整数要求，得到整数规划的最优解若松弛问题的最优解满足整数要求，得到整数规划的最优解,否否则转下一步；则转下一步；2）分支与定界：）分支与定界：任意选一个非整数解的变量任意选一个非整数解的变量xi，在松弛问题中加上约束：，在松弛问题中加上约束：xixi和和xixi+1组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界。标值是分枝问题的下界。检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数解并且目标值大于算，若还存在非整数解并且目标值大于(max)整数解的目标值，需要继续整数解的目标值，需要继续分枝，再检查，直到得到最优解。分枝，再检查，直到得到最优解。分支定界法的解题步骤：分支定界法的解题步骤：分支定界法的解题步骤：分支定界法的解题步骤：Page170分支定界法分支定界法例例4.4用分枝定界法求解整数规划问题用分枝定界法求解整数规划问题解：首先去掉整数约束，变成一般线性规划问题解：首先去掉整数约束，变成一般线性规划问题( (原整数规原整数规划问题的松驰问题划问题的松驰问题) )LPIPPage171分支定界法分支定界法用图解法求松弛问题的最优解，如图所示。用图解法求松弛问题的最优解，如图所示。x1x23(18/11,40/11)21123x118/11,x2=40/11Z=218/11(19.8)即即Z也是也是IP最小值的下限。最小值的下限。对于对于x118/111.64，取值取值x11，x12对于对于x2=40/113.64，取值，取值x23，x24先将（先将（LP）划分为（）划分为（LP1）和（和（LP2）,取取x11,x12Page172分支定界法分支定界法分支：分支：分别求出（分别求出（LP1）和（）和（LP2）的最优解。）的最优解。Page173分支定界法分支定界法先求先求LP1,如图所示。此时在如图所示。此时在B点取得最优解。点取得最优解。x11,x2=3,Z(1)16找到整数解，问题已探明，此找到整数解，问题已探明，此枝停止计算。枝停止计算。x1x233(18/11,40/11)11BAC同理求同理求LP2,如图所示。在如图所示。在C点点取得最优解。即取得最优解。即:x12,x2=10/3,Z(2)56/318.7Z(2)Z(1)16原问题有比原问题有比16更小的最优更小的最优解，但解，但x2 不是整数，故继续不是整数，故继续分支。分支。Page174分支定界法分支定界法在在IP2中分别再加入条件：中分别再加入条件：x23,x24得下式两支：得下式两支：分别求出分别求出LP21和和LP22的最优解的最优解Page175分支定界法分支定界法x1x233(18/11,40/11)11BACD先求先求LP21,如图所示。此时如图所示。此时D在点取得最优解。在点取得最优解。即即x112/52.4,x2=3,Z(21)-87/5-17.4Z(211)如对如对LP212继续分解，其最小值继续分解，其最小值也不会低于也不会低于15.5，问题探明，问题探明,剪枝。剪枝。Page178分支定界法分支定界法原整数规划问题的最原整数规划问题的最优解为优解为: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无可无可行解行解LP211x1=2,x2=3Z(211)17LP212x1=3,x2=5/2Z(212)15.5x11x12x23x24x12x13Page179分支定界法分支定界法例例4.5用分枝定界法求解用分枝定界法求解解解:先求对应的松弛问题（记为先求对应的松弛问题（记为LP0）用图解法得到最优解用图解法得到最优解X(3.57,7.14),Z0=35.7,如下图所如下图所示。示。Page180分支定界法分支定界法1010松弛问题松弛问题LP0的最优解的最优解X=(3.57,7.14),Z0=35.7x1x2oABCPage181分支定界法分支定界法10x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.5Page182分支定界法分支定界法10x1x2oABCLP1LP2134LP21:X=(4.33,6),Z21=35.336Page183分支定界法分支定界法10x1x2oACLP1346LP211:X=(4,6),Z211=34LP212:X=(5,5),Z212=355LP212Page184分支定界法分支定界法上述分枝过程可用下图表示：上述分枝过程可用下图表示：上述分枝过程可用下图表示：上述分枝过程可用下图表示：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无可行解无可行解x27Page185小结小结学习要点：学习要点： 掌握一般整数规划问题概念及模型结构掌握一般整数规划问题概念及模型结构 掌握分支定界法原理掌握分支定界法原理 能够用分支定界法求解一般整数规划问题能够用分支定界法求解一般整数规划问题课后练习：课后练习：Page186分配问题与匈牙利法分配问题与匈牙利法指派问题的数学模型的标准形式：指派问题的数学模型的标准形式：指派问题的数学模型的标准形式：指派问题的数学模型的标准形式：设设n个人被分配去做个人被分配去做n件工作，规定每个人只做一件工作，件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第每件工作只有一个人去做。已知第i个人去做第个人去做第j件工作的效率件工作的效率（时间或费用）为时间或费用）为Cij(i=1.2n;j=1.2n)并假设并假设Cij0。问。问应如何分配才能使总效率（应如何分配才能使总效率（时间或费用）最高？时间或费用）最高？设决策变量设决策变量Page187分配问题与匈牙利法分配问题与匈牙利法指派问题的数学模型为：指派问题的数学模型为：Page188分配问题与匈牙利法分配问题与匈牙利法克尼格定理克尼格定理克尼格定理克尼格定理 : :如果从分配问题效率矩阵如果从分配问题效率矩阵aij的每一行元素中分别减的每一行元素中分别减去去(或加上或加上)一个常数一个常数ui，从每一列中分别减去，从每一列中分别减去(或加上或加上)一个一个常数常数vj，得到一个新的效率矩阵，得到一个新的效率矩阵bij，则以，则以bij为效率矩阵为效率矩阵的分配问题与以的分配问题与以aij为效率矩阵的分配问题具有相同的最优为效率矩阵的分配问题具有相同的最优解。解。Page189分配问题与匈牙利法分配问题与匈牙利法指派问题的求解步骤：指派问题的求解步骤：指派问题的求解步骤：指派问题的求解步骤：1)变变换换指指派派问问题题的的系系数数矩矩阵阵(cij)为为(bij)，使使在在(bij)的的各各行行各各列中都出现列中都出现0元素，即元素，即从从(cij)的每行元素都减去该行的最小元素；的每行元素都减去该行的最小元素；再从所得新系数矩阵的每列元素中减去该列的最小元素。再从所得新系数矩阵的每列元素中减去该列的最小元素。2)进行试指派，以寻求最优解。进行试指派，以寻求最优解。在在(bij)中中找找尽尽可可能能多多的的独独立立0元元素素，若若能能找找出出n个个独独立立0元元素素，就就以以这这n个个独独立立0元元素素对对应应解解矩矩阵阵(xij)中中的的元元素素为为1，其其余余为为0，这就得到最优解。，这就得到最优解。Page190分配问题与匈牙利法分配问题与匈牙利法找独立找独立0元素，常用的步骤为：元素，常用的步骤为：从只有一个从只有一个0元素的行开始，给该行中的元素的行开始，给该行中的0元素加圈，记作元素加圈，记作。然后划去。然后划去所在列的其它所在列的其它0元素，记作元素，记作；这表示该列所代表；这表示该列所代表的任务已指派完，不必再考虑别人了。依次进行到最后一行。的任务已指派完，不必再考虑别人了。依次进行到最后一行。从只有一个从只有一个0元素的列开始（画元素的列开始（画的不计在内），给该列中的的不计在内），给该列中的0元素加圈，记作元素加圈，记作；然后划去；然后划去所在行的所在行的0元素，记作元素，记作，表示，表示此人已有任务，不再为其指派其他任务了。依次进行到最后一列。此人已有任务，不再为其指派其他任务了。依次进行到最后一列。若仍有没有划圈的若仍有没有划圈的0元素，且同行元素，且同行(列列)的的0元素至少有两个，比元素至少有两个，比较这行各较这行各0元素所在列中元素所在列中0元素的数目，选择元素的数目，选择0元素少这个元素少这个0元素加元素加圈圈(表示选择性多的要表示选择性多的要“礼让礼让”选择性少的选择性少的)。然后划掉同行同列。然后划掉同行同列的其它的其它0元素。可反复进行，直到所有元素。可反复进行，直到所有0元素都已圈出和划掉为止。元素都已圈出和划掉为止。Page191分配问题与匈牙利法分配问题与匈牙利法若若元素的数目元素的数目m 等于矩阵的阶数等于矩阵的阶数n（即：（即：mn），那么这指，那么这指派问题的最优解已得到。若派问题的最优解已得到。若m n,则转入下一步。则转入下一步。3)用最少的直线通过所有用最少的直线通过所有0元素。其方法：元素。其方法：对没有对没有的行打的行打“”；对已打对已打“”的行中所有含的行中所有含元素的列打元素的列打“”；再对打有再对打有“”的列中含的列中含元素的行打元素的行打“”；重复重复、直到得不出新的打直到得不出新的打号的行、列为止；号的行、列为止；对没有打对没有打号的行画横线，有打号的行画横线，有打号的列画纵线，这就得到覆盖号的列画纵线，这就得到覆盖所有所有0元素的最少直线数元素的最少直线数l。注注：l应应等等于于m，若若不不相相等等，说说明明试试指指派派过过程程有有误误，回回到到第第2步步，另另行行试试指指派派；若若lmn，表表示示还还不不能能确确定定最最优优指指派派方方案案，须须再再变变换换当当前前的的系系数矩阵，以找到数矩阵，以找到n个独立的个独立的0元素，为此转第元素，为此转第4步。步。Page192分配问题与匈牙利法分配问题与匈牙利法4)变换矩阵变换矩阵(bij)以增加以增加0元素元素在没有被直线通过的所有元素中找出最小值，没有被直线在没有被直线通过的所有元素中找出最小值，没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个通过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。新系数矩阵的最优解和原问题仍相同。转回第最小值。新系数矩阵的最优解和原问题仍相同。转回第2步。步。Page193分配问题与匈牙利法分配问题与匈牙利法例例4.6有一份中文说明书，需译成英、日、德、俄四种文字，有一份中文说明书，需译成英、日、德、俄四种文字，分别记作分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？如何分派任务，可使总时间最少？任务任务人员人员ABCD甲甲67112乙乙4598丙丙31104丁丁5982Page194分配问题与匈牙利法分配问题与匈牙利法解：解：1）变换系数矩阵，增加变换系数矩阵，增加0元素。元素。52）试指派（找独立）试指派（找独立0元素）元素） 找到找到3个独立零元素个独立零元素但但m=3n=4Page195分配问题与匈牙利法分配问题与匈牙利法3）作最少的直线覆盖所有作最少的直线覆盖所有0元素元素 独立零元素的个数独立零元素的个数m等于最少等于最少直线数直线数l，即，即lm=3n=4；4）没有被直线通过的元素中选择最小值为）没有被直线通过的元素中选择最小值为1，变换系数矩，变换系数矩阵，将没有被直线通过的所有元素减去这个最小元素；直阵，将没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。得到新的矩阵，重复线交点处的元素加上这个最小值。得到新的矩阵，重复2）步进行试指派步进行试指派Page196分配问题与匈牙利法分配问题与匈牙利法000000试指派试指派 得到得到4个独立零元素，个独立零元素，所以最优解矩阵为：所以最优解矩阵为：即完成即完成4个任务的总时间最少个任务的总时间最少为：为：241+8=15Page197分配问题与匈牙利法分配问题与匈牙利法例例4.7已知四人分别完成四项工作所需时间如下表，求最优已知四人分别完成四项工作所需时间如下表，求最优分配方案。分配方案。任务任务人员人员ABCD甲甲215134乙乙1041415丙丙9141613丁丁78119Page198分配问题与匈牙利法分配问题与匈牙利法解：解：1）变换系数矩阵，增加变换系数矩阵，增加0元素。元素。 2）试指派（找独立）试指派（找独立0元素）元素）独立独立0元素的个数为元素的个数为4,指派问题的最优指指派问题的最优指派方案即为甲负责派方案即为甲负责D工作，乙负责工作，乙负责B工作，工作，丙负责丙负责A工作，丁负责工作，丁负责C工作。这样安排工作。这样安排能使总的工作时间最少，为能使总的工作时间最少，为4491128。Page199分配问题与匈牙利法分配问题与匈牙利法例例4.8已知五人分别完成五项工作耗费如下表，求最优分配已知五人分别完成五项工作耗费如下表，求最优分配方案。方案。任务任务人员人员ABCDE甲甲759811乙乙9127119丙丙85468丁丁73696戊戊467511Page200分配问题与匈牙利法分配问题与匈牙利法-1 -2解：解：1）变换系数矩阵，增加）变换系数矩阵，增加0元素。元素。Page201分配问题与匈牙利法分配问题与匈牙利法 2）试指派（找独立）试指派（找独立0元素）元素）独立独立0元素的个数元素的个数l45，故画直线调整矩阵。，故画直线调整矩阵。Page202分配问题与匈牙利法分配问题与匈牙利法 选择直线外的最小元素选择直线外的最小元素为为1；直线外元素减；直线外元素减1，直线交点元素加直线交点元素加1，其，其他保持不变。他保持不变。Page203分配问题与匈牙利法分配问题与匈牙利法 l =m=40,d-=0;当实际值未达到目标值时：当实际值未达到目标值时：d+=0,d-0;当实际值同目标值恰好一致时：当实际值同目标值恰好一致时：d+=0,d-=0;故恒有故恒有d+d-=0Page224目标规划问题及其数学模型目标规划问题及其数学模型2.统一处理目标和约束。统一处理目标和约束。对有严格限制的资源使用建立系统约束，数学形式同线性规划对有严格限制的资源使用建立系统约束，数学形式同线性规划中的约束条件。如中的约束条件。如C和和D设备的使用限制。设备的使用限制。对不严格限制的约束，连同原线性规划建模时的目标，均通过对不严格限制的约束，连同原线性规划建模时的目标，均通过目标约束来表达。目标约束来表达。1）例如要求甲、乙两种产品保持）例如要求甲、乙两种产品保持1:1的比例，系统约束表达为：的比例，系统约束表达为：x1=x2。由于这个比例允许有偏差，。由于这个比例允许有偏差，当当x1x2时，出现正偏差时，出现正偏差d+，即：，即：x1-d+=x2或或x1x2-d+=0Page225目标规划问题及其数学模型目标规划问题及其数学模型正负偏差不可能同时出现，故总有：正负偏差不可能同时出现，故总有：x1x2+d-d+=0若希望甲的产量不低于乙的产量，即不希望若希望甲的产量不低于乙的产量，即不希望d-0,用目标约束可用目标约束可表为表为:若希望甲的产量低于乙的产量，即不希望若希望甲的产量低于乙的产量，即不希望d0,用目标约束可用目标约束可表为表为:若希望甲的产量恰好等于乙的产量，即不希望若希望甲的产量恰好等于乙的产量，即不希望d0,也不希望也不希望d-0用目标约束可表为用目标约束可表为:Page226目标规划问题及其数学模型目标规划问题及其数学模型3）设备）设备B必要时可加班及加班时间要控制，目标约束表示为：必要时可加班及加班时间要控制，目标约束表示为：2）力求使利润指标不低于）力求使利润指标不低于12元，目标约束表示为：元，目标约束表示为：4）设备）设备A既要求充分利用，又尽可能不加班，目标约束表示为：既要求充分利用，又尽可能不加班，目标约束表示为：Page227目标规划问题及其数学模型目标规划问题及其数学模型3.目标的优先级与权系数目标的优先级与权系数在一个目标规划的模型中，为达到某一目标可牺牲其他一些在一个目标规划的模型中，为达到某一目标可牺牲其他一些目标，称这些目标是属于不同层次的优先级。优先级层次的高低目标，称这些目标是属于不同层次的优先级。优先级层次的高低可分别通过优先因子可分别通过优先因子P1,P2,表示。对于同一层次优先级的不同表示。对于同一层次优先级的不同目标，按其重要程度可分别乘上不同的权系数。权系数是一个个目标，按其重要程度可分别乘上不同的权系数。权系数是一个个具体数字，乘上的权系数越大，表明该目标越重要。具体数字，乘上的权系数越大，表明该目标越重要。现假定：现假定：第第1优先级优先级P1企业利润；企业利润；第第2优先级优先级P2甲乙产品的产量保持甲乙产品的产量保持1:1的比例的比例第第3优先级优先级P3设备设备A,B尽量不超负荷工作。其中设备尽量不超负荷工作。其中设备A的重要性的重要性比设备比设备B大三倍。大三倍。Page228目标规划问题及其数学模型目标规划问题及其数学模型上述目标规划模型可以表示为：上述目标规划模型可以表示为：Page229目标规划问题及其数学模型目标规划问题及其数学模型目标规划数学模型的一般形式目标规划数学模型的一般形式达成函数达成函数目标约束目标约束其中：其中：g gk k为第为第k k个目标约束的预期目标值，个目标约束的预期目标值， 和和 为为p pl l 优先因子对应各目标的权系数。优先因子对应各目标的权系数。Page230目标规划问题及其数学模型目标规划问题及其数学模型用目标规划求解问题的过程：用目标规划求解问题的过程：用目标规划求解问题的过程：用目标规划求解问题的过程：明确问题，列出明确问题，列出目标的优先级和目标的优先级和权系数权系数构造目标规构造目标规划模型划模型求出满意解求出满意解满意否？满意否？分析各项目标分析各项目标完成情况完成情况据此制定出决策方案据此制定出决策方案NYPage231目标规划的图解分析法目标规划的图解分析法目标规划的图解法：目标规划的图解法：目标规划的图解法：目标规划的图解法：适用两个变量的目标规划问题，但其操作简单，适用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于理解一般目标规划原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。的求解原理和过程。图解法解题步骤：图解法解题步骤：图解法解题步骤：图解法解题步骤：1.将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏差变量）的直线方程分别标示于坐标平面上。差变量）的直线方程分别标示于坐标平面上。2.确定系统约束的可行域。确定系统约束的可行域。3.在目标约束所代表的边界线上，用箭头标出正、负偏差变量值在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向增大的方向Page232目标规划的图解分析法目标规划的图解分析法3.求满足最高优先等级目标的解求满足最高优先等级目标的解4.转到下一个优先等级的目标，再不破坏所有较高优先等级目标转到下一个优先等级的目标，再不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解的前提下，求出该优先等级目标的解5.重复重复4，直到所有优先等级的目标都已审查完毕为止，直到所有优先等级的目标都已审查完毕为止6.确定最优解和满意解。确定最优解和满意解。Page233目标规划的图解分析法目标规划的图解分析法例例5.2用图解法求解下列目标规划问题用图解法求解下列目标规划问题Page234目标规划的图解分析法目标规划的图解分析法(a)(b)(c)(d )x2x1(e)(f)d1-d1+d2+d2-d3-d3+d4-d4+满意解满意解(3,3)046834622Page235目标规划的图解分析法目标规划的图解分析法x1x2(a)(b)d1+d1-(c)d2-d2+(d)d3-d3+GD满意解是线段满意解是线段GD上任意点上任意点其中其中G点点X(2,4),D点点X(10/3,10/3)05.51055.6112,410/3,10/35107例例5.3Page236目标规划的图解分析法目标规划的图解分析法Ox1x22040605020406050abd1-d1+d2-d2+cdd3-d3+d4-d4+(24,26)满意解满意解X=(24，26)例例5.4Page237目标规划应用举例目标规划应用举例例例5.5已知一个生产计划的线性规划模型如下，其中目标函已知一个生产计划的线性规划模型如下，其中目标函数为总利润，数为总利润，x1,x2为产品为产品A、B产量。产量。现有下列目标：现有下列目标：1.要求总利润必须超过要求总利润必须超过2500元；元；2.考虑产品受市场影响，为避免积压，考虑产品受市场影响，为避免积压，A、B的生产量不超过生产量不超过60件件和和100件；件；3.由于甲资源供应比较紧张，不要超过现有量由于甲资源供应比较紧张，不要超过现有量140。试建立目标规划模型，并用图解法求解。试建立目标规划模型，并用图解法求解。Page238目标规划应用举例目标规划应用举例解：以产品解：以产品A,B的单件利润比的单件利润比2.5:1为权系数，模型如下：为权系数，模型如下：Page239目标规划应用举例目标规划应用举例0x20x11401201008060402020406080100ABCDC(60,58.3)为所求的满意解。为所求的满意解。(24,26)Chapter6图与网络分析图与网络分析(GraphTheoryandNetworkAnalysis)(GraphTheoryandNetworkAnalysis)图的基本概念与模型图的基本概念与模型树与图的最小树树与图的最小树最短路问题最短路问题网络的最大流网络的最大流本章主要内容：本章主要内容：本章主要内容：本章主要内容：Page241图的基本概念与模型图的基本概念与模型长长江江汉汉江江武昌武昌武昌武昌汉口汉口汉口汉口汉阳汉阳汉阳汉阳您能从武汉理工大学出发走过您能从武汉理工大学出发走过每座桥且只走一次然后回到学每座桥且只走一次然后回到学校吗校吗?Page242近代图论的历史可追溯到近代图论的历史可追溯到18世纪的七桥问题世纪的七桥问题穿过穿过Knigsberg城的七座桥，要求每座桥通过一次且仅通过一次。城的七座桥，要求每座桥通过一次且仅通过一次。这就是著名的这就是著名的“哥尼斯堡哥尼斯堡7桥桥”难题。难题。Euler1736年证明了不年证明了不可能存在这样的路线。可能存在这样的路线。图的基本概念与模型图的基本概念与模型KnigsbergKnigsberg桥对应的图桥对应的图Page243图的基本概念与模型图的基本概念与模型图论中图是由点和边构成，可以反映一些对象之间的关系。图论中图是由点和边构成，可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。曲直，对于反映对象之间的关系并不是重要的。图的定义：图的定义：图的定义：图的定义：若用点表示研究的对象，用边表示这些对象之间的联系，若用点表示研究的对象，用边表示这些对象之间的联系，则图则图G可以定义为点和边的集合，记作：可以定义为点和边的集合，记作：其中其中:V点集点集E边集边集图图G区别于几何学中的图。这里只关心图中有多少个点以区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。及哪些点之间有连线。Page244图的基本概念与模型图的基本概念与模型(v1)赵赵(v2)钱钱孙孙(v3) 李李(v4)周周(v5)吴吴(v6)陈陈(v7)e2e1e3e4e5(v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。可见图论中的图与几何图、工程图是不一样的。例如：在一个人群中，对相互认识这个关系我们可以用图来例如：在一个人群中，对相互认识这个关系我们可以用图来表示。表示。Page245图的基本概念与模型图的基本概念与模型定义定义:图中的点用图中的点用v表示，边用表示，边用e表示。对每条边可用它所连表示。对每条边可用它所连接的点表示，记作：接的点表示，记作：e1=v1,v1;e2=v1,v2;v3e7e4e8e5e6e1e2e3v1v2v4v5端点端点,关联边关联边,相邻相邻若有边若有边e可表示为可表示为e=vi,vj，称，称vi和和vj是边是边e的的端点端点，反之称边，反之称边e为点为点vi或或vj的的关联边关联边。若点。若点vi、vj与同一条边关与同一条边关联，称点联，称点vi和和vj相邻；若边相邻；若边ei和和ej具具有公共的端点，称边有公共的端点，称边ei和和ej相邻相邻。Page246图的基本概念与模型图的基本概念与模型环环,多重边多重边,简单图简单图如果边如果边e的两个端点相重，称该边为的两个端点相重，称该边为环环。如右图中边。如右图中边e1为环。如果两个点为环。如果两个点之间多于一条，称为之间多于一条，称为多重边多重边，如右图，如右图中的中的e4和和e5，对无环、无多重边的图，对无环、无多重边的图称作称作简单图简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5Page247图的基本概念与模型图的基本概念与模型次，奇点，偶点，孤立点次，奇点，偶点，孤立点与某一个点与某一个点vi相关联的边的数目称为相关联的边的数目称为点点vi的的次次（也叫做度），记作（也叫做度），记作d(vi)。右图中右图中d(v1),d(v3)=5,d(v5)=1。次为奇数的点称作次为奇数的点称作奇点奇点，次为偶数，次为偶数的点称作的点称作偶点偶点，次为，次为1的点称为的点称为悬挂悬挂点点，次为，次为0的点称作的点称作孤立点孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次图的次:一个图的次等于各点的次之和。一个图的次等于各点的次之和。Page248图的基本概念与模型图的基本概念与模型链，圈，连通图链，圈，连通图图中某些点和边的交替序列，若其图中某些点和边的交替序列，若其中各边互不相同，且对任意中各边互不相同，且对任意vi,t-1和和vit均相邻称为均相邻称为链链。用。用表示：表示：v3e7e4e8e5e6e1e2e3v1v2v4v5起点与终点重合的链称作起点与终点重合的链称作圈圈。如。如果每一对顶点之间至少存在一条果每一对顶点之间至少存在一条链，称这样的图为链，称这样的图为连通图连通图，否则，否则称图不连通。称图不连通。Page249图的基本概念与模型图的基本概念与模型二部图（偶图）二部图（偶图）图图G=(V,E)的点集的点集V可以分为两各非空子集可以分为两各非空子集X，Y，集，集XY=V,XY=,使得同一集合中任意两个顶点均不使得同一集合中任意两个顶点均不相邻，称这样的图为偶图。相邻，称这样的图为偶图。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为二部图，明显为二部图，(b)也是二部图，但不明显，改画为也是二部图，但不明显，改画为(c)时可以清楚看出。时可以清楚看出。Page250图的基本概念与模型图的基本概念与模型子图，部分图子图，部分图(支撑子图支撑子图)图图G1=V1、E1和图和图G2=V2，E2如果有如果有称称G1是是G2的一个的一个子图子图。若有若有，则称，则称G1是是G2的的一个一个部分图部分图(支撑子图支撑子图)。v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（G图）图）Page251图的基本概念与模型图的基本概念与模型网络（赋权图）网络（赋权图）设图设图G（V，E），对），对G的每一条边的每一条边(vi,vj)相应赋予数量指标相应赋予数量指标wij，wij称为边称为边(vi,vj)的的权权,赋予权的图赋予权的图G称为网络称为网络(或或赋权图）赋权图）。权可以代表距离、费用、通过能力权可以代表距离、费用、通过能力(容量容量)等等。等等。端点无序的赋权图称为端点无序的赋权图称为无向网络无向网络，端点有序的赋权图称为，端点有序的赋权图称为有有向网络。向网络。910201571419256Page252图的基本概念与模型图的基本概念与模型出次与入次出次与入次有有向向图图中中，以以vi为为始始点点的的边边数数称称为为点点vi的的出出次次，用用d+(vi)表表示示；以以vi为为终终点点的的边边数数称称为为点点vi 的的入入次次，用用表表示示d-(vi)；vi 点点的出次和入次之和就是该点的次。的出次和入次之和就是该点的次。有向图中，所有顶点的入次之和等于所有顶点的出次之有向图中，所有顶点的入次之和等于所有顶点的出次之和。和。Page253图的基本概念与模型图的基本概念与模型图的模型应用图的模型应用图的模型应用图的模型应用例例6.1有甲有甲,乙乙,丙丙,丁丁,戊戊,己己6名运动员报名参加名运动员报名参加A,B,C,D,E,F6个项目的比赛。下表中打个项目的比赛。下表中打的是各运动员报告参加的比赛项的是各运动员报告参加的比赛项目。问目。问6个项目的比赛顺序应如何安排，做到每名运动员都个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。不连续地参加两项比赛。ABCDEF甲甲乙乙丙丙丁丁戊戊己己Page254图的基本概念与模型图的基本概念与模型解：用图来建模。把比赛项目作为研究对象，用点表示。如解：用图来建模。把比赛项目作为研究对象，用点表示。如果果2个项目有同一名运动员参加，在代表这两个项目的点之个项目有同一名运动员参加，在代表这两个项目的点之间连一条线，可得下图。间连一条线，可得下图。ABCDEF在图中找到一个点序在图中找到一个点序列，使得依次排列的列，使得依次排列的两点不相邻，即能满两点不相邻，即能满足要求。如：足要求。如：1)A,C,B,F,E,D2)D,E,F,B,C,APage255图的基本概念与模型图的基本概念与模型一一个个班班级级的的学学生生共共计计选选修修A、B、C、D、E、F六六门门课课程程，其其中中一一部部分分人人同同时时选选修修D、C、A，一一部部分分人人同同时时选选修修B、C、F，一一部部分分人人同同时时选选修修B、E，还还有有一一部部分分人人同同时时选选修修A、B，期期终终考考试试要要求求每每天天考考一一门门课课，六六天天内内考考完完，为为了了减减轻轻学学生生负负担担，要要求求每每人人都都不不会会连连续续参参加加考考试，试设计一个考试日程表。试，试设计一个考试日程表。思考题思考题思考题思考题Page256图的基本概念与模型图的基本概念与模型思考题解答：思考题解答：思考题解答：思考题解答：以每门课程为一个顶点，共同被选修的课程之间用边以每门课程为一个顶点，共同被选修的课程之间用边相连，得图，按题意，相邻顶点对应课程不能连续考试，不相连，得图，按题意，相邻顶点对应课程不能连续考试，不相邻顶点对应课程允许连续考试，因此，作图的补图，问题相邻顶点对应课程允许连续考试，因此，作图的补图，问题是在图中寻找一条哈密顿道路，如是在图中寻找一条哈密顿道路，如CEAFDBCEAFDB，就是一个符合要求的考试课程表。就是一个符合要求的考试课程表。Page257图的基本概念与模型图的基本概念与模型A AF FE ED DC CB BPage258图的基本概念与模型图的基本概念与模型A AF FE ED DC CB BPage259图的基本概念与模型图的基本概念与模型图的基本性质：图的基本性质：图的基本性质：图的基本性质：定理定理1任何图中，顶点次数之和等于所有边数的任何图中，顶点次数之和等于所有边数的2倍。倍。定理定理2任何图中，次为奇数的顶点必为偶数个。任何图中，次为奇数的顶点必为偶数个。证明：由于每条边必与两个顶点关联，在计算点的次时，每条边证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的均被计算了两次，所以顶点次数的总和等于边数的2倍。倍。证明：设证明：设V1和和V2分别为图分别为图G中奇点与偶点的集合。由定理中奇点与偶点的集合。由定理1可得：可得：2m为偶数，且偶点的次之和为偶数，且偶点的次之和也为偶数，所以也为偶数，所以必为偶必为偶数，即奇数点的个数必为偶数。数，即奇数点的个数必为偶数。Page260图的基本概念与模型图的基本概念与模型图的矩阵描述：图的矩阵描述：如何在计算机中存储一个图呢？现在已有很多存储的方法，如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有：也根据所关心的问题不同而有：邻接矩阵、关联矩阵、权矩阵等。邻接矩阵、关联矩阵、权矩阵等。1.邻接矩阵邻接矩阵对于图对于图G=（V，E），），|V|=n，|E|=m，有，有n n阶方阶方矩阵矩阵A=(aij)n n，其中其中Page261图的基本概念与模型图的基本概念与模型v5v1v2v3v4v64332256437例例6.2下图所表示的图可以构造邻接矩阵下图所表示的图可以构造邻接矩阵A如下如下Page262对于赋权图对于赋权图G=(V,E),其中边其中边有权有权,构造矩阵构造矩阵B=(bij)n n其中：其中：图的基本概念与模型图的基本概念与模型2.2.关联矩阵关联矩阵关联矩阵关联矩阵对于图对于图G=(V,E),|V|=n,|E|=m,有有m n阶阶矩阵矩阵M=(mij)m n，其中其中:3.3.权矩阵权矩阵权矩阵权矩阵Page263图的基本概念与模型图的基本概念与模型101000000000110010000000010001110000000000001001001111000000000000001100000000000111000100110000v1v2v3v4v5v6v7v8e1e2e3e4e5e6e7e8e9e10e11e12v1v2v3v5v8v7e1e2e3e4e6e5e7e9e12e10e11e8v6v4例例6.3下图所表示的图可以构造邻接矩阵下图所表示的图可以构造邻接矩阵M如下如下:M=（mij）=Page264图的基本概念与模型图的基本概念与模型v5v1v2v3v4v64332256437例例6.4下图所表示的图可以构造权矩阵下图所表示的图可以构造权矩阵B如下如下:Page265树与图的最小树树与图的最小树树是图论中结构最简单但又十分重要的图。在自然和社会领树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。域应用极为广泛。例例6.2乒乓求单打比赛抽签后，可用图来表示相遇情况，如乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。下图所示。AB CDEF GH运动员运动员Page266树与图的最小树树与图的最小树例例6.3某企业的组织机构图也可用树图表示。某企业的组织机构图也可用树图表示。厂长厂长人事科人事科财务科财务科总工总工程师程师生产副生产副厂长厂长经营副经营副厂长厂长开发科开发科技术科技术科生产科生产科设备科设备科供应科供应科销售科销售科检验科检验科动力科动力科Page267树与图的最小树树与图的最小树树：无圈的连通图即为树树：无圈的连通图即为树性质性质1：任何树中必存在次为：任何树中必存在次为1的点。的点。性质性质2：n个顶点的树必有个顶点的树必有n-1条边。条边。性质性质3：树中任意两个顶点之间，恰有且仅有一条链。：树中任意两个顶点之间，恰有且仅有一条链。性质性质4：树连通，但去掉任一条边，必变为不连通。：树连通，但去掉任一条边，必变为不连通。性质性质5：树无回圈，但不相邻的两个点之间加一条边，恰：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。得到一个圈。v1v2v3v4v5v6Page268树与图的最小树树与图的最小树图的最小部分树图的最小部分树(支撑树支撑树)如果如果G2是是G1的部分图，又是树图，则称的部分图，又是树图，则称G2是是G1的部分树的部分树（或支撑树）。树图的各条边称为树枝，一般图（或支撑树）。树图的各条边称为树枝，一般图G1含有多含有多个部分树，其中树枝总长最小的部分树，称为该图的最小个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。部分树（或最小支撑树）。v1v2v3v4v5v1v2v3v4v5G1G2Page269树与图的最小树树与图的最小树a ab bc cf fe ed dh hg gb bf fe ed dPage270树与图的最小树树与图的最小树a ab bc cf fe ed dh hg gb bf fd dg gPage271树与图的最小树树与图的最小树b bc ce ed da ab bc cf fe ed dh hg gPage272树与图的最小树树与图的最小树a ab bc ch ha ab bc cf fe ed dh hg gPage273树与图的最小树树与图的最小树a af fd dg ga ab bc cf fe ed dh hg gPage274树与图的最小树树与图的最小树求树的方法：破圈法和避圈法求树的方法：破圈法和避圈法求树的方法：破圈法和避圈法求树的方法：破圈法和避圈法破圈法破圈法破圈法破圈法Page275树与图的最小树树与图的最小树部分树部分树Page276树与图的最小树树与图的最小树避圈法避圈法避圈法避圈法v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5Page277树与图的最小树树与图的最小树赋权图中求最小树的方法：破圈法和避圈法赋权图中求最小树的方法：破圈法和避圈法赋权图中求最小树的方法：破圈法和避圈法赋权图中求最小树的方法：破圈法和避圈法破圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边数边数n-1=5Page278树与图的最小树树与图的最小树v1v2v3v4v5v643521得到最小树：得到最小树：MinC(T)=15Page279树与图的最小树树与图的最小树避圈法避圈法:去掉去掉G中所有边，得到中所有边，得到n个孤立点；然后加边。个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能形成加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通圈，直到点点连通(即即:n-1条边条边)。5v1v2v3v4v5v6843752618Page280树与图的最小树树与图的最小树v1v2v3v4v5v6435215v1v2v3v4v5v6843752618MinC(T)=15Page281树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636练习：练习：练习：练习：应用破圈法求最小树应用破圈法求最小树应用破圈法求最小树应用破圈法求最小树Page282树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636Page283树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323Page284树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323Page285树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323Page286树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323Page287树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 9161625253 3282817174 41 12323Page288树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 9161625253 3282817174 41 12323Page289树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323Page290树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323Page291树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323Page292树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323Page293树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 317174 41 12323min=1+4+9+3+17+23=57Page294树与图的最小树树与图的最小树练习：练习：练习：练习：应用避圈法求最小树应用避圈法求最小树应用避圈法求最小树应用避圈法求最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636Page295树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636Page296树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636Page297树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636Page298树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636Page299树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636Page300树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636min=1+4+9+3+17+23=57min=1+4+9+3+17+23=57Page301树与图的最小树树与图的最小树课堂练习：课堂练习：课堂练习：课堂练习：3749346321MinC(T)=12MinC(T)=15254173314475答案：答案：Page302树与图的最小树树与图的最小树34122323242MinC(T)=12213638534567454321MinC(T)=18Page303最短路问题最短路问题如何用最短的线路将三部电话连起来？如何用最短的线路将三部电话连起来？此问题可抽象为设此问题可抽象为设ABC为等边三角形，连接三顶点的为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如然是二边之和（如ABAC）。）。ABCPage304最短路问题最短路问题ABCP但若增加一个周转站（新点但若增加一个周转站（新点P），连接），连接4点的新网络的最短路点的新网络的最短路线为线为PAPBPC。最短新路径之长。最短新路径之长N比原来只连三点的最比原来只连三点的最短路径短路径O要短。这样得到的网络不仅比原来节省材料，而且要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。稳定性也更好。Page305最短路问题最短路问题问题描述：问题描述：就是从给定的网络图中找出一点到各点或任意两点之就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路间距离最短的一条路.有些问题，如选址、管道铺设时的选线、设备更新、有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。短路的问题。因此这类问题在生产实际中得到广泛应用。Page306最短路问题最短路问题例例例例6.46.4渡河游戏渡河游戏渡河游戏渡河游戏一老汉带了一只狼、一只羊、一棵白菜想要从南岸过一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法并且在河上来回次数最少？这个问题就可以用求最短路方法解决。解决。Page307最短路问题最短路问题定义：定义：1）人）人M（Man），狼），狼W（Wolf），），羊羊G（Goat），），草草H（Hay）2）点点vi表示河岸的状态表示河岸的状态3）边边ek表示由状态表示由状态vi经一次渡河到状态经一次渡河到状态vj4）权权边边ek上的权定为上的权定为1我们可以得到下面的加权有向图我们可以得到下面的加权有向图Page308最短路问题最短路问题状态说明：状态说明：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的最短路问题。的最短路问题。v1v2v3v4v5u5u4u3u2u1Page309最短路问题最短路问题求最短路有两种算法求最短路有两种算法:狄克斯屈拉狄克斯屈拉(Dijkstra)标号算法标号算法逐次逼近算法逐次逼近算法Page310最短路问题最短路问题狄克斯屈拉狄克斯屈拉狄克斯屈拉狄克斯屈拉( (DijkstraDijkstra) )标号算法的基本思路：标号算法的基本思路：标号算法的基本思路：标号算法的基本思路：若序列若序列vs,v1.vn-1,vn 是从是从vs到到vt间的最短路，则序列间的最短路，则序列vs,v1.vn-1 必为从必为从vs 到到vn-1的最短路。的最短路。假定假定v1v2v3v4是是v1v4的最短路，则的最短路，则v1v2v3一定是一定是v1v3的最短路，的最短路，v2v3v4也一定是也一定是v2v4的最短路。的最短路。v1v2v3v4v5Page311最短路问题最短路问题求网络图的最短路，设图的起点是求网络图的最短路，设图的起点是vs,终点是终点是vt ,以以vi为起点为起点vj为终点的弧记为为终点的弧记为(i,j) 距离为距离为dijP P标号标号标号标号( (点标号点标号点标号点标号) )：b(j)起点起点vs到点到点vj的最短路长；的最短路长；T 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步。步。Page312最短路问题最短路问题例例6.5求下图求下图v1到到v7的最短路长及最短路线的最短路长及最短路线86252353421057086225441114751071211v7已标号，计算结束。从已标号，计算结束。从v1到到v7的最短路长是的最短路长是11,最短路线：最短路线：v1v4v6v7P标号标号T标号标号Page313最短路问题最短路问题从上例知，只要某点已标号，说明已找到起点从上例知，只要某点已标号，说明已找到起点vs到到该点的最短路线及最短距离，因此可以将每个点标该点的最短路线及最短距离，因此可以将每个点标号，求出号，求出vs到任意点的最短路线，如果某个点到任意点的最短路线，如果某个点vj不能不能标号，说明标号，说明vs不可达不可达vj 。注：无向图最短路的求法只将上述步骤注：无向图最短路的求法只将上述步骤2将弧改成边即可。将弧改成边即可。Page314最短路问题最短路问题例例6.6求下图求下图v1到各点的最短距离及最短路线。到各点的最短距离及最短路线。4526178393261216180452231039612641166188122482418所有点都已标号，点上的标号就是所有点都已标号，点上的标号就是v1到该点的最短距离，最短到该点的最短距离，最短路线就是红色的链。路线就是红色的链。Page315最短路问题最短路问题课堂练习：课堂练习：1.用用Dijkstra算法求下图从算法求下图从v1到到v6的最短距离及路线。的最短距离及路线。v3v54v1v2v4v635222421v1到到v6的最短路为：的最短路为：Page316最短路问题最短路问题2.求从求从v1到到v8的最短路径的最短路径237184566134105275934682Page317最短路问题最短路问题237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到到v8的最短路径为的最短路径为v1v4v7v5v8，最短距离为，最短距离为10Page318最短路问题最短路问题3.求下图中求下图中v1点到另外任意一点的最短路径点到另外任意一点的最短路径v1v2v3v4v6v5322762133Page319最短路问题最短路问题v1V2V3V4V6V5322762133024714Page320最短路问题最短路问题v1V2V3V4V6V5322762133024714Page321最短路问题最短路问题算法适用条件：算法适用条件：Dijkstra算法只适用于全部权为非负情况，如果某算法只适用于全部权为非负情况，如果某边上权为负的，算法失效。此时可采用逐次逼近边上权为负的，算法失效。此时可采用逐次逼近算法。算法。例例6.7如右图所示中按如右图所示中按dijkstra算算法可得法可得P(v1)=5为从为从vsv1的最短的最短路长显然是错误的，从路长显然是错误的，从vsv2v1路长只有路长只有3。v2vsv15-58Page322最短路问题最短路问题最短路问题的应用：最短路问题的应用：例例6.7电信公司准备准备在甲、乙两地沿路架设一条光缆线，电信公司准备准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。通图。权数表示两地间公路的长度（单位：公里）。v1（甲地）甲地）1517624431065v2v7(乙地乙地)v3v4v5v6Page323最短路问题最短路问题解：这是一个求无向图的最短路的问题。解：这是一个求无向图的最短路的问题。Page324最短路问题最短路问题例例6.8设备更新问题。某公司使用一台设备，在每年年初，设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表设备每年年初的价格表年份年份12345年初价格年初价格1111121213Page325最短路问题最短路问题设备维修费如下表设备维修费如下表使用年数使用年数0-11-22-33-44-5每年维修费用每年维修费用5681118解：解：将问题转化为最短路问题，如下图：用将问题转化为最短路问题，如下图：用vi表示表示“第第i年年年年初购进一台新设备初购进一台新设备”,弧（弧（vi,vj）表示第）表示第i年年初购进的设备年年初购进的设备一直使用到第一直使用到第j年年初。年年初。v1v2v3v4v5v6Page326最短路问题最短路问题把所有弧的权数计算如下表，把所有弧的权数计算如下表，把权数赋到图中，再用把权数赋到图中，再用Dijkstra算法求最短路。算法求最短路。123456116223041592162230413172331417235186v1v2v3v4v5v6162230415916223041312317181723Page327最短路问题最短路问题最终得到下图，可知，最终得到下图，可知，v1到到v6的距离是的距离是53，最短路径有两条：，最短路径有两条：v1v3v6和和v1v4v6V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723V2（16,1）16(30,1)(53,3)(53,4)Page328网络的最大流网络的最大流如何制定一个运输计划使生产地到销售地的产品输送量最大。如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。这就是一个网络最大流问题。Page329网络的最大流网络的最大流基本概念：基本概念：1.1.容量网络：容量网络：容量网络：容量网络：队网络上的每条弧队网络上的每条弧(vi,vj)都给出一个最大的都给出一个最大的通过能力，称为该弧的通过能力，称为该弧的容量容量容量容量，简记为，简记为cij。容量网络中通常规。容量网络中通常规定一个定一个发点发点发点发点(也称源点，记为也称源点，记为s)和一个和一个收点收点收点收点(也称汇点，记为也称汇点，记为t)，网络中其他点称为，网络中其他点称为中间点中间点中间点中间点。st4844122679Page330网络的最大流网络的最大流2.网络的最大流网络的最大流是指网络中从发点到收点之间允许通过的最大流量。是指网络中从发点到收点之间允许通过的最大流量。3.流与可行流流与可行流流流是指加在网络各条弧上的实际流量，对加在弧是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上上的负载量记为的负载量记为fij。若。若fij=0，称为零流。，称为零流。满足以下条件的一组流称为满足以下条件的一组流称为可行流可行流。容量限制条件。容量网络上所有的弧满足：容量限制条件。容量网络上所有的弧满足：0fijcij中间点平衡条件。中间点平衡条件。若以若以v(f)表示网络中从表示网络中从st的流量，则有：的流量，则有：Page331网络的最大流网络的最大流结论：任何网络上一定存在可行流。（零流即是结论：任何网络上一定存在可行流。（零流即是可行流）可行流）网络最大流问题：网络最大流问题：指满足容量限制条件和中间点平衡的条件下，使指满足容量限制条件和中间点平衡的条件下，使v(f)值值达到最大。达到最大。Page332网络的最大流网络的最大流割与割集割与割集割是指容量网络中的发点和收点分割开，并使割是指容量网络中的发点和收点分割开，并使st的流中断的流中断的一组弧的集合。割容量是组成割集合中的各条弧的容量之的一组弧的集合。割容量是组成割集合中的各条弧的容量之和，用和，用表示。表示。如下图中，如下图中，AA将网络上的点分割成将网络上的点分割成两个集合。并有两个集合。并有，称弧的集合，称弧的集合(v1,v3),(v2,v4)是一个割，且是一个割，且的流量为的流量为18。Page333网络的最大流网络的最大流stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(3)7(6)AABBPage334网络的最大流网络的最大流定理定理定理定理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 2在网络中在网络中st的最大流量等于它的最小割集的容量，的最大流量等于它的最小割集的容量，即：即：v(f)=c (V,V)Page335网络的最大流网络的最大流增广链增广链增广链增广链在网络的发点和收点之间能找到一条链，在该链上所在网络的发点和收点之间能找到一条链，在该链上所有指向为有指向为st的弧，称为前向弧，记作的弧，称为前向弧，记作+,存在存在f0，则称这样的，则称这样的链为增广链。链为增广链。例如下图中，例如下图中，sv2v1v3v4t。定理定理定理定理3 3网络网络N中的流中的流f是最大流当且仅当是最大流当且仅当N中不包含任何增广中不包含任何增广链链Page336网络的最大流网络的最大流stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(4)7(5)Page337网络的最大流网络的最大流求网络最大流的标号算法：求网络最大流的标号算法： 基本思想基本思想基本思想基本思想由一个流开始，系统地搜寻增广链，然后在此链上增由一个流开始，系统地搜寻增广链，然后在此链上增流，继续这个增流过程，直至不存在增广链。流，继续这个增流过程，直至不存在增广链。 基本方法基本方法基本方法基本方法 (1)找出第一个可行流，（例如所有弧的流量找出第一个可行流，（例如所有弧的流量fij =0。）。）(2)用标号的方法找一条增广链用标号的方法找一条增广链首先给发点首先给发点s标号标号(),标号中的数字表示允许的最大调整标号中的数字表示允许的最大调整量。量。选择一个点选择一个点vi 已标号并且另一端未标号的弧沿着某条链已标号并且另一端未标号的弧沿着某条链向收点检查：向收点检查：Page338网络的最大流网络的最大流如果弧的起点为如果弧的起点为vi，并且有，并且有fij0，则，则vj标号标号(fji)(3)重复第重复第(2)步，可能出现两种结局：步，可能出现两种结局：标号过程中断，标号过程中断，t无法标号，说明网络中不存在增广链，无法标号，说明网络中不存在增广链，目前流量为最大流。同时可以确定最小割集，目前流量为最大流。同时可以确定最小割集，记已标号的点记已标号的点集为集为V,未标号的点集合为未标号的点集合为V,(V,V)为网络的最小割。为网络的最小割。t得到标号，反向追踪在网络中找到一条从得到标号，反向追踪在网络中找到一条从s到到t得由标号得由标号点及相应的弧连接而成的增广链。继续第点及相应的弧连接而成的增广链。继续第(4)步步Page339网络的最大流网络的最大流(4)修改流量。设原图可行流为修改流量。设原图可行流为f，令，令得到网络上一个新的可行流得到网络上一个新的可行流f。(5)擦除图上所有标号，重复擦除图上所有标号，重复(1)-(4)步，直到图中找不到任步，直到图中找不到任何增广链，计算结束。何增广链，计算结束。Page340网络的最大流网络的最大流例例6.10用标号算法求下图中用标号算法求下图中st的最大流量，并找出最小割。的最大流量，并找出最小割。stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)Page341网络的最大流网络的最大流解：解：(1)先给先给s标号标号()stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()Page342网络的最大流网络的最大流stv1v3v2v48(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)Page343网络的最大流网络的最大流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)Page344网络的最大流网络的最大流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)找到一条增广链找到一条增广链sv1v3tPage345网络的最大流网络的最大流(4)修改增广链上的流量，非增广链上的流量不变，得到新修改增广链上的流量，非增广链上的流量不变，得到新的可行流。的可行流。stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(3)7(5)()(1)(1)(1)Page346网络的最大流网络的最大流(5)擦除所有标号，重复上述标号过程，寻找另外的增广链。擦除所有标号，重复上述标号过程，寻找另外的增广链。stv1v3v2v48(8)9(4)5(5)10(8)6(0)2(0)9(9)5(3)7(5)()(1)(1)(1)Page347网络的最大流网络的最大流(5)擦除所有标号，重复上述标号过程，寻找另外的增广链。擦除所有标号，重复上述标号过程，寻找另外的增广链。stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)()(2)(2)=min,2=2(2)(1)=min2,3=2(3)=min2,5=2(2)(1)(4)=min2,1=1(1)(t)=min1,2=1Page348网络的最大流网络的最大流(6)修改增广链上的流量，非增广链上的流量不变，得到新修改增广链上的流量，非增广链上的流量不变，得到新的可行流。的可行流。stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)()(2)(2)(2)(1)(1)Page349网络的最大流网络的最大流stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)()(2)(2)(2)(1)(1)(7)擦除所有标号，重复上述标号过程，寻找另外的增广链。擦除所有标号，重复上述标号过程，寻找另外的增广链。Page350网络的最大流网络的最大流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=1Page351网络的最大流网络的最大流例例6.9求下图求下图st的最大流，并找出最小割的最大流，并找出最小割stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)Page352网络的最大流网络的最大流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 3ttPage353网络的最大流网络的最大流(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)Page354网络的最大流网络的最大流(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)Page355网络的最大流网络的最大流(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 3ttPage356网络的最大流网络的最大流(5)修改增广链上的流量，非增广链上的流量不变，得到新的可修改增广链上的流量，非增广链上的流量不变，得到新的可行流。行流。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)Page357网络的最大流网络的最大流(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)Page358网络的最大流网络的最大流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)(5)=min,1=1(5)=min1,1=1(5)=min1,2=1(7)重新搜寻增广链。重新搜寻增广链。存在增广链：存在增广链：存在增广链：存在增广链：svsv5 5vv3 3ttPage359网络的最大流网络的最大流(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)Page360网络的最大流网络的最大流stv1v2v3v4v54(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)擦除原标号擦除原标号Page361网络的最大流网络的最大流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 4ttPage362网络的最大流网络的最大流stv1v2v3v4v54(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)调整增广链上的流量，非增广链流量不变，得到新的可行流调整增广链上的流量，非增广链流量不变，得到新的可行流Page363网络的最大流网络的最大流stv1v2v3v4v54(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)擦除标号，在新的可行流上重新标号。擦除标号，在新的可行流上重新标号。Page364网络的最大流网络的最大流stv1v2v3v4v54(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。