Chapter07-网络最优化问题

Chapter7.NetworkOptimizationProblems第七章.网络最优化问题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再生公司该公司使用两种不同的再生过程来将报纸、混合纸、白色办公纸和纸板转化为纸浆。从再生原料提出再生纸浆的数量和纸浆的提取本钱由于使用不同的再生过程而不同。通过两种不同的再生过程产生的纸浆通过其他处理转化为新闻用纸、包装用纸或高质量打印纸。两种处理过程的具体数据如下纸浆生产问题提取纸浆数据再生过程1再生过程2原料每吨成本产出结果每吨成本产出结果报纸1390%1285%混合纸1180%1385%白色办公纸995%1090%纸板1375%1485%最终纸浆产出结果新闻用纸包装用纸打印纸纸浆来源每吨成本产出每吨成本产出每吨成本产出过程1595%690%890%过程2690%895%795%如果有70吨报纸，50吨混合纸，30吨白色办公纸和40吨纸板。如何转化成60吨新闻用纸纸浆，40吨包装用纸纸浆，50吨打印纸纸浆，本钱最低。使用供给为负，需求为正的方法转化为最小费用流问题的网络图电子表格模型最优解分析流量守恒规那么的应用当不确定总供给和总需求的关系时，假设供给大于需求如果没有可行解，再更改为需求大于供给最小费用流问题的应用通过配送网络的费用最小现金流管理工厂协调产品组合BMZ公司的最大流问题BMZ公司是欧洲一家生产豪华汽车的制造商，其产品出口到美国尤为重要BMZ公司的汽车尤其在加利福尼亚大受欢送，因此保持洛杉矶中心零部件的充足供给，以便及时维修这些汽车就显得特别重要了最大流问题BMZ公司的最大流问题BMZ公司需要迅速执行一项方案，下个月要从位于斯图加特和德国的主要工厂运送尽可能多的配件到洛杉矶的配送中心配件运送数量的限制因素就是公司配送网络的容量BMZ公司配送网络BMZ问题的网络模型通过每一条运送路线应该运送多少配件，才能使从斯图加特到洛杉矶的总流量最大？BMZ公司的最大流问题BMZ公司的电子表格模型最大流问题的假设网络中所有流起源于一个节点，这个节点叫作源[起点]，所有的流终止于另一个节点，这个节点叫作收点[终点]。BMZ问题中的源和收点分别代表工厂和配送中心其余所有的节点叫作转运点通过每一个弧的流只允许沿着弧的箭头所指方向流动。由源发出的所有的弧背向源，而所有终结于收点的弧都指向收点最大流问题的假设最大流问题的目标是使得从源到收点的总流量最大。这个流量的大小可以用两种等价的方法来衡量，分别叫作从源点出发的流量和进入收点的流量最大流问题和最小费用流问题区别最小费用流问题：供给点、需求点最大流问题：源、收点最小费用流问题的供给量和需求量都是固定的，而最大流问题的源和收点却不是最小费用流问题的供给点和需求点可能有多个，但最大流问题的源和收点只有一个BMZ公司具有多个供给点和需求点的案例BMZ公司在柏林还有一家更小的工厂一旦洛杉矶配送中心出现缺货，位于西雅图的配送中心就可以给有关的客户供给配件扩展的BMZ问题的网络模型扩展的BMZ问题通过每一条运送路线应该运送多少配件，才能使从斯图加特和柏林到洛杉矶和西雅图的总流量最大？电子表格描述最大流问题的应用通过配送网络的流量最大，如BMZ问题通过从供给商到处理设施的公司供给网络的流量最大通过管道运输系统运送的油量最大最大化通过输水系统的水量通过交通网络的车流量最大网络流与整数解使用单纯形法求解具有约束的右侧值是整数的任何最小本钱的网络流模型，最优解自动取整。但是如果参加了副约束，这样不服从流量守恒规那么，就不能保证问题的线性规划模型的解是整数。特殊建模的考虑265431100100-7500-50如果要求进入节点3的流量至少为50，进入节点4的流量至少为60，如何建模？特殊建模的考虑辅助约束-X13-X23<=-50-X14-X24<=-60必须参加虚节点或虚弧线特殊建模的考虑26540301100100-7500-50如果要求进入节点3的流量至少为50，进入节点4的流量至少为60，如何建模？34$0L.B.=-50$0L.B.=-60特殊建模的考虑12$8$6U.B.=35特殊建模的考虑12$8$6U.B.=3510$0特殊建模的考虑24$6$3U.B.=351$43U.B.=35U.B.=30$5,U.B.=40100100-80-75特殊建模的考虑24$6$3U.B.=351$43U.B.=35U.B.=30$5,U.B.=40-100-100+80+750U.B.=100U.B.=100200$999$999辅助约束与整数解参加辅助约束，那么不会自己取整需要参加整数约束里特城的消防队问题里特城是一个农村的小镇它的消防队要为包括许多农场社区在内的大片地区提供效劳在这个地区有很多路，从消防站到任何一个社区都有很多条路线可供选择最短路问题里特城的道路系统最短路问题的网络规划从消防站到某个特定的农场社区的最短路线是那条？里特城的消防队问题最短路问题的标号法1959年，Dijkstra提出算法步骤：步骤1：起点是已标号点，标号为0步骤2：从所有已标号点向未标号点扩散，得到未标号点的临时标号最短路问题的标号法上述公式也用于更新临时标号点的临时标号最短路问题的标号法步骤3：某临时标号点的所有可能标号的最小值即是其最终标号，此时将该临时标号点标记为已标号点，并记录其前一节点最短路问题的标号法步骤4：重复步骤2和3直至找到最短路线，此时得到的最终标号即为其最短路线的长度最短路问题的标号法优点：Dijkstra的标号法是求解最短路问题的最优化算法，也是目前最好的算法，而且可以求得起点到各点的最短路最短路问题的网络规划电子表格描述最短路问题的假设在网络中选择一条路，这条路始于某一节点，这节点叫作源，终于另一个节点，这个节点叫作目标地连接两个节点的连线通常叫作边[允许任一个方向的行进]，虽然也允许存在弧[只允许沿着一个方向行进]最短路问题的假设和每条边相关的一个非负数，叫作该边的长度[注意：在网络中，除了在边的旁边说明了其长度的准确数字以外，所画的每一条边的长度并不说明其真实的长度]目标是寻找从源点到目标地的最短路线[总长度最小的路]最短路问题的应用行进的总距离最小一系列活动的总本钱最小一系列活动的总时间最小总本钱最小的例子:莎拉的汽车基金莎拉刚刚高中毕业在毕业典礼上，她的父母给了她21000美元的汽车基金帮助她购置并保养一辆使用了三年的二手车，以供她上大学使用总本钱最小的例子:莎拉的汽车基金由于开车费用和维修费用随着汽车的老化而飞速上涨，所以，如果能够最小化总的净本钱，莎拉可能在接下来的三个夏天里，一次或屡次折价将她的汽车置换为其他使用了三年的二手车。四年后，莎拉的父母会把她的旧车置换成一辆新车，作为莎拉的毕业礼物。莎拉的本钱数据总本钱最小的例子:莎拉的汽车基金在接下来的三个夏天里，莎拉应该何时折价卖掉她的汽车？如何考虑？如何转换成最短路问题？最短路的描述权=购置本钱+总使用和维护本钱-销售收入电子表格描述总时间最小化的例子:

