本文選題：最小費(fèi)用最大雙流　切入點(diǎn)：余網(wǎng)絡(luò)　出處：《南京郵電大學(xué)》2017年碩士論文　論文類型：學(xué)位論文

【摘要】：最小費(fèi)用最大雙流問題具有很大的研究意義,許多網(wǎng)絡(luò)優(yōu)化問題都可歸為它的特例,如最短路問題、最大流問題、最小費(fèi)用最大流問題等。隨著物流運(yùn)輸?shù)陌l(fā)展,對于以上問題的研究已經(jīng)滿足不了運(yùn)輸行業(yè)不斷發(fā)展的需要,需要迫切的對雙費(fèi)用流問題進(jìn)行深入研究,研究最小費(fèi)用最大雙流不僅具有理論價(jià)值,而且也具有很大的實(shí)用價(jià)值。本文對于傳統(tǒng)的最小費(fèi)用最大雙流算法進(jìn)行改進(jìn),主要成果如下:1.通過對比剩余網(wǎng)絡(luò)和余網(wǎng)絡(luò)的區(qū)別,提出了一種基于剩余網(wǎng)絡(luò)的最小費(fèi)用最大雙流算法,該算法避免了在構(gòu)建剩余網(wǎng)絡(luò)時(shí),增廣路徑中有逆流存在引起的混淆。對改進(jìn)的算法進(jìn)行推理證明得出算法的正確性,仿真實(shí)驗(yàn)的結(jié)果證明算法能得到網(wǎng)絡(luò)的最大雙流。2.提出了一種定流值比例的最小雙費(fèi)用流的新算法,在求得的最大雙流和最小費(fèi)用的基礎(chǔ)上,調(diào)整雙流值,在求得定流值比例的同時(shí)使其總費(fèi)用最小。邏輯推理和仿真實(shí)驗(yàn)結(jié)果均表明,所提出的算法可行、有效,能較好地解決稀疏網(wǎng)絡(luò)以及復(fù)雜網(wǎng)絡(luò)中定流值比例的最小雙費(fèi)用流問題。3.發(fā)現(xiàn)了一種最小費(fèi)用流的新算法,新算法首先利用改進(jìn)的Dijkstra算法搜索出從源點(diǎn)至匯點(diǎn)的所有費(fèi)用路徑,并且在余網(wǎng)絡(luò)中增廣流值,由于余網(wǎng)絡(luò)比剩余網(wǎng)絡(luò)構(gòu)造簡單,所以最終提高了算法的時(shí)間效率。仿真實(shí)驗(yàn)結(jié)果表明新算法較復(fù)雜網(wǎng)絡(luò)更適用于稀疏網(wǎng)絡(luò)。4.一種最小費(fèi)用流的新算法應(yīng)用于容量-費(fèi)用雙流網(wǎng)絡(luò)中,從而得到一種求解最小雙費(fèi)用流的新算法,并通過實(shí)例驗(yàn)證算法是有效的。
[Abstract]:The minimum cost maximum double flow problem is of great significance, and many network optimization problems can be classified as its special cases, such as the shortest path problem, the maximum flow problem, the minimum cost maximum flow problem and so on. The research on the above problems can not meet the needs of the continuous development of the transportation industry. It is urgent to study the double cost flow problem. The research on the minimum cost maximum double flow is not only of theoretical value. It is also of great practical value. This paper improves the traditional two-stream algorithm with minimum cost and maximum cost. The main results are as follows: 1. By comparing the difference between residual network and residual network, In this paper, a two-flow algorithm with minimum cost and maximum cost based on residual network is proposed. The algorithm avoids the confusion caused by the countercurrent in the augmented path when the residual network is constructed. The reasoning of the improved algorithm proves the correctness of the algorithm. The simulation results show that the algorithm can get the maximum double flow of the network. 2. A new algorithm of minimum double cost flow with constant flow value ratio is proposed, which adjusts the double flow value on the basis of the obtained maximum double flow and minimum cost. At the same time, the proportion of constant flow value is obtained and the total cost is minimized. The results of logical reasoning and simulation experiments show that the proposed algorithm is feasible and effective. A new algorithm of minimum cost flow is found. The improved Dijkstra algorithm is used to search all the cost paths from the source point to the meeting point. And the value of current is increased in the redundant network, because the redundant network is easier to construct than the residual network. The simulation results show that the new algorithm is more suitable for sparse networks than complex networks. A new algorithm with minimum cost flows is applied to capacity-cost two-stream networks. A new algorithm for solving the minimum double cost flow is obtained, and an example is given to verify the effectiveness of the algorithm.
【學(xué)位授予單位】：南京郵電大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 王錫萍;最小費(fèi)用流在水電站中的應(yīng)用[J];甘肅科技;1998年05期

2 李紀(jì)宏;劉雪華;;基于最小費(fèi)用距離模型的自然保護(hù)區(qū)功能分區(qū)[J];自然資源學(xué)報(bào);2006年02期

