運籌學課程論文

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

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