最優(yōu)化理論在多商品流中的應用

1、最優(yōu)化理論在多商品流中的應用負載均衡及其對偶問題的線性規(guī)劃建模一、最優(yōu)化理論簡介 最優(yōu)化原理可這樣闡述：一個最優(yōu)化策略具有這樣的性質，不論過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸多決策必須構成最優(yōu)策略。簡而言之，一個最優(yōu)化策略的子策略總是最優(yōu)的。一個問題滿足最優(yōu)化原理又稱其具有最優(yōu)子結構性質。 最優(yōu)化方法是近幾十年形成的，它主要運用數學方法研究各種系統(tǒng)的優(yōu)化途徑及方案，為決策者提供科學決策的依據。最優(yōu)化方法的主要研究對象是各種有組織系統(tǒng)的管理問題及其生產經營活動。最優(yōu)化方法的目的在于針對所研究的系統(tǒng)，求得一個合理運用人力、物力和財力的最佳方案，發(fā)揮和提高系統(tǒng)的效能及效益，最終

2、達到系統(tǒng)的最優(yōu)目標。實踐表明，隨著科學技術的日益進步和生產經營的日益發(fā)展，最優(yōu)化方法已成為現代管理科學的重要理論基礎和不可缺少的方法，被人們廣泛地應用到公共管理、經濟管理、國防等各個領域，發(fā)揮著越來越重要的作用。本文將著重介紹在通信網絡中，為了滿足各個不同的業(yè)務所要求的網絡寬帶的分配，也就是多商品流問題的最優(yōu)化方法模型的建立和及其對偶問題的線性規(guī)劃建模。二、多商品流問題1、多商品流簡介 網絡的主要作用是將業(yè)務從源端送到宿端。為了充分利用網絡的資源，包括線路、轉接設備等，總是希望合理地分配流量，以是從源端到宿端的流量盡可能的大，傳輸的代價盡可能的小。但網絡內流量分配并不是任意的，它受限于網絡的拓

3、撲結構，邊和端的容量及費用，另外可能還有各種別的限制。 如果將網絡中節(jié)點間的業(yè)務看作是一個流的話，為滿足一對節(jié)點對之間的業(yè)務需求而涉及業(yè)務流路徑帶寬分配被稱作為單商品流問題。然而，現實生活中我們要面對的卻是網絡中各個節(jié)點對，而不只是一個節(jié)點對之間存在業(yè)務需求。針對多個節(jié)點對的業(yè)務，我們需要設計多商品流問題的最優(yōu)化線性規(guī)劃建模方法。2、多商品流負載均衡問題的描述 多商品流問題有多個研究方向，本文研究的是多商品流的最佳路由負載均衡問題。給定一個通信網絡拓撲圖G(V,E)，其中V表示的是所有節(jié)點的集合，E表示的是所有鏈路的集合，G(V,E)表示所有的點與邊之間的通過一定連接關系所構成的圖。接下來給定

4、部分或者全部節(jié)點對之間的流量需求：(1)共計K個這樣的需求，編號k=1,2,K (2)第k個需求的大小為hk，第k個需求下的源端點和宿端點分別為sk和dk。除了源宿端點外的其他節(jié)點，比如節(jié)點i，用vi表示；lij表示節(jié)點i和j之間的鏈路邊；第k個需求下lij邊上的流量用xijk表示。另外，網絡拓撲中每條邊上的單位流量的代價為cij，邊的帶寬即容量為uij。目標函數是所有鏈路邊上帶寬利用率的最大值z，最終目標是最小化z。為了便于理解負載均衡問題，首先來分析最佳路由的一般問題。多商品流最佳路由一般問題要求是為所有的需求尋找合適的路徑，并且要求目標函數達到最優(yōu)，這里的優(yōu)化目標函數不是上述的鏈路利用率

5、z，而是所有K個業(yè)務的流量總代價，即最小化流量代價之和。值得注意的是：1)每個節(jié)點對之間的需求不是必為1，而是預先給定的值hk 2)不是所有節(jié)點對之間都有需求 3) 邊上代價cij的含義是單位流量的代價。給出通信網絡模型后，我們可以直觀地感覺到這顯然已經不能用普通的算法來求解，而需要應用線性規(guī)劃建模的思想來解決多商品流問題。三、負載均衡的線性規(guī)劃建模1、最佳路由一般問題的線性規(guī)劃建模 根據上文所述的網絡模型，根據線性規(guī)劃建模的思想，我們可以得出以下的目標函數以及多商品流最佳路由的一般問題的各個約束條件。目標函數中的fx=k(i,j)Ecijxijk。第一行以及第二行分別是在任意k個業(yè)務需求hk

