運(yùn)籌學(xué)課程論文

運(yùn)籌學(xué)論文一利用表上作業(yè)法解產(chǎn)銷相等運(yùn)輸問(wèn)題摘要：運(yùn)輸問(wèn)題是運(yùn)籌學(xué)中的一個(gè)重要問(wèn)題，也是物流系統(tǒng)優(yōu)化的常見(jiàn)的問(wèn)題，同時(shí)也是一種特殊的線性規(guī)劃問(wèn)題。怎么樣盡可能的減少運(yùn)輸成本以及減少運(yùn)輸費(fèi)用一直是各類物流系統(tǒng)密切關(guān)注的問(wèn)題。本文通過(guò)科學(xué)的方法對(duì)問(wèn)題具體化，再建立數(shù)學(xué)模型進(jìn)行求解，以找到運(yùn)輸成本最小的組合。關(guān)鍵詞：運(yùn)輸問(wèn)題產(chǎn)銷均衡表上作業(yè)法一、 引言運(yùn)輸問(wèn)題是線性規(guī)劃的一種特殊形式，運(yùn)輸問(wèn)題主要是解決這樣的問(wèn)題：在大宗物資調(diào)運(yùn)時(shí)，有若干個(gè)產(chǎn)地，根據(jù)己知的運(yùn)輸交通網(wǎng)，如何制定一個(gè)運(yùn)輸方案，將這些物資運(yùn)到各個(gè)銷傳地，使得總運(yùn)費(fèi)最小。物流管理的本質(zhì)要求就是求實(shí)效，即以最少的消耗，實(shí)現(xiàn)最優(yōu)的服務(wù)，達(dá)到最佳的經(jīng)濟(jì)效益。搞好物流管理，可以通過(guò)合理的運(yùn)輸方案，使中間裝卸搬運(yùn)、儲(chǔ)存費(fèi)用降低、損失減少，在其他條件不變的情況下，降低物流成本就意味著擴(kuò)大了企業(yè)的利潤(rùn)空間，提高了利潤(rùn)水平，所以一個(gè)合理的運(yùn)輸方案有著重要的意義。運(yùn)輸問(wèn)題提出后，人們對(duì)其求解方法進(jìn)行了大量研究，并有了大量成果，尤其在近十幾年，借由大量軟件的開發(fā)，運(yùn)輸問(wèn)題大多可以由電腦來(lái)解決，特別是對(duì)于那些數(shù)據(jù)異常多的運(yùn)輸問(wèn)題，軟件的應(yīng)用就更加必要。但是，本文想重點(diǎn)探討的是Danzig的表上作業(yè)法，這種方法是最簡(jiǎn)單和最常用的，對(duì)于數(shù)據(jù)較少的運(yùn)輸問(wèn)題，非常適合。二、 運(yùn)輸問(wèn)題研究現(xiàn)狀：運(yùn)輸問(wèn)題是運(yùn)籌學(xué)的一個(gè)分支，它研究的是如何在一個(gè)大宗物資調(diào)運(yùn)中，制定出一個(gè)由若干個(gè)產(chǎn)地，將這些物資根據(jù)已知的運(yùn)輸交通網(wǎng)運(yùn)到各個(gè)銷傳地的方案，使得總運(yùn)費(fèi)最小。運(yùn)輸問(wèn)題是在1941年美國(guó)學(xué)者希奇柯克在研究生產(chǎn)組織和鐵路運(yùn)輸方面的線性規(guī)劃問(wèn)題時(shí)提出的。運(yùn)輸問(wèn)題的提出，不僅可以求出物資的合理調(diào)運(yùn)方案，其他類型的問(wèn)題也都可以經(jīng)過(guò)變換后轉(zhuǎn)為運(yùn)輸問(wèn)題來(lái)進(jìn)行求解。運(yùn)輸問(wèn)題自提出以來(lái)，人們對(duì)其解法進(jìn)行了大量的研究：從目標(biāo)函數(shù)的角度，運(yùn)輸問(wèn)題同時(shí)考慮運(yùn)輸總費(fèi)用最小、運(yùn)輸過(guò)程中損壞率最低和單位運(yùn)價(jià)變化的調(diào)整等多個(gè)目標(biāo)，所以有宋葉新、陳綿云和吳曉平研究的具有模糊信息的目標(biāo)運(yùn)輸問(wèn)題求解、李珍萍研究的最短時(shí)限運(yùn)輸問(wèn)題、帶瓶頸限制的運(yùn)輸問(wèn)題、運(yùn)用禁忌搜索算法解決帶固定費(fèi)用的運(yùn)輸問(wèn)題、調(diào)整單位運(yùn)價(jià)使得運(yùn)輸計(jì)劃最優(yōu)的運(yùn)輸問(wèn)題的逆問(wèn)題等等。從算法角度來(lái)看，人們對(duì)運(yùn)輸問(wèn)題提出了大量算法，如表上作業(yè)法、圖上求解法、遺傳算法、神經(jīng)網(wǎng)絡(luò)算法、減運(yùn)價(jià)算法、仿真優(yōu)化法、內(nèi)點(diǎn)法等等。從計(jì)算機(jī)求解角度來(lái)看，目前己經(jīng)有很多對(duì)運(yùn)用計(jì)算機(jī)求解運(yùn)輸問(wèn)題的研究，如運(yùn)輸問(wèn)題的計(jì)算機(jī)求解、Excel求解運(yùn)輸問(wèn)題、Ling。求解運(yùn)輸問(wèn)題、Matlab求解。此外，還有其他軟件也可以求解運(yùn)輸問(wèn)題，比如運(yùn)籌學(xué)CAI軟件，不過(guò)功能比較少,Winqsb等等，現(xiàn)實(shí)中運(yùn)用比較廣泛的是Lingo和Matlab。運(yùn)輸問(wèn)題是社會(huì)經(jīng)濟(jì)生活中經(jīng)常出現(xiàn)的優(yōu)化問(wèn)題，我們經(jīng)常碰到物資調(diào)運(yùn)如煤、糧食、鋼材、木材等，這些都是大宗型的運(yùn)輸，在物流流通中通過(guò)合理的運(yùn)輸方案，使中間裝卸搬運(yùn)、儲(chǔ)存費(fèi)用降低、損失減少，以最少的消耗，實(shí)現(xiàn)經(jīng)濟(jì)效益最大化，所以一個(gè)合理的科學(xué)的運(yùn)輸方案有著重要的意義。在眾多的求解方法和求解工具中，總會(huì)有各自的優(yōu)缺點(diǎn)，所以尋求一個(gè)好中更好的求解工具，提高求解效率和可擴(kuò)展性將會(huì)有很重要的意義。同時(shí)，在現(xiàn)實(shí)生活中，許多問(wèn)題都可以轉(zhuǎn)化成運(yùn)輸問(wèn)題數(shù)學(xué)模型進(jìn)行求解，所以研究運(yùn)輸問(wèn)題也等于研究了很多相關(guān)的問(wèn)題，其意義更明顯。三、相關(guān)理論概述：運(yùn)輸問(wèn)題：運(yùn)輸問(wèn)題是線性規(guī)劃的一種特殊形式，運(yùn)輸問(wèn)題主要是解決這樣的問(wèn)題：在大宗物資調(diào)運(yùn)時(shí)，有若干個(gè)產(chǎn)地，根據(jù)己知的運(yùn)輸交通網(wǎng)，如何制定一個(gè)運(yùn)輸方案，將這些物資運(yùn)到各個(gè)銷售地，使得總運(yùn)費(fèi)最小。物流管理的本質(zhì)要求就是求實(shí)效，即以最少的消耗，實(shí)現(xiàn)最優(yōu)的服務(wù)，達(dá)到最佳的經(jīng)濟(jì)效益。線性規(guī)劃：線性規(guī)劃是運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法較成熟的一個(gè)重要分支,它是輔助人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法.在經(jīng)濟(jì)管理、交通運(yùn)輸、工農(nóng)業(yè)生產(chǎn)等經(jīng)濟(jì)活動(dòng)中，提高經(jīng)濟(jì)效果是人們不可缺少的要求，而提高經(jīng)濟(jì)效果一般通過(guò)兩種途徑：一是技術(shù)方面的改進(jìn)，例如改善生產(chǎn)工藝，使用新設(shè)備和新型原材料.二是生產(chǎn)與計(jì)劃的改進(jìn)，即合理安排人力物力資源.線性規(guī)劃所研究的是：在一定條件下，合理安排人力物力等資源，使經(jīng)濟(jì)效果達(dá)到最好.一般地，求線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小值的問(wèn)題，統(tǒng)稱為線性規(guī)劃問(wèn)題。滿足線性約束條件的解叫做可行解，由所有可行解組成的集合叫做可行域。決策變量、約束條件、目標(biāo)函數(shù)是線性規(guī)劃的三要素。3、 經(jīng)典運(yùn)輸模型：經(jīng)典的運(yùn)輸問(wèn)題是一個(gè)線性規(guī)劃模型。假定某種物資有m個(gè)產(chǎn)地，n個(gè)銷地街為第i產(chǎn)地的供應(yīng)量，bj為第j個(gè)銷地的需求量,勺為從產(chǎn)地i到銷地j的單位運(yùn)費(fèi)，Xjj為產(chǎn)地i到銷地j的調(diào)運(yùn)數(shù)量，XRO,其中i=l,2，…,m：j=l,2，…,n。問(wèn)如何組織調(diào)運(yùn)才能使得總運(yùn)費(fèi)最?。吭搯?wèn)題為了尋找最佳調(diào)運(yùn)方案，即求解所有％的值.使總的運(yùn)輸費(fèi)用:2^1￡旗1勺％達(dá)到最少。其中當(dāng)￡』為=￡苗場(chǎng)時(shí)為平衡型運(yùn)輸問(wèn)題：當(dāng)其不相等的時(shí)候就位不平衡型運(yùn)輸問(wèn)題。實(shí)際上步平衡型的運(yùn)輸問(wèn)題通過(guò)轉(zhuǎn)換可以變成平衡型的問(wèn)題。當(dāng)產(chǎn)量總量等于銷餌總量時(shí)，運(yùn)輸問(wèn)題有可行解，且有最優(yōu)解，且當(dāng)產(chǎn)量和銷侈量均為整數(shù)時(shí)，必存在決策變量均為整數(shù)的最優(yōu)解。平衡型運(yùn)輸問(wèn)題的數(shù)學(xué)模型如下：miiiZ=￡寓崩當(dāng)勺刊S.t. ￡?。軽jj=bj,j=l,2...m￡金iXjj=ai,i=l,2...nXjj?0,對(duì)所有的i,j運(yùn)輸問(wèn)題的解法通常用表上作業(yè)法。表上作業(yè)法是單純形法在求解運(yùn)輸問(wèn)題。4、 表上作業(yè)法運(yùn)輸問(wèn)題的解法通常用表上作業(yè)法。表上作業(yè)法是單純形法在求解運(yùn)輸問(wèn)題。表上作業(yè)通常有三種：西北角法、最小元素法、vogel（沃格爾）法。（1） 西北角法：從西北角（左上角）格開始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然后按行（列）標(biāo)下一格的數(shù)。若某行（列）的產(chǎn)量（銷量）己滿足，則把該行（列）的其他格劃去。如此進(jìn)行下去，直至得到一個(gè)基本可行解。（2） 最小元素法：從運(yùn)價(jià)最小的格開始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然后按運(yùn)價(jià)從小到大順序填數(shù)。若某行（列）的產(chǎn)量（銷量）己滿足，則把該行（列）的其他格劃去。如此進(jìn)行下去，直至得到一個(gè)基本可行解。（3） vogel（沃格爾）法：在運(yùn)價(jià)表上寫出每行和每列運(yùn)價(jià)中最小元素和次小元素之差。從所有行差額和列差額中選取差額最大的一行或一列進(jìn)行分配，并對(duì)該行（或列）最小元素格填數(shù)。重新計(jì)算差額，重復(fù)上述手續(xù)。剩最后一行或一列按余額分配，只填數(shù)即可，確保有數(shù)字個(gè)數(shù)為m+n-1個(gè)。

