運(yùn)輸問(wèn)題及其解法【文獻(xiàn)綜述】

《運(yùn)輸問(wèn)題及其解法【文獻(xiàn)綜述】》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、畢業(yè)論文文獻(xiàn)綜述信息與計(jì)算科學(xué)運(yùn)輸問(wèn)題及其解法運(yùn)輸問(wèn)題一直是運(yùn)籌學(xué)以及經(jīng)濟(jì)學(xué)研究的一個(gè)重要問(wèn)題，因?yàn)楝F(xiàn)在的社會(huì)是一個(gè)追求效率的社會(huì)，隨著網(wǎng)絡(luò)的發(fā)展以及網(wǎng)上購(gòu)物的興旺，各大物流公司瘋狂的瓜分這商品運(yùn)輸?shù)氖袌?chǎng)，如何更好的解決運(yùn)輸問(wèn)題在制造更大的生產(chǎn)效率上顯得尤為重要，隨著網(wǎng)絡(luò)因素的加入，對(duì)于運(yùn)輸問(wèn)題的調(diào)度可討論的問(wèn)題就越來(lái)越多，如何在現(xiàn)有的約束條件下進(jìn)一步優(yōu)化目標(biāo)，采用運(yùn)輸問(wèn)題的何種方法才能使得運(yùn)輸?shù)男首罡?，所花的費(fèi)用最少。本文主要就是針對(duì)不同的運(yùn)輸問(wèn)題提供不同的解決方案做出研究，以求能夠?yàn)榇蠖鄶?shù)運(yùn)輸?shù)膯?wèn)題提供最有

2、效的解決方法。一、運(yùn)輸問(wèn)題研究的現(xiàn)狀：運(yùn)輸問(wèn)題是特殊的線性規(guī)劃問(wèn)題,它是早期的線性網(wǎng)絡(luò)最優(yōu)化的一個(gè)例子。最早研究這類問(wèn)題的是美國(guó)學(xué)者希奇柯克(Hitchcock),1941年他在研究生產(chǎn)組織和鐵路運(yùn)輸方面的線性規(guī)劃問(wèn)題時(shí)提出運(yùn)輸問(wèn)題的基本模型;后來(lái)柯普曼(Koopmans)在1947年獨(dú)立地提出運(yùn)輸問(wèn)題并詳細(xì)地對(duì)此問(wèn)題加以討論;從上世紀(jì)40年代早期開始，康脫洛維奇(Kantorovich)圍繞著運(yùn)輸問(wèn)題作了大量的研究，因此運(yùn)輸問(wèn)題又稱為希奇柯克問(wèn)題或康脫洛維奇問(wèn)題?，F(xiàn)在人們對(duì)于運(yùn)輸問(wèn)題有了很多解法，運(yùn)輸問(wèn)題也成了

3、大學(xué)運(yùn)籌學(xué)屮的重要章節(jié)，主要的解法有單純型法，表上作業(yè)法，最短路徑法以及l(fā)ingo軟件實(shí)現(xiàn)的解法等等，但是，隨著時(shí)代的發(fā)展，運(yùn)輸問(wèn)題也有了新的解法，國(guó)外主要以運(yùn)輸問(wèn)題求解算法為研究主體，以表上作業(yè)法、最短路法、最小費(fèi)用最大流以及押能算法等為代表;國(guó)內(nèi)從算法、冃標(biāo)函數(shù)、約束函數(shù)等發(fā)面考慮，但是現(xiàn)在研究運(yùn)輸問(wèn)題的主要是物流行業(yè)，決定運(yùn)輸成本的因素有了很大的改變，比如現(xiàn)在新增加的服務(wù)水平對(duì)運(yùn)輸問(wèn)題的影響等等。同吋也出現(xiàn)了對(duì)運(yùn)輸問(wèn)題的-些新的解法，比如：整數(shù)最小極差運(yùn)輸問(wèn)題及其解法，松約束運(yùn)輸問(wèn)題模型及算法等等。同時(shí)，計(jì)

4、算機(jī)技術(shù)也逐漸的加入了運(yùn)輸問(wèn)題的研究上。二、運(yùn)輸問(wèn)題研究的內(nèi)容：我們可以對(duì)運(yùn)輸問(wèn)題做出余下的定義：所謂運(yùn)輸問(wèn)題，就是指從若干個(gè)產(chǎn)地往若干個(gè)銷地運(yùn)輸某種物資，根據(jù)各產(chǎn)地的產(chǎn)量、各銷地的銷量和現(xiàn)有的交通網(wǎng)絡(luò)，如何安排運(yùn)輸使總運(yùn)費(fèi)最少的問(wèn)題.基于應(yīng)對(duì)突發(fā)事件的需要，HAMMER等提出了如何將貨物盡快運(yùn)抵目的地的運(yùn)輸問(wèn)題，即時(shí)間運(yùn)輸問(wèn)題(也稱瓶頸運(yùn)輸問(wèn)題).近年來(lái)，又有人對(duì)傳統(tǒng)的運(yùn)輸問(wèn)題作了一些有意義的推廣，如有容量限制的運(yùn)輸問(wèn)題、變量有上界的運(yùn)輸問(wèn)題、運(yùn)費(fèi)不完全確定的運(yùn)輸問(wèn)題、在盡快將貨物運(yùn)抵目的地的前提下使總運(yùn)費(fèi)最少

