第3章運輸問題11-04-11

1、第三章第三章 運輸問題運輸問題北京物資學院信息學院北京物資學院信息學院北京物資學院運籌學教學課件北京物資學院運籌學教學課件本章主要內容本章主要內容第一節(jié)第一節(jié) 運輸問題的數(shù)學模型及其特征運輸問題的數(shù)學模型及其特征第二節(jié)第二節(jié) 運輸問題的求解運輸問題的求解表上作業(yè)法表上作業(yè)法第三節(jié)第三節(jié) 產銷不平衡的運輸問題及應用產銷不平衡的運輸問題及應用第一節(jié)第一節(jié) 運輸問題的數(shù)學模型及其特征運輸問題的數(shù)學模型及其特征 運輸問題的定義運輸問題的定義 運輸問題的數(shù)學模型運輸問題的數(shù)學模型 運輸問題的特征運輸問題的特征1. 1. 運輸問題的定義運輸問題的定義例例1 1： 某集團新購進一批鋼材，分別存儲在三個倉庫，

2、現(xiàn)在某集團新購進一批鋼材，分別存儲在三個倉庫，現(xiàn)在要將這批鋼材運到分布在各地的四個工廠。各倉庫的庫存量、要將這批鋼材運到分布在各地的四個工廠。各倉庫的庫存量、各工廠的需求量以及從各倉庫往各個工廠每運送一噸鋼材所各工廠的需求量以及從各倉庫往各個工廠每運送一噸鋼材所需的費用見下表，問如何調運才能使總運費降到最低？需的費用見下表，問如何調運才能使總運費降到最低？工廠工廠B1工廠工廠B2工廠工廠B3工廠工廠B4庫存量庫存量倉庫倉庫A1291079倉庫倉庫A213425倉庫倉庫A384257需求量需求量3846運輸問題：運輸問題：有有m個供應點向個供應點向n個需求點供應某種物資，這個需求點供應某種物資，

3、這m個供應點個供應點A1、A2、.Am的供應量分別為的供應量分別為a1、a2、.am；n個需求點個需求點B1、B2、.Bn的需求量分別為的需求量分別為b1、b2、.bn；已已知從任一供應點知從任一供應點Ai向任一需求點向任一需求點Bj運輸一個單位物資的費用運輸一個單位物資的費用為為cij。問采取什么樣的物資調運方案才能使總運費最省？問采取什么樣的物資調運方案才能使總運費最??？B1B2Bn供應量供應量A1c11c12c1na1A2c21c22c2na2Amcm1cm2cmnam需求量需求量b1b2bn2. 2. 運輸問題的數(shù)學模型運輸問題的數(shù)學模型1111min(1,2,.). .(1,2,.

4、)0,1,2,.,1,2,.mnijijijnijijmijjiijzc xxaims txbjnxim jn 11mnijijab （其其中中）運輸問題的約束方程組系數(shù)矩陣及特征運輸問題的約束方程組系數(shù)矩陣及特征11121212221211.111.1.11.111111.1111nnmmmnxxxxxxxxxA 矩陣矩陣A是一個是一個m+n行行mn列的矩陣，它的秩不超過列的矩陣，它的秩不超過m+n-1。運輸問題一般有運輸問題一般有m+n-1個基變量。個基變量。系數(shù)矩陣非常稀疏。系數(shù)矩陣非常稀疏。 xij的系數(shù)列向量為：的系數(shù)列向量為：m行n行(0.1.0.1.0)TijimjPee 3.

5、運輸問題的特征運輸問題的特征特征特征1：運輸問題一定有可行解；運輸問題一定有可行解；特征特征2：運輸問題一定有最優(yōu)解；運輸問題一定有最優(yōu)解；特征特征3：運輸問題每一組基對應運輸問題每一組基對應 m+n-1個基變量；個基變量；特征特征4：運輸問題的運輸問題的 m+n-1個基變量構成的變量組不含個基變量構成的變量組不含閉回路閉回路；特征特征5：任意一個非基變量和任意一個非基變量和 m+n-1個基變量組成的變個基變量組成的變量組中必定存在一條并且只存在唯一一條閉回路；量組中必定存在一條并且只存在唯一一條閉回路； 特征特征6：如果運輸問題中的供應量和需求量都是整數(shù)，如果運輸問題中的供應量和需求量都是整

