運(yùn)輸問題相關(guān)研究與應(yīng)用【文獻(xiàn)綜述】

《運(yùn)輸問題相關(guān)研究與應(yīng)用【文獻(xiàn)綜述】》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、畢業(yè)論文文獻(xiàn)綜述［學(xué)與應(yīng)用數(shù)學(xué)運(yùn)輸問題相關(guān)研究與應(yīng)用運(yùn)輸問題是社會經(jīng)濟(jì)生活和軍事活動中經(jīng)常出現(xiàn)的優(yōu)化問題。在經(jīng)濟(jì)建設(shè)和國防建設(shè)中，經(jīng)常遇到煤、鋼鐵、木材、糧食、武器裝備等物資的調(diào)運(yùn)問題。如何制定調(diào)運(yùn)方案，將物資運(yùn)往指定地點(diǎn)，而且實(shí)現(xiàn)運(yùn)輸成本最小，即為運(yùn)輸問題。運(yùn)輸問題是特殊的線性規(guī)劃問題，它是早期的線性網(wǎng)絡(luò)最優(yōu)化的一個(gè)例子。與一般線性規(guī)劃問題不同，它的約束方程組的系數(shù)矩陣具有特殊的結(jié)構(gòu)，這就需要采用不同的甚至更為簡便的求解方法來解決這種在實(shí)際工作中經(jīng)常遇到的問題。運(yùn)輸問題不僅代表了物資合理調(diào)運(yùn)、車輛合理調(diào)度

2、等問題，有些其他類型的問題經(jīng)過適當(dāng)變換后也可以歸結(jié)為運(yùn)輸問題。從算法角度考慮，目前對于運(yùn)輸問題的求解提出了很多可行的解法，如表上作業(yè)法、圖上求解法以及應(yīng)用計(jì)算機(jī)實(shí)現(xiàn)的啟發(fā)式多種算法等。表上作業(yè)法是解決一般運(yùn)輸問題最常用的解法，因其求解工作均在運(yùn)輸表上進(jìn)行而得名。它是一種迭代算法，迭代步驟為：先按某種規(guī)則找岀一個(gè)初始解；再對現(xiàn)行解作最優(yōu)性判別；若該解不是最優(yōu)解，就在運(yùn)輸表上対它進(jìn)行調(diào)整改進(jìn)，從而得出一個(gè)新解，再重復(fù)判別改進(jìn)的過程，直至得到運(yùn)輸問題的最優(yōu)解為止。表上作業(yè)法一方面是在求解過程中首先要找出初始基可行

3、解，需要一定計(jì)算工作量，即需要經(jīng)過(m+n-1)次加減運(yùn)算給出初始方案。另一方面是在初始基可行解基礎(chǔ)上，還要用繁瑣的閉回路法或位勢法計(jì)算所有空格(非基變量)的檢驗(yàn)數(shù)，再判別是否達(dá)到最優(yōu)解。如果沒有得出最優(yōu)解，還需要在表上用閉回路法進(jìn)行調(diào)整，確定換入變量和換出變量，找出新的基可行解，再進(jìn)行檢驗(yàn)等步驟，直到求出最優(yōu)解為止。由于當(dāng)產(chǎn)地m、銷地n較大時(shí)表上作業(yè)法的操作顯得尤為繁瑣。文獻(xiàn)［1］提出了運(yùn)輸問題的一種新解法，該方法通過構(gòu)造賦權(quán)二部圖，應(yīng)用圖論的相關(guān)理論，給出求解運(yùn)輸問題的另一種圖上解法。其一般步驟為：第一

4、步把運(yùn)輸問題轉(zhuǎn)化為賦權(quán)完全二部圖Go第二步用最小權(quán)元素法，求初始基可行解，即求G的一個(gè)生成樹T(x)0第三步取T(x)的權(quán)最大邊e,若兩個(gè)以上取英中之一。第四步T(x)-e為兩棵樹TI和T2,若TI的產(chǎn)地與T2的銷地Z間無權(quán)小于e的邊可添加，轉(zhuǎn)第六步。否則，添加權(quán)小于叫w(e)的邊構(gòu)成一個(gè)閉回路，驗(yàn)證總運(yùn)費(fèi)是否減少?若總運(yùn)費(fèi)不減少，轉(zhuǎn)第六步，否則，用圖上閉回路調(diào)節(jié)法，得到新的生成樹T(xl),且其總運(yùn)費(fèi)少于T(x)的總運(yùn)費(fèi)。第五步収T(xl)中的權(quán)最大邊，仍記為e,轉(zhuǎn)第四步。第六步除e外取T（x）中的權(quán)最大