5、的運(yùn)輸問(wèn)題、對(duì)總運(yùn)輸量有限制的運(yùn)輸問(wèn)題、要求貨物盡量在某一給沱時(shí)間以前如數(shù)運(yùn)到的運(yùn)輸問(wèn)題等等。用數(shù)學(xué)語(yǔ)言可表述為假設(shè)某種材料有m個(gè)原材料產(chǎn)地Ai（i二1,2,3..?，m）可以提供，它們的生產(chǎn)能力分別為如1=1,2,3,…,nt有n個(gè)目的地Bj，戶，2,…,n需要這種材料,每個(gè)目的地的需求量分別為bj，cij是從Ai到Bj的運(yùn)輸費(fèi)用。該問(wèn)題是要求出怎樣的運(yùn)輸方案能使總運(yùn)輸費(fèi)用最少？這是運(yùn)輸問(wèn)題的定義，但是運(yùn)輸問(wèn)題屮往往會(huì)有很多特許問(wèn)題，比如供大于求或者需求多余供應(yīng)等等。對(duì)于運(yùn)輸問(wèn)題的研究主要是對(duì)各種運(yùn)輸問(wèn)題提供相

6、應(yīng)算法，在這么多年的研究上表上作業(yè)法己經(jīng)成為許多方法中比較重要的一種方法，同時(shí)，本文還就特殊的幾類運(yùn)輸問(wèn)題給出了解決方案。三、運(yùn)輸問(wèn)題的種類以及其解法：1、單純形法：所謂的單純形法是指：在線性規(guī)劃的基礎(chǔ)上，在滿足運(yùn)輸問(wèn)題的條件下，通過(guò)對(duì)目標(biāo)函數(shù)（在這里就是運(yùn)輸費(fèi)用最小）求解最優(yōu)解的解法，他是借助于高等代數(shù)上的線性方程組的最優(yōu)解的求法在運(yùn)輸問(wèn)題上的應(yīng)用，本文對(duì)該種方法只是做了簡(jiǎn)單的介紹，不是本文的中心。2、表上作業(yè)法：表上作業(yè)法是求解運(yùn)輸問(wèn)題的一種簡(jiǎn)單有效的方法，概括的來(lái)說(shuō)，表上作業(yè)法就是指在給出運(yùn)輸?shù)囊环N滿足條件

7、的初始方案，一般來(lái)講這個(gè)方案不會(huì)是最好的，因此需要給出一個(gè)判別準(zhǔn)則，并對(duì)初始方案進(jìn)行調(diào)整、改進(jìn)，直到求得最優(yōu)方案為止。然而在求解過(guò)程中，有時(shí)會(huì)出現(xiàn)迭代次數(shù)較多，工作量繁瑣的情況。本文試圖對(duì)于一些特定的運(yùn)輸問(wèn)題提供簡(jiǎn)化的表上作業(yè)法的求解。本文還給出了一種多日標(biāo)決策問(wèn)題的表上作業(yè)法的求解以及其他對(duì)表上作業(yè)法的改進(jìn)。3、結(jié)合最短路徑的解法：在傳統(tǒng)的運(yùn)輸問(wèn)題屮，運(yùn)價(jià)是已知數(shù)據(jù)，它所解決的問(wèn)題只是單一地求解將物品由供應(yīng)地向需求地調(diào)運(yùn)的方案,沒(méi)有考慮實(shí)際運(yùn)輸過(guò)程中所行走的路線。而現(xiàn)實(shí)中，供應(yīng)地與需求地一般都不在同一地點(diǎn)，兩者

8、之間可能有多條可行走的路線。因此，傳統(tǒng)的運(yùn)輸問(wèn)題在實(shí)際應(yīng)用中存在一定缺陷。本文在考慮最短路的基礎(chǔ)上求解運(yùn)輸問(wèn)題,在很大程度上可解決這-實(shí)際問(wèn)題。該種方法在現(xiàn)在社會(huì)的研究屮，特別是交通網(wǎng)越來(lái)越完善的前提下就顯得尤為的重要，考慮路線問(wèn)題來(lái)決沱運(yùn)輸問(wèn)題的方案在現(xiàn)在社會(huì)里也許會(huì)帶來(lái)更大的經(jīng)濟(jì)效益。該方法是結(jié)合了運(yùn)籌學(xué)屮的求解最短路徑的方法來(lái)找出運(yùn)輸時(shí)的最佳運(yùn)輸路線，己達(dá)到減少運(yùn)輸