数据模型决策05网络优化（PPT64页)

第5章:网络优化所谓网络优化，简单地说，即对网络进行定性和定量分析，以便为实现某种优化目标而寻求最优方案．这方面的典型问题有：最小支撑树问题，最小费用流问题、最大流问题、最短路问题，中心问题，重心问题、运输问题、指派问题等等．树图结构：最小支撑树问题光缆通信连接问题•某公园决定铺设最先进的光纤网络，为它的主要景点之间提供高速通信(数据，声音和录像)。•为了利用光纤技术在景点之间高速通信的优势，不需要在每两个景点之间都用一条光缆把他们直接联系起来。•问题：确定需要铺设那些光缆使得提供给每个景点之间的高速通信的成本最低。公园光缆通信问题的路径系统BADCFEG221315754474图中虚线表示可供选择的边最佳的解决办法BADCFEG221315由于任意两个节点之间均可以通信，这个图必须是连通图。并且，这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然满足条件,并且成本更小。树、图的专有名词•图G定义为点和边的集合,记为G={V，E},其中，Ｖ是点的集合，Ｅ是边的集合。有向图区别于无向图的关键，在于它的边（此时也称弧）是有方向的。•一个图连同定义在其边集上的实函数一起称为一个网络，我们把定义在边集上的实函数称为边的权数。该网络记为Ｎ＝{V，E，W}。•对于图G={V，E},如果任意两个节点间都可以由一条或几条边连起来，则称该图为连通图。•连通并且不含圈的无向图称为树。•若树Ｄ中点的集合等于图Ｇ的点的集合，树Ｄ中边的集合是图Ｇ的边的集合的子集，称树Ｄ为图Ｇ的支撑树。•在所有的支撑树中总成本最小的树称为最小支撑树。最小支撑树问题的算法1.选择第一条边：选择成本最低的备选边（图中虚线）。2.选择下一条边：在一个已经有一条边连接的节点和另一个还没有边连接的节点之间选择成本最低的备选边。3.重复第2个步骤，直到所有的节点都有一条边（可能会有多于一条边）与其相连.此时，就得到了最优解(最小支撑树)其中第2步的目的是为了保证每次生成的树都是连接当前子图的所有顶点的成本最小的树。算法的应用：首次连接BADCFEG221315745744V={C，D}W={A，B，E，F，G}从V中的节点连向W中节点的备选边中选择成本最小的一条边算法的应用：第二次连接BADCFEG221315745744V={B，C，D}W={A，E，F，G}算法的应用：第三次连接BADCFEG221315745744V={A，B，C，D}W={E，F，G}算法的应用：第四次连接BADCFEG221315745744V={A，B，C，D，F}W={E，G}算法的应用：第五次连接BADCFEG221315745744V={A，B，C，D，E，F}W={G}算法的应用：最后的连接BADCFEG221315745744V={A，B，C，D，E，F，G}最小费用流问题这里的流是一个广泛的概念，例如在交通运输网络中有人流、车流、货物流、供水系统中有水流，金融系统中有现金流，通信系统中有信息流，等等。问题的提出：在一个关于流的网络中，每一个流量都有一定的费用，流所走的路线不一样，单位费用不一样。同样数量的流量，因为走的路线不一样，总的费用也不一样。从而我们希望确定在给定网络流量的基础上，让流沿着怎样的路线走，能使总的费用最小。无限配送公司问题•无限配送公司有两家工厂生产产品,这些产品需要运到两个仓库。•工厂1生产80个单位；工厂2生产70个单位。•仓库1需要60个单位；仓库2需要90个单位。•工厂1和仓库1之间以及工厂2和仓库2之间各有一条铁路运输轨道。•卡车司机总共可以从每家工厂运输50个单位到配送中心，然后可以从配送中心运输50个单位到每个仓库（任何运输到配送中心的产品必须随后运送到仓库）。•问题：确定一个运输方案（即每条路线运送多少单位的产品），使得运输成本达到最小。网络模型F1DCF2W2W1$700$900[80][-60][-90][70][0]$300[50]$200[50]$400[50]$400[50]净流量=流出-流入最小费用流的专有名词1.网络中的圆圈被称为节点。2.如果节点要求的净流量(流出减去流入)是一个确定的正数的话，这个点就是一个供应点。3.如果节点要求的净流量(流出减去流入)是一个确定的负数的话，这个点就是一个需求点。4.若节点要求的净流量恒为0，这个点称为转运点。我们把流出接点的量等于流入节点的量称为流量守恒。5.在网络里的箭头被称为弧。6.允许通过某一条弧的最大流量被称为该弧的容量。最小费用流问题的假定1.至少有一个节点是供应点；至少有一个节点是需求点；所有剩下的节点都是转运点。2.通过弧的流只允许沿着箭头的方向流动，通过弧的最大流量取决于该弧的容量。3.网络中有足够的弧提供足够的容量，使得所有在供应点产生的流都能够到达需求点。4.在流的单位成本已知的前提下，通过每一条弧的流的成本与流量成正比（费用系数是确定的）。5.最小费用流问题的目标是在给定需求的条件下，使通过网络供应的总成本最小。一个网络模型F1DCF2W2W1$700$900[80][-60][-90][70][0]$300[50]$200[50]$400[50]$400[50]净流量=流出-流入数学模型所有变量非负为各个节点间运输量设50x,x,x,x90xx70xx0xxxx60xx80xx.t.sx900x400x400x200x300x700zminx,x,x,x,x,x2DCWDC2F1DCWDC1F2W2F2DCW2W2FDC2FDC2FDC1F2DCW1DCW1DCW1W1FDC1F1W1F2W2F2DCWDC2F1DCWDC1F1W1F2W2F2DCWDC2F1DCWDC1F1W1F最佳的解决办法F1DCF2W2W1(30)(40)[80][-60][-90][70][0](50)(30)(30)(50)最小费用流问题的数学建模设一个有n个节点，m条弧的网络图Ｎ＝{Ｖ,Ｅ,Ｗ}，每一个节点i都对应于一个数bi，表示该节点要求的净流量。如果bi0，节点i为供应节点，供应量为bi；如果bi0，则为需求节点，需求量为-bi；如果bi=0，该节点为转运点。对于一个网络，如果有，称为供求平衡的网络。网络所有弧（i,j）∈G上的流量xij（一共n个分量）组成的向量X=[xij]称为网络的一个流。10niib（１）网络中求流量分配使总流量达到一定要求，而总费用最低如果网络的一个流满足以下条件，则这样的流称为可行流。a、平衡条件：对网络中的任一节点i，在网络中从节点i通过弧(i,j)流向关联的他节点j的流量xij之和减去与节点i关联的其他节点j通过弧(j,i)流入i的流量xji之和与该节点要求的净流量平衡。即：ij(i,j)Exijjii(i,j)E(j,i)Exxb,i1,2,...,nb、容量限制条件：ijij0xu,i,j1,2,...,nji(j,i)Ex数学模型：网络的每一弧(i,j),都有一个单位流量的费用系数cij与它对应，如果弧(i,j)上的流量为xij，则该弧上这些流量引起的费用为cijxij。网络最小费用流问题就是找到使总费用最小的可行流。ijij(i,j)Eijjii(i,j)E(j,i)Eijijminzcxxxb,i1,2,...,ns.t.0xu((i,j)E)模型有可行解的必要条件是：该网络是供求平衡的网络。即：。为什么？10niib最小费用流问题的数学建模（2）另一类最小费用流问题是在预算费用C给定的情况下，求流量分配，使得从能够输送的总流量达到最大。仍用决策变量表示通过弧(i,j)的流量，表示弧(i,j)的费用系数，表示弧(i,j)上的容量，则数学模型为：tsvvijxijcijuijij(i,j)Esijjist(i,j)E(j,i)EtijijmaxzfcxCf,(iv)s.t.xx0,(iv,v)f,(iv)0xu((i,j)E)最大流问题一、有关概念：例：下图是输油管道网，为起点，为终点，，，，为中转站，弧上的数字表示该管道的最大输油能力（也称容量），记为，问应如何安排各管道输油量，才能使从到的总输油量最大？1v3v2v,4v,5vsvtv6viju1v3v2v4v5vsvtv6v22333455534svtv1v3v2v4v5vsvtv6v22333455534①分别称为发点、收点。其余的点称为转运点。,svtv②每一个弧上都给定一个容量的网络称为容量网络，记)W,E,V(G③的每一个弧上都给定一个实际流量的网络称为给定了网络一个流。Gijx1v3v2v4v5vsvtv6v)5,5()2,3()2,4()2,5()2,4()4,5()3,3()3,3()0,3()2,2()2,2(b.容量限制条件：对每一弧上都有ijij0xua.平衡条件：转运点：流出量-流入量=0。发收点：发点流出量=收点流入量=网络总流量。若，称弧是饱和弧。ijijxu)v,v(ji使网络总流量达到最大的可行流称为最大流。如果网络的一个流满足以下条件，则这样的流称为可行流:最大流问题的数学建模用决策变量表示通过弧(i,j)的流量，表示弧(i,j)的容量，则数学模型为：ijxijusijjist(i,j)E(j,i)Etijijmaxzff,(iv)xx0,(iv,v)s.t.f,(iv)0xu((i,j)E)1v3v2v4v5vsvtv6v22333455534BMZ公司的最大流问题•BMZ公司是欧洲一家生产豪华汽车的制造商。虽然它生产的汽车在所有发达国家销量都不错，对它来讲，出口到美国尤其重要。BMZ汽车正在加利福尼亚变得特别受欢迎，因此保证洛杉矶中心良好的供应显得特别的重要。•大部分汽车配件以及新车是在该公司位于德国的斯图加特的总厂生产的，BMZ公司需要制定一个计划，使得下个月从总厂运送到洛杉矶配送中心的配件流尽可能大。•可以运送多少配件的限制条件就是该公司配送网络的容量。•问题：通过每条运输路线可以运送多少货物，使得从总厂运送到洛杉矶配送中心的配件流最大。BMZ销售网STLIBORONONYLANewYorkRotterdamStuttgartLisbonNewOrleans{40unitsmax.]Bordeaux[70unitsmax.]LosAngeles[80unitsmax.][60unitsmax.][50unitsmax.][30unitsmax.][50unitsmax.][40unitsmax.][70unitsmax]BMZ的一个网络模型ACBFEG[70][80][70][60][40][50][30][50][40]D数学模型0,700,800,300,500400,600,400,700,50000000..max)(,,,,,,,,fxxxxxxxxxfxxxxxxxxxxxxxxxfxxxtsfzGAfGAxxxxxxxxxFGEGDFCFCEBEADACABFGEGFGDFCFEGCEBEDFADCFCEACBEABADACABFGEGDFCFCEBEADACAB的总流量）到（从运送的货物数量为到网络中从流量为各条弧上的运输量设最短路问题最短路问题是网络理论中应用最广泛的问题之一。许多优化问题都可以使用这个模型，如设备更新、管道的铺设、线路的安排、厂区的布局等。最短路问题的一般提法是：设为连通图，图中各边或弧有权(表示，间没有边或弧）,为图中任意两点，求一条道路，使它是从到的所有路中总权最小的路。即：),(EVG),(jivvijlijliv,svjvtvsvtv)v,v(ijjil)(L最小。最短路问题的假定