网络最优化问题精编版

1、 Copyright 2011 北京工商大学商学院北京工商大学商学院 2 无限配送公司的问题无限配送公司的问题 无限配送公司有两个工厂生产产品，这无限配送公司有两个工厂生产产品，这 些产品需要运到两个仓库里些产品需要运到两个仓库里 工厂工厂1 1生产生产8080个单位个单位 工厂工厂2 2生产生产7070个单位个单位 仓库仓库1 1需要需要6060个单位个单位 仓库仓库2 2需要需要9090个单位个单位 Copyright 2011 北京工商大学商学院北京工商大学商学院 3 无限配送公司的问题无限配送公司的问题 在工厂在工厂1 1和仓库和仓库1 1之间以及工厂之间以及工厂2 2和仓和仓 库库2

2、 2之间各有一条铁路运输轨道之间各有一条铁路运输轨道 卡车司机至多可以从工厂运输卡车司机至多可以从工厂运输5050 个单位到配送中心，然后可以从个单位到配送中心，然后可以从 配送中心运输配送中心运输5050个单位到仓库个单位到仓库 Copyright 2011 北京工商大学商学院北京工商大学商学院 4 配送网络配送网络 Copyright 2011 北京工商大学商学院北京工商大学商学院 5 配送网络的数据配送网络的数据 Copyright 2011 北京工商大学商学院北京工商大学商学院 6 最小费用流问题的网络模型最小费用流问题的网络模型 Copyright 2011 北京工商大学商学院北京工

3、商大学商学院 7 每条路线应该运送多少每条路线应该运送多少 单位的产品？单位的产品？ 无限配送公司的问题无限配送公司的问题 Copyright 2011 北京工商大学商学院北京工商大学商学院 8 最优解最优解 Copyright 2011 北京工商大学商学院北京工商大学商学院 9 最小费用流问题的术语最小费用流问题的术语 所有最小费用流问题都是用带有通 过其中的流的网络表示的 网络中的圆圈被称为节点 如果节点产生的净流量流出减去流入 是一个确定的正数的话，这个节点就 是供应点 如果节点产生的净流量是一个确定的 负数的话，那么这个节点就称为需求 点 Copyright 2011 北京工商大学商学

4、院北京工商大学商学院 10 最小费用流问题的术语最小费用流问题的术语 如果节点产生的净流量恒为零，那么这个 节点就称为转运点，我们把流出节点的量 等于流入节点的量称为流量守恒 网络中的箭头称为弧 允许通过某一条弧的最大流量称为该 弧的容量 Copyright 2011 北京工商大学商学院北京工商大学商学院 11 最小费用流问题的假设最小费用流问题的假设 至少有一个节点是供应点 至少有一个节点是需求点 所有剩下的节点都是转运点 通过弧的流只允许沿着箭头的方向 流动，通过弧的最大流量取决于该 弧的容量如果流是双向的话，则需 要用一对箭头指向相反的弧来表示 Copyright 2011 北京工商大学

5、商学院北京工商大学商学院 12 最小费用流问题的假设最小费用流问题的假设 网络中有足够的弧提供足够的容 量，使得所有在供应点中产生的 流都能够达到需求点 在流的单位成本已知的前提下， 通过每一条弧的流的成本和流量 成正比 最小费用流问题的目标是在满足给定 需求的条件下，使得通过网络供应的 总成本最小或通过这样做使得总利润 最大化 Copyright 2011 北京工商大学商学院北京工商大学商学院 13 最小费用流问题的特征最小费用流问题的特征 具有可行解的特征：在以上假设下，当且 仅当供应点所提供的流量总和等于需求点 所需要的流量总和时，最小费用流问题有 可行解 具有整数解的特征：只要其所有的

