《网络最优化问题.pptx》由会员分享，可在线阅读，更多相关《网络最优化问题.pptx（108页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、无限配送公司的问题无限配送公司的问题无限配送公司有两个工厂生产产品，无限配送公司有两个工厂生产产品，这些产品需要运到两个仓库里这些产品需要运到两个仓库里工厂工厂1 1生产生产8080个单位个单位工厂工厂2 2生产生产7070个单位个单位仓库仓库1 1需要需要6060个单位个单位仓库仓库2 2需要需要9090个单位个单位第1页/共108页无限配送公司的问题无限配送公司的问题在工厂在工厂1 1和仓库和仓库1 1之间以及工厂之间以及工厂2 2和和仓库仓库2 2之间各有一条铁路运输轨道之间各有一条铁路运输轨道卡车司机至多可以从工厂运输卡车司机至多可以从工厂运输5050个单位到配送中心，然后可以从个单位
2、到配送中心，然后可以从配送中心运输配送中心运输5050个单位到仓库个单位到仓库第2页/共108页配送网络配送网络第3页/共108页配送网络的数据配送网络的数据第4页/共108页最小费用流问题的网络模型最小费用流问题的网络模型第5页/共108页每条路线应该运送多少每条路线应该运送多少单位的产品？单位的产品？无限配送公司的问题无限配送公司的问题第6页/共108页最优解最优解第7页/共108页最小费用流问题的术语最小费用流问题的术语1.所有最小费用流问题都是用带有通过其中的流的网络表示的2.网络中的圆圈被称为节点3.如果节点产生的净流量流出减去流入是一个确定的正数的话，这个节点就是供应点4.如果节点
3、产生的净流量是一个确定的负数的话，那么这个节点就称为需求点第8页/共108页最小费用流问题的术语最小费用流问题的术语5.如果节点产生的净流量恒为零，那么这个节点就称为转运点，我们把流出节点的量等于流入节点的量称为流量守恒6.网络中的箭头称为弧7.允许通过某一条弧的最大流量称为该弧的容量第9页/共108页最小费用流问题的假设最小费用流问题的假设1.至少有一个节点是供应点2.至少有一个节点是需求点3.所有剩下的节点都是转运点4.通过弧的流只允许沿着箭头的方向流动，通过弧的最大流量取决于该弧的容量如果流是双向的话，则需要用一对箭头指向相反的弧来表示第10页/共108页最小费用流问题的假设最小费用流问
4、题的假设5.网络中有足够的弧提供足够的容量，使得所有在供应点中产生的流都能够达到需求点6.在流的单位成本已知的前提下，通过每一条弧的流的成本和流量成正比7.最小费用流问题的目标是在满足给定需求的条件下，使得通过网络供应的总成本最小或通过这样做使得总利润最大化第11页/共108页最小费用流问题的特征最小费用流问题的特征具有可行解的特征：在以上假设下，当且仅当供应点所提供的流量总和等于需求点所需要的流量总和时，最小费用流问题有可行解具有整数解的特征：只要其所有的供应、需求和弧的容量都是整数值，那么任何最小费用流问题的可行解就一定有所有流量都是整数的最优解第12页/共108页电子表格描述电子表格描述
5、第13页/共108页SUMIF 函数函数SUMIF公式可以简化节点流约束公式可以简化节点流约束 SUMIF(Range A,x,Range B)区域区域A中的每一个量满足条件中的每一个量满足条件x时，时，SUMIF函数就会计算区域函数就会计算区域B中相应内容之和中相应内容之和节点节点x的净流出的净流出流出流出-流入流入就等于就等于SUMIF(“From labels”,x,“Flow”)SUMIF(“To labels”,x,“Flow”)第14页/共108页对每一个节点有一个约束，必须遵循“流量守恒规则”转运问题：净流量=流出量-流入量最小成本网络流中将流量守恒规则应用于每个节点总供给总需求
6、流出量-流入量=供给或需求总供给=供给或需求总供给=总需求流出量-流入量=供给或需求第15页/共108页对每一个节点有一个约束，必须遵循“流量守恒规则”净流量=流入量-流出量最小成本网络流中将流量守恒规则应用于每个节点总供给总需求流入量-流出量=供给或需求总供给总需求流入量-流出量=供给或需求总供给=总需求流入量-流出量=供给或需求第16页/共108页转运问题Newark港和Jacksonville港接受到进口到美国的汽车分别为200辆和300辆。B城，G城，Y城，R城和M城的经销商分别需要100辆，60辆，170辆、80辆和70辆汽车。根据各个城市间的运输费用确定成本最小的运送汽车的方式。第
7、17页/共108页净流量=流出量-流入量第18页/共108页净流量等于流入量-流出量第19页/共108页请在电子表格里分别按照供给为正和供给为负的情况，建立两种情况下的模型，并求解比较第20页/共108页供给为正、需求为负时的电子表格模型第21页/共108页供给为负、需求为正的电子表格模型第22页/共108页分析最优解第23页/共108页广义网络流问题广义网络流问题目前所考虑的网络流问题，从一条弧线出来的流量与进入的流量一定是相等的。事实上是这种情况吗？第24页/共108页Coal Bank Hollow 再生公司该公司使用两种不同的再生过程来将报纸、混合纸、白色办公纸和纸板转化为纸浆。从再生
8、原料提出再生纸浆的数量和纸浆的提取成本由于使用不同的再生过程而不同。通过两种不同的再生过程产生的纸浆通过其他处理转化为新闻用纸、包装用纸或高质量打印纸。两种处理过程的具体数据如下第25页/共108页纸浆生产问题提取纸浆数据 再生过程再生过程1 再生过程再生过程2原料原料每吨成本每吨成本 产出结果产出结果每吨成本每吨成本产出结果产出结果报纸报纸13 90%1285%混合纸混合纸11 80%1385%白色办白色办公纸公纸9 95%1090%纸板纸板13 75%1485%第26页/共108页最终纸浆产出结果新闻用纸包装用纸打印纸纸浆来源纸浆来源 每吨成本每吨成本 产出产出 每吨成本每吨成本 产出产出
9、每吨成本每吨成本 产出产出过程1 5 95%6 90%8 90%过程2 6 90%8 95%7 95%如果有70吨报纸，50吨混合纸，30吨白色办公纸和40吨纸板。如何转化成60吨新闻用纸纸浆，40吨包装用纸纸浆，50吨打印纸纸浆，成本最低。使用供给为负，需求为正的方法第27页/共108页转化为最小费用流问题的网络图第28页/共108页电子表格模型第29页/共108页最优解分析第30页/共108页流量守恒规则的应用当不确定总供给和总需求的关系时，假设供给大于需求如果没有可行解，再更改为需求大于供给第31页/共108页最小费用流问题的应用最小费用流问题的应用1.1.通过配送网络的费用最小通过配送
10、网络的费用最小2.2.现金流管理现金流管理3.3.工厂协调产品组合工厂协调产品组合第32页/共108页BMZ公司的最大流问题公司的最大流问题BMZBMZ公司是欧洲一家生产豪华汽车的制造商，其产品出口到美国尤为重要公司是欧洲一家生产豪华汽车的制造商，其产品出口到美国尤为重要BMZ公司的汽车尤其在加利福尼亚大受欢迎，因此保持洛杉矶中心零部件的充足供给，以便及时维修这些汽车就显得特别重要了第33页/共108页BMZ公司的最大流问题公司的最大流问题BMZ公司需要迅速执行一项计划，下个月要从位于斯图加特和德国的主要工厂运送尽可能多的配件到洛杉矶的配送中心配件运送数量的限制因素就是公司配送网络的容量第34
11、页/共108页BMZ 公司配送网络公司配送网络第35页/共108页BMZ问题的网络模型问题的网络模型第36页/共108页通过每一条运送路线应通过每一条运送路线应该运送多少配件，才能该运送多少配件，才能使从斯图加特到洛杉矶使从斯图加特到洛杉矶的总流量最大？的总流量最大？BMZ公司的最大流问题公司的最大流问题第37页/共108页BMZ公司的电子表格模型公司的电子表格模型第38页/共108页最大流问题的假设最大流问题的假设1.1.网络中所有流起源于一个节点，这个节点网络中所有流起源于一个节点，这个节点叫作源叫作源 起点起点，所有的流终止于另一个节，所有的流终止于另一个节点，这个节点叫作收点点，这个节
12、点叫作收点 终点终点。BMZBMZ问题问题中的源和收点分别代表工厂和配送中心中的源和收点分别代表工厂和配送中心2.2.其余所有的节点叫作转运点其余所有的节点叫作转运点3.3.通过每一个弧的流只允许沿着弧的箭头所通过每一个弧的流只允许沿着弧的箭头所指方向流动。由源发出的所有的弧背向源，指方向流动。由源发出的所有的弧背向源，而所有终结于收点的弧都指向收点而所有终结于收点的弧都指向收点第39页/共108页最大流问题的假设最大流问题的假设4.4.最大流问题的目标是使得从源到收点最大流问题的目标是使得从源到收点的总流量最大。这个流量的大小可以的总流量最大。这个流量的大小可以用两种等价的方法来衡量，分别叫
13、作用两种等价的方法来衡量，分别叫作从源点出发的流量和进入收点的流量从源点出发的流量和进入收点的流量第40页/共108页最大流问题和最小费用流问题区别最大流问题和最小费用流问题区别最小费用流问题：供应点、最小费用流问题：供应点、需求点需求点最大流问题：源、收点最大流问题：源、收点最小费用流问题的供应量和最小费用流问题的供应量和需求量都是固定的，而最大需求量都是固定的，而最大流问题的源和收点却不是流问题的源和收点却不是最小费用流问题的供应点和最小费用流问题的供应点和需求点可能有多个，但最大需求点可能有多个，但最大流问题的源和收点只有一个流问题的源和收点只有一个第41页/共108页BMZ 公司具有多
14、个供应点和需求点的案例公司具有多个供应点和需求点的案例BMZBMZ公司在柏林还有一家更小的工厂公司在柏林还有一家更小的工厂一旦洛杉矶配送中心出现缺货，位于西雅一旦洛杉矶配送中心出现缺货，位于西雅图的配送中心就可以给有关的客户供应配图的配送中心就可以给有关的客户供应配件件第42页/共108页扩展的扩展的BMZ问题的网络模型问题的网络模型第43页/共108页扩展的扩展的BMZ问题问题通过每一条运送路线通过每一条运送路线应该运送多少配件，应该运送多少配件，才能使从斯图加特和才能使从斯图加特和柏林到洛杉矶和西雅柏林到洛杉矶和西雅图的总流量最大？图的总流量最大？第44页/共108页电子表格描述电子表格描
15、述第45页/共108页最大流问题的应用最大流问题的应用1.1.通过配送网络的流量最大，如通过配送网络的流量最大，如BMZBMZ问题问题2.2.通过从供应商到处理设施的公司供应网络的流通过从供应商到处理设施的公司供应网络的流量最大量最大3.3.通过管道运输系统运送的油量最大通过管道运输系统运送的油量最大4.4.最大化通过输水系统的水量最大化通过输水系统的水量5.5.通过交通网络的车流量最大通过交通网络的车流量最大第46页/共108页网络流与整数解使用单纯形法求解具有约束的右侧值是整数的任何最小成本的网络流模型，最优解自动取整。但是如果加入了副约束，这样不服从流量守恒规则，就不能保证问题的线性规划
16、模型的解是整数。第47页/共108页特殊建模的考虑特殊建模的考虑265431100100-7500-50如果要求进入节点3的流量至少为50，进入节点4的流量至少为60，如何建模？第48页/共108页特殊建模的考虑特殊建模的考虑辅助约束-X13-X23=-50-X14-X24=-60必须加入虚节点或虚弧线第49页/共108页特殊建模的考虑特殊建模的考虑26540301100100-7500-50如果要求进入节点3的流量至少为50，进入节点4的流量至少为60，如何建模？34$0L.B.=-50$0L.B.=-60第50页/共108页特殊建模的考虑特殊建模的考虑12$8$6U.B.=35第51页/共
17、108页特殊建模的考虑特殊建模的考虑12$8$6U.B.=3510$0第52页/共108页特殊建模的考虑特殊建模的考虑24$6$3U.B.=351$43U.B.=35U.B.=30$5,U.B.=40100100-80-75第53页/共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第54页/共108页辅助约束与整数解加入辅助约束，则不会自己取整需要加入整数约束第55页/共108页里特城的消防队问题里特城的消防队问题里特城是一个农村的小镇里特
18、城是一个农村的小镇它的消防队要为包括许多农场社区它的消防队要为包括许多农场社区在内的大片地区提供服务在内的大片地区提供服务在这个地区有很多路，从消防站到在这个地区有很多路，从消防站到任何一个社区都有很多条路线可供任何一个社区都有很多条路线可供选择选择第56页/共108页里特城的道路系统里特城的道路系统第57页/共108页最短路问题的网络规划最短路问题的网络规划第58页/共108页从消防站到某个特定从消防站到某个特定的农场社区的最短路的农场社区的最短路线是那条？线是那条？里特城的消防队问题里特城的消防队问题第59页/共108页最短路问题的标号法最短路问题的标号法q19591959年，年，Dijk
19、straDijkstra提出提出q算法步骤：算法步骤：v步骤步骤1 1：起点是已标号点，：起点是已标号点，标号为标号为0 0v步骤步骤2 2：从所有已标号点：从所有已标号点向未标号点扩散，得到向未标号点扩散，得到未标号点的临时标号未标号点的临时标号第60页/共108页最短路问题的标号法最短路问题的标号法上述公式也用于更新临时标号点的临时标号第61页/共108页最短路问题的标号法最短路问题的标号法v步骤步骤3 3：某临时标号点：某临时标号点的所有可能标号的最的所有可能标号的最小值即是其最终标号，小值即是其最终标号，此时将该临时标号点此时将该临时标号点标记为已标号点，并标记为已标号点，并记录其前一
20、节点记录其前一节点第62页/共108页最短路问题的标号法最短路问题的标号法v步骤步骤4 4：重复步骤：重复步骤2 2和和3 3直至找到直至找到最短路线，此时得到的最终标最短路线，此时得到的最终标号即为其最短路线的长度号即为其最短路线的长度第63页/共108页最短路问题的标号法最短路问题的标号法q优点：优点：DijkstraDijkstra的标号的标号法是求解法是求解最短路问题最短路问题的最优化算法，也是的最优化算法，也是目前最好的算法，而目前最好的算法，而且可以求得起点到各且可以求得起点到各点的最短路点的最短路第64页/共108页最短路问题的网络规划最短路问题的网络规划第65页/共108页电子
21、表格描述电子表格描述第66页/共108页最短路问题的假设最短路问题的假设1.在网络中选择一条路，这条路始于某在网络中选择一条路，这条路始于某一节点，这节点叫作源，终于另一个一节点，这节点叫作源，终于另一个节点，这个节点叫作目标地节点，这个节点叫作目标地2.连接两个节点的连线通常叫作边连接两个节点的连线通常叫作边允许允许任一个方向的行进任一个方向的行进，虽然也允许存在，虽然也允许存在弧弧只允许沿着一个方向行进只允许沿着一个方向行进第67页/共108页最短路问题的假设最短路问题的假设3.3.和每条边相关的一个非负数，叫作该边的长度和每条边相关的一个非负数，叫作该边的长度 注意：在网络中，除了在边的
22、旁边表明了其长注意：在网络中，除了在边的旁边表明了其长度的准确数字以外，所画的每一条边的长度并不度的准确数字以外，所画的每一条边的长度并不表明其真实的长度表明其真实的长度 4.4.目标是寻找从源点到目标地的最短路线目标是寻找从源点到目标地的最短路线 总长度总长度最小的路最小的路 第68页/共108页最短路问题的应用最短路问题的应用1.1.行进的总距离最小行进的总距离最小2.2.一系列活动的总成本最小一系列活动的总成本最小3.3.一系列活动的总时间最小一系列活动的总时间最小第69页/共108页总成本最小的例子总成本最小的例子:莎拉的汽车基金莎拉的汽车基金莎拉刚刚高中毕业莎拉刚刚高中毕业在毕业典礼
23、上，她的父母给了她在毕业典礼上，她的父母给了她2100021000美美元的汽车基金帮助她购买并保养一辆使用元的汽车基金帮助她购买并保养一辆使用了三年的二手车，以供她上大学使用了三年的二手车，以供她上大学使用第70页/共108页总成本最小的例子总成本最小的例子:莎拉的汽车基金莎拉的汽车基金由于开车费用和维修费用随着汽车的老化而飞速上涨，所以，如果能够最小化总的净成本，莎拉可能在接下来的三个夏天里，一次或多次折价将她的汽车置换为其他使用了三年的二手车。四年后，莎拉的父母会把她的旧车置换成一辆新车，作为莎拉的毕业礼物。第71页/共108页莎拉的成本数据莎拉的成本数据第72页/共108页总成本最小的例
24、子总成本最小的例子:莎拉的汽车基金莎拉的汽车基金在接下来的三个夏天在接下来的三个夏天里，莎拉应该何时折里，莎拉应该何时折价卖掉她的汽车？如价卖掉她的汽车？如何考虑？如何转换成何考虑？如何转换成最短路问题？最短路问题？第73页/共108页最短路的描述最短路的描述权权=购买成本购买成本+总使用和维护成本总使用和维护成本-销售收入销售收入第74页/共108页电子表格描述电子表格描述第75页/共108页总时间最小化的例子总时间最小化的例子:奎克公司奎克公司q奎克公司获悉它的一个竞争对手计划将把一种很有销售潜力的新产品投放市场q奎克公司也一直在研制一种类似的产品，并计划在20个月后投放市场第76页/共1
25、08页总时间最小化的例子总时间最小化的例子:奎克公司奎克公司q奎克公司的管理者希望迅速推出产品去参与竞争q现在还有四个阶段没有完成，每个阶段都可以正常水平、优先水平和应急水平加速完成。正常水平由于后三个阶段的实施速度太慢而被排除了q有3000万美元用于这四个阶段的实施过程第77页/共108页各阶段所需的时间和成本各阶段所需的时间和成本第78页/共108页总时间最小化的例子总时间最小化的例子:奎克公司奎克公司每个阶段应该以什么每个阶段应该以什么样的速度进行？如何样的速度进行？如何考虑？如何转换成最考虑？如何转换成最短路问题？短路问题？第79页/共108页最短路问题的描述最短路问题的描述虚拟节点节
26、点节点:(:(阶段阶段,剩余资金剩余资金)；弧；弧:活动；权活动；权:时间时间第80页/共108页电子表格描述电子表格描述第81页/共108页最优解最优解第82页/共108页最小支撑树最小支撑树:摩登公司的问题摩登公司的问题摩登公司决定铺设最先进的光纤网络系统以便在其主要中心之间提供高速通信，包括数据、声音和视频等为了充分利用光纤技术在中心之间高速通信的优势，不需要在每两个中心之间都用一条光缆把它们直接连接起来，那些需要光缆直接连接的中心有一系列的光缆连接它们第83页/共108页摩登公司主要中心、纤维光缆的可能布局及成摩登公司主要中心、纤维光缆的可能布局及成本本第84页/共108页应该铺设哪些
27、光纤以应该铺设哪些光纤以便在每两个中心之间便在每两个中心之间提供高速通信？提供高速通信？最小支撑树最小支撑树:摩登公司的问题摩登公司的问题第85页/共108页最小支撑树的假设最小支撑树的假设给你网络中的节点，但没有给你边。或者，给你可供选择的边和如果把它插入到网络中后的每条边的正的成本或者相似的度量在设计网络时你希望通过插入足够的边，以满足每两个节点之间都存在一条路的需要目标是寻找一种方法，使得在满足要求的同时总成本最小第86页/共108页最小支撑树的算法最小支撑树的算法1.1.选择第一条边：选择成本最低的备选边选择第一条边：选择成本最低的备选边2.2.选择下一条边：在一个已经有一条边连接的节
28、点和另一个还没有边连接的选择下一条边：在一个已经有一条边连接的节点和另一个还没有边连接的节点之间选择成本最低的备选边节点之间选择成本最低的备选边3.3.重复第二个步骤，直到所有的节点重复第二个步骤，直到所有的节点都有一条边都有一条边 可能会有多于一条边可能会有多于一条边 与与其相连。此时就得到了最优解其相连。此时就得到了最优解 最小最小支撑树支撑树)当有几条边同时是成本最低的边时，当有几条边同时是成本最低的边时，任意选择一条边不会影响最后的最任意选择一条边不会影响最后的最优值优值第87页/共108页摩登公司的算法应用摩登公司的算法应用:第一步第一步第88页/共108页摩登公司的算法应用摩登公司
29、的算法应用:第二步第二步第89页/共108页摩登公司的算法应用摩登公司的算法应用:第三步第三步第90页/共108页摩登公司的算法应用摩登公司的算法应用:第四步第四步第91页/共108页摩登公司的算法应用摩登公司的算法应用:第五步第五步第92页/共108页摩登公司的算法应用摩登公司的算法应用:最后一步最后一步第93页/共108页最优解最优解第94页/共108页最小支撑树问题最小支撑树问题避圈法：开始选一条最小权避圈法：开始选一条最小权的边，以后每一步中，总从的边，以后每一步中，总从未被选取的边中选一条权最未被选取的边中选一条权最小的边，并使之与已被选取小的边，并使之与已被选取的边不构成圈的边不构
30、成圈(如果有两条如果有两条或两条以上的边都是权最小或两条以上的边都是权最小的边，则从中任选一条的边，则从中任选一条)第95页/共108页最小支撑树问题最小支撑树问题q算例第96页/共108页最小支撑树问题最小支撑树问题破圈法：任取一个圈，从圈破圈法：任取一个圈，从圈中去掉权最大的边中去掉权最大的边(如果有两如果有两条或两条以上的边都是权最条或两条以上的边都是权最大的边，则任意去掉其中一大的边，则任意去掉其中一条条)。在余下的图中，重复这。在余下的图中，重复这个步骤，一直到图中不含圈个步骤，一直到图中不含圈为止。去边的同时必须保证为止。去边的同时必须保证图的连通性图的连通性第97页/共108页最
31、小支撑树问题最小支撑树问题q算例第98页/共108页最小支撑树的应用最小支撑树的应用1.电信网络电信网络计算机网络、电话专用线计算机网络、电话专用线网络、有线电视网络等等网络、有线电视网络等等的设计的设计2.低负荷运输网络的设计，使得网络低负荷运输网络的设计，使得网络中提供链接的部分中提供链接的部分如铁路、公路等如铁路、公路等的总成本最小的总成本最小第99页/共108页最小支撑树的应用最小支撑树的应用3.高压输电线路网络的设计高压输电线路网络的设计4.连接多个场所的管道网络设计连接多个场所的管道网络设计5.电器设备线路网络电器设备线路网络如数字计算机如数字计算机系统系统的设计，使得线路总长度最
32、的设计，使得线路总长度最短短第100页/共108页规划问题总结规划问题总结q线性规划线性规划v资源分配问题资源分配问题v成本收益平衡问题成本收益平衡问题v网络配送问题：运输问题，指网络配送问题：运输问题，指派问题，最小费用流问题，最派问题，最小费用流问题，最大流问题，最短路问题大流问题，最短路问题v混合问题混合问题q最小支撑树问题最小支撑树问题第101页/共108页规划问题总结规划问题总结q资源分配问题资源分配问题v将有限的资源分配到各种活动中将有限的资源分配到各种活动中去去v函数约束：使用的资源数量函数约束：使用的资源数量可用可用的资源数量的资源数量v需要确定三类数据：资源可用量、需要确定三
33、类数据：资源可用量、单位活动消耗的资源量和单位活单位活动消耗的资源量和单位活动对绩效测度的贡献量动对绩效测度的贡献量v目标就是在满足资源限制的条件目标就是在满足资源限制的条件下使活动水平能够最大化所选择下使活动水平能够最大化所选择的绩效测度的绩效测度第102页/共108页规划问题总结规划问题总结q成本收益平衡问题成本收益平衡问题v函数约束：完成的水平函数约束：完成的水平最最低可接受水平低可接受水平v需要的三类数据：每种收益需要的三类数据：每种收益的最低可接受水平、每种活的最低可接受水平、每种活动对每一收益的贡献、每种动对每一收益的贡献、每种活动的单位成本活动的单位成本v通过选择各种活动水平的组
34、通过选择各种活动水平的组合，以最小的成本来实现最合，以最小的成本来实现最低可接受的各种收益低可接受的各种收益第103页/共108页规划问题总结规划问题总结q配送网络问题配送网络问题v函数约束是确定的需求：函数约束是确定的需求：提供的数量提供的数量=需要的数量需要的数量q混合问题混合问题v函数约束多种多样：资源函数约束多种多样：资源约束、收益约束、确定性约束、收益约束、确定性需求约束需求约束第104页/共108页规划问题总结规划问题总结q运输问题运输问题v出发地：供应量出发地：供应量v目的地：需求量目的地：需求量v配送成本等于单位成本乘于配送成本等于单位成本乘于配送量配送量v目标就是确定如何配送
35、使配目标就是确定如何配送使配送总成本最小送总成本最小q运输问题的变形运输问题的变形第105页/共108页规划问题总结规划问题总结q指派问题指派问题v任务和被指派者任务和被指派者v目标就是确定怎样进行任务目标就是确定怎样进行任务的指派，以最小化完成任务的指派，以最小化完成任务的总成本的总成本q指派问题的变形指派问题的变形q是特殊的运输问题是特殊的运输问题第106页/共108页规划问题总结规划问题总结q最小费用流问题最小费用流问题v用带流的网络图表示用带流的网络图表示v节点，供应点，需求点，转运点，弧，节点，供应点，需求点，转运点，弧，容量容量v至少有一个供应点一个需求点，其余是至少有一个供应点一个需求点，其余是转运点转运点v通过每一条弧的流的成本和流量成正比通过每一条弧的流的成本和流量成正比v目标是在满足给定需求的条件下，使得目标是在满足给定需求的条件下，使得通过网络供应的总成本最小通过网络供应的总成本最小第107页/共108页感谢您的观看！第108页/共108页