网络最优化问题.ppt

《网络最优化问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、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个单位到配送中心，然后可以从配送中心

2、运输50个单位到仓库配送网络配送网络的数据最小费用流问题的网络模型每条路线应该运送多少单位的产品？无限配送公司的问题最优解最小费用流问题的术语所有最小费用流问题都是用带有通过其中的流的网络表示的网络中的圆圈被称为节点如果节点产生的净流量[流出减去流入]是一个确定的正数的话，这个节点就是供应点如果节点产生的净流量是一个确定的负数的话，那么这个节点就称为需求点最小费用流问题的术语如果节点产生的净流量恒为零，那么这个节点就称为转运点，我们把流出节点的量等于流入节点的量称为流量守恒网络中的箭头称为弧允许通过某一条弧的最大流量称为该弧的容量最小费用流问题的假设至少有一个节点是供应点

3、至少有一个节点是需求点所有剩下的节点都是转运点通过弧的流只允许沿着箭头的方向流动，通过弧的最大流量取决于该弧的容量[如果流是双向的话，则需要用一对箭头指向相反的弧来表示]最小费用流问题的假设网络中有足够的弧提供足够的容量，使得所有在供应点中产生的流都能够达到需求点在流的单位成本已知的前提下，通过每一条弧的流的成本和流量成正比最小费用流问题的目标是在满足给定需求的条件下，使得通过网络供应的总成本最小[或通过这样做使得总利润最大化]最小费用流问题的特征具有可行解的特征：在以上假设下，当且仅当供应点所提供的流量总和等于需求点所需要的流量总和时，最小费用流问题有可行解具有整数解的

4、特征：只要其所有的供应、需求和弧的容量都是整数值，那么任何最小费用流问题的可行解就一定有所有流量都是整数的最优解电子表格描述SUMIF函数SUMIF公式可以简化节点流约束SUMIF(RangeA,x,RangeB)区域A中的每一个量满足条件x时，SUMIF函数就会计算区域B中相应内容之和节点x的净流出[流出-流入]就等于SUMIF(“Fromlabels”,x,“Flow”)–SUMIF(“Tolabels”,x,“Flow”)对每一个节点有一个约束，必须遵循“流量守恒规则”转运问题：净流量=流出量-流入量最小成本网络流中将流量守恒规则应用于每个节点总供给>总需求流出量-

5、流入量<=供给或需求总供给<总需求流出量-流入量>=供给或需求总供给=总需求流出量-流入量=供给或需求对每一个节点有一个约束，必须遵循“流量守恒规则”净流量=流入量-流出量最小成本网络流中将流量守恒规则应用于每个节点总供给>总需求流入量-流出量>=供给或需求总供给<总需求流入量-流出量<=供给或需求总供给=总需求流入量-流出量=供给或需求转运问题Newark港和Jacksonville港接受到进口到美国的汽车分别为200辆和300辆。B城，G城，Y城，R城和M城的经销商分别需要100辆，60辆，170辆、80辆和70辆汽车。根据各个城市间的运输费用确定成本最小的运送汽车的

6、方式。净流量=流出量-流入量净流量等于流入量-流出量请在电子表格里分别按照供给为正和供给为负的情况，建立两种情况下的模型，并求解比较供给为正、需求为负时的电子表格模型供给为负、需求为正的电子表格模型分析最优解广义网络流问题目前所考虑的网络流问题，从一条弧线出来的流量与进入的流量一定是相等的。事实上是这种情况吗？CoalBankHollow再生公司该公司使用两种不同的再生过程来将报纸、混合纸、白色办公纸和纸板转化为纸浆。从再生原料提出再生纸浆的数量和纸浆的提取成本由于使用不同的再生过程而不同。通过两种不同的再生过程产生的纸浆通过其他处理转化为新闻用纸、包装用纸或高质量打印纸

7、。两种处理过程的具体数据如下纸浆生产问题提取纸浆数据再生过程1再生过程2原料每吨成本产出结果每吨成本产出结果报纸1390%1285%混合纸1180%1385%白色办公纸995%1090%纸板1375%1485%最终纸浆产出结果新闻用纸包装用纸打印纸纸浆来源每吨成本产出每吨成本产出每吨成本产出过程1595%690%890%过程2690%895%795%如果有70吨报纸，50吨混合纸，30吨白色办公纸和40吨纸板。如何转化成60吨新闻用纸纸浆，40吨包装用纸纸浆，50吨打印纸纸浆，成本最低。使用供给为负，需求为正的方法转化为最小费