線性規(guī)劃在運(yùn)輸問(wèn)題中的應(yīng)用

1、線性規(guī)劃在運(yùn)輸問(wèn)題中的應(yīng)用【摘要】 用運(yùn)籌學(xué)的思想探討運(yùn)籌學(xué)課程的教學(xué)方法。運(yùn)籌學(xué)中的指派問(wèn)題、最短路問(wèn)題，最小費(fèi)用流問(wèn)題可轉(zhuǎn)化為運(yùn)輸問(wèn)題或轉(zhuǎn)運(yùn)問(wèn)題，從而可以統(tǒng)籌安排這些教學(xué)內(nèi)容，為提高教學(xué)效果，減少教學(xué)時(shí)間找出更優(yōu)的教學(xué)方法?！娟P(guān)鍵詞】 運(yùn)輸問(wèn)題；轉(zhuǎn)運(yùn)問(wèn)題； 運(yùn)籌學(xué)；線性規(guī)劃；教學(xué)方法引言：隨著我國(guó)國(guó)民經(jīng)濟(jì)的不斷開(kāi)展，企業(yè)之間的交易活動(dòng)更加頻繁,同地區(qū)、不同地區(qū)、甚至跨國(guó)的交易活動(dòng)也不斷發(fā)生，運(yùn)輸那么成為交易的活動(dòng)重點(diǎn)了。交通運(yùn)輸作為國(guó)民經(jīng)濟(jì)的一個(gè)重要部門(mén)，作為人類(lèi)進(jìn)步、社會(huì)開(kāi)展的一個(gè)重要推動(dòng)力，其開(kāi)展模式正在對(duì)環(huán)境產(chǎn)生越來(lái)越重要的影響。傳統(tǒng)的運(yùn)輸方式已經(jīng)不能滿(mǎn)足環(huán)境保護(hù)、經(jīng)濟(jì)開(kāi)展以及交通運(yùn)

2、輸本身開(kāi)展的需求，探尋與環(huán)境、資源條件相適應(yīng)的運(yùn)輸是非常重要的一個(gè)問(wèn)題。人們?cè)谶\(yùn)輸方面趨利避害建立更好的運(yùn)輸方法，讓交通運(yùn)輸?shù)姆椒ǖ竭_(dá)一個(gè)更高的水平。1線性規(guī)劃簡(jiǎn)介線性規(guī)劃法是解決多變量最優(yōu)決策的方法，是在各種 相互關(guān)聯(lián)的多變量約束條件下，解決或規(guī)劃一個(gè)對(duì)象的線性目標(biāo)函數(shù)最優(yōu)的問(wèn)題，即給與一定數(shù)量的人力、物力和資源，如何應(yīng)用而能得到最大經(jīng)濟(jì)效益。當(dāng)資源限制或約束條件表現(xiàn)為線性等式或不等式，目標(biāo)函數(shù)表示為線性函數(shù)時(shí)，可運(yùn)用線性規(guī)劃法進(jìn)行決策。線性規(guī)劃法就是在線性等式或不等式的約束條件下，求解線性目標(biāo)函數(shù)的最大值或最小值的方法。其中目標(biāo)函數(shù)是決策者要求到達(dá)目標(biāo)的數(shù)學(xué)表達(dá)式，用一個(gè)極大&#

3、160;或極小值表示。約束條件是指實(shí)現(xiàn)目標(biāo)的能力資源和內(nèi) 部條件的限制因素，用一組等式或不等式來(lái)表示。線性規(guī)劃是決策系統(tǒng)的靜態(tài)最優(yōu)化數(shù)學(xué)規(guī)劃方法之一。它作為經(jīng)營(yíng)管理決策中的數(shù)學(xué)手段，在現(xiàn)代決策中的應(yīng)用是非常廣泛的，它可以用來(lái)解決科學(xué)研究、工程設(shè)計(jì)、生產(chǎn)安排、軍事指揮、經(jīng)濟(jì)規(guī)劃；經(jīng)營(yíng)管理等各方面提出的大量問(wèn)題。 最近幾年，我國(guó)物流產(chǎn)業(yè)快速開(kāi)展，形成了物流熱。在物流作業(yè)的管理活動(dòng)中，有著大量的規(guī)劃問(wèn)題，物資的合理調(diào)運(yùn)就是其中一個(gè)比擬重要的問(wèn)題。求物資調(diào)運(yùn)的最優(yōu)調(diào)運(yùn)方案，就是要在滿(mǎn)足各種資源限制的條件下，找到使運(yùn)輸總費(fèi)用最小的調(diào)運(yùn)方案。 2.線性規(guī)劃在運(yùn)輸中的應(yīng)用在現(xiàn)實(shí)

