運(yùn)用圖論理論優(yōu)化運(yùn)輸方案畢業(yè)論文-全文預(yù)覽
【正文】 網(wǎng)絡(luò),每條弧上,除了給的,還給出了一個(gè)單位流量的費(fèi)用,所謂的最小費(fèi)用最大流就是要求一個(gè)最大流,使得流的總運(yùn)輸費(fèi)用取得最小值,即:,其中. 求費(fèi)用為權(quán)的賦權(quán)圖的最短通路與網(wǎng)絡(luò)中的增廣路相對(duì)應(yīng),當(dāng)沿著一條關(guān)于可行流的可增廣路以調(diào)整得到可行流時(shí),費(fèi)用增量為: ()稱 為增廣路的“費(fèi)用”. 若是流量中所有可行流的費(fèi)用最小者,即可得到,即為所求的最小費(fèi)用最大流. 由于,它的頂點(diǎn)是原網(wǎng)絡(luò)的頂點(diǎn),而把中的每一條弧變成兩個(gè)相反方向的弧和,定義的權(quán)為: () () .1. 取 = 0。的弧為非飽和弧。,稱為發(fā)點(diǎn),稱為收點(diǎn),并稱為弧上的容量,簡(jiǎn)記為.滿足下列兩個(gè)條件的流稱為可行流: 1. 容量限制:對(duì)于,有。為弧集。的弧為零流弧。為未標(biāo)號(hào)點(diǎn)集合。第二個(gè)數(shù)字是單位方量的運(yùn)費(fèi),包括道路維修費(fèi)、筑路費(fèi)、運(yùn)輸費(fèi)等,用表示,用表示.圖1 運(yùn)輸線路示意圖圖1所示的運(yùn)輸圖可以抽象為圖2的有向網(wǎng)絡(luò).圖2 有向圖網(wǎng)絡(luò) ,增廣路為,割集弧如圖5虛線所截的飽和弧,被標(biāo)記點(diǎn)為,未被標(biāo)記點(diǎn)為。,以各倉(cāng)庫(kù)的物資儲(chǔ)備量、道路運(yùn)輸能力、各水庫(kù)大壩所需要的最小物資量為約束條件構(gòu)造模型如下: ()式中為第個(gè)倉(cāng)庫(kù)的物資儲(chǔ)備數(shù)量。規(guī)定從第個(gè)水庫(kù)到點(diǎn)的道路運(yùn)輸能力為,:1. 對(duì)于初始可行流,它是運(yùn)輸量為0的最小費(fèi)用流。4. 在增廣鏈上對(duì)進(jìn)行調(diào)整,調(diào)整量為: , ()令 . ()得到新的可行流, 使流值增大,令,返回到第(2).圖12 模型求解過程桃曲坡水庫(kù)、玉皇閣水庫(kù)和高爾塬水庫(kù)都位于渭河的支流上,每逢汛期,都會(huì)有大量的防汛物資從附近的倉(cāng)庫(kù)運(yùn)送到這3座水庫(kù),:桃曲坡,230。每條弧上的標(biāo)注為,代表從到點(diǎn)的道路運(yùn)輸能力(即為第倉(cāng)庫(kù)的物資儲(chǔ)備量)。,，結(jié)果見表2(表中物資運(yùn)輸流量表示從各倉(cāng)庫(kù)到各水庫(kù)的防洪物資數(shù)量，單位為).表2 運(yùn)輸計(jì)算結(jié)果計(jì)算結(jié)果為,滿足各水庫(kù)最低物資需求量的運(yùn)輸方案,即只要給定每座水庫(kù)的最低需求量,隨時(shí)改變每座水庫(kù)的最低需求量,改變運(yùn)輸方案. 第四章 總結(jié)最小費(fèi)用最大流理論在網(wǎng)絡(luò)優(yōu)化模型中具有核心位置,因?yàn)樗粌H具有廣泛類型的應(yīng)用,該理論能夠研究具有多個(gè)發(fā)點(diǎn)和多個(gè)終點(diǎn)的問題,使得通過網(wǎng)絡(luò)發(fā)送的
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1