運(yùn)籌學(xué)運(yùn)輸問題表上作業(yè)法

1、運(yùn) 籌 學(xué),李細(xì)霞2013物流工程1班2014~2015學(xué)年第二學(xué)期,課程主要內(nèi)容,Transportation problem,3,第三章 運(yùn)輸問題,學(xué)習(xí)目標(biāo),主要內(nèi)容,思考,運(yùn)輸問題要解決什么？什么叫一個(gè)運(yùn)輸方案？什么叫一個(gè)最優(yōu)的運(yùn)輸方案？若用xij表示從Si到Dj的運(yùn)量，那么在產(chǎn)銷平衡的條件下，求總運(yùn)費(fèi)最小的方案。,問題描述,7,表格模型,,8,生產(chǎn)量：A1-7噸， A2-4噸， A3-9噸銷售量：B1-3噸，B

2、2-6噸，B3-5噸，B4-6噸,舉例,產(chǎn)銷平衡？,9,調(diào)運(yùn)示意圖,10,此問題是線性規(guī)劃問題嗎？,請(qǐng)建立此問題的模型,目標(biāo)？約束條件？,思考,11,二、建立模型,設(shè)：xij——第i產(chǎn)地到第j銷地之間的調(diào)運(yùn)量，則有,Min z = ? ? cij· xij,3,4,i=1,j=1,x11+x12+x13+x14=7,x11+x21+x31=3,xij?0,(i=1,2,┄,3；j=1,2,┄,4),,,產(chǎn)量限制,銷量限制,x2

3、1+x22+x23+x24=4,x31+x32+x33+x34=9,x12+x22+x32=6,x13+x23+x33=5,x14+x24+x34=6,可否用單純形法求解？,12,??ai=?bj,產(chǎn)銷平衡運(yùn)輸問題的一般表示,,13,調(diào)運(yùn)模型為：,,m×n個(gè)變量,m個(gè)約束,n個(gè)約束,共有m+n個(gè)約束條件？,,14,約束條件展開,15,約束條件的系數(shù)矩陣,有何特點(diǎn)？,16,1.變量數(shù)：m?n個(gè)2.約束方程數(shù)：m+n個(gè) 最大

4、獨(dú)立方程數(shù)：m+n-13.系數(shù)列向量結(jié)構(gòu)：,產(chǎn)銷平衡運(yùn)輸問題模型的特點(diǎn),Why?,0…1.1.0,17,,,定理,平衡條件下的運(yùn)輸問題一定有最優(yōu)解,唯一最優(yōu)解？無窮多最優(yōu)解？,18,基本可行解,檢驗(yàn)數(shù),基變換,用單純形法求解線性規(guī)劃問題的步驟,表上作業(yè)法,19,單純形法在求解運(yùn)輸問題時(shí)的一種簡(jiǎn)化方法,,20,1.西北角法 2.最小元素法3.伏格爾法,,1.閉回路法2.位勢(shì)法,,閉回路法,,表上作業(yè)法步驟,舉例,,,

5、,產(chǎn)量,,,,,產(chǎn)地,銷地,A1 A2 A3,B1 B2 B3 B4,銷量,4,1,3,10,2,5,3 6 5 6,7 4 9,3,11,9,8,7,10,運(yùn)價(jià),總產(chǎn)=總銷,22,23,西北角法,3,4,2,2,3,6,有何疑問？,24,西北角法的優(yōu)劣？,太簡(jiǎn)單咯！,最優(yōu)解有點(diǎn)望塵莫及呢,25,幾點(diǎn)疑問,為什么要從西北角開始？,為什么每次填數(shù)一定要填最大允許量，然后劃掉一行（或一列）？,為什么有數(shù)