3 趙建英;;基于復(fù)雜最小費(fèi)用流的影片運(yùn)輸問題[J];內(nèi)蒙古財(cái)經(jīng)學(xué)院學(xué)報(bào)(綜合版);2006年04期

4 楊成林;周科平;高文翔;楊念哥;;改進(jìn)的最小費(fèi)用理論在盲豎井選址中的應(yīng)用[J];數(shù)學(xué)的實(shí)踐與認(rèn)識;2008年01期

5 方冬云;;電壓傳輸中的兩種最小費(fèi)用算法分析[J];曲阜師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年01期

6 高明霞;賀國光;;一類點(diǎn)權(quán)網(wǎng)絡(luò)的最小費(fèi)用流問題[J];武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版);2012年03期

7 林景榮;最小費(fèi)用流在商業(yè)網(wǎng)點(diǎn)布局上的應(yīng)用[J];海南大學(xué)學(xué)報(bào)(自然科學(xué)版);1996年01期

8 顏鐵成;關(guān)于多收點(diǎn)容量網(wǎng)絡(luò)最小費(fèi)用流的一個(gè)問題[J];鐵道師院學(xué)報(bào);1998年04期

9 謝政,劉衛(wèi)華,湯澤瀅;最小費(fèi)用樹[J];國防科技大學(xué)學(xué)報(bào);1999年05期

10 劉磊;劉三陽;孫小軍;;最小費(fèi)用路算法的改進(jìn)及其應(yīng)用[J];西安文理學(xué)院學(xué)報(bào)(自然科學(xué)版);2007年01期

相關(guān)會議論文 前3條

1 馮雷;孟祥萍;;電站最小費(fèi)用MATLAB優(yōu)化仿真[A];'2006系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)交流會論文集[C];2006年

2 馬建華;;單行道設(shè)置問題的優(yōu)化模型[A];第二十七屆中國控制會議論文集[C];2008年

3 俞洋;田亞菲;;一種新的變步長LMS算法及其仿真[A];通信理論與信號處理新進(jìn)展——2005年通信理論與信號處理年會論文集[C];2005年

相關(guān)博士學(xué)位論文 前10條

1 魯海燕;最小費(fèi)用網(wǎng)絡(luò)流的若干新問題研究[D];浙江大學(xué);2007年

2 魏哲學(xué);樣本斷點(diǎn)距離問題的算法與復(fù)雜性研究[D];山東大學(xué);2015年

3 劉春明;基于增強(qiáng)學(xué)習(xí)和車輛動(dòng)力學(xué)的高速公路自主駕駛研究[D];國防科學(xué)技術(shù)大學(xué);2014年

4 張敏霞;生物地理學(xué)優(yōu)化算法及其在應(yīng)急交通規(guī)劃中的應(yīng)用研究[D];浙江工業(yè)大學(xué);2015年

5 李紅;流程挖掘算法研究[D];云南大學(xué);2015年

6 卜晨陽;演化約束優(yōu)化及演化動(dòng)態(tài)優(yōu)化求解算法研究[D];中國科學(xué)技術(shù)大學(xué);2017年

7 陳拉明;基于非凸優(yōu)化的稀疏重建理論與算法[D];清華大學(xué);2016年

8 劉新旺;多核學(xué)習(xí)算法研究[D];國防科學(xué)技術(shù)大學(xué);2013年

9 于濱;城市公交系統(tǒng)模型與算法研究[D];大連理工大學(xué);2006年

10 曾國強(qiáng);改進(jìn)的極值優(yōu)化算法及其在組合優(yōu)化問題中的應(yīng)用研究[D];浙江大學(xué);2011年

相關(guān)碩士學(xué)位論文 前10條

1 劉英;生產(chǎn)網(wǎng)絡(luò)最小費(fèi)用流問題的研究[D];西安電子科技大學(xué);2010年

2 胡勇文;用對偶原理求解最小費(fèi)用流的允許邊算法[D];河南理工大學(xué);2011年

3 陳秋茹;不確定網(wǎng)絡(luò)多倉庫多品種有路徑限制的最小費(fèi)用流算法[D];湘潭大學(xué);2017年

4 王欣欣;求解帶時(shí)間窗口的多式聯(lián)運(yùn)最小費(fèi)用問題[D];北京郵電大學(xué);2009年

5 白睿;最大流及最小費(fèi)用的算法研究[D];南京郵電大學(xué);2012年

6 葛浩;動(dòng)態(tài)最小費(fèi)用路在L_1模下的逆問題研究[D];浙江大學(xué);2006年

7 黃廈;基于改進(jìn)蟻群算法的柔性作業(yè)車間調(diào)度問題研究[D];昆明理工大學(xué);2015年

8 李平;基于Hadoop的信息爬取與輿情檢測算法研究[D];昆明理工大學(xué);2015年

9 趙官寶;基于位表的關(guān)聯(lián)規(guī)則挖掘算法研究[D];昆明理工大學(xué);2015年

10 殷文華;移動(dòng)容遲網(wǎng)絡(luò)中基于社會感知的多播分發(fā)算法研究[D];內(nèi)蒙古大學(xué);2015年

，

本文編號：1638238