4、的生產(chǎn)經(jīng)營(yíng)、商品銷(xiāo)售、經(jīng)濟(jì)建設(shè)和物資管理過(guò)程中，常常會(huì)遇到各類(lèi)物資的分配和調(diào)運(yùn)問(wèn)題，即將各種生產(chǎn)資料或生活資料消耗品從供給基地調(diào)運(yùn)到需求基地，這里就需要如何根據(jù)現(xiàn)有條件科學(xué)、合理的安排調(diào)運(yùn)方案，提高運(yùn)輸經(jīng)濟(jì)效益。這就是屬于線性規(guī)劃中網(wǎng)絡(luò)配送的以最小的本錢(qián)完成貨物的運(yùn)輸問(wèn)題。運(yùn)輸問(wèn)題就是討論有關(guān)物資調(diào)運(yùn)的問(wèn)題，即將數(shù)量和單位運(yùn)價(jià)都給定的某種物資從供給站運(yùn)送到消費(fèi)站，要求在供給和需求平衡的同時(shí)，制定出流量與流向，使總運(yùn)輸本錢(qián)最低。運(yùn)輸問(wèn)題是特殊的線性規(guī)劃問(wèn)題，根據(jù)問(wèn)題的要求，建立數(shù)學(xué)模型，用表上作業(yè)法或線性規(guī)劃軟件求解，即可得出最正確的調(diào)運(yùn)方案，取得了較好的經(jīng)濟(jì)效益。在運(yùn)輸問(wèn)題中，確定的需求限制占

5、據(jù)著重要的地位，即必須確定需求以及相應(yīng)地確定需求的約束條件。  3.運(yùn)輸問(wèn)題的特征 運(yùn)輸問(wèn)題關(guān)心的是以最低的總配送本錢(qián)把供給中心出發(fā)地的任何產(chǎn)品運(yùn)送到每一個(gè)接收中心目的地。每一個(gè)出發(fā)地都有一定供給量配送到目的地，每一個(gè)目的地都需要一定的需求量。運(yùn)輸問(wèn)題在供給量和需求量?jī)煞矫娑甲龀隽巳缦碌募僭O(shè)：需求假設(shè)。每一個(gè)出發(fā)地都有一個(gè)固定的供給量，所有的供給量都必須配送到目的地。與之類(lèi)似，每一個(gè)目的地都有一個(gè)固定的需求量，整個(gè)需求量都必須由出發(fā)地滿(mǎn)足本錢(qián)假設(shè)。從任何一個(gè)出發(fā)地到任何一個(gè)目的地的貨物配送本錢(qián)和所配送的數(shù)量成線性比例關(guān)系。因此，這個(gè)本錢(qián)就等于配送的單位本錢(qián)乘以所配送的數(shù)量。

6、運(yùn)輸問(wèn)題所需要的數(shù)據(jù)僅僅是供給量、需求量和單位本錢(qián)，這些就是模型參數(shù)。如果一個(gè)問(wèn)題可以完全描述成如下表所示的參數(shù)表形式，明確出發(fā)地、供給量、需求量和單位本錢(qián)，并且符合需求假設(shè)和本錢(qián)假設(shè)，那么這個(gè)問(wèn)題不管其中是否涉及到運(yùn)輸都適用于運(yùn)輸問(wèn)題模型，最終目的都是要使配送的總本錢(qián)最小。 4.運(yùn)輸問(wèn)題的數(shù)學(xué)模型 設(shè)某種物品有 m 個(gè)產(chǎn)地 ， ， ，各產(chǎn)地的產(chǎn)量分別是 ，；有 n 個(gè)銷(xiāo)地 ，各銷(xiāo)地的銷(xiāo)量分別為 ，假定從 產(chǎn)地 i=1，2，m 向銷(xiāo)地 j=1，2，n 運(yùn)輸單位物品的運(yùn)價(jià)為 ，假設(shè)用表示從到的運(yùn)輸量，那么在產(chǎn)銷(xiāo)平衡條件下，總費(fèi)用最低的數(shù)學(xué)模型為  運(yùn)輸問(wèn)題通常用表上