6、數(shù)，則任一基解中各變量的取值也都是整數(shù)。則任一基解中各變量的取值也都是整數(shù)。 閉回路閉回路定義：凡是能夠排列成下列序列的一組變量的集合就定義：凡是能夠排列成下列序列的一組變量的集合就稱為運輸問題的一個閉回路。稱為運輸問題的一個閉回路。1 12 12 23 21,s ssi ji ji ji ji ji jxxxxxx并稱集合中每一個變量為此閉回路的一個并稱集合中每一個變量為此閉回路的一個頂點頂點；稱連；稱連接相鄰兩個變量（頂點）以及連接最后一個頂點和第接相鄰兩個變量（頂點）以及連接最后一個頂點和第一個頂點的線段為此閉回路的一個頂點的線段為此閉回路的邊邊?；蚧? 11 22 22 31,s ss

7、i ji ji ji ji ji jxxxxxxB1B2B3B4B5A1A2A3A4X45X41X31X33X13X15B1B2B3B4B5A1A2A3A4X34X32X14X12B1B2B3B4B5A1A2A3A4X35X41X31X43X13X15B1B2B3B4B5A1A2A3A4X11X12X22X24X44X42X21（1 1）每個頂點都是轉折點；）每個頂點都是轉折點；（2 2）閉回路是一條閉合的折線，每一條邊都是水）閉回路是一條閉合的折線，每一條邊都是水平或垂直的；平或垂直的；（3 3）閉回路上同一行（列）的頂點有偶數(shù)個。）閉回路上同一行（列）的頂點有偶數(shù)個。閉回路上的點對應的系數(shù)

8、列向量線性相關。閉回路上的點對應的系數(shù)列向量線性相關。PijPikPlkPlsPusPujijimjPee 0ijiklklsusujPPPPPP 由于由于容易證明容易證明第二節(jié)第二節(jié) 運輸問題的求解運輸問題的求解-表上作業(yè)法表上作業(yè)法第四步：確定進基變量和出基變量，調整非最優(yōu)的調運第四步：確定進基變量和出基變量，調整非最優(yōu)的調運方案，獲得更好的調運方案；方案，獲得更好的調運方案；轉第二步。轉第二步。表上作業(yè)法的基本步驟：表上作業(yè)法的基本步驟：第一步：編制初始調運方案，即尋找第一個基可行解；第一步：編制初始調運方案，即尋找第一個基可行解；第二步：計算各非基變量的檢驗數(shù)；第二步：計算各非基變量的

9、檢驗數(shù)；第三步：判斷當前的調運方案是否是最優(yōu)方案，如果已經第三步：判斷當前的調運方案是否是最優(yōu)方案，如果已經是最優(yōu)，則算法結束，問題已經解決；否則，轉第四步；是最優(yōu)，則算法結束，問題已經解決；否則，轉第四步；第一步：編制初始調運方案第一步：編制初始調運方案要求得運輸問題的初始基可行解，必須保證找到要求得運輸問題的初始基可行解，必須保證找到 m+n1 個基變量個基變量.運輸問題的任意運輸問題的任意m+n-1個變量構成一組基變量的充要條個變量構成一組基變量的充要條件是變量組中不含閉回路件是變量組中不含閉回路.關鍵關鍵:找出找出m+n-1個不含閉回路的變量。個不含閉回路的變量。西北角法（左上角法）西

10、北角法（左上角法）最小元素法最小元素法Vogel 法法問題：如何使得一個選定的變量不包含在閉回路中問題：如何使得一個選定的變量不包含在閉回路中？B1B2B3B4庫存量庫存量A1291079A213425A384257需求量需求量3846623163對應的總運費為對應的總運費為 C 1= 23 + 93 + 96 + 36 + 32 + 42 + 43 + 23 + 21 + 51 + 56 = 1106 = 110西北角法西北角法( (左上角法左上角法) )-3-3-6-6-2-2 -3-3-1-1 -6-6最小元素最小元素法法B1B2B3B4庫存量庫存量A1291079A213425A384

