管理運(yùn)籌學(xué)-第三章運(yùn)輸問(wèn)題_第1頁(yè)
已閱讀1頁(yè),還剩49頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、第三章 運(yùn)輸問(wèn)題,北京物資學(xué)院信息學(xué)院2017年4月,北京物資學(xué)院運(yùn)籌學(xué)教學(xué)課件,本章主要內(nèi)容,第一節(jié) 運(yùn)輸問(wèn)題的數(shù)學(xué)模型及其特征第二節(jié) 運(yùn)輸問(wèn)題的求解—表上作業(yè)法第三節(jié) 產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及應(yīng)用,第一節(jié) 運(yùn)輸問(wèn)題的數(shù)學(xué)模型及其特征,運(yùn)輸問(wèn)題的定義 運(yùn)輸問(wèn)題的數(shù)學(xué)模型 運(yùn)輸問(wèn)題的特征,,1. 運(yùn)輸問(wèn)題的定義,例1: 某集團(tuán)新購(gòu)進(jìn)一批鋼材,分別存儲(chǔ)在三個(gè)倉(cāng)庫(kù),現(xiàn)在要將這批鋼材運(yùn)到分布在各地的四個(gè)工廠。各倉(cāng)庫(kù)的庫(kù)存量、各工廠的

2、需求量以及從各倉(cāng)庫(kù)往各個(gè)工廠每運(yùn)送一噸鋼材所需的費(fèi)用見(jiàn)下表,問(wèn)如何調(diào)運(yùn)才能使總運(yùn)費(fèi)降到最低?,運(yùn)輸問(wèn)題:有m個(gè)供應(yīng)點(diǎn)向n個(gè)需求點(diǎn)供應(yīng)某種物資,這m個(gè)供應(yīng)點(diǎn)A1、A2、…...Am的供應(yīng)量分別為a1、a2、…...am;n個(gè)需求點(diǎn)B1、B2、…...Bn的需求量分別為b1、b2、…...bn;已知從任一供應(yīng)點(diǎn)Ai向任一需求點(diǎn)Bj運(yùn)輸一個(gè)單位物資的費(fèi)用為cij。問(wèn)采取什么樣的物資調(diào)運(yùn)方案才能使總運(yùn)費(fèi)最???,,,2. 運(yùn)輸問(wèn)題的數(shù)學(xué)模型,,,

3、,運(yùn)輸問(wèn)題的約束方程組系數(shù)矩陣及特征,矩陣A是一個(gè)m+n行mn列的矩陣,它的秩為m+n-1。運(yùn)輸問(wèn)題應(yīng)該有m+n-1個(gè)基變量。系數(shù)矩陣非常稀疏。 xij的系數(shù)列向量為:,,3. 運(yùn)輸問(wèn)題的特征,特征1:運(yùn)輸問(wèn)題一定有可行解;特征2:運(yùn)輸問(wèn)題一定有最優(yōu)解;特征3:運(yùn)輸問(wèn)題每一組基對(duì)應(yīng) m+n-1個(gè)基變量;特征4:運(yùn)輸問(wèn)題的 m+n-1個(gè)基變量構(gòu)成的變量組不含閉回路;特征5:任意一個(gè)非基變量和 m+n-1個(gè)基變量組成的變量組中

4、必定存在一條并且只存在唯一一條閉回路; 特征6:如果運(yùn)輸問(wèn)題中的供應(yīng)量和需求量都是整數(shù),則任一基解中各變量的取值也都是整數(shù)。,,閉回路,,定義:凡是能夠排列成下列序列的一組變量的集合就稱為運(yùn)輸問(wèn)題的一個(gè)閉回路。,并稱集合中每一個(gè)變量為此閉回路的一個(gè)頂點(diǎn);稱連接相鄰兩個(gè)變量(頂點(diǎn))以及連接最后一個(gè)頂點(diǎn)和第一個(gè)頂點(diǎn)的線段為此閉回路的邊。,或,X45,,X41,,X31,,X33,,X13,,X15,,X34,,X32,,,X14,,X12

