用蟻群算法求解最小極大流問(wèn)題.pdf

1、網(wǎng)絡(luò)流問(wèn)題是近幾十年來(lái)運(yùn)籌學(xué)、網(wǎng)絡(luò)分析等學(xué)科研究的熱點(diǎn)問(wèn)題。1997年, Shi-Yamamoto提出了最小極大流問(wèn)題,現(xiàn)已有的算法均是通過(guò)理論證明在多維空間中得到網(wǎng)絡(luò)的最小極大流,卻沒(méi)有基于蟻群算法研究最小極大流問(wèn)題。因此,鑒于該問(wèn)題的網(wǎng)絡(luò)特性和蟻群算法求解網(wǎng)絡(luò)問(wèn)題的優(yōu)越性,針對(duì)最小極大流問(wèn)題,可以采用以蟻群算法為基礎(chǔ)進(jìn)行算法設(shè)計(jì)從而求解最小極大流問(wèn)題。
　　首先,對(duì)最小極大流問(wèn)題進(jìn)行了理論分析,提出結(jié)合蟻群算法求解問(wèn)題的思想,

2、設(shè)計(jì)程序求解最小極大流問(wèn)題。接著,通過(guò)定理證明可知,最小極大流問(wèn)題可轉(zhuǎn)換為一個(gè)線性優(yōu)化問(wèn)題,構(gòu)造了適于蟻群算法的模型,運(yùn)用蟻群算法尋找該線性優(yōu)化方程的價(jià)值向量,并運(yùn)用MATLAB求解線性方程最優(yōu)解,該最優(yōu)解即為網(wǎng)絡(luò)的一個(gè)極大流,繼而得到最小極大流。
　　文章對(duì)一個(gè)復(fù)雜的交通模擬圖利用MATLAB編程求解最小極大流問(wèn)題。數(shù)值實(shí)驗(yàn)表明,基于蟻群算法的方法在最小極大流問(wèn)題上得到了較好的結(jié)果,分析的結(jié)果驗(yàn)證了該算法的可行性。通過(guò)數(shù)值實(shí)驗(yàn)得