11、257需求量需求量3846523443對應的總運費為對應的總運費為 C 2= 95 + 75 + 74 + 14 + 13 + 23 + 22 + 42 + 43 + 23 + 24 = 1004 = 100-3-3-4-4-2-2-3-3-4-4-5-5Vogel 法法B1B2B3B4庫存量庫存量A1291079A213425A384257需求量需求量3846154533對應的總運費為對應的總運費為 C 2= 23 + 93 + 95 + 75 + 71 + 21 + 25 + 45 + 43 + 23 + 24 =884 =88-3-3-1-1-5-5-3-3-5-5-4-4B1B2B3B

12、4供應量供應量A178143A226535A314278需求量需求量2176105262退化情況的處理退化情況的處理-2-2-1-1-5-5-2-2-6-6用西北角法求下列運輸問題的第一個基可行解用西北角法求下列運輸問題的第一個基可行解B1B2B3供應量供應量A11842A25251A35737需求量需求量217172-2-2-1-1-7-7注意：每次只能劃去一行或一列，不能同時劃去行和列。注意：每次只能劃去一行或一列，不能同時劃去行和列。當只剩下一行（列）時，只能劃去列（行）。當只剩下一行（列）時，只能劃去列（行）。想一想：為什么？想一想：為什么？00用最小元素法求下列運輸問題的第一個基可行

13、解用最小元素法求下列運輸問題的第一個基可行解第二步：計算各非基變量的檢驗數(shù)第二步：計算各非基變量的檢驗數(shù)1. 1. 閉回路法閉回路法；2. 2. 位勢法。位勢法。檢驗數(shù)的定義：檢驗數(shù)的定義：非基變量的取值每增加非基變量的取值每增加1 1時，總運費的時，總運費的 增加量。增加量。運輸問題的最優(yōu)性條件：運輸問題的最優(yōu)性條件：檢驗數(shù)非負檢驗數(shù)非負1. 1. 閉回路法閉回路法基變量不含閉回路，但任何一個非基變量都可以與基變基變量不含閉回路，但任何一個非基變量都可以與基變量構成唯一一條閉回路量構成唯一一條閉回路B1B2B3B4庫存量庫存量A1291079A213425A384257需求量需求量38466

14、23163141412222333347934256cccccc 含義：含義：x14 每增加一個單位，總運費增加每增加一個單位，總運費增加-6個單位個單位+1+1+1-1-1-1623163所有非基變量的檢驗數(shù)見上表所有非基變量的檢驗數(shù)見上表B1B2B3B4庫存量庫存量A12910790-6A2134255-5A384257143需求需求量量38462. 2. 位勢法位勢法位勢位勢：運輸問題的對偶變量稱為位勢。：運輸問題的對偶變量稱為位勢。因為因為m個供應點個供應點n個需求點的運輸問題有個需求點的運輸問題有m+n個約束，個約束，因此運輸問題就有因此運輸問題就有m+n個位勢。個位勢。 行位勢行位

15、勢:關于供應點關于供應點Ai的約束對應的對偶變量，記為的約束對應的對偶變量，記為 ui, i=1,2,m。列位勢列位勢:關于需求點關于需求點Bj的約束對應的對偶變量，記為的約束對應的對偶變量，記為vj, j = 1,2,n。 定理定理：運輸問題變量運輸問題變量xij的檢驗數(shù)的檢驗數(shù)ijijijcuv 11101(,.,.)10ijijBijijmnijijcC B Pcuuvvcuv 證明：證明：位勢及檢驗數(shù)的求法位勢及檢驗數(shù)的求法由于基變量的檢驗數(shù)為由于基變量的檢驗數(shù)為0，所以可以利用，所以可以利用m+n-1 個基變個基變量求出位勢量求出位勢B1B2B3B4庫存量庫存量A1291079A21

16、3425 A384257需求量需求量3846623163029-610-8130-65-5143第四步：調整調運方案第四步：調整調運方案1. 1. 確定入基變量：選取最小負檢驗數(shù)對應的非基變量確定入基變量：選取最小負檢驗數(shù)對應的非基變量入基入基2. 2. 確定出基變量和調整量確定出基變量和調整量將進基變量對應的閉回路中的頂點分為將進基變量對應的閉回路中的頂點分為奇頂點奇頂點和和偶頂點偶頂點，令令= min 閉回路上所有偶頂點對應的運量閉回路上所有偶頂點對應的運量xij 則則即為調即為調整量，選取一個運量等于整量，選取一個運量等于的偶頂點為出基變量。的偶頂點為出基變量。3.調整：閉回路上奇頂點上

