管理運籌學--運輸問題

1、管理運籌學管理運籌學華國偉華國偉Email:北京交通大學經管學院物流管理系北京交通大學經管學院物流管理系第三章第三章 運輸問題運輸問題 Transportation Problem本節(jié)內容提要本節(jié)內容提要3.1 運輸問題的數學模運輸問題的數學模 3.2 表上作業(yè)法表上作業(yè)法3.1 運輸問題的數學模型運輸問題的數學模型1aiama1bjbnb11c1jc1 icijcincmncmjc1mc1nc例：某運輸問題的資料如下：例：某運輸問題的資料如下：單位 銷地 運價產地產量2910291342584257銷量38464321 BBBB321AAA一、運輸問題的數學模型一、運輸問題的數學模型 )4

2、. 3 . 2 . 1, 3 . 2 . 1(06483759524824371092min342414332313322212312111343332312423222114131211343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZxijij 約約束束條條件件：目目標標函函數數：為為運運量量設設 數學模型的一般形式數學模型的一般形式 已知資料如下：已知資料如下：單 銷 產 量產地產量銷 量nBB 11 mAAmaa 1nbb 1mnmncccc 1111運運價價nijjm1iiba供需平衡供需平衡 ) ( 0m

3、in11ijjijijiijminjijijxbabxaxxcZ當產銷平衡時，其模型如下：當產銷平衡時，其模型如下：Ai的產品全部的產品全部供應出去供應出去Bj的需求全的需求全部得到滿足部得到滿足產銷平衡的運輸問題必定存最優(yōu)解產銷平衡的運輸問題必定存最優(yōu)解.當產大于銷時，其模型是：當產大于銷時，其模型是： ) ( 0min11ijjijijiijminjijijxbabxaxxcZ當產小于銷時，其模型是：當產小于銷時，其模型是：0, 0, 0)(0min ijjijjiijjijiijijijcbabaxbxaxxcZ并假設：并假設： 1112121222nm1m2mn 1 1 1 1 1 1

4、 nx xx xxxxxx 1 1 11 1 1 1 1 1 1 1 1 mnijimjPee1mn 個基變量平衡表、運價表和二為一：平衡表、運價表和二為一：銷產B1B2Bn產量A1x11x12x1na1A2x21x22x2na2Amxm1xm2xmnam銷量b1b1bn約束條件或解可用產銷平衡表表示約束條件或解可用產銷平衡表表示: minjijijxczmin11 )n,j(bx)m,i (axmijijnjiij1 1 11 )n,j;m,i (xij11 0 uivj無約束無約束 （i=1,2, ,m;j=1,2, ,n)uivj設設u ui,v,vj為對偶變量，對偶問題模型為為對偶變量

5、，對偶問題模型為nijjjmiiivbuaw1maxijjicvum個個 n個個 特征：特征： 1 1、平衡運輸問題必有可行解，也、平衡運輸問題必有可行解，也必有最優(yōu)解；必有最優(yōu)解； 2 2、運輸問題的基本可行解中應包、運輸問題的基本可行解中應包括括 m+n1 個基變量。個基變量。 . .重復重復. . ，直到找到最優(yōu)解為止。，直到找到最優(yōu)解為止。步驟：步驟： . .找出找出初始基本可行解初始基本可行解（初始調運方案，一（初始調運方案，一般般m+n-1m+n-1個數字格），用西北角法、最小元素法；個數字格），用西北角法、最小元素法； . .求出各非基變量的檢驗數，判別是否達到求出各非基變量的檢

6、驗數，判別是否達到最優(yōu)解。如果是停止計算，否則轉入下一步，用最優(yōu)解。如果是停止計算，否則轉入下一步，用位勢法計算；位勢法計算； . .改進當前的基本可行解（確定換入、換改進當前的基本可行解（確定換入、換出變量），用閉合回路法調整；出變量），用閉合回路法調整； 二、表上作業(yè)法二、表上作業(yè)法確定確定m+n-1個基變量個基變量空格空格3.2 求解運輸問題的算法求解運輸問題的算法:表上作業(yè)法表上作業(yè)法開開 始始求各非基變求各非基變量的檢驗數量的檢驗數是否達到最優(yōu)解是否達到最優(yōu)解結束結束確定換入變量確定換入變量與換出變量與換出變量新的基可行解新的基可行解求初始基可行解求初始基可行解例一、某運輸資料如下表

