第六章-运筹学图与网络优化PPT学习教案

1、会计学1第六章第六章-运筹学图与网络优化运筹学图与网络优化第1页/共59页北京徐州青岛天津济南武汉南京上海连云港郑州第2页/共59页v甲v乙v丙v丁v戊第3页/共59页第4页/共59页v2v1e3e2e1v2a1a2a3v3v1第5页/共59页简单图：不含环和多重边的无向图。多重图：不含环，但含有多重边的无向图。第6页/共59页第7页/共59页v2e1v4v3v1e2v2v1e3e2e1不连通图第8页/共59页第9页/共59页第10页/共59页11221111(),(121)KKKtttkiiiiiiiiiiiiGvevevevev vtkvv无向图 中一个点、边交错序列， ， ， ， ,，若

2、满足， ， ，称这个点边序列为连接 ，的链。11kkiiiiGvvvv无向图 中，连结 与 的一条链，当 与是同一个点时，称此链为圈。第11页/共59页第12页/共59页v2e1v4v3v1e2v5v6v7e3e4e5e6e7e8e9第13页/共59页11221111()121KKKtttkiiiiiiiiiiiiDvavavavavvtkvv有向图 中一条链， ， ， ,，若满足=( ，)(， ， ，)，则称这个点弧序列为从 到的一条路。112211()KKKiiiiiiiDvavavavG DD有向图 中一个点、弧交错序列， ， ， ,，若此序列在基础图 ( )中所对应的点边序列是一条链，

3、则称这个点弧序列是 的链。第14页/共59页11kkiiiiDvvvv有向图 中，连结 与 的一条链，当 与是同一个点时，称此路为回路。第15页/共59页v2a1v4v3v1a2v5v6v7a6a5a4a3a10a9a8a7a11第16页/共59页第17页/共59页第18页/共59页v2v4v1v3v5第19页/共59页()()GVEGVEVVEEGG设图，称是 的一个支撑子图。第20页/共59页v2v4v1v3v5v2v4v1v3v5支撑子图第21页/共59页()ijijijijGVEGvvwGwvv图，对 中每一条边 ，相应地有一个数，则称图 为赋权图，称为边 ，上的权，表示距离、时间、费

4、用等。( )( )()ijijvvTTGTTw Tw TwTw TGTG，设 是 的一个支撑树，称 中所有边的权之和为支撑树 的权，记为，即。如果支撑树的权是 所有支撑树的权中最小的，则称为 的最小支撑树。第22页/共59页第23页/共59页v3v2v4v1v5v6615572344第24页/共59页破圈法求解例3第25页/共59页2314974363231457435741第26页/共59页()()()()min( )ijijijststijvvPDVAvvwvvDPvvw PwPPw P，赋权有向图，图中各弧，有权， 为图 中任意两点，求一条路 ，使它是从 到 的所有路中总权最小的路，即。

5、定义：路 的权是 中所有弧的权之和，记为第27页/共59页v41v6v2v16v5v74106v3310124v8v9322263第28页/共59页11111sntstsnsnvvvvvvvvvvv若序列， ， ，是从 到 的最短路，则序列， ， ，必为从 到的最短路。第29页/共59页第30页/共59页()min()( )jjiijT vT vP v，()()min()jjjjP vT vT vvT是 标号Dijkstra方法求解例4第31页/共59页v4v6v2v1v5v7v3v84677956444155第32页/共59页v3v45v6v2v14v5v71487561246第33页/共5

6、9页v3v4v6v2v1v5v759118751225612第34页/共59页第35页/共59页v3v45v6v2v14v5v71487561256第36页/共59页第37页/共59页vsv1v285-5权为负数第38页/共59页v1v3v4v7v2v5v8v93424116562784v653第39页/共59页第40页/共59页项目第1年 第2年 第3年 第4年 第5年购买费 11 11 12 12 13机器役龄 0-1 1-2 2-3 3-4 4-5维修费 5 6 8 11 18第41页/共59页第42页/共59页1641302218171617413022592331v1v2v3v4v5

7、v623第43页/共59页v38v5v2v110v4v63654113517网络流量最大习题6-4第44页/共59页第45页/共59页第46页/共59页v38v5v2v110v4v63654113517v3v5v2v1v4v6可行流第47页/共59页ij弧第48页/共59页0()0()ijijiiijijiifcvvfcvv ， ， ，第49页/共59页v38v5v2v110v4v63654113517链第50页/共59页v3v5v2v1v4v61054317增广链第51页/共59页标号已检查点标号点标号未检查点未标号点第52页/共59页第53页/共59页()()ijijijijijmin cfvvfvv令，；，()()()ijijijijijijijfvvffvvfvv ，且有，第54页/共59页v1(5,1)v3v2vs(3,3)v4vt(1,1)(2,2)(1,1)(5,3)(3,0)(4,3)(2,1)第55页/共59页(10,10)vtv3v6v2vs(14,10)v5(5,5)(6,4)(3,1)(9,9)(6,6)(