17、的運量增加調整：閉回路上奇頂點上的運量增加，偶頂點上的運偶頂點上的運量減少量減少。閉回路以外頂點的運量不變。閉回路以外頂點的運量不變。上例中：若選上例中：若選x14進基，進基，則則 =min6,3,6=3, 出基變量為出基變量為x23,調整后得：調整后得：B1B2B3B4庫存庫存量量A12910790-6A2134255-5A384257143需求量需求量3846623163總運費：總運費： C = 23 + 93 + 73 + 35 + 24 + 53 = 92 110 x32進基，則進基，則 =min3,3=3, 出基變量選出基變量選x34,調整調整后得：后得：B1B2B3B4庫存量庫存量

18、A1291079A213425A384257需求需求量量38463543330-6-2294756618-3檢驗數(shù)全部非負，已經是最優(yōu)調運方案；檢驗數(shù)全部非負，已經是最優(yōu)調運方案；總費用總費用C*= 23 + 90 + 76 + 35 + 43 + 24 = 83 B1B2B3B4庫存量庫存量A1291079A213425A384257需求量需求量38460543360-6-529773531113表上作業(yè)法計算中應注意的問題表上作業(yè)法計算中應注意的問題1.1.解的情況解的情況 唯一：唯一：非基變量檢驗數(shù)全部大于非基變量檢驗數(shù)全部大于0 0； 無窮多解：無窮多解：至少存在一個非基變量檢驗數(shù)等于

19、至少存在一個非基變量檢驗數(shù)等于0 0。2.退化情況：退化情況：在確定初始基可行解的時候，當填在確定初始基可行解的時候，當填(i,j)格子時，格子時，若若ai=bj, 則則xij=ai=bj, 但此時只能劃去一行或一列，但此時只能劃去一行或一列，在后面的填充過程中相應格子要填在后面的填充過程中相應格子要填0。3.調整時，若閉回路上出現(xiàn)兩個或兩個以上偶頂點調整時，若閉回路上出現(xiàn)兩個或兩個以上偶頂點取值同時達到最小，只能選一個變量出基。取值同時達到最小，只能選一個變量出基。課堂練習課堂練習用表上作業(yè)法求解下列運輸問題用表上作業(yè)法求解下列運輸問題. .B1B2B3B4供應量供應量A13113107A2

20、19284A3741059需求量需求量3656B1B2B3B4供應量供應量A13113107A219284A3741059需求量需求量3656431363B1B2B3B4供應量供應量A13113107A219284A3741059需求量需求量36564313630310-12-59121-11012調整量為調整量為 min3,1=1，出基變量為出基變量為x23.B1B2B3B4供應量供應量 A13113107 A219284 A3741059需求量需求量3656531362最優(yōu)解最優(yōu)解: :1314212432345,2,3,1,6,3,03 51021 38 14 65385ijxxxxxx

21、xf 其其余余總總費費用用0310-23-590221912由于由于x11的檢驗數(shù)為的檢驗數(shù)為0，所以最優(yōu)解不唯一。，所以最優(yōu)解不唯一。B1B2B3B4供應量供應量 A13113107 A219284 A3741059需求量需求量36565133620310-23-592219120最優(yōu)解最優(yōu)解: :1113212432342,5,1,3,6,3,03 23 51 18 34 65 385ijxxxxxxxf 其其余余總總費費用用第三節(jié)第三節(jié) 產銷不平衡的運輸問題及應用產銷不平衡的運輸問題及應用表上作業(yè)法是以產銷平衡為前提的：表上作業(yè)法是以產銷平衡為前提的：11mnijijab 實際中，往往遇

22、到產銷不平衡的運輸問題實際中，往往遇到產銷不平衡的運輸問題1.1.產大于銷（供過于求）產大于銷（供過于求） 11mnijijab 2.2.銷大于產（供不應求）銷大于產（供不應求）11mnijijab 產銷不平衡運輸問題向產銷平衡運輸問題的轉化產銷不平衡運輸問題向產銷平衡運輸問題的轉化產大于銷的運輸問題：產大于銷的運輸問題：11mnijijab 1111min(1,2,.). .(1,2,. )0,1,2,.,1,2,.mnijijijnijijmijjiijzc xxaims txbjnxim jn 數(shù)學模型數(shù)學模型設設xi n+1 是產地是產地Ai 的儲存量，化成標準形的儲存量，化成標準形1

