数据模型决策05网络优化（64页)ppt课件

1、第5章:网络优化 所谓网络优化，简单地说，即对网络进展定性和定量分析，以便为实现某种优化目的而寻求最优方案这方面的典型问题有：最小支撑树问题，最小费用流问题、最大流问题、最短路问题，中心问题，重心问题、运输问题、指派问题等等树图构造：最小支撑树问题光缆通讯衔接问题 某公园决议铺设最先进的光纤网络，为它的主要景点之间提供高速通讯(数据，声音和录像)。 为了利用光纤技术在景点之间高速通讯的优势，不需求在每两个景点之间都用一条光缆把他们直接联络起来。问题：确定需求铺设那些光缆使得提供应每个景点之间的高速通讯的本钱最低。公园光缆通讯问题的途径系统图中虚线表示可供选择的边最正确的处理方法 由于恣意两个节

2、点之间均可以通讯，这个图必需是连通图。并且，这个图必需是无圈的。否那么，从圈上恣意去掉一条边，剩下的图依然满足条件,并且本钱更小。树、图的专有名词 图G定义为点和边的集合,记为G=V，E,其中，是点的集合，是边的集合。有向图区别于无向图的关键，在于它的边此时也称弧是有方向的。一个图连同定义在其边集上的实函数一同称为一个网络，我们把定义在边集上的实函数称为边的权数。该网络记为V，E，W。 对于图G=V，E,假设恣意两个节点间都可以由一条或几条边连起来，那么称该图为连通图。连通并且不含圈的无向图称为树。假设树中点的集合等于图的点的集合，树中边的集合是图的边的集合的子集，称树为图的支撑树。在一切的支

3、撑树中总本钱最小的树称为最小支撑树。最小支撑树问题的算法 选择第一条边：选择本钱最低的备选边图中虚线。 选择下一条边：在一个曾经有一条边衔接的节点和另一个还没有边衔接的节点之间选择本钱最低的备选边。 反复第2个步骤，直到一切的节点都有一条边能够会有多于一条边与其相连 . 此时，就得到了最优解(最小支撑树)其中第2步的目的是为了保证每次生成的树都是衔接当前子图的一切顶点的本钱最小的树。算法的运用： 初次衔接 V=C，D W=A，B，E，F，G从V中的节点连向W中节点的备选边中选择本钱最小的一条边算法的运用： 第二次衔接 V=B，C，D W=A，E，F，G算法的运用： 第三次衔接 V=A，B，C，

4、D W=E，F，G算法的运用： 第四次衔接 V=A，B，C，D，F W=E，G算法的运用： 第五次衔接 V=A，B，C，D，E，F W=G算法的运用： 最后的衔接 V=A，B，C，D，E，F，G最小费用流问题 这里的流是一个广泛的概念，例如在交通运输网络中有人流、车流、货物流、供水系统中有水流，金融系统中有现金流，通讯系统中有信息流，等等。 问题的提出：在一个关于流的网络中，每一个流量都有一定的费用，流所走的道路不一样，单位费用不一样。同样数量的流量，由于走的道路不一样，总的费用也不一样。从而我们希望确定在给定网络流量的根底上，让流沿着怎样的道路走，能使总的费用最小。无限配送公司问题 无限配送

