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

最优化理论在多商品流中的应用——负载均衡及其对偶问题的线性规划建模、最优化理论简介最优化原理可这样阐述： 一个最优化策略具有这样的性质， 不论过去状态和决 策如何，对前面的决策所形成的状态而言，余下的诸多决策必须构成最优策略 简而言之， 一个最优化策略的子策略总是最优的 一个问题满足最优化原理又称 其具有最优子结构性质最优化方法是近几十年形成的， 它主要运用数学方法研究各种系统的优化途径 及方案，为决策者提供科学决策的依据 最优化方法的主要研究对象是各种有组 织系统的管理问题及其生产经营活动 最优化方法的目的在于针对所研究的系统， 求得一个合理运用人力、 物力和财力的最佳方案， 发挥和提高系统的效能及效益， 最终达到系统的最优目标 实践表明，随着科学技术的日益进步和生产经营的日 益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法， 被 人们广泛地应用到公共管理、 经济管理、 国防等各个领域， 发挥着越来越重要的 作用本文将着重介绍在通信网络中， 为了满足各个不同的业务所要求的网络宽带的 分配，也就是多商品流问题的最优化方法模型的建立和及其对偶问题的线性规划 建模二、多商品流问题1、多商品流简介网络的主要作用是将业务从源端送到宿端。

为了充分利用网络的资源， 包括线 路、转接设备等， 总是希望合理地分配流量， 以是从源端到宿端的流量尽可能的 大，传输的代价尽可能的小 但网络内流量分配并不是任意的， 它受限于网络的 拓扑结构，边和端的容量及费用，另外可能还有各种别的限制如果将网络中节点间的业务看作是一个流的话， 为满足一对节点对之间的业务 需求而涉及业务流路径带宽分配被称作为单商品流问题 然而，现实生活中我们 要面对的却是网络中各个节点对， 而不只是一个节点对之间存在业务需求 针对 多个节点对的业务，我们需要设计多商品流问题的最优化线性规划建模方法2、多商品流负载均衡问题的描述多商品流问题有多个研究方向，本文研究的是多商品流的最佳路由负载均衡 问题给定一个通信网络拓扑图G(V,E),其中V表示的是所有节点的集合，E表示 的是所有链路的集合，G(V,E )表示所有的点与边之间的通过一定连接关系所构成 的图接下来给定部分或者全部节点对之间的流量需求： (1)共计 K 个这样的需 求，编号k=1,2,…,K⑵第k个需求的大小为hk,第k个需求下的源端点和宿端 点分别为少和dk除了源宿端点外的其他节点，比如节点i，用vi表示；lj表示 节点i和j之间的链路边；第k个需求下lj边上的流量用xjk表示。