6、格只有6個(gè)？（總共有12個(gè)格）,26,基本可行解,一個(gè)基本可行解：有m+n-1個(gè)基變量（有數(shù)格），其余為非基變量（空格）,m+n-1個(gè)變量不能構(gòu)成閉回路,充要條件,運(yùn)輸問題的m+n個(gè)約束方程中，有且只有m+n-1個(gè)有效方程,舉例,下面這些有數(shù)格組成了閉回路（不能作為基本可行解）,什么是閉回路？,下面這些有數(shù)格沒有組成閉回路（可以作為基本可行解）,29,幾點(diǎn)疑問的解答,為什么要從西北角開始？,為什么每次填數(shù)一定要填最大允許量，然后劃掉一

7、行（或一列）,為什么有數(shù)格只有6個(gè)？（總共有12個(gè)格）,m+n-1個(gè)變量不能構(gòu)成閉回路,只有6個(gè)有數(shù)格,基變量的個(gè)數(shù)為m+n-1（3+4-1）,,,,30,所有問題答案歸結(jié)一句話：保證初始方案是運(yùn)輸問題（線性規(guī)劃問題）的基本可行解,Why？隨便一個(gè)可行解不行么？,31,最小元素法,3,11,3,10,1,9,2,8,7,4,10,5,3,1,4,6,3,3,32,最小元素法的優(yōu)劣？,也很簡(jiǎn)單哦,最優(yōu)解可望，但還是有一定距離的,33,伏

8、格爾法,34,,,,,,,產(chǎn)地,銷地,A1 A2 A3,B1 B2 B3 B4,行差額,列差額,3 11 3 10 1 9 2 8 7 4 10 5,0 1 1,2 5 1 3,,0 1 2,2 - 1 3,,0 1 -,2 - 1 2,,7 6 -,- - 1 2,,,Vogel法:,,,,,,,,產(chǎn)地,銷地,A1 A2 A3,B1 B2

9、B3 B4,7 4 9,產(chǎn)量,銷量,3 6 5 6,6,3,5,2,1,3,產(chǎn)銷平衡表,單位運(yùn)價(jià)表,伏格爾法（差額法）,對(duì)最小元素法的改進(jìn),35,伏格爾法的優(yōu)劣？,離最優(yōu)解貌似很近了哦,求解過程有點(diǎn)麻煩呢！,用Vogel法求出的初始解叫做“近似最優(yōu)解”,36,課堂練習(xí)：用最小元素法求初始解,37,只有5個(gè)有數(shù)格，不是基本可行解嗎？,5,3,4,1,7,課堂練習(xí)答案,38,應(yīng)用舉例：用最小元素法或伏格爾法求初始解,,“總

10、利潤(rùn)最大”而不是“運(yùn)費(fèi)最小”，“最小元素”怎么找？,39,最優(yōu)性檢驗(yàn)——閉回路法,表示什么？,每個(gè)空格都能找到閉回路嗎？有的話，是否唯一？,每個(gè)空格有且只有一條閉回路！,46,如何判斷初始方案是否達(dá)到最優(yōu)？,若存在某些檢驗(yàn)數(shù)小于0，則說明調(diào)整后運(yùn)價(jià)將減少。（不是最優(yōu)解） 若存在某些檢驗(yàn)數(shù)等于0，則說明調(diào)整后運(yùn)價(jià)將不發(fā)生改變。（多個(gè)最優(yōu)解）若所有檢驗(yàn)數(shù)大于0，說明調(diào)整后運(yùn)價(jià)將增加。（唯一最優(yōu)解）,最優(yōu)方案：所有檢驗(yàn)數(shù)≥0,注意是目標(biāo)最

11、小化的問題,思考,如果將運(yùn)輸問題的運(yùn)價(jià)表改為利潤(rùn)表，則應(yīng)如果求初始方案，如何判斷方案是否最優(yōu)？,48,最優(yōu)性檢驗(yàn)——位勢(shì)法（對(duì)偶變量法）,設(shè) U1,U2,…Um,V1, V2,…, Vn 是對(duì)應(yīng)m+n個(gè)約束條件的對(duì)偶變量其中Ui對(duì)應(yīng)第i個(gè)產(chǎn)地的產(chǎn)量約束， Vj對(duì)應(yīng)第j個(gè)銷地的銷量約束稱Ui為行位勢(shì)， Vj為列位勢(shì),49,2. 令u1=0，則依cij=ui+vj 計(jì)算各ui和vj,3.計(jì)算空格處位勢(shì)；?ij=cij-（ui+vj）