6、供应、 需求和弧的容量都是整数值，那么任何 最小费用流问题的可行解就一定有所有 流量都是整数的最优解 Copyright 2011 北京工商大学商学院北京工商大学商学院 14 电子表格描述电子表格描述 Copyright 2011 北京工商大学商学院北京工商大学商学院 15 SUMIF SUMIF 函数函数 SUMIF公式可以简化节点流约束公式可以简化节点流约束 SUMIF(Range A, x, Range B) 区域区域A中的每一个量满足条件中的每一个量满足条件x时，时，SUMIF函函 数就会计算区域数就会计算区域B中相应内容之和中相应内容之和 节点节点x的净流出的净流出流出流出-流入流入

7、就等于就等于 SUMIF(“From labels”, x, “Flow”) SUMIF(“To labels”, x, “Flow”) Copyright 2011 北京工商大学商学院北京工商大学商学院 16 对每一个节点有一个约束，必须遵循对每一个节点有一个约束，必须遵循“流量流量 守恒规则守恒规则” 转运问题：净流量=流出量-流入量 最小成本网络流中将流量守恒规则应用于每个节点 总供给总需求流出量-流入量=供给或需求 总供给=供给或需求 总供给=总需求流出量-流入量=供给或需求 Copyright 2011 北京工商大学商学院北京工商大学商学院 17 对每一个节点有一个约束，必须遵循对每

8、一个节点有一个约束，必须遵循“流量流量 守恒规则守恒规则” 净流量=流入量-流出量 最小成本网络流中将流量守恒规则应用于每个节点 总供给总需求流入量-流出量=供给或需求 总供给总需求流入量-流出量=供给或需求 总供给=总需求流入量-流出量=供给或需求 Copyright 2011 北京工商大学商学院北京工商大学商学院 18 转运问题 Newark港和港和Jacksonville港接受到进口到美国港接受到进口到美国 的汽车分别为的汽车分别为200辆和辆和300辆。辆。 B城，城，G城，城，Y城，城，R城和城和M城的经销商分别需城的经销商分别需 要要100辆，辆，60辆，辆，170辆、辆、80辆和

9、辆和70辆汽车。辆汽车。 根据各个城市间的运输费用确定成本最小的根据各个城市间的运输费用确定成本最小的 运送汽车的方式。运送汽车的方式。 Copyright 2011 北京工商大学商学院北京工商大学商学院 19 净流量净流量= =流出量流出量- -流入量流入量 Copyright 2011 北京工商大学商学院北京工商大学商学院 20 净流量等于流入量净流量等于流入量- -流出量流出量 Copyright 2011 北京工商大学商学院北京工商大学商学院 21 请在电子表格里分别按照供给为正和供给 为负的情况，建立两种情况下的模型，并 求解比较 Copyright 2011 北京工商大学商学院北京

10、工商大学商学院 22 供给为正、需求为负时的电子表格模型 Copyright 2011 北京工商大学商学院北京工商大学商学院 23 供给为负、需求为正的电子表格模型 Copyright 2011 北京工商大学商学院北京工商大学商学院 24 分析最优解分析最优解 Copyright 2011 北京工商大学商学院北京工商大学商学院 25 广义网络流问题广义网络流问题 目前所考虑的网络流问题，从一条弧线出 来的流量与进入的流量一定是相等的。 事实上是这种情况吗？ Copyright 2011 北京工商大学商学院北京工商大学商学院 26 Coal Bank Hollow Coal Bank Hollo

11、w 再生公司再生公司 该公司使用两种不同的再生过程来将报纸、 混合纸、白色办公纸和纸板转化为纸浆。 从再生原料提出再生纸浆的数量和纸浆的 提取成本由于使用不同的再生过程而不同。 通过两种不同的再生过程产生的纸浆通过 其他处理转化为新闻用纸、包装用纸或高 质量打印纸。 两种处理过程的具体数据如下 Copyright 2011 北京工商大学商学院北京工商大学商学院 27 纸浆生产问题提取纸浆数据 再生过程再生过程1 再生过程再生过程2 原料原料每吨成本每吨成本 产出结果产出结果每吨成本每吨成本 产出结果产出结果 报纸报纸13 90%1285% 混合纸混合纸11 80%1385% 白色办白色办 公纸