5、公司有两家工厂消费产品,这些产品需求运到两个仓库。工厂1消费80个单位；工厂2消费70个单位。 仓库1需求60个单位；仓库2需求90个单位 。工厂1和仓库1之间以及工厂2和仓库2之间各有一条铁路运输轨道。卡车司机总共可以从每家工厂运输50个单位到配送中心，然后可以从配送中心运输50个单位到每个仓库 任何运输到配送中心的产品必需随后运送到仓库。问题：确定一个运输方案即每条道路运送多少单位的产品，使得运输本钱到达最小。网络模型 净流量=流出-流入最小费用流的专有名词 网络中的圆圈被称为节点。 假设节点要求的净流量(流出减去流入) 是一个确定的正数的话，这个点就是一个供应点。 假设节点要求的净流量(

6、流出减去流入) 是一个确定的负数的话，这个点就是一个需求点。假设节点要求的净流量恒为0，这个点称为转运点。我们把流出接点的量等于流入节点的量称为流量守恒。在网络里的箭头被称为弧。 允许经过某一条弧的最大流量被称为该弧的容量。 最小费用流问题的假定 至少有一个节点是供应点；至少有一个节点是需求点；一切剩下的节点都是转运点。 经过弧的流只允许沿着箭头的方向流动，经过弧的最大流量取决于该弧的容量。网络中有足够的弧提供足够的容量，使得一切在供应点产生的流都可以到达需求点。 在流的单位本钱知的前提下，经过每一条弧的流的本钱与流量成正比费用系数是确定的。 最小费用流问题的目的是在给定需求的条件下，使经过网

7、络供应的总本钱最小。一个网络模型 净流量=流出-流入数学模型最正确的处理方法 最小费用流问题的数学建模 设一个有n个节点，m条弧的网络图, ，每一个节点i都对应于一个数bi，表示该节点要求的净流量。 假设bi0，节点i为供应节点，供应量为bi；假设bi0，那么为需求节点，需求量为-bi； 假设bi=0，该节点为转运点。 对于一个网络，假设有 ，称为供求平衡的网络。 网络一切弧i,jG上的流量xij一共n个分量组成的向量X=xij称为网络的一个流。网络中求流量分配使总流量到达一定要求，而总费用最低假设网络的一个流满足以下条件，那么这样的流称为可行流。a、平衡条件：对网络中的任一节点i，在网络中从

8、节点i经过弧(i,j)流向关联的他节点j的流量xij之和减去与节点i关联的其他节点j经过弧(j,i)流入i的流量xji之和 与该节点要求的净流量平衡。即：b、容量限制条件：数学模型：网络的每一弧(i,j),都有一个单位流量的费用系数cij与它对应，假设弧(i,j)上的流量为xij，那么该弧上这些流量引起的费用为cijxij。网络最小费用流问题就是找到使总费用最小的可行流。模型有可行解的必要条件是：该网络是供求平衡的网络。即： 。为什么？最小费用流问题的数学建模2另一类最小费用流问题是在预算费用C给定的情况下，求流量分配，使得从 可以保送的总流量到达最大。 仍用决策变量 表示经过弧(i,j)的流

9、量， 表示弧(i,j)的费用系数， 表示弧(i,j)上的容量，那么数学模型为：最大流问题一、 有关概念：例：以下图是输油管道网， 为起点， 为终点， ， ， ， 为中转站，弧上的数字表示该管道的最大输油能 力也称容量，记为 ，问应如何安排各管道输油量，才干使从 到 的总输油量最大？ 分别称 为发点、收点。其他的点称为转运点。 每一个弧上都给定一个容量的网络称为容量网络，记 的每一个弧上都给定一个实践流量 的网络称为给定了网络一个流。b.容量限制条件： 对每一弧上都有 a.平衡条件： 转运点：流出量-流入量=0。 发收点：发点流出量=收点流入量=网络总流量。 假设 ，称弧 是饱和弧。使网络总流量

10、到达最大的可行流称为最大流 。假设网络的一个流满足以下条件，那么这样的流称为可行流:最大流问题的数学建模 用决策变量 表示经过弧(i,j)的流量， 表示弧(i,j)的容量，那么数学模型为：BMZ公司的最大流问题 BMZ公司是欧洲一家消费奢华汽车的制造商。虽然它消费的汽车在一切兴隆国家销量都不错，对它来讲，出口到美国尤其重要。BMZ汽车正在加利福尼亚变得特别受欢迎，因此保证洛杉矶中心良好的供应显得特别的重要。 大部分汽车配件以及新车是在该公司位于德国的斯图加特的总厂消费的，BMZ公司需求制定一个方案，使得下个月从总厂运送到洛杉矶配送中心的配件流尽能够大。 可以运送多少配件的限制条件就是该公司配送

