管理運籌學(xué)--運輸問題

1、管理運籌學(xué),華國偉Email:huaguowei@gmail.com北京交通大學(xué)經(jīng)管學(xué)院物流管理系,,第三章 運輸問題 Transportation Problem,本節(jié)內(nèi)容提要,3.1 運輸問題的數(shù)學(xué)模 3.2 表上作業(yè)法,,3.1 運輸問題的數(shù)學(xué)模型,,,,,,,,A1,Ai,Am,產(chǎn)地,產(chǎn)量,銷地,B1,Bj,Bn,銷量,例：某運輸問題的資料如下：,,,一、運輸問題的數(shù)學(xué)模型,,,,,數(shù)學(xué)模型的一般形式

2、 已知資料如下：,供需平衡,,當(dāng)產(chǎn)銷平衡時，其模型如下：,Ai的產(chǎn)品全部供應(yīng)出去,Bj的需求全部得到滿足,產(chǎn)銷平衡的運輸問題必定存最優(yōu)解.,當(dāng)產(chǎn)大于銷時，其模型是：,,當(dāng)產(chǎn)小于銷時，其模型是：,,,,m,n,,,,平衡表、運價表和二為一：,約束條件或解可用產(chǎn)銷平衡表表示:,,ui?vj無約束 （i=1,2, …,m;j=1,2, …,n),,ui,vj,設(shè)ui,vj為對偶變量，對偶問題模型為,m個,n個,,,特征： 1

3、、平衡運輸問題必有可行解，也必有最優(yōu)解； 2、運輸問題的基本可行解中應(yīng)包括 m+n－1 個基變量。,⑷.重復(fù)⑵. ⑶，直到找到最優(yōu)解為止。,步驟：,⑴.找出初始基本可行解（初始調(diào)運方案，一般m+n-1個數(shù)字格），用西北角法、最小元素法；,⑵.求出各非基變量的檢驗數(shù)，判別是否達(dá)到最優(yōu)解。如果是停止計算，否則轉(zhuǎn)入下一步，用位勢法計算；,⑶.改進當(dāng)前的基本可行解（確定換入、換出變量），用閉合回路法調(diào)整；,,二、表上作業(yè)法,確定m+n-1

4、個基變量,空格,,3.2 求解運輸問題的算法:表上作業(yè)法,開 始,求各非基變量的檢驗數(shù),是否達(dá)到最優(yōu)解,結(jié)束,確定換入變量與換出變量,新的基可行解,求初始基可行解,N,Y,最小元素法，伏格爾法,閉回路法，位勢法,閉回路調(diào)整法,例一、某運輸資料如下表所示：,,,1、求初始方案：,3.2.1初始基可行解的確定—西北角法,西北角發(fā)也就是從運價表的西北角位置開始,依次安排m個產(chǎn)地和n個銷地之間的運輸業(yè)務(wù),從而得到一個初始調(diào)運方案的方法

5、. 西北角法應(yīng)遵循“優(yōu)先安排運價表上編號最小的產(chǎn)地和銷地之間(即運價表的西北角位置)的運輸業(yè)務(wù)”的規(guī)則.,,⑴.西北角法(或左上角法): 此法是純粹的人為的規(guī)定,沒有理論依據(jù)和實際背景,但它易操作,特別適合在計算機上編程計算,因而受歡迎.方法如下：,總的運費＝(3×3)＋(4×11)＋(2×9)＋(2×2)＋(3×10)＋(6×5)＝135元,,3,11,3,10,1,

6、9,2,7,4,10,5,8,3,4,,1,,6,,3,,3,⑵.初始基可行解的確定--最小元素法： 基本思想是就近供應(yīng)，即從運價最小的地方開始供應(yīng)（調(diào)運），然后次小，直到最后供完為止。,總的運輸費用＝（3×1）＋（6×4） ＋（4×3）＋（1×2）＋（3×10）＋（3×5）＝86元,,分別計算各行、各列次小、最小運價的差值,優(yōu)先在最大差值處進行供需搭配.