12、公纸 9 95%1090% 纸板纸板13 75%1485% Copyright 2011 北京工商大学商学院北京工商大学商学院 28 最终纸浆产出结果 新闻用纸包装用纸打印纸 纸浆来源纸浆来源 每吨成本每吨成本 产出产出 每吨成本每吨成本 产出产出 每吨成本每吨成本 产出产出 过程1 5 95% 6 90% 8 90% 过程2 6 90% 8 95% 7 95% 如果有70吨报纸，50吨混合纸，30吨白色办公纸 和40吨纸板。 如何转化成60吨新闻用纸纸浆，40吨包装用纸纸 浆，50吨打印纸纸浆，成本最低。 使用供给为负，需求为正的方法 Copyright 2011 北京工商大学商学院北京工商

13、大学商学院 29 转化为最小费用流问题的网络图转化为最小费用流问题的网络图 Copyright 2011 北京工商大学商学院北京工商大学商学院 30 电子表格模型 Copyright 2011 北京工商大学商学院北京工商大学商学院 31 最优解分析 Copyright 2011 北京工商大学商学院北京工商大学商学院 32 流量守恒规则的应用流量守恒规则的应用 当不确定总供给和总需求的关系时，假设 供给大于需求 如果没有可行解，再更改为需求大于供给 Copyright 2011 北京工商大学商学院北京工商大学商学院 33 最小费用流问题的应用最小费用流问题的应用 通过配送网络的费用最小通过配送网

14、络的费用最小 现金流管理现金流管理 工厂协调产品组合工厂协调产品组合 Copyright 2011 北京工商大学商学院北京工商大学商学院 34 BMZBMZ公司的最大流问题公司的最大流问题 BMZBMZ公司是欧洲一家生产豪华汽车的制公司是欧洲一家生产豪华汽车的制 造商，其产品出口到美国尤为重要造商，其产品出口到美国尤为重要 BMZ公司的汽车尤其在加利福尼亚大受 欢迎，因此保持洛杉矶中心零部件的充 足供给，以便及时维修这些汽车就显得 特别重要了 Copyright 2011 北京工商大学商学院北京工商大学商学院 35 BMZBMZ公司的最大流问题公司的最大流问题 BMZ公司需要迅速执行一项计划，

15、下个月要 从位于斯图加特和德国的主要工厂运送尽可 能多的配件到洛杉矶的配送中心 配件运送数量的限制因素就是公司配送网络 的容量 Copyright 2011 北京工商大学商学院北京工商大学商学院 36 BMZ BMZ 公司配送网络公司配送网络 Copyright 2011 北京工商大学商学院北京工商大学商学院 37 BMZBMZ问题的网络模型问题的网络模型 Copyright 2011 北京工商大学商学院北京工商大学商学院 38 通过每一条运送路线应通过每一条运送路线应 该运送多少配件，才能该运送多少配件，才能 使从斯图加特到洛杉矶使从斯图加特到洛杉矶 的总流量最大？的总流量最大？ BMZBM

16、Z公司的最大流问题公司的最大流问题 Copyright 2011 北京工商大学商学院北京工商大学商学院 39 BMZBMZ公司的电子表格模型公司的电子表格模型 Copyright 2011 北京工商大学商学院北京工商大学商学院 40 最大流问题的假设最大流问题的假设 网络中所有流起源于一个节点，这个节点网络中所有流起源于一个节点，这个节点 叫作源叫作源 起点起点 ，所有的流终止于另一个节，所有的流终止于另一个节 点，这个节点叫作收点点，这个节点叫作收点 终点终点 。BMZBMZ问题问题 中的源和收点分别代表工厂和配送中心中的源和收点分别代表工厂和配送中心 其余所有的节点叫作转运点其余所有的节点

