网络最优化问题

7.1最小费用流问题7.2案例研究：BMZ公司的最大流问题7.3最大流问题7.4最短路问题：里特城的消防队问题7.4最短路问题：一般特征7.4最短路问题：最小化莎拉的总成本问题7.4最短路问题：最小化奎克公司总时间问题7.5最小支撑树问题：摩登公司问题)主要内容现在是1页\一共有108页\编辑于星期三无限配送公司的问题无限配送公司有两个工厂生产产品，这些产品需要运到两个仓库里工厂1生产80个单位工厂2生产70个单位最小费用流问题仓库1需要60个单位仓库2需要90个单位现在是2页\一共有108页\编辑于星期三无限配送公司的问题在工厂1和仓库1之间以及工厂2和仓库2之间各有一条铁路运输轨道卡车司机至多可以从工厂运输50个单位到配送中心，然后可以从配送中心运输50个单位到仓库现在是3页\一共有108页\编辑于星期三配送网络现在是4页\一共有108页\编辑于星期三配送网络的数据现在是5页\一共有108页\编辑于星期三最小费用流问题的网络模型现在是6页\一共有108页\编辑于星期三每条路线应该运送多少单位的产品？无限配送公司的问题现在是7页\一共有108页\编辑于星期三最优解现在是8页\一共有108页\编辑于星期三最小费用流问题的术语所有最小费用流问题都是用带有通过其中的流的网络表示的网络中的圆圈被称为节点如果节点产生的净流量[流出减去流入]是一个确定的正数的话，这个节点就是供应点如果节点产生的净流量是一个确定的负数的话，那么这个节点就称为需求点现在是9页\一共有108页\编辑于星期三最小费用流问题的术语如果节点产生的净流量恒为零，那么这个节点就称为转运点，我们把流出节点的量等于流入节点的量称为流量守恒网络中的箭头称为弧允许通过某一条弧的最大流量称为该弧的容量现在是10页\一共有108页\编辑于星期三最小费用流问题的假设至少有一个节点是供应点至少有一个节点是需求点所有剩下的节点都是转运点通过弧的流只允许沿着箭头的方向流动，通过弧的最大流量取决于该弧的容量[如果流是双向的话，则需要用一对箭头指向相反的弧来表示]现在是11页\一共有108页\编辑于星期三最小费用流问题的假设网络中有足够的弧提供足够的容量，使得所有在供应点中产生的流都能够达到需求点在流的单位成本已知的前提下，通过每一条弧的流的成本和流量成正比最小费用流问题的目标是在满足给定需求的条件下，使得通过网络供应的总成本最小[或通过这样做使得总利润最大化]现在是12页\一共有108页\编辑于星期三最小费用流问题的特征具有可行解的特征：在以上假设下，当且仅当供应点所提供的流量总和等于需求点所需要的流量总和时，最小费用流问题有可行解具有整数解的特征：只要其所有的供应、需求和弧的容量都是整数值，那么任何最小费用流问题的可行解就一定有所有流量都是整数的最优解现在是13页\一共有108页\编辑于星期三电子表格描述现在是14页\一共有108页\编辑于星期三SUMIF函数SUMIF公式可以简化节点流约束

