运筹学全套配套课件朱道立 ch09.ppt

《运筹学全套配套课件朱道立 ch09.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本章主要讨论图论基本概念、理论和方法以及最短路问题、最大流问题和最小费用流问题等网络优化模型及其基本算法。第九章网络优化模型目录图与网络树最短路问题最大流问题最小费用流问题目录图与网络树最短路问题最大流问题最小费用流问题基本概念：顶点、弧、有向图、无向图、链、道路、环、连通图、连通子图、次1234123412345213次道路顶点无向图链有向图弧环连通图弧是由一对有序的顶点组成，表示了两个顶点之间可能运动的方向连通子图由顶点集和弧组成的图称为有向图由顶点集和边组成的图称为无向图链有一序列弧，如果每一个弧与前一个弧恰有一个公

2、共顶点，则称这一序列弧为一个链。道路如果链中每一个弧的终点是下面一个弧的起点，则这个链称为一个道路。环连接a点与b点的一条链，如果a与b是同一个点时，称此链为环。连通图一个图中任意两点间至少有一个链相连，则称此图为连通图。任何一个不连通图都可以分为若干个连通子图，每一个子图称为原图的一个分图。次:以a点为顶点的边的条数称为顶点的次网络点或边带有某种数量指标的图叫网络图，简称网络。与点或边有关的某些数量指标，我们经常称之为权，权可以代表如距离、费用、容量等。左图可以看作：从发电厂（节点1）向某城市（节点6）输送电力，必须通过

3、中转站（节点2，3，4，5）转送，边上数字代表两节点间的距离。电力公司希望选择合适的中转站，使从电厂到城市的传输路线最短。一个输油管道网。节点1表示管道的起点，节点6表示管道的终点，节点2到5表示中转站，旁边的数字表示该段管道能通过的最大输送量。应怎样安排输油线路，使从节点1到节点6的总输送量最大？一张城市分布图。现在要在各城市之间架设电话线，应如何架设，使各城市之间既能通话，又使总的架设路线最短？目录图与网络树最短路问题最大流问题最小费用流问题树：连通且不含环的无向图树的性质：任意两顶点之间必有一条且仅有一条链。去掉任一

4、条边，则树成为不连通图。不相邻的两个顶点间添上一条边，恰好得到一个环。部分图、生成子图、部分树部分图生成子图部分树如果V1V，E1E则称G1为G的部分图；设G=(V，E)和G1=(V1，E1)如果G1=(V1，E1)，G=(V，E)，并且V1V，,则称G1为G的生成子图；如果G=(V，E)的部分图G1=(V，E1)是树，则称G1为G的一个部分树。最小生成树：具有最小权的生成树1325464332322最小生成树不一定唯一目录图与网络树最短路问题最大流问题最小费用流问题最短路问题从一特殊的节点出发，找出从该节点到网络中

5、任何其它节点的最短路径问题某人买了一辆价值1200美元的新车，一辆车每年的维护费用依赖于年初时的车龄，具体费用见下表。为了避免旧车的高维护费用，他决定卖掉旧车买新车。旧车的价格依赖于交易时的车龄，见下表。为计算简单起见，假设任何时间新车的价格不变均为1200美元。他希望在今后5年内的净费用最小（即：净费用=购买价+维护价-售出价）。车龄每年的维护费用交易费用012345200040005000900012000700060002000100001234562177777121212213131441221算法1325464

6、332322第0步：P(1)=0,T(i)=+∞；第1步：与1相连的标号为2,3，均是T标号，修改2,3的标号，T(2)=min{T(2),P(1)+w12}=4,T(3)=3；在所有的T标号中，3的标号最小，改3的标号为P(3)=3；第2步：修改与3相连的T标号；在所有剩下的T标号中，2的标号最小，改为P(2)=4；第3步：修改与2相连的T标号；在所有剩下的T标号中，5的标号最小，改为P(5)=6；第4步：修改与5相连的T标号；在所有剩下的T标号中，4的标号最小，改为P(4)=7；第5步：修改与4相连的T标号；只剩下节点

7、6是T标号，修改6的标号，P(6)=8。从节点6开始回退，得到最短路。P(1)=0T(3)=+∞T(2)=+∞T(3)=3T(5)=+∞P(3)=3T(5)=6T(2)=4T(4)=+∞T(6)=+∞P(2)=4T(4)=7P(5)=6T(6)=8P(4)=7P(6)=8P(6)=8P(5)=6P(3)=3P(1)=0例：从发电厂（记为节点1）向某城市（记为节点6）输送电，必须通过中转站（记为节点2，3，4，5）转送。图给出了两节点间的距离。电力公司希望选择合适的中转站，使从电厂到城市的传输路线最短。即从节点1到节点6的最

8、短路径。这就是一个最短路问题。用Excel求解最短路算法净流量=流出该节点的流量—流入该节点的流量中间节点的平衡值为0，起点为1，终点为-1。各个点的净流量等于平衡值最短路平衡流P(6)=8P(5)=6P(3)=3P(1)=0城市出租车公司在纽约市为出租车司机已经确定了10个搭乘车站。为了减少运行时间，