第2章 图与网络分析补充

1、第二章 图论(t ln)与网络分析补充 补充(bchng)内容图的基本概念应用举例最小支撑树问题举例运输问题补充最短路径问题举例网络最大流问题举例网络计划补充例共六十九页图的基本概念应用(yngyng)举例共六十九页共六十九页最小支撑(zh chng)树问题举例 例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222225452634531共六十九页算法2（破圈法）： 在图中找圈，并删除其中(qzhng)最大边。如此进行下去，

2、直至图中不存在圈。55.5v1v2v3v4v53.57.5423共六十九页 例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字(shz)所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222225452634531共六十九页 例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字(shz)所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS22222245263453

3、1共六十九页 例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求(yoqi)设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS22222252634531共六十九页 例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上(bin shn)的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222222634531共六十九页 例今有煤气站A，将给一居民区供应煤气，居民区各

4、用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求(yoqi)设计一个最经济的煤气管道路线，并求所需的总费用。ABCDEFGHIJKS2222222634531共六十九页 例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设(p sh)各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。IABCDEFGHJKS222222234531共六十九页 例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用(fi yong)（单位：万

5、元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用(fi yong)。IJABCDEFGHKS22222223431此即为最经济(jngj)的煤气管道路线，所需的总费用为25万元共六十九页运输问题补充：产销(chnxio)不平衡问题1. 产大于销 （ ） 模型(mxng)：增加松弛变量运输表：B1BnBn+1A1x11x1nx1,n+1a1Amxm1xmnxm,n+1amb1bnbn+1实际意义：虚设一 个销地运价为零共六十九页2. 产小于销 （ ） 模型：增加松弛变量运输(ynsh)表：实际意义：虚设(xsh)一 个销地B1BnA1x11x1na1Amxm1xmnam

6、Am+1xm+1，1xm+1,nam+1b1bn共六十九页 运输问题应用举例（生产与储存问题） 例、某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压(jy)一个季度需储存、维护等费用0.15万元。 试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。生产能力单位成本（万元）一季度2510.8二季度3511.1三季度3011.0四季度1011.3共六十九页 应用举例（生产与储存问题） 例、某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规

7、格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15元。 试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。产地销地第一季度第二季度第三季度第四季度第一季度第二季度第三季度第四季度产量(chnling)销量(xio lin)253530101015252010.9510.811.1011.2511.111.2511.4011.0011.1511.30MMMMMM分析：本问题可转化为一运输问题共六十九页最短路问题举例无向(w xin)图情形求网络(wnglu)中v1至v7的最短路。v1v2v3v

8、4v5v6v7225355715713共六十九页课堂练习 无向(w xin)图情形答案(d n)（1）：v1v2v3v4v5v6v72253557157130,v12,v13,v14,v2/ v47,v38,v513,v6共六十九页课堂练习 无向(w xin)图情形答案(d n)（2）：v1v2v3v4v5v6v72253557157130,v12,v13,v14,v2/ v47,v38,v513,v6共六十九页最短路模型的应用(yngyng)设备更新问题（P119 例 5.3）v2v1v3v4v5v6第i年12345价格ai1111121213使用寿命0112233445费用bj568111

9、80,v116,v122,v130,v141,v153,v3/v416分析(fnx)：结点：V=v1，v6， vi表示第i年初；边： E=(vi，vj) 表示第i年初购买，用至第j年初；i= 1,5; j= 2,6权cij： i年初 j年初的费用，即cij= i年初购买费+（j-i）年里的维修费3022415916223041172331172318共六十九页v2v1v3v4v5v60,v116,v122,v130,v141,v153,v3/v4163022415916223041172331172318共六十九页截集概念(ginin)复习例. 如图所示的网络中，弧旁数字为(cij ,fij)

10、v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）确定所有的截集；（2）求最小截集的容量(rngling)；（3）证明图中的流为最大流；最大流问题举例共六十九页v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）所有(suyu)的截集： V1=vs，截集为(vs,v1), (vs,v2)，截量为：6共六十九页v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）所有(suyu)的截集： V1=vs，截集为(vs,v1), (vs,v2)，截量为：6V1=vs ,v