7、差值=次小-最小,步驟：,10 計算未劃去行、列的差額;,20 找出最大差額對應(yīng)的最小元素cij進行供需分配;,30 在未被劃去的行、列重新計算差額.,(3)初始基可行解的確定---最大差值法(伏格爾法) Vogel,,6,,,,,,,,,,,,,行差值,0,1,1,,6,3,,,,,,,3,6,3,,,,,,,,5,1,2,6,3,,,,,,,,,,以上方法得到的初始解為基可行解每次行(需求)或列(供應(yīng))達(dá)到飽和每次必劃掉一行

8、或一列得到的元素個數(shù)必為m+n-1個西北角法 最小元素法 最大差值法,練習(xí),P97 3.1 3.2,,,σij≥0 （因為目標(biāo)函數(shù)要求最小化） 表格中有調(diào)運量的地方為基變量,空格處為非基變 量.基變量的檢驗數(shù)σij＝0,非基變量的檢驗數(shù)σij≥0. σij 0 表示運費增加.,,2、最優(yōu)解的判別（檢驗數(shù)的求法）：,非基變量增加一個單位目標(biāo)值的變化,,,閉回路：從空格出發(fā)順時針(或逆

9、時針)畫水平(或垂直)直線,遇到填有運量的方格可轉(zhuǎn)90°,然后繼續(xù)前進,直到到達(dá)出發(fā)的空格所形成的閉合回路.,調(diào)運方案的任意空格存在唯一閉回路.,,,,,,差值法方案,一、最優(yōu)調(diào)運方案的判定,,最小元素法方案,,,,,,+,-,+,-,x11為換入變量，x11：0→1，運費的變化為3-1+2-3=1。這個變化就是x11的檢驗數(shù)，故 ?11=1,,3,1,3,6,3,,,,,1,2,4,3,1,3,

10、6,3,1,2,,,,,-1,4,3,1,3,6,3,1,2,,,,,,,1,-1,4,3,1,3,6,3,1,2,1,-1,,,,,12,4,3,1,3,6,3,1,2,1,-1,12,,,,,,,10,4,檢驗數(shù)中有負(fù)數(shù)，說明原方案不是最優(yōu)解。,,檢驗數(shù)還存在負(fù)數(shù), 原方案不是最優(yōu)方案.,,用閉回路求解檢驗數(shù)時,需要給每一個空格找一條閉回路.當(dāng)產(chǎn)銷點較多時,該方法較麻煩.,,,ui,vj自由變量,（2） 位勢法 標(biāo)準(zhǔn)型運

11、輸問題的對偶問題是：,檢驗數(shù),對偶變量值等于原問題的檢驗數(shù),松弛變量,,基變量的檢驗數(shù)為零(?基變量xij)，,得m+n-1個方程,含m+n個未知數(shù), 令某個ui ( 或vj)=0,可解出m+n個ui 和vj;由此得非基變量的檢驗數(shù).,,1.由基變量的檢驗數(shù)為0, ?ij=cij-(ui+vj)=0, u1=0 (v1=0),得ui, vj2. 利用?ij=cij-(ui+vj),求非基變量的檢驗數(shù)可令任意的行或列的位勢為0 (任意

12、值均可,為0出于計算簡單考慮),,位勢法,,令v1=0, 由c21=1= u2 +v1，得 u2=1,,,,,,,,,0,,,1,,1,,,2,,,,,,,,0,1,1,2,8,-3,7,位勢表,2,9,8,9,-3,-2,,檢驗數(shù),,,,,,,,0,1,1,2,8,-3,7,檢驗數(shù)表,1,2,1,-1,10,12,,?24=-1＜0，當(dāng)前方案 不是最優(yōu)方案。,,1. 以最小負(fù)檢驗數(shù)為出發(fā)點尋找一條閉回路.2. 確定調(diào)整量,調(diào)出格