17、叫作转运点 通过每一个弧的流只允许沿着弧的箭头所通过每一个弧的流只允许沿着弧的箭头所 指方向流动。由源发出的所有的弧背向源，指方向流动。由源发出的所有的弧背向源， 而所有终结于收点的弧都指向收点而所有终结于收点的弧都指向收点 Copyright 2011 北京工商大学商学院北京工商大学商学院 41 最大流问题的假设最大流问题的假设 最大流问题的目标是使得从源到收点最大流问题的目标是使得从源到收点 的总流量最大。这个流量的大小可以的总流量最大。这个流量的大小可以 用两种等价的方法来衡量，分别叫作用两种等价的方法来衡量，分别叫作 从源点出发的流量和进入收点的流量从源点出发的流量和进入收点的流量 C

18、opyright 2011 北京工商大学商学院北京工商大学商学院 42 最大流问题和最小费用流问题区别最大流问题和最小费用流问题区别 最小费用流问题：供应点、需最小费用流问题：供应点、需 求点求点 最大流问题：源、收点最大流问题：源、收点 最小费用流问题的供应量和需最小费用流问题的供应量和需 求量都是固定的，而最大流问求量都是固定的，而最大流问 题的源和收点却不是题的源和收点却不是 最小费用流问题的供应点和需最小费用流问题的供应点和需 求点可能有多个，但最大流问求点可能有多个，但最大流问 题的源和收点只有一个题的源和收点只有一个 Copyright 2011 北京工商大学商学院北京工商大学商学

19、院 43 BMZ BMZ 公司具有多个供应点和需求点的案例公司具有多个供应点和需求点的案例 BMZBMZ公司在柏林还有一家更小的工厂公司在柏林还有一家更小的工厂 一旦洛杉矶配送中心出现缺货，位于西雅一旦洛杉矶配送中心出现缺货，位于西雅 图的配送中心就可以给有关的客户供应配图的配送中心就可以给有关的客户供应配 件件 Copyright 2011 北京工商大学商学院北京工商大学商学院 44 扩展的扩展的BMZBMZ问题的网络模型问题的网络模型 Copyright 2011 北京工商大学商学院北京工商大学商学院 45 扩展的扩展的BMZBMZ问题问题 通过每一条运送路线通过每一条运送路线 应该运送多

20、少配件，应该运送多少配件， 才能使从斯图加特和才能使从斯图加特和 柏林到洛杉矶和西雅柏林到洛杉矶和西雅 图的总流量最大？图的总流量最大？ Copyright 2011 北京工商大学商学院北京工商大学商学院 46 电子表格描述电子表格描述 Copyright 2011 北京工商大学商学院北京工商大学商学院 47 最大流问题的应用最大流问题的应用 通过配送网络的流量最大，如通过配送网络的流量最大，如BMZBMZ问题问题 通过从供应商到处理设施的公司供应网络的流通过从供应商到处理设施的公司供应网络的流 量最大量最大 通过管道运输系统运送的油量最大通过管道运输系统运送的油量最大 最大化通过输水系统的水

21、量最大化通过输水系统的水量 通过交通网络的车流量最大通过交通网络的车流量最大 Copyright 2011 北京工商大学商学院北京工商大学商学院 48 网络流与整数解网络流与整数解 使用单纯形法求解具有约束的右侧值是整数使用单纯形法求解具有约束的右侧值是整数 的任何最小成本的网络流模型，最优解自动的任何最小成本的网络流模型，最优解自动 取整。取整。 但是如果加入了副约束，这样不服从流量守但是如果加入了副约束，这样不服从流量守 恒规则，就不能保证问题的线性规划模型的恒规则，就不能保证问题的线性规划模型的 解是整数。解是整数。 Copyright 2011 北京工商大学商学院北京工商大学商学院 4

22、9 特殊建模的考虑特殊建模的考虑 26 5 4 31100 100 -75 0 0 -50 如果要求进入节点3的流量至少为50，进入节点4 的流量至少为60，如何建模？ Copyright 2011 北京工商大学商学院北京工商大学商学院 50 特殊建模的考虑特殊建模的考虑 辅助约束 -X13-X23=-50 -X14-X24=-60 必须加入虚节点或虚弧线 Copyright 2011 北京工商大学商学院北京工商大学商学院 51 特殊建模的考虑特殊建模的考虑 26 5 40 301100 100 -75 0 0 -50 如果要求进入节点3的流量至少为50，进入节点4 的流量至少为60，如何建模

