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

《最优化理论在多商品流中的应用》由会员分享，可在线阅读，更多相关《最优化理论在多商品流中的应用（9页珍藏版）》请在金锄头文库上搜索。

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

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

3、，它受限于网络的 拓扑结构，边和端的容量及费用，另外可能还有各种别的限制。如果将网络中节点间的业务看作是一个流的话，为满足一对节点对之间的业务 需求而涉及业务流路径带宽分配被称作为单商品流问题。然而，现实生活中我们 要面对的却是网络中各个节点对，而不只是一个节点对之间存在业务需求。针对 多个节点对的业务，我们需要设计多商品流问题的最优化线性规划建模方法。2、多商品流负载均衡问题的描述多商品流问题有多个研究方向，本文研究的是多商品流的最佳路由负载均衡 问题。给定一个通信网络拓扑图G(V,E)，其中V表示的是所有节点的集合，E表示 的是所有链路的集合，G(V,E)表示所有的点与边之间的通过一定连接

4、关系所构成 的图。接下来给定部分或者全部节点对之间的流量需求：(1)共计 K 个这样的需 求，编号k=l,2,.,K (2)第k个需求的大小为hk，第k个需求下的源端点和宿端 点分别为sk和dk。除了源宿端点外的其他节点，比如节点i,用*表示；I表示 节点i和j之间的链路边；第k个需求下lij边上的流量用Xjjk表示。另外，网络 拓扑中每条边上的单位流量的代价为边的带宽即容量为七。目标函数是所 有链路边上带宽利用率的最大值z,最终目标是最小化z。为了便于理解负载均衡问题，首先来分析最佳路由的一般问题。多商品流最佳 路由一般问题要求是为所有的需求寻找合适的路径，并且要求目标函数达到最优 这里的优

5、化目标函数不是上述的链路利用率z,而是所有K个业务的流量总代价， 即最小化流量代价之和。值得注意的是：1)每个节点对之间的需求不是必为 1， 而是预先给定的值 hk 2)不是所有节点对之间都有需求 3) 边上代价 cij 的含义 是单位流量的代价。给出通信网络模型后，我们可以直观地感觉到这显然已经不能用普通的算法来 求解，而需要应用线性规划建模的思想来解决多商品流问题。三、负载均衡的线性规划建模1、最佳路由一般问题的线性规划建模根据上文所述的网络模型，根据线性规划建模的思想，我们可以得出以下的目标函数以及多商品流最佳路由的一般问题的各个约束条件。subject toMinimizefor ea

6、ch (ij) e Efor each ftrand each (ij) E EM uip炉的)詢目标函数中的 f(X)=M(i,j)E CijXij。第一行以及第二行分别是在任意 k 个业务需求 hk 下流出源点和流入宿点的流 量约束。第三行是除了源点和宿点之外的其他节点在任意 k 个业务下的流入流量 等于流出流量的约束。第四个表达式是每条边lij上在所有K个业务下的总流量 满足小于等于这条边所对应的容量的约束。最后一行表达式是在任意k个业务下 每条边的流量必须大于等于0的约束。这样，我们就建立起了多商品流最佳路由一般问题的线性规划模型，通过计算 机我们便可以得到所想要的最佳路由结果。理解了

7、一般问题，下面我们将介绍多 商品流负载均衡问题的最优化线性规划建模。2、最佳路由负载均衡问题的线性规划建模负载均衡问题是在一般问题上改变了最终所要求的目标而得来的。负载均衡问 题要求的是在保证任意 k 个业务满足需求的情况下，使所有链路边中的最大链路 利用率最小化，也就是说我们要求的是均衡的路由方式，而不是某条链路上利用 率很高也就是说负载很重、很拥挤，而某些其他的链路则几乎没有负载。因此， 我们的目标函数f(x)由一般问题中的总流量代价乙Y(zj)E cijxij转边成最小化最 大链路利用率z。当然，约束条件也要在一般问题的基础上做一定的修改。我们通过分析得到一下目标函数以及约束目标：Min

8、intize zsubject toX心厂乂糸=叭/：(A/)eUOTeFj(ij)eErisktdk气护for each (if/) e E 0r for each 比 and each (ij) E E与一般路由对比可以发现，我们将约束目标改为了 Min(z),即卩最小化链路利用率，其中z是所有链路利用率的集合，是一个矢量。约束条件部分，只有第四 行的流量约束不等式的右边由Uj变为了 ZUq,也就是链路容量利用率。当约束目 标达到最优时，实际上这个不等式取到了等式。至此，我们便得到了通信网络多商品流最佳路由问题的负载平衡问题的线性规 划建模。3、负载均衡问题的对偶问题线性规划建模根据最优化

9、理论的知识我们了解到，对于每一个给定的线性规划问题，都存在着与之对应 的对偶线性规划。这两种线性规划的最优解之间存在着密切的联系。那么，负载均衡问题存 在对偶问题嘛？如果存在，负载均衡问题的对偶问题是什么？怎么通过最优化理论的知识来 建立线性规划模型？下面我们就来对其进行分析。首先，我们需要2套对偶变量：p （流守恒约束）和q （容量约束）。应用最优化理论中对偶问题的分析方法，我们可以将（三-2）中的约束条件转换为对偶形式：心5?气心pq） = z +p：（护-澤j +条）/j /K+E臨卜汹-2母丿+菇j fc=i ji J根据对偶相关知识，还应该添加两个针对对偶变量p和q约束，即g 0t

10、V（ij）假定主问题的最佳解中，xjk取值大于0,根据互不松弛定理可知，其对应的对偶约束取等 号，即：叭_曾+冷=0。只考虑特定的需求k，其流变量取值大于0的边构成一些路径， 如下图所示：只看其中的一条路径，例如sabt，可得:对上式求和可得：若以rj为权重，该路径长度等于ps-pt。那其他路径呢？例如sbt？PbPs + rsa 0PtPb + rbt = 0对上两式求和可得：若以rj为权重，该路径长度大于等于ps-pt。这说明了什么呢？对比 可知，达到最优解的路径比其他路径的长度要短，也就是说该问题的最佳解实际上就在最短 路上！而最短路的算法是与之相比更容易实现的。原本较为复杂的负载均衡问

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