6、下流出源點和流入宿點的流量約束。第三行是除了源點和宿點之外的其他節(jié)點在任意k個業(yè)務下的流入流量等于流出流量的約束。第四個表達式是每條邊lij上在所有K個業(yè)務下的總流量滿足小于等于這條邊所對應的容量的約束。最后一行表達式是在任意k個業(yè)務下每條邊的流量必須大于等于0的約束。這樣，我們就建立起了多商品流最佳路由一般問題的線性規(guī)劃模型，通過計算機我們便可以得到所想要的最佳路由結果。理解了一般問題，下面我們將介紹多商品流負載均衡問題的最優(yōu)化線性規(guī)劃建模。2、最佳路由負載均衡問題的線性規(guī)劃建模 負載均衡問題是在一般問題上改變了最終所要求的目標而得來的。負載均衡問題要求的是在保證任意k個業(yè)務滿足需求的情況下

7、，使所有鏈路邊中的最大鏈路利用率最小化，也就是說我們要求的是均衡的路由方式，而不是某條鏈路上利用率很高也就是說負載很重、很擁擠，而某些其他的鏈路則幾乎沒有負載。因此，我們的目標函數f(x)由一般問題中的總流量代價k(i,j)Ecijxijk轉邊成最小化最大鏈路利用率z。當然，約束條件也要在一般問題的基礎上做一定的修改。 我們通過分析得到一下目標函數以及約束目標：與一般路由對比可以發(fā)現，我們將約束目標改為了Min(z)，即 最小化鏈路利用率，其中z是所有鏈路利用率的集合，是一個矢量。約束條件部分，只有第四行的流量約束不等式的右邊由uij變?yōu)榱藌uij，也就是鏈路容量利用率。當約束目標達到最優(yōu)時，

8、實際上這個不等式取到了等式。至此，我們便得到了通信網絡多商品流最佳路由問題的負載平衡問題的線性規(guī)劃建模。3、負載均衡問題的對偶問題線性規(guī)劃建模 根據最優(yōu)化理論的知識我們了解到，對于每一個給定的線性規(guī)劃問題，都存在著與之對應的對偶線性規(guī)劃。這兩種線性規(guī)劃的最優(yōu)解之間存在著密切的聯系。那么，負載均衡問題存在對偶問題嘛？如果存在，負載均衡問題的對偶問題是什么？怎么通過最優(yōu)化理論的知識來建立線性規(guī)劃模型？下面我們就來對其進行分析。 首先，我們需要2套對偶變量：p（流守恒約束）和q（容量約束）。應用最優(yōu)化理論中對偶問題的分析方法，我們可以將(三-2)中的約束條件轉換為對偶形式： 根據對偶相關知識，還應該

9、添加兩個針對對偶變量p和q約束，即q0,p free。其中free表示的是自由變量，也就是說p的符號不定，可以大于等于0也可以小于0。變形得： 故意將其寫為三行是為了便于分析。等式右邊第一行就是對偶問題的目標函數；第二行由于原問題中z為自由變量，所以該項系數必須等于0；第三行由于原問題中xijk大于等于0，所以在對偶問題中該項系數必須大于等于0，否則xijk可以取到正無窮大來使等式左端達到最小，這顯然是與原問題相悖的。 在上述約束中令rij=-qij，可得：假定主問題的最佳解中，xijk取值大于0，根據互不松弛定理可知，其對應的對偶約束取等號，即：pjk-pik+rij=0。只考慮特定的需求k

10、，其流變量取值大于0的邊構成一些路徑，如下圖所示： 只看其中的一條路徑，例如sabt，可得： 對上式求和可得：若以rij為權重，該路徑長度等于ps-pt。那其他路徑呢？例如sbt？ 對上兩式求和可得：若以rij為權重，該路徑長度大于等于ps-pt。這說明了什么呢？對比可知，達到最優(yōu)解的路徑比其他路徑的長度要短，也就是說該問題的最佳解實際上就在最短路上！而最短路的算法是與之相比更容易實現的。原本較為復雜的負載均衡問題，如果轉換成其對偶問題，只要給出合適的權重rij，原問題就能轉換成對偶問題，然后通過最短路算法求得最佳解。 我們知道，Internet的路由協議是基于最短路的?？刂坡酚傻奈ㄒ环椒ㄊ窃O置不同的權重。怎樣設置權重才是最佳的呢？最佳路由問題的對偶提供了一條思路：根據優(yōu)化目標建模OR問題；求解OR問題得到的對偶變量取值，其實就是最佳權重。需要注意的是：即使得到了最佳權重，沿著最短路安排流量也不完全等價于原問題的最佳解。這是因為對偶問題其實并沒有得到原問題所要求的分流比例信息，也就是并沒有得到鏈路利用率，但是我們是真的必需要得到鏈路利用率嗎？不是的我們實際上希望得到的是k個業(yè)務在圖中的流量分配。因此對偶解應該看作是對原最佳解的近似，但是卻是我們實際上需要的解。四、總結最佳路由問題與最短路問題表面