【數(shù)學(xué)與應(yīng)用數(shù)學(xué)專(zhuān)業(yè)】【畢業(yè)論文+文獻(xiàn)綜述+開(kāi)題報(bào)告】運(yùn)輸問(wèn)題的求解及其應(yīng)用

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

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

2、etransportationproblemwithoptimalsolutionscheme,thensyntheticallyinducesaboutclosedloopmethodorpotentialsmethodwhichwealwaysuse.Atthesametime,weexploreabettermethodtoone-timelygettheresult.Itnotonlyavoidscalculatingonebyoneallthebasicvariableinspectionnumberwithclosedloopmethod,butalsoavoidsthe

3、processofsolvingthelinearequationsmanytimestocalculatpotentialswithpotentialsmethod.Inshort,thegoalofmytopicisanalyzingandstudyingpracticalproblemswithexsitedorachievedmethods.Keywords:Transportationproblem;Theoptimalsolution;One-timealgorithm;Closedloopmethod;Potentialsmethod目錄1運(yùn)輸問(wèn)題簡(jiǎn)介12運(yùn)輸問(wèn)題模型2

4、3幾種常用檢驗(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)輸問(wèn)題在消防中的應(yīng)用157結(jié)束語(yǔ)17致謝18參考文獻(xiàn)191運(yùn)輸問(wèn)題簡(jiǎn)介運(yùn)輸問(wèn)題是一類(lèi)具有特殊結(jié)構(gòu)的線(xiàn)性規(guī)劃問(wèn)題。由于運(yùn)輸問(wèn)題約束方程組的系數(shù)矩陣是完全么模的，即所有的子行列式為0或±1，存在著比單純形法更簡(jiǎn)單的特殊解法。對(duì)于規(guī)模不太大的運(yùn)輸問(wèn)題可用圖上作業(yè)法或表上作業(yè)法求解。這類(lèi)問(wèn)題的典型提法是，為了把某種產(chǎn)品從若干個(gè)產(chǎn)地調(diào)運(yùn)到若干個(gè)銷(xiāo)地，已知每個(gè)產(chǎn)地的供應(yīng)量和每個(gè)銷(xiāo)地的需求量，如何在許多可行的調(diào)運(yùn)方案中，確定一個(gè)總運(yùn)輸費(fèi)或

5、總運(yùn)輸量最少的方案。具有上述特點(diǎn)的線(xiàn)性規(guī)劃問(wèn)題通常被稱(chēng)為運(yùn)輸型問(wèn)題?，F(xiàn)已發(fā)現(xiàn)的運(yùn)輸型問(wèn)題有以下6類(lèi):①一般運(yùn)輸問(wèn)題,又稱(chēng)希契科克運(yùn)輸問(wèn)題，簡(jiǎn)稱(chēng)H問(wèn)題。②網(wǎng)絡(luò)運(yùn)輸問(wèn)題，又稱(chēng)圖上運(yùn)輸問(wèn)題,簡(jiǎn)稱(chēng)T問(wèn)題。③最大流量問(wèn)題,簡(jiǎn)稱(chēng)F問(wèn)題。④最短路徑問(wèn)題,簡(jiǎn)稱(chēng)S問(wèn)題。⑤任務(wù)分配問(wèn)題，又稱(chēng)指派問(wèn)題,簡(jiǎn)稱(chēng)A問(wèn)題。⑥生產(chǎn)計(jì)劃問(wèn)題，又稱(chēng)日程計(jì)劃問(wèn)題,簡(jiǎn)稱(chēng)CPS問(wèn)題。其中一般運(yùn)輸問(wèn)題、任務(wù)分配問(wèn)題和生產(chǎn)計(jì)劃問(wèn)題通常都可以用表上作業(yè)法求解，而網(wǎng)絡(luò)運(yùn)輸問(wèn)題、最大流量問(wèn)題和最短路徑問(wèn)題一般可用圖上作業(yè)法或網(wǎng)絡(luò)技術(shù)求解（參見(jiàn)文獻(xiàn)[1]）。當(dāng)使用表上作業(yè)法求解運(yùn)輸問(wèn)題時(shí)。初始基本可行解的求法有三種：①左上角法。它的基本

6、思想是給運(yùn)輸表中左上角的變量分配運(yùn)輸量以確定產(chǎn)銷(xiāo)關(guān)系。②最小元素法，或最小成本法。它的基本思想是就近供應(yīng)，即從運(yùn)輸表中運(yùn)價(jià)最小的格子開(kāi)始分配運(yùn)輸量以確定產(chǎn)銷(xiāo)關(guān)系。③元素差額法,又稱(chēng)沃格爾近似法，簡(jiǎn)稱(chēng)VAM法。它是從運(yùn)輸表中各行和各列的最小元素和次小元素的差額來(lái)確定產(chǎn)銷(xiāo)關(guān)系。改進(jìn)初始基本可行解的方法有兩種：①閉回路法。這種方法需要對(duì)每一個(gè)空格尋找一條閉回路，并根據(jù)閉回路求出每個(gè)空格的檢驗(yàn)數(shù)。當(dāng)運(yùn)輸問(wè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ù)的空

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