12、,1.在表中增加一行一列,填上行位勢(shì)ui,列位勢(shì)vj, 在對(duì)應(yīng)初始方案有數(shù)格處寫0（基變量檢驗(yàn)數(shù)為0）；,位勢(shì)法的圖表形式:,,,,ui,,,,,產(chǎn)地,銷地,A1 A2A3,B1 B2 B3 B4,vj,,u3=-5,3,11,3,10,1,9,2,8,7,4,10,5,0,0,0,0,0,0,v3=3,v4=10,u1=0,u2=-1,v1=2,v2=9,1,2,1,-1,10,12,50,,,位勢(shì)法計(jì)算非基

13、變量xij檢驗(yàn)數(shù)的公式 σij=cij-（ui+vj）,比較檢驗(yàn)數(shù)計(jì)算的兩種方法,51,52,三、方案改進(jìn)（閉回路法）當(dāng)至少有一個(gè)非基變量的檢驗(yàn)數(shù)是負(fù)值時(shí)，說明作業(yè)表上當(dāng)前的調(diào)運(yùn)方案不是最優(yōu)的，應(yīng)進(jìn)行調(diào)整。 步驟：1.若檢驗(yàn)數(shù)σij小于零，則首先在作業(yè)表上以xij為起始變量作出閉回路，并求出調(diào)整量θ,若有多個(gè)檢驗(yàn)數(shù)小于零，則取其中最小的負(fù)數(shù),53,繼續(xù)上例，因σ24= -1 ，畫出以x24為起始變量的閉回路,54,

14、,?計(jì)算調(diào)整量： θ =Min（3，1）=12. 按照下面的方法調(diào)整調(diào)運(yùn)量： 閉回路上，奇數(shù)次頂點(diǎn)的調(diào)運(yùn)量減去θ ，偶數(shù)次頂點(diǎn)（包括起始頂點(diǎn)）的調(diào)運(yùn)量加上θ ；閉回路之外的變量調(diào)運(yùn)量不變。,55,3. 得到調(diào)整后的調(diào)運(yùn)方案：,4.計(jì)算新方案的檢驗(yàn)數(shù)，重復(fù)上述步驟，直至所有檢驗(yàn)數(shù)都 ≥0，即得到最優(yōu)方案。,56,最優(yōu)調(diào)運(yùn)方案,,相應(yīng)的最小總運(yùn)費(fèi)為：,運(yùn)輸問題的應(yīng)用,產(chǎn)銷不平衡問題生產(chǎn)與存儲(chǔ)問題轉(zhuǎn)運(yùn)問題,,由于在變量個(gè)數(shù)相等

15、的情況下，表上作業(yè)法的計(jì)算遠(yuǎn)比單純形法簡(jiǎn)單得多。所以在解決實(shí)際問題時(shí)，人們常常盡可能把某些線性規(guī)劃的問題化為運(yùn)輸問題的數(shù)學(xué)模型。下面介紹幾個(gè)典型的例子。,設(shè)有三個(gè)化肥廠(A，B，C)供應(yīng)四個(gè)地區(qū)(Ⅰ，Ⅱ，Ⅲ，Ⅳ)的農(nóng)用化肥。各化肥廠年產(chǎn)量，各地區(qū)年需要量及從各化肥廠到各地區(qū)運(yùn)送單位化肥的運(yùn)價(jià)如下表所示。試求出總的運(yùn)費(fèi)最節(jié)省的化肥調(diào)撥方案。,產(chǎn)銷不平衡問題,,,,這是一個(gè)產(chǎn)銷不平衡的運(yùn)輸問題，總產(chǎn)量為160萬噸，四個(gè)地區(qū)的最低需求為110