7、所示：例一、某運輸資料如下表所示：單位單位 銷地銷地 運價運價 產地產地產量產量311310719284741059銷量銷量36564321 BBBB321AAA1 1、求初始方案：、求初始方案：3.2.1初始基可行解的確定初始基可行解的確定西北角法 西北角發(fā)也就是從運價表的西北角位置開始,依次安排m個產地和n個銷地之間的運輸業(yè)務,從而得到一個初始調運方案的方法. 西北角法應遵循“優(yōu)先安排運價表上編號最小的產地和銷地之間(即運價表的西北角位置)的運輸業(yè)務”的規(guī)則. . .西北角法西北角法( (或左上角法或左上角法):): 此法是純粹的人為的規(guī)定此法是純粹的人為的規(guī)定, ,沒有理論依據和實際背沒

8、有理論依據和實際背景景, ,但它易操作但它易操作, ,特別適合在計算機上編程計算特別適合在計算機上編程計算, ,因而受因而受歡迎歡迎. .方法如下：方法如下：總的運費總的運費(3(33)3)(4(411)11)(2(29)9)(2(22)2)(3(310)10)(6(65)5)135135元元B1B2B3B4產量產量A17A2 4A39銷量銷量3656311310192741058341633 . .初始基可行解的確定初始基可行解的確定-最小元素法：最小元素法： 基本思想是就近供應，即從運價最小的地方開始供基本思想是就近供應，即從運價最小的地方開始供應（調運），然后次小，直到最后供完為止。應（

9、調運），然后次小，直到最后供完為止?？偟倪\輸費用（總的運輸費用（3 31 1）（）（6 64 4） （4 43 3）（）（1 12 2）（）（3 31010）（）（3 35 5）8686元元分別計算各行、各列次小、最小運價的差值分別計算各行、各列次小、最小運價的差值, ,優(yōu)先優(yōu)先在最大差值處進行供需搭配在最大差值處進行供需搭配. . 差值差值=次小次小-最小最小 步驟：步驟：10 計算未劃去行、列的差額計算未劃去行、列的差額; 20 找出最大差額對應的最小元素找出最大差額對應的最小元素cij進行供需分配進行供需分配;30 在未被劃去的行、列重新計算差額在未被劃去的行、列重新計算差額.(3)初始

10、基可行解的確定初始基可行解的確定-最大差值法最大差值法(伏格爾法伏格爾法) Vogel 6 銷銷產產B1B2B3B4供量供量A17A24A39銷量銷量 3656B1B2B3B4供量供量A13113107A219284A3741059銷量銷量3656列差值列差值2513行差值行差值 01 1 6 3 銷銷產產B1B2B3B4供量供量A17A24A3 9銷量銷量 3656B1B2B3B4行差值行差值A13113100A219281A3741052列差值列差值213 3 6 3 銷銷產產B1B2B3B4供量供量A17A24A3 9銷量銷量 3656B1B2B3B4行差值行差值A13113100A21

11、9281A374105列差值列差值212 5 1 2 6 3B1B2B3B4差值差值A13113107A219286A374105差值差值12 銷銷產產B1B2B3B4供量供量A17A24A3 39銷量銷量 3656 以上方法得到的初始解為基可行解 每次行(需求)或列(供應)達到飽和 每次必劃掉一行或一列 得到的元素個數必為m+n-1個 西北角法 最小元素法 最大差值法練習 P97 3.1 3.2 ijij0 0 （因為目標函數要求最小化）因為目標函數要求最小化） 表格中有調運量的地方為基變量表格中有調運量的地方為基變量, ,空格處為非基變空格處為非基變 量量. .基變量的檢驗數基變量的檢驗數

