運用圖論理論優(yōu)化運輸方案_畢業(yè)論文-資料下載頁
2025-08-16 19:32本頁面
【導讀】來越廣泛的應(yīng)用.是圖論的應(yīng)用問題的研究之一,對現(xiàn)實生活中的運輸問題具有很好的指導意義.本文運用圖論理論對車輛流問題抽象和形式化,在線路連接有向圖的基礎(chǔ)上,建立數(shù)學模型,并運用最大流和最小割基本理論對具體問題進行求解.在文章中首先引入流、割等概念與網(wǎng)絡(luò)圖知識點的基本定義??
【正文】 t 。高爾塬 ,190t 。玉皇閣 ,110t .這附近有 7 個倉庫，每個倉庫的物資儲備量和從某座倉庫運輸物資到某座水庫的單位運輸費用見表 1. 將表 1 中的信息網(wǎng)絡(luò)化 ,將得到圖 13,① ,② ,? ⑦ 分別代表倉庫 :馬欄、廟灣、瑤曲、柳林、石門關(guān)、青草坪 、石柱 。⑧ ,⑨ ,⑩ 分別代表水庫桃曲坡、玉皇閣和高爾塬 。每條弧上的標注為 ),( ijij tc , ijc 代表從 i 到 j 點的道路運輸能力 (即為第 i 倉庫的物資儲備量 )。ijt 為從 i 到 j 點的單位物資運輸費用 . 16 表 1 單位物資運費 圖 13 運輸網(wǎng)絡(luò)示意圖 建立物資運輸模型 : ?????????????????? ?? ?)3,2,1,72,1(3 . 2 . 3 )(,)3,2,1()72,1(..m i n,7131,jicfjqfipftsftZjijiiji ,jjii ,ji jjiji?? 17 式中 Z 為 總 運 輸 費用 。 ijf 代 表 道 路運 輸 流量 . )72,1( ??ipi 的值分別為 :90,80,110,105,95,115,95。 1q , 2q , 3q 的值分別為 :230,190,110。 ijc ,ijt 的值見圖13 中的線上的標注 .對模型根據(jù)最小費用最大流 的求解步驟進行求解，結(jié)果見表2(表中物資運輸流量表示從各倉庫到各水庫的防洪物資數(shù)量，單位為 t ). 表 2 運輸計算結(jié)果 計算結(jié)果為 ,滿足各水庫最低物資需求量的運輸方案 ,總運輸費用為 54650 元 .最小費用最大流理論可以求解出任意的對應(yīng)于某個最低運輸量的運輸方案 ,即只要給定每座水庫的最低需求量 ,就可以根據(jù)最小費用最大流理論求解出在這個最低運輸量限制下的運輸方案 .實際中可以根據(jù)汛情的變化 ,隨時改變每座水庫的最低需求量 ,改變運輸方案 . 18 第四章 總結(jié) 最小費用最大流理論在網(wǎng)絡(luò)優(yōu)化模型中具有核心位置 ,因為它不僅具有廣泛類型的應(yīng)用 ,而且可以被極為有效的求解 .與最大流理論相似 ,它關(guān)注的是通過有弧容量限制的網(wǎng)絡(luò)的流量問題 .與最短路徑理論 ? ?21 相似 ,它關(guān)注的是經(jīng)過一條弧的流量的費用 .事實上 ,該理論能夠研究具有多個發(fā)點和多個終點的問題 ,還考慮費用問題 .目的就是在滿足給定需求的前提下 ,使得通過網(wǎng)絡(luò)發(fā)送的有效供給的總成本最小 ,從而獲得最大利益 . 本文 運用圖論 理論這一數(shù)學工具把實際問題抽象為有向網(wǎng)絡(luò) ,進而建立數(shù)學模型 ,并運用最大流和最小割基本理論對具體問題進行求解 .在文中引入了流、割等概念與網(wǎng)絡(luò)圖知識點的基本定義 ,對最大流與最小割基本理論和基本思想進行了概述 ,并著重介紹了最小費用最大流的理論思想 ,包括它的計算方法和算法步驟 .然后把最小費用最大流理論應(yīng)用到實際應(yīng)用問題中 ,解決出土石料運輸問題和防洪物資運輸問題 ,求解給出合理的運輸方案 . 應(yīng)用圖論理論優(yōu)化運輸方案這種方法理論上嚴密、解題步驟直觀清晰、適用性強 ,該方法同時能夠求關(guān)鍵路段 ,取得最小費用最大運輸流量 ,達到整 體最優(yōu)化 .對公路、水路、鐵路等 其他 運輸系統(tǒng)有普遍意義 .本文考慮的是 圖論理論在運輸問題上的 簡單的應(yīng)用 .而實際上 ,也可以 應(yīng)用運籌學中的圖論理論原理解決和優(yōu)化在生活中的其他方面問題 ,如通信編解碼 ,矩陣運算 ,任務(wù)分配 ,GPS 路徑規(guī)劃 ??1 等等 ,這有待于日后 對圖論理論 的繼續(xù)研究 . 19 參考文獻 [1] 朱金壽 ,朱琪 ,王靜 .最小費用最大流算法在路徑規(guī)劃中的應(yīng)用 [J].湖北 :武漢理工大學學報 ,2020,(3). [2] 林詒勛 .線性規(guī) 劃與網(wǎng)絡(luò)流 [M].開封 :河南大學出版社 ,2020. [3] 錢頌迪 .運籌學 [M].北京 :清華大學出版社 ,1993. [4] 盧向南 ,李俊杰 ,壽涌毅 .應(yīng)用運籌學 [M].浙江 :浙江大學出版社 ,2020. [5] 艾素梅 ,魏文宏 ,劉力 .數(shù)學模型的圖論方法 [M].河北 :滄州師范?？茖W校學報 ,2020,(4). [6] 杜端甫 .運籌圖論 [M].北京 :北京航空航天大學出版社 ,:60148. [7] .圖論 [M].上海 :上海科學技術(shù)出版社 ,1987. [8] 郭太平 ,田雁新 .用最大流 — 最小截原理 進行工期 — 費用優(yōu)化的分析 [J].湖南 :湖南城市學院學報 ,2020,(1). [9] 楊菊花 ,蓋宇仙 .用最小費用最大流理論確定鐵路貨物運價問題的研究 [J].蘭州交通大學學報 (自然科學版 ),2020,(1). [10] 孫宏杜 ,文徐杰 .最小費用最大流模型在航班銜接問題中的應(yīng)用 [J].南京航空航天大學學報 ,2020,(10). [11] 謝凡榮 .運輸網(wǎng)絡(luò)中求最小費用最大流的一個算法 [J].安徽 :運籌與管理 ,2020,(4). [12] 李明捷 ,石榮 ,蔣鳳偉 .圖論最大流理論在機場登機口分配中的應(yīng)用 [J].天津 :中國 民航大學學報 .2020,(5). [13] 王偉 ,嚴余松 .鐵路局請求車審批優(yōu)化 [J].江蘇 :西南交通大學學報 .2020,(5). 20 致 謝 光陰荏苒 ,轉(zhuǎn)眼四年的大學生活即將結(jié)束 .在 **學院的時光即將成為美好的回憶 ,這段經(jīng)歷使我終身受益 ,終身難忘 .謹以此文向所有關(guān)心和支持我的人致以最誠摯的敬意 ！ 在我論文的完成過程中 ,要感謝我的導師 **老師 .老師花費了大量的心血對我指導 ,她思想的活躍、思想的深度以及對問題敏銳的洞察使我受益匪淺 ,她對數(shù)學研究的嚴謹態(tài)度深深的影響了我 ,她對我一如既往的支持使我不斷在完 成論文的道路上前進 .本論文的主要思想正是來源于她的啟發(fā)和鼓勵 ,感謝 **老師對我論文的多次審閱并提出寶貴建議 . 還要感謝所有老師們 ,這四年來在學習上和生活上給予的悉心指導和熱心幫助 ,在許多問題上給我及時的指導和啟迪 ,指引我克服了很多生活和學習中遇到的困難 .四年來 ,老師們淵博的專業(yè)知識 ,嚴謹?shù)闹螌W態(tài)度 ,謙遜的為人和孜孜不倦的探索精神給我留下了深深的印象 ,并深深的影響了我 .這些必將惠及我將來的學習、工作和生活 ,同時感謝四年里同學們給我的幫助 .
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1