矩陣?yán)碚撛谕ㄐ诺膽?yīng)用

矩陣?yán)碚撛谕ㄐ啪W(wǎng)絡(luò)中的應(yīng)用——利用幺模矩陣分析最小費(fèi)用流問題摘要將通信網(wǎng)絡(luò)中節(jié)點(diǎn)間的業(yè)務(wù)看作是一個(gè)流，假設(shè)一對節(jié)點(diǎn)間存在v個(gè)流量的業(yè)務(wù)需求，怎樣使得最終達(dá)到滿足要求且費(fèi)用最小。通過線性規(guī)劃建模，利用矩陣?yán)碚撝型耆勰＞仃囈约扮勰＞仃嚨闹R，保證求得的最優(yōu)解為整數(shù)解，使得最小費(fèi)用流問題得以解決。關(guān)鍵字：最小費(fèi)用流，完全幺模矩陣，幺模矩陣，整數(shù)解ABSTRACTViewthebusinesscommunicationbetweennodesinthenetworkasastream,avoftheflowbetweennodesbusinessneeds,howtomaketheendmeettherequirementsandminimumcost.Thelinearprogrammingmodel,byusingmatrixtheorytotallyunimodularmatrixandknowledgeunimodularmatrix,guaranteetoobtaintheoptimalsolutionfortheintegersolution,sothattheminimumcostflowproblemcanbesolved.KeyWords:MinimumCostFlow,TotallyUnimodular,Unimodular,integersolution第一章矩陣?yán)碚摵喗榫烤€性變換下的不變量時(shí)，為了簡介、方便而引入了矩陣的概念。矩陣的理論發(fā)展非常的迅速，到19世紀(jì)末，矩陣?yán)碚擉w系已經(jīng)基本形成。到20世紀(jì)，矩陣?yán)碚摰玫搅诉M(jìn)一步的發(fā)展。目前，它已近發(fā)展成為在物理、控制論、經(jīng)濟(jì)學(xué)、等學(xué)科有大量應(yīng)用的分支。用矩陣的理論與方法來處理通信網(wǎng)絡(luò)技術(shù)中的各種問題已越來越普遍。在通信工程技術(shù)中引進(jìn)矩陣?yán)碚摬粌H使理論的表達(dá)極為簡捷，而且對理論的實(shí)質(zhì)刻畫也更為深刻，這一點(diǎn)是不容置疑的，更由于計(jì)算機(jī)和計(jì)算方法的普及發(fā)展，不僅為矩陣?yán)碚摰膽?yīng)用開辟了廣闊的前景，也使通信網(wǎng)絡(luò)技術(shù)的研究發(fā)生新的變化，開拓了嶄新的研究途徑，例如網(wǎng)絡(luò)中的最小費(fèi)用流問題、最短分離路徑對問題、多商品流問題等，無不與矩陣?yán)碚摪l(fā)生緊密結(jié)合。因此矩陣的理論與方法已成為研究通信工程技第二章最小費(fèi)用流問題1、最小費(fèi)用流簡介通信網(wǎng)絡(luò)的主要作用是將業(yè)務(wù)從源端發(fā)送到宿端。為了充分利用網(wǎng)絡(luò)的資源，包括線路、轉(zhuǎn)接設(shè)備等，總是希望合理地分配流量，以是從源端到宿端的流量盡可能的大，傳輸?shù)拇鷥r(jià)盡可能的小。但網(wǎng)絡(luò)內(nèi)流量分配并不是任意的，它受限于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，邊和端的容量及費(fèi)用，另外可能還有各種別的限制。在通信網(wǎng)絡(luò)中，如果將網(wǎng)絡(luò)中節(jié)點(diǎn)間的業(yè)務(wù)看作是一個(gè)流的話，為滿足一對節(jié)點(diǎn)對之間的業(yè)務(wù)需求而涉及業(yè)務(wù)流路徑帶寬分配被稱作為單商網(wǎng)絡(luò)拓?fù)渲型ㄟ^利用其他一些中間節(jié)點(diǎn)并且合理的分配路徑來搬運(yùn)v個(gè)小。2、最小費(fèi)用流問題的描述通信網(wǎng)絡(luò)中的各個(gè)交換機(jī)或者路由器通?？梢钥醋鍪蔷W(wǎng)絡(luò)拓?fù)鋱D中的一個(gè)個(gè)節(jié)點(diǎn)，它們之間的鏈路可以描述為各個(gè)節(jié)點(diǎn)間相連的線段。通過這樣的轉(zhuǎn)換就可以將網(wǎng)絡(luò)拓?fù)渫ㄟ^圖的形式描繪出來，以便進(jìn)一步分表示的是所有鏈路的集合，G(V,E)表示所有的點(diǎn)與邊之間的通過一定連接關(guān)系所構(gòu)成的圖。除了源、宿端點(diǎn)外的其他節(jié)點(diǎn)，比如節(jié)點(diǎn)i，用v表iijijij外，給定網(wǎng)絡(luò)拓?fù)渲忻織l邊上的單位流量的代價(jià)為c，邊的帶寬即容量絡(luò)中除了源點(diǎn)s和宿點(diǎn)t之外的其他節(jié)點(diǎn)∈?{,}流入的流量和流出的流量應(yīng)該守恒，即相加為0(3)每條鏈路邊上的流量x應(yīng)該滿足ijij小化總的鏈路流量與單位流量代價(jià)的乘積的和。第三章矩陣?yán)碚摲治鲎钚≠M(fèi)用流1、最小費(fèi)用流的矩陣形式通過上面的分析，我們可以通過線性規(guī)劃建模得到以下結(jié)果：上面的線性規(guī)劃建模結(jié)果是在確定的源點(diǎn)到宿點(diǎn)存在v個(gè)單位流的情況。實(shí)際情況下，我們考慮從源節(jié)點(diǎn)到宿節(jié)點(diǎn)，圖中每個(gè)節(jié)點(diǎn)i的需求對比這兩個(gè)表達(dá)式，我們可以看到只有約束條件的等式右端從v或者0供應(yīng)量為正整數(shù)；所有的需求量之和等于供應(yīng)量之和，即∑=1()=為了書寫方便，我們可以將約束條件及約束目標(biāo)寫為矩陣形式。這里ijijijNijij我們將矩陣N成為點(diǎn)邊關(guān)聯(lián)矩陣。這樣線性規(guī)劃表達(dá)式可以這樣描述：觀察上述表達(dá)式，注意到最小費(fèi)用流問題的矩陣形式具有最優(yōu)化理論中單純型法的標(biāo)準(zhǔn)型形式，即{?|=,≥0}，這與最小費(fèi)用流問題的矩陣形式中的約束條件{?|=,≥0}具有相同的形式。這樣我們就可以利用最優(yōu)化理論中的單純型法來分析求解這個(gè)矩陣但是，求出來的解是整數(shù)解嗎如果不是整數(shù)解還滿足我們的要求嗎這個(gè)問題將在(三-3)部分得到解答，在此之前，我們首先來分析矩陣?yán)碚撝型耆勰＞仃嚭顽勰＞仃嚒?、完全幺模矩陣和幺模矩陣、完全幺模矩陣陣。接下來，我們利用歸納法證明上文中提到的點(diǎn)邊關(guān)聯(lián)矩陣N是“完全幺模矩陣”。幺模矩陣陣的所有列線性無關(guān))的行列式都為±1，則矩陣A為幺模矩陣。接下來我們證明完全幺模矩陣是幺模矩陣。假定A是完全幺模矩陣；則由定義，其所有子方陣的行列式的取值都A必是子方陣；而且基矩陣的行列式不能為0。故而A的基矩陣行列式為±1，因此完全幺模矩陣是幺模矩陣。緊接著，我們證明幺模矩陣的基本可行解必為整數(shù)。BBjbj表示X的第j個(gè)元素。最后，由線性代數(shù)矩陣?yán)碚摬糠值目死?Cramer)B得=||/||。由于B是整數(shù)矩陣，B的行列式為b±1，顯然基本結(jié)構(gòu)x都是整數(shù)；另外基本可行解必是基本解。由此，我j們可得以下結(jié)論：假定矩陣A為滿秩且為幺模矩陣，同時(shí)假定矢量b的元素都是整數(shù)；則由{?|=,≥0}定義的多面體中，基本可3、最小費(fèi)用流的整數(shù)解、最優(yōu)解是否為整數(shù)解回到(三-1)中最后的問題，得到的最小費(fèi)用流問題的矩陣形式，即：我們已經(jīng)知道，通過求解上面的線性規(guī)劃模型便可以得到最小費(fèi)用流問題的最優(yōu)解，但是求出來的這個(gè)解一定會是整數(shù)解嗎？如果不是整數(shù)解，那便不滿足我們的要求，因?yàn)槲覀儾荒軐⑦吷狭髁看嬖谛?shù)的路徑成為一條由源點(diǎn)到宿點(diǎn)的路徑。怎樣避免這個(gè)問題呢？首先想到的是我們可以再約束條件中加入邊上流變量x必須為整數(shù)的約束，即在1的流量，要么沒有流從這條邊上流過。但是增加了約束條件必然會增加運(yùn)算量，這顯然是我們不希望看到的。實(shí)際上，通過(三-2)中的矩陣?yán)碚撝R，我們注意到關(guān)聯(lián)矩陣N是完全幺模矩陣，根據(jù)(三中的結(jié)論可知關(guān)聯(lián)矩陣N必是幺模矩陣，從而以它為系數(shù)矩陣的最小費(fèi)用流問題中，基本可行解必是整數(shù)。若線性規(guī)劃存在最佳解，必可在某個(gè)基本可行解處得到，因此，最小費(fèi)用流問題問題的最佳解必是整數(shù)解。至此，我們首先對最小費(fèi)用流問題進(jìn)行了線性規(guī)劃建模，然后我們對線性規(guī)劃建模求得的解是否為整數(shù)解提出了疑問。接下來，我們引入了矩陣?yán)碚撝型耆勰＞仃嚭顽勰＞仃嚨闹R，得到了幺模矩陣的解必為整數(shù)解的結(jié)論。最后，我們注意到關(guān)聯(lián)矩陣N實(shí)際上是完全幺模矩陣，也就是幺模矩陣；這樣一來，最小費(fèi)用流問題中建立的線性規(guī)劃模型的解便必為整數(shù)解！最終