5、邊,仍記為e,轉(zhuǎn)第四步。一直到取遍T（x）中的每一邊e,去掉e后的兩棵樹T1與T2的產(chǎn)地與銷地Z間無權(quán)小于e的邊可添加，或者有權(quán)小于e的邊可添加，添加后總運(yùn)費(fèi)不減少，則得到最優(yōu)樹。圖上求解法與表上作業(yè)法相比，用圖上求解法判別最優(yōu)解時(shí)，需要驗(yàn)證（m+n?l）基變量邊是否可以用非基變量對應(yīng)邊代替（英中m、n分別是產(chǎn)地和銷地的數(shù)量）。當(dāng)m、n較大吋,mn-（m+n-l）遠(yuǎn)遠(yuǎn)大于（m+n?l）,因此當(dāng)m、n較大時(shí)，理論上用圖上求解法較方便。但同時(shí)當(dāng)m、n很大時(shí)，圖上邊、權(quán)及邊線太多，易混淆，不利于實(shí)際操作。而文獻(xiàn)」

6、21］給出了求解運(yùn)輸問題的一種網(wǎng)絡(luò)算法,運(yùn)用網(wǎng)絡(luò)圖求解運(yùn)輸問題，可以更直觀、快速、形彖地得到初始解，并且該初始解更接近最優(yōu)解或己經(jīng)是最優(yōu)解，可以大大減少計(jì)算工作量。但當(dāng)產(chǎn)銷地?cái)?shù)量較多時(shí)，網(wǎng)絡(luò)圖繪制可能相對麻煩些。此外文獻(xiàn)［2］、［3］、［4］、［5］、［6］等還提出利用某些數(shù)學(xué)軟件編程求解運(yùn)輸問題的方法，比較表上作業(yè)法計(jì)算繁瑣，方案調(diào)整的工作量大，容易出錯(cuò)的缺陷，文獻(xiàn)［2］提出的LINGO軟件語法簡潔,具有良好的可讀性,準(zhǔn)確性高，易于被用戶掌握。而文獻(xiàn)［3］提岀用線性規(guī)劃的方法來解決運(yùn)輸問題，但由于此類問題

7、所涉及的條件變量較多，一般的數(shù)學(xué)方法運(yùn)算難度較大，結(jié)果不容易求出，所以作者利用Matlab軟件構(gòu)建函數(shù)用來解決線性規(guī)劃問題。隨后文獻(xiàn)［4］直接用這種方法來解決實(shí)際中的物流運(yùn)輸問題。文獻(xiàn)［5］對運(yùn)輸問題的一般提法和模型給出了數(shù)值算法，概念清楚，步驟明確，易于編程實(shí)現(xiàn)，且有很好地收斂性。而文獻(xiàn)［6］對用最小元素法求初始基本可行解的過程進(jìn)行編程調(diào)解，減少了工作量，具有較強(qiáng)的通用性。文獻(xiàn)［7］提出了又提出了求解運(yùn)輸問題的一種新算法，以平衡運(yùn)輸問題為例，其求解的算法基本步驟為：第一步：對平衡運(yùn)輸問題的運(yùn)價(jià)矩陣進(jìn)行變換

8、，使得在各行各列中都出現(xiàn)0元素。⑴從運(yùn)價(jià)矩陣的每行例）元素減去該行（列）的最小元素；⑵再從所得運(yùn)價(jià)矩陣的每列（行）減去該列（行）的最小元素。第二步：計(jì)算各行（產(chǎn)地）和各列（銷地）的分配數(shù)。行的分配數(shù)就是該行中為0的那些元素所對應(yīng)的銷量之和；列的分配數(shù)就是該列屮為0的那個(gè)元素所對應(yīng)的產(chǎn)量之和；第三步：比較分配數(shù)與產(chǎn)量（銷量），對于分配數(shù)小于產(chǎn)量（銷量）的行（41）減去該行（列）的最小正數(shù)。并消去由此而產(chǎn)生的列（行）