最优化理论在多商品流中的应用.docx

《最优化理论在多商品流中的应用.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最优化理论在多商品流中的应用——负载均衡及其对偶问题的线性规划建模一、最优化理论简介最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸多决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。最优化方法是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统，求得一个合理运用人力、物

2、力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、国防等各个领域，发挥着越来越重要的作用。本文将着重介绍在通信网络中，为了满足各个不同的业务所要求的网络宽带的分配，也就是多商品流问题的最优化方法模型的建立和及其对偶问题的线性规划建模。二、多商品流问题1、多商品流简介网络的主要作用是将业务从源端送到宿端。为了充分利用网络的资源，包括线路、转接设备等，总是希望合理地分配流量，

3、以是从源端到宿端的流量尽可能的大，传输的代价尽可能的小。但网络内流量分配并不是任意的，它受限于网络的拓扑结构，边和端的容量及费用，另外可能还有各种别的限制。如果将网络中节点间的业务看作是一个流的话，为满足一对节点对之间的业务需求而涉及业务流路径带宽分配被称作为单商品流问题。然而，现实生活中我们要面对的却是网络中各个节点对，而不只是一个节点对之间存在业务需求。针对多个节点对的业务，我们需要设计多商品流问题的最优化线性规划建模方法。2、多商品流负载均衡问题的描述多商品流问题有多个研究方向，本文研究的是多商品流的最佳路由负载均衡问题。给定一个通信网

4、络拓扑图G(V,E)，其中V表示的是所有节点的集合，E表示的是所有链路的集合，G(V,E)表示所有的点与边之间的通过一定连接关系所构成的图。接下来给定部分或者全部节点对之间的流量需求：(1)共计K个这样的需求，编号k=1,2,…,K(2)第k个需求的大小为hk，第k个需求下的源端点和宿端点分别为sk和dk。除了源宿端点外的其他节点，比如节点i，用vi表示；lij表示节点i和j之间的链路边；第k个需求下lij边上的流量用xijk表示。另外，网络拓扑中每条边上的单位流量的代价为cij，边的带宽即容量为uij。目标函数是所有链路边上带宽利用率的最

5、大值z，最终目标是最小化z。为了便于理解负载均衡问题，首先来分析最佳路由的一般问题。多商品流最佳路由一般问题要求是为所有的需求寻找合适的路径，并且要求目标函数达到最优，这里的优化目标函数不是上述的链路利用率z，而是所有K个业务的流量总代价，即最小化流量代价之和。值得注意的是：1)每个节点对之间的需求不是必为1，而是预先给定的值hk2)不是所有节点对之间都有需求3)边上代价cij的含义是单位流量的代价。给出通信网络模型后，我们可以直观地感觉到这显然已经不能用普通的算法来求解，而需要应用线性规划建模的思想来解决多商品流问题。三、负载均衡的线性规划

6、建模1、最佳路由一般问题的线性规划建模根据上文所述的网络模型，根据线性规划建模的思想，我们可以得出以下的目标函数以及多商品流最佳路由的一般问题的各个约束条件。目标函数中的fx=k(i,j)ϵEcijxijk。第一行以及第二行分别是在任意k个业务需求hk下流出源点和流入宿点的流量约束。第三行是除了源点和宿点之外的其他节点在任意k个业务下的流入流量等于流出流量的约束。第四个表达式是每条边lij上在所有K个业务下的总流量满足小于等于这条边所对应的容量的约束。最后一行表达式是在任意k个业务下每条边的流量必须大于等于0的约束。这样，我们就建立起了多商品

7、流最佳路由一般问题的线性规划模型，通过计算机我们便可以得到所想要的最佳路由结果。理解了一般问题，下面我们将介绍多商品流负载均衡问题的最优化线性规划建模。2、最佳路由负载均衡问题的线性规划建模负载均衡问题是在一般问题上改变了最终所要求的目标而得来的。负载均衡问题要求的是在保证任意k个业务满足需求的情况下，使所有链路边中的最大链路利用率最小化，也就是说我们要求的是均衡的路由方式，而不是某条链路上利用率很高也就是说负载很重、很拥挤，而某些其他的链路则几乎没有负载。因此，我们的目标函数f(x)由一般问题中的总流量代价k(i,j)ϵEcijxijk转边

8、成最小化最大链路利用率z。当然，约束条件也要在一般问题的基础上做一定的修改。我们通过分析得到一下目标函数以及约束目标：与一般路由对比可以发现，我们将约束目标改为了M