13、中最小的運量.,2.3 改進的方法—閉回路調(diào)整法,,,從(p,q)空格開始畫閉回路,其它轉(zhuǎn)角點都是填有運量的方格,并從(p,q)空格開始給閉回路上的點按+1,-1,+1,-1編號，-1格的最小運量為調(diào)整量.,換出變量,運價,,新的調(diào)運方案為：,或者直接算,,7,1,3,4,9,11,10,2,3,10,8,5,,運輸問題的求解－－表上作業(yè)法步驟小結(jié),第一步:確定初始基可行解（可行調(diào)運方案） 方法：最小元素法與伏格爾法第二步:

14、判別當(dāng)前可行方案是否最優(yōu) 方法：閉回路法與位勢法第三步:對現(xiàn)有方案進行調(diào)整 方法：閉回路法,,3.2.4 表上作業(yè)法計算中的問題,無窮多最優(yōu)解 某非基變量(空格)的檢驗數(shù)為0.退化方案點數(shù)=產(chǎn)地數(shù)+銷地數(shù)－1;同時去掉一行和一列時應(yīng)添加0方案;調(diào)整時出現(xiàn)兩個或兩個以上的最小值,新方案中也要添加0方案.,⑴.無窮多最優(yōu)解：產(chǎn)銷平衡的運輸問題必定存最優(yōu)解.如果非基變量的σij＝0, 則該問題有無窮多最優(yōu)解

15、. 如上例: (1.1) 中的檢驗數(shù)是 0, 經(jīng)過調(diào)整, 可得到另一個最優(yōu)解.,4、表上作業(yè)法計算中的問題,,,⑵.退化: 表格中一般要有(m+n-1)個數(shù)字格.但有時, 在分配運量時則需要同時劃去一行和一列, 這時需要補一個0, 以保證有(m+n-1)個數(shù)字格. 一般可在劃去的行和列的任意空格處加一個 0 即可.,,,,正常時一次只劃掉同時劃掉了一行和一列此時同時劃掉一行和一列, 不要補零,,,,例1：,,,2 1

16、 3 5 5 2 6 82 1 7 6,例2：,0,0,0,,,,,,,,,§4 運輸問題的擴展,本節(jié)重點,供需不平衡的運輸問題,轉(zhuǎn)運問題,運輸問題的分類,產(chǎn)銷平衡問題：∑ai=∑bj產(chǎn)銷不平衡問題：,,產(chǎn)大于銷：∑ai >∑bj,產(chǎn)小于銷：∑ai <∑bj,供需不平衡---虛設(shè)產(chǎn)地、銷地,產(chǎn)大于銷時增加一個虛擬

17、的銷售點,其銷量為產(chǎn)銷的差額,各產(chǎn)地到該銷地的單位運價為0.銷大于產(chǎn)時增加一個虛擬的產(chǎn)地,其產(chǎn)量為產(chǎn)銷的差額,該產(chǎn)地到各銷地的單位運價為0.,,1. 產(chǎn)大于銷 ：,模型：,運輸表：,實際意義：虛設(shè)一個銷地,運價為零,,,2. 產(chǎn)小于銷 ：,模型：,運輸表：,實際意義：虛設(shè)一 個產(chǎn)地,,運價為零,,一、供需不平衡的運輸問題,1、供不應(yīng)求的運輸問題,虛設(shè)一個供應(yīng)地，其虛供應(yīng)量為供不應(yīng)求部分。,虛設(shè)一個供應(yīng)地A3，其供應(yīng)量=130-

18、110=20,,,0 0 0,,用最小元素法或差值法求初始方案。,,例. 甲、乙、丙三個城市今年冬季分別需要煤炭320、250、350萬噸, 由A、B兩處煤礦負(fù)責(zé)供應(yīng).已知煤炭年供應(yīng)量為A—400萬噸,B—450萬噸.由各煤礦至各城市的單位運價(萬元/萬噸)如下.,由于需大于供,經(jīng)研究決定,甲城市供應(yīng)量可減少0~30萬噸,乙城市需要量應(yīng)全部滿足,丙城市供應(yīng)量不少于270萬噸,試求將供應(yīng)量分配完

