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