12、ijij0,非基變量的檢驗數非基變量的檢驗數ijij0. 0. ij 0 表示運費增加表示運費增加. 2 2、最優(yōu)解的判別（檢驗數的求法）：、最優(yōu)解的判別（檢驗數的求法）：1jijBijcC B P01njjj mZZx 檢驗數檢驗數非基變量增加一個非基變量增加一個單位目標值的變化單位目標值的變化（1）閉回路法）閉回路法 閉回路：從空格出發(fā)順時針閉回路：從空格出發(fā)順時針(或逆時針或逆時針)畫水平畫水平(或垂直或垂直)直直線線,遇到填有運量的方格遇到填有運量的方格可轉可轉90,然后繼續(xù)前進然后繼續(xù)前進,直到到達出發(fā)直到到達出發(fā)的空格所形成的閉合回路的空格所形成的閉合回路.調運方案的任意空格存在唯

13、一閉回路調運方案的任意空格存在唯一閉回路. 銷銷產產B1B2B3B4供量供量A1 5 27A23 14A3 6 39銷量銷量 3656差值法方案差值法方案一、最優(yōu)調運方案的判定一、最優(yōu)調運方案的判定銷銷 產產 B1 B2 B3 B4 產產量量 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 銷銷量量 3 6 5 6 314 633最小元素法方案最小元素法方案+-+- x11為換入變量，為換入變量，x11：01，運費的變化為，運費的變化為3- -1+2- -3=1。這個變化就是。這個變化就是x11的檢驗數，故的檢驗數，故 11=1B1B2B3B4產量產量A17