19、又使總運費最低的調(diào)運方案.,拆分需求—剛需與彈性需求,,,甲：供應(yīng)量可減少0~30萬噸，乙城市全部滿足，丙城市供應(yīng)量不少于270萬噸。,,甲：供應(yīng)量可減少0~30萬噸，乙城市全部滿足，丙城市供應(yīng)量不少于270萬噸。,1521,2216,M,M,M,0,0,,,,,最高需求>產(chǎn)量,,,二、轉(zhuǎn)運問題,出現(xiàn)下列問題：產(chǎn)地與銷地之間沒有直達(dá)路線，貨物由產(chǎn)地到銷地必須通過中轉(zhuǎn)站轉(zhuǎn)運；某些產(chǎn)地可以輸入貨物，銷地也可以輸出貨物，產(chǎn)地與

20、銷地之間雖然有直達(dá)運輸線，但直達(dá)運輸?shù)馁M用（距離）比經(jīng)過某些中轉(zhuǎn)站的還要高。,解法：,根據(jù)問題求出最大可能周轉(zhuǎn)量Q；,,3. 兼中轉(zhuǎn)站的產(chǎn)地Ai=,4. 兼中轉(zhuǎn)站的銷地Bj=,列出各產(chǎn)地的輸出量和各銷地的輸入量及各產(chǎn)銷地之間的運價表, 用表上作業(yè)法求解.,輸出：產(chǎn)地；中轉(zhuǎn)站(純/兼)輸入：銷地；中轉(zhuǎn)站(純/兼),,例 某貨物, 其產(chǎn)地A1的產(chǎn)量為10單位,A2的產(chǎn)量為2單位, 銷地A3、A4、A5的銷量分別為3單位、1單位和8單位

21、, 其中產(chǎn)地A2、銷A4又可作為中轉(zhuǎn)站. 同時, 貨物可通過純中轉(zhuǎn)站A6進行運輸. 各產(chǎn)地、銷地及中轉(zhuǎn)站之間的單位物資運價如表所示, 試求一個使總運費最省的調(diào)運方案.,,最大可能周轉(zhuǎn)量 Q=a1+a2=10+2=12,A1 純產(chǎn)地, 輸出量10;A2產(chǎn)地兼中轉(zhuǎn)站,輸出量2+12=14,輸入量12;A3 純銷地, 輸入量3;A4銷地兼中轉(zhuǎn)站,輸出量12,輸入量1+12=13;A5純銷地,輸入量8;A6純中轉(zhuǎn)站,輸出量、輸入

22、量均為12.根據(jù)以上情況列產(chǎn)銷平衡表.,不參加實際調(diào)運,3.4 應(yīng)用舉例,搞清“產(chǎn)地、銷地”、“運價”, “產(chǎn)量、需求”, 寫出產(chǎn)銷平衡表,運輸問題的要素:,未知數(shù)如何設(shè),虛設(shè)產(chǎn)地與銷地;拆分產(chǎn)地與銷地,,例 3. 某廠按合同規(guī)定須于每個季度末分別提供10,15,25,20臺同一規(guī)格的柴油機.已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本如下表.如果生產(chǎn)出來的柴油機當(dāng)季不交貨,每臺積壓一個季度需儲存、維護費用0.15萬元.要求在

