第七章運(yùn)輸問(wèn)題ppt課件.ppt

《第七章運(yùn)輸問(wèn)題ppt課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、運(yùn)輸問(wèn)題在工商管理中有著廣泛的應(yīng)用，它是一類特殊的線性規(guī)劃問(wèn)題，對(duì)于運(yùn)輸問(wèn)題，當(dāng)然可以用前面所介紹的單純形法進(jìn)行求解，但由于這類線性規(guī)劃問(wèn)題在結(jié)構(gòu)上有其特殊性，我們可以找到比標(biāo)準(zhǔn)單純形法更簡(jiǎn)單有效的專門(mén)方法，從而節(jié)約計(jì)算時(shí)間和費(fèi)用，因此，這里把運(yùn)輸問(wèn)題單列一章進(jìn)行討論。本章介紹運(yùn)輸問(wèn)題的模型、表上作業(yè)法以及運(yùn)輸問(wèn)題的一些實(shí)際應(yīng)用。運(yùn)問(wèn)題輸?shù)诹乱?、運(yùn)輸問(wèn)題的提出及其數(shù)學(xué)模型一般的運(yùn)輸問(wèn)題就是要解決把某種產(chǎn)品從若干個(gè)產(chǎn)地調(diào)運(yùn)到若干個(gè)銷地，在每個(gè)產(chǎn)地的供應(yīng)量與每個(gè)銷地的需求量已知，并知道各地之間的運(yùn)輸單價(jià)的前提下，如何確定一個(gè)使得總的運(yùn)輸費(fèi)用

2、最小的方案。例題1：某公司從兩個(gè)產(chǎn)地A1，A2將產(chǎn)品運(yùn)往三個(gè)銷地B1，B2，B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地的單位產(chǎn)品運(yùn)費(fèi)如表3-1所示。問(wèn)如何調(diào)運(yùn)，使得總運(yùn)輸費(fèi)最??？解：從表中可以看到，A1，A2兩個(gè)產(chǎn)地的總產(chǎn)量為500件；B1，B2，B3三個(gè)銷地的總銷量為500件，因此這是一個(gè)產(chǎn)銷平衡的運(yùn)輸問(wèn)題。把A1，A2的產(chǎn)量全部分配給B1，B2，B3，正好滿足這三個(gè)銷地的需要。此數(shù)學(xué)模型當(dāng)然可用線性規(guī)劃的常用方法求解（比如單純形法），但求解的程序相對(duì)復(fù)雜，即使利用計(jì)算機(jī)程序來(lái)求解，其輸入和解決問(wèn)題的規(guī)模都受到限制。因此，管理運(yùn)

3、籌學(xué)中有專門(mén)的求解運(yùn)輸問(wèn)題的程序，一般只要輸入產(chǎn)點(diǎn)數(shù)，各產(chǎn)地的產(chǎn)量，銷點(diǎn)數(shù)，各銷地的銷量，以及各產(chǎn)地到各銷地的運(yùn)輸單價(jià)，立即可得到運(yùn)輸問(wèn)題的最優(yōu)解。把本例的相關(guān)數(shù)據(jù)輸入運(yùn)輸問(wèn)題的程序，得到最優(yōu)解為：先給出一般運(yùn)輸問(wèn)題的線性規(guī)劃模型。我們用A1，A2，…，表示某種物資的m個(gè)產(chǎn)地；B1，B2，…，Bn表示某種物資的n個(gè)銷地；表示產(chǎn)地的產(chǎn)量；表示銷地的銷量；表示把物資從產(chǎn)地i運(yùn)到銷地j的單位運(yùn)價(jià)；并設(shè)為從產(chǎn)地運(yùn)到銷地的運(yùn)輸量，則產(chǎn)銷平衡的運(yùn)輸問(wèn)題的線性規(guī)劃數(shù)學(xué)模型如下所示有時(shí)上述問(wèn)題的一般模型會(huì)發(fā)生如下一些變化：求目標(biāo)函數(shù)值的最大值而不是最小值