7、作業(yè)法求解，表上作業(yè)法是單純形法求解運(yùn)輸問(wèn)題時(shí)的一種簡(jiǎn)化方法，其實(shí)質(zhì)是單純形法。表上作業(yè)法首先需要經(jīng)過(guò)次加法運(yùn)算求出初始基可行解。在初始基可行解根底上用閉回路法或位勢(shì)法計(jì)算所有空格非基變量的檢驗(yàn)數(shù) ，如用位勢(shì)法，需要經(jīng)過(guò)解次一元一次方程計(jì)算位勢(shì)和計(jì)算個(gè)檢驗(yàn)數(shù)，共需要計(jì)算 次。 當(dāng)所有檢驗(yàn)數(shù)時(shí)，得最優(yōu)解，否那么需要在表上用閉回路法進(jìn)行調(diào)整，確定換入變量和換出變量，找出新 的基可行解，直到得出最優(yōu)解為止。假設(shè)需要調(diào)整 k 次，那么 中間環(huán)節(jié)需要計(jì)算次。故全部過(guò)程一共需要經(jīng)過(guò)次運(yùn)算，當(dāng) m，n 很大時(shí)，表上作業(yè)的計(jì)算量龐大且繁雜。本文提出的用線性規(guī)劃法求解 運(yùn)

8、輸問(wèn)題將大大提高最優(yōu)解的求解速度，大大提高了效率。 5.實(shí)例 現(xiàn)在物流業(yè)面臨的新問(wèn)題是： 認(rèn)定所給問(wèn)題確實(shí)是一個(gè)線性規(guī)劃問(wèn)題； 把它建立起線性數(shù)學(xué)模型； 并能夠完成具體實(shí)務(wù)的全部工作。第一個(gè)問(wèn)題實(shí)質(zhì)上是具體實(shí)務(wù)究竟?jié)M足什么條件才能應(yīng)用線性規(guī)劃的方法。一般地說(shuō)，必須有：一定要滿(mǎn)足將目標(biāo)表為最小化或最大化的要求；一定要有到達(dá)目標(biāo)的不同方法，且必須要有選擇的可能性；要求的目標(biāo)是有限制條件的；必須將約束條件用數(shù)學(xué)表示為線性等式或線性不等式，并將目標(biāo)函數(shù)化為線性函數(shù)。5.1物資調(diào)運(yùn)最優(yōu)問(wèn)題： 例 1：蘋(píng)果的運(yùn)價(jià)及產(chǎn)銷(xiāo)量如表 1，求總運(yùn)費(fèi)最省的運(yùn)輸方案。運(yùn)價(jià)銷(xiāo)地產(chǎn)量

9、B1 B2 B3產(chǎn)地A174109產(chǎn)地A231137銷(xiāo)量656表1解：找線性關(guān)系：設(shè)表示產(chǎn)地供給銷(xiāo)地的物資數(shù)量，產(chǎn)地A1 產(chǎn)量只有9個(gè)單位，可供銷(xiāo)地B1、B2、B3， 其和為9，B1、B2、B3 的量有多種選擇。而B(niǎo)1 只需6個(gè)單位，可選A 1、A2 的產(chǎn)量，其和小于6。因?yàn)榭備N(xiāo)量大于總產(chǎn)量。故約束為： 又從A1 運(yùn)1 個(gè)單位的蘋(píng)果到B1 需運(yùn)價(jià)7 個(gè)單位，假設(shè)個(gè)單位那么運(yùn)價(jià)，因此滿(mǎn)足約束的得總運(yùn)價(jià)的目標(biāo)函數(shù)為：此約束方程組不是標(biāo)準(zhǔn)型。將約束條件方程組2標(biāo)準(zhǔn)化為：用單純形法的程序在計(jì)算機(jī)上可得最優(yōu)調(diào)運(yùn)矩陣為，最省的運(yùn)費(fèi)為。特別地，當(dāng)產(chǎn)量大于銷(xiāo)量時(shí)，如常數(shù)9 改為12，約束條

