北航最優(yōu)化方法大作業(yè)參考

1、11流量工程問題流量工程問題1.1問題重述問題重述定義一個有向網(wǎng)絡(luò)G=(NE)，其中N是節(jié)點集，E是弧集。令A(yù)是網(wǎng)絡(luò)G的點弧關(guān)聯(lián)矩陣，即NE階矩陣，且第l列與弧里(Ij)對應(yīng)，僅第i行元素為1，第j行元素為1，其余元素為0。再令bm=(bm1…bmN)T，fm=(fm1…fmE)T，則可將等式約束表示成：Afm=bm本算例為一經(jīng)典TE算例。算例網(wǎng)絡(luò)有7個節(jié)點和13條弧，每條弧的容量是5個單位。此外有四個需求量均為4個單位的源一目的對，具

2、體的源節(jié)點、目的節(jié)點信息如圖所示。這里為了簡單，省區(qū)了未用到的弧。此外，弧上的數(shù)字表示弧的編號。此時，c=((55…5)113)T，根據(jù)上述四個約束條件，分別求得四個情況下的最優(yōu)決策變量x=((x12x13…x75)113)。圖1網(wǎng)絡(luò)拓撲和流量需求31.2.4算例算例4（b4=[4000004]T）MinimizecTx4SubjecttoAx4=b4X4=0利用Matlab編寫對偶單純形法程序，可求得:最優(yōu)解為x4=[40040000

3、04000]T對應(yīng)的最優(yōu)值cTx4=601.3計算結(jié)果及結(jié)果說明計算結(jié)果及結(jié)果說明1.3.1算例算例1（b1=[4400000]T）算例1中，由b1可知，節(jié)點2為需求節(jié)點，節(jié)點1為供給節(jié)點，由節(jié)點1將信息傳輸至節(jié)點2的最短路徑為弧1。圖2算例1最優(yōu)傳輸示意圖求得的最優(yōu)解為x1=[4000000000000]T，即只經(jīng)過弧1運輸4個單位流量，其余弧無流量。又因為，每條弧的費用均為5，所以最小費用為20。經(jīng)分析，計算結(jié)果合理可信。1.3.2