16、萬噸，最高需求為無限。根據(jù)現(xiàn)有產(chǎn)量，第Ⅳ個(gè)地區(qū)每年最多能分配到60萬噸，這樣最高需求為210萬噸，大于產(chǎn)量。為了求得平衡，在產(chǎn)銷平衡表中增加一個(gè)假想的化肥廠D，其年產(chǎn)量為50萬噸。由于各地區(qū)的需要量包含兩部分，如地區(qū)Ⅰ，其中30萬噸是最低需求，故不能由假想化肥廠D供給，令相應(yīng)運(yùn)價(jià)為M(任意大正數(shù))，而另一部分20萬噸滿足或不滿足均可以，因此可以由假想化肥廠D供給，按前面講的，令相應(yīng)運(yùn)價(jià)為0。對(duì)凡是需求分兩種情況的地區(qū)，實(shí)際上可按照兩個(gè)地

17、區(qū)看待。這樣可以寫出這個(gè)問題的產(chǎn)銷平衡表和單位運(yùn)價(jià)表。,產(chǎn)銷平衡表,單位運(yùn)價(jià)表,根據(jù)表上作業(yè)法計(jì)算，可以求得這個(gè)問題的最優(yōu)方案,請(qǐng)簡(jiǎn)單描述此方案,生產(chǎn)與儲(chǔ)存問題,某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供10，15，25，20臺(tái)同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如表所示。又如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨的，每臺(tái)每積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi)用0.15萬元。要求在完成合同的情況下，作出使該廠全年生產(chǎn)費(fèi)用(包括儲(chǔ)

18、存、維護(hù)費(fèi)用) 最小的方案。,解：由于每個(gè)季度生產(chǎn)出來的柴油機(jī)不一定當(dāng)季交貨，所以設(shè)xij為第i季度生產(chǎn)的用于第j季度交貨的柴油機(jī)數(shù)。根據(jù)合同要求，必須滿足,又每季度生產(chǎn)的用于當(dāng)季和以后各季交貨的柴油機(jī)數(shù)不可能超過該季度的生產(chǎn)能力，故又有：,第i季度生產(chǎn)的用于j季度交貨的每臺(tái)柴油機(jī)的實(shí)際成本cij應(yīng)該是該季度單位成本加上儲(chǔ)存、維護(hù)等費(fèi)用。cij的具體數(shù)值見下表：,設(shè)用ai表示該廠第i季度的生產(chǎn)能力，bj表示第i季度的合同供應(yīng)量，則問題可

19、寫成：,目標(biāo)函數(shù)：約束條件：,顯然，這是一個(gè)產(chǎn)大于銷的運(yùn)輸問題模型。注意到這個(gè)問題中當(dāng)i＞j時(shí)，xij=0，所以應(yīng)令對(duì)應(yīng)的cij=M，再加上一個(gè)假想的需求D，就可以把這個(gè)問題變成產(chǎn)銷平衡的運(yùn)輸模型，并寫出產(chǎn)銷平衡表和單位運(yùn)價(jià)表(合在一起，見下表)。,經(jīng)用表上作業(yè)法求解，可得多個(gè)最優(yōu)方案，下表是最優(yōu)方案之一。,即第Ⅰ季度生產(chǎn)25臺(tái)，10臺(tái)當(dāng)季交貨，15臺(tái)Ⅱ季度交貨；Ⅱ季度生產(chǎn)5臺(tái)，用于Ⅲ季度交貨；Ⅲ季度生產(chǎn)30臺(tái)，其中20臺(tái)于當(dāng)季交貨