23、11111min(1,2,.). .(1,2,. ,1)0,1,2,.,1,2,.1mnijijijnijijmijjiijzc xxaims txbjn nxim jn 其中其中,11110,1,.i nmnnijijcimbab 引入一個虛擬的銷地（需求量等于引入一個虛擬的銷地（需求量等于 ），并），并令各個產地到虛擬銷地的單位運費為令各個產地到虛擬銷地的單位運費為0 0。11mnijijab 產小于銷的運輸問題：產小于銷的運輸問題：11mnijijab 引入一個虛擬的產地（產量等于引入一個虛擬的產地（產量等于 ），），并令該虛擬產地到各銷地的單位運費為并令該虛擬產地到各銷地的單位運費為0

24、 0。11nmjijiba 總供應量為總供應量為1919千噸，而總需求量為千噸，而總需求量為1515千噸千噸例例2： A1、A2、A3三個蔬菜生產地生產的蔬菜主要供應三個蔬菜生產地生產的蔬菜主要供應B1、B2、B3、B4四個城市。已知三個產地今年的蔬菜產量預計分四個城市。已知三個產地今年的蔬菜產量預計分別為別為7千噸、千噸、5千噸和千噸和7千噸；四個城市今年的蔬菜需求量分別千噸；四個城市今年的蔬菜需求量分別為為2千噸、千噸、3千噸、千噸、4千噸和千噸和6千噸；從每個蔬菜產地平均運輸千噸；從每個蔬菜產地平均運輸1千噸蔬菜到各個城市的單位費用千噸蔬菜到各個城市的單位費用(萬元萬元)見下表，你能否替

25、他見下表，你能否替他們編制一個總運費最省的蔬菜調運方案？們編制一個總運費最省的蔬菜調運方案？ 單位運費單位運費B1B2B3B4供應量供應量A1211347A2103595A378127需求量需求量2346 需求地需求地生產地生產地B1B2B3B4B5供應量供應量A12113407A21035905A3781207需求量需求量2346400-220430825723343222387最優(yōu)解中最優(yōu)解中x15=2, x25=2，表示兩個產地沒有運出去的蔬菜量。表示兩個產地沒有運出去的蔬菜量。假如例假如例2 2中各產地的蔬菜總產量不是中各產地的蔬菜總產量不是1919千噸，而是千噸，而是1212千噸，就

26、成了一個供不應求的運輸問題。千噸，就成了一個供不應求的運輸問題。 單位運費單位運費B1B2B3B4供應量供應量A1211343A2103594A378125需求量需求量2346 單位運費單位運費B1B2B3B4供應量供應量A1211344A2103593A378125A400003需求量需求量2346 引入一個虛擬產地引入一個虛擬產地例例3 3 設有三個化肥廠供應四個地區(qū)的農用化肥。假定等量的設有三個化肥廠供應四個地區(qū)的農用化肥。假定等量的化肥在這些地區(qū)使用效果相同，已知各化肥廠年產量，各地化肥在這些地區(qū)使用效果相同，已知各化肥廠年產量，各地區(qū)年需要量及從各個化肥廠到各地區(qū)單位化肥的運價如下表

27、區(qū)年需要量及從各個化肥廠到各地區(qū)單位化肥的運價如下表所示，試決定使總運費最省的化肥調撥方案。所示，試決定使總運費最省的化肥調撥方案。 需求地區(qū)需求地區(qū)化肥廠化肥廠IIIIIIIV產量產量（萬噸）（萬噸）A1613221750B1413191560C192023-50最低需求最低需求（萬噸）（萬噸）3070 010最高需求最高需求（萬噸）（萬噸）507030不限不限這是一個產銷不平衡的運輸問題，總產量這是一個產銷不平衡的運輸問題，總產量160160萬噸，四個萬噸，四個地區(qū)的最低需求量為地區(qū)的最低需求量為110110萬噸，最高需求為無限。根據(jù)現(xiàn)萬噸，最高需求為無限。根據(jù)現(xiàn)有產量，第四個地區(qū)每年最多能分配到有產量，第四個地區(qū)每年最多能分配