14、A24A39銷量銷量365631363124B1B2B3B4產量產量A17A24A39銷量銷量36563136312-14B1B2B3B4產量產量A17A24A39銷量銷量365631363121-14B1B2B3B4產量產量A17A24A39銷量銷量365631363121-1124B1B2B3B4產量產量A17A24A39銷量銷量365631363121-112104 檢驗數中有負數，說明原方案不是最優(yōu)解。檢驗數中有負數，說明原方案不是最優(yōu)解。空格閉回路檢驗數(11)(12)(22)(24)(31)(33)(11)-(13)-(23)-(21)-(11)(12)-(14)-(34)-(32

15、)-(22)(22)-(23)-(13)-(14)-(34)-(32)-(22)(24)-(23)-(13)-(14)-(24)(31)-(34)-(14)-(13)-(23)-(21)-(31)(33)-(34)-(14)-(13)-(33)121-11012檢驗數還存在檢驗數還存在負數負數, 原方案不是最優(yōu)方案原方案不是最優(yōu)方案. 用閉回路求解檢驗數時,需要給每一個空格找一條閉回路.當產銷點較多時,該方法較麻煩.ui,vj自由變量自由變量（2） 位勢法位勢法標準型運輸問題的對偶問題是：標準型運輸問題的對偶問題是： njjjmiiivbuamax11 )n,j;m,i (cvuijji11

16、XBXNXS0CN-CBB-1N-CBB-1-YS1-YS2-Y檢驗數檢驗數對偶變量值等于對偶變量值等于原問題的檢驗數原問題的檢驗數松弛變量松弛變量11212( ,.,. )()ijijBijijijijmnijijijcC B PcYPcu uuv vv Pcuvij()ijijijcuv 基變量的檢驗數為零基變量的檢驗數為零( 基變量基變量xij)，()0ijijijcuv得得m+n- -1個方程個方程,含含m+n個未知數個未知數, 令某個令某個ui ( 或或vj)=0,可解出可解出m+n個個ui 和和vj;由此得非基變量的檢驗由此得非基變量的檢驗數數.()ijijijcuv 1.由基變量

17、的檢驗數為0, ij=cij-(ui+vj)=0, u1=0 (v1=0),得ui, vj 2. 利用 ij=cij-(ui+vj),求非基變量的檢驗數 可令任意的行或列的位勢為可令任意的行或列的位勢為0 (任意值均任意值均可可,為為0出于計算簡單考慮出于計算簡單考慮)銷銷 產產 B1 B2 B3 B4 產產量量 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 銷銷量量 3 6 5 6 314 633位勢法位勢法 令令v1=0, 由由c21=1= u2 +v1，得得 u2=1B1B2B3B4ui311310A11928A274105A3vj 0 1 1 2

18、0 1 1 28-3 7位勢表位勢表2989-3-2)(jiijijvuc檢驗數檢驗數B1B2B3B4ui311310A11928A274105A3vj 0 1 1 28-3 7檢驗數表檢驗數表121-11012 24=-10，當前方案，當前方案 不是最優(yōu)方案。不是最優(yōu)方案。 1. 以以最小負檢驗數最小負檢驗數為出發(fā)點尋找一條閉回路為出發(fā)點尋找一條閉回路. 2. 確定調整量確定調整量,調出格中調出格中最小最小的運量的運量.2.3 改進的方法改進的方法閉回路調整法閉回路調整法二、二、 調運方案的調整調運方案的調整pqijj , i)(min 0 xpq為換入變量為換入變量從從( (p,q) )空

19、格開始畫閉回路空格開始畫閉回路, ,其它轉角點都是填有運其它轉角點都是填有運量的方格量的方格, ,并從并從( (p,q) )空格開始給閉回路上的點按空格開始給閉回路上的點按+1+1,-1,+1,-1,-1,+1,-1編號，編號，-1-1格的最小運量格的最小運量為調整量為調整量. .換出換出變量變量銷銷地地 產產地地 B1 B2 B3 B4 產產量量 A1 A2 A3 3 6 4(+1) 1(- -1) 3(- -1) (+1) 3 7 4 9 銷銷量量 3 6 5 6 運價運價B1B2B3B4產量A1527A2314A3639銷量3656新的調運方案為：新的調運方案為：851186zz2401

20、或者直接算或者直接算 需供B1B2B3B4uiA10210A2218A39125Vj -7-1-70713491110231085運輸問題的求解表上作業(yè)法步驟小結運輸問題的求解表上作業(yè)法步驟小結第一步第一步: :確定初始基可行解（可行調運方案）確定初始基可行解（可行調運方案） 方法：最小元素法與伏格爾法方法：最小元素法與伏格爾法第二步第二步: :判別當前可行方案是否最優(yōu)判別當前可行方案是否最優(yōu) 方法：閉回路法與位勢法方法：閉回路法與位勢法第三步第三步: :對現(xiàn)有方案進行調整對現(xiàn)有方案進行調整 方法：閉回路法方法：閉回路法3.2.4 表表上上作業(yè)法計算中的問題作業(yè)法計算中的問題無窮多最優(yōu)解無窮多

21、最優(yōu)解 某非基變量某非基變量(空格空格)的檢驗數為的檢驗數為0.退化退化方案點數方案點數=產地數產地數+銷地數銷地數1;同時去掉一行和一列時應添加同時去掉一行和一列時應添加0方案方案;調整時出現(xiàn)兩個或兩個以上的最小值調整時出現(xiàn)兩個或兩個以上的最小值,新方案中也要添加新方案中也要添加0方案方案. . .無窮多最優(yōu)解：無窮多最優(yōu)解：產銷平衡的運輸問題必定存最產銷平衡的運輸問題必定存最優(yōu)解優(yōu)解. .如果非基變量的如果非基變量的ij0, 則該問題有無窮多最優(yōu)則該問題有無窮多最優(yōu)解解. 如上例如上例: (1.1) 中的檢驗數是中的檢驗數是 0, 經過調整經過調整, 可得到另可得到另一個最優(yōu)解一個最優(yōu)解.

22、 4、表上作業(yè)法計算中的問題、表上作業(yè)法計算中的問題 .退化退化: 表格中一般要有表格中一般要有(m+n-1)個數字格個數字格.但有時但有時, 在分配運量時則需要同時劃去一在分配運量時則需要同時劃去一行和一列行和一列, 這時需要補一個這時需要補一個0, 以保證有以保證有(m+n-1)個數字格個數字格. 一般可在劃去的行和列一般可在劃去的行和列的任意空格處加一個的任意空格處加一個 0 即可即可. 正常時一次只劃掉同時劃掉了一行和一列 此時同時劃掉一行和一列, 不要補零例例1：B1B2B3B4A178143A226355A31427821762 1 3 5 5 2 6 82 1 7 6 例例2：B

23、1B2B3A11221A23132A32314124B1B2B3A111A222A34412400 04 運輸問題的擴展運輸問題的擴展本本節(jié)節(jié)重重點點供需不平衡的運輸問題供需不平衡的運輸問題供不應求供不應求供過于求供過于求轉運問題轉運問題運輸問題的分類運輸問題的分類產銷產銷平衡平衡問題：問題：ai=bj產銷產銷不平衡不平衡問題：問題：產大于銷：產大于銷：ai bj產小于銷：產小于銷：ai 產量產量二、轉運問題二、轉運問題出現(xiàn)下列問題：出現(xiàn)下列問題：1. 產地與銷地之間沒有直達路線，貨物由產地到銷產地與銷地之間沒有直達路線，貨物由產地到銷地必須通過中轉站轉運；地必須通過中轉站轉運；2. 某些產地

24、可以輸入貨物，銷地也可以輸出貨物，某些產地可以輸入貨物，銷地也可以輸出貨物，3. 產地與銷地之間雖然有直達運輸線，但直達運輸產地與銷地之間雖然有直達運輸線，但直達運輸的費用（距離）比經過某些中轉站的還要高。的費用（距離）比經過某些中轉站的還要高。解法：解法：無轉運問題。無轉運問題。1. 根據問題求出最大可能周轉量根據問題求出最大可能周轉量Q；2. 純轉運點純轉運點產地：輸出量產地：輸出量Q；銷地：輸入量銷地：輸入量Q；輸入輸入=輸出輸出3. 兼中轉站的產地兼中轉站的產地Ai=銷銷地：輸入量地：輸入量Q；產地：輸出量產地：輸出量Q+ai；4. 兼中轉站的銷地兼中轉站的銷地Bj=銷銷地：輸入量地：

25、輸入量bj+Q；產地：輸出量產地：輸出量Q；列出各產地的輸出量和各銷地的輸入量及各產列出各產地的輸出量和各銷地的輸入量及各產銷地之間的運價表銷地之間的運價表, 用表上作業(yè)法求解用表上作業(yè)法求解.輸出：產地；中轉站輸出：產地；中轉站(純純/兼兼)輸入：銷地；中轉站輸入：銷地；中轉站(純純/兼兼)例例 某貨物某貨物, 其產地其產地A1的產量為的產量為10單位單位,A2的產量為的產量為2單位單位, 銷地銷地A3、A4、A5的銷量分別為的銷量分別為3單位、單位、1單位和單位和8單位單位, 其中產地其中產地A2、銷、銷A4又可作為中轉站又可作為中轉站. 同時同時, 貨貨物可通過純中轉站物可通過純中轉站A

26、6進行運輸進行運輸. 各產地、銷地及中轉各產地、銷地及中轉站之間的單位物資運價如表所示站之間的單位物資運價如表所示, 試求一個使總運費試求一個使總運費最省的調運方案最省的調運方案. 銷地銷地產地產地A2A3A4A5A6A126312A2 03M24A4M2031A613270最大可能周轉量最大可能周轉量 Q=a1+a2=10+2=12A1 純產地純產地, 輸出量輸出量10;A2產地兼中轉站產地兼中轉站,輸出量輸出量2+12=14,輸入量輸入量12;A3 純銷地純銷地, 輸入量輸入量3;A4銷地兼中轉站銷地兼中轉站,輸出量輸出量12,輸入量輸入量1+12=13;A5純銷地純銷地,輸入量輸入量8;

27、A6純中轉站純中轉站,輸出量、輸入量均為輸出量、輸入量均為12.根據以上情況列產銷平衡表根據以上情況列產銷平衡表. 銷地產地A2A3A4A5A6輸出量A12631210A203M2414A4M203112A61327012輸入量1231381248 銷地產地A2A3A4A5A6輸出量A118110A212214A41212A611112輸入量1231381248不參加實際調運不參加實際調運3.4 應用舉例應用舉例搞清搞清“產地、銷地產地、銷地”、“運價運價”, “產量、需求產量、需求”, 寫出寫出產銷平衡產銷平衡表表運輸問題的要素運輸問題的要素:未知數未知數如何設如何設虛設虛設產地與銷地產地與

28、銷地;拆分拆分產地與銷地產地與銷地例例 3. 某廠按合同規(guī)定須于每個季度末分別提供某廠按合同規(guī)定須于每個季度末分別提供10,15,25,20臺同一規(guī)格的柴油機臺同一規(guī)格的柴油機.已知該廠各季度已知該廠各季度的生產能力及生產每臺柴油機的成本如下表的生產能力及生產每臺柴油機的成本如下表.如果如果生產出來的柴油機當季不交貨生產出來的柴油機當季不交貨,每臺積壓一個季度每臺積壓一個季度需儲存、維護費用需儲存、維護費用0.15萬元萬元.要求在完成合同的情要求在完成合同的情況下況下,做出該廠全年費用最小的決策做出該廠全年費用最小的決策.季度季度生產能力生產能力單位成本單位成本IIIIIIIV25353010

29、10.811.111.011.3搞清搞清“產地、銷地產地、銷地”、“運價運價”, “產量、需求產量、需求”, 寫出寫出產銷平衡產銷平衡表表未知數未知數如何設如何設設設xij為第為第i季度生產的用于第季度生產的用于第j季度交貨的柴油機數季度交貨的柴油機數.合同要求：合同要求：11122213233314243444 10 15 2520 xxxxxxxxxx產量約束：產量約束：1112131422232433344425 35 30 10 xxxxxxxxxx第第i季度生產的用于第季度生產的用于第j季度交貨的柴油機的實際成本季度交貨的柴油機的實際成本cij=生產成本生產成本+儲存維護費用儲存維護

30、費用ijIIIIIIIVIIIIIIIV10.810.9511.1011.1011.2511.0011.2511.4011.1511.3044114141m in. .0ijijijijijijjiijzc xxas txbx ijIIIIIIIV產量產量IIIIIIIV10.8MMM10.9511.10MM11.1011.2511.00M11.2511.4011.1511.3025353010銷量銷量10152520ijIIIIIIIVD產量產量IIIIIIIV10.8MMM10.9511.10MM11.1011.2511.00M11.2511.4011.1511.3000002535301

31、0銷量銷量1015252030 例: 某玩具公司分別生產三種新型的玩具, 每月可供應量分別為1000件, 2000件,2000件，他們分別被送到甲乙丙三個百貨商店銷售, 已知每月百貨商店各類玩具預期銷售量為1500件, 由于經營原因, 各百貨商店銷售不同玩具的盈利額不同, 又知丙百貨商店要求至少供應C玩具1000件, 而拒絕進入A種玩具, 求滿足上述條件下使總盈利額為最大的供銷分配方案.甲乙丙可供量ABC516124810-911100020002000C先滿足丙1000件甲乙丙丁可供量ABC516124810-91100010002000100015001500500500甲乙丙丁可供量AB

32、C11041286M7500010002000100015001500500500 已知某運輸問題的產銷平衡表, 最優(yōu)調運方案及單位運價表分別如表所示, 由于從產地2至銷地B的道路因故暫時封閉, 故需對調運方案進行修正,試用盡可能簡單的方法重新找出最優(yōu)調運方案.ABCDE產量1233414513948銷量35463ABCDE1231021201020510793010106410變?yōu)樽優(yōu)镸, 計算檢驗數進行調整計算檢驗數進行調整 已知某運輸問題的資料如下表所示已知某運輸問題的資料如下表所示B1B2B3B4發(fā)量發(fā)量A1265315A2132112A3327413收量收量1013125 1、表中的

33、發(fā)量、收量單位為：噸，運價單位為：元、表中的發(fā)量、收量單位為：噸，運價單位為：元/ /噸噸 試求出最優(yōu)運輸方案試求出最優(yōu)運輸方案. . 練習：練習： 2、如將、如將A2的發(fā)量改為的發(fā)量改為1717，其它資料不變，試求最優(yōu)調，其它資料不變，試求最優(yōu)調 運方案。運方案。13A312A2510A1B4B3B2B1最終的運送方案最終的運送方案總的運費總的運費 85元元/噸噸 已知資料如下表所示，問如何供電能使總的輸電費已知資料如下表所示，問如何供電能使總的輸電費用為最小？用為最小？發(fā)電廠 發(fā)電量A1700A2200A3100城市需電量B1500B2250B3100B4150電力供需表電力供需表B1B2B3B4A110523A24312A35634單位輸電費用單位輸電費用作業(yè)：作業(yè)：B1B2B3B4ui A1105230A24-1-4-3-6A350-3-2-5vj 10523 (ui+vj) B1B2B3B4ui A10000A20455A30666vj ij- (ui+vj)