【數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)】【畢業(yè)論文】運(yùn)輸問題的求解及其應(yīng)用

《【數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)】【畢業(yè)論文】運(yùn)輸問題的求解及其應(yīng)用》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、（20__屆）本科畢業(yè)論文運(yùn)輸問題的求解及其應(yīng)用摘要：本課題主要探討了如何判別一個(gè)運(yùn)輸問題的調(diào)運(yùn)方案是最優(yōu)，對(duì)通常采用的兩種閉回路法或位勢(shì)法做綜述整理，同時(shí)探討更好的一次性算法，既避免了閉回路法中對(duì)所有非基變量檢驗(yàn)數(shù)的一一計(jì)算,又回避了位勢(shì)法中需要多次求解線性方程組以計(jì)算位勢(shì)的過程。本課題主要利用了已有或已得到的算法對(duì)實(shí)際問題進(jìn)行分析研究。關(guān)鍵詞：運(yùn)輸問題；最優(yōu)方案；一次性算法；閉回路法；位勢(shì)法TransportationproblemsolvinganditsapplicationAbstract:Mys

2、ubjectmainlydiscusseshowtodistinguishthetransportationproblemwithoptimalsolutionscheme,thensyntheticallyinducesaboutclosedloopmethodorpotentialsmethodwhichwealwaysuse.Atthesametime,weexploreabettermethodtoone-timelygettheresult.Itnotonlyavoidscalculatingon

3、ebyoneallthebasicvariableinspectionnumberwithclosedloopmethod,butalsoavoidstheprocessofsolvingthelinearequationsmanytimestocalculatpotentialswithpotentialsmethod.Inshort,thegoalofmytopicisanalyzingandstudyingpracticalproblemswithexsitedorachievedmethods.Ke

4、ywords:Transportationproblem;Theoptimalsolution;One-timealgorithm;Closedloopmethod;Potentialsmethod目錄1運(yùn)輸問題簡(jiǎn)介12運(yùn)輸問題模型23幾種常用檢驗(yàn)法的缺陷33.1閉回路法的缺陷43.2位勢(shì)法的缺陷83.3改進(jìn)的閉回路法的缺陷113.4動(dòng)態(tài)規(guī)劃法的缺陷124一種新的檢驗(yàn)方法125應(yīng)用舉例136運(yùn)輸問題在消防中的應(yīng)用157結(jié)束語(yǔ)17致謝18參考文獻(xiàn)191運(yùn)輸問題簡(jiǎn)介運(yùn)輸問題是一類具有特殊結(jié)構(gòu)的線性規(guī)劃問題。由于

5、運(yùn)輸問題約束方程組的系數(shù)矩陣是完全么模的，即所有的子行列式為0或±1，存在著比單純形法更簡(jiǎn)單的特殊解法。對(duì)于規(guī)模不太大的運(yùn)輸問題可用圖上作業(yè)法或表上作業(yè)法求解。這類問題的典型提法是，為了把某種產(chǎn)品從若干個(gè)產(chǎn)地調(diào)運(yùn)到若干個(gè)銷地，已知每個(gè)產(chǎn)地的供應(yīng)量和每個(gè)銷地的需求量，如何在許多可行的調(diào)運(yùn)方案中，確定一個(gè)總運(yùn)輸費(fèi)或總運(yùn)輸量最少的方案。具有上述特點(diǎn)的線性規(guī)劃問題通常被稱為運(yùn)輸型問題?，F(xiàn)已發(fā)現(xiàn)的運(yùn)輸型問題有以下6類:①一般運(yùn)輸問題,又稱希契科克運(yùn)輸問題，簡(jiǎn)稱H問題。②網(wǎng)絡(luò)運(yùn)輸問題，又稱圖上運(yùn)輸問題,簡(jiǎn)稱T問題。③最

6、大流量問題,簡(jiǎn)稱F問題。④最短路徑問題,簡(jiǎn)稱S問題。⑤任務(wù)分配問題，又稱指派問題,簡(jiǎn)稱A問題。⑥生產(chǎn)計(jì)劃問題，又稱日程計(jì)劃問題,簡(jiǎn)稱CPS問題。其中一般運(yùn)輸問題、任務(wù)分配問題和生產(chǎn)計(jì)劃問題通常都可以用表上作業(yè)法求解，而網(wǎng)絡(luò)運(yùn)輸問題、最大流量問題和最短路徑問題一般可用圖上作業(yè)法或網(wǎng)絡(luò)技術(shù)求解（參見文獻(xiàn)[1]）。當(dāng)使用表上作業(yè)法求解運(yùn)輸問題時(shí)。初始基本可行解的求法有三種：①左上角法。它的基本思想是給運(yùn)輸表中左上角的變量分配運(yùn)輸量以確定產(chǎn)銷關(guān)系。②最小元素法，或最小成本法。它的基本思想是就近供應(yīng)，即從運(yùn)輸表中運(yùn)價(jià)

7、最小的格子開始分配運(yùn)輸量以確定產(chǎn)銷關(guān)系。③元素差額法,又稱沃格爾近似法，簡(jiǎn)稱VAM法。它是從運(yùn)輸表中各行和各列的最小元素和次小元素的差額來確定產(chǎn)銷關(guān)系。改進(jìn)初始基本可行解的方法有兩種：①閉回路法。這種方法需要對(duì)每一個(gè)空格尋找一條閉回路，并根據(jù)閉回路求出每個(gè)空格的檢驗(yàn)數(shù)。當(dāng)運(yùn)輸問題中m和n較大時(shí)，計(jì)算檢驗(yàn)數(shù)的工作量很大。②位勢(shì)法，或乘數(shù)法。先對(duì)初始調(diào)運(yùn)方案求出位勢(shì)，然后求各空格的檢驗(yàn)數(shù)。當(dāng)所有的檢驗(yàn)數(shù)均為非負(fù)時(shí)，就得到最優(yōu)方案。如果出現(xiàn)負(fù)的檢驗(yàn)數(shù)，則從檢驗(yàn)數(shù)為負(fù)的空格出發(fā)，作閉回路，重新計(jì)算檢驗(yàn)數(shù)，作進(jìn)一步調(diào)

8、整。用位勢(shì)法求檢驗(yàn)數(shù)就是對(duì)偶問題的表上作業(yè)法（參見文獻(xiàn)[2]）。但是我們發(fā)現(xiàn)對(duì)于實(shí)際的運(yùn)輸問題，上述優(yōu)化方法很難將運(yùn)輸過程中所發(fā)生的費(fèi)用都考慮進(jìn)去，因此，如果教條地采用上述優(yōu)化方法直接進(jìn)行優(yōu)化，則很難保證此方案是真正的最佳方案。實(shí)際的運(yùn)輸問題中上述方法沒考慮到的因素有：（1）對(duì)運(yùn)輸問題中的中轉(zhuǎn)再分撥，其中轉(zhuǎn)的裝卸搬運(yùn)費(fèi)用，無論是求最小費(fèi)用最大流的優(yōu)化方法還是表上作業(yè)法求具有中轉(zhuǎn)站的運(yùn)輸問題最佳方案時(shí)，都沒有考慮此