4、。有些運(yùn)輸問(wèn)題中，其目標(biāo)是找出利潤(rùn)最大或營(yíng)業(yè)額最大的調(diào)運(yùn)方案，這時(shí)要求目標(biāo)函數(shù)的最大值。當(dāng)某些運(yùn)輸線路的運(yùn)輸能力有一定限制時(shí)，這時(shí)要在線性規(guī)劃模型的約束條件上加上運(yùn)輸能力限制的約束條件。當(dāng)生產(chǎn)總量不等于銷量總量，即產(chǎn)銷不平衡時(shí)，這時(shí)需要通過(guò)一個(gè)假想倉(cāng)庫(kù)或假想生產(chǎn)地來(lái)化成產(chǎn)銷平衡的問(wèn)題，具體做法在后面闡述。二、運(yùn)輸問(wèn)題的求解---表上作業(yè)法直接采用單純形法求解運(yùn)輸問(wèn)題明顯是不利的。好在運(yùn)輸問(wèn)題具有特殊的結(jié)構(gòu)，因此可以利用單純形法的原理提出一種直接在運(yùn)輸表上計(jì)算以求解產(chǎn)銷平衡運(yùn)輸問(wèn)題的簡(jiǎn)便方法--表上作業(yè)法。它大大簡(jiǎn)化了計(jì)算過(guò)程的求解方法計(jì)算

5、過(guò)程如下：Step1給出初始調(diào)運(yùn)方案（初始基可行解）。對(duì)于有m個(gè)產(chǎn)地n個(gè)銷地的產(chǎn)銷平衡的問(wèn)題，從其線性規(guī)劃的模型上可知其有m+n個(gè)約束方程，但由于產(chǎn)銷平衡，前m個(gè)約束方程之和等于后n個(gè)約束方程之和，所以其數(shù)學(xué)模型最多只有m+n-1個(gè)獨(dú)立的約束方程。實(shí)際上其正好是m+n-1個(gè)獨(dú)立的約束方程，也就是說(shuō)運(yùn)輸問(wèn)題的約束方程組系數(shù)矩陣的秩等于m+n-1，因此其基可行解中基變量的個(gè)數(shù)為m+n-1。表上作業(yè)法中找初始基可行解，就是在m×n產(chǎn)銷平衡表上找出m+n-1個(gè)數(shù)字格，其相應(yīng)的調(diào)運(yùn)量就是基變量，格子中所填寫(xiě)的值即為基變量的值。Step2判斷初始調(diào)運(yùn)

6、方案是否最優(yōu)求表中各空格（對(duì)應(yīng)于非基變量）的檢驗(yàn)數(shù)以判定當(dāng)前解是否最優(yōu)，若已是最優(yōu)解則停止計(jì)算；否則轉(zhuǎn)到下一步。Step3.調(diào)整確定入基變量與出基變量。從一個(gè)基可行解轉(zhuǎn)換成另一個(gè)"更好"的基可行解，即進(jìn)行方案調(diào)整。Step4重復(fù)2、3直至得到最優(yōu)解。三、例題某食品公司有三個(gè)生產(chǎn)面包的分廠A1，A2，A3，有四個(gè)銷售分公司B1，B2，B3，B4，其各分廠每日的產(chǎn)量、各分銷售公司每日的銷量以及各分廠到各分銷售公司的單位運(yùn)價(jià)如表3-2所示。問(wèn)該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品在滿足各銷點(diǎn)的需求量的前提下，總運(yùn)費(fèi)最少？Step1求初始調(diào)運(yùn)方案---最小元素法求

7、初始調(diào)運(yùn)方案，也就是求初始基可行解有3種方法(西北角法、最小元素法、伏格爾法)，在此只介紹最小元素法。該方法的基本思想是采用“優(yōu)先安排單位運(yùn)價(jià)最小的產(chǎn)地與銷地之間的運(yùn)輸業(yè)務(wù)”，用這個(gè)規(guī)則來(lái)確定初始基可行解。我們直接在運(yùn)輸表中的格子里填數(shù)表示基變量。為了把初始基可行解與運(yùn)價(jià)分開(kāi)，把運(yùn)價(jià)放在每一欄的右上角，每一欄的中間填上初始基可行解（調(diào)運(yùn)量）見(jiàn)表3-3。在表上找到單位運(yùn)價(jià)最小的開(kāi)始分配運(yùn)輸量，并使取盡可能大的值，即取min（4，3）3，把所在空格里填上3，然后把A2的產(chǎn)量改寫(xiě)為4-3=1，把B1的銷量改寫(xiě)為3-3=0，并把B1列劃去。在剩下

8、的3×3矩陣?yán)镎业竭\(yùn)價(jià)最小的變量，取min（1，5）=1，A2的產(chǎn)量改為1-1=0，B3的銷量改為5-1=4，并把A2行劃去。在剩下的矩陣?yán)镎业竭\(yùn)價(jià)最小的變量，取min（7，4）=4，A1的產(chǎn)