23、？ 3 4 $0 L.B.= -50 $0 L.B.= -60 Copyright 2011 北京工商大学商学院北京工商大学商学院 52 特殊建模的考虑特殊建模的考虑 12 $8 $6 U.B.=35 Copyright 2011 北京工商大学商学院北京工商大学商学院 53 特殊建模的考虑特殊建模的考虑 1 2 $8 $6 U.B.=35 10 $0 Copyright 2011 北京工商大学商学院北京工商大学商学院 54 特殊建模的考虑特殊建模的考虑 24 $6 $3 U.B.=35 1 $4 3 U.B.=35 U.B.=30 $5,U.B.=40 100 100-80 -75 Copyr

24、ight 2011 北京工商大学商学院北京工商大学商学院 55 特殊建模的考虑特殊建模的考虑 24 $6 $3 U.B.=35 1 $4 3 U.B.=35 U.B.=30 $5,U.B.=40 -100 -100 +80 +75 0 U.B.=100 U.B.=100 200 $999 $999 Copyright 2011 北京工商大学商学院北京工商大学商学院 56 辅助约束与整数解辅助约束与整数解 加入辅助约束，则不会自己取整 需要加入整数约束 Copyright 2011 北京工商大学商学院北京工商大学商学院 57 里特城的消防队问题里特城的消防队问题 里特城是一个农村的小镇里特城是一

25、个农村的小镇 它的消防队要为包括许多农场社区在它的消防队要为包括许多农场社区在 内的大片地区提供服务内的大片地区提供服务 在这个地区有很多路，从消防站到任在这个地区有很多路，从消防站到任 何一个社区都有很多条路线可供选择何一个社区都有很多条路线可供选择 Copyright 2011 北京工商大学商学院北京工商大学商学院 58 里特城的道路系统里特城的道路系统 Copyright 2011 北京工商大学商学院北京工商大学商学院 59 最短路问题的网络规划最短路问题的网络规划 Copyright 2011 北京工商大学商学院北京工商大学商学院 60 从消防站到某个特定从消防站到某个特定 的农场社区

26、的最短路的农场社区的最短路 线是那条？线是那条？ 里特城的消防队问题里特城的消防队问题 Copyright 2011 北京工商大学商学院北京工商大学商学院 61 最短路问题的标号法最短路问题的标号法 q19591959年，年，DijkstraDijkstra提出提出 q算法步骤：算法步骤： v步骤步骤1 1：起点是已标号点，：起点是已标号点， 标号为标号为0 0 v步骤步骤2 2：从所有已标号点：从所有已标号点 向未标号点扩散，得到未向未标号点扩散，得到未 标号点的临时标号标号点的临时标号 Copyright 2011 北京工商大学商学院北京工商大学商学院 62 最短路问题的标号法最短路问题的

27、标号法 上述公式也用于更新临时标号点的临时标号 Copyright 2011 北京工商大学商学院北京工商大学商学院 63 最短路问题的标号法最短路问题的标号法 v步骤步骤3 3：某临时标号点：某临时标号点 的所有可能标号的最小的所有可能标号的最小 值即是其最终标号，此值即是其最终标号，此 时将该临时标号点标记时将该临时标号点标记 为已标号点，并记录其为已标号点，并记录其 前一节点前一节点 Copyright 2011 北京工商大学商学院北京工商大学商学院 64 最短路问题的标号法最短路问题的标号法 v步骤步骤4 4：重复步骤：重复步骤2 2和和3 3直至找到最直至找到最 短路线，此时得到的最终