5、,X35,,X41,X31,,X43,,X13,,X15,,,X11,,X12,,X22,,X24,,X44,,X42,X21,(1)每個(gè)頂點(diǎn)都是轉(zhuǎn)折點(diǎn);(2)閉回路是一條閉合的折線,每一條邊都是水平或垂直的;(3)閉回路上同一行(列)的頂點(diǎn)有偶數(shù)個(gè)。,,,閉回路上的點(diǎn)對(duì)應(yīng)的系數(shù)列向量線性相關(guān)。,,,Pij,,,,,Pik,Plk,Pls,Pus,Puj,由于,容易證明,,第二節(jié) 運(yùn)輸問(wèn)題的求解--表上作業(yè)法,第四步:確定進(jìn)基變量和

6、出基變量,調(diào)整非最優(yōu)的調(diào)運(yùn)方案,獲得更好的調(diào)運(yùn)方案;轉(zhuǎn)第二步。,表上作業(yè)法的基本步驟:,第一步:編制初始調(diào)運(yùn)方案,即尋找第一個(gè)基可行解;,第二步:計(jì)算各非基變量的檢驗(yàn)數(shù);,,第三步:判斷當(dāng)前的調(diào)運(yùn)方案是否是最優(yōu)方案,如果已經(jīng)是最優(yōu),則算法結(jié)束,問(wèn)題已經(jīng)解決;否則,轉(zhuǎn)第四步;,,第一步:編制初始調(diào)運(yùn)方案,要求得運(yùn)輸問(wèn)題的初始基可行解,必須保證找到 m+n–1 個(gè)基變量.,運(yùn)輸問(wèn)題的任意m+n-1個(gè)變量構(gòu)成一組基變量的充要條件是變量組中不含

7、閉回路.關(guān)鍵:找出m+n-1個(gè)不含閉回路的變量。,西北角法(左上角法)最小元素法Vogel 法,問(wèn)題:如何使得一個(gè)選定的變量不包含在閉回路中?,對(duì)應(yīng)的總運(yùn)費(fèi)為 z 1= 2×3 + 9×6 + 3×2 + 4×3 + 2×1 + 5×6 = 110,,,,,,,西北角法(左上角法),,最小元素法,對(duì)應(yīng)的總運(yùn)費(fèi)為 z 2= 9×5 + 7×4 +

8、 1×3 + 2×2 + 4×3 + 2×4 = 100,,,,,,,,,Vogel 法,對(duì)應(yīng)的總運(yùn)費(fèi)為 z 3= 2×3 + 9×5 + 7×1 + 2×5 + 4×3 + 2×4 =88,,,,,,,,,,,,,,退化情況的處理,用西北角法求下列運(yùn)輸問(wèn)題的第一個(gè)基可行解,,,,,,注意:每次只能劃去一行或一列,不能同時(shí)劃去行和列。

9、當(dāng)只剩下一行(列)時(shí),只能劃去列(行)。想一想:為什么?,,用最小元素法求下列運(yùn)輸問(wèn)題的第一個(gè)基可行解,第二步:計(jì)算各非基變量的檢驗(yàn)數(shù),1. 閉回路法;2. 位勢(shì)法。,檢驗(yàn)數(shù)的定義:非基變量的取值每增加1時(shí),總運(yùn)費(fèi)的 增加量。運(yùn)輸問(wèn)題的最優(yōu)性條件:檢驗(yàn)數(shù)非負(fù),1. 閉回路法,,基變量不含閉回路,但任何一個(gè)非基變量都可以與基變量構(gòu)成唯一一條閉回路,,,,,,,含義:x14 每增加一個(gè)單位,總運(yùn)費(fèi)增加-6個(gè)單位,+1,+1,+