10、件前兩個(gè)方程改為，后面三個(gè)用等式。當(dāng)產(chǎn)銷(xiāo)平衡時(shí)，約束方程組是等式方程組，方程組的個(gè)數(shù)為個(gè)。5.2車(chē)輛調(diào)度問(wèn)題物流部門(mén)承接的運(yùn)輸千萬(wàn)種，并往往是幾十種物資同時(shí)調(diào)運(yùn)。為此，只有一種物資的數(shù)學(xué)模型求最優(yōu)調(diào)運(yùn)方案方法，在多種物質(zhì)運(yùn)輸情況下就不能直接使用。原因是：在調(diào)度汽車(chē)去完成運(yùn)輸任務(wù)時(shí)，免不了要出現(xiàn)空駛現(xiàn)象。例如某車(chē)隊(duì)有一天要完成如表2 所示的運(yùn)輸任務(wù)，各地間的距離如表3，問(wèn)應(yīng)怎樣安排汽車(chē)去完成這些任務(wù)才能做到最??？ 分析：滿(mǎn)車(chē)路線和方向顯然是固定的，但空車(chē)的路程、方向卻沒(méi)有固定。如把木材從火車(chē)站運(yùn)到建筑工地卸下后，空車(chē)即可去火車(chē)站裝煤，也可去文具公司裝紙張。空車(chē)的走法不同，空駛的t

11、83;km 數(shù)當(dāng)然也不同，這就產(chǎn)生了車(chē)輛調(diào)度問(wèn)題。車(chē)輛調(diào)度問(wèn)題主要解決的是：怎樣安排車(chē)輛去完成所有的運(yùn)輸任務(wù)并使空駛的t·km數(shù)最小。物資調(diào)運(yùn)問(wèn)題是“怎樣才能使物資運(yùn)輸?shù)膖·km 數(shù)最小；這就是說(shuō)把空車(chē)看成是一批貨物卸幾噸貨物就看成是幾噸空車(chē)，那么把車(chē)輛調(diào)度問(wèn)題轉(zhuǎn)化為物資調(diào)運(yùn)問(wèn)題。把空車(chē)看成是貨物，其發(fā)、收產(chǎn)、銷(xiāo)點(diǎn)及發(fā)、收產(chǎn)、銷(xiāo)量按如下的方法決定： 1假設(shè)某點(diǎn)的缷貨總量大于裝貨總量，那么該點(diǎn)是空車(chē)的發(fā)點(diǎn)，其發(fā)量等于卸貨總量與裝貨總量之差。如學(xué)校的卸貨總量為4，裝貨為0，故學(xué)校是發(fā)點(diǎn)，發(fā)量為4。2假設(shè)某點(diǎn)裝貨總量大于卸貨總量，那么該點(diǎn)是空車(chē)的收點(diǎn)，其收量也是二者之差

12、。3如果某點(diǎn)的卸貨總量等于裝貨總量，如此點(diǎn)不存在空車(chē)那么不予考慮。為此，車(chē)輛調(diào)度問(wèn)題可作為物資調(diào)運(yùn)問(wèn)題來(lái)處理。即空車(chē)的流向應(yīng)怎樣才能使車(chē)輛調(diào)度合理？其主要步驟如下：確定空車(chē)的收發(fā)點(diǎn)和收發(fā)量，并列表；確定空車(chē)調(diào)運(yùn)的數(shù)學(xué)模型，并求解；根據(jù)所得解并結(jié)合具體情況合理調(diào)派車(chē)輛。解：收點(diǎn)：火車(chē)站、文具公司、糧店；發(fā)點(diǎn)：建筑工地、鋼廠、學(xué)校。約束條件為：用單純形法的程序在計(jì)算機(jī)上可得：鋼廠、學(xué)校分別向火車(chē)站發(fā)2t 空車(chē)，建筑工地向文具公司和糧店發(fā)2t 空車(chē)。空車(chē)噸公里數(shù)最小是：6.結(jié)論通過(guò)上例分析，我們可以很清楚地了解線性規(guī)劃企業(yè)運(yùn)輸決策的整個(gè)運(yùn)作過(guò)程具有很大的實(shí)踐意義。利用線性規(guī)劃進(jìn)行運(yùn)輸決策，可以制定出

