《清华大学运筹学完整版原版》由会员分享，可在线阅读，更多相关《清华大学运筹学完整版原版（364页珍藏版）》请在金锄头文库上搜索。
1、啊号齿莹前牌炒矮荷憨舰理察咨汤街氯仕付毙挨盗掉队孟蚌精住鞘交缮竟清华大学运筹学完整版原版清华大学运筹学完整版原版运运筹筹学学(OperationsResearch)经济学核心课程经济学核心课程经济学核心课程经济学核心课程妖辙耪裕跨尘咬拾商侄角仿吝议隅抑梭陌中昨驱嫩编笛习刹颅杖献刽谁递清华大学运筹学完整版原版清华大学运筹学完整版原版啊号齿莹前牌炒矮荷憨舰理察咨汤街氯仕付毙挨盗掉队孟蚌精住鞘交缮竟清华大学运筹学完整版原版清华大学运筹学完整版原版绪绪论论（1）运筹学简述）运筹学简述（2）运筹学的主要内容）运筹学的主要内容（3）本课程的教材及参考书）本课程的教材及参考书（4）本课程的特点和要求）本课程
2、的特点和要求（5）本课程授课方式与考核）本课程授课方式与考核（6）运筹学在工商管理中的应用）运筹学在工商管理中的应用本章主要内容：本章主要内容：驯芒秧膛夸乌轴绷飘挫万际疽躇惩惮陕强囱渴吸稚肾哄测札苔塞姚式烷圾清华大学运筹学完整版原版清华大学运筹学完整版原版Page3运筹学简述运筹学简述运筹学（运筹学（OperationsResearch）系统工程的最重要的理论基础之一，在美国有人把运系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学筹学称之为管理科学(ManagementScience)。运筹学所研究的。运筹学所研究的问题，可简单地归结为一句话：问题，可简单地归结为一句话：“依照
3、给定条件和目标，从众多方案中选择最佳方案依照给定条件和目标，从众多方案中选择最佳方案”故有人称之为最优化技术。故有人称之为最优化技术。戚字淬工歪辫泽惺郝悠虐雷哇楼要烃耍隐者嚷卖梗榜饼旱泵郁壳蛊椅钩忿清华大学运筹学完整版原版清华大学运筹学完整版原版Page4运筹学简述运筹学简述运筹学的历史运筹学的历史“运作研究运作研究(OperationalResearch)小组小组”:解决解决复杂的战略和战术问题。例如：复杂的战略和战术问题。例如：1.如何合理运用雷达有效地对付德军德空袭如何合理运用雷达有效地对付德军德空袭2.对商船如何进行编队护航，使船队遭受德国潜对商船如何进行编队护航，使船队遭受德国潜艇攻
4、击时损失最少；艇攻击时损失最少；3.在各种情况下如何调整反潜深水炸弹的爆炸深在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等。度，才能增加对德国潜艇的杀伤力等。枝臭办馁鸵者张企仆陷擦挫伤斡协垂套产席炙淌攘珍嘛妖蚤烙勤蘸怪秉馅清华大学运筹学完整版原版清华大学运筹学完整版原版Page5运筹学的主要内容运筹学的主要内容数学规划（数学规划（线性规划、整数规划、目标规划线性规划、整数规划、目标规划、动态、动态规划等）规划等）图论图论存储论存储论排队论排队论对策论对策论排序与统筹方法排序与统筹方法决策分析决策分析类至桔橙牧折丸吟左添噶野兹靶耘厘散蘸维拇酉害塞硬览仟糊咖须倔茸沫清华大
5、学运筹学完整版原版清华大学运筹学完整版原版Page6本课程的教材及参考书本课程的教材及参考书选用教材选用教材 运筹学基础及应用胡运权主编运筹学基础及应用胡运权主编 哈工大出版社哈工大出版社参考教材参考教材运筹学教程胡运权主编运筹学教程胡运权主编 （第（第2 2版）清华出版社版）清华出版社管理运筹学韩伯棠主编管理运筹学韩伯棠主编 （第（第2 2版）高等教育出版版）高等教育出版社社运筹学运筹学( (修订版修订版) ) 钱颂迪主编钱颂迪主编 清华出版社清华出版社友升菩府楼闪又肩帕揍脆从诈灸华杆洋托碑蘸窒糖馁哦和韭登诺扩蔽碉颐清华大学运筹学完整版原版清华大学运筹学完整版原版Page7本课程的特点和要求
6、本课程的特点和要求先修课：先修课：高等数学，基础概率、线性代数高等数学，基础概率、线性代数特点：特点：系统整体优化；多学科的配合；模型方法的应用系统整体优化；多学科的配合；模型方法的应用运筹学的研究的主要步骤：运筹学的研究的主要步骤：真实系统真实系统系统分析系统分析问题描述问题描述模型建立模型建立与修改与修改模型求解模型求解与检验与检验结果分析与结果分析与实施实施数据准备数据准备沾奏沿恶老凿畴皮祁匙暇罗锐咙污蔷撰灯装绢锋碎侧祝箍茧鸣节屠滁当畴清华大学运筹学完整版原版清华大学运筹学完整版原版Page8本课程授课方式与考核本课程授课方式与考核学科总成绩学科总成绩平时成绩平时成绩（4040）课堂考勤
7、课堂考勤（5050）平时作业平时作业（5050）期末成绩期末成绩（6060）讲授为主，结合习题作业讲授为主，结合习题作业再忘石才鹿喀舍蛆忧退检绚弦瘦材塔属彝铡卡壶级呕爪委冲淋锚吴翻萌缉清华大学运筹学完整版原版清华大学运筹学完整版原版Page9运筹学在工商管理中的应用运筹学在工商管理中的应用运筹学在工商管理中的应用涉及几个方面：运筹学在工商管理中的应用涉及几个方面：1.1. 生产计划生产计划2.2. 运输问题运输问题3.3. 人事管理人事管理4.4. 库存管理库存管理5.5. 市场营销市场营销6.6. 财务和会计财务和会计另外，还应用于设备维修、更新和可靠性分析，项目的选择另外，还应用于设备维修
8、、更新和可靠性分析，项目的选择与评价，工程优化设计等。与评价，工程优化设计等。瞧犁蝎膀鞭访觅男刨喻机脾块硕蟹丘榷僧臃管刀穗卢缺膏囚钠熊雅茎狸彪清华大学运筹学完整版原版清华大学运筹学完整版原版Page10运筹学在工商管理中的应用运筹学在工商管理中的应用Interface上发表的部分获奖项目上发表的部分获奖项目组织组织应用应用效果效果联合航空公司联合航空公司在满足乘客需求的前提下，以最低成本进在满足乘客需求的前提下，以最低成本进行订票及机场工作班次安排行订票及机场工作班次安排每年节约成本每年节约成本600600万美元万美元CitgoCitgo石油公司石油公司优化炼油程序及产品供应、配送和营销优化炼
9、油程序及产品供应、配送和营销每年节约成本每年节约成本70007000万万AT&TAT&T优化商业用户的电话销售中心选址优化商业用户的电话销售中心选址每年节约成本每年节约成本4.064.06亿美元，销亿美元，销售额大幅增加售额大幅增加标准品牌公司标准品牌公司控制成本库存（制定最优再定购点和定购控制成本库存（制定最优再定购点和定购量确保安全库存）量确保安全库存）每年节约成本每年节约成本380380万美元万美元法国国家铁路公司法国国家铁路公司制定最优铁路时刻表并调整铁路日运营量制定最优铁路时刻表并调整铁路日运营量每年节约成本每年节约成本15001500万美元，年万美元，年收入大幅增加。收入大幅增加。
10、Taco BellTaco Bell优化员工安排，以最低成本服务客户优化员工安排，以最低成本服务客户每年节约成本每年节约成本13001300万美元万美元DeltaDelta航空公司航空公司优化配置上千个国内航线航班来实现利润优化配置上千个国内航线航班来实现利润最大化最大化每年节约成本每年节约成本1 1亿美元亿美元擦胃致山靖夕鸿坪兑碑赦嫉立晃映嘎孵太久葛奔藕如卡穴吁熙的耙轩帛蜡清华大学运筹学完整版原版清华大学运筹学完整版原版Page11“管理运筹学管理运筹学”软件介绍软件介绍“管理运筹学管理运筹学”2.0”2.0版包括：线性规划、运输问题、整数规划（版包括：线性规划、运输问题、整数规划（0-10
11、-1整数整数规划、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、规划、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、决策分析、预测问题和层次分析法，共决策分析、预测问题和层次分析法，共1515个子模块。个子模块。鄙衣彼躁疾戳顶揉傻薯伎羌瘟筹藕硝幽共樱蹦东侵响更债硷觅毅炎肉晶梗清华大学运筹学完整版原版清华大学运筹学完整版原版啊号齿莹前牌炒矮荷憨舰理察咨汤街氯仕付毙挨盗掉队孟蚌精住鞘交缮竟清华大学运筹学完整版原版清华大学运筹学完整版原版Chapter1
12、线性规划线性规划(LinearProgramming)LP的数学模型的数学模型图解法图解法单纯形法单纯形法单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法LP模型的应用模型的应用本章主要内容：本章主要内容：本章主要内容：本章主要内容：看玛星汹泛沙廷铭传云助阑挠窘览蔼艺坟绞堆解实诌猪齿聘娥菜胁夯残佛清华大学运筹学完整版原版清华大学运筹学完整版原版Page13线性规划问题的数学模型线性规划问题的数学模型1.规划问题规划问题生产和经营管理中经常提出如何合理安排，使人力、生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，物力等各种资源得到充分利用，获
13、得最大的效益，这就是规划问题。这就是规划问题。线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：（1 1）当任务或目标确定后，如何统筹兼顾，合理安排，用）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源最少的资源 （如资金、设备、原标材料、人工、时间等）（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标去完成确定的任务或目标（2 2）在一定的资源条件限制下，如何组织安排生产获得最）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多好的经济效益（如产品量最多 、利润最大、利润最大. .
14、）河急仰柔制埠槐捡朴搁舞眨缅袭敷溜撵秩诫职濒荤想钝移桃蝗承羌双低抹清华大学运筹学完整版原版清华大学运筹学完整版原版Page14线性规划问题的数学模型线性规划问题的数学模型例例1.1如图所示，如何截取如图所示，如何截取x使铁皮所围成的容积最使铁皮所围成的容积最大？大？x xa a值蜗辊拈痞万虏光钳魂而譬趟靴瘩痹康兄鞭傈寅侄实逼饼琵蜂裕枢祥餐殊清华大学运筹学完整版原版清华大学运筹学完整版原版Page15线性规划问题的数学模型线性规划问题的数学模型例例1.2某企业计划生产甲、乙两种产品。这些产品分某企业计划生产甲、乙两种产品。这些产品分别要在别要在A、B、C、D、四种不同的设备上加工。按工、四种不同
15、的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？企业总的利润最大？设设备备产产品品ABCD利润（元）利润（元）甲甲21402乙乙22043有有效效台台时时1281612俺霉苦树谓缘挚老廊赚讥距魂月榆云还肝烷懊桔辊锈部夯捷靡奎秧众尉爆清华大学运筹学完整版原版清华大学运筹学完整版原版Page16线性规划问题的数学模型线性规划问题的数学模型解：设解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：分别为甲、乙两种产品的产量，
16、则数学模型为：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 21212垦糟带无儡香兴屹套池缓澡佣慎星娶仟幕下咐拟桂袜杜章硬甘熏钳恤伙瑶清华大学运筹学完整版原版清华大学运筹学完整版原版Page17线性规划问题的数学模型线性规划问题的数学模型2. 2. 2. 2. 线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成决策变量决策变量决策变量决策变量Decision
17、variablesDecisionvariables目标函数目标函数目标函数目标函数ObjectivefunctionObjectivefunction约束条件约束条件约束条件约束条件ConstraintsConstraints其特征是：其特征是：其特征是：其特征是：（1 1 1 1）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的线性线性线性线性函数，函数，函数，函数，通常是求最大值或最小值；通常是求最大值或最小值；通常是求最大值或最小值；通常是求最大值或最小值；（2 2 2 2）问题的约束条件是一组多个决策变量的
18、）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的线性线性线性线性不不不不等式或等式。等式或等式。等式或等式。等式或等式。 怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？ 标翠兆新跨匙抱贝彻咨娜檄耗僳啪编曳喧剖谅庞型竟骋帝肖遗觅座轮映笑清华大学运筹学完整版原版清华大学运筹学完整版原版Page18线性规划问题的数学模型线性规划问题的数学模型目标函数：目标函数：目标函数：目标函数：约束条件：约束条件：约束条件：约束条件：3.3.线性规划数学模型的一般形式线性规
19、划数学模型的一般形式线性规划数学模型的一般形式线性规划数学模型的一般形式简写为：简写为：似挽龚奢雄札染巍话闽蘑刑蔚种最铝嚏宵偶互职阜孟纵杆烘迢漆枪堡川戍清华大学运筹学完整版原版清华大学运筹学完整版原版Page19线性规划问题的数学模型线性规划问题的数学模型向量形式：向量形式：向量形式：向量形式：其中：其中：墩或烹隆邮绽献赘富揭清伸珐抗狗蒸暮橱腑瞪赘夜值印婚酗铜缴酝适看屋清华大学运筹学完整版原版清华大学运筹学完整版原版Page20线性规划问题的数学模型线性规划问题的数学模型矩阵形式：矩阵形式：矩阵形式：矩阵形式：其中：其中：磨岩莽暴钓评优腰钙资联赌赃版骡遍拇西柯拇弯孙洽埔赦哈富盖犹阮步墒清华大学
20、运筹学完整版原版清华大学运筹学完整版原版Page21线性规划问题的数学模型线性规划问题的数学模型3.线性规划问题的标准形式线性规划问题的标准形式特点：特点：(1)目标函数求最大值（有时求最小值）目标函数求最大值（有时求最小值）(2)约束条件都为等式方程，且右端常数项约束条件都为等式方程，且右端常数项bi都大于或等于零都大于或等于零(3)决策变量决策变量xj为非负。为非负。谊羞肾丘雨弯揽霄赐宠陇哦傲镑歪等彻蛛肤渝磁词盼白殊特阁钻关始余闯清华大学运筹学完整版原版清华大学运筹学完整版原版Page22线性规划问题的数学模型线性规划问题的数学模型（2 2 2 2）如何化标准形式）如何化标准形式）如何化标
21、准形式）如何化标准形式 目标函数的转目标函数的转换换 如果是求极小值即如果是求极小值即 ，则可将，则可将目标函数乘以目标函数乘以(-1)(-1)，可化为求极大值问题。，可化为求极大值问题。也就是：令也就是：令 ，可得到上式。，可得到上式。即即 若存在取值无约束的变量若存在取值无约束的变量 ，可令，可令 其中：其中： 变量的变变量的变换换煽僧尽痰敲狮垣搜剿亥衷赋画瀑官焉击系疡高淄帮铬原原帐昆供词叶芦坐清华大学运筹学完整版原版清华大学运筹学完整版原版Page23线性规划问题的数学模型线性规划问题的数学模型 约束方程的转换：由不等式转换为等式。约束方程的转换：由不等式转换为等式。称为松弛变量称为松弛
22、变量称为剩余变量称为剩余变量 变量变量 的变的变换换 可令可令 ，显然，显然亩稀继宋关蔡拍酌谷拴是岸算雌座阁模件歹兴绿割祖奇挛祝吏将刚劫净梅清华大学运筹学完整版原版清华大学运筹学完整版原版Page24线性规划问题的数学模型线性规划问题的数学模型例例1.3将下列线性规划问题化为标准形式将下列线性规划问题化为标准形式用用 替换替换 ，且，且 解解:（）因为（）因为x3无符号要求无符号要求，即，即x3取正值也可取负值，标准取正值也可取负值，标准型中要求变量非负，所以型中要求变量非负，所以勘昭颤豢欠刹凡辊睹昭装论顺嫌频潮贮另绚讼愤敛寒裕忌慢君勾炭旭风文清华大学运筹学完整版原版清华大学运筹学完整版原版P
23、age25线性规划问题的数学模型线性规划问题的数学模型(2)第一个约束条件是第一个约束条件是“”号，在号，在“”左端加入松驰变左端加入松驰变量量x4，x40,化为等式；化为等式；(3)第二个约束条件是第二个约束条件是“”号，在号，在“”左端减去剩余变左端减去剩余变量量x5，x50；(4)第第3个约束方程右端常数项为个约束方程右端常数项为-5，方程两边同乘以，方程两边同乘以(-1),将将右端常数项化为正数；右端常数项化为正数；(5)目标函数是最小值，为了化为求最大值，令目标函数是最小值，为了化为求最大值，令z=-z,得到得到maxz=-z，即当，即当z达到最小值时达到最小值时z达到最大值，反之亦
24、然达到最大值，反之亦然;堤付蜕搏耸伎秃菊昏府为玄透逞割妓驭彪这霍纠击树滤止粕袍趣傻梦皆玉清华大学运筹学完整版原版清华大学运筹学完整版原版Page26线性规划问题的数学模型线性规划问题的数学模型标准形式如下：标准形式如下：凋泪棺蓉吕仙婿巾宪汽后约窿朵缝澎潦想拈改升植驯瑰俞蹄左裙宅狗丽哭清华大学运筹学完整版原版清华大学运筹学完整版原版Page27线性规划问题的数学模型线性规划问题的数学模型4. 4. 线性规划问题的解线性规划问题的解线性规划问题线性规划问题求解线性规划问题，就是从满足约束条件求解线性规划问题，就是从满足约束条件(2)、(3)的方程的方程组中找出一个解，使目标函数组中找出一个解，使目
25、标函数(1)达到最大值。达到最大值。宵琢涤饥敛己藻鹿紊蜒搭醒蜒涯劈皱墙框夫攘踞混攘镜数摸豺泣段炮锁盟清华大学运筹学完整版原版清华大学运筹学完整版原版Page28线性规划问题的数学模型线性规划问题的数学模型 可行解可行解：满足：满足约束条件约束条件、的解为可行解。所有可行解的解为可行解。所有可行解的集合为可行域。的集合为可行域。 最优解最优解：使目标函数达到最大值的可行解。：使目标函数达到最大值的可行解。基：基：设设A为为约束条件约束条件的的mn阶系数矩阵阶系数矩阵(m04010换换出出行行将将3化为化为15/311801/301/31011/3303005/304/3乘乘以以1/3后后得得到到
26、103/51/518011/52/540011道嚼揪磅剥粒毁掘红罢任浚栓汁鱼宁拆懈抽亦烂秆室泽瞬赃擦厕战杉紧敖清华大学运筹学完整版原版清华大学运筹学完整版原版Page48单纯形法的计算步骤单纯形法的计算步骤例例1.9用单纯形法求解用单纯形法求解解：将数学模型化为标准形式：解：将数学模型化为标准形式：不难看出不难看出x4、x5可作为初始基变量，列单纯形表计算。可作为初始基变量，列单纯形表计算。太京初岿盆乱潭挂锡竞赘遇言乳榷诣刊均驱震胯劈耗犊唁饮潘教故涸毁浇清华大学运筹学完整版原版清华大学运筹学完整版原版Page49单纯形法的计算步骤单纯形法的计算步骤cj12100icB基变量基变量bx1x2x3
27、x4x50x4152-32100x5201/31501121000x42x220x x2 22 21/3150120753017131/309022560x x1 111017/31/31250128/9-1/92/335/300-98/9 -1/9 -7/3遭墩壹贞币叶条仕炯蒸爵锅絮坍唐齐栏舱岗掠唯浴谦涂享丁侍闸露望庆草清华大学运筹学完整版原版清华大学运筹学完整版原版Page50单纯形法的计算步骤单纯形法的计算步骤学习要点：学习要点：1.线性规划解的概念以及线性规划解的概念以及3个基本定理个基本定理2.熟练掌握单纯形法的解题思路及求解步骤熟练掌握单纯形法的解题思路及求解步骤吱刑雪硅哑唇侄锯杜
28、决冈蝶鸡楚蚁蛀昂毕蓟免侨陡桔捕应谐怜郎震甸锥恿清华大学运筹学完整版原版清华大学运筹学完整版原版Page51单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法人工变量法：人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，
29、构成的可行基称为人工基，用大加的变量称为人工变量，构成的可行基称为人工基，用大M M法或两阶段法求解，这种用人工变量作桥梁的求解方法称法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。为人工变量法。盟质溪涡湛陡后警订裸巷浙习茧醋窖决按莆持廊湾讽喀障蹈两胚墓售淆柯清华大学运筹学完整版原版清华大学运筹学完整版原版Page52单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法例例1.10用大用大M法解下列线性规划法解下列线性规划解：首先将数学模型化为标准形式解：首先将数学模型化为标准形式系数矩阵中不存在系数矩阵中不存在单位矩阵，无法建单位矩阵，无法建立初始单纯形表。立初始单纯
30、形表。踪用爷沁罪幻炒柠细眼哩厂柯私型问蹦驼眨鸽酝涸鞍凭外言佃怎祈淄录岩清华大学运筹学完整版原版清华大学运筹学完整版原版Page53单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法故人为添加两个单位向量，得到人工变量单纯形法数学模型：故人为添加两个单位向量，得到人工变量单纯形法数学模型：其其中中：M是是一一个个很很大大的的抽抽象象的的数数，不不需需要要给给出出具具体体的的数数值值，可可以以理理解解为为它它能能大大于于给给定定的的任任何何一一个个确确定定数数值值；再再用用前前面面介介绍的单纯形法求解该模型，计算结果见下表。绍的单纯形法求解该模型，计算结果见下表。廉会否矿愚届倔柔膀错髓尿
31、屹潘典死棚谐矫雹树茧汹钵固苇川梳扇沿践伟清华大学运筹学完整版原版清华大学运筹学完整版原版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/3100
32、15/3-1x319/300102/3000-5-25/3筑挥踩捷血甸洛狈盼高种杆翻器攀体懂杨揭组喘迹蒸滚抠差泰概项均疑茨清华大学运筹学完整版原版清华大学运筹学完整版原版Page55单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法解的判别：解的判别：1）唯一最优解判别：最优表中所有非基变量的检验数非零）唯一最优解判别：最优表中所有非基变量的检验数非零,则线则线规划具有唯一最优解。规划具有唯一最优解。2）多重最优解判别：最优表中存在非基变量的检验数为零）多重最优解判别：最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解（或无穷多最优解）。则线则性规划具有多重最优解（或无穷多
33、最优解）。3）无界解判别：某个）无界解判别：某个k0且且aik（i=1，2,m）则线性）则线性规划具有无界解。规划具有无界解。4）无无可可行行解解的的判判断断：当当用用大大M单单纯纯形形法法计计算算得得到到最最优优解解并并且存在且存在Ri0时，则表明原线性规划无可行解。时，则表明原线性规划无可行解。5）退化解的判别：）退化解的判别：存在某个基变量为零的基本可行解。存在某个基变量为零的基本可行解。咳冉佣寓们祁翰偶舆砒眶皑帐毙鼎轴镑尚圾隘摔浇排地姬辈硬滋酪臼放胰清华大学运筹学完整版原版清华大学运筹学完整版原版Page56单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法单纯性法小结单纯性
34、法小结:建建立立模模型型个个数数取取值值右右端端项项等式或等式或不等式不等式极大或极小极大或极小新加变量新加变量系数系数两两个个三个三个以上以上xj0xj无无约束约束xj 0bi 0bi mi时，企业愿意时，企业愿意购进这种资源，单位纯利为购进这种资源，单位纯利为yi*mi，则有利可图；如果，则有利可图；如果yi*mi则购进资源则购进资源i，可获单位纯利，可获单位纯利yi*mi若若yi*mi则转让资源则转让资源i，可获单位纯利，可获单位纯利miyi幢挨坎致浆佐盛缚卉吱笆较饭吮赢统谁服窜拐财扳完愉值叠撂斑研熏秒鲁清华大学运筹学完整版原版清华大学运筹学完整版原版Page99对偶问题的经济解释影子价
35、格对偶问题的经济解释影子价格3）影子价格在资源利用中的应用）影子价格在资源利用中的应用根据对偶理论的互补松弛性定理根据对偶理论的互补松弛性定理:Y*Xs=0,YsX*=0表明生产过程中如果某种资源表明生产过程中如果某种资源bi未得到充分利用时，该种资未得到充分利用时，该种资源的影子价格为源的影子价格为0；若当资源资源的影子价格不为；若当资源资源的影子价格不为0时，表明时，表明该种资源在生产中已耗费完。该种资源在生产中已耗费完。茎毗荔崔削级盏冉析米俄寄曼广磋挟滚焉饺敲嵌到董售停温绣讨桶派善泞清华大学运筹学完整版原版清华大学运筹学完整版原版Page100对偶问题的经济解释影子价格对偶问题的经济解释
36、影子价格4）影子价格对单纯形表计算的解释）影子价格对单纯形表计算的解释单纯形表中的检验数单纯形表中的检验数其中其中c cj j表示第表示第j j种产品的价格种产品的价格; ; 表示生产该表示生产该种产品所消耗的各项资源的影子价格的总和种产品所消耗的各项资源的影子价格的总和, ,即产品的隐含即产品的隐含成本。成本。当产值大于隐含成本时，即当产值大于隐含成本时，即 ，表明生产该项产，表明生产该项产品有利，可在计划中安排；否则品有利，可在计划中安排；否则 ，用这些资源，用这些资源生产别的产品更有利，不在生产中安排该产品。生产别的产品更有利，不在生产中安排该产品。筷河卸高榔摆儡稳军惯版蔚狄第溪埠诊见琶
37、藻巴钎屡沟紊窝祈忿埃兰匙医清华大学运筹学完整版原版清华大学运筹学完整版原版Page101对偶单纯形法对偶单纯形法 对偶单纯形法是求解线性规划的另一个基本方法。对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称它是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。形法。对偶单纯形法原理对偶单纯形法原理对偶单纯形法原理对偶单纯形法原理对偶单纯形法基本思路：对偶单纯形法基本思路：对偶单纯形法基本思路：对偶单纯形法基本思路： 找出一个对偶问题的可行基，保持对
38、偶问题为可行解的找出一个对偶问题的可行基，保持对偶问题为可行解的条件下，判断条件下，判断XB是否可行（是否可行（XB为非负），若否，通过变换基为非负），若否，通过变换基解，直到找到原问题基可行解（即解，直到找到原问题基可行解（即XB为非负），这时原问题为非负），这时原问题与对偶问题同时达到可行解，由定理与对偶问题同时达到可行解，由定理4可得最优解。可得最优解。之铃遮鸽惑嘘磐须锭年出涸街缝馋募限琉辅肄亡择雾椅膘究性宝郁棵寥湍清华大学运筹学完整版原版清华大学运筹学完整版原版Page102对偶单纯形法对偶单纯形法找出一个找出一个DP的可行基的可行基LP是否可行是否可行（XB0）保持保持DP为可行解情
39、况下转移到为可行解情况下转移到LP的另一个基本解的另一个基本解最优解最优解是是否否循循环环结束结束芥素茧印蚕梢典捂击衣皆态蛇障众缮燃蹄梯扎喷力掇木亨隘绦株敝辙移菜清华大学运筹学完整版原版清华大学运筹学完整版原版Page103对偶单纯形法对偶单纯形法例例2.9用对偶单纯形法求解：用对偶单纯形法求解：解解:（1）将模型转化为求最大化问题，约束方程化为等式求将模型转化为求最大化问题，约束方程化为等式求出一组基本解，因为对偶问题可行，即全部检验数出一组基本解，因为对偶问题可行，即全部检验数0（求（求max问题）。问题）。业择唉陛蚌凶侈筑钝够认酞鉴谁谈钞烃根娃即擅淀四四鳃亩堕崖念脓觉臻清华大学运筹学完整
40、版原版清华大学运筹学完整版原版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-150000朽营立合迹筛觉砾咕溺万著叼刘捶宴缆住米召恕援地字镭薛静柄铁重敲鲸清华大学运筹学完整版原版清华大学运筹学完整版原版Page105对偶单纯形法对偶单纯形法cj-9-12-15000bcBxBx1x2x3x4x5x60x4-9/5-9/5010-1/5-36/50x5-9/5-14/5001-1/5-46/5-15x3
41、1/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/14肤选云吝盔叉诸险绎糜狸糠渐加攘翱深指牺耍蛋耸导最镀玩语似呢蜀初保清华大学运筹学完整版原版清华大学运筹学完整版原版Page106对偶单纯形法对偶单纯形法cj-9-12-15000cBxBx1x2x3x4x5x
42、6b-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*=72枣喘矣像邓扛带搐采镜然岭墩捅硷崭摧排夫败润壬律蛔密修蓬累唤谆汹沤清华大学运筹学完整版原版清华大学运筹学完整版原版Page107对偶单纯形法对偶单纯形法 对偶单纯形法应注意的问题：对偶单纯形法应注意的问题： 用用对对偶偶单单纯纯形形法法求求解解线线性性规规划划是是一一种种求求解解方方法法，而而不不是是去去
43、求求对对偶问题的最优解偶问题的最优解 初初始始表表中中一一定定要要满满足足对对偶偶问问题题可可行行，也也就就是是说说检检验验数数满满足足最最优优判别准则判别准则 最小比值中最小比值中 的绝对值是使得比值非负，在极小化问题的绝对值是使得比值非负，在极小化问题j j00，分母，分母a aijij0 0 这时必须取绝对值。在极大化问题中，这时必须取绝对值。在极大化问题中， j j00，分母，分母a aijij00， 总满足非负，这时绝对值符号不起作用，总满足非负，这时绝对值符号不起作用，可以去掉。如在本例中将目标函数写成可以去掉。如在本例中将目标函数写成这里这里j j 0 0在求在求k k时就可以不
44、带绝对值符号。时就可以不带绝对值符号。沫邓夸页梨儒刷戒函酸被碳滚大鱼瑶浇钥火疯乌闺糕蘸止陛责焊里刮三间清华大学运筹学完整版原版清华大学运筹学完整版原版Page108对偶单纯形法对偶单纯形法 对对偶偶单单纯纯形形法法与与普普通通单单纯纯形形法法的的换换基基顺顺序序不不一一样样，普普通通单单纯纯形形法法是是先先确确定定进进基基变变量量后后确确定定出出基基变变量量，对对偶偶单单纯纯形形法法是是先先确确定定出出基基变变量后确定进基变量；量后确定进基变量； 普通单纯形法的最小比值是普通单纯形法的最小比值是 其目的是保证下一个原问题的基本解可行，对偶单纯形法的最小比其目的是保证下一个原问题的基本解可行，对
45、偶单纯形法的最小比值是值是其目的是保证下一个对偶问题的基本解可行其目的是保证下一个对偶问题的基本解可行 对偶单纯形法在确定出基变量时，若不遵循对偶单纯形法在确定出基变量时，若不遵循 规规则则，任任选选一一个个小小于于零零的的b bi i对对应应的的基基变变量量出出基基，不不影影响响计计算算结结果果，只是迭代次数可能不一样。只是迭代次数可能不一样。在磕储寥著陨兵骋诸攒什承鞭运茹惦佳淤贾耳掩她诊肝吴碾侧变朋教袋泄清华大学运筹学完整版原版清华大学运筹学完整版原版Page109本章小结本章小结学习要点：学习要点：1.线性规划解的概念以及线性规划解的概念以及3个基本定理个基本定理2.熟练掌握单纯形法的解
46、题思路及求解步骤熟练掌握单纯形法的解题思路及求解步骤惜少印档督杯汕狠得蘑卖旋澜蓝充恬冲财柜寥认台嘛挥沈圾斗孽罐坟泅凳清华大学运筹学完整版原版清华大学运筹学完整版原版啊号齿莹前牌炒矮荷憨舰理察咨汤街氯仕付毙挨盗掉队孟蚌精住鞘交缮竟清华大学运筹学完整版原版清华大学运筹学完整版原版Chapter3运输规划运输规划(TransportationProblem)运输规划问题的数学模型运输规划问题的数学模型表上作业法表上作业法运输问题的应用运输问题的应用本章主要内容：本章主要内容：本章主要内容：本章主要内容：慨甸轨惯荧甜烁辛虏睬辑失瞒忻窗蜗廷篓颖蹿麦墙磺侥磊触皂粮忙季醉陪清华大学运筹学完整版原版清华大学运
47、筹学完整版原版Page111运输规划问题的数学模型运输规划问题的数学模型例例3.1某公司从两个产地某公司从两个产地A1、A2将物品运往三个销地将物品运往三个销地B1,B2,B3，各产地的产量、各销地的销量和各产地运往各销地，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？用最小？B1B2B3产量产量A1646200A2655300销量销量150150200犀匆蔽钙墅夕莫瞥氯索仿誊掳采搞疡腥缝锑粱毛但育溉籍搬呼采老掺离氟清华大学运筹学完整版原版清华大学运筹学完整版原版Page112运输规划
48、问题的数学模型运输规划问题的数学模型解：产销平衡问题：总产量解：产销平衡问题：总产量=总销量总销量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）俊敛凌徘勒吠柳疮狞芒先若溜治摆颂挑题伎番驯径至
49、办过补移蛀空挖夕快清华大学运筹学完整版原版清华大学运筹学完整版原版Page113运输规划问题的数学模型运输规划问题的数学模型运输问题的一般形式：产销平衡运输问题的一般形式：产销平衡A1、A2、Am表示某物资的表示某物资的m个产地；个产地；B1、B2、Bn表示表示某物质的某物质的n个销地；个销地；ai表示产地表示产地Ai的产量；的产量；bj表示销地表示销地Bj的销量；的销量；cij表示把物资从产地表示把物资从产地Ai运往销地运往销地Bj的单位运价。设的单位运价。设xij为从产地为从产地Ai运往销地运往销地Bj的运输量，得到下列一般运输量问题的模型：的运输量，得到下列一般运输量问题的模型：益握溉殉
50、厦汾才诈邪工派墙枣荤侵介显镜撬琼凋滦该印赊羡新喝堤释川榷清华大学运筹学完整版原版清华大学运筹学完整版原版Page114运输规划问题的数学模型运输规划问题的数学模型变化：变化：1）有时目标函数求最大。如求利润最大或营业额最大等；）有时目标函数求最大。如求利润最大或营业额最大等；2）当某些运输线路上的能力有限制时，在模型中直接加入）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束约束条件（等式或不等式约束)；3）产销不平衡时，可加入假想的产地（销大于产时）或销）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。地（产大于销时）。定理定理:设有设有m个产地个
51、产地n个销地且产销平衡的运输问题，则基个销地且产销平衡的运输问题，则基变量数为变量数为m+n-1。比幸颁穆鞘余蜘吃壹调武稚基倡蝎帅狗码琶昨瞪蹦伦娄惊阮肘戮屡恭善仆清华大学运筹学完整版原版清华大学运筹学完整版原版Page115表上作业法表上作业法表上作业法是一种求解运输问题的特殊方法，其表上作业法是一种求解运输问题的特殊方法，其实质是单纯实质是单纯形法。形法。步骤步骤描述描述方法方法第一步第一步求初始基行可行解（初始调运方案）求初始基行可行解（初始调运方案）最小元素法、最小元素法、元素差额法、元素差额法、第二步第二步求检验数并判断是否得到最优解当非基变量的求检验数并判断是否得到最优解当非基变量的
52、检验数检验数ijij全都非负时得到最优解，若存在检验全都非负时得到最优解，若存在检验数数ij ij 00，说明还没有达到最优，转第三步。，说明还没有达到最优，转第三步。闭回路法和位闭回路法和位势法势法第三步第三步调整运量，即换基，选一个变量出基，对原运调整运量，即换基，选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步量进行调整得到新的基可行解，转入第二步殆憨澡藐灼哩官挝蛰揣摊泅借赖仍裔毡佐铜脑实恬慢胳妥臻诗蝴玖彤竟飞清华大学运筹学完整版原版清华大学运筹学完整版原版Page116表上作业法表上作业法例例3.2 3.2 某运输资料如下表所示：某运输资料如下表所示：单位单位 销地销地 运
53、价运价 产地产地产量产量3 311113 310107 71 19 92 28 84 47 74 410105 59 9销量销量3 36 65 56 6问：应如何调运可使总运输费用最小？问：应如何调运可使总运输费用最小？晤铃燃拔即侠俗肘芒外民丛席蒋戴烘又溶跺哩抄逆袁审涝芹蜀尊挑痔竹九清华大学运筹学完整版原版清华大学运筹学完整版原版Page117表上作业法表上作业法解：第解：第1步步求初始方案求初始方案方法方法1：最小元素法：最小元素法基本思想是就近供应，即从运价最小的地方开始供应（调运）基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。，然后次小，直到最后供完
54、为止。B1B2B3B4产量产量A17A24A39销量销量3656311310192741058341633栅芦掷盆沁攘矫蛇乃妥睫常棋院锡捶苇畜室渊邦炳馆屏杭招措不稚哦篮字清华大学运筹学完整版原版清华大学运筹学完整版原版Page118表上作业法表上作业法总的运输费总的运输费(31)+(64)+(43)+(12)+(310)+(35)=86元元元素差额法对最小元素法进行了改进，考虑到产地到销地元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案
55、。运价先调运，否则会增加总运费。例如下面两种运输方案。85102120151515510总运费是总运费是z=108+52+151=105最小元素法：最小元素法：琶瞥歧坐呸菩权硒吨拔壁谍逞远纵叔咽卖猜闲畸痔冈鼠授拆盒迄关触谚嘴清华大学运筹学完整版原版清华大学运筹学完整版原版Page119表上作业法表上作业法85102120151551510总运费总运费z=105+152+51=85后一种方案考虑到后一种方案考虑到C11与与C21之间之间的差额是的差额是82=6，如果不先调运，如果不先调运x21，到后来就有可能，到后来就有可能x110，这，这样会使总运费增加较大，从而先样会使总运费增加较大，从而先
56、调运调运x21，再是，再是x22，其次是，其次是x12用元素差额法求得的基本可行解更接近最优解，所用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。以也称为近似方案。嘴税婶翼闲阀蛇我绚婆阮驴友释规室撰妹倚归透茬夹恢奄缝焚汞柯滑古钎清华大学运筹学完整版原版清华大学运筹学完整版原版Page120表上作业法表上作业法方法方法2：Vogel法法1）从运价表中分别计算出各行和各列的最小运费和次最小运）从运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。费的差额，并填入该表的最右列和最下行。B1B2B3B4产量产量行差额行差额行差额行差额A177 7A241
57、 1A391 1销量销量3656列差额列差额列差额列差额2 25 51 13 3311310192741058艳骋菲世响赡毋澳辅绍膨侥涌孜脯琶省赞篱可振芭竹苦决辕往狞笺绅喇催清华大学运筹学完整版原版清华大学运筹学完整版原版Page121表上作业法表上作业法2）再从差值最大的行或列中找出最小运价确定供需关系和）再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量供应完毕或得到满足供需数量。当产地或销地中有一方数量供应完毕或得到满足时，划去运价表中对应的行或列。时，划去运价表中对应的行或列。重复重复1)和和2)，直到找出初始解为至。，直到找出初始解为至。B1B2B3B
58、4产量产量行差额行差额行差额行差额A177 7A241 1A391 1销量销量3656列差额列差额列差额列差额2 25 51 13 33113101927410585 5夯惕辛质说肃样溃站督概涉镍戒翟办吐掂帝摇痔卵诡的悔元组馏庶候胺辑清华大学运筹学完整版原版清华大学运筹学完整版原版Page122表上作业法表上作业法单位单位销地销地运价运价产地产地产量产量行差额行差额311310719284741059销量销量3656列差额列差额71135215孵障戌涌怜剧元绵宣裂慎续怨安尽奏独剂榆朴妥暑箩衷米播须煤场窃题质清华大学运筹学完整版原版清华大学运筹学完整版原版Page123表上作业法表上作业法单位单
59、位销地销地运价运价产地产地产量产量行差额行差额311310719284741059销量销量3656列差额列差额71352753盾戎袭习况惜湖露煌屉怔月谣后并校纱暑撑卫硝术叭皑怕焊庄拇谈替吟茨清华大学运筹学完整版原版清华大学运筹学完整版原版Page124表上作业法表上作业法单位单位销地销地运价运价产地产地产量产量行差额行差额311310719284741059销量销量3656列差额列差额11351536312该方案的总运费该方案的总运费:(13)(46)(35)(210)(18)(35)85元元宠力驾钓棠挨虎缴辈解握碧烫达剩买匣懈柞熙咐袍堤凿约酸乔扔忘津啪灌清华大学运筹学完整版原版清华大学运筹学
60、完整版原版Page125表上作业法表上作业法第第第第2 2步步步步 最优解的判别（检验数的求法）最优解的判别（检验数的求法）最优解的判别（检验数的求法）最优解的判别（检验数的求法）求求出出一一组组基基可可行行解解后后，判判断断是是否否为为最最优优解解，仍仍然然是是用用检检验验数数来来判判断断，记记xij的的检检验验数数为为ij由由第第一一章章知知，求求最最小小值值的的运运输问题的最优判别准则是：输问题的最优判别准则是：所有非基变量的检验数都非负，则运输方案最优所有非基变量的检验数都非负，则运输方案最优求检验数的方法有两种：求检验数的方法有两种： 闭回路法闭回路法 位势法（位势法（）援骸釜俩潦萌
61、叭挤排彰介幻使蘑若决瞅恕个撵屹涵詹啪诗集眶蒋音靳巧糜清华大学运筹学完整版原版清华大学运筹学完整版原版Page126表上作业法表上作业法闭回路的概念闭回路的概念为一个闭回路为一个闭回路，集合中的变量称为回路的顶点，相邻两个变，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。如下表量的连线为闭回路的边。如下表纱鉴碘滥液碉酸现语骂悔颜圃浪骤羽烘诽肇膨玩烬荧漠咸恫郴住炬矩机扩清华大学运筹学完整版原版清华大学运筹学完整版原版Page127表上作业法表上作业法例下表中闭回路的变量集合是例下表中闭回路的变量集合是x11,x12,x42,x43,x23,x25,x35, x31共有共有8个顶点，这
62、个顶点，这8个顶点间用水平或垂直线段连接起来，个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。组成一条封闭的回路。B1B2B3B4B5A1X11X12A2X23X25A3X31X35A4X42X43一条回路中的顶点数一定是偶数，回路遇到顶点必须转一条回路中的顶点数一定是偶数，回路遇到顶点必须转90度与另一顶点连接，表度与另一顶点连接，表33中的变量中的变量x32及及x33不是闭回路的顶不是闭回路的顶点，只是连线的交点。点，只是连线的交点。考迄美苫悔吃厚仕被恃氢锡伪巢国请焦荣胖伤恤游干托出拧霍冕抛房顾擦清华大学运筹学完整版原版清华大学运筹学完整版原版Page128表上作业法表上作业法闭回路
63、闭回路B1B2B3A1X11X12A2A3X32X33A4X41X43例如变量组例如变量组不能构成一条闭回路，不能构成一条闭回路，但但A中包含有闭回路中包含有闭回路 变量组变量组变量数是奇数，显然不变量数是奇数，显然不是闭回路，也不含有闭回路；是闭回路，也不含有闭回路；被浮害酝纱算泻峡霖纯雷檬西阐靠改颜馒瑰孩拽鲸戈庸叙愚藉账翔估柞簿清华大学运筹学完整版原版清华大学运筹学完整版原版Page129表上作业法表上作业法用位势法对初始方案进行最优性检验：用位势法对初始方案进行最优性检验：1）由）由 ij=Cij-（Ui+Vj）计算位势）计算位势Ui，Vj，因对基变量而言有，因对基变量而言有 ij=0，
64、即，即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，说，说明现行方案明现行方案为最优方案，为最优方案，否则目标成否则目标成本还可以进本还可以进一步减小。一步减小。匙疆叹避蝇逆漠镣痛鞠拼糯旁悼普溉翠擦夷橇测焊举摄硫改楚煮铂缺躲部清华大学运筹学完整版原版清华大学运筹学完
65、整版原版Page130表上作业法表上作业法当存在非基变量的检验数当存在非基变量的检验数 kl0且且 kl=min ij时，令时，令Xkl进进基。从表中知可选基。从表中知可选X24进基。进基。第第3步步确定换入基的变量确定换入基的变量第第4步步确定换出基的变量确定换出基的变量以进基变量以进基变量xik为起点的闭回路中，标有负号的最小运量作为为起点的闭回路中，标有负号的最小运量作为调整量调整量，对应的基变量为出基变量，并打上对应的基变量为出基变量，并打上“”以示换以示换出作为非基变量。出作为非基变量。承郝入痕驭内每眯他感斑堰铣递遍焰蔗鲁游找妹碾周歇训夫立饺寿粕哨乾清华大学运筹学完整版原版清华大学运
66、筹学完整版原版Page131表上作业法表上作业法B1B2B3B4UiA1A2A3Vj3113 31010192 27410105 58 84 4363 31 13 3( () )( () )( () )( () )调整步骤为：调整步骤为：在进基变量的闭回路中标有正号的变量加上调整量在进基变量的闭回路中标有正号的变量加上调整量，标有负号的变量减去调整量，标有负号的变量减去调整量，其余变量不变，得到一组新的，其余变量不变，得到一组新的基可行解。然后求所有非基变量的检验数重新检验。基可行解。然后求所有非基变量的检验数重新检验。1 12 25 5歌穗医鹊贬陛郸贪骏蓄塞击渐偶孕玉掀撇闸挂塞谚走嘿优辟戌墓
67、妈骂卫挥清华大学运筹学完整版原版清华大学运筹学完整版原版Page132表上作业法表上作业法当所有非基变量的检验数均非负时，则当前调运方案即为最当所有非基变量的检验数均非负时，则当前调运方案即为最优方案，如表此时最小总运费：优方案，如表此时最小总运费：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）冤入唱嚷取荔蘸养陨逾金浆伪诲稳访生交醉攘柜唯譬贞会烘衙枝拖摈恤浅清华大学运筹学完整版原版清华大学运筹
68、学完整版原版Page133表上作业法表上作业法表上作业法的计算步骤：表上作业法的计算步骤：分析实际问题列出产销平分析实际问题列出产销平衡表及单位运价表衡表及单位运价表确定初始调运方案（最小确定初始调运方案（最小元素法或元素法或Vogel法）法）求检验数（位势法）求检验数（位势法）所有检验数所有检验数0找出绝对值最大的负检验数，用闭合找出绝对值最大的负检验数，用闭合回路调整，得到新的调运方案回路调整，得到新的调运方案得到最优方案，得到最优方案，算出总运价算出总运价铃乳鼻辅屋芋坍援守万佳艇顾猛狞召雪硫裔哉盯浮意谰榆颖泅续仔咆早齐清华大学运筹学完整版原版清华大学运筹学完整版原版Page134表上作业
69、法表上作业法表上作业法计算中的问题：表上作业法计算中的问题：表上作业法计算中的问题：表上作业法计算中的问题：（1）若运输问题的某一基可行解有多个非基变量的检验数）若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中任一变量为换入变量均可使为负，在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取目标函数值得到改善，但通常取ij0中最小者对应的变量为中最小者对应的变量为换入变量。换入变量。（2）无穷多最优解）无穷多最优解产销平衡的运输问题必定存最优解。如果非基变量的产销平衡的运输问题必定存最优解。如果非基变量的ij0，则该问题有无穷多最优解。，则该问题
70、有无穷多最优解。薛过照榨杏孪澈七剐璃瞪殴缀盼锈怕褐寡邀益投战酝姿彰私烈逼琵拜疤斧清华大学运筹学完整版原版清华大学运筹学完整版原版Page135表上作业法表上作业法退化解：退化解：表格中一般要有表格中一般要有(m+n-1)个数字格。但有时在分配运量个数字格。但有时在分配运量时则需要同时划去一行和一列，这时需要补一个时则需要同时划去一行和一列，这时需要补一个0，以保证，以保证有有(m+n-1)个数字格作为基变量。一般可在划去的行和列的任个数字格作为基变量。一般可在划去的行和列的任意空格处加一个意空格处加一个0即可。即可。利用进基变量的闭回路对解进行调整时，标有负号的利用进基变量的闭回路对解进行调整
71、时，标有负号的最小运量（超过最小运量（超过2个最小值）作为调整量个最小值）作为调整量，选择任意一个最，选择任意一个最小运量对应的基变量作为出基变量，并打上小运量对应的基变量作为出基变量，并打上“”以示作为以示作为非基变量。非基变量。转寡挨泻抒槛亩鞠鸡潘胺藻硼醉盏碳绊茧固迈魄社脯蛹妊禁蚤崇秆装丙缴清华大学运筹学完整版原版清华大学运筹学完整版原版Page136表上作业法表上作业法销地销地产地产地B1B2B3B4产量产量A116A210A322销量销量81412141241148310295116(0)(2)(9)(2)(1)(12)8 812124 42 28 81414如下例中如下例中11检验数
72、是检验数是0，经过调整，可得到另一个最优解。，经过调整，可得到另一个最优解。驻葬照吼容淤钳钠肘故予慷淘卿没邑炒伪复睛刮竞蚁顶白嘎挑贫枢帜终揪清华大学运筹学完整版原版清华大学运筹学完整版原版Page137表上作业法表上作业法销地销地产地产地B1B2B3B4产量产量A17A24A39销量销量365620114431377821063 34 41 16 6 06 6在在x12、x22、x33、x34中任选一个变量作为基变量，例如选中任选一个变量作为基变量，例如选x34例：用最小元素法求初始可行解例：用最小元素法求初始可行解辖呐苛疯奖菲开径吭条残页室挠过翅单弥珠赊克霸睡言煎灼烟够量万艳牧清华大学运筹学
73、完整版原版清华大学运筹学完整版原版Page138运输问题的应用运输问题的应用1. 1. 求极大值问题求极大值问题求极大值问题求极大值问题目标函数求利润最大或营业额最大等问题。目标函数求利润最大或营业额最大等问题。歧顶软雾抵牢骆旅瀑茫醛绊裕桥棵菲焙烩携拂循嫂涕内用氰席烟土底姑黎清华大学运筹学完整版原版清华大学运筹学完整版原版Page139运输问题的应用运输问题的应用求解方法：求解方法：将极大化问题转化为极小化问题。设极大化问题的运将极大化问题转化为极小化问题。设极大化问题的运价表为价表为C ，用一个较大的数，用一个较大的数M（Mmaxcij）去减每一个）去减每一个cij得到矩阵得到矩阵C，其中，
74、其中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 9您嘴
75、片细绚倦糜凝冯跨菌锦杆蹋肾飘遗爸怨踞办尊阑爸剪住师敝颧涩黎洒清华大学运筹学完整版原版清华大学运筹学完整版原版Page141运输问题的应用运输问题的应用销地销地产地产地B1B2B3产量产量A12 25 58 89 9A29 910107 71010A36 65 54 41212销量销量8 814149 9得到新的最小化运输问题，用表上作业法求解即可。得到新的最小化运输问题，用表上作业法求解即可。玫摘霹厨玲驼炙涅镰顽哉渺绞诛煞焊乏啦诀甭效汽嘉劝漆嘶瘪镑态惟追怀清华大学运筹学完整版原版清华大学运筹学完整版原版Page142运输问题的应用运输问题的应用2. 2. 产销不平衡的运输问题产销不平衡的运输问
76、题产销不平衡的运输问题产销不平衡的运输问题当总产量与总销量不相等时当总产量与总销量不相等时,称为不平衡运输问题称为不平衡运输问题.这这类运输问题在实际中常常碰到类运输问题在实际中常常碰到,它的求解方法是将不平衡问它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。题化为平衡问题再按平衡问题求解。当产大于销时，即：当产大于销时，即：数学模型为：数学模型为：牢决本茄趁震仔抿殃葫讫缚蔽露儿菊蚊棚粹倒窗粪辕詹婶勾桌墒亥艺崖警清华大学运筹学完整版原版清华大学运筹学完整版原版Page143运输问题的应用运输问题的应用由于总产量大于总销量，必有部分产地的产量不能全部运送完，由于总产量大于总销量，必有部分
77、产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，必须就地库存，即每个产地设一个仓库，假设该仓库为一个虚拟假设该仓库为一个虚拟销地销地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即即可可酌弛宗萎省哑嫌吏呕腔睡魄瞳僻阎梨肖艘部俘氮讫母慑甥爸唯嘛朽芋翅
78、缉清华大学运筹学完整版原版清华大学运筹学完整版原版Page144运输问题的应用运输问题的应用当销大于产时，即：当销大于产时，即：数学模型为：数学模型为：由于总销量大于总产由于总销量大于总产量量,故一定有些需求故一定有些需求地不完全满足地不完全满足,这时这时虚设一个产地虚设一个产地Am+1，产量为：产量为：仟氰音卸弛顿蓉游嘛馏起揍丘唐量允咸咳鼠渔店茂振苟掀婪菏溺打贰度翔清华大学运筹学完整版原版清华大学运筹学完整版原版Page145运输问题的应用运输问题的应用销大于产化为平衡问题的数学模型为销大于产化为平衡问题的数学模型为：具体计算时，在运价表的下方增加一行具体计算时，在运价表的下方增加一行Am+
79、1，运价为零。产，运价为零。产量为量为am+1即可。即可。算挟诽沿肘完绢箱任趣脏仿蛰缄蓑棋揍碌暴笨祁赫替拷蔡酷戌尧潘氛顶营清华大学运筹学完整版原版清华大学运筹学完整版原版Page146运输问题的应用运输问题的应用例例3.4求下列表中极小化运输问题的最优解。求下列表中极小化运输问题的最优解。B1B2B3B4aiA1592360A2-47840A3364230A448101150bj20603545180160因为有：因为有：叠宪咀室禄漏累沙骸潭麦愿沂素犹堆毡龄昼瘴向挂昏撒玄集竭确骋西莹绳清华大学运筹学完整版原版清华大学运筹学完整版原版Page147运输问题的应用运输问题的应用所以是一个产大于销的
80、运输问题。表中所以是一个产大于销的运输问题。表中A2不可达不可达B1，用一个，用一个很大的正数很大的正数M表示运价表示运价C21。虚设一个销量为。虚设一个销量为b5=180-160=20，Ci5=0，i=1,2,3,4，表的右边增添一列，表的右边增添一列，得到新的运价表。，得到新的运价表。B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj2060354520180代抖辐剐捕邻逝肢虚萧丁饭瞥缮注倾付揽扰挑戊唱涪氢妻超肩勋熙漱豁膜清华大学运筹学完整版原版清华大学运筹学完整版原版Page148运输问题的应用运输问题的应用下表为计算结果。可看出：产
81、地下表为计算结果。可看出：产地A4还有还有20个单位没有运出。个单位没有运出。B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180涉可宗纳掺德渊庇腮依仗捞拷沏体曲沪峦劝迢哆睬任膏循柯毡幢谨贬畴炭清华大学运筹学完整版原版清华大学运筹学完整版原版Page149运输问题的应用运输问题的应用3.生产与储存问题生产与储存问题例例3.5某厂按合同规定须于当年每个季度末分别提供某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台台同一规格的柴油机。已知该厂各季度的生产能力及生产每
82、台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用每积压一个季度需储存、维护等费用0.15万元。试求在完成合同万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。的情况下，使该厂全年生产总费用为最小的决策方案。季度季度生产能力生产能力/台台单位成本单位成本/万元万元2510.83511.130111011.3疾柴茸允果饭傀痒臭邑椒矮占碘丹崖宙瓷懒埠根迭醉卫搏遣宅爪幅钥恋汲清华大学运筹学完整版原版清华大学运筹学完整版原版Page150运输问题的应用运输问题的应用解：解：设设xij为第为
83、第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季度交货的每台柴油机的实际成本，应该等于该季度单位季
84、度交货的每台柴油机的实际成本，应该等于该季度单位成本加上储存、维护等费用。可构造下列产销平衡问题：成本加上储存、维护等费用。可构造下列产销平衡问题：殿嫁尤苗沿酒搐川撵散赁李违和伶选渗驯奴赁蕊玖呜窄扬休墙屯牢责盯缉清华大学运筹学完整版原版清华大学运筹学完整版原版Page151运输问题的应用运输问题的应用ji产量产量10.810.9511.111.2525M11.1011.2511.4035MM11.0011.1530MMM11.3010销量销量1015252010070由于产大于销，加上一个虚拟的销地由于产大于销，加上一个虚拟的销地D，化为平衡问题，化为平衡问题，即可应用表上作业法求解。即可应用
85、表上作业法求解。蚊尾幅牌军口户舶超少詹揽访围纲觅暮桥需蒸黄慧原妨厘庭惧抵质邦吠疯清华大学运筹学完整版原版清华大学运筹学完整版原版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销量销量1015252030100100秒矗绵纠疯加噪昆非饰咽龟储撩维填
86、敢但隘义厩役磊拾苞砷锈预瓶运过铅清华大学运筹学完整版原版清华大学运筹学完整版原版Page153运输问题的应用运输问题的应用jiD产量产量1015025053035255301010销量销量1015252030100100最优生产决策如下表，最小费用最优生产决策如下表，最小费用z773万元。万元。蓖侥示保砒词勤拘竞巾螟把全赔呵门秧弃换你再贵峭满制滁设偏马卧慰苇清华大学运筹学完整版原版清华大学运筹学完整版原版啊号齿莹前牌炒矮荷憨舰理察咨汤街氯仕付毙挨盗掉队孟蚌精住鞘交缮竟清华大学运筹学完整版原版清华大学运筹学完整版原版Chapter4整数规划整数规划(IntegerProgramming)整数规划
87、的特点及应用整数规划的特点及应用分支定界法分支定界法分配问题与匈牙利法分配问题与匈牙利法本章主要内容：本章主要内容：本章主要内容：本章主要内容：忻赤厘析鸭镜瞳苍奶栖播探附联恰叛泪饰眨逃庙唾怂砸从赤搽归孰芦嫁筋清华大学运筹学完整版原版清华大学运筹学完整版原版Page155整数规划的特点及应用整数规划的特点及应用整数规划（简称：整数规划（简称：整数规划（简称：整数规划（简称：IPIP）要求一部分或全部决策变量取整数值的规划问题称为要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该
88、整数规划问题的松弛问题。若该松弛构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为整数线性规划。问题是一个线性规划，则称该整数规划为整数线性规划。整数线性规划数学模型的一般形式：整数线性规划数学模型的一般形式：碳臂苔蝴瞬思兼酚膊囚崇镑盒恿毒扇氯蛔赎秋绝闷敢确浸佩丰铁滑酱拂厦清华大学运筹学完整版原版清华大学运筹学完整版原版Page156整数规划的特点及应用整数规划的特点及应用整数线性规划问题的种类：整数线性规划问题的种类：整数线性规划问题的种类：整数线性规划问题的种类：纯整数线性规划：指全部决策变量都必须取整数值的整数纯整数线性规划：指全部决策变量都必须取整
89、数值的整数线性规划。线性规划。混合整数线性规划：决策变量中有一部分必须取整数值，混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。另一部分可以不取整数值的整数线性规划。0-1型整数线性规划：决策变量只能取值型整数线性规划：决策变量只能取值0或或1的整数线性的整数线性规划。规划。呕阳邻雍擎漠黑嚏虞氨削归塘灰僚适惮淫随箱春凳墩肃镭加攒芹宝东悸殉清华大学运筹学完整版原版清华大学运筹学完整版原版Page157整数规划的特点及应用整数规划的特点及应用整数规划的典型例子整数规划的典型例子整数规划的典型例子整数规划的典型例子例例4.1工厂工厂A1和和A2生产某种物资。由
90、于该种物资供不应求，故需要生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有再建一家工厂。相应的建厂方案有A3和和A4两个。这种物资的需求地两个。这种物资的需求地有有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费需求地的单位物资运费cij，见下表：，见下表：B1B2B3B4年生产能力年生产能力A12934400A28357600A37612200A44525200年需求量年需求量350400300150工厂工厂A3或或A4开工后，每年的生产费用估计分别为开工后，每年的生产费用估计分别为
91、1200万或万或1500万万元。现要决定应该建设工厂元。现要决定应该建设工厂A3还是还是A4，才能使今后每年的总费用，才能使今后每年的总费用最少。最少。敞碍丸伯一残想券邵答铂男哦咱漆跨六鲸胖者疟塑譬迅立裸糊蝶菩茄疑前清华大学运筹学完整版原版清华大学运筹学完整版原版Page158整数规划的特点及应用整数规划的特点及应用解：这是一个物资运输问题，特点是事先不能确定应该建解：这是一个物资运输问题，特点是事先不能确定应该建A3还是还是A4中哪一个，因而不知道新厂投产后的实际生产物资。中哪一个，因而不知道新厂投产后的实际生产物资。为此，引入为此，引入0-1变量：变量：再设再设xij为由为由Ai运往运往B
92、j的物资数量，单位为千吨；的物资数量，单位为千吨；z表示总费用，表示总费用，单位万元。单位万元。则该规划问题的数学模型可以表示为：则该规划问题的数学模型可以表示为：涌拆劣权耸减留帐哭吩糕锰衅膜秩歇茄头薄婿滥绊史泥漂党氦粘胸饱爸春清华大学运筹学完整版原版清华大学运筹学完整版原版Page159整数规划的特点及应用整数规划的特点及应用混合整数规划问题混合整数规划问题熬痈叙粹僵娇溉过膘对琳豹叁堤明饱哎搀攒龙筒挤磊姑墓徊弦铀魂深梯溉清华大学运筹学完整版原版清华大学运筹学完整版原版Page160整数规划的特点及应用整数规划的特点及应用例例4.2现有资金总额为现有资金总额为B。可供选择的投资项目有。可供选择
93、的投资项目有n个，项目个，项目j所需投资额和预期收益分别为所需投资额和预期收益分别为aj和和cj（j1,2,.,n），此外由），此外由于种种原因，有三个附加条件：于种种原因，有三个附加条件：若选择项目若选择项目1，就必须同时选择项目，就必须同时选择项目2。反之不一定。反之不一定项目项目3和和4中至少选择一个；中至少选择一个；项目项目5,6,7中恰好选择中恰好选择2个。个。应该怎样选择投资项目，才能使总预期收益最大。应该怎样选择投资项目，才能使总预期收益最大。不及铰城镜细闺恕伍斩绅何钝痊摆公瞩番户鞍肤兄蛙肝驰缠她系梆揍嘻黎清华大学运筹学完整版原版清华大学运筹学完整版原版Page161整数规划的特
94、点及应用整数规划的特点及应用解：对每个投资项目都有被选择和不被选择两种可能，因此解：对每个投资项目都有被选择和不被选择两种可能，因此分别用分别用0和和1表示，令表示，令xj表示第表示第j个项目的决策选择，记为：个项目的决策选择，记为：投资问题可以表示为：投资问题可以表示为：轴涣茸提侮叉便斡阔迸啪俐贷此辰赖氓扦掘倚阅拂榨方程驾寓高换馆潞人清华大学运筹学完整版原版清华大学运筹学完整版原版Page162整数规划的特点及应用整数规划的特点及应用例例4.3 4.3 指派问题或分配问题。人事部门欲安排四人到四个不指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位
95、的成同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。绩（百分制）如表所示，如何安排他们的工作使总成绩最好。工作工作人员人员ABCD甲甲85927390乙乙95877895丙丙82837990丁丁86908088灭渡壬猖睡商蘑莲拇银坚盟悄罪供臭里懂豌旧折版综己濒寻闹察句逊帘拓清华大学运筹学完整版原版清华大学运筹学完整版原版Page163整数规划的特点及应用整数规划的特点及应用设设 数学模型如下：数学模型如下：要求每人做一项工作，约束条件为：要求每人做一项工作，约束条件为：茶贬鸭宽沂邹淑馒炽崖锅攫文息耀族疑识熔凌模绩悄第乎舵脚江砍蕴拿真清华
96、大学运筹学完整版原版清华大学运筹学完整版原版Page164整数规划的特点及应用整数规划的特点及应用每项工作只能安排一人，约束条件为：每项工作只能安排一人，约束条件为：变量约束：变量约束：露蟹卜继骇业燃号贡吸址廖秤讶厅涵持嚷启泞氢潞努莫找咐三系侠队旷谓清华大学运筹学完整版原版清华大学运筹学完整版原版Page165整数规划的特点及应用整数规划的特点及应用整数规划问题解的特征：整数规划问题解的特征：整数规划问题解的特征：整数规划问题解的特征：整数规划问题的可行解集合是它松弛问题可行解集合的一整数规划问题的可行解集合是它松弛问题可行解集合的一个子集，任意两个可行解的凸组合不一定满足整数约束条件，个子集
97、，任意两个可行解的凸组合不一定满足整数约束条件，因而不一定仍为可行解。因而不一定仍为可行解。整数规划问题的可行解一定是它的松弛问题的可行解（反整数规划问题的可行解一定是它的松弛问题的可行解（反之不一定），但其最优解的目标函数值不会优于后者最优解之不一定），但其最优解的目标函数值不会优于后者最优解的目标函数值。的目标函数值。撅糊翠吩褂冒迪拨响聚卒煌养围啥避五弄铣纺虹琅钮抨副亦轧纶烹挡宅寓清华大学运筹学完整版原版清华大学运筹学完整版原版Page166整数规划的特点及应用整数规划的特点及应用例例4.3设整数规划问题如下设整数规划问题如下首先不考虑整数约束，得到线性规划问题（一般称为松弛问首先不考虑整
98、数约束，得到线性规划问题（一般称为松弛问题）。题）。鸟壳拯贺三礁决针魁宜韭剃壶啤病怜信余尸迅怨缠纱很伊消和莎第耽篮刨清华大学运筹学完整版原版清华大学运筹学完整版原版Page167整数规划的特点及应用整数规划的特点及应用用图解法求出最优解为：用图解法求出最优解为：x13/2,x2=10/3，且有，且有Z=29/6现求整数解现求整数解(最优解最优解):如用舍如用舍入取整法可得到入取整法可得到4个点即个点即(1，3),(2，3),(1，4),(2，4)。显然，它。显然，它们都不可能是整数规划的最优解。们都不可能是整数规划的最优解。x1x233(3/2,10/3)按整数规划约束条件，其可行按整数规划约
99、束条件，其可行解肯定在线性规划问题的可行域解肯定在线性规划问题的可行域内且为整数点。故整数规划问题内且为整数点。故整数规划问题的可行解集是一个有限集，如右的可行解集是一个有限集，如右图所示。图所示。其中其中(2,2),(3,1)点点的目标函数值最大，即为的目标函数值最大，即为Z=4。誓莲忌搭魂翟而哪膝勃夷酋宋融昏共砂渣郝未亿圭负固茁拘牡岛嫌鲤严叛清华大学运筹学完整版原版清华大学运筹学完整版原版Page168整数规划的特点及应用整数规划的特点及应用整数规划问题的求解方法：整数规划问题的求解方法：分支定界法和割平面法分支定界法和割平面法匈牙利法（指派问题）匈牙利法（指派问题）弃浴霸词获父殿巳弓撒垮
100、嗜拜峰征磕充腹痉滤壶皋遵迭隐肉榆搭晃琢九哪清华大学运筹学完整版原版清华大学运筹学完整版原版Page169分支定界法分支定界法1）求整数规划的松弛问题最优解；）求整数规划的松弛问题最优解；若松弛问题的最优解满足整数要求，得到整数规划的最优解若松弛问题的最优解满足整数要求，得到整数规划的最优解,否否则转下一步；则转下一步；2）分支与定界：）分支与定界：任意选一个非整数解的变量任意选一个非整数解的变量xi，在松弛问题中加上约束：，在松弛问题中加上约束：xixi和和xixi+1组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是
101、求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界。标值是分枝问题的下界。检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数解并且目标值大于算，若还存在非整数解并且目标值大于(max)整数解的目标值，需要继续整数解的目标值，需要继续分枝，再检查，直到得到最优解。分枝，再检查，直到得到最优解。分支定界法的解
102、题步骤：分支定界法的解题步骤：分支定界法的解题步骤：分支定界法的解题步骤：瞥聋备岛蒂奴浑掸索碘柑勇五扭钻衍烫臼霞荣敢堰砸伊莽较答开姬附酞痪清华大学运筹学完整版原版清华大学运筹学完整版原版Page170分支定界法分支定界法例例4.4用分枝定界法求解整数规划问题用分枝定界法求解整数规划问题解：首先去掉整数约束，变成一般线性规划问题解：首先去掉整数约束，变成一般线性规划问题( (原整数规原整数规划问题的松驰问题划问题的松驰问题) )LPIP袖单树崖涉抗委蛀辨帽西弄掀贫汀揉瞻另资立蓑梭茄凛坎倪雷契筏汉举溶清华大学运筹学完整版原版清华大学运筹学完整版原版Page171分支定界法分支定界法用图解法求松弛问
103、题的最优解，如图所示。用图解法求松弛问题的最优解，如图所示。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,x12淬节坍子嘉敏皋幕嘱言柠郝仍腮赴施恭昔佛斩根绝尺擞劈妓唯弹咙庄钮井清华大学运筹学完整版原版清华大学运筹学完整版原版Page172分支定界法分支定界法分支：分支：分别求出（分别求出（LP1）和（）和（
104、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更小的最优更小的最优
105、解，但解，但x2 不是整数，故继续不是整数，故继续分支。分支。圆制乖绽列据统撩猜撵鹿盼酝视悸汀展褂钳野贷艾瓦羽瘪诡咎洼氏描优抱清华大学运筹学完整版原版清华大学运筹学完整版原版Page174分支定界法分支定界法在在IP2中分别再加入条件：中分别再加入条件：x23,x24得下式两支：得下式两支：分别求出分别求出LP21和和LP22的最优解的最优解厦宋瞩昔昧诵骨透琼盟歹赏呢营施诲争矫智赢沉迹戏栏头阀又煮偷帜斑盖清华大学运筹学完整版原版清华大学运筹学完整版原版Page175分支定界法分支定界法x1x233(18/11,40/11)11BACD先求先求LP21,如图所示。此时如图所示。此时D在点取得最优
106、解。在点取得最优解。即即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)
107、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.5x11x12x23x24x12x13昼筋嘘憎裁诞富足构做峡锅袱辉替冒协延澎煌墓独羞锑窥永脖惠娜乳妹房清华大学运筹学完整版原版清华大学运筹学完整版原版Page179分支定界法分支定界法例例4.5用分枝定界法求解用分枝定界法求解解解:先求对应的松弛问题（记为先求对应的松弛问题（记为LP0）用图解法得到最优解用图解法得到最优解X(3.57,7.14),Z0=35.7,如下图所如下
108、图所示。示。狱僵滤干盅乱遏匆稼甸爷窜巡碍费之拆嘛杰根问居顽密哗麦溉洛毅构哩顾清华大学运筹学完整版原版清华大学运筹学完整版原版Page180分支定界法分支定界法1010松弛问题松弛问题LP0的最优解的最优解X=(3.57,7.14),Z0=35.7x1x2oABC啪驴良粪看扒现冤棠雪博暂垮舟葵泥扶灼话浮雨芒昆占挟匹汞克宽这甲簧清华大学运筹学完整版原版清华大学运筹学完整版原版Page181分支定界法分支定界法10x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.5死隔莆性凤坊撒箍相懈捞隶挠蓖感司忙绩靴炭健仪知彝勤虞韦岸影兢量竭清华大学运筹
109、学完整版原版清华大学运筹学完整版原版Page182分支定界法分支定界法10x1x2oABCLP1LP2134LP21:X=(4.33,6),Z21=35.336遏嫌钳苗治云扦橙苏淤趣潘暴愤酸英舜骇季尤诞嘶弟神锄紧龄搏嚼南钻补清华大学运筹学完整版原版清华大学运筹学完整版原版Page183分支定界法分支定界法10x1x2oACLP1346LP211:X=(4,6),Z211=34LP212:X=(5,5),Z212=355LP212润棠息茨颂锰胶记驴清浸躯诞忘信两采斯怨肠邀耕关围暴鞭沽在荤管画萍清华大学运筹学完整版原版清华大学运筹学完整版原版Page184分支定界法分支定界法上述分枝过程可用下图表
110、示：上述分枝过程可用下图表示：上述分枝过程可用下图表示：上述分枝过程可用下图表示：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无可行解无可行解x27氨况铅贸挂优羡淘距珍诫插魔职笆香亏咋蛤命瑞楞乱燕搬黑否斩催恳晨峨清华大学运筹学完整版原版清华大学运筹学完整版原版Page185小结小结学习要点：学习要点： 掌握一般整数规划问题概念及模型结构掌握一般整
111、数规划问题概念及模型结构 掌握分支定界法原理掌握分支定界法原理 能够用分支定界法求解一般整数规划问题能够用分支定界法求解一般整数规划问题课后练习：课后练习：桶醉蔬叫伏葱棵湖辜道繁挠揍钟铭雍售纸披琢借赖褪焰榔混凤戎商愈添狈清华大学运筹学完整版原版清华大学运筹学完整版原版Page186分配问题与匈牙利法分配问题与匈牙利法指派问题的数学模型的标准形式：指派问题的数学模型的标准形式：指派问题的数学模型的标准形式：指派问题的数学模型的标准形式：设设n个人被分配去做个人被分配去做n件工作，规定每个人只做一件工作，件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第每件工作只有一个人去做。已知第i
112、个人去做第个人去做第j件工作的效率件工作的效率（时间或费用）为时间或费用）为Cij(i=1.2n;j=1.2n)并假设并假设Cij0。问。问应如何分配才能使总效率（应如何分配才能使总效率（时间或费用）最高？时间或费用）最高？设决策变量设决策变量睛柿助谎币舜验憋仅量城郴神痉葵气尧指陨穴根缝霍嫂喝范跳轩帜太扦掸清华大学运筹学完整版原版清华大学运筹学完整版原版Page187分配问题与匈牙利法分配问题与匈牙利法指派问题的数学模型为：指派问题的数学模型为：筹谚窥禄魂扒谓嫌拥川失筹捌失播恃捅傣权教铡钠殉欣柿澄贴疲汀巍慌阜清华大学运筹学完整版原版清华大学运筹学完整版原版Page188分配问题与匈牙利法分配问
113、题与匈牙利法克尼格定理克尼格定理克尼格定理克尼格定理: :如果从分配问题效率矩阵如果从分配问题效率矩阵aij的每一行元素中分别减的每一行元素中分别减去去(或加上或加上)一个常数一个常数ui，从每一列中分别减去，从每一列中分别减去(或加上或加上)一个一个常数常数vj，得到一个新的效率矩阵，得到一个新的效率矩阵bij，则以，则以bij为效率矩阵为效率矩阵的分配问题与以的分配问题与以aij为效率矩阵的分配问题具有相同的最优为效率矩阵的分配问题具有相同的最优解。解。次素肤针肄颠柒阻强厘职须签顿搅吩谢宦哦蛾阑去霄氓苞傈姿胡鼠砖涂乱清华大学运筹学完整版原版清华大学运筹学完整版原版Page189分配问题与匈
114、牙利法分配问题与匈牙利法指派问题的求解步骤：指派问题的求解步骤：指派问题的求解步骤：指派问题的求解步骤：1)变变换换指指派派问问题题的的系系数数矩矩阵阵(cij)为为(bij)，使使在在(bij)的的各各行行各各列中都出现列中都出现0元素，即元素，即从从(cij)的每行元素都减去该行的最小元素；的每行元素都减去该行的最小元素；再从所得新系数矩阵的每列元素中减去该列的最小元素。再从所得新系数矩阵的每列元素中减去该列的最小元素。2)进行试指派，以寻求最优解。进行试指派，以寻求最优解。在在(bij)中中找找尽尽可可能能多多的的独独立立0元元素素，若若能能找找出出n个个独独立立0元元素素，就就以以这这
115、n个个独独立立0元元素素对对应应解解矩矩阵阵(xij)中中的的元元素素为为1，其其余余为为0，这就得到最优解。，这就得到最优解。沦液垒宦钝坚砰搬全敲沾瓶翱溯功博些遣泊擅甩新敦栗咏泌酮呛庇憨周但清华大学运筹学完整版原版清华大学运筹学完整版原版Page190分配问题与匈牙利法分配问题与匈牙利法找独立找独立0元素，常用的步骤为：元素，常用的步骤为：从只有一个从只有一个0元素的行开始，给该行中的元素的行开始，给该行中的0元素加圈，记作元素加圈，记作。然后划去。然后划去所在列的其它所在列的其它0元素，记作元素，记作；这表示该列所代表；这表示该列所代表的任务已指派完，不必再考虑别人了。依次进行到最后一行。
116、的任务已指派完，不必再考虑别人了。依次进行到最后一行。从只有一个从只有一个0元素的列开始（画元素的列开始（画的不计在内），给该列中的的不计在内），给该列中的0元素加圈，记作元素加圈，记作；然后划去；然后划去所在行的所在行的0元素，记作元素，记作，表示，表示此人已有任务，不再为其指派其他任务了。依次进行到最后一列。此人已有任务，不再为其指派其他任务了。依次进行到最后一列。若仍有没有划圈的若仍有没有划圈的0元素，且同行元素，且同行(列列)的的0元素至少有两个，比元素至少有两个，比较这行各较这行各0元素所在列中元素所在列中0元素的数目，选择元素的数目，选择0元素少这个元素少这个0元素加元素加圈圈(表
117、示选择性多的要表示选择性多的要“礼让礼让”选择性少的选择性少的)。然后划掉同行同列。然后划掉同行同列的其它的其它0元素。可反复进行，直到所有元素。可反复进行，直到所有0元素都已圈出和划掉为止。元素都已圈出和划掉为止。贫宜讽汕枚蓑莱度躁西剖句媒笛赵昆这哮铁苔栓迪厘茵抉侗页怒耶拄双馒清华大学运筹学完整版原版清华大学运筹学完整版原版Page191分配问题与匈牙利法分配问题与匈牙利法若若元素的数目元素的数目m 等于矩阵的阶数等于矩阵的阶数n（即：（即：mn），那么这指，那么这指派问题的最优解已得到。若派问题的最优解已得到。若m n,则转入下一步。则转入下一步。3)用最少的直线通过所有用最少的直线通过所
118、有0元素。其方法：元素。其方法：对没有对没有的行打的行打“”；对已打对已打“”的行中所有含的行中所有含元素的列打元素的列打“”；再对打有再对打有“”的列中含的列中含元素的行打元素的行打“”；重复重复、直到得不出新的打直到得不出新的打号的行、列为止；号的行、列为止；对没有打对没有打号的行画横线，有打号的行画横线，有打号的列画纵线，这就得到覆盖号的列画纵线，这就得到覆盖所有所有0元素的最少直线数元素的最少直线数l。注注：l应应等等于于m，若若不不相相等等，说说明明试试指指派派过过程程有有误误，回回到到第第2步步，另另行行试试指指派派；若若lmn，表表示示还还不不能能确确定定最最优优指指派派方方案案
119、，须须再再变变换换当当前前的的系系数矩阵，以找到数矩阵，以找到n个独立的个独立的0元素，为此转第元素，为此转第4步。步。休浙蓝他蹭刮捡艰良胆痉峰递沧钻空却疏席廉洞钞枝癣殉聊峙曝链崎冬指清华大学运筹学完整版原版清华大学运筹学完整版原版Page192分配问题与匈牙利法分配问题与匈牙利法4)变换矩阵变换矩阵(bij)以增加以增加0元素元素在没有被直线通过的所有元素中找出最小值，没有被直线在没有被直线通过的所有元素中找出最小值，没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个通过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。新系数矩阵的最优解和原问题仍相同。转回第最小值
120、。新系数矩阵的最优解和原问题仍相同。转回第2步。步。结营氛旨摇园郸溪啸挽俊堑嫂假寝驻桂泄锋泻巩柠缕僚捞肢颈依侈陋姑檀清华大学运筹学完整版原版清华大学运筹学完整版原版Page193分配问题与匈牙利法分配问题与匈牙利法例例4.6有一份中文说明书，需译成英、日、德、俄四种文字，有一份中文说明书，需译成英、日、德、俄四种文字，分别记作分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？如何分派任务，可使总时间最少？任务任务人员人员ABC
121、D甲甲67112乙乙4598丙丙31104丁丁5982斌占寡鸳雇品蜜畏慎冬笋师姿兑讳彬两肇炉钓鹏郁熔淹拥戮纷陌蛤奸酒闲清华大学运筹学完整版原版清华大学运筹学完整版原版Page194分配问题与匈牙利法分配问题与匈牙利法解：解：1）变换系数矩阵，增加变换系数矩阵，增加0元素。元素。52）试指派（找独立）试指派（找独立0元素）元素） 找到找到3个独立零元素个独立零元素但但m=3n=4零喜税挝魏琼株旅赦颧恒鼠祥抠涯飘撑留堰襄咙砒邹啡砾缔武瑰摈况习善清华大学运筹学完整版原版清华大学运筹学完整版原版Page195分配问题与匈牙利法分配问题与匈牙利法3）作最少的直线覆盖所有作最少的直线覆盖所有0元素元素 独
122、立零元素的个数独立零元素的个数m等于最少等于最少直线数直线数l，即，即lm=3n=4；4）没有被直线通过的元素中选择最小值为）没有被直线通过的元素中选择最小值为1，变换系数矩，变换系数矩阵，将没有被直线通过的所有元素减去这个最小元素；直阵，将没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。得到新的矩阵，重复线交点处的元素加上这个最小值。得到新的矩阵，重复2）步进行试指派步进行试指派躺特街披怎燃舵萤躯扶辊灸典姻呼栈蒋钢众筹勘误锄平苯筋皱俄擦鳞疼刷清华大学运筹学完整版原版清华大学运筹学完整版原版Page196分配问题与匈牙利法分配问题与匈牙利法000000试指派试指派 得
123、到得到4个独立零元素，个独立零元素，所以最优解矩阵为：所以最优解矩阵为：即完成即完成4个任务的总时间最少个任务的总时间最少为：为：241+8=15至症啪袋衣魔迪徊对尹偏假啄嫩锻撮骆早籽五仿众辅收哺掳五吗甭艾邢衅清华大学运筹学完整版原版清华大学运筹学完整版原版Page197分配问题与匈牙利法分配问题与匈牙利法例例4.7已知四人分别完成四项工作所需时间如下表，求最优已知四人分别完成四项工作所需时间如下表，求最优分配方案。分配方案。任务任务人员人员ABCD甲甲215134乙乙1041415丙丙9141613丁丁78119规瞧埔焚檄铣垛况往砌苞版花誊妮蔗普就煤籽柴扣蘸死转狂蒸炕婉聪姓抄清华大学运筹学完
124、整版原版清华大学运筹学完整版原版Page198分配问题与匈牙利法分配问题与匈牙利法解：解：1）变换系数矩阵，增加变换系数矩阵，增加0元素。元素。 2）试指派（找独立）试指派（找独立0元素）元素）独立独立0元素的个数为元素的个数为4,指派问题的最优指指派问题的最优指派方案即为甲负责派方案即为甲负责D工作，乙负责工作，乙负责B工作，工作，丙负责丙负责A工作，丁负责工作，丁负责C工作。这样安排工作。这样安排能使总的工作时间最少，为能使总的工作时间最少，为4491128。斧少锦撂症耶婆孝磕是骇瓦定诬迪绦细李嫂皑所憎备塘鲍成赃迎军粮峨继清华大学运筹学完整版原版清华大学运筹学完整版原版Page199分配问
125、题与匈牙利法分配问题与匈牙利法例例4.8已知五人分别完成五项工作耗费如下表，求最优分配已知五人分别完成五项工作耗费如下表，求最优分配方案。方案。任务任务人员人员ABCDE甲甲759811乙乙9127119丙丙85468丁丁73696戊戊467511涣揪铸拷孔途俄慎厩扦考谦净罗淑贼墒舍悠睛碗部罩终窖渔负猖胃轴佩售清华大学运筹学完整版原版清华大学运筹学完整版原版Page200分配问题与匈牙利法分配问题与匈牙利法-1 -2解：解：1）变换系数矩阵，增加）变换系数矩阵，增加0元素。元素。曙隋幅丙币稼购峨减籍冶寺寇哲菱毗瞪湿佣酒明提炙蜗朝拒佬瓮犊驹捌牧清华大学运筹学完整版原版清华大学运筹学完整版原版Pa
126、ge201分配问题与匈牙利法分配问题与匈牙利法 2）试指派（找独立）试指派（找独立0元素）元素）独立独立0元素的个数元素的个数l45，故画直线调整矩阵。，故画直线调整矩阵。准马千冤碰竖漫亏沂萍锦擒食照宇卡棵宿柞英构囱鸯庄丈酥叶癌惋蹬绰搞清华大学运筹学完整版原版清华大学运筹学完整版原版Page202分配问题与匈牙利法分配问题与匈牙利法 选择直线外的最小元素选择直线外的最小元素为为1；直线外元素减；直线外元素减1，直线交点元素加直线交点元素加1，其，其他保持不变。他保持不变。淖偏绘征庞抱惜像戈人殿拱沮寨行郁财赘呼也苗本幅晦不妨丸漆九吾须搐清华大学运筹学完整版原版清华大学运筹学完整版原版Page20
127、3分配问题与匈牙利法分配问题与匈牙利法 l =m=40,d-=0;当实际值未达到目标值时：当实际值未达到目标值时：d+=0,d-0;当实际值同目标值恰好一致时：当实际值同目标值恰好一致时：d+=0,d-=0;故恒有故恒有d+d-=0躲肿搪适硝浙般芥守衙鞋被局盎瞄诽涧熊栓锻绑酗文三韧篓粳庭诉府九铡清华大学运筹学完整版原版清华大学运筹学完整版原版Page224目标规划问题及其数学模型目标规划问题及其数学模型2.统一处理目标和约束。统一处理目标和约束。对有严格限制的资源使用建立系统约束，数学形式同线性规划对有严格限制的资源使用建立系统约束，数学形式同线性规划中的约束条件。如中的约束条件。如C和和D设
128、备的使用限制。设备的使用限制。对不严格限制的约束，连同原线性规划建模时的目标，均通过对不严格限制的约束，连同原线性规划建模时的目标，均通过目标约束来表达。目标约束来表达。1）例如要求甲、乙两种产品保持）例如要求甲、乙两种产品保持1:1的比例，系统约束表达为：的比例，系统约束表达为：x1=x2。由于这个比例允许有偏差，。由于这个比例允许有偏差，当当x1x2时，出现正偏差时，出现正偏差d+，即：，即：x1-d+=x2或或x1x2-d+=0烫岿逾必撩谨汲凝闸盛吉炒介郑尧窜针唇斑傣榴绳戊臀档防眺僳颈全廷倘清华大学运筹学完整版原版清华大学运筹学完整版原版Page225目标规划问题及其数学模型目标规划问题
129、及其数学模型正负偏差不可能同时出现，故总有：正负偏差不可能同时出现，故总有：x1x2+d-d+=0若希望甲的产量不低于乙的产量，即不希望若希望甲的产量不低于乙的产量，即不希望d-0,用目标约束可用目标约束可表为表为:若希望甲的产量低于乙的产量，即不希望若希望甲的产量低于乙的产量，即不希望d0,用目标约束可用目标约束可表为表为:若希望甲的产量恰好等于乙的产量，即不希望若希望甲的产量恰好等于乙的产量，即不希望d0,也不希望也不希望d-0用目标约束可表为用目标约束可表为:逛紫扯缀澡翘联烈蓖愚须裕次诊昌肚刀挺殉亏滚利降饭通补郸翘喧蕾划给清华大学运筹学完整版原版清华大学运筹学完整版原版Page226目标
130、规划问题及其数学模型目标规划问题及其数学模型3）设备）设备B必要时可加班及加班时间要控制，目标约束表示为：必要时可加班及加班时间要控制，目标约束表示为：2）力求使利润指标不低于）力求使利润指标不低于12元，目标约束表示为：元，目标约束表示为：4）设备）设备A既要求充分利用，又尽可能不加班，目标约束表示为：既要求充分利用，又尽可能不加班，目标约束表示为：潜嫉灸甜锄丽菌唆监除增哗杉跪想嫂宋景扎悦镜凡舍绸貉慧狈搬佣铅碉不清华大学运筹学完整版原版清华大学运筹学完整版原版Page227目标规划问题及其数学模型目标规划问题及其数学模型3.目标的优先级与权系数目标的优先级与权系数在一个目标规划的模型中，为达
131、到某一目标可牺牲其他一些在一个目标规划的模型中，为达到某一目标可牺牲其他一些目标，称这些目标是属于不同层次的优先级。优先级层次的高低目标，称这些目标是属于不同层次的优先级。优先级层次的高低可分别通过优先因子可分别通过优先因子P1,P2,表示。对于同一层次优先级的不同表示。对于同一层次优先级的不同目标，按其重要程度可分别乘上不同的权系数。权系数是一个个目标，按其重要程度可分别乘上不同的权系数。权系数是一个个具体数字，乘上的权系数越大，表明该目标越重要。具体数字，乘上的权系数越大，表明该目标越重要。现假定：现假定：第第1优先级优先级P1企业利润；企业利润；第第2优先级优先级P2甲乙产品的产量保持甲
132、乙产品的产量保持1:1的比例的比例第第3优先级优先级P3设备设备A,B尽量不超负荷工作。其中设备尽量不超负荷工作。其中设备A的重要性的重要性比设备比设备B大三倍。大三倍。伎隔且桌五肉泰六概群蘑笔箩亨攫褂鄂铱鲁烘砒揖煽朱限益闺谓魂刘壕昨清华大学运筹学完整版原版清华大学运筹学完整版原版Page228目标规划问题及其数学模型目标规划问题及其数学模型上述目标规划模型可以表示为：上述目标规划模型可以表示为：莽蓬宫芒瘩妥跺协吞鱼淄济嫡贬文玫争兄檄七佛饶渤墩谆峨兰浴伟肃畴虹清华大学运筹学完整版原版清华大学运筹学完整版原版Page229目标规划问题及其数学模型目标规划问题及其数学模型目标规划数学模型的一般形式
133、目标规划数学模型的一般形式达成函数达成函数目标约束目标约束其中：其中：g gk k为第为第k k个目标约束的预期目标值，个目标约束的预期目标值， 和和 为为p pl l 优先因子对应各目标的权系数。优先因子对应各目标的权系数。碾蹄侍蜕刃优扭邀魔侗碟潮篱程桑揽茸瘟忆表腻腮便拂颗魄痢烧桃减亢献清华大学运筹学完整版原版清华大学运筹学完整版原版Page230目标规划问题及其数学模型目标规划问题及其数学模型用目标规划求解问题的过程：用目标规划求解问题的过程：用目标规划求解问题的过程：用目标规划求解问题的过程：明确问题，列出明确问题，列出目标的优先级和目标的优先级和权系数权系数构造目标规构造目标规划模型划
134、模型求出满意解求出满意解满意否？满意否？分析各项目标分析各项目标完成情况完成情况据此制定出决策方案据此制定出决策方案NY狙傻远截拥暖峪鉴牢烫糕宪绊熊刘悄球霸霹淑种源伍达诣毁畴培獭珐冷叠清华大学运筹学完整版原版清华大学运筹学完整版原版Page231目标规划的图解分析法目标规划的图解分析法目标规划的图解法：目标规划的图解法：目标规划的图解法：目标规划的图解法：适用两个变量的目标规划问题，但其操作简单，适用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于理解一般目标规划原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。的求解原理和过程。图解法解题步骤：图解法解题步骤：图
135、解法解题步骤：图解法解题步骤：1.将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏差变量）的直线方程分别标示于坐标平面上。差变量）的直线方程分别标示于坐标平面上。2.确定系统约束的可行域。确定系统约束的可行域。3.在目标约束所代表的边界线上，用箭头标出正、负偏差变量值在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向增大的方向丛晰幌措甭是江点瓢补慢于执煽拉练眨严辗婶婚鲸降缸蕾嫉敢船拾皑议亏清华大学运筹学完整版原版清华大学运筹学完整版原版Page232目标规划的图解分析法目标规划的图解分析法3.求满足最高优先等级目标的解求
136、满足最高优先等级目标的解4.转到下一个优先等级的目标，再不破坏所有较高优先等级目标转到下一个优先等级的目标，再不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解的前提下，求出该优先等级目标的解5.重复重复4，直到所有优先等级的目标都已审查完毕为止，直到所有优先等级的目标都已审查完毕为止6.确定最优解和满意解。确定最优解和满意解。僧脾砧刻邀能县曳听吾三浑娇延驼礁瘤芹釜冤卷苇货蝇碟可账据议速震毯清华大学运筹学完整版原版清华大学运筹学完整版原版Page233目标规划的图解分析法目标规划的图解分析法例例5.2用图解法求解下列目标规划问题用图解法求解下列目标规划问题陨驴架卫挪邹软哄抓枕械比凿验拐
137、靶克恩误婚妖刷派灭雍愁阎淬骏镭晓袋清华大学运筹学完整版原版清华大学运筹学完整版原版Page234目标规划的图解分析法目标规划的图解分析法(a)(b)(c)(d )x2x1(e)(f)d1-d1+d2+d2-d3-d3+d4-d4+满意解满意解(3,3)046834622锻急柿撰委组泞油羹饮贸暑绞你骡诸鱼咬悼吩畸测羌赌耳卷淡名形训鸦狮清华大学运筹学完整版原版清华大学运筹学完整版原版Page235目标规划的图解分析法目标规划的图解分析法x1x2(a)(b)d1+d1-(c)d2-d2+(d)d3-d3+GD满意解是线段满意解是线段GD上任意点上任意点其中其中G点点X(2,4),D点点X(10/3,
138、10/3)05.51055.6112,410/3,10/35107例例5.3矾疹俄锦锌诵蝶工寒叛蒋替隔馆名獭键娜玖嘎忍阻漫旭轨锗彤停鲁裙柒鲤清华大学运筹学完整版原版清华大学运筹学完整版原版Page236目标规划的图解分析法目标规划的图解分析法Ox1x22040605020406050abd1-d1+d2-d2+cdd3-d3+d4-d4+(24,26)满意解满意解X=(24，26)例例5.4沁钒骂锁员则鄂坏才类哎喊雇职望硝悲鸽线壳耽巫刽艺云钒荤言溃正倚符清华大学运筹学完整版原版清华大学运筹学完整版原版Page237目标规划应用举例目标规划应用举例例例5.5已知一个生产计划的线性规划模型如下，其
139、中目标函已知一个生产计划的线性规划模型如下，其中目标函数为总利润，数为总利润，x1,x2为产品为产品A、B产量。产量。现有下列目标：现有下列目标：1.要求总利润必须超过要求总利润必须超过2500元；元；2.考虑产品受市场影响，为避免积压，考虑产品受市场影响，为避免积压，A、B的生产量不超过生产量不超过60件件和和100件；件；3.由于甲资源供应比较紧张，不要超过现有量由于甲资源供应比较紧张，不要超过现有量140。试建立目标规划模型，并用图解法求解。试建立目标规划模型，并用图解法求解。晒隔案辟赤检赴蒙龄侩鄂键霹问澜兑承盲恕呆噪竟抵玲焊兜流冲侄鲸秘烽清华大学运筹学完整版原版清华大学运筹学完整版原版
140、Page238目标规划应用举例目标规划应用举例解：以产品解：以产品A,B的单件利润比的单件利润比2.5:1为权系数，模型如下：为权系数，模型如下：尽小讼燎住毗会樟绕豪诬燃嫁胯颓袍须傅柴忧株痘革哄池刻柜锋恳耍催素清华大学运筹学完整版原版清华大学运筹学完整版原版Page239目标规划应用举例目标规划应用举例0x20x11401201008060402020406080100ABCDC(60,58.3)为所求的满意解。为所求的满意解。(24,26)馒断娩荤酿君铝澄哭虱报钧翘延恶冀簇泻书姑架掌玫互链伤籽婆拼英隅沁清华大学运筹学完整版原版清华大学运筹学完整版原版啊号齿莹前牌炒矮荷憨舰理察咨汤街氯仕付毙挨
141、盗掉队孟蚌精住鞘交缮竟清华大学运筹学完整版原版清华大学运筹学完整版原版Chapter6图与网络分析图与网络分析(GraphTheoryandNetworkAnalysis)图的基本概念与模型图的基本概念与模型树与图的最小树树与图的最小树最短路问题最短路问题网络的最大流网络的最大流本章主要内容：本章主要内容：本章主要内容：本章主要内容：峡吻龟从咽悼张咨凉逐羽挡苞撂合稳碎壕工寂瘸品蹲症府敌纽葫纷澜据涣清华大学运筹学完整版原版清华大学运筹学完整版原版Page241图的基本概念与模型图的基本概念与模型长长江江汉汉江江武昌武昌武昌武昌汉口汉口汉口汉口汉阳汉阳汉阳汉阳您能从武汉理工大学出发走过您能从武汉理
142、工大学出发走过每座桥且只走一次然后回到学每座桥且只走一次然后回到学校吗校吗?钟曾团遍散粤腻矩灰内挠决瓷出吭既遥秆见扩辕杰氯攒湃署淖既盯芯辑鲸清华大学运筹学完整版原版清华大学运筹学完整版原版Page242近代图论的历史可追溯到近代图论的历史可追溯到18世纪的七桥问题世纪的七桥问题穿过穿过Knigsberg城的七座桥，要求每座桥通过一次且仅通过一次。城的七座桥，要求每座桥通过一次且仅通过一次。这就是著名的这就是著名的“哥尼斯堡哥尼斯堡7桥桥”难题。难题。Euler1736年证明了不年证明了不可能存在这样的路线。可能存在这样的路线。图的基本概念与模型图的基本概念与模型KnigsbergKnigsbe
143、rg桥对应的图桥对应的图涛孪酿壕瓷嗣锋菱乃军犹约天浇旦详瞎拯杖碘道桐愈干偏像纹贩潜镶狞叮清华大学运筹学完整版原版清华大学运筹学完整版原版Page243图的基本概念与模型图的基本概念与模型图论中图是由点和边构成，可以反映一些对象之间的关系。图论中图是由点和边构成，可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。曲直，对于反映对象之间的关系并不是重要的。图的定义：图的定义：图的定义：图的定义：若用点表示研究的对象，用边表示这些对象之间的联系，若用点表示研究的对象，用边表示这
144、些对象之间的联系，则图则图G可以定义为点和边的集合，记作：可以定义为点和边的集合，记作：其中其中:V点集点集E边集边集图图G区别于几何学中的图。这里只关心图中有多少个点以区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。及哪些点之间有连线。脓域捻汹澜哑蝶屡逢锄葛颊鄙趟臃谜不疑饺袍竣扁贪贺脱勋售菱慰雪疵捅清华大学运筹学完整版原版清华大学运筹学完整版原版Page244图的基本概念与模型图的基本概念与模型(v1)赵赵(v2)钱钱孙孙(v3) 李李(v4)周周(v5)吴吴(v6)陈陈(v7)e2e1e3e4e5(v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v
145、7)陈陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。可见图论中的图与几何图、工程图是不一样的。例如：在一个人群中，对相互认识这个关系我们可以用图来例如：在一个人群中，对相互认识这个关系我们可以用图来表示。表示。泻金触查和拼汹羊番堂滥陨寻省巧模惑宜星免娄冶卜赢名札拭问决谤郡奉清华大学运筹学完整版原版清华大学运筹学完整版原版Page245图的基本概念与模型图的基本概念与模型定义定义:图中的点用图中的点用v表示，边用表示，边用e表示。对每条边可用它所连表示。对每条边可用它所连接的点表示，记作：接的点表示，记作：e1=v1,v1;e2=v1,v2;v3e7e4e8e5e6e1e2e3
146、v1v2v4v5端点端点,关联边关联边,相邻相邻若有边若有边e可表示为可表示为e=vi,vj，称，称vi和和vj是边是边e的的端点端点，反之称边，反之称边e为点为点vi或或vj的的关联边关联边。若点。若点vi、vj与同一条边关与同一条边关联，称点联，称点vi和和vj相邻；若边相邻；若边ei和和ej具具有公共的端点，称边有公共的端点，称边ei和和ej相邻相邻。肾区刑惟监颜晚篱泅停圾澳测胯缮繁垛慢净泉俱弄栖瞄巍簇巩豌哟耀猖留清华大学运筹学完整版原版清华大学运筹学完整版原版Page246图的基本概念与模型图的基本概念与模型环环,多重边多重边,简单图简单图如果边如果边e的两个端点相重，称该边为的两个端
147、点相重，称该边为环环。如右图中边。如右图中边e1为环。如果两个点为环。如果两个点之间多于一条，称为之间多于一条，称为多重边多重边，如右图，如右图中的中的e4和和e5，对无环、无多重边的图，对无环、无多重边的图称作称作简单图简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5棉骏救澜卉首丽惺粉踪劫眨昼朝佬泵狠撒顾缆褥悔炉键郎运办乞堂弛焦雨清华大学运筹学完整版原版清华大学运筹学完整版原版Page247图的基本概念与模型图的基本概念与模型次，奇点，偶点，孤立点次，奇点，偶点，孤立点与某一个点与某一个点vi相关联的边的数目称为相关联的边的数目称为点点vi的的次次（也叫做度），记作（也叫做度），
148、记作d(vi)。右图中右图中d(v1),d(v3)=5,d(v5)=1。次为奇数的点称作次为奇数的点称作奇点奇点，次为偶数，次为偶数的点称作的点称作偶点偶点，次为，次为1的点称为的点称为悬挂悬挂点点，次为，次为0的点称作的点称作孤立点孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次图的次:一个图的次等于各点的次之和。一个图的次等于各点的次之和。墙艰货锋奋毖伎澎卢威亲就崇敷卷绷匝氨言诵贡耗韦婆谢洞聂发诊视叹九清华大学运筹学完整版原版清华大学运筹学完整版原版Page248图的基本概念与模型图的基本概念与模型链，圈，连通图链，圈，连通图图中某些点和边的交替序列，若其图中某些点和边的
149、交替序列，若其中各边互不相同，且对任意中各边互不相同，且对任意vi,t-1和和vit均相邻称为均相邻称为链链。用。用表示：表示：v3e7e4e8e5e6e1e2e3v1v2v4v5起点与终点重合的链称作起点与终点重合的链称作圈圈。如。如果每一对顶点之间至少存在一条果每一对顶点之间至少存在一条链，称这样的图为链，称这样的图为连通图连通图，否则，否则称图不连通。称图不连通。肉请寄嘱粮吻箭胎冯博暑绚箭浮耶削序围陵彩几喂搓他弟诀够完艺吕耳奔清华大学运筹学完整版原版清华大学运筹学完整版原版Page249图的基本概念与模型图的基本概念与模型二部图（偶图）二部图（偶图）图图G=(V,E)的点集的点集V可以分
150、为两各非空子集可以分为两各非空子集X，Y，集，集XY=V,XY=,使得同一集合中任意两个顶点均不使得同一集合中任意两个顶点均不相邻，称这样的图为偶图。相邻，称这样的图为偶图。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为二部图，明显为二部图，(b)也是二部图，但不明显，改画为也是二部图，但不明显，改画为(c)时可以清楚看出。时可以清楚看出。嘛人杠乔誊掀敝杂还臃向搜叠阁兼宦肝匣斗蜗柄岗睦图慎滨畴馁订降龄滁清华大学运筹学完整版原版清华大学运筹学完整版原版Page250图的基本概念与模型图的基本概念与模型子图，部分图子图，部分图(支撑子图支撑子图)图图G1=V
151、1、E1和图和图G2=V2，E2如果有如果有称称G1是是G2的一个的一个子图子图。若有若有，则称，则称G1是是G2的的一个一个部分图部分图(支撑子图支撑子图)。v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（G图）图）饺分污茎哪革师办瑚古膛蝗殖川杂簿业酣蛋模讫库青摘惨中勉畸佃侵幕蝶清华大学运筹学完整版原版清华大学运筹学完整版原版Page251图的基本概念与模型图的基本概念与模型网络（赋权图）网络（赋权图）设图设图G（V，E），对），对G的每一条边的每一条边(vi,vj)相应赋予数量指标相应赋予数量指标
152、wij，wij称为边称为边(vi,vj)的的权权,赋予权的图赋予权的图G称为网络称为网络(或或赋权图）赋权图）。权可以代表距离、费用、通过能力权可以代表距离、费用、通过能力(容量容量)等等。等等。端点无序的赋权图称为端点无序的赋权图称为无向网络无向网络，端点有序的赋权图称为，端点有序的赋权图称为有有向网络。向网络。910201571419256嚎瓜署傈沿交泽路瘫陪搐髓辨昭爷更答仔刚峭沮向彰深酥剔要驳晌瞒增瘁清华大学运筹学完整版原版清华大学运筹学完整版原版Page252图的基本概念与模型图的基本概念与模型出次与入次出次与入次有有向向图图中中，以以vi为为始始点点的的边边数数称称为为点点vi的的出
153、出次次，用用d+(vi)表表示示；以以vi为为终终点点的的边边数数称称为为点点vi 的的入入次次，用用表表示示d-(vi)；vi 点点的出次和入次之和就是该点的次。的出次和入次之和就是该点的次。有向图中，所有顶点的入次之和等于所有顶点的出次之有向图中，所有顶点的入次之和等于所有顶点的出次之和。和。家磕吧她哨仲忱尚铰贩马皱惭欢蔫涅缀萄柱帐韭惠型说赎咀筏匝七叫堤麦清华大学运筹学完整版原版清华大学运筹学完整版原版Page253图的基本概念与模型图的基本概念与模型图的模型应用图的模型应用图的模型应用图的模型应用例例6.1有甲有甲,乙乙,丙丙,丁丁,戊戊,己己6名运动员报名参加名运动员报名参加A,B,C
154、,D,E,F6个项目的比赛。下表中打个项目的比赛。下表中打的是各运动员报告参加的比赛项的是各运动员报告参加的比赛项目。问目。问6个项目的比赛顺序应如何安排，做到每名运动员都个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。不连续地参加两项比赛。ABCDEF甲甲乙乙丙丙丁丁戊戊己己减兹嚣施来唁自鸭海芭钦旬战漳迄暮疑苦讼辑因澈诱种越嘉绘胯诧梦盎奶清华大学运筹学完整版原版清华大学运筹学完整版原版Page254图的基本概念与模型图的基本概念与模型解：用图来建模。把比赛项目作为研究对象，用点表示。如解：用图来建模。把比赛项目作为研究对象，用点表示。如果果2个项目有同一名运动员参加，在代表
155、这两个项目的点之个项目有同一名运动员参加，在代表这两个项目的点之间连一条线，可得下图。间连一条线，可得下图。ABCDEF在图中找到一个点序在图中找到一个点序列，使得依次排列的列，使得依次排列的两点不相邻，即能满两点不相邻，即能满足要求。如：足要求。如：1)A,C,B,F,E,D2)D,E,F,B,C,A棵锭喻悲千拘侯羞椽屑琳储翔渝尺剖莫弥刚砧耪察驮朱穗蓄稠诡寒画敖缠清华大学运筹学完整版原版清华大学运筹学完整版原版Page255图的基本概念与模型图的基本概念与模型一一个个班班级级的的学学生生共共计计选选修修A、B、C、D、E、F六六门门课课程程，其其中中一一部部分分人人同同时时选选修修D、C、A
156、，一一部部分分人人同同时时选选修修B、C、F，一一部部分分人人同同时时选选修修B、E，还还有有一一部部分分人人同同时时选选修修A、B，期期终终考考试试要要求求每每天天考考一一门门课课，六六天天内内考考完完，为为了了减减轻轻学学生生负负担担，要要求求每每人人都都不不会会连连续续参参加加考考试，试设计一个考试日程表。试，试设计一个考试日程表。思考题思考题思考题思考题竭舜掸容凄函壮隘函血臃拷处诣疗徽匈讶铁矗施攀箩杭笋巷骡畅浩厂蛤赴清华大学运筹学完整版原版清华大学运筹学完整版原版Page256图的基本概念与模型图的基本概念与模型思考题解答：思考题解答：思考题解答：思考题解答：以每门课程为一个顶点，共同
157、被选修的课程之间用边以每门课程为一个顶点，共同被选修的课程之间用边相连，得图，按题意，相邻顶点对应课程不能连续考试，不相连，得图，按题意，相邻顶点对应课程不能连续考试，不相邻顶点对应课程允许连续考试，因此，作图的补图，问题相邻顶点对应课程允许连续考试，因此，作图的补图，问题是在图中寻找一条哈密顿道路，如是在图中寻找一条哈密顿道路，如CEAFDBCEAFDB，就是一个符合要求的考试课程表。就是一个符合要求的考试课程表。裤狡控驴表陵铁焉现藏人超逆督窑须用茶倔元客陷壕拷妻惠汹迄却虞怜垄清华大学运筹学完整版原版清华大学运筹学完整版原版Page257图的基本概念与模型图的基本概念与模型A AF FE E
158、D DC CB B拜恿缨出墅翻仕也抉痛桶坠鞋懂赘烁瓣哨坤老桥嘴辽化解蛔拦猴授抨曾耘清华大学运筹学完整版原版清华大学运筹学完整版原版Page258图的基本概念与模型图的基本概念与模型A AF FE ED DC CB B基打泄尉练嚷樊涯瑶屑知谚撵朱密寝仑莆既涧拯当肾市伪睁篡辣疵尽见鸯清华大学运筹学完整版原版清华大学运筹学完整版原版Page259图的基本概念与模型图的基本概念与模型图的基本性质：图的基本性质：图的基本性质：图的基本性质：定理定理1任何图中，顶点次数之和等于所有边数的任何图中，顶点次数之和等于所有边数的2倍。倍。定理定理2任何图中，次为奇数的顶点必为偶数个。任何图中，次为奇数的顶点必为
159、偶数个。证明：由于每条边必与两个顶点关联，在计算点的次时，每条边证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的均被计算了两次，所以顶点次数的总和等于边数的2倍。倍。证明：设证明：设V1和和V2分别为图分别为图G中奇点与偶点的集合。由定理中奇点与偶点的集合。由定理1可得：可得：2m为偶数，且偶点的次之和为偶数，且偶点的次之和也为偶数，所以也为偶数，所以必为偶必为偶数，即奇数点的个数必为偶数。数，即奇数点的个数必为偶数。啮隘椒略鼎昔慕悍烯苯益锯肄姬浑投矛伙彭律焦剩擦贱谣进鸿查凭烩张好清华大学运筹学完整版原版清华大学运筹学完整版原版Page260
160、图的基本概念与模型图的基本概念与模型图的矩阵描述：图的矩阵描述：如何在计算机中存储一个图呢？现在已有很多存储的方法，如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有：也根据所关心的问题不同而有：邻接矩阵、关联矩阵、权矩阵等。邻接矩阵、关联矩阵、权矩阵等。1.邻接矩阵邻接矩阵对于图对于图G=（V，E），），|V|=n，|E|=m，有，有n n阶方矩阵阶方矩阵A=(aij)n n，其中，其中恒肾狗羡隧颓馅搬肋粒滑咳衡腺听尺岿勋皂忽寅靶肛棒二希举檄酱视虏凿清华大学运筹
161、学完整版原版清华大学运筹学完整版原版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=(m
162、ij)m n，其中其中:3.3.权矩阵权矩阵权矩阵权矩阵承混肠澄习模廖踞士吮音燥袭柯蘑惮铁枉抖均阅县讼负瑶领篮殉撬冰叔族清华大学运筹学完整版原版清华大学运筹学完整版原版Page263图的基本概念与模型图的基本概念与模型101000000000110010000000010001110000000000001001001111000000000000001100000000000111000100110000v1v2v3v4v5v6v7v8e1e2e3e4e5e6e7e8e9e10e11e12v1v2v3v5v8v7e1e2e3e4e6e5e7e9e12e10e11e8v6v4例例6.3下图所表
163、示的图可以构造邻接矩阵下图所表示的图可以构造邻接矩阵M如下如下:M=（mij）=蹦嘉嗡纳宙和纯导宅男强淌匆藉干槐竣啪峰钠芒疫奥彻兼坝雇蜂蜀径措敢清华大学运筹学完整版原版清华大学运筹学完整版原版Page264图的基本概念与模型图的基本概念与模型v5v1v2v3v4v64332256437例例6.4下图所表示的图可以构造权矩阵下图所表示的图可以构造权矩阵B如下如下:陋博项闯全敝楼凌璃捞梨狰扬煽净横峡个箕梦深垣鳞冠磊膝剧翠懂葫逢牙清华大学运筹学完整版原版清华大学运筹学完整版原版Page265树与图的最小树树与图的最小树树是图论中结构最简单但又十分重要的图。在自然和社会领树是图论中结构最简单但又十分重
164、要的图。在自然和社会领域应用极为广泛。域应用极为广泛。例例6.2乒乓求单打比赛抽签后，可用图来表示相遇情况，如乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。下图所示。AB CDEF GH运动员运动员苏艺钒情舔陪略号矫潞嗓转槽闰绊底拒强唐跨逃吻高灰偏递蟹修歧闹棋熙清华大学运筹学完整版原版清华大学运筹学完整版原版Page266树与图的最小树树与图的最小树例例6.3某企业的组织机构图也可用树图表示。某企业的组织机构图也可用树图表示。厂长厂长人事科人事科财务科财务科总工总工程师程师生产副生产副厂长厂长经营副经营副厂长厂长开发科开发科技术科技术科生产科生产科设备科设备科供应科供应科销售科销售科
165、检验科检验科动力科动力科往绢柱所走偏回优建货氏潍续晰禹俘务屎纪欺来尸算军耀刮硫狗贩挨锋北清华大学运筹学完整版原版清华大学运筹学完整版原版Page267树与图的最小树树与图的最小树树：无圈的连通图即为树树：无圈的连通图即为树性质性质1：任何树中必存在次为：任何树中必存在次为1的点。的点。性质性质2：n个顶点的树必有个顶点的树必有n-1条边。条边。性质性质3：树中任意两个顶点之间，恰有且仅有一条链。：树中任意两个顶点之间，恰有且仅有一条链。性质性质4：树连通，但去掉任一条边，必变为不连通。：树连通，但去掉任一条边，必变为不连通。性质性质5：树无回圈，但不相邻的两个点之间加一条边，恰：树无回圈，但不
166、相邻的两个点之间加一条边，恰得到一个圈。得到一个圈。v1v2v3v4v5v6淖饺咱瞅培绿衍莲脐酬卿契扇敞卵玲锻泉菌狈泵昼胯涝絮缕晒褥笆舷拧馈清华大学运筹学完整版原版清华大学运筹学完整版原版Page268树与图的最小树树与图的最小树图的最小部分树图的最小部分树(支撑树支撑树)如果如果G2是是G1的部分图，又是树图，则称的部分图，又是树图，则称G2是是G1的部分树的部分树（或支撑树）。树图的各条边称为树枝，一般图（或支撑树）。树图的各条边称为树枝，一般图G1含有多含有多个部分树，其中树枝总长最小的部分树，称为该图的最小个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。部分树
167、（或最小支撑树）。v1v2v3v4v5v1v2v3v4v5G1G2龟济笨挖婉痛戊抿耙褐堡滨屿橱对摔柱内陇奈恶孰呐钡狰垄惋殖推玫鬼虏清华大学运筹学完整版原版清华大学运筹学完整版原版Page269树与图的最小树树与图的最小树a ab bc cf fe ed dh hg gb bf fe ed d牲迂锹踩涉峻洲促邓本肃硼杜岿擦吸道倪哀云匆号喝杆硅荫匝袋隶莱赚窘清华大学运筹学完整版原版清华大学运筹学完整版原版Page270树与图的最小树树与图的最小树a ab bc cf fe ed dh hg gb bf fd dg g峙役邓迁跑腐喇晴而私闽臂乖果输傈耳荔瀑茧堕蓟贱萍逻宝力笑蕉孔观领清华大学运筹学完整
168、版原版清华大学运筹学完整版原版Page271树与图的最小树树与图的最小树b bc ce ed da ab bc cf fe ed dh hg g付咨外分弱点情蓟左谬嗣奴德帕告圃窖博肢崎锰劣斋弥垣墙邓答梭济额倔清华大学运筹学完整版原版清华大学运筹学完整版原版Page272树与图的最小树树与图的最小树a ab bc ch ha ab bc cf fe ed dh hg g截晶痰俭句枚浴发欲俩倒吏赖括铣冗持妨颓意箱涨拄锗私贸亢艇锻饰蟹朝清华大学运筹学完整版原版清华大学运筹学完整版原版Page273树与图的最小树树与图的最小树a af fd dg ga ab bc cf fe ed dh hg g达德
169、酗煌冲既肌昭诲课倘猴熏豆团诱申棘巫因雹赤挚伟暖法屹玲萍尼盛豌清华大学运筹学完整版原版清华大学运筹学完整版原版Page274树与图的最小树树与图的最小树求树的方法：破圈法和避圈法求树的方法：破圈法和避圈法求树的方法：破圈法和避圈法求树的方法：破圈法和避圈法破圈法破圈法破圈法破圈法躲鬼霍例半啦抗课悟值翅辑捉咬沤沽客身兜咋盼谤灵形啊履迅赐阔腰袄菱清华大学运筹学完整版原版清华大学运筹学完整版原版Page275树与图的最小树树与图的最小树部分树部分树僻霄芍皆睁素寺檀呐灿因茂警坤葵背步棵昨咽琐柳埔肖累论货裔栖盼都饵清华大学运筹学完整版原版清华大学运筹学完整版原版Page276树与图的最小树树与图的最小树避
170、圈法避圈法避圈法避圈法v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5椅琶掷肛炮淫林丘灸设蒙辕裸狭久慌吞波浊钵荔赤宾骸测店势蒙桥怨朋副清华大学运筹学完整版原版清华大学运筹学完整版原版Page277树与图的最小树树与图的最小树赋权图中求最小树的方法：破圈法和避圈法赋权图中求最小树的方法：破圈法和避圈法赋权图中求最小树的方法：破圈法和避圈法赋权图中求最小树的方法：破圈法和避圈法破圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边
171、数边数n-1=5储褥涩婆犁营目兆效棋盔旺静纸壬货忧抨阴窃过端额椎玩栓渔貌哼潦陡锡清华大学运筹学完整版原版清华大学运筹学完整版原版Page278树与图的最小树树与图的最小树v1v2v3v4v5v643521得到最小树：得到最小树：MinC(T)=15曼斧袭枉谩钠渭显稿乞痛桩月牟庐奎副装润磷拌若供例郁股缩狗抓甘稍吕清华大学运筹学完整版原版清华大学运筹学完整版原版Page279树与图的最小树树与图的最小树避圈法避圈法:去掉去掉G中所有边，得到中所有边，得到n个孤立点；然后加边。个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能形成加边的原则为：从最短边开始添加，加边的过程中不能形成
172、圈，直到点点连通圈，直到点点连通(即即:n-1条边条边)。5v1v2v3v4v5v6843752618纫坟悔湛积尹全皂找甲喳豢甄刚塔仗脊汇灶斯征碘惫审蹬墨贵凛柜试滥山清华大学运筹学完整版原版清华大学运筹学完整版原版Page280树与图的最小树树与图的最小树v1v2v3v4v5v6435215v1v2v3v4v5v6843752618MinC(T)=15逼事汛垣窑升奄贿纯兰蔑干熊氓董抑侯奢腔冰闷撼顾熊驱括致写范懦恬珍清华大学运筹学完整版原版清华大学运筹学完整版原版Page281树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 91616252
173、53 3282817174 41 123233636练习：练习：练习：练习：应用破圈法求最小树应用破圈法求最小树应用破圈法求最小树应用破圈法求最小树焰嫌祟毋已骡钾倚尽拓讽蹋桔铺脖涪慌训糯落肯咐佃军立嫁划牛辫辅杭梳清华大学运筹学完整版原版清华大学运筹学完整版原版Page282树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636际励屋职泞封饶幼褐饱艺彤异逢芭联蜒扳旧鸽碑春诛赁役锈黑需坦阐鲁懂清华大学运筹学完整版原版清华大学运筹学完整版原版Page283树与图的最小树树与图的最小树
174、v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323屁舀静诡痉颁撂罚疽耘歧讯斯砖靖金作舔卓监俊剑全几菠趋婚祈观咯腑陋清华大学运筹学完整版原版清华大学运筹学完整版原版Page284树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323氦嗓改练迷毗厦翘焰蝎冈赵桃美役梁沃砰嚏意拱诅奎执馋痕挪零川解萤掘清华大学运筹学完整版原版清华大学运筹学完整版原版Page285树与图的最小树树与图的最小树v1v1v7v7v4
175、v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323五卑滩俯杭姜萄疗麓井病杜羡洋馅被绵沪址天圈胳欣烯侧牢进骤戚京纠驾清华大学运筹学完整版原版清华大学运筹学完整版原版Page286树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323园吞慰玻苟子李韶真本是频眶陕执鹿欧词狂面滓衰稀廊阻锻钞料刃搀蒜尝清华大学运筹学完整版原版清华大学运筹学完整版原版Page287树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6
176、9 9161625253 3282817174 41 12323椿沟徐惟耀窑飘舵苹蝴款椭叼售辣携鞋双丸扛动腿记碟肇蒂衅煤胚滁淡殊清华大学运筹学完整版原版清华大学运筹学完整版原版Page288树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 9161625253 3282817174 41 12323间股楼阻英械尘哄虽田背狡扇屁是矗忙促躲捏抢天呛返缆蝗琉诗匡肖瞒迪清华大学运筹学完整版原版清华大学运筹学完整版原版Page289树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 123
177、23与停皋讫疙广醚新嘎示点禽傀咐蕴类傅造虐拌薪汾鳃润笆鞋喉静珐纱恋茬清华大学运筹学完整版原版清华大学运筹学完整版原版Page290树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323乐幕取笑仅娘凝彼坷继杉琅义人澎钾甘袱亮孩辱狭家舜脖勋于传冬吏棵囊清华大学运筹学完整版原版清华大学运筹学完整版原版Page291树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323趋圈稀挨步阳魔晨逼柯撞僳僵涌阅雀垢闻咱隶峨辟蔚迁豹瑶庄破庚提脆瘁清华大学
178、运筹学完整版原版清华大学运筹学完整版原版Page292树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323素使坚廊至凡订椰渺活跑花搪而渔障寺员评温巳败琢弓第肪炕单甲汽耐哦清华大学运筹学完整版原版清华大学运筹学完整版原版Page293树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 317174 41 12323min=1+4+9+3+17+23=57棱秒夺虐兵惮容忱搐霞欺雌阁隐戊讯与够沂炙玻禾叮拎枚盐史岁签羌姓糠清华大学运筹学完整版原版清华大学运筹学完整版原版Page29
179、4树与图的最小树树与图的最小树练习：练习：练习：练习：应用避圈法求最小树应用避圈法求最小树应用避圈法求最小树应用避圈法求最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636出鬼理锣沉挂据钩敛挠致妻此岁疫上桑靖羡哼习揽爱砾雅臆别荤局铁脆星清华大学运筹学完整版原版清华大学运筹学完整版原版Page295树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636体永弧理责坞斩庶辩胀玄玛挖拥跃弄
180、峻群酣署驻坛澄鞋藻悦屠蠕华冗幢淤清华大学运筹学完整版原版清华大学运筹学完整版原版Page296树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636歼龙扰铁畅瞄还谈虚疾勘尽眶桩摸晚但尤瘪糜胞晦绎立懒依毅脯忌奇恐猫清华大学运筹学完整版原版清华大学运筹学完整版原版Page297树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636洁砂净耕婚飞鱼墩笼铜灯帐予蹿艰凳贸急
181、富涩吊博烹官箕黄蚜怔筒黑顿恃清华大学运筹学完整版原版清华大学运筹学完整版原版Page298树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636慑蔗奎景节追金垣叛骄骆犬郝立埃衷褂码以附涩驳踞若化耻毫掺措坤爬毒清华大学运筹学完整版原版清华大学运筹学完整版原版Page299树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636墒办揩湖迹肆似献卧万掷霍米师幢渭宙器孰陌
182、萤挤抒蜂帮积羌揪冬茧脸耶清华大学运筹学完整版原版清华大学运筹学完整版原版Page300树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636min=1+4+9+3+17+23=57min=1+4+9+3+17+23=57号均疡喳弊烛挨龟窥被雨提扛斡娩提副只礁盈跃闸枷极佑牢敦刮酸曝衬每清华大学运筹学完整版原版清华大学运筹学完整版原版Page301树与图的最小树树与图的最小树课堂练习：课堂练习：课堂练习：课堂练习：3749346321MinC(T)=12MinC(T)=152541
183、73314475答案：答案：阀挞蛰拆煌楔洽访叙虏涕撒笆旅宛港掠氨碗锁宰形沛莎卑倔挎叭蚂靶枫成清华大学运筹学完整版原版清华大学运筹学完整版原版Page302树与图的最小树树与图的最小树34122323242MinC(T)=12213638534567454321MinC(T)=18翰趣阿龋队含脂竟芯甲铝瑰咆贴伪未妹嘎簇担帕田卖铝羚舔啃主蒸娜坚糊清华大学运筹学完整版原版清华大学运筹学完整版原版Page303最短路问题最短路问题如何用最短的线路将三部电话连起来？如何用最短的线路将三部电话连起来？此问题可抽象为设此问题可抽象为设ABC为等边三角形，连接三顶点的为等边三角形，连接三顶点的路线（称为网络）
184、。这种网络有许多个，其中最短路线者显路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如然是二边之和（如ABAC）。）。ABC轿耕眯吟颊聚椒丛码秽瓜塘踪觅捻乓述皆碳脑汛锚瘪沉好戌窃诊务醉肮肯清华大学运筹学完整版原版清华大学运筹学完整版原版Page304最短路问题最短路问题ABCP但若增加一个周转站（新点但若增加一个周转站（新点P），连接），连接4点的新网络的最短路点的新网络的最短路线为线为PAPBPC。最短新路径之长。最短新路径之长N比原来只连三点的最比原来只连三点的最短路径短路径O要短。这样得到的网络不仅比原来节省材料，而且要短。这样得到的网络不仅比原来节省材料，而且稳定性也
185、更好。稳定性也更好。鳖质又询荤绚佰辑暖蒋祖肢孜橡驾抛旋车虞玲霓骂条挟起拣苑酶茵履稀演清华大学运筹学完整版原版清华大学运筹学完整版原版Page305最短路问题最短路问题问题描述：问题描述：就是从给定的网络图中找出一点到各点或任意两点之就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路间距离最短的一条路.有些问题，如选址、管道铺设时的选线、设备更新、有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。短路的问题。因此这类问题在生产实际中得
186、到广泛应用。腹福浓辊梯闪辑括宿煌坚手妙渐阀匝许仁岁峭热岛钳真聊谁堂加容配筒誊清华大学运筹学完整版原版清华大学运筹学完整版原版Page306最短路问题最短路问题例例例例6.46.4渡河游戏渡河游戏渡河游戏渡河游戏一老汉带了一只狼、一只羊、一棵白菜想要从南岸过一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，问应该怎样安排渡河，才能做到既把所
187、有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法并且在河上来回次数最少？这个问题就可以用求最短路方法解决。解决。同判披丽岔姻拍至淤软筷兴莽眩贵蜕绦磐热竿珠蝉娜状食循酋果建八的什清华大学运筹学完整版原版清华大学运筹学完整版原版Page307最短路问题最短路问题定义：定义：1）人）人M（Man），狼），狼W（Wolf），），羊羊G（Goat），），草草H（Hay）2）点点vi表示河岸的状态表示河岸的状态3）边边ek表示由状态表示由状态vi经一次渡河到状态经一次渡河到状态vj4）权权边边ek上的权定为上的权定为1我们可以得到下面的加权有向图我们可以得到下面的加权有向图遣滨攫亢冤
188、例锋闹绑谴陵损腐敦蜀砚竞没吓逢芒皑岩绦弟倾鉴办贸舜遂颧清华大学运筹学完整版原版清华大学运筹学完整版原版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的最短路问题。的最短路问题。v1v2v3v4v5u5u4u3u2u1采筏研掏凯眼条乍槽茎壁秧鹤翟黎截臭穴耕颈寐退槽股碟啃臂堤桥虾颈曹清华大学运筹学完整版原版清华大学运筹学完整版原版Page309最短路问题最短路问题求最短路有两种算
189、法求最短路有两种算法:狄克斯屈拉狄克斯屈拉(Dijkstra)标号算法标号算法逐次逼近算法逐次逼近算法瞎蓬柴耀贡柒移诬戒浪筐仆湍妙藩薪猾孰橙炯澈吼彩遣僧蛰乌葫胎斥荆债清华大学运筹学完整版原版清华大学运筹学完整版原版Page310最短路问题最短路问题狄克斯屈拉狄克斯屈拉狄克斯屈拉狄克斯屈拉(Dijkstra)(Dijkstra)标号算法的基本思路：标号算法的基本思路：标号算法的基本思路：标号算法的基本思路：若序列若序列vs,v1.vn-1,vn 是从是从vs到到vt间的最短路，则序列间的最短路，则序列vs,v1.vn-1 必为从必为从vs 到到vn-1的最短路。的最短路。假定假定v1v2v3v4
190、是是v1v4的最短路，则的最短路，则v1v2v3一定是一定是v1v3的最短路，的最短路，v2v3v4也一定是也一定是v2v4的最短路。的最短路。v1v2v3v4v5竟篱望碰精精倾两暇筏侗裴忆偿竭乍浆藐表逻趣贿巩峻乳预恤妆弯浴酉柒清华大学运筹学完整版原版清华大学运筹学完整版原版Page311最短路问题最短路问题求网络图的最短路，设图的起点是求网络图的最短路，设图的起点是vs,终点是终点是vt ,以以vi为起点为起点vj为终点的弧记为为终点的弧记为(i,j) 距离为距离为dijP P标号标号标号标号( (点标号点标号点标号点标号) )：b(j)起点起点vs到点到点vj的最短路长；的最短路长；T T
191、标号标号标号标号( (边标号边标号边标号边标号) )：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最短路
192、问题最短路问题例例6.5求下图求下图v1到到v7的最短路长及最短路线的最短路长及最短路线86252353421057086225441114751071211v7已标号，计算结束。从已标号，计算结束。从v1到到v7的最短路长是的最短路长是11,最短路线：最短路线：v1v4v6v7P标号标号T标号标号屠示就绞际差铁赘安扁稀彼实裕邱恐谊努庚撵掖萝肢譬睛郧悦孺坏十凭姨清华大学运筹学完整版原版清华大学运筹学完整版原版Page313最短路问题最短路问题从上例知，只要某点已标号，说明已找到起点从上例知，只要某点已标号，说明已找到起点vs到到该点的最短路线及最短距离，因此可以将每个点标该点的最短路线及最短距
193、离，因此可以将每个点标号，求出号，求出vs到任意点的最短路线，如果某个点到任意点的最短路线，如果某个点vj不能不能标号，说明标号，说明vs不可达不可达vj 。注：无向图最短路的求法只将上述步骤注：无向图最短路的求法只将上述步骤2将弧改成边即可。将弧改成边即可。蚜袭矣率区炎酗么牵早玫激肝萎陀火渍邯雪昔德率杂涌师警萤眼辨彰峡苔清华大学运筹学完整版原版清华大学运筹学完整版原版Page314最短路问题最短路问题例例6.6求下图求下图v1到各点的最短距离及最短路线。到各点的最短距离及最短路线。4526178393261216180452231039612641166188122482418所有点都已标号
194、，点上的标号就是所有点都已标号，点上的标号就是v1到该点的最短距离，最短到该点的最短距离，最短路线就是红色的链。路线就是红色的链。绳确婆鞠孩拳误催巧绵樊瞩洼勃镀错是绪者魏笋域落爷群狭绚椅便闽己津清华大学运筹学完整版原版清华大学运筹学完整版原版Page315最短路问题最短路问题课堂练习：课堂练习：1.用用Dijkstra算法求下图从算法求下图从v1到到v6的最短距离及路线。的最短距离及路线。v3v54v1v2v4v635222421v1到到v6的最短路为：的最短路为：造昧渤枉实拙邯粒削卖辱鬃啪佣娥秩模诌寡成篷授灿棍煌灯纤巩羊需夹晤清华大学运筹学完整版原版清华大学运筹学完整版原版Page316最短
195、路问题最短路问题2.求从求从v1到到v8的最短路径的最短路径237184566134105275934682赫卸惰瞎靴捐趁掐滁肘陶丧享涯炭丹仇较烃窝蓑歧次蔡柬士纽翠臻吕涨菩清华大学运筹学完整版原版清华大学运筹学完整版原版Page317最短路问题最短路问题237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到到v8的最短路径为的最短路径为v1v4v7v5v8，最短距离为，最短距离为10钥史宝哗甘榜最占文掺熟盲哇迄派枪鸡殃许练抛氮备苔携钦洁熏衍闷美砰清华大学运筹学完整版原版清华大学运筹学完整版原版Page318最短路问题最短路问题3
196、.求下图中求下图中v1点到另外任意一点的最短路径点到另外任意一点的最短路径v1v2v3v4v6v5322762133朝本滇汐锰痰壳忌合沤砰尊僚玛测僚般涟铜见概描菱寥燃卞慰拷翻溢浮彪清华大学运筹学完整版原版清华大学运筹学完整版原版Page319最短路问题最短路问题v1V2V3V4V6V5322762133024714袄羔汁谁蹲抄坏骆榨蛾抒舌江鬃褐偷解桐描挛泅瓢垢柄尸邪压稻逃撅胆屹清华大学运筹学完整版原版清华大学运筹学完整版原版Page320最短路问题最短路问题v1V2V3V4V6V5322762133024714洋献媚翰青锋短哩长汁沃京迫岿扣揭柄矫滤禄亿前称斗椿酮存押拟哀准宵清华大学运筹学完整版
197、原版清华大学运筹学完整版原版Page321最短路问题最短路问题算法适用条件：算法适用条件：Dijkstra算法只适用于全部权为非负情况，如果某算法只适用于全部权为非负情况，如果某边上权为负的，算法失效。此时可采用逐次逼近边上权为负的，算法失效。此时可采用逐次逼近算法。算法。例例6.7如右图所示中按如右图所示中按dijkstra算算法可得法可得P(v1)=5为从为从vsv1的最短的最短路长显然是错误的，从路长显然是错误的，从vsv2v1路长只有路长只有3。v2vsv15-58溢砒卑鸣疹晶誓滋孕雌尧攒镐詹迹纬甭辜屉稗塑妊奸撂伞凝府责痒炭讣肾清华大学运筹学完整版原版清华大学运筹学完整版原版Page3
198、22最短路问题最短路问题最短路问题的应用：最短路问题的应用：例例6.7电信公司准备准备在甲、乙两地沿路架设一条光缆线，电信公司准备准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。通图。权数表示两地间公路的长度（单位：公里）。v1（甲地）（甲地）1517624431065v2v7(乙地乙地)v3v4v5v6一暑产镰蝉咀厌爵辙声挤袍障寝私灿掩钉盐冰郴拦惯绳坚墒陀臂停又娟凌清华大学运筹学完整版原版清华大学运筹学完整版原版Page323最短路问题最短路问题解：这是一
199、个求无向图的最短路的问题。解：这是一个求无向图的最短路的问题。秧投趴彼肉癣谢抗屹健售薪怯豁峭蔷艳廊郧慢刹眩恕刑绍嚏潦创笆升倍椰清华大学运筹学完整版原版清华大学运筹学完整版原版Page324最短路问题最短路问题例例6.8设备更新问题。某公司使用一台设备，在每年年初，设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就低。如果继续使用旧设备，可以
200、省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表设备每年年初的价格表年份年份12345年初价格年初价格1111121213匆钒尹剿德咎详茸惋耳物悠诺牢挝智笺辕演冗还权齿蓝薛钩谗竞赎容岂宿清华大学运筹学完整版原版清华大学运筹学完整版原版Page325最短路问题最短路问题设备维修费如下表设备维修费如下表使用年数使用年数0-11-22-33-44-5每年维修费用每年维修费用5681118解：解：将问题转化为最短路问题
201、，如下图：用将问题转化为最短路问题，如下图：用vi表示表示“第第i年年年年初购进一台新设备初购进一台新设备”,弧（弧（vi,vj）表示第）表示第i年年初购进的设备年年初购进的设备一直使用到第一直使用到第j年年初。年年初。v1v2v3v4v5v6历胆宜为剐市胳减喜摄硅九睫磨胞词泣虱睦灸籍衷厚拆落涯庚擂晴痛这彻清华大学运筹学完整版原版清华大学运筹学完整版原版Page326最短路问题最短路问题把所有弧的权数计算如下表，把所有弧的权数计算如下表，把权数赋到图中，再用把权数赋到图中，再用Dijkstra算法求最短路。算法求最短路。1234561162230415921622304131723314172
202、35186v1v2v3v4v5v6162230415916223041312317181723康辗挡刻泻咯响次寝墙村关脾喷劝邻测鼎疹袒脚迄抢译煞燃撮颠卓双奢逸清华大学运筹学完整版原版清华大学运筹学完整版原版Page327最短路问题最短路问题最终得到下图，可知，最终得到下图，可知，v1到到v6的距离是的距离是53，最短路径有两条：，最短路径有两条：v1v3v6和和v1v4v6V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723V2（16,1）16(30,1)(53,3)(53,4)殃癌搔畦战租都岸剁疵女媒葡池蒂舍坯挫奸抵笋卷锨冕剿挣畔斥讳暖作
203、壤清华大学运筹学完整版原版清华大学运筹学完整版原版Page328网络的最大流网络的最大流如何制定一个运输计划使生产地到销售地的产品输送量最大。如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。这就是一个网络最大流问题。蔽主礼玻硕炎徘迷暑艘政市鹅妖悸乖健俏遁氏罪锑牛敷瞳面衫磨兴挖报炭清华大学运筹学完整版原版清华大学运筹学完整版原版Page329网络的最大流网络的最大流基本概念：基本概念：1.1.容量网络：容量网络：容量网络：容量网络：队网络上的每条弧队网络上的每条弧(vi,vj)都给出一个最大的都给出一个最大的通过能力，称为该弧的通过能力，称为该弧的容量容量容量容量
204、，简记为，简记为cij。容量网络中通常规。容量网络中通常规定一个定一个发点发点发点发点(也称源点，记为也称源点，记为s)和一个和一个收点收点收点收点(也称汇点，记为也称汇点，记为t)，网络中其他点称为，网络中其他点称为中间点中间点中间点中间点。st4844122679缀褂小竣恫纽湖之鳃捍蚁浴糜抒应瞒菲烁限蹭屯撬刑项觅皑邢孪径布洁旦清华大学运筹学完整版原版清华大学运筹学完整版原版Page330网络的最大流网络的最大流2.网络的最大流网络的最大流是指网络中从发点到收点之间允许通过的最大流量。是指网络中从发点到收点之间允许通过的最大流量。3.流与可行流流与可行流流流是指加在网络各条弧上的实际流量，对
205、加在弧是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上上的负载量记为的负载量记为fij。若。若fij=0，称为零流。，称为零流。满足以下条件的一组流称为满足以下条件的一组流称为可行流可行流。容量限制条件。容量网络上所有的弧满足：容量限制条件。容量网络上所有的弧满足：0fijcij中间点平衡条件。中间点平衡条件。若以若以v(f)表示网络中从表示网络中从st的流量，则有：的流量，则有：挖域间菌佑闷蕴福宛辜材脆詹诱乳骏较坛泅蔫功泛哀泅保畔嘛绷拇窄央浆清华大学运筹学完整版原版清华大学运筹学完整版原版Page331网络的最大流网络的最大流结论：任何网络上一定存在可行流。（零流即是结论：任何网络上
206、一定存在可行流。（零流即是可行流）可行流）网络最大流问题：网络最大流问题：指满足容量限制条件和中间点平衡的条件下，使指满足容量限制条件和中间点平衡的条件下，使v(f)值值达到最大。达到最大。渡踩汀溜教炳凤黍屈抛贵切履四置运抬醋鞍叮倾二膝多脓膨鸿踊言置绩尹清华大学运筹学完整版原版清华大学运筹学完整版原版Page332网络的最大流网络的最大流割与割集割与割集割是指容量网络中的发点和收点分割开，并使割是指容量网络中的发点和收点分割开，并使st的流中断的流中断的一组弧的集合。割容量是组成割集合中的各条弧的容量之的一组弧的集合。割容量是组成割集合中的各条弧的容量之和，用和，用表示。表示。如下图中，如下图
207、中，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)AABB行苏缎沙裁隋咨缝盒奢势后冰惺偿答婴展塔忱争跪磺涅诞娠妥酒轨牡瞬储清华大学运筹学完整版原版清华大学运筹学完整版原版Page334网络的最大流网络的最大流定理定理定理定理1 1设网
208、络设网络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
209、,V)癸样镊春兰蹄杜芹莉鉴阑辰擞绑民社械仁浦恋奥浪肄桂铬项硬塞驮狐痈险清华大学运筹学完整版原版清华大学运筹学完整版原版Page335网络的最大流网络的最大流增广链增广链增广链增广链在网络的发点和收点之间能找到一条链，在该链上所在网络的发点和收点之间能找到一条链，在该链上所有指向为有指向为st的弧，称为前向弧，记作的弧，称为前向弧，记作+,存在存在f0，则称这样的，则称这样的链为增广链。链为增广链。例如下图中，例如下图中，sv2v1v3v4t。定理定理定理定理3 3网络网络N中的流中的流f是最大流当且仅当是最大流当且仅当N中不包含任何增广中不包含任何增广链链萎芒延骸促太俩晶曝驭钨妨峻行助阮榔碍博
210、恢纵叁门尽愿乞聪副之署嚏悲清华大学运筹学完整版原版清华大学运筹学完整版原版Page336网络的最大流网络的最大流stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(4)7(5)始阜烦云仍酸相寞酌光舒顶亚馁过倾耿断父卯耪积星在改敦亡索弹离司钝清华大学运筹学完整版原版清华大学运筹学完整版原版Page337网络的最大流网络的最大流求网络最大流的标号算法：求网络最大流的标号算法： 基本思想基本思想基本思想基本思想由一个流开始，系统地搜寻增广链，然后在此链上增由一个流开始，系统地搜寻增广链，然后在此链上增流，继续这个增流过程，直至不存在增广链。流，继续这个增流过程，直至不存
211、在增广链。 基本方法基本方法基本方法基本方法 (1)找出第一个可行流，（例如所有弧的流量找出第一个可行流，（例如所有弧的流量fij =0。）。）(2)用标号的方法找一条增广链用标号的方法找一条增广链首先给发点首先给发点s标号标号(),标号中的数字表示允许的最大调整标号中的数字表示允许的最大调整量。量。选择一个点选择一个点vi 已标号并且另一端未标号的弧沿着某条链已标号并且另一端未标号的弧沿着某条链向收点检查：向收点检查：甥御委拆俩驭臆立槐手差臆绒耍妓奸岂絮渭拨寅筷辉倡锤虽堑捻彻浆拢琵清华大学运筹学完整版原版清华大学运筹学完整版原版Page338网络的最大流网络的最大流如果弧的起点为如果弧的起点
212、为vi，并且有，并且有fij0，则，则vj标号标号(fji)(3)重复第重复第(2)步，可能出现两种结局：步，可能出现两种结局：标号过程中断，标号过程中断，t无法标号，说明网络中不存在增广链，无法标号，说明网络中不存在增广链，目前流量为最大流。同时可以确定最小割集，目前流量为最大流。同时可以确定最小割集，记已标号的点记已标号的点集为集为V,未标号的点集合为未标号的点集合为V,(V,V)为网络的最小割。为网络的最小割。t得到标号，反向追踪在网络中找到一条从得到标号，反向追踪在网络中找到一条从s到到t得由标号得由标号点及相应的弧连接而成的增广链。继续第点及相应的弧连接而成的增广链。继续第(4)步步
213、尊胎驳巴剂博撞尹软茹跨迢佛拂潦腋商百丝蔗供崎莲疯会个悼畏缝叶暴彬清华大学运筹学完整版原版清华大学运筹学完整版原版Page339网络的最大流网络的最大流(4)修改流量。设原图可行流为修改流量。设原图可行流为f，令，令得到网络上一个新的可行流得到网络上一个新的可行流f。(5)擦除图上所有标号，重复擦除图上所有标号，重复(1)-(4)步，直到图中找不到任步，直到图中找不到任何增广链，计算结束。何增广链，计算结束。渺卵犯患遇陆幅猫扇涉根淳惕荔免十册慧枢扦盔倍姨卜介芹录试坍腥讶斜清华大学运筹学完整版原版清华大学运筹学完整版原版Page340网络的最大流网络的最大流例例6.10用标号算法求下图中用标号算法
214、求下图中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网络的最大流网络的最大流stv1
215、v3v2v48(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
216、-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)找到一条增广链找到一条增广链sv1v3t镰赦痈井听殿觉炕他春侧每班寿逼话譬急徊凶纲袜獭丘捶姐澳惰删硕情纯清华大学运筹学完整版原版清华大学运筹学完整版原版Pa
217、ge345网络的最大流网络的最大流(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
218、(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=1中纤掳段普萍掩张捣罕禽景刊拦更霖恋黍蹲镇逝攫瞪赣耙聘菇
219、揽弟步亡褐清华大学运筹学完整版原版清华大学运筹学完整版原版Page348网络的最大流网络的最大流(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)
220、(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=1锭颅凝卖脐泻慧疡搪壶幼扳预兄
221、袍嗜住豌捕真识笨忠乐搀儡掇芍查肝遏绝清华大学运筹学完整版原版清华大学运筹学完整版原版Page351网络的最大流网络的最大流例例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)在
222、已知可行流的基础上，通过标号寻找增广链。在已知可行流的基础上，通过标号寻找增广链。()(2)=min,6=6(6)(3)=min6,2=2(2)(t)=min2,5=2(2)存在增广链存在增广链存在增广链存在增广链svsv2 2vv3 3tt袋役炸钢计某阂柄蒸光莱经辛陀能寸挫童曝蛆肌诊洗糙谦抉手饿儒胸洁侧清华大学运筹学完整版原版清华大学运筹学完整版原版Page353网络的最大流网络的最大流(2)修改增广链上的流量，非增广链上的流量不变，得到新修改增广链上的流量，非增广链上的流量不变，得到新的可行流。的可行流。stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(
223、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)重新搜寻增广链。重新搜寻增广链
224、。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 3tt严腥柄判厩噎屡笺鼓藐逞赐堂瓢胚搀妊宋锦圆阑倪词彝讶港讲浇坷锑磕肘清华大学运筹学完整版原版清华大学运筹学完整版原版Page356网络的最大流网络的最大流(5)修改增广链上的流量，非增广链上的流量不变，得到新的可修改增广链上的流量，非增广链上的流量不变，得到新的可行流。行
225、流。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)木么捶节悸匙合绒朝辩逞跋魄笋邓惯旺判报焰凑粥芜甥芦棺狡叠箭摄莆麦清华大学运筹学完整版原版清华大学运筹学完整版原版Page
226、358网络的最大流网络的最大流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 3tt辞丫肢叁郊梢评王箱郡高搅言甫连粉畅屏丫傲姆功钨咙虹责成适诚萌栽拼清华大学运筹学完整版原版清华大学运筹学完整版原版Page359网络的最大流网络的最大流(8)调整增广链上的流量，非增广链流量不变，得到新的可行流调整增广链上的流量，非增广链流量不
227、变，得到新的可行流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)擦除原标号擦除原标号茸荒今伯谤版感五此勒昏胳卑蛊宰旺玄辆垒氓赴孰液讫捉培绩扬疚桨绒谷清华大学运筹学完整版原版清华大学运筹学完整版原版Pag
228、e361网络的最大流网络的最大流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甫缘菜继帜浆成臻裙控拨社地主伎猎崭琼纠栽哀贴湾枉浦坡很警腊澄闷遁清华大学运筹学完整版原版清华大学运筹学完整版原版Page362网络的最大流网络的最大流stv1v2v3v4v54(3)3(3)
229、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)擦除标号，在新的可行流上重新标号。擦除标号，在新的可行流上重新标号。针
230、佛椰篮抉驱解扒谣惧唯患由坎荷操鸳佐鹏采都着蹦袖哆墒比域聂秩投傍清华大学运筹学完整版原版清华大学运筹学完整版原版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。罐罚徊阀声协低呻绢八眼腆掌射率林涩殉哥剿绘篮渠产占鬼肛能站臭磐却清华大学运筹学完整版原版清华大学运筹学完整版原版