20、，10臺(tái)于Ⅳ季度交貨。Ⅳ季度生產(chǎn)10臺(tái)，于當(dāng)季交貨。按此方案生產(chǎn)，該廠總的生產(chǎn)費(fèi)用(包括儲(chǔ)存、維護(hù)費(fèi)用)為773萬元。,轉(zhuǎn)運(yùn)問題,①每個(gè)產(chǎn)地的產(chǎn)品不一定直接發(fā)運(yùn)到銷售點(diǎn)，可以將其中幾個(gè)產(chǎn)地集中一起運(yùn)；②運(yùn)往各銷地的產(chǎn)品可以先運(yùn)給其中幾個(gè)銷地，再轉(zhuǎn)運(yùn)給其他銷地；③除產(chǎn)、銷地之外，中間還可以有幾個(gè)轉(zhuǎn)運(yùn)站，在產(chǎn)地之間、銷地之間或產(chǎn)地與銷地間進(jìn)行轉(zhuǎn)運(yùn)。,71,產(chǎn)地：原產(chǎn)地、中間轉(zhuǎn)運(yùn)站、轉(zhuǎn)運(yùn)物資的銷地銷地：原銷地、中間轉(zhuǎn)運(yùn)站、轉(zhuǎn)運(yùn)物資的產(chǎn)地

21、如果是產(chǎn)銷不平衡問題，先通過增加虛擬的產(chǎn)地或銷地轉(zhuǎn)化為產(chǎn)銷平衡問題。設(shè)各轉(zhuǎn)運(yùn)站轉(zhuǎn)運(yùn)物資的數(shù)量均為總產(chǎn)量∑ ai（或總銷量∑ bj ）專職轉(zhuǎn)運(yùn)站的產(chǎn)量和銷量均為∑ ai原產(chǎn)地Ai的產(chǎn)量均為（ai+∑ ai）原銷地Bj的銷量均為（ bj+∑ ai）將各條線路實(shí)際的運(yùn)輸單價(jià)列成單位運(yùn)價(jià)表，其中不可能的運(yùn)輸其單位運(yùn)價(jià)用M表示。,擴(kuò)展運(yùn)輸表的構(gòu)建步驟,舉例：A、B兩個(gè)化肥廠每年各生產(chǎn)磷肥900萬噸和600萬噸，這些化肥要運(yùn)到三個(gè)港口

22、，已知三個(gè)港口C、D、E每年能承擔(dān)的船運(yùn)量分別為700、400、300萬噸，兩個(gè)工廠及三個(gè)港口之間單位運(yùn)價(jià)如下表所示，為按需要把磷肥運(yùn)到各港口，怎樣安排運(yùn)輸才能使運(yùn)費(fèi)最少？,73,表1,表2,表3,產(chǎn)銷平衡運(yùn)輸表的構(gòu)建,F,發(fā)量,收量,900+1500=2400,600+1500=2100,1500,1500,1500,1500,1500,700+1500=2200,400+1500=1900,300+1500=1800,100,0,0

23、,0,0,0,將表2和表3合并為一張表（加上單位運(yùn)價(jià)）,例：已知各產(chǎn)地、銷地、中間轉(zhuǎn)運(yùn)站及相互之間每噸產(chǎn)品的運(yùn)價(jià)如表所示，問在考慮到產(chǎn)銷地之間直接運(yùn)輸和非直接運(yùn)輸?shù)母鞣N可能方案的情況下，如何將三個(gè)廠每天生產(chǎn)的產(chǎn)品運(yùn)往銷售地，使總的運(yùn)費(fèi)最少。,(1) 由于問題中所有產(chǎn)地、中間轉(zhuǎn)運(yùn)站、銷地都可以看作產(chǎn)地，又可看作銷地。因此把整個(gè)問題當(dāng)作有11個(gè)產(chǎn)地和11個(gè)銷地的擴(kuò)大的運(yùn)輸問題。(2) 對(duì)擴(kuò)大的運(yùn)輸問題建立單位運(yùn)價(jià)表。方法將表中不可能的運(yùn)輸