11、1，截集为(vs,v2), (v1,vt)，截量为：7共六十九页v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）所有(suyu)的截集： V1=vs，截集为(vs,v1), (vs,v2)，截量为：6V1=vs ,v1，截集为(vs,v2), (v1,vt)，截量为：7V1=vs ,v2，截集为，截量为：7共六十九页v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）所有(suyu)的截集： V1=vs，截集为(vs,v1), (vs,v2)，截量为：6V1=vs ,v1，截集为(vs,v2), (v1

12、,vt)，截量为：7V1=vs ,v2，截集为，截量为：7V1=vs ,v3，截集为，截量为：12共六十九页v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）所有(suyu)的截集： V1=vs，截集为(vs,v1), (vs,v2)，截量为：6V1=vs ,v1，截集为(vs,v2), (v1,vt)，截量为：7V1=vs ,v2，截集为，截量为：7V1=vs ,v3，截集为，截量为：12V1=vs ,v1,v2，截集为，截量为：5共六十九页v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）所有(su

13、yu)的截集： V1=vs，截集为(vs,v1), (vs,v2)，截量为：6V1=vs ,v1，截集为(vs,v2), (v1,vt)，截量为：7V1=vs ,v2，截集为，截量为：7V1=vs ,v3，截集为，截量为：12V1=vs ,v1,v2，截集为，截量为：5共六十九页v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（2）最小截量min C (V1,V2)= 5；（3）v(f*)=5= min C (V1,V2) f*是最大流。共六十九页例 有三个发电站v1,v2,v3，发电能力分别(fnbi)为15、10和40兆瓦，经输电网可把电力送到8号

14、地区，电网能力如图所示。求三个发电站输到该地区的最大电力。v2v1v3v4v5v6v7v8401530154510151020v01015401020151515 10201020201535共六十九页例、图中A、B、C、D、E、F分别表示陆地和岛屿，表示桥梁及其编号(bin ho)。河两岸分别互为敌对的双方部队占领，问至少应切断几座桥梁（具体指出编号(bin ho)）才能达到阻止对方部队过河的目的。试用图论方法进行分析。ABDEFC共六十九页分析：转化为一个(y )网络图，弧的容量为两点间的桥梁数。则问题(wnt)为求最小截。ABDEFCABCDEF211111222222共六十九页分析：转

15、化为一个(y )网络图，弧的容量为两点间的桥梁数。则问题(wnt)为求最小截。答案：最小截为AE、CD、CFABDEFCABCDEF211111222222共六十九页例、有一批人从我国A城赴俄罗斯B城，可能的旅行(lxng)路线如图： 边防队拟建立(jinl)足够数量检查站以便使每辆汽车至少必经过一个检查站，建立(jinl)检查站的费用根据各路段条件有所不同（如图数字所示），求最小费用解。aBAbcdefg468232573843764（分析：最小截问题）共六十九页例、过纽约ALBANY的北-南高速公路，路况通过能力如下图所示，图中弧上数字单位(dnwi)：千辆/小时。求（1）该路网能承受的北

16、-南向最大流量；（2）若要扩充通过能力，应在那一组路段上扩充，说明原因。2143562366241331进入Albany（北）离开Albany（南）共六十九页案例：垃圾处理问题 某地区有3个城镇，各城镇每天产生(chnshng)的垃圾要运往该地区的4个垃圾处理场处理，现考虑各城镇到各处理场的道路对各城镇垃圾外运的影响。假设各城镇每日产生(chnshng)的垃圾量、各处理场的日处理能力及各条道路（可供运垃圾部分）的容量（其中容量为0表示无此直接道路）如右表所示，试用网络流方法分析目前的道路状况能否使所有垃圾都运到处理场得到处理，如果不能，应首先拓宽哪条道路。处理场城镇1234垃圾量1302010

17、05020020407035040205080处理量60409030共六十九页共六十九页共六十九页共六十九页共六十九页共六十九页参考答案：本题可化为最大流问题，先构造如下网络图，图中si表示(biosh)第i天可提供3车的“源”。 现该公司接到在今后(jnhu)4天内为A、B、C三个项目运送T的任务，三个项目对T的需求量分别为3、4、5车。受交通限制，第1天去B的道路不通行；第2天去A的道路不通行；第3天去C的道路不通行；另每天至多有2台车为一个项目运送T。 共六十九页用观察法得到可行流，进一步用标号(bioho)法得到最大流，可满足三个项目的需求，即能完成任务。运输方案见图中各弧上的流量（不

18、带括弧的数字）。本题有多个最优解，下图只是其一。 共六十九页网络(wnglu)计划补充例共六十九页共六十九页(1) 绘制(huzh)的网络图如下：共六十九页共六十九页另一补充(bchng)例共六十九页共六十九页共六十九页共六十九页共六十九页共六十九页共六十九页补充(bchng)练习共六十九页共六十九页共六十九页共六十九页共六十九页补充(bchng)练习共六十九页共六十九页共六十九页(1) 共六十九页(2)方案2网络计划图（图中结点(ji din)时间只供阅卷参考），关键线路B-E-A-D-H，计算工期43天。共六十九页(3)将比原计划(jhu)拖后1天；(4)工作D赶工(n n)（缩短）1天，工作F赶工(n n)（缩短）1天。共六十九页共六十九页共六十九页共六十九页内容摘要第二章 图论与网络分析补充。要求设计一个最经济的煤气管道路线，并求