28、标号即短路线，此时得到的最终标号即 为其最短路线的长度为其最短路线的长度 Copyright 2011 北京工商大学商学院北京工商大学商学院 65 最短路问题的标号法最短路问题的标号法 q优点：优点：DijkstraDijkstra的标号的标号 法是求解法是求解最短路问题最短路问题 的最优化算法，也是的最优化算法，也是 目前最好的算法，而目前最好的算法，而 且可以求得起点到各且可以求得起点到各 点的最短路点的最短路 Copyright 2011 北京工商大学商学院北京工商大学商学院 66 最短路问题的网络规划最短路问题的网络规划 Copyright 2011 北京工商大学商学院北京工商大学商学

29、院 67 电子表格描述电子表格描述 Copyright 2011 北京工商大学商学院北京工商大学商学院 68 最短路问题的假设最短路问题的假设 在网络中选择一条路，这条路始于某在网络中选择一条路，这条路始于某 一节点，这节点叫作源，终于另一个一节点，这节点叫作源，终于另一个 节点，这个节点叫作目标地节点，这个节点叫作目标地 连接两个节点的连线通常叫作边连接两个节点的连线通常叫作边允许允许 任一个方向的行进任一个方向的行进，虽然也允许存在，虽然也允许存在 弧弧只允许沿着一个方向行进只允许沿着一个方向行进 Copyright 2011 北京工商大学商学院北京工商大学商学院 69 最短路问题的假设最

30、短路问题的假设 和每条边相关的一个非负数，叫作该边的长度和每条边相关的一个非负数，叫作该边的长度 注意：在网络中，除了在边的旁边表明了其长注意：在网络中，除了在边的旁边表明了其长 度的准确数字以外，所画的每一条边的长度并不度的准确数字以外，所画的每一条边的长度并不 表明其真实的长度表明其真实的长度 目标是寻找从源点到目标地的最短路线目标是寻找从源点到目标地的最短路线 总长度总长度 最小的路最小的路 Copyright 2011 北京工商大学商学院北京工商大学商学院 70 最短路问题的应用最短路问题的应用 行进的总距离最小行进的总距离最小 一系列活动的总成本最小一系列活动的总成本最小 一系列活动

31、的总时间最小一系列活动的总时间最小 Copyright 2011 北京工商大学商学院北京工商大学商学院 71 总成本最小的例子总成本最小的例子: : 莎拉的汽车基金莎拉的汽车基金 莎拉刚刚高中毕业莎拉刚刚高中毕业 在毕业典礼上，她的父母给了她在毕业典礼上，她的父母给了她2100021000美美 元的汽车基金帮助她购买并保养一辆使用元的汽车基金帮助她购买并保养一辆使用 了三年的二手车，以供她上大学使用了三年的二手车，以供她上大学使用 Copyright 2011 北京工商大学商学院北京工商大学商学院 72 总成本最小的例子总成本最小的例子: : 莎拉的汽车基金莎拉的汽车基金 由于开车费用和维修费

32、用随着汽车的老化 而飞速上涨，所以，如果能够最小化总的 净成本，莎拉可能在接下来的三个夏天里， 一次或多次折价将她的汽车置换为其他使 用了三年的二手车。四年后，莎拉的父母 会把她的旧车置换成一辆新车，作为莎拉 的毕业礼物。 Copyright 2011 北京工商大学商学院北京工商大学商学院 73 莎拉的成本数据莎拉的成本数据 Copyright 2011 北京工商大学商学院北京工商大学商学院 74 总成本最小的例子总成本最小的例子: : 莎拉的汽车基金莎拉的汽车基金 在接下来的三个夏天在接下来的三个夏天 里，莎拉应该何时折里，莎拉应该何时折 价卖掉她的汽车？如价卖掉她的汽车？如 何考虑？如何转