奎克公司奎克公司得悉它的一个竞争对手方案将把一种很有销售潜力的新产品投放市场奎克公司也一直在研制一种类似的产品，并方案在20个月后投放市场总时间最小化的例子:

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

奎克公司每个阶段应该以什么样的速度进行？如何考虑？如何转换成最短路问题？最短路问题的描述虚拟节点节点:(阶段,剩余资金)；弧:活动；权:时间电子表格描述最优解最小支撑树:摩登公司的问题摩登公司决定铺设最先进的光纤网络系统以便在其主要中心之间提供高速通信，包括数据、声音和视频等为了充分利用光纤技术在中心之间高速通信的优势，不需要在每两个中心之间都用一条光缆把它们直接连接起来，那些需要光缆直接连接的中心有一系列的光缆连接它们最小支撑树问题摩登公司主要中心、纤维光缆的可能布局及本钱应该铺设哪些光纤以便在每两个中心之间提供高速通信？最小支撑树:摩登公司的问题最小支撑树的假设给你网络中的节点，但没有给你边。或者，给你可供选择的边和如果把它插入到网络中后的每条边的正的本钱[或者相似的度量]在设计网络时你希望通过插入足够的边，以满足每两个节点之间都存在一条路的需要目标是寻找一种方法，使得在满足要求的同时总本钱最小最小支撑树的算法选择第一条边：选择本钱最低的备选边选择下一条边：在一个已经有一条边连接的节点和另一个还没有边连接的节点之间选择本钱最低的备选边重复第二个步骤，直到所有的节点都有一条边[可能会有多于一条边]与其相连。此时就得到了最优解[最小支撑树])当有几条边同时是本钱最低的边时，任意选择一条边不会影响最后的最优值摩登公司的算法应用:第一步摩登公司的算法应用:第二步摩登公司的算法应用:第三步摩登公司的算法应用:第四步摩登公司的算法应用:第五步摩登公司的算法应用:最后一步最优解最小支撑树问题避圈法：开始选一条最小权的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已被选取的边不构成圈(如果有两条或两条以上的边都是权最小的边，那么从中任选一条)最小支撑树问题算例最小支撑树问题破圈法：任取一个圈，从圈中去掉权最大的边(如果有两条或两条以上的边都是权最大的边，那么任意去掉其中一条)。在余下的图中，重复这个步骤，一直到图中不含圈为止。去边的同时必须保证图的连通性最小支撑树问题算例最小支撑树的应用电信网络[计算机网络、专用线网络、有线电视网络等等]的设计低负荷运输网络的设计，使得网络中提供链接的局部[如铁路、公路等]的总本钱最小最小支撑树的应用高压输电线路网络的设计连接多个场所的管道网络设计电器设备线路网络[如数字计算机系统]的设计，使得线路总长度最短规划问题总结线性规划资源分配问题本钱收益平衡问题网络配送问题：运输问题，指派问题，最小费用流问题，最大流问题，最短路问题混合问题最小支撑树问题规划问题总