1、矩陣理論在通信網絡中的應用利用幺模矩陣分析最小費用流問題摘要 將通信網絡中節點間的業務看作是一個流，假設一對節點間存在v個流量的業務需求，怎樣使得最終達到滿足要求且費用最小。通過線性規劃建模，利用矩陣理論中完全幺模矩陣以及幺模矩陣的知識，保證求得的最優解為整數解，使得最小費用流問題得以解決。關鍵字：最小費用流，完全幺模矩陣，幺模矩陣，整數解ABSTRACTView the business communication between nodes in the network as a stream, a v of the flow between nodes business needs, h

2、ow to make the end meet the requirements and minimum cost. The linear programming model, by using matrix theory totally unimodular matrix and knowledge unimodular matrix, guarantee to obtain the optimal solution for the integer solution, so that the minimum cost flow problem can be solved.Key Words:

3、 Minimum Cost Flow ,Totally Unimodular ,Unimodular , integer solution第一章 矩陣理論簡介 根據世界數學發展史的記載，矩陣理論概念剩余19世紀50年代，是為了解決線性方程組的需要而誕生的。1855年，英國數學家Caylag在研究線性變換下的不變量時，為了簡介、方便而引入了矩陣的概念。矩陣的理論發展非常的迅速，到19世紀末，矩陣理論體系已經基本形成。到20世紀，矩陣理論得到了進一步的發展。目前，它已近發展成為在物理、控制論、經濟學、等學科有大量應用的分支。 用矩陣的理論與方法來處理通信網絡技術中的各種問題已越來越普遍。在通信工程

4、技術中引進矩陣理論不僅使理論的表達極為簡捷，而且對理論的實質刻畫也更為深刻，這一點是不容置疑的，更由于計算機和計算方法的普及發展，不僅為矩陣理論的應用開辟了廣闊的前景，也使通信網絡技術的研究發生新的變化，開拓了嶄新的研究途徑，例如網絡中的最小費用流問題、最短分離路徑對問題、多商品流問題等，無不與矩陣理論發生緊密結合。因此矩陣的理論與方法已成為研究通信工程技術的數學基礎。第二章 最小費用流問題1、最小費用流簡介 通信網絡的主要作用是將業務從源端發送到宿端。為了充分利用網絡的資源，包括線路、轉接設備等，總是希望合理地分配流量，以是從源端到宿端的流量盡可能的大，傳輸的代價盡可能的小。但網絡內流量分配

5、并不是任意的，它受限于網絡的拓撲結構，邊和端的容量及費用，另外可能還有各種別的限制。 在通信網絡中，如果將網絡中節點間的業務看作是一個流的話，為滿足一對節點對之間的業務需求而涉及業務流路徑帶寬分配被稱作為單商品流問題。現假設一對節點間存在v個流量的業務需求，即需要在通信網絡拓撲中通過利用其他一些中間節點并且合理的分配路徑來搬運v個單位的流，使得最終達到滿足要求時的總費用代價最小。2、最小費用流問題的描述 通信網絡中的各個交換機或者路由器通常可以看做是網絡拓撲圖中的一個個節點，它們之間的鏈路可以描述為各個節點間相連的線段。通過這樣的轉換就可以將網絡拓撲通過圖的形式描繪出來，以便進一步分析。給定一

6、個通信網絡拓撲圖G(V,E)，其中V表示的是所有節點的集合，E表示的是所有鏈路的集合，G(V,E)表示所有的點與邊之間的通過一定連接關系所構成的圖。除了源、宿端點外的其他節點，比如節點i，用vi表示；lij表示節點i和j之間的鏈路邊； lij邊上的流量用xij表示。另外，給定網絡拓撲中每條邊上的單位流量的代價為cij，邊的帶寬即容量為uij。接下來給定一對節點對之間的業務流量需求的理論描述：(1)源點s到宿點t之間需要v個流量的業務，即源點s需要流出v個單位的流量，宿點t需要流入v個單位的流量；并且假設流入為正，流出為負 (2)網絡中除了源點s和宿點t之外的其他節點iV-s,t流入的流量和流出

7、的流量應該守恒，即相加為0 (3)每條鏈路邊上的流量xij應該滿足大于等于0且小于等于這條邊lij上對應的帶寬容量uij (4)優化目標是最小化總的鏈路流量與單位流量代價的乘積的和。第三章 矩陣理論分析最小費用流1、最小費用流的矩陣形式 通過上面的分析，我們可以通過線性規劃建模得到以下結果： 上面的線性規劃建模結果是在確定的源點到宿點存在v個單位流的情況。實際情況下，我們考慮從源節點到宿節點，圖中每個節點i的需求等于b(i)，而不再是單一值v或者0。這種情況下，上面的表達式需要做一點兒改變： 對比這兩個表達式，我們可以看到只有約束條件的等式右端從v或者0變為了b(i)，b(i)表示頂點i的需求

