系統(tǒng)優(yōu)化算法課程設(shè)計(jì)論文-最小費(fèi)用最大流算法設(shè)計(jì)與實(shí)現(xiàn)(已修改)
2025-06-23 02:17 本頁面
【正文】 課程設(shè)計(jì) （論文） 課程名稱： 系統(tǒng)優(yōu)化算法設(shè)計(jì)與實(shí)現(xiàn) 題 目 ： 最小費(fèi)用最大流算法設(shè)計(jì)與實(shí)現(xiàn) 院 （系）： 管理學(xué)院 專業(yè)班級： 信管 1302 姓 名： 王程 學(xué) 號 ： 130404026 指導(dǎo) 教 師： 黃光球 2021 年 7 月 18 日 西安建筑科技大學(xué) 課程設(shè)計(jì)（論文）任務(wù)書 專業(yè)班級： 信管 1302 學(xué)生姓名： 王程 指導(dǎo)教師（簽名）： 一、課程設(shè)計(jì)（論文）題目 最小費(fèi)用最大流算法設(shè)計(jì)與實(shí)現(xiàn) 二、本次課程設(shè)計(jì)（論文）應(yīng)達(dá)到的目的 《 系統(tǒng)優(yōu)算法設(shè)計(jì)與實(shí)現(xiàn) 》 課程設(shè)計(jì)是實(shí)踐教學(xué)環(huán)節(jié)的重要組成部分，其目的是通過課程設(shè)計(jì)加深學(xué)生對 系統(tǒng)優(yōu)算法設(shè)計(jì)與實(shí)現(xiàn) 基本知識 掌握和基本編程技能 的 培養(yǎng) ，提高綜合運(yùn)用知識 解決實(shí)際問題 的能力； 本次要求學(xué)生通過掌握 系統(tǒng)優(yōu)算法設(shè)計(jì)與實(shí)現(xiàn)的程序設(shè)計(jì) 方法， 以提高 學(xué)生獨(dú)立分析問題、解決問題的能力，逐步增強(qiáng)實(shí)際工程訓(xùn)練。 三、本次課程設(shè)計(jì)（論文）任務(wù)的主要內(nèi)容和要求 設(shè)計(jì)內(nèi)容： 網(wǎng)絡(luò)最大流問題，只考慮了流的數(shù)量，沒有考慮流的費(fèi)用。實(shí)際上許多問題還要考慮流的最小費(fèi)用問題。 在網(wǎng)絡(luò) G=（ V,E,C）中， 每條邊 （ vi，vj） 除了已給容量 cij外，還給出了單位流量的費(fèi)用 dij （ dij =0），記 G=（ V,E,C，d） 。求 G的一個(gè)可行流 f={fij}， 使得流量 W(f)=v，且總費(fèi)用最小。 ( , )() ij ij ijv v Ed f d f?? ? 特別地，當(dāng)要求 f為最大流時(shí)，此問題即為最小費(fèi)用最大流問題。 最小費(fèi)用最大流問題的常用算法有兩種：（ 1）原始算法；（ 2）對偶算法。本文將使用對偶算法來解決最小費(fèi)用最大流問題 ，即先找一個(gè)流量為 W(f（ 0） ) v的最小費(fèi)用流（可用零流作為初始流），然后尋找從 vs到 vt的可增廣鏈 ? ，用最大流方法將 f（ 0） 調(diào)整到 f（ 1） ,使 f（ 1） 流量為 W(f（ 0） )+θ ，且保證 f（ 1） 是在 W(f（ 0） )+θ 流量下的最小費(fèi)用流，不斷進(jìn)行到 W(f（ 0） )= v為止。 要求 ： 1．提交 正確的和完整的程序設(shè)計(jì)代碼 。 2．提交設(shè)計(jì)說明書。 3. 接受現(xiàn)場檢驗(yàn)。 四、應(yīng)收集的資料及主要參考文獻(xiàn)： 應(yīng)收集的資料：本次設(shè)計(jì)應(yīng)該收集和題目背景的有關(guān)資料。 主要參考文獻(xiàn)： .《 運(yùn)籌學(xué) 》 .清華大學(xué)出版社， 2021 ， 《 C程序設(shè)計(jì)》 ， 清華大學(xué)出版社， 2021 ， 求最小費(fèi)用最大流問題的一種方法 [J]， 中國民航學(xué)院學(xué)報(bào) ,2021 ,譚毓澄 ,余劍敏 ， 制造網(wǎng)絡(luò)的一個(gè)最小費(fèi)用最大流算法 [J]. 江西師范大學(xué)學(xué)報(bào) (自然科學(xué)版 ). 2021 ,董雪 ,呂林劍 ， 交通運(yùn)輸網(wǎng)絡(luò)中兩個(gè)結(jié)點(diǎn)間有流量約束的最小費(fèi)用最大流算法 [J]， 蘭州交通大學(xué)學(xué)報(bào) . 2021 五、 審核批準(zhǔn)意見 教研室主任（簽字） 設(shè)計(jì)總說明 摘要 ： 在現(xiàn)實(shí)生活中，關(guān)于系統(tǒng)網(wǎng)絡(luò)的研究就有不少。許多系統(tǒng)網(wǎng)絡(luò)就包含了流量的問題，如何實(shí)現(xiàn)網(wǎng)絡(luò)最大流往往是我們一直關(guān)注并研究的重點(diǎn)。但在經(jīng)濟(jì)活動中或是涉及 “ 流 ” 的問題時(shí)，我們考慮的還有 “ 費(fèi)用 ” 的因素， “ 最小費(fèi)用最大流問題 ” 就往往被系統(tǒng)管理者和決策者所重視。 最小費(fèi)用最大流是一類網(wǎng)絡(luò)優(yōu)化問題 ,它與最大流的區(qū)別在于 ,它不僅要考慮流量問題 ,還要考慮費(fèi)用因素 ,其優(yōu)化的目標(biāo)是流量最大且費(fèi)用最小。本文綜合求最大流原理和求最短路原理 ,在直接輸入初始狀態(tài)下就求出任何一個(gè)網(wǎng)絡(luò)圖的最小費(fèi)用值 ,最大流值以及其他一些相關(guān)數(shù)據(jù)。該算法程序可以為我們減少大量計(jì)算 ,提高工作效率 ,因此被大量使用研究 。 關(guān)鍵字： 發(fā) 點(diǎn)、匯點(diǎn)、最短路徑、最大流、增廣路徑、 Dijkstra 算法、逐次逼近 法 目 錄 1 緒論 .................................................. 1 內(nèi)容簡介 ................................................1 本次課設(shè)目的 ............................................1 課設(shè)內(nèi)容 ................................................1 2 最小費(fèi)用最大流算法設(shè)計(jì)說明 .............................. 2 程序設(shè)計(jì)過程詳述 ........................................2 編程實(shí)現(xiàn)過程詳述 ........................................2 原代碼 ..................................................4 3 實(shí)驗(yàn)研究小結(jié) .......................................... 17 使用說明詳述 ...........................................17 本部分功能操作注 意事項(xiàng) .............................17 本部分功能與其他系統(tǒng)的關(guān)系 .........................17 測試案例詳述 ..........................................17 參考文獻(xiàn) ................................................ 20 第 1 頁 共 20 頁 1 緒論 內(nèi)容 簡介 本文綜合求最大流原理和求最短路原理 ,在直接輸入初始狀態(tài)下就求出任何一個(gè)網(wǎng)絡(luò)圖的最小費(fèi)用值 ,最大流值以及其 它 一些相關(guān)數(shù)據(jù)。 本次課設(shè) 目的 （ 1）在 G 上，除了已給容量 cij，還給了每一條弧的費(fèi)
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號-1