SUMIF(RangeA,x,RangeB)区域A中的每一个量满足条件x时，SUMIF函数就会计算区域B中相应内容之和节点x的净流出[流出-流入]就等于SUMIF(“Fromlabels”,x,“Flow”)–SUMIF(“Tolabels”,x,“Flow”)现在是15页\一共有108页\编辑于星期三对每一个节点有一个约束，必须遵循“流量守恒规则”转运问题：净流量=流出量-流入量最小成本网络流中将流量守恒规则应用于每个节点总供给>总需求流出量-流入量<=供给或需求总供给<总需求流出量-流入量>=供给或需求总供给=总需求流出量-流入量=供给或需求现在是16页\一共有108页\编辑于星期三对每一个节点有一个约束，必须遵循“流量守恒规则”净流量=流入量-流出量最小成本网络流中将流量守恒规则应用于每个节点总供给>总需求流入量-流出量>=供给或需求总供给<总需求流入量-流出量<=供给或需求总供给=总需求流入量-流出量=供给或需求现在是17页\一共有108页\编辑于星期三转运问题Newark港和Jacksonville港接受到进口到美国的汽车分别为200辆和300辆。B城，G城，Y城，R城和M城的经销商分别需要100辆，60辆，170辆、80辆和70辆汽车。根据各个城市间的运输费用确定成本最小的运送汽车的方式。现在是18页\一共有108页\编辑于星期三净流量=流出量-流入量现在是19页\一共有108页\编辑于星期三净流量等于流入量-流出量现在是20页\一共有108页\编辑于星期三请在电子表格里分别按照供给为正和供给为负的情况，建立两种情况下的模型，并求解比较现在是21页\一共有108页\编辑于星期三供给为正、需求为负时的电子表格模型现在是22页\一共有108页\编辑于星期三供给为负、需求为正的电子表格模型现在是23页\一共有108页\编辑于星期三分析最优解现在是24页\一共有108页\编辑于星期三广义网络流问题目前所考虑的网络流问题，从一条弧线出来的流量与进入的流量一定是相等的。事实上是这种情况吗？现在是25页\一共有108页\编辑于星期三CoalBankHollow再生公司该公司使用两种不同的再生过程来将报纸、混合纸、白色办公纸和纸板转化为纸浆。从再生原料提出再生纸浆的数量和纸浆的提取成本由于使用不同的再生过程而不同。通过两种不同的再生过程产生的纸浆通过其他处理转化为新闻用纸、包装用纸或高质量打印纸。两种处理过程的具体数据如下现在是26页\一共有108页\编辑于星期三纸浆生产问题提取纸浆数据再生过程1再生过程2原料每吨成本产出结果每吨成本产出结果报纸1390%1285%混合纸1180%1385%白色办公纸995%1090%纸板1375%1485%现在是27页\一共有108页\编辑于星期三最终纸浆产出结果新闻用纸包装用纸打印纸纸浆来源每吨成本产出每吨成本产出每吨成本产出过程1595%690%890%过程2690%895%795%如果有70吨报纸，50吨混合纸，30吨白色办公纸和40吨纸板。如何转化成60吨新闻用纸纸浆，40吨包装用纸纸浆，50吨打印纸纸浆，成本最低。使用供给为负，需求为正的方法现在是28页\一共有108页\编辑于星期三转化为最小费用流问题的网络图现在是29页\一共有108页\编辑于星期三电子表格模型现在是30页\一共有108页\编辑于星期三最优解分析现在是31页\一共有108页\编辑于星期三流量守恒规则的应用当不确定总供给和总需求的关系时，假设供给大于需求如果没有可行解，再更改为需求大于供给现在是32页\一共有108页\编辑于星期三最小费用流问题的应用通过配送网络的费用最小现金流管理工厂协调产品组合现在是33页\一共有108页\编辑于星期三BMZ公司的最大流问题BMZ公司是欧洲一家生产豪华汽车的制造商，其产品出口到美国尤为重要BMZ公司的汽车尤其在加利福尼亚大受欢迎，因此保持洛杉矶中心零部件的充足供给，以便及时维修这些汽车就显得特别重要了最大流问题现在是34页\一共有108页\编辑于星期三BMZ公司的最大流问题BMZ公司需要迅速执行一项计划，下个月要从位于斯图加特和德国的主要工厂运送尽可能多的配件到洛杉矶的配送中心配件运送数量的限制因素就是公司配送网络的容量现在是35页\一共有108页\编辑于星期三BMZ公司配送网络现在是36页\一共有108页\编辑于星期三BMZ问题的网络模型现在是37页\一共有108页\编辑于星期三通过每一条运送路线应该运送多少配件，才能使从斯图加特到洛杉矶的总流量最大？BMZ公司的最大流问题现在是38页\一共有108页\编辑于星期三BMZ公司的电子表格模型现在是39页\一共有108页\编辑于星期三最大流问题的假设网络中所有流起源于一个节点，这个节点叫作源[起点]，所有的流终止于另一个节点，这个节点叫作收点[终点]。BMZ问题中的源和收点分别代表工厂和配送中心其余所有的节点叫作转运点通过每一个弧的流只允许沿着弧的箭头所指方向流动。由源发出的所有的弧背向源，而所有终结于收点的弧都指向收点现在是40页\一共有108页\编辑于星期三最大流问题的假设最大流问题的目标是使得从源到收点的总流量最大。这个流量的大小可以用两种等价的方法来衡量，分别叫作从源点出发的流量和进入收点的流量现在是41页\一共有108页\编辑于星期三最大流问题和最小费用流问题区别最小费用流问题：供应点、需求点最大流问题：源、收点最小费用流问题的供应量和需求量都是固定的，而最大流问题的源和收点却不是最小费用流问题的供应点和需求点可能有多个，但最大流问题的源和收点只有一个现在是42页\一共有108页\编辑于星期三BMZ公司具有多个供应点和需求点的案例BMZ公司在柏林还有一家更小的工厂一旦洛杉矶配送中心出现缺货，位于西雅图的配送中心就可以给有关的客户供应配件现在是43页\一共有108页\编辑于星期三扩展的BMZ问题的网络模型现在是44页\一共有108页\编辑于星期三扩展的BMZ问题通过每一条运送路线应该运送多少配件，才能使从斯图加特和柏林到洛杉矶和西雅图的总流量最大？现在是45页\一共有108页\编辑于星期三电子表格描述现在是46页\一共有108页\编辑于星期三最大流问题的应用通过配送网络的流量最大，如BMZ问题通过从供应商到处理设施的公司供应网络的流量最大通过管道运输系统运送的油量最大最大化通过输水系统的水量通过交通网络的车流量最大现在是47页\一共有108页\编辑于星期三网络流与整数解使用单纯形法求解具有约束的右侧值是整数的任何最小成本的网络流模型，最优解自动取整。但是如果加入了副约束，这样不服从流量守恒规则，就不能保证问题的线性规划模型的解是整数。现在是48页\一共有108页\编辑于星期三特殊建模的考虑265431100100-7500-50如果要求进入节点3的流量至少为50，进入节点4的流量至少为60，如何建模？现在是49页\一共有108页\编辑于星期三特殊建模的考虑辅助约束-X13-X23<=-50-X14-X24<=-60必须加入虚节点或虚弧线现在是50页\一共有108页\编辑于星期三特殊建模的考虑26540301100100-7500-50如果要求进入节点3的流量至少为50，进入节点4的流量至少为60，如何建模？34$0L.B.=-50$0L.B.=-60现在是51页\一共有108页\编辑于星期三特殊建模的考虑12$8$6U.B.=35现在是52页\一共有108页\编辑于星期三特殊建模的考虑12$8$6U.B.=3510$0现在是53页\一共有108页\编辑于星期三特殊建模的考虑24$6$3U.B.=351$43U.B.=35U.B.=30$5,U.B.=40100100-80-75现在是54页\一共有108页\编辑于星期三特殊建模的考虑24$6$3U.B.=351$43U.B.=35U.B.=30$5,U.B.=40-100-100+80+750U.B.=100U.B.=100200$999$999现在是55页\一共有108页\编辑于星期三辅助约束与整数解加入辅助约束，则不会自己取整需要加入整数约束现在是56页\一共有108页\编辑于星期三里特城的消防队问题里特城是一个农村的小镇它的消防队要为包括许多农场社区在内的大片地区提供服务在这个地区有很多路，从消防站到任何一个社区都有很多条路线可供选择最短路问题现在是57页\一共有108页\编辑于星期三里特城的道路系统现在是58页\一共有108页\编辑于星期三最短路问题的网络规划现在是59页\一共有108页\编辑于星期三从消防站到某个特定的农场社区的最短路线是那条？里特城的消防队问题现在是60页\一共有108页\编辑于星期三最短路问题的标号法1959年，Dijkstra提出算法步骤：步骤1：起点是已标号点，标号为0步骤2：从所有已标号点向未标号点扩散，得到未标号点的临时标号现在是61页\一共有108页\编辑于星期三最短路问题的标号法上述公式也用于更新临时标号点的临时标号现在是62页\一共有108页\编辑于星期三最短路问题的标号法步骤3：某临时标号点的所有可能标号的最小值即是其最终标号，此时将该临时标号点标记为已标号点，并记录其前一节点现在是63页\一共有108页\编辑于星期三最短路问题的标号法步骤4：重复步骤2和3直至找到最短路线，此时得到的最终标号即为其最短路线的长度现在是64页\一共有108页\编辑于星期三最短路问题的标号法优点：Dijkstra的标号法是求解最短路问题的最优化算法，也是目前最好的算法，而且可以求得起点到各点的最短路现在是65页\一共有108页\编辑于星期三最短路问题的网络规划现在是66页\一共有108页\编辑于星期三电子表格描述现在是67页\一共有108页\编辑于星期三最短路问题的假设在网络中选择一条路，这条路始于某一节点，这节点叫作源，终于另一个节点，这个节点叫作目标地连接两个节点的连线通常叫作边[允许任一个方向的行进]，虽然也允许存在弧[只允许沿着一个方向行进]现在是68页\一共有108页\编辑于星期三最短路问题的假设和每条边相关的一个非负数，叫作该边的长度[注意：在网络中，除了在边的旁边表明了其长度的准确数字以外，所画的每一条边的长度并不表明其真实的长度]目标是寻找从源点到目标地的最短路线[总长度最小的路]现在是69页\一共有108页\编辑于星期三最短路问题的应用行进的总距离最小一系列活动的总成本最小一系列活动的总时间最小现在是70页\一共有108页\编辑于星期三总成本最小的例子:莎拉的汽车基金莎拉刚刚高中毕业在毕业典礼上，她的父母给了她21000美元的汽车基金帮助她购买并保养一辆使用了三年的二手车，以供她上大学使用现在是71页\一共有108页\编辑于星期三总成本最小的例子:莎拉的汽车基金由于开车费用和维修费用随着汽车的老化而飞速上涨，所以，如果能够最小化总的净成本，莎拉可能在接下来的三个夏天里，一次或多次折价将她的汽车置换为其他使用了三年的二手车。四年后，莎拉的父母会把她的旧车置换成一辆新车，作为莎拉的毕业礼物。现在是72页\一共有108页\编辑于星期三莎拉的成本数据现在是73页\一共有108页\编辑于星期三总成本最小的例子:莎拉的汽车基金在接下来的三个夏天里，莎拉应该何时折价卖掉她的汽车？如何考虑？如何转换成最短路问题？现在是74页\一共有108页\编辑于星期三最短路的描述权=购买成本+总使用和维护成本-销售收入现在是75页\一共有108页\编辑于星期三电子表格描述现在是76页\一共有108页\编辑于星期三总时间最小化的例子:

奎克公司奎克公司获悉它的一个竞争对手计划将把一种很有销售潜力的新产品投放市场奎克公司也一直在研制一种类似的产品，并计划在20个月后投放市场现在是77页\一共有108页\编辑于星期三总时间最小化的例子:

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

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