8、量或者供應量。需求量為負整數，供應量為正整數；所有的需求量之和等于供應量之和，即i=1nbi=0。b(i)>0，則頂點i為供應節點；b(i)<0，則頂點i為需求節點；b(i)=0，則頂點i為轉運節點。 為了書寫方便，我們可以將約束條件及約束目標寫為矩陣形式。這里定義m維矢量c=cij、x=xij、u=uij，n維矢量b=b(i)；將第一行的所有約束條件寫為n×m維的矩陣N，矩陣N中的元素取值只為1或者-1；當頂點i是邊j的起點時，Nij=1；當頂點i是邊j的終點時，Nij=1；我們將矩陣N成為點邊關聯矩陣。這樣線性規劃表達式可以這樣描述： 觀察上述表達式，注意到最小費用流

9、問題的矩陣形式具有最優化理論中單純型法的標準型形式，即xRn|Ax=b,x0，這與最小費用流問題的矩陣形式中的約束條件xRn|Nx=b,x0具有相同的形式 。這樣我們就可以利用最優化理論中的單純型法來分析求解這個矩陣問題。但是，求出來的解是整數解嗎？如果不是整數解還滿足我們的要求嗎？這個問題將在(三-3)部分得到解答，在此之前，我們首先來分析矩陣理論中完全幺模矩陣和幺模矩陣。2、完全幺模矩陣和幺模矩陣2.1、完全幺模矩陣 若矩陣A的說有字方陣的行列式都為0或±1，則矩陣A為完全幺模矩陣。接下來，我們利用歸納法證明上文中提到的點邊關聯矩陣N是“完全幺模矩陣”。2.2、幺模矩陣 假定p&

10、#215;q矩陣A行滿秩，若A的所有基矩陣(A的p×q子方陣，且該矩陣的所有列線性無關)的行列式都為±1，則矩陣A為幺模矩陣。接下來我們證明完全幺模矩陣是幺模矩陣。假定A是完全幺模矩陣；則由定義，其所有子方陣的行列式的取值都是0或±1。A的基矩陣必是子方陣；而且基矩陣的行列式不能為0。故而A的基矩陣行列式為±1，因此完全幺模矩陣是幺模矩陣。緊接著，我們證明幺模矩陣的基本可行解必為整數。首先，基本解的非基變量取值都為0；基變量部分XB由A的基矩陣B定義：BXB=b。然后，令Bjb表示用矢量b替換B的第j列后得到的矩陣；xj表示XB的第j個元素。最后，由線性

11、代數矩陣理論部分的克拉默(Cramer)法則求解可得xj=|Bjb|/|B|。由于Bjb是整數矩陣，B的行列式為±1，顯然基本結構xj都是整數；另外基本可行解必是基本解。由此，我們可得以下結論：假定矩陣A為滿秩且為幺模矩陣，同時假定矢量b的元素都是整數；則由xRn|Ax=b,x0定義的多面體中，基本可行解必為整數。3、最小費用流的整數解3.1、最優解是否為整數解 回到(三-1)中最后的問題，得到的最小費用流問題的矩陣形式，即：我們已經知道，通過求解上面的線性規劃模型便可以得到最小費用流問題的最優解，但是求出來的這個解一定會是整數解嗎？如果不是整數解，那便不滿足我們的要求，因為我們不能

12、將邊上流量存在小數的路徑成為一條由源點到宿點的路徑。怎樣避免這個問題呢？首先想到的是我們可以再約束條件中加入邊上流變量xij必須為整數的約束，即xij0,1；也就是說邊lij上要么存在1的流量，要么沒有流從這條邊上流過。但是增加了約束條件必然會增加運算量，這顯然是我們不希望看到的。3.2、關聯矩陣N是幺模矩陣實際上，通過(三-2)中的矩陣理論知識，我們注意到關聯矩陣N是完全幺模矩陣，根據(三-2.2)中的結論可知關聯矩陣N必是幺模矩陣，從而以它為系數矩陣的最小費用流問題中，基本可行解必是整數。若線性規劃存在最佳解，必可在某個基本可行解處得到，因此，最小費用流問題問題的最佳解必是整數解。3.3、結論至此，我們首先對最小費用流問題進行了線性規劃建模，然后我們對線性規劃建模求得的解是否為整數解提出了疑問。接下來，我們引入了矩陣理論中完全幺模矩陣和幺模矩陣的知識，得到了幺模矩陣的解必為整數解的結論。最后，我們注意到關聯矩陣N實際上是完全幺模矩陣，也就是幺模矩陣；這樣一來，最小費用流問題中建立的線性規劃模型的解便必為整