13、最正確運(yùn)輸方案，往哪里運(yùn)，運(yùn)多少，而且可以同時(shí)對(duì)線性規(guī)劃的進(jìn)一步運(yùn)用、剖析運(yùn)輸決策中各環(huán)節(jié)、各部門(mén)之間的內(nèi)在聯(lián)系，使人力、物力和財(cái)力能夠得到充分利用，從而實(shí)現(xiàn)最優(yōu)化的貨物流通，使企業(yè)的利潤(rùn)進(jìn)一步追加，最終得到最正確運(yùn)輸方案，提高企業(yè)經(jīng)濟(jì)效益。然而在實(shí)際應(yīng)用中，往往要綜合考慮各個(gè)方面的影響因素，僅僅從貨物分配方面考慮并不能單純的解決運(yùn)輸費(fèi)用的最小控制，所以，對(duì)于該問(wèn)題的研究還有待于更深一步的探討。7.心得與體會(huì)在教學(xué)中，將看似不同的問(wèn)題歸納轉(zhuǎn)化為同一問(wèn)題，非常重要。首先，這涉及到教學(xué)內(nèi)容的結(jié)構(gòu)問(wèn)題，原來(lái)看似不同的問(wèn)題可能在教材的不同章節(jié)，轉(zhuǎn)化為同一問(wèn)題后可并入同一章節(jié)。第二，對(duì)提高教學(xué)效果有一定

14、的幫助。對(duì)老師而言，可減少教學(xué)時(shí)間，原先要花較多時(shí)間講解不同的問(wèn)題，現(xiàn)在只需講解一個(gè)問(wèn)題，然后作為同一問(wèn)題舉一反三，不僅可將原問(wèn)題講授得更清楚，也解決了新問(wèn)題。對(duì)學(xué)生而言，原先要記多種問(wèn)題的解法，現(xiàn)在只需記一種解法就可以了，減輕了學(xué)習(xí)負(fù)擔(dān)。第三，更重要的是，啟發(fā)學(xué)生對(duì)問(wèn)題有更深入的理解，抓住事物的本質(zhì)，而不是停留在外表，這對(duì)培養(yǎng)學(xué)生抽象思維、綜合歸納能力是大有裨益的。當(dāng)然，要做到這一點(diǎn)，對(duì)老師的要求顯然更高，必須要花更多的時(shí)間和精力研究問(wèn)題，吃透教材，理解精髓，融會(huì)貫穿，非一般的應(yīng)付教學(xué)所能解決的。最后，在用計(jì)算機(jī)求解方面，可用同一程序處理這些類(lèi)似的問(wèn)題。因此，將看似不同的問(wèn)題歸納轉(zhuǎn)化為同一問(wèn)題，可以統(tǒng)籌安排教學(xué)內(nèi)容，在現(xiàn)有的教學(xué)條件下，能幫助我們提高教學(xué)效果，減少教學(xué)時(shí)間。這正是運(yùn)籌學(xué)的精髓，對(duì)各種有限資源進(jìn)行統(tǒng)籌安排，找出最優(yōu)方案。所以本文與其說(shuō)是教學(xué)體會(huì)，還不如說(shuō)是運(yùn)籌學(xué)方法的運(yùn)用，用運(yùn)籌學(xué)方法探討運(yùn)籌學(xué)的教學(xué)問(wèn)題，為運(yùn)籌學(xué)教學(xué)找到一種更好的方法。8.參考文獻(xiàn)1 徐輝,張延飛.管理運(yùn)