四、實(shí)例分析:某公司下屬四個(gè)儲(chǔ)存某種物資的料庫(kù)，供應(yīng)五個(gè)工地的需要。四個(gè)料庫(kù)的供應(yīng)量和五個(gè)工地的需求量以及由各料庫(kù)到各工地調(diào)運(yùn)單位物資的運(yùn)價(jià)見(jiàn)卜.表，試求運(yùn)輸費(fèi)用最小的合理調(diào)運(yùn)方案。工地料庫(kù)ABCDE供應(yīng)量（t）甲32353100乙33134300丙78422600J'54778800需求量（t）2503003504005001800現(xiàn)在我們分別利用三種方法求解運(yùn)輸費(fèi)用:（1）西北角法:工地料庫(kù)ABCDE供應(yīng)量（t）甲3(100)XXXX0乙3(150)3(150)XXX0丙X8(150)4(350)2(100)X0J'XXX7(300)8(500)0需求量（t）000001800運(yùn)費(fèi)：3X100+3X150+3X150+8X150+4X350+2X100+7X300+5X800=10100(2)最小元素法：工地料庫(kù)ABCDE供應(yīng)量（t）甲X2(100)XXX0乙XX1(300)XX0丙XXX2(400)2(200)0J'5(250)4(200)7(50)X8(300)0需求量（t）000001800運(yùn)費(fèi)：5X250+2X100+4X200+1X300+7X50+2X400+2X200+8X300=6500(3)VOGEL(沃格爾)法:工地料庫(kù)ABCDE供應(yīng)量（t）甲XXXX3(100)0乙XX1(300)XX0丙XXX2(200)2(400)0J'5(250)4(300)7(50)7(200)X0需求量（t）000001800運(yùn)費(fèi)：5X250+4X300+1X300+7X50+2X400+3X100+2X400=6000三種方法運(yùn)費(fèi)：6000<6800<<10100五:結(jié)論：對(duì)于表上作業(yè)法的三種方法而言，西北角法雖然簡(jiǎn)單，但是，這種方法只是單純的解決了運(yùn)輸分配問(wèn)題，沒(méi)有考慮運(yùn)費(fèi)問(wèn)題，因而導(dǎo)致了這種方法最后的運(yùn)費(fèi)較高，離最優(yōu)運(yùn)費(fèi)相距甚遠(yuǎn)。因而，在解決實(shí)際問(wèn)題的時(shí)候，往往會(huì)放棄這種方法。而最小元素法初看起來(lái)十分合理，但是，有時(shí)按最小單位運(yùn)價(jià)優(yōu)先安排物品調(diào)運(yùn)時(shí)，往往選擇了價(jià)格較高的運(yùn)點(diǎn)，從而使運(yùn)輸費(fèi)用增加，因而最小元素法所得的運(yùn)費(fèi)多是較