24、方案的運(yùn)價(jià)用任意大的正數(shù)M代替。,(3) 所有中間轉(zhuǎn)運(yùn)站的產(chǎn)量等于銷量。由于運(yùn)費(fèi)最少時(shí)不可能出現(xiàn)一批物資來回倒運(yùn)的現(xiàn)象，所以每個(gè)轉(zhuǎn)運(yùn)站的轉(zhuǎn)運(yùn)數(shù)不超過20噸。可以規(guī)定T1，T2，T3，T4的產(chǎn)量和銷量均為20噸。由于實(shí)際的轉(zhuǎn)運(yùn)量,可以在每個(gè)約束條件中增加一個(gè)松弛變量xii，xii相當(dāng)于一個(gè)虛構(gòu)的轉(zhuǎn)運(yùn)站，意義就是自己運(yùn)給自己。(20-xii)就是每個(gè)轉(zhuǎn)運(yùn)站的實(shí)際轉(zhuǎn)運(yùn)量，xii的對(duì)應(yīng)運(yùn)價(jià)cii=0。,(4) 擴(kuò)大的運(yùn)輸問題中原來的產(chǎn)地與銷地

25、因?yàn)橐灿修D(zhuǎn)運(yùn)站的作用，所以同樣在原來產(chǎn)量與銷量的數(shù)字上加20噸，即三個(gè)廠每天糖果產(chǎn)量改成27，24，29噸，銷量均為20噸；四個(gè)銷售點(diǎn)的每天銷量改為23，26，25，26噸，產(chǎn)量均為20噸，同時(shí)引進(jìn)xii作為松弛變量。,下面寫出擴(kuò)大運(yùn)輸問題的產(chǎn)銷平衡表與單位運(yùn)價(jià)表，由于這是一個(gè)產(chǎn)銷平衡的運(yùn)輸問題，所以可以用表上作業(yè)法求解(計(jì)算略),帶有約束的運(yùn)輸問題及推廣應(yīng)用,在某軍供點(diǎn)B1處有10車物資，4車運(yùn)往A1點(diǎn)，6車運(yùn)往A2點(diǎn)；在B2處有2車

26、物資運(yùn)往A3點(diǎn)；在B3處有3車物資運(yùn)往A4點(diǎn)。車隊(duì)只有兩輛卡車、兩輛加載車可供使用，空車送貨前集中在A0處, 并要求: 1) B2處兩車特種物資需要提前用加載車運(yùn)往A3點(diǎn)；2)送完所有物資后，所有車輛返回到A0點(diǎn)。問如何運(yùn)輸，才能使空車行駛里程最少？已知各供需點(diǎn)間的距離如表所示。,某航運(yùn)公司承擔(dān)六個(gè)港口城市A、B、C、D、E、F的四條固定航線的物資運(yùn)輸任務(wù)。已知各條航線的起點(diǎn)、終點(diǎn)城市及每天航班數(shù)見下表。,,假定各條航線使用相同型號(hào)的船

27、只，又各城市間的航程天數(shù)見下表：,又知每條船只每次裝卸貨的時(shí)間各需1天，則該航運(yùn)公司至少應(yīng)配備多少條船，才能滿足所有航線的運(yùn)貨需求?,解 該公司所需配備船只分兩部分。(1) 載貨航程需要的周轉(zhuǎn)船只數(shù)。例如航線1，在港口E裝貨1天，E→D航程17天，在D卸貨1天，總計(jì)19天。每天3航班，故該航線周轉(zhuǎn)船只需57條。各條航線周轉(zhuǎn)所需船只數(shù)見表。,以上累計(jì)共需周轉(zhuǎn)船只數(shù)91條 .,(2) 各港口間調(diào)度所需船只數(shù)。有些港口每天到達(dá)船數(shù)多于需要

28、船數(shù)，例如港口D，每天到達(dá)3條，需求1條；而有些港口到達(dá)數(shù)少于需求數(shù)，例如港口B。各港口每天余缺船只數(shù)的計(jì)算見表。,為使配備船只數(shù)最少，應(yīng)做到周轉(zhuǎn)的空船數(shù)為最少。因此建立以下運(yùn)輸問題，其產(chǎn)銷平衡表見表。,單位運(yùn)價(jià)表應(yīng)為相應(yīng)各港口之間的船只航程天數(shù)，見表。,用表上作業(yè)法求出空船的最優(yōu)調(diào)度方案,由表3-39知最少需周轉(zhuǎn)的空船數(shù)為2×1+13×1+5×1+17×1+3×1=40條。