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

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

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

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