另外，网络 拓扑中每条边上的单位流量的代价为 Cij,边的带宽即容量为uj目标函数是所有链路边上带宽利用率的最大值 z,最终目标是最小化z为了便于理解负载均衡问题， 首先来分析最佳路由的一般问题 多商品流最佳 路由一般问题要求是为所有的需求寻找合适的路径， 并且要求目标函数达到最优， 这里的优化目标函数不是上述的链路利用率 z,而是所有K个业务的流量总代价， 即最小化流量代价之和值得注意的是： 1)每个节点对之间的需求不是必为 1， 而是预先给定的值 hk 2)不是所有节点对之间都有需求 3) 边上代价 cij 的含义 是单位流量的代价给出通信网络模型后， 我们可以直观地感觉到这显然已经不能用普通的算法来 求解，而需要应用线性规划建模的思想来解决多商品流问题三、负载均衡的线性规划建模1、最佳路由一般问题的线性规划建模根据上文所述的网络模型，根据线性规划建模的思想，我们可以得出以下的目 标函数以及多商品流最佳路由的一般问题的各个约束条件Minimize /(x)subject tok = 1,2 Ky喇-E弘=-冰{*(殉朋A XV — 工 x/i ~ k~ 1,2 K〉琲 < u^, for each (ij) 6 E isTskXn > 0f for each k9 and each (ij E £目标函数中的？??？ = 》?？》（？？ ??）?????????第一行以及第二行分别是在任意 k个业务需求hk下流出源点和流入宿点的流 量约束。

第三行是除了源点和宿点之外的其他节点在任意 k个业务下的流入流量 等于流出流量的约束第四个表达式是每条边 lj上在所有K个业务下的总流量 满足小于等于这条边所对应的容量的约束最后一行表达式是在任意k个业务下 每条边的流量必须大于等于0的约束这样，我们就建立起了多商品流最佳路由一般问题的线性规划模型， 通过计算 机我们便可以得到所想要的最佳路由结果 理解了一般问题，下面我们将介绍多 商品流负载均衡问题的最优化线性规划建模2、最佳路由负载均衡问题的线性规划建模负载均衡问题是在一般问题上改变了最终所要求的目标而得来的 负载均衡问题要求的是在保证任意k个业务满足需求的情况下，使所有链路边中的最大链路 利用率最小化，也就是说我们要求的是均衡的路由方式， 而不是某条链路上利用率很高也就是说负载很重、很拥挤，而某些其他的链路则几乎没有负载因此， 我们的目标函数f(x)由一般冋题中的总流量代价刀??召??,??)?？????转边成最小化最 大链路利用率Z当然，约束条件也要在一般问题的基础上做一定的修改我们通过分析得到一下目标函数以及约束目标:Minimize zsubject toy屯-工%=吐 爲-工 xJdk = ~hk>{/： {/：yj)e£)Ac = 1,2f K2 4 - X 琲=°-》Xq < for each (ij) G ElsksKxfy > 0t for each ktand each (t/ 6 E与一般路由对比可以发现，我们将约束目标改为了 Min(z)，即最小化链路利 用率，其中z是所有链路利用率的集合，是一个矢量。

约束条件部分，只有第四 行的流量约束不等式的右边由Uij变为了 zuij，也就是链路容量利用率当约束目 标达到最优时，实际上这个不等式取到了等式至此，我们便得到了通信网络多商品流最佳路由问题的负载平衡问题的线性规 划建模3、负载均衡问题的对偶问题线性规划建模根据最优化理论的知识我们了解到， 对于每一个给定的线性规划问题， 都存在着与之对应的对偶线性规划这两种线性规划的最优解之间存在着密切的联系 那么，负载均衡问题存在对偶问题嘛？如果存在， 负载均衡问题的对偶问题是什么？怎么通过最优化理论的知识来 建立线性规划模型？下面我们就来对其进行分析首先，我们需要2套对偶变量：p （流守恒约束）和q （容量约束）应用最优化理论中对 偶问题的分析方法，我们可以将 （三-2）中的约束条件转换为对偶形式：根据对偶相关知识，还应该添加两个针对对偶变量 p和q约束，即??< 0, ?? ?????其中 free 表示的是自由变量，也就是说 p的符号不定，可以大于等于 0也可以小于0变形得:工皿1-嘛）+ [ 1 z\ (U) /于原问题中z为自由变量，所以该项系数必须等于 0 ；第三行由于原问题中 Xjk大于等于0，所以在对偶问题中该项系数必须大于等于 0，否则Xjk可以取到正无穷大来使等式左端达到最小，这显然是与原问题相悖的。

在上述约束中令rij=-qij，可得:KMaximize 工 一 p%)feisubject toPy - pf + r[f > 0,X D V(ij)假定主问题的最佳解中，Xjk取值大于0,根据互不松弛定理可知， 其对应的对偶约束取等 号，即: ???- ???+ ????? 0只考虑特定的需求 k,其流变量取值大于 0的边构成一些路径， 如下图所示：只看其中的一条路径，例如 sabt，可得:Pa-Ps + rsa = 0 pft — p« + - °Pt - Pb + % = 0对上式求和可得：若以 rij为权重，该路径长度等于 ps-pt那其他路径呢？例如 sbt？Pb~Ps + rsa > 0Pt-Pb + rbt = 0可知，达到最优解的路径比其他路径的长度要短， 也就是说该问题的最佳解实际上就在最短 路上！ 而最短路的算法是与之相比更容易实现的 原本较为复杂的负载均衡问题， 如果转换 成其对偶问题，只要给出合适的权重 rij ，原问题就能转换成对偶问题，然后通过最短路算法求得最佳解我们知道， Internet 的路由协议是基于最短路的 控制路由的唯一方法是设置不同的权重 怎样设置权重才是最佳的呢？最佳路由问题的对偶提供了一条思路：根据优化目标建模 OR问题；求解 OR 问题得到的对偶变量取值，其实就是最佳权重。

需要注意的是：即使得到了 最佳权重， 沿着最短路安排流量也不完全等价于原问题的最佳解 这是因为对偶问题其实并 没有得到原问题所要求的分流比例信息， 也就是并没有得到链路利用率， 但是我们是真的必 需要得到链路利用率吗？不是的我们实际上希望得到的是 k 个业务在图中的流量分配 因此 对偶解应该看作是对原最佳解的近似，但是却是我们实际上需要的解四、总结最佳路由问题与最短路问题表面上看有很大不同， 但上述结论表明， 它们具有深层次的联 系对偶的思想为我们提供了得到这种思路的一种可能的手段 通过上面的分析问题解决问题的过程，我认识到了最优化理论的重要性以及线性规划建模在实际生活中的应用很高兴自己能有幸上最优化理论这门课， 它真的让我学到了很多， 也了解了一些其他的知 识，比如从问题的另一面去分析问题说不定能达到意想不到的效果。