33、换成何考虑？如何转换成 最短路问题？最短路问题？ Copyright 2011 北京工商大学商学院北京工商大学商学院 75 最短路的描述最短路的描述 权权= =购买成本购买成本+ +总使用和维护成本总使用和维护成本- -销售收入销售收入 Copyright 2011 北京工商大学商学院北京工商大学商学院 76 电子表格描述电子表格描述 Copyright 2011 北京工商大学商学院北京工商大学商学院 77 总时间最小化的例子总时间最小化的例子: : 奎克公司奎克公司 q 奎克公司获悉它的一个竞争对手计划 将把一种很有销售潜力的新产品投放 市场 q 奎克公司也一直在研制一种类似的产 品，并计划

34、在20个月后投放市场 Copyright 2011 北京工商大学商学院北京工商大学商学院 78 总时间最小化的例子总时间最小化的例子: : 奎克公司奎克公司 q 奎克公司的管理者希望迅速推出产品去参 与竞争 q 现在还有四个阶段没有完成，每个阶段都 可以正常水平、优先水平和应急水平加速 完成。正常水平由于后三个阶段的实施速 度太慢而被排除了 q 有3000万美元用于这四个阶段的实施过程 Copyright 2011 北京工商大学商学院北京工商大学商学院 79 各阶段所需的时间和成本各阶段所需的时间和成本 Copyright 2011 北京工商大学商学院北京工商大学商学院 80 总时间最小化的例

35、子总时间最小化的例子: : 奎克公司奎克公司 每个阶段应该以什么每个阶段应该以什么 样的速度进行？如何样的速度进行？如何 考虑？如何转换成最考虑？如何转换成最 短路问题？短路问题？ Copyright 2011 北京工商大学商学院北京工商大学商学院 81 最短路问题的描述最短路问题的描述 虚拟 节点 节点节点: ( : (阶段阶段, , 剩余资金剩余资金) )；弧；弧: : 活动；权活动；权: : 时间时间 Copyright 2011 北京工商大学商学院北京工商大学商学院 82 电子表格描述电子表格描述 Copyright 2011 北京工商大学商学院北京工商大学商学院 83 最优解最优解

36、Copyright 2011 北京工商大学商学院北京工商大学商学院 84 最小支撑树最小支撑树: 摩登公司的问题摩登公司的问题 摩登公司决定铺设最先进的光纤网络系统 以便在其主要中心之间提供高速通信，包 括数据、声音和视频等 为了充分利用光纤技术在中心之间高速通 信的优势，不需要在每两个中心之间都用 一条光缆把它们直接连接起来，那些需要 光缆直接连接的中心有一系列的光缆连接 它们 Copyright 2011 北京工商大学商学院北京工商大学商学院 85 摩登公司主要中心、纤维光缆的可能布局及成本摩登公司主要中心、纤维光缆的可能布局及成本 Copyright 2011 北京工商大学商学院北京工商

37、大学商学院 86 应该铺设哪些光纤以应该铺设哪些光纤以 便在每两个中心之间便在每两个中心之间 提供高速通信？提供高速通信？ 最小支撑树最小支撑树: 摩登公司的问题摩登公司的问题 Copyright 2011 北京工商大学商学院北京工商大学商学院 87 最小支撑树的假设最小支撑树的假设 给你网络中的节点，但没有给你边。或者，给 你可供选择的边和如果把它插入到网络中后的 每条边的正的成本或者相似的度量 在设计网络时你希望通过插入足够的边，以满 足每两个节点之间都存在一条路的需要 目标是寻找一种方法，使得在满足要求的同时 总成本最小 Copyright 2011 北京工商大学商学院北京工商大学商学院

38、 88 最小支撑树的算法最小支撑树的算法 选择第一条边：选择成本最低的备选边选择第一条边：选择成本最低的备选边 选择下一条边：在一个已经有一条边连选择下一条边：在一个已经有一条边连 接的节点和另一个还没有边连接的节点接的节点和另一个还没有边连接的节点 之间选择成本最低的备选边之间选择成本最低的备选边 重复第二个步骤，直到所有的节点都重复第二个步骤，直到所有的节点都 有一条边有一条边 可能会有多于一条边可能会有多于一条边 与其与其 相连。此时就得到了最优解相连。此时就得到了最优解 最小支撑最小支撑 树树) ) 当有几条边同时是成本最低的边时，当有几条边同时是成本最低的边时， 任意选择一条边不会影

