Chapter网络最优化问题.ppt

Chapter 7. Network Optimization Problems 主要内容 7.1最小费用流问题 7.2案例研究：BMZ公司的最大流问题 7.3最大流问题 7.4最短路问题：里特城的消防队问题 7.4最短路问题：一般特征 7.4最短路问题：最小化莎拉的总成本问题 7.4最短路问题：最小化奎克公司总时间问题 7.5最小支撑树问题：摩登公司问题) 无限配送公司的问题 无限配送公司有两个工厂生产产品，这些产品需要运到两个仓库里 工厂1生产80个单位 工厂2生产70个单位 无限配送公司的问题 在工厂1和仓库1之间以及工厂2和仓库2之间各有一条铁路运输轨道 卡车司机至多可以从工厂运输50个单位到配送中心，然后可以从配送中心运输50个单位到仓库 配送网络 配送网络的数据 最小费用流问题的网络模型 无限配送公司的问题 最优解 最小费用流问题的术语 所有最小费用流问题都是用带有通过其中的流的网络表示的 网络中的圆圈被称为节点 如果节点产生的净流量[流出减去流入]是一个确定的正数的话，这个节点就是供应点 如果节点产生的净流量是一个确定的负数的话，那么这个节点就称为需求点 最小费用流问题的术语 如果节点产生的净流量恒为零，那么这个节点就称为转运点，我们把流出节点的量等于流入节点的量称为流量守恒 网络中的箭头称为弧 允许通过某一条弧的最大流量称为该弧的容量 最小费用流问题的假设 至少有一个节点是供应点 至少有一个节点是需求点 所有剩下的节点都是转运点 通过弧的流只允许沿着箭头的方向流动，通过弧的最大流量取决于该弧的容量[如果流是双向的话，则需要用一对箭头指向相反的弧来表示] 最小费用流问题的假设 网络中有足够的弧提供足够的容量，使得所有在供应点中产生的流都能够达到需求点 在流的单位成本已知的前提下，通过每一条弧的流的成本和流量成正比 最小费用流问题的目标是在满足给定需求的条件下，使得通过网络供应的总成本最小[或通过这样做使得总利润最大化] 最小费用流问题的特征 具有可行解的特征：在以上假设下，当且仅当供应点所提供的流量总和等于需求点所需要的流量总和时，最小费用流问题有可行解 具有整数解的特征：只要其所有的供应、需求和弧的容量都是整数值，那么任何最小费用流问题的可行解就一定有所有流量都是整数的最优解 电子表格描述 SUMIF 函数 SUMIF公式可以简化节点流约束 SUMIF(Range A, x, Range B) 区域A中的每一个量满足条件x时，SUMIF函数就会计算区域B中相应内容之和 节点x的净流出[流出-流入]就等于SUMIF(“From labels”, x, “Flow”) – SUMIF(“To labels”, x, “Flow”) 净流量=流出量-流入量 净流量等于流入量-流出量 请在电子表格里分别按照供给为正和供给为负的情况，建立两种情况下的模型，并求解比较 供给为正、需求为负时的电子表格模型 供给为负、需求为正的电子表格模型 分析最优解 广义网络流问题 目前所考虑的网络流问题，从一条弧线出来的流量与进入的流量一定是相等的。 事实上是这种情况吗？ Coal Bank Hollow 再生公司 该公司使用两种不同的再生过程来将报纸、混合纸、白色办公纸和纸板转化为纸浆。从再生原料提出再生纸浆的数量和纸浆的提取成本由于使用不同的再生过程而不同。 通过两种不同的再生过程产生的纸浆通过其他处理转化为新闻用纸、包装用纸或高质量打印纸。 两种处理过程的具体数据如下 纸浆生产问题提取纸浆数据 最终纸浆产出结果 如果有70吨报纸，50吨混合纸，30吨白色办公纸和40吨纸板。 如何转化成60吨新闻用纸纸浆，40吨包装用纸纸浆，50吨打印纸纸浆，成本最低。 使用供给为负，需求为正的方法 转化为最小费用流问题的网络图 电子表格模型 最优解分析 流量守恒规则的应用 当不确定总供给和总需求的关系时，假设供给大于需求 如果没有可行解，再更改为需求大于供给 最小费用流问题的应用 BMZ公司的最大流问题 BMZ公司是欧洲一家生产豪华汽车的制造商，其产品出口到美国尤为重要 BMZ公司的汽车尤其在加利福尼亚大受欢迎，因此保持洛杉矶中心零部件的充足供给，以便及时维修这些汽车就显得特别重要了 BMZ公司的最大流问题 BMZ公司需要迅速执行一项计划，下个月要从位于斯图加特和德国的主要工厂运送尽可能多的配件到洛杉矶的配送中心 配件运送数量的限制因素就是公司配送网络的容量 BMZ 公司配送网络 BMZ问题的网络模型 BMZ公司的最大流问题 BMZ公司的电子表格模型 最大流问题的假设 最大流问题的假设 最大流问题和最小费用流问题区别 最小费用流问题：供应点、需求点 最大流问题：源、收点 最小费用流问题的供应量和需求量都是固定的，而最大流问题的源和收点却不是