10、1,-1,-1,-1,所有非基變量的檢驗(yàn)數(shù)見(jiàn)上表,,2. 位勢(shì)法,位勢(shì):運(yùn)輸問(wèn)題的對(duì)偶變量稱為位勢(shì)。因?yàn)閙個(gè)供應(yīng)點(diǎn)n個(gè)需求點(diǎn)的運(yùn)輸問(wèn)題有m+n個(gè)約束,因此運(yùn)輸問(wèn)題就有m+n個(gè)位勢(shì)。,,行位勢(shì):關(guān)于供應(yīng)點(diǎn)Ai的約束對(duì)應(yīng)的對(duì)偶變量,記為 ui, i=1,2,…m。列位勢(shì):關(guān)于需求點(diǎn)Bj的約束對(duì)應(yīng)的對(duì)偶變量,記為vj, j = 1,2,…,n。,定理:運(yùn)輸問(wèn)題變量xij的檢驗(yàn)數(shù),證明:,位勢(shì)及檢驗(yàn)數(shù)的求法,由于基變量的檢驗(yàn)

11、數(shù)為0,所以可以利用m+n-1 個(gè)基變量求出位勢(shì),,,0,2,9,-6,10,-8,13,0,-6,,5,-5,14,3,第四步:調(diào)整調(diào)運(yùn)方案,1. 確定進(jìn)基變量:選取最小負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量進(jìn)基,2. 確定出基變量和調(diào)整量,將進(jìn)基變量對(duì)應(yīng)的閉回路中的頂點(diǎn)分為奇頂點(diǎn)和偶頂點(diǎn),令θ= min{ 閉回路上所有偶頂點(diǎn)對(duì)應(yīng)的運(yùn)量xij } 則θ即為調(diào)整量,選取一個(gè)運(yùn)量等于θ的偶頂點(diǎn)為出基變量。,3.調(diào)整:閉回路上奇頂點(diǎn)上的運(yùn)量增加θ,偶頂點(diǎn)

12、上的運(yùn)量減少θ。閉回路以外頂點(diǎn)的運(yùn)量不變。,上例中:若選x14進(jìn)基,則?=min{6,3,6}=3, 出基變量為x23,調(diào)整后得:,,,,,,,總運(yùn)費(fèi): z= 2×3 + 9×3 + 7×3 + 3×5 + 2×4 + 5×3 = 92 < 110,,x32進(jìn)基,則?=min{3,3}=3, 出基變量選x34,調(diào)整后得:,0,-6,-2,2,9,4,7,5,6,6,1,

13、8,-3,,,,,檢驗(yàn)數(shù)全部非負(fù),已經(jīng)是最優(yōu)調(diào)運(yùn)方案;總費(fèi)用z*= 2×3 + 9×0 + 7×6 + 3×5 + 4×3 + 2×4 = 83,0,-6,-5,2,9,7,7,3,5,3,1,11,3,表上作業(yè)法計(jì)算中應(yīng)注意的問(wèn)題,1.解的情況 唯一:非基變量檢驗(yàn)數(shù)全部大于0; 無(wú)窮多解:至少存在一個(gè)非基變量檢驗(yàn)數(shù)等于0。,2.退化情況:在確定初始基可行解的時(shí)

14、候,當(dāng)填(i,j)格子時(shí),若ai=bj, 則xij=ai=bj, 但此時(shí)只能劃去一行或一列,在后面的填充過(guò)程中相應(yīng)格子要填0。,3.調(diào)整時(shí),若閉回路上出現(xiàn)兩個(gè)或兩個(gè)以上偶頂點(diǎn)取值同時(shí)達(dá)到最小,只能選一個(gè)變量出基。,課堂練習(xí)用表上作業(yè)法求解下列運(yùn)輸問(wèn)題.,,,,,,,0,3,10,-1,2,-5,9,1,2,1,-1,10,12,,,,,調(diào)整量為 min{3,1}=1,出基變量為x23.,最優(yōu)解:,0,3,10,-2,3,-5,9,0,

15、2,2,1,9,12,由于x11的檢驗(yàn)數(shù)為0,所以最優(yōu)解不唯一。,,,,,0,3,10,-2,3,-5,9,2,2,1,9,12,0,最優(yōu)解:,,第三節(jié) 產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及應(yīng)用,表上作業(yè)法是以產(chǎn)銷平衡為前提的:,實(shí)際中,往往遇到產(chǎn)銷不平衡的運(yùn)輸問(wèn)題,1.產(chǎn)大于銷(供過(guò)于求),2.銷大于產(chǎn)(供不應(yīng)求),產(chǎn)銷不平衡運(yùn)輸問(wèn)題向產(chǎn)銷平衡運(yùn)輸問(wèn)題的轉(zhuǎn)化,產(chǎn)大于銷的運(yùn)輸問(wèn)題:,數(shù)學(xué)模型,設(shè)xi n+1 是產(chǎn)地Ai 的儲(chǔ)存量,化成標(biāo)準(zhǔn)形,其中