11、网络的容量。 问题：经过每条运输道路可以运送多少货物，使得从总厂运送到洛杉矶配送中心的配件流最大。 BMZ 销售网 BMZ的一个网络模型 ACBFEG708070604050305040D数学模型最短路问题最短路问题是网络实际中运用最广泛的问题之一。许多优化问题都可以运用这个模型，如设备更新、管道的铺设、线路的安排、厂区的规划等。最短路问题的普通提法是：设 为连通图，图中各边或弧 有权 ( 表示 ， 间没有边或弧, 为图中恣意两点，求一条道路 ，使它是从 到 的一切路中总权最小的路。即： 最小。最短路问题的假定 在网络中选择一条路，这条路始于某一节点，叫做始点，并且终于另一个节点，叫终点。 连

12、结两个节点的连线通常叫做边(允许任一方向的行进,也允许存在弧(只允许朝一个方向行进)。 与每条边相关的一个非负数称为该边的长度。(留意，边和弧也能够代表其他类型的活动) 目的是为了选择从始点到终点的最短路(总长度最小的路) 。 一个最短路问题的运用：为了实现更加人性化的效力,公园管理层需求面向游客出一本旅游线路指南的小册子。 在该小册子中要通知旅客从公园入口,各个景点之间以及入口之间的最短线路。问题:首先思索从公园入口到公园出口的最短线路.景点号A B C D E F GA0 2 4 5 8 7 1313B2 0 2 3 6 5 1111C4 2 0 1 4 3 99D5 3 1 0 5 4

13、1010E8 6 4 5 0 1 58F7 5 3 4 1 0 67G13 11 9 10 5 6 013由于 最小，所以医院应建在F ，此时离医院最远的景点A 间隔为7。 中心问题：中心医务室应建在哪个景点，可使离医务室最远的景点游客就诊时所走的路程最近？ 重心问题：知各景点的员工人数分别为40,25,45,30,20,35,50.那么会议中心应建在哪个景点，可使一切员工在参与会议时间所走的总路程最短？ 由于 最小，所以会议中心应建在C公园的重心(各个景点员工人数40,25,45,30,20,35,50.)景点号ABCDEFGA08016020320280520B50050751501252

14、75C18090045180135405D15090300150120300E16012080100020100F245175105140350210G650550450500250300014351105875106010859801810有向网络最短路问题的数学建模 设始点为1，终点为n，引入01决策变量 ，假设弧(i,j)在从始点到终点的某条途径上，那么 ，否那么 。那么数学模型为：使总本钱最小的最短路问题萨拉刚刚高中毕业。在毕业仪式上，她父母给了她21000美圆的汽车基金协助她购买并保养一辆运用了3年的二手车，以供她上大学。 由于开车费用，维修费用随着汽车的老化而飞速上涨，萨拉可以一次

15、或者几次折价将她的汽车置换为其他运用了3年的二手车，在四年大学毕业后，她父母将送给她一辆新车，到那时她一定方案把旧车折价买出。问题：在接下来的3个暑期，萨拉什么时候应该折价买掉她的汽车(假设必要的话)可以使得她在大学四年的开车，买车，保养汽车的总费用最小？ 萨拉破费数据 拥有年份的开车和维修费 最后一年买出的价值 购买 价格 1234123412，000 美元 2，000 美元 3，000 美元 4，500 美元 6，500 美元 8，500 美元 6，500 美元 4，500 美元 3，000 美元 问题：在接下来的3个暑期，萨拉什么时候应该折价买掉她的汽车(假设必要的话)可以使得她在大学四

16、年的开车，买车，保养汽车的总费用最小？ 最短路网络 解：把这个问题化为最短路问题。节点表示如今(入学)，节点，分别表示第一年年末，第二年年末，第三年年末，第四年年末。从一个节点到另外一个节点的弧表示在第一个节点这个时间买车，然后在第二个节点的那个时间把车折价卖掉的活动最短路网络 弧长买车的价钱运用和保养的费用折价买出的价值。这样该问题就变为：求从节点到节点的最短路问题.数学模型最短路问题也可看成最小费用流问题的特例当确定从任一节点i至另一节点j的最短路时，只需作以下假定：(1)当网络中恣意两个节点之间存在衔接的弧时，弧上的费用系数等于该弧的长度；(2)作为起点的节点i为供应节点且其净流出量为1

17、，作为终点的节点j为需求节点且其净流出量为-1，一切其他节点的净流出量为零；(3) 总费用等于从节点i起点到节点j终点所经过的各条弧的长度之和，目的函数是总费用最小，也就是从节点i到节点j的途径最短。运输问题运输问题的普通提法是：设某种物资有 个产地各产地的产量是有 个销地各销地的销量是假定从产地 到销地运输单位物品的运价是 ，问怎样调运这些物品才干使总运费最小？运输问题例：某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量及各产地运往各销地的单位运费如表所示。如何调运，使总运费最少？销地产地B1B2B3产量A1646200A2655300销量150150

18、200500500单位运费 x11 x12 x13 x21 x22 x23 运输问题的假设需求假设： 每一个出发地产地都有一个固定的供应量，一切的供应量都必需配送到目的地销地。与之相类似，每一个目的地都有一个固定的需求量，整个需求量都必需由出发地满足。 本钱假设： 从任何一个出发地到任何一个目的地的货物配送本钱 和所配送的数量成线性比例关系，因此这个本钱就等于配 送的单位本钱乘以所配送的数量。上例运输问题的线性模型 min z=6 x11+4 x12+6 x13+6 x21+5 x22+5 x23 s.t. x11+ x12+ x13=200 x21+ x22+ x23=300 x11+ x2

19、1=150 x12+ x22=150 x13+ x23=200 xij0推行为普通： 销地B1B2Bn供应量 产地A1C11 x11C12x12 C1nx1na1AmCm1xm1Cm2xm2Cmn xmnam需求量b1b2bnai =bj(平衡)运输问题的线性规划模型Min z=S.t.定理：假设(平衡)运输问题有可行解,那么证 :设运输问题有可行解那么应满足约束从而有运输问题的变形总供应量总需求量的情形供求，LP模型中把约束xijai改为xijai即可供求，LP模型中把约束xijbj改为xijbj即可目的函数最大化的情形，如目的是追求利润或收入时，只需将目的函数改为max即可某些道路的运输才

20、干有一定限制的情形如从A2到B3遭到运输才干限制，最多只能运送150时，只需在原LP模型上添加x23150即可运输问题的计算机求解用线性规划程序求解，输出部分信息多，且变量和约束输入较费事。用运输问题程序求解，只需输入产地个数、销地个数、各产地的产量、各销地的销量、各产地到各销地的单位运价。前例输入后，得到的最优运输方案为：销地产地B1B2B3产量A1501500200A21000200300销量150150200指派问题有4个工人,要指派他们分别完成4项任务,每人做各项任务所耗费的时间如下表。要求1人只做1件事，如何指派使总本钱最少?人 工作B1B2B3B4工资24745325112A33956364313A43251254615模型用0-1变量表示“是非决策：min z=14*35x11+14*41 x12 +14*27 x13+14*40 x14 +12* 47x21+ 12*45 x22+ 12*32x23 +12*51x24 +13*39x31 +13*56x32 + 13*36x33 + 13*43 x34 +15*32x41 +15*51x42 +15*25x43 +15*46x44 s.t. x11+x12+x13+x14 =1 (A1只能干一件事) x21+x22+x