运筹学课程设计之最大网速问题的数学模型

最大网速问题的数学模型最大网速问题的数学模型摘要本题给出了各节点之间的网络流图，需求解它们之间的最大流，即最大网速，为了能有效地解决此问题，我们首先利用求解最大流的标号法对网络图中的可增广链进行逐一分析，并对该链上的流量进行调整，直到该图中没有可增广链后，求得节点1到节点6的最大网速为6兆，然后再通过MATLAB编程实现对标号法求解的结果进行验证。最后，又通过提高各节点之间的网速来达到提高从节点1到节点6网速的目的，得出了各链之间增加的具体流量。即sv到1v的容量应增加到263x，3v到tv的容量应增加到22x，2v到4v与4v到tv的容量都应增加到72x。当然若2023x，即03x，则sv到1v的容量不变。同理，若032x，即06x，则2v到4v与4v到tv的容量也不变。关键词：网络最大流；可增广链；网络流图；MATLAB；最大网速问题的数学模型目录一问题的提出..................................................................1二模型假设....................................................................1三符号说明....................................................................2四问题的分析..................................................................2五模型的建立与求解............................................................25.1模型的建立..............................................................25.1.1可行流............................................................35.1.2割集..............................................................35.1.3最大流-最小割定理.................................................45.1.4可增广链推论......................................................45.1.5寻求最大流的方法..................................................45.1.6可行流调整算法....................................................45.1.7最大流的标号算法..................................................45.2模型的求解..............................................................5六模型的优化.................................................................136.1网络最大流的算法拓展...................................................136.2问题的优化求解.........................................................14模型评价......................................................................16参考文献......................................................................17最大网速问题的数学模型附录..........................................................................18最大网速问题的数学模型第1页共20页一、问题的提出下图为一网络，节点1到节点2的宽带带宽为6兆，节点1到节点3的宽带带宽为2兆，节点2到节点4的宽带带宽为3兆，…节点4到节点6的宽带带宽为2兆，求节点1到节点6的最大网速。进一步，若想提高节点1到节点6的最大网速x兆，如何实现？二、模型假设2.1假设流量在网络传输中没有损失；2.2假设环境对网速没有影响；最大网速问题的数学模型第2页共20页三、符号说明3.1符号说明符号含义iv、jv某一顶点处的标号sv、tv始点和终点的标号S标号点集合S为标号点集合(,)SS割集f可行流ijf/jif从iv到jv的流量/从jv到iv的流量ijciv到jv所在链上的容量E边集iv流量调整量四、问题分析问题的分析：通过对题目的剖析，我们可以知道，要想求解最大流，我们必须要保证在从节点1到节点6之间没有可增广链，因此本题求解的方向是从如何求解可增广链，然后逐步求得最大流。五、模型建立及求解5.1模型的建立由题中所给图形，我们可以对其标号做一点修改，得到图1：最大网速问题的数学模型第3页共20页图1网络传输过程中的流量图为了方便对问题的求解，我们引入以下概念和定理：5.1.1可行流由书中所给定义知非负数ijc为边的容量，本文中即指带宽，而图中（8,1）对应（ijc，ijf）其中ijf表示任一边（iv，jv）的流量，本文中即指单位成本，通过容量可以构建一个容量网络(,,)GVEC。要想求最大流，则找到所有的可行流ijff，而可行流需满足如下条件：（1）容量限制条件：对G中每条边(,)ijvv，有0ijijfc；（2）平衡条件：对中间点iv，有ijkijkff，即物资的输入量与输出量相等。5.1.2割集容量网络(,,)GVEC，,stvv为收、发点，若有边集E为E的子集，将G分为两个子图1G和2G，其顶点集合分别记为,SS，,SSVSS，,stvv分属,SS，满足：①(,)GVEE不连通；②E为E的真子集，而(,)GVEE仍连通，，则称E为G的割集，记为(,)ESS。另外，割集(,)SS中所有始点在S，终点在S的边的容量之和，称为(,)SS的割集容量，记为(,)CSS。最大网速问题的数学模型第4页共20页5.1.3最大流-最小割定理任一个网络G中，从sv到tv的最大流的流量等于分离sv、tv的最小割的容量。5.1.4可增广链推论可行流f是最大流的充要条件是不存在从sv到tv的（关于f的）可增广链。5.1.5寻求最大流的方法：从一个可行流开始，寻求关于这个可行流的可增广链，若存在，则可经过调整，得到一个新的可行流，其流量比原来的可行流要大，重复这个过程，知道不存在关于该流的可增广链时就得到了最大流。5.1.6可行流调整算法根据*S的定义，中的前向边(,)ijvv上必有*ijijfc，后向边上必有*0ijf。令**(,)(,)ijijijijijijcfvvfvv当为前向边当为后向边取=min,0ij显然我们把*f修改为*1f：***1*(,)(,)ijijijijijfvvffvvf为上的前向边为上的后向边其余不难验证*1f仍为可行流。5.1.7最大流的标号算法：用标号法寻求网络中最大流的基本思想是寻找可增广链，使网络的流量得到增加，直到最大为止。即首先给出一个初始流，这样的流是存在的，例如零流。如果存在关于它的可增广链，那么调整该链上每条弧上的流量，就可以得到新的流。对于新的流，如果仍存在可增最大网速问题的数学模型第5页共20页广链，则用同样的方法使流的值增大，继续这个过程，直到网络中不存在关于新得到流的可增广链为止，则该流就是所求的最大流。这种方法分为以下两个过程：1.标号过程：通过标号过程寻找一条可增广链；2.调整过程：沿着可增广链的逆方向依次调整网络的流量。这两个过程的步骤分述如下。（A）标号过程：（i）给发点标号为[,]sv。（ii）若顶点iv已经标号，则对iv的所有未标号的邻接顶点jv按以下规则标号：①若[,]ijvvE，且ijijfc时，令min[,]ivijijijcf，则给顶点sv标号为[,]，若ijijfc，则不给顶点sv标号。②[,]jivvE，且0ijf，令min[,]jjijf，则给jv标号为[,]jjv，若0ijf，则不给jv标号。（iii）不断地重复步骤（ii）直到收点tv被标号，或不再有顶点可以标号为止。当tv被标号时，表明存在一条从sv到tv的可增广链，则转向调整过程（B）。如若tv点不能被标号，且不存在其它可以标号的顶点时，表明不存在从sv到tv的可增广链，算法结束，此时所获得的流就是最大流。（B）调整过程（1）令（可增广链简写为KZGL，前向边简称QXB，后向边简写为HXB）ijtijijijtijijijf+δv,vQXBf=f-δv,vHXBfv,vGLìïïïïï¢íïïïïïî若（）是的若（）是的若（）不在KZ上（2）去掉所有标号，回到第一步，对可行流f¢重新标号。5.2模型的求解最大网速问题的数学模型第6页共20页对于本题，我们采取标号法进行求解。我们对sv进行标号[,]sv，检查邻接点1v，2v，发现1v满足1(,)svvE，且1106ssfc。令1min[60,]6v则给1v标号[,6]sv。同理可知给2v以标号[,2]sv。检查1v的邻接点3v，知2v已标号，发现v3满足13(,)vvE，且131303fc。令3min[30,6]3v则给v3标号1[,3]v。检查v3的邻接点tv，发现tv满足3(,)tvvE，且3302ttfc。令min[20,3]2vt则给tv标号3[,2]v。由于tv已得标号，说明存在可增广链，故标号过程结束，得图2：图2sv到tv的可增广链图最大网速问题的数学模型第7页共20页由图中可知，可增广链为13stvvvv。因为找到了一条可增广链，所以转入调整过程，取2vt为调整量，由tv点开始，由逆可增广链方向按标号3[,2]v找到点3v。令332ttff。，再由3v点的标号1[,3]v找到前一个点1v，并令13132ff。按1v的标号[,2]sv，找到前一个点sv，并令112ssff。调整过程结束，调整中的可增广链见图2的双线边，调整后的可行流情况见图3：图3经第一次标号调整后的可行流图至此，重新开始标号，寻找下一条可增广链。首先对sv进行标号[,]sv，检查邻接点1v，发现1v满足1(,)svvE，且1126ssfc。令1min[62,]4v则给1v标号[,4]sv。检查1v的邻接点3v，知2v已标号，发现3v满足13(,)vvE，且131323fc。令3min[32,4]1v则给3v标号1[,1]v。检查3v的邻接点2v，tv，发现tv满足3(,)tvvE，但3322ttfc不满足标号条件ijijfc。最大网速问题的数学模型第8页共20页因此检查3v的邻接点2v，发现2v满足32(,)vvE，且323203fc。因此令2min[30,1]1v则给2v标号3[,1]v。检查2v的邻接点4v，发现4v满足24(,)vvE，且242407fc。令4min[70,1]1v则给4v标号2[,1]v。检查4v的邻接点tv，发现tv满足4(,)tvvE，且4407ttfc==。令min[70,1]1vt则给tv标号4[,1]v