16、,引入一個(gè)虛擬的銷地(需求量等于 ),并令各個(gè)產(chǎn)地到虛擬銷地的單位運(yùn)費(fèi)為0。,產(chǎn)小于銷的運(yùn)輸問(wèn)題:,引入一個(gè)虛擬的產(chǎn)地(產(chǎn)量等于 ),并令該虛擬產(chǎn)地到各銷地的單位運(yùn)費(fèi)為0。,總供應(yīng)量為19千噸,而總需求量為15千噸,例2: A1、A2、A3三個(gè)蔬菜生產(chǎn)地生產(chǎn)的蔬菜主要供應(yīng)B1、B2、B3、B4四個(gè)城市。已知三個(gè)產(chǎn)地今年的蔬菜產(chǎn)量預(yù)計(jì)分別為7千噸、5千噸和7千噸;四個(gè)城市今年的蔬菜需求量分別為

17、2千噸、3千噸、4千噸和6千噸;從每個(gè)蔬菜產(chǎn)地平均運(yùn)輸1千噸蔬菜到各個(gè)城市的單位費(fèi)用(萬(wàn)元)見(jiàn)下表,你能否替他們編制一個(gè)總運(yùn)費(fèi)最省的蔬菜調(diào)運(yùn)方案?,0,0,-2,2,0,4,3,0,8,2,5,7,2,3,8,7,最優(yōu)解中x15=2, x25=2,表示兩個(gè)產(chǎn)地沒(méi)有運(yùn)出去的蔬菜量。,假如例2中各產(chǎn)地的蔬菜總產(chǎn)量不是19千噸,而是12千噸,就成了一個(gè)供不應(yīng)求的運(yùn)輸問(wèn)題。,引入一個(gè)虛擬產(chǎn)地,例3 設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的農(nóng)用化肥。假定等量

18、的化肥在這些地區(qū)使用效果相同,已知各化肥廠年產(chǎn)量,各地區(qū)年需要量及從各個(gè)化肥廠到各地區(qū)單位化肥的運(yùn)價(jià)如下表所示,試決定使總運(yùn)費(fèi)最省的化肥調(diào)撥方案。,這是一個(gè)產(chǎn)銷不平衡的運(yùn)輸問(wèn)題,總產(chǎn)量160萬(wàn)噸,四個(gè)地區(qū)的最低需求量為110萬(wàn)噸,最高需求為無(wú)限。根據(jù)現(xiàn)有產(chǎn)量,第四個(gè)地區(qū)每年最多能分配到60萬(wàn)噸,這樣最高需求為210萬(wàn)噸,大于總產(chǎn)量。為了求得平衡,在產(chǎn)銷平衡表中增加一個(gè)假想的化肥廠D,其產(chǎn)量為50萬(wàn)噸。由于各個(gè)地區(qū)的需求量包含兩部分,其中

19、最低需求量不能由假想的化肥廠D供應(yīng),令運(yùn)價(jià)為M,而另一部分滿足或不滿足均可以,故也可以由假想的化肥廠供應(yīng),令相應(yīng)運(yùn)價(jià)為0。把需求是兩種情況的看成兩個(gè)地區(qū),得到這個(gè)問(wèn)題的產(chǎn)銷平衡表。,根據(jù)表上作業(yè)法可以求得這個(gè)問(wèn)題的最優(yōu)方案,,,,,,,,,,運(yùn)輸問(wèn)題的求解軟件(WINQSB),進(jìn)入WINQSB選擇Network Modeling模塊選取Transportation Problem;輸入問(wèn)題名稱、產(chǎn)地?cái)?shù)目、銷地?cái)?shù)目、選擇目標(biāo)函數(shù)類型,數(shù)

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論