39、响最后的最优任意选择一条边不会影响最后的最优 值值 Copyright 2011 北京工商大学商学院北京工商大学商学院 89 摩登公司的算法应用摩登公司的算法应用: 第一步第一步 Copyright 2011 北京工商大学商学院北京工商大学商学院 90 摩登公司的算法应用摩登公司的算法应用: 第二步第二步 Copyright 2011 北京工商大学商学院北京工商大学商学院 91 摩登公司的算法应用摩登公司的算法应用: 第三步第三步 Copyright 2011 北京工商大学商学院北京工商大学商学院 92 摩登公司的算法应用摩登公司的算法应用: 第四步第四步 Copyright 2011 北京工

40、商大学商学院北京工商大学商学院 93 摩登公司的算法应用摩登公司的算法应用: 第五步第五步 Copyright 2011 北京工商大学商学院北京工商大学商学院 94 摩登公司的算法应用摩登公司的算法应用: 最后一步最后一步 Copyright 2011 北京工商大学商学院北京工商大学商学院 95 最优解最优解 Copyright 2011 北京工商大学商学院北京工商大学商学院 96 最小支撑树问题最小支撑树问题 避圈法：开始选一条最小权避圈法：开始选一条最小权 的边，以后每一步中，总从的边，以后每一步中，总从 未被选取的边中选一条权最未被选取的边中选一条权最 小的边，并使之与已被选取小的边，并

41、使之与已被选取 的边不构成圈的边不构成圈( (如果有两条或如果有两条或 两条以上的边都是权最小的两条以上的边都是权最小的 边，则从中任选一条边，则从中任选一条) ) Copyright 2011 北京工商大学商学院北京工商大学商学院 97 最小支撑树问题最小支撑树问题 q算例 A B C D E F G H I 6 3 1 2 2 1 6 10 4 2 6 3 2 4 3 Copyright 2011 北京工商大学商学院北京工商大学商学院 98 最小支撑树问题最小支撑树问题 破圈法：任取一个圈，从圈破圈法：任取一个圈，从圈 中去掉权最大的边中去掉权最大的边( (如果有两如果有两 条或两条以上的

42、边都是权最条或两条以上的边都是权最 大的边，则任意去掉其中一大的边，则任意去掉其中一 条条) )。在余下的图中，重复这。在余下的图中，重复这 个步骤，一直到图中不含圈个步骤，一直到图中不含圈 为止。去边的同时必须保证为止。去边的同时必须保证 图的连通性图的连通性 Copyright 2011 北京工商大学商学院北京工商大学商学院 99 最小支撑树问题最小支撑树问题 q算例 A B C D E F G H I 6 3 1 2 2 1 6 10 4 2 6 3 2 4 3 Copyright 2011 北京工商大学商学院北京工商大学商学院 100 最小支撑树的应用最小支撑树的应用 电信网络电信网络

43、计算机网络、电话专用线计算机网络、电话专用线 网络、有线电视网络等等网络、有线电视网络等等的设计的设计 低负荷运输网络的设计，使得网络低负荷运输网络的设计，使得网络 中提供链接的部分中提供链接的部分如铁路、公路等如铁路、公路等 的总成本最小的总成本最小 Copyright 2011 北京工商大学商学院北京工商大学商学院 101 最小支撑树的应用最小支撑树的应用 高压输电线路网络的设计高压输电线路网络的设计 连接多个场所的管道网络设计连接多个场所的管道网络设计 电器设备线路网络电器设备线路网络如数字计算机如数字计算机 系统系统的设计，使得线路总长度最的设计，使得线路总长度最 短短 Copyright 2011 北京工商大学商学院北京工商大学商学院 102 规划问题总结规划问题总结 q线性规划线性规划 v资源分配问题资源分配问题 v成本收益平衡问题成本收益平衡问题 v网络配送问题：运输问题，指网络配