23、完成合同的情況下,做出該廠全年費用最小的決策.,搞清“產(chǎn)地、銷地”、“運價”, “產(chǎn)量、需求”, 寫出產(chǎn)銷平衡表,未知數(shù)如何設(shè),,設(shè)xij為第i季度生產(chǎn)的用于第j季度交貨的柴油機數(shù).,合同要求：,產(chǎn)量約束：,第i季度生產(chǎn)的用于第j季度交貨的柴油機的實際成本cij=生產(chǎn)成本+儲存維護費用,目標(biāo)函數(shù)：,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,例: 某玩具公司分別生產(chǎn)三種新型的玩具, 每月可供應(yīng)量分別為1000件, 2

24、000件,2000件，他們分別被送到甲乙丙三個百貨商店銷售, 已知每月百貨商店各類玩具預(yù)期銷售量為1500件, 由于經(jīng)營原因, 各百貨商店銷售不同玩具的盈利額不同, 又知丙百貨商店要求至少供應(yīng)C玩具1000件, 而拒絕進入A種玩具, 求滿足上述條件下使總盈利額為最大的供銷分配方案.,C先滿足丙1000件,,已知某運輸問題的產(chǎn)銷平衡表, 最優(yōu)調(diào)運方案及單位運價表分別如表所示, 由于從產(chǎn)地2至銷地B的道路因故暫時封閉, 故需對調(diào)運方案進行修

25、正,試用盡可能簡單的方法重新找出最優(yōu)調(diào)運方案.,10變?yōu)镸, 計算檢驗數(shù)進行調(diào)整,,已知某運輸問題的資料如下表所示,1、表中的發(fā)量、收量單位為：噸，運價單位為：元/噸 試求出最優(yōu)運輸方案.,練習(xí)：,2、如將A2的發(fā)量改為17，其它資料不變，試求最優(yōu)調(diào) 運方案。,已知資料如下表所示，問如何供電能使總的輸電費用為最小？,電力供需表,單位輸電費用,作業(yè)：,(ui+vj),σij,- (ui+vj),=,cij,,C=5200

26、,運輸問題習(xí)題,,二、如下所示的運輸問題中,如果某一產(chǎn)地有一個單位物資未運出,就將發(fā)生存儲費用.假定三個產(chǎn)地單位物資存儲費用分別為2,2,1,請用最小元素法求初始方案, 用位勢法調(diào)整出最優(yōu)方案并計算出最優(yōu)方案的總費用.,,三、某最小費用運輸問題的調(diào)運方案如下(黑體字為運量):1.上述方案是否可作為表上作業(yè)法求解時的初始解?說明理由.2.如問題1的答案為是,請用用位勢法進行檢驗并求出最優(yōu)方案.,,單位運價,,,四、某公司和供貨商A、B

27、、C簽訂了長期供貨合同, 按月為位于不同地區(qū)的三個下屬工廠供應(yīng)某種原料, 三個供貨商提供的原料品質(zhì)基本相同, 但由于所處的地理位置、人工成本等導(dǎo)致其實際供貨成本有所不同. 由于一次生產(chǎn)事故，導(dǎo)致最大的供貨商A下個月的供貨量無法全部滿足. 下個月供貨商的供應(yīng)量、工廠的需求量和供貨商與工廠之間的供貨成本如下表所示. 公司經(jīng)緊急協(xié)商, 在工廠1所在地籌措到100噸的貨源, 供貨成本為23百元/噸; 工廠2所在地貨源充足, 供

28、貨成本為25百元/噸. 但由于運力緊張兩處貨源均無法調(diào)運到外地. 鑒于此種情況公司決定要優(yōu)先保證工廠1的全部需求, 工廠3的需求至少要滿足500噸. 該公司面臨的問題是應(yīng)如何協(xié)調(diào)各供貨商和工廠之間的供貨關(guān)系, 才能使總的供貨成本最小.請為本問題建立適合于應(yīng)用于表上作業(yè)法的產(chǎn)銷平衡表. (不必計算),,,五、已知某極小化運輸問題的有關(guān)數(shù)據(jù)如下表所示:表中黑體字為運量。要求：用位勢法計算表中方案的檢驗數(shù)并進行進一步調(diào)整。,,,,教育部門