网络最优化问题PPT课件.ppt

7 1最小费用流问题7 2案例研究 BMZ公司的最大流问题7 3最大流问题7 4最短路问题 里特城的消防队问题7 4最短路问题 一般特征7 4最短路问题 最小化莎拉的总成本问题7 4最短路问题 最小化奎克公司总时间问题7 5最小支撑树问题 摩登公司问题 主要内容 无限配送公司的问题 无限配送公司有两个工厂生产产品 这些产品需要运到两个仓库里工厂1生产80个单位工厂2生产70个单位 最小费用流问题 仓库1需要60个单位仓库2需要90个单位 无限配送公司的问题 在工厂1和仓库1之间以及工厂2和仓库2之间各有一条铁路运输轨道卡车司机至多可以从工厂运输50个单位到配送中心 然后可以从配送中心运输50个单位到仓库 配送网络 配送网络的数据 最小费用流问题的网络模型 每条路线应该运送多少单位的产品 无限配送公司的问题 最优解 最小费用流问题的术语 所有最小费用流问题都是用带有通过其中的流的网络表示的网络中的圆圈被称为节点如果节点产生的净流量 流出减去流入 是一个确定的正数的话 这个节点就是供应点如果节点产生的净流量是一个确定的负数的话 那么这个节点就称为需求点 最小费用流问题的术语 如果节点产生的净流量恒为零 那么这个节点就称为转运点 我们把流出节点的量等于流入节点的量称为流量守恒网络中的箭头称为弧允许通过某一条弧的最大流量称为该弧的容量 最小费用流问题的假设 至少有一个节点是供应点至少有一个节点是需求点所有剩下的节点都是转运点通过弧的流只允许沿着箭头的方向流动 通过弧的最大流量取决于该弧的容量 如果流是双向的话 则需要用一对箭头指向相反的弧来表示 最小费用流问题的假设 网络中有足够的弧提供足够的容量 使得所有在供应点中产生的流都能够达到需求点在流的单位成本已知的前提下 通过每一条弧的流的成本和流量成正比最小费用流问题的目标是在满足给定需求的条件下 使得通过网络供应的总成本最小 或通过这样做使得总利润最大化 最小费用流问题的特征 具有可行解的特征 在以上假设下 当且仅当供应点所提供的流量总和等于需求点所需要的流量总和时 最小费用流问题有可行解具有整数解的特征 只要其所有的供应 需求和弧的容量都是整数值 那么任何最小费用流问题的可行解就一定有所有流量都是整数的最优解 电子表格描述 SUMIF函数 SUMIF公式可以简化节点流约束SUMIF RangeA x RangeB 区域A中的每一个量满足条件x时 SUMIF函数就会计算区域B中相应内容之和节点x的净流出 流出 流入 就等于SUMIF Fromlabels x Flow SUMIF Tolabels x Flow 对每一个节点有一个约束 必须遵循 流量守恒规则 转运问题 净流量 流出量 流入量 对每一个节点有一个约束 必须遵循 流量守恒规则 净流量 流入量 流出量 转运问题 Newark港和Jacksonville港接受到进口到美国的汽车分别为200辆和300辆 B城 G城 Y城 R城和M城的经销商分别需要100辆 60辆 170辆 80辆和70辆汽车 根据各个城市间的运输费用确定成本最小的运送汽车的方式 净流量 流出量 流入量 净流量等于流入量 流出量 请在电子表格里分别按照供给为正和供给为负的情况 建立两种情况下的模型 并求解比较 供给为正 需求为负时的电子表格模型 供给为负 需求为正的电子表格模型 分析最优解 广义网络流问题 目前所考虑的网络流问题 从一条弧线出来的流量与进入的流量一定是相等的 事实上是这种情况吗 CoalBankHollow再生公司 该公司使用两种不同的再生过程来将报纸 混合纸 白色办公纸和纸板转化为纸浆 从再生原料提出再生纸浆的数量和纸浆的提取成本由于使用不同的再生过程而不同 通过两种不同的再生过程产生的纸浆通过其他处理转化为新闻用纸 包装用纸或高质量打印纸 两种处理过程的具体数据如下 纸浆生产问题提取纸浆数据 最终纸浆产出结果 如果有70吨报纸 50吨混合纸 30吨白色办公纸和40吨纸板 如何转化成60吨新闻用纸纸浆 40吨包装用纸纸浆 50吨打印纸纸浆 成本最低 使用供给为负 需求为正的方法 转化为最小费用流问题的网络图 电子表格模型 最优解分析 流量守恒规则的应用 当不确定总供给和总需求的关系时 假设供给大于需求如果没有可行解 再更改为需求大于供给 最小费用流问题的应用 通过配送网络的费用最小现金流管理工厂协调产品组合 BMZ公司的最大流问题 BMZ公司是欧洲一家生产豪华汽车的制造商 其产品出口到美国尤为重要BMZ公司的汽车尤其在加利福尼亚大受欢迎 因此保持洛杉矶中心零部件的充足供给 以便及时维修这些汽车就显得特别重要了 最大流问题 BMZ公司的最大流问题 BMZ公司需要迅速执行一项计划 下个月要从位于斯图加特和德国的主要工厂运送尽可能多的配件到洛杉矶的配送中心配件运送数量的限制因素就是公司配送网络的容量 BMZ公司配送网络 BMZ问题的网络模型 通过每一条运送路线应该运送多少配件 才能使从斯图加特到洛杉矶的总流量最大 BMZ公司的最大流问题 BMZ公司的电子表格模型 最大流问题的假设 网络中所有流起源于一个节点 这个节点叫作源 起点 所有的流终止于另一个节点 这个节点叫作收点 终点 BMZ问题中的源和收点分别代表工厂和配送中心其余所有的节点叫作转运点通过每一个弧的流只允许沿着弧的箭头所指方向流动 由源发出的所有的弧背向源 而所有终结于收点的弧都指向收点 最大流问题的假设 最大流问题的目标是使得从源到收点的总流量最大 这个流量的大小可以用两种等价的方法来衡量 分别叫作从源点出发的流量和进入收点的流量 最大流问题和最小费用流问题区别 最小费用流问题 供应点 需求点最大流问题 源 收点最小费用流问题的供应量和需求量都是固定的 而最大流问题的源和收点却不是最小费用流问题的供应点和需求点可能有多个 但最大流问题的源和收点只有一个 BMZ公司具有多个供应点和需求点的案例 BMZ公司在柏林还有一家更小的工厂一旦洛杉矶配送中心出现缺货 位于西雅图的配送中心就可以给有关的客户供应配件 扩展的BMZ问题的网络模型 扩展的BMZ问题 通过每一条运送路线应该运送多少配件 才能使从斯图加特和柏林到洛杉矶和西雅图的总流量最大 电子表格描述 最大流问题的应用 通过配送网络的流量最大 如BMZ问题通过从供应商到处理设施的公司供应网络的流量最大通过管道运输系统运送的油量最大最大化通过输水系统的水量通过交通网络的车流量最大 网络流与整数解 使用单纯形法求解具有约束的右侧值是整数的任何最小成本的网络流模型 最优解自动取整 但是如果加入了副约束 这样不服从流量守恒规则 就不能保证问题的线性规划模型的解是整数 特殊建模的考虑 2 6 5 4 3 1 100 100 75 0 0 50 如果要求进入节点3的流量至少为50 进入节点4的流量至少为60 如何建模 特殊建模的考虑 辅助约束 X13 X23 50 X14 X24 60必须加入虚节点或虚弧线 特殊建模的考虑 2 6 5 40 30 1 100 100 75 0 0 50 如果要求进入节点3的流量至少为50 进入节点4的流量至少为60 如何建模 3 4 0L B 50 0L B 60 特殊建模的考虑 1 2 8 6 U B 35 特殊建模的考虑 1 2 8 6 U B 35 10 0 特殊建模的考虑 2 4 6 3 U B 35 1 4 3 U B 35 U B 30 5 U B 40 100 100 80 75 2020 1 7 55 特殊建模的考虑 2 4 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 辅助约束与整数解 加入辅助约束 则不会自己取整需要加入整数约束 里特城的消防队问题 里特城是一个农村的小镇它的消防队要为包括许多农场社区在内的大片地区提供服务在这个地区有很多路 从消防站到任何一个社区都有很多条路线可供选择 最短路问题 里特城的道路系统 最短路问题的网络规划 从消防站到某个特定的农场社区的最短路线是那条 里特城的消防队问题 最短路问题的标号法 1959年 Dijkstra提出算法步骤 步骤1 起点是已标号点 标号为0步骤2 从所有已标号点向未标号点扩散 得到未标号点的临时标号 最短路问题的标号法 上述公式也用于更新临时标号点的临时标号 最短路问题的标号法 步骤3 某临时标号点的所有可能标号的最小值即是其最终标号 此时将该临时标号点标记为已标号点 并记录其前一节点 最短路问题的标号法 步骤4 重复步骤2和3直至找到最短路线 此时得到的最终标号即为其最短路线的长度 最短路问题的标号法 优点 Dijkstra的标号法是求解最短路问题的最优化算法 也是目前最好的算法 而且可以求得起点到各点的最短路 最短路问题的网络规划 电子表格描述 最短路问题的假设 在网络中选择一条路 这条路始于某一节点 这节点叫作源 终于另一个节点 这个节点叫作目标地连接两个节点的连线通常叫作边 允许任一个方向的行进 虽然也允许存在弧 只允许沿着一个方向行进 最短路问题的假设 和每条边相关的一个非负数 叫作该边的长度 注意 在网络中 除了在边的旁边表明了其长度的准确数字以外 所画的每一条边的长度并不表明其真实的长度 目标是寻找从源点到目标地的最短路线 总长度最小的路 最短路问题的应用 行进的总距离最小一系列活动的总成本最小一系列活动的总时间最小 总成本最小的例子 莎拉的汽车基金 莎拉刚刚高中毕业在毕业典礼上 她的父母给了她21000美元的汽车基金帮助她购买并保养一辆使用了三年的二手车 以供她上大学使用 总成本最小的例子 莎拉的汽车基金 由于开车费用和维修费用随着汽车的老化而飞速上涨 所以 如果能够最小化总的净成本 莎拉可能在接下来的三个夏天里 一次或多次折价将她的汽车置换为其他使用了三年的二手车 四年后 莎拉的父母会把她的旧车置换成一辆新车 作为莎拉的毕业礼物 莎拉的成本数据 总成本最小的例子 莎拉的汽车基金 在接下来的三个夏天里 莎拉应该何时折价卖掉她的汽车 如何考虑 如何转换成最短路问题 最短路的描述 权 购买成本 总使用和维护成本 销售收入 电子表格描述 总时间最小化的例子 奎克公司 奎克公司获悉它的一个竞争对手计划将把一种很有销售潜力的新产品投放市场奎克公司也一直在研制一种类似的产品 并计划在20个月后投放市场 总时间最小化的例子 奎克公司 奎克公司的管理者希望迅速推出产品去参与竞争现在还有四个阶段没有完成 每个阶段都可以正常水平 优先水平和应急水平加速完成 正常水平由于后三个阶段的实施速度太慢而被排除了有3000万美元用于这四个阶段的实施过程 各阶段所需的时间和成本 总时间最小化的例子 奎克公司 每个阶段应该以什么样的速度进行 如何考虑 如何转换成最短路问题 最短路问题的描述 虚拟节点 节点 阶段 剩余资金 弧 活动 权 时间 电子表格描述 最优解 最小支撑树 摩登公司的问题 摩登公司决定铺设最先进的光纤网络系统以便在其主要中心之间提供高速通信 包括数据 声音和视频等为了充分利用光纤技术在中心之间高速通信的优势 不需要在每两个中心之间都用一条光缆把它们直接连接起来 那些需要光缆直接连接的中心有一系列的光缆连接它们 最小支撑树问题 摩登公司主要中心 纤维光缆的可能布局及成本 应该铺设哪些光纤以便在每两个中心之间提供高速通信 最小支撑树 摩登公司的问题 最小支撑树的假设 给你网络中的节点 但没有给你边 或者 给你可供选择的边和如果把它插入到网络中后的每条边的正的成本 或者相似的度量 在设计网络时你希望通过插入足够的边 以满足每两个节点之间都存在一条路的需要目标是寻找一种方法 使得在满足要求的同时总成本最小 最小支撑树的算法 选择第一条边 选择成本最低的备选边选择下一条边 在一个已经有一条边连接的节点和另一个还没有边连接的节点之间选择成本最低的备选边重复第二个步骤 直到所有的节点都有一条边 可能会有多于一条边 与其相连 此时就得到了最优解 最小支撑树 当有几条边同时是成本最低的边时 任意选择一条边不会影响最后的最优值 摩登公司的算法应用 第一步 摩登公司的算法应用 第二步 摩登公司的算法应用 第三步 摩登公司的算法应用 第四步 摩登公司的算法应用 第五步 摩登公司的算法应用 最后一步 最优解 最小支撑树问题 避圈法 开始选一条最小权的边 以后每一步中 总从未被选取的边中选一条权最小的边 并使之与已被选取的边不构成圈 如果有两条或两条以上的边都是权最小的边 则从中任选一条 最小支撑树问题 算例 最小支撑树问题 破圈法 任取一个圈 从圈中去掉权最大的边 如果有两条或两条以上的边都是权最大的边 则任意去掉其中一条 在余下的图中 重复这个步骤 一直到图中不含圈为止 去边的同时必须保证图的连通性 最小支撑树问题 算例 最小支撑树的应用 电信网络 计算机网络 电话专用线网络 有线电视网络等等 的设计低负荷运输网络的设计 使得网络中提供链接的部分 如铁路 公路等 的总成本最小 最小支撑树的应用 高压输电线路网络的设计连接多个场所的管道网络设计电器设备线路网络 如数字计算机系统 的设计 使得线路总长度最短 规划问题总结 线