運輸問題剖析

1、運輸問題剖析 第三章第三章 運輸問題運輸問題 運輸問題剖析 本章主要內(nèi)容本章主要內(nèi)容 第一節(jié)第一節(jié) 運輸問題的數(shù)學(xué)模型及其特征運輸問題的數(shù)學(xué)模型及其特征 第二節(jié)第二節(jié) 運輸問題的求解運輸問題的求解表上作業(yè)法表上作業(yè)法 第三節(jié)第三節(jié) 產(chǎn)銷不平衡的運輸問題及應(yīng)用產(chǎn)銷不平衡的運輸問題及應(yīng)用 運輸問題剖析 第一節(jié)第一節(jié) 運輸問題的數(shù)學(xué)模型及其特征運輸問題的數(shù)學(xué)模型及其特征 運輸問題的定義運輸問題的定義 運輸問題的數(shù)學(xué)模型運輸問題的數(shù)學(xué)模型 運輸問題的特征運輸問題的特征 運輸問題剖析 1. 1. 運輸問題的定義運輸問題的定義 例例1 1： 某集團新購進一批鋼材，分別存儲在三個倉庫，現(xiàn)在某集團新購進一批鋼

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

3、，這個需求點供應(yīng)某種物資，這m個個 供應(yīng)點供應(yīng)點A1、A2、.Am的供應(yīng)量分別為的供應(yīng)量分別為a1、a2、.am；n個個 需求點需求點B1、B2、.Bn的需求量分別為的需求量分別為b1、b2、.bn；已知已知 從任一供應(yīng)點從任一供應(yīng)點Ai向任一需求點向任一需求點Bj運輸一個單位物資的費用為運輸一個單位物資的費用為 cij。問采取什么樣的物資調(diào)運方案才能使總運費最省？問采取什么樣的物資調(diào)運方案才能使總運費最省？ B1B2Bn供應(yīng)量供應(yīng)量 A1c11c12c1na1 A2c21c22c2na2 Amcm1cm2cmnam 需求量需求量b1b2bn 運輸問題剖析 2. 2. 運輸問題的數(shù)學(xué)模型運輸問

4、題的數(shù)學(xué)模型 11 1 1 min (1,2,.) . .(1,2,. ) 0,1,2,.,1,2,. mn ijij ij n iji j m ijj i ij zc x xaim s txbjn xim jn 11 mn ij ij ab （其其中中） 運輸問題剖析 運輸問題的約束方程組系數(shù)矩陣及特征運輸問題的約束方程組系數(shù)矩陣及特征 111212122212 11.1 11.1 . 11.1 111 11. . .1 111 nnmmmn xxxxxxxxx A 矩陣矩陣A是一個是一個m+n行行mn列的矩陣，它的秩不超過列的矩陣，它的秩不超過m+n-1。 運輸問題一般有運輸問題一般有m+

5、n-1個基變量。個基變量。 系數(shù)矩陣非常稀疏。系數(shù)矩陣非常稀疏。 xij的系數(shù)列向量為：的系數(shù)列向量為： m行 n行 (0.1.0.1.0)T ijimj Pee 運輸問題剖析 3. 運輸問題的特征運輸問題的特征 特征特征1：運輸問題一定有可行解；運輸問題一定有可行解； 特征特征2：運輸問題一定有最優(yōu)解；運輸問題一定有最優(yōu)解； 特征特征3：運輸問題每一組基對應(yīng)運輸問題每一組基對應(yīng) m+n-1個基變量；個基變量； 特征特征4：運輸問題的運輸問題的 m+n-1個基變量構(gòu)成的變量組不含個基變量構(gòu)成的變量組不含 閉回路閉回路； 特征特征5：任意一個非基變量和任意一個非基變量和 m+n-1個基變量組成的

6、變個基變量組成的變 量組中必定存在一條并且只存在唯一一條閉回路；量組中必定存在一條并且只存在唯一一條閉回路； 特征特征6：如果運輸問題中的供應(yīng)量和需求量都是整數(shù)，如果運輸問題中的供應(yīng)量和需求量都是整數(shù)， 則任一基解中各變量的取值也都是整數(shù)。則任一基解中各變量的取值也都是整數(shù)。 運輸問題剖析 閉回路閉回路 定義：凡是能夠排列成下列序列的一組變量的集合就定義：凡是能夠排列成下列序列的一組變量的集合就 稱為運輸問題的一個閉回路。稱為運輸問題的一個閉回路。 1 12 12 23 21 , s ss i ji ji ji ji ji j xxxxxx 并稱集合中每一個變量為此閉回路的一個頂點；稱連并稱集

7、合中每一個變量為此閉回路的一個頂點；稱連 接相鄰兩個變量（頂點）以及連接最后一個頂點和第接相鄰兩個變量（頂點）以及連接最后一個頂點和第 一個頂點的線段為此閉回路的邊一個頂點的線段為此閉回路的邊。 或或 1 11 22 22 31 , s ss i ji ji ji ji ji j xxxxxx 運輸問題剖析 B1B2B3B4B5 A1 A2 A3 A4 X45 X41 X31X33 X13X15 運輸問題剖析 B1B2B3B4B5 A1 A2 A3 A4 X34 X32 X14X12 運輸問題剖析 B1B2B3B4B5 A1 A2 A3 A4 X35 X41 X31 X43 X13X15 運輸

8、問題剖析 B1B2B3B4B5 A1 A2 A3 A4 X11X12 X22X24 X44X42 X21 （1 1）每個頂點都是轉(zhuǎn)折點；）每個頂點都是轉(zhuǎn)折點； （2 2）閉回路是一條閉合的折線，每一條邊都是水）閉回路是一條閉合的折線，每一條邊都是水 平或垂直的；平或垂直的； （3 3）閉回路上同一行（列）的頂點有偶數(shù)個。）閉回路上同一行（列）的頂點有偶數(shù)個。 運輸問題剖析 閉回路上的點對應(yīng)的系數(shù)列向量線性相關(guān)。閉回路上的點對應(yīng)的系數(shù)列向量線性相關(guān)。 Pij Pik PlkPls Pus Puj ijimj Pee 0 ijiklklsusuj PPPPPP 由于由于 容易證明容易證明 運輸問題

9、剖析 第二節(jié)第二節(jié) 運輸問題的求解運輸問題的求解-表上作業(yè)法表上作業(yè)法 第四步：確定進基變量和出基變量，調(diào)整非最優(yōu)的調(diào)運第四步：確定進基變量和出基變量，調(diào)整非最優(yōu)的調(diào)運 方案，獲得更好的調(diào)運方案；方案，獲得更好的調(diào)運方案；轉(zhuǎn)第二步。轉(zhuǎn)第二步。 表上作業(yè)法的基本步驟：表上作業(yè)法的基本步驟： 第一步：編制初始調(diào)運方案，即尋找第一個基可行解第一步：編制初始調(diào)運方案，即尋找第一個基可行解； 第二步：計算各非基變量的檢驗數(shù)；第二步：計算各非基變量的檢驗數(shù)； 第三步：判斷當(dāng)前的調(diào)運方案是否是最優(yōu)方案，如果已經(jīng)第三步：判斷當(dāng)前的調(diào)運方案是否是最優(yōu)方案，如果已經(jīng) 是最優(yōu)，則算法結(jié)束，問題已經(jīng)解決；否則，轉(zhuǎn)第四

10、步；是最優(yōu)，則算法結(jié)束，問題已經(jīng)解決；否則，轉(zhuǎn)第四步； 運輸問題剖析 第一步：編制初始調(diào)運方案第一步：編制初始調(diào)運方案 要求得運輸問題的初始基可行解，必須保證找到要求得運輸問題的初始基可行解，必須保證找到 m+n1 個基變量個基變量. 運輸問題的任意運輸問題的任意m+n-1個變量構(gòu)成一組基變量的充要條個變量構(gòu)成一組基變量的充要條 件是變量組中不含閉回路件是變量組中不含閉回路. 關(guān)鍵關(guān)鍵:找出找出m+n-1個不含閉回路的變量。個不含閉回路的變量。 西北角法（左上角法）西北角法（左上角法） 最小元素法最小元素法 Vogel 法法 問題：如何使得一個選定的變量不包含在閉回路中？問題：如何使得一個選定

11、的變量不包含在閉回路中？ 運輸問題剖析 B1B2B3B4庫存量庫存量 A1291079 A213425 A384257 需求量需求量3846 6 2 3 1 6 3 對應(yīng)的總運費為對應(yīng)的總運費為 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庫存量庫存量 A1291079 A213425 A384257 需求量需求量3846 5 2

12、 34 4 3 對應(yīng)的總運費為對應(yīng)的總運費為 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 -5 運輸問題剖析 Vogel 法法 B1B2B3B4庫存量庫存量 A1291079 A213425 A384257 需求量需求量3846 1 5 4 5 3 3 對應(yīng)的總運費為對應(yīng)的總運費為 C 2= 23 + 93 + 95 + 75 + 71 + 21 + 25 + 45 + 43 + 23 + 24 =884 =88 -3 -3 -1 -

13、1 -5 -5 -3 -3 -5 -5 -4 -4 運輸問題剖析 B1B2B3B4供應(yīng)量供應(yīng)量 A178143 A226535 A314278 需求量需求量2176 1 0 5 2 6 2 退化情況的處理退化情況的處理 -2 -2 -1 -1 -5 -5 -2 -2 -6 -6 用西北角法求下列運輸問題的第一個基可行解用西北角法求下列運輸問題的第一個基可行解 運輸問題剖析 B1B2B3供應(yīng)量供應(yīng)量 A11842 A25251 A35737 需求量需求量217 1 7 2 -2 -2 -1 -1 -7 -7 注意：每次只能劃去一行或一列，不能同時劃去行和列。注意：每次只能劃去一行或一列，不能同時

14、劃去行和列。 當(dāng)只剩下一行（列）時，只能劃去列（行）。當(dāng)只剩下一行（列）時，只能劃去列（行）。 想一想：為什么？想一想：為什么？ 0 0 用最小元素法求下列運輸問題的第一個基可行解用最小元素法求下列運輸問題的第一個基可行解 運輸問題剖析 第二步：計算各非基變量的檢驗數(shù)第二步：計算各非基變量的檢驗數(shù) 1. 1. 閉回路法閉回路法； 2. 2. 位勢法位勢法。 檢驗數(shù)的定義：非基變量的取值每增加檢驗數(shù)的定義：非基變量的取值每增加1 1時，總運費的時，總運費的 增加量。增加量。 運輸問題的最優(yōu)性條件：檢驗數(shù)非負(fù)運輸問題的最優(yōu)性條件：檢驗數(shù)非負(fù) 運輸問題剖析 1. 1. 閉回路法閉回路法 基變量不含閉

15、回路，但任何一個非基變量都可以與基變基變量不含閉回路，但任何一個非基變量都可以與基變 量構(gòu)成唯一一條閉回路量構(gòu)成唯一一條閉回路 B1B2B3B4庫存量庫存量 A1291079 A213425 A384257 需求量需求量3846 6 2 3 1 6 3 14141222233334 7934256cccccc 含義：含義：x14 每增加一個單位，總運費增加每增加一個單位，總運費增加-6個單位個單位 +1 +1 +1 -1 -1 -1 運輸問題剖析 6 2 3 16 3 所有非基變量的檢驗數(shù)見上表所有非基變量的檢驗數(shù)見上表 B1B2B3B4庫存量庫存量 A1291079 0-6 A213425

16、5-5 A384257 143 需求需求 量量 3846 運輸問題剖析 2. 2. 位勢法位勢法 位勢：運輸問題的對偶變量稱為位勢。位勢：運輸問題的對偶變量稱為位勢。 因為因為m個供應(yīng)點個供應(yīng)點n個需求點的運輸問題有個需求點的運輸問題有m+n個約束，個約束， 因此運輸問題就有因此運輸問題就有m+n個位勢。個位勢。 行位勢行位勢:關(guān)于供應(yīng)點關(guān)于供應(yīng)點Ai的約束對應(yīng)的對偶變量，記為的約束對應(yīng)的對偶變量，記為 ui, i=1,2,m。 列位勢列位勢:關(guān)于需求點關(guān)于需求點Bj的約束對應(yīng)的對偶變量，記為的約束對應(yīng)的對偶變量，記為vj, j = 1,2,n。 運輸問題剖析 定理定理：運輸問題變量運輸問題變

17、量xij的檢驗數(shù)的檢驗數(shù) ijijij cuv 1 11 0 1 (,.,.) 1 0 ijijBijijmnijij cC B Pcuuvvcuv 證明：證明： 運輸問題剖析 位勢及檢驗數(shù)的求法位勢及檢驗數(shù)的求法 由于基變量的檢驗數(shù)為由于基變量的檢驗數(shù)為0，所以可以利用，所以可以利用m+n-1 個基變個基變 量求出位勢量求出位勢 B1B2B3B4庫存量庫存量 A1291079 A213425 A384257 需求量需求量3846 6 23 16 3 0 29 -6 10 -8 13 0 -6 5-5 143 運輸問題剖析 第四步：調(diào)整調(diào)運方案第四步：調(diào)整調(diào)運方案 1. 1. 確定入基變量：選

18、取最小負(fù)檢驗數(shù)對應(yīng)的非基變量確定入基變量：選取最小負(fù)檢驗數(shù)對應(yīng)的非基變量 入基入基 2. 2. 確定出基變量和調(diào)整量確定出基變量和調(diào)整量 將進基變量對應(yīng)的閉回路中的頂點分為奇頂點和偶頂點，將進基變量對應(yīng)的閉回路中的頂點分為奇頂點和偶頂點， 令令= min 閉回路上所有偶頂點對應(yīng)的運量閉回路上所有偶頂點對應(yīng)的運量xij 則則即為調(diào)即為調(diào) 整量，選取一個運量等于整量，選取一個運量等于的偶頂點為出基變量。的偶頂點為出基變量。 3.調(diào)整：閉回路上奇頂點上的運量增加調(diào)整：閉回路上奇頂點上的運量增加，偶頂點上的運偶頂點上的運 量減少量減少。閉回路以外頂點的運量不變。閉回路以外頂點的運量不變。 運輸問題剖析

19、 上例中：若選上例中：若選x14進基，進基， 則則 =min6,3,6=3, 出基變量為出基變量為x23,調(diào)整后得：調(diào)整后得： B1B2B3B4庫存庫存 量量 A1291079 0-6 A213425 5-5 A384257 143 需求量需求量3846 6 23 16 3 運輸問題剖析 總運費：總運費： C = 23 + 93 + 73 + 35 + 24 + 53 = 92 110 x32進基，則進基，則 =min3,3=3, 出基變量選出基變量選x34,調(diào)整調(diào)整 后得：后得： B1B2B3B4庫存量庫存量 A1291079 A213425 A384257 需求需求 量量 3846 3 5

20、 43 33 0 -6 -2 2947 5 6 6 1 8-3 運輸問題剖析 檢驗數(shù)全部非負(fù)，已經(jīng)是最優(yōu)調(diào)運方案；檢驗數(shù)全部非負(fù)，已經(jīng)是最優(yōu)調(diào)運方案； 總費用總費用 C*= 23 + 90 + 76 + 35 + 43 + 24 = 83 B1B2B3B4庫存量庫存量 A1291079 A213425 A384257 需求量需求量3846 0 5 43 36 0 -6 -5 29 77 3 5 31 113 運輸問題剖析 表上作業(yè)法計算中應(yīng)注意的問題表上作業(yè)法計算中應(yīng)注意的問題 1.1.解的情況解的情況 唯一：非基變量檢驗數(shù)全部大于唯一：非基變量檢驗數(shù)全部大于0 0； 無窮多解：至少存在一個非

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

22、. . B1B2B3B4供應(yīng)量供應(yīng)量 A13113107 A219284 A3741059 需求量需求量3656 運輸問題剖析 B1B2B3B4供應(yīng)量供應(yīng)量 A13113107 A219284 A3741059 需求量需求量 3656 4 31 36 3 運輸問題剖析 B1B2B3B4供應(yīng)量供應(yīng)量 A13113107 A219284 A3741059 需求量需求量 3656 4 31 36 3 0 310 -1 2 -5 9 12 1-1 10 12 調(diào)整量為調(diào)整量為 min3,1=1，出基變量為出基變量為x23. 運輸問題剖析 B1B2B3B4供應(yīng)量供應(yīng)量 A13113107 A219284

23、 A3741059 需求量需求量 3656 5 3 1 36 2 最優(yōu)解最優(yōu)解: : 131421243234 5,2,3,1,6,3,0 3 510 21 38 14 65 385 ij xxxxxxx f 其其余余 總總費費用用 0 310 -2 3 -5 9 02 21 912 由于由于x11的檢驗數(shù)為的檢驗數(shù)為0，所以最優(yōu)解不唯一。，所以最優(yōu)解不唯一。 運輸問題剖析 B1B2B3B4供應(yīng)量供應(yīng)量 A13113107 A219284 A3741059 需求量需求量 3656 5 1 3 36 2 0 310 -2 3 -5 9 2 21 912 0 最優(yōu)解最優(yōu)解: : 111321243

24、234 2,5,1,3,6,3,0 3 23 51 18 34 65 385 ij xxxxxxx f 其其余余 總總費費用用 運輸問題剖析 第三節(jié)第三節(jié) 產(chǎn)銷不平衡的運輸問題及應(yīng)用產(chǎn)銷不平衡的運輸問題及應(yīng)用 表上作業(yè)法是以產(chǎn)銷平衡為前提的：表上作業(yè)法是以產(chǎn)銷平衡為前提的： 11 mn ij ij ab 實際中，往往遇到產(chǎn)銷不平衡的運輸問題實際中，往往遇到產(chǎn)銷不平衡的運輸問題 1.1.產(chǎn)大于銷（供過于求）產(chǎn)大于銷（供過于求） 11 mn ij ij ab 2.2.銷大于產(chǎn)（供不應(yīng)求）銷大于產(chǎn)（供不應(yīng)求） 11 mn ij ij ab 運輸問題剖析 產(chǎn)銷不平衡運輸問題向產(chǎn)銷平衡運輸問題的轉(zhuǎn)化產(chǎn)銷

25、不平衡運輸問題向產(chǎn)銷平衡運輸問題的轉(zhuǎn)化 產(chǎn)大于銷的運輸問題：產(chǎn)大于銷的運輸問題： 11 mn ij ij ab 11 1 1 min (1,2,.) . .(1,2,. ) 0,1,2,.,1,2,. mn ijij ij n iji j m ijj i ij zc x xaim s txbjn xim jn 數(shù)學(xué)模型數(shù)學(xué)模型 運輸問題剖析 設(shè)設(shè)xi, n+1 是產(chǎn)地是產(chǎn)地Ai 的庫存量，化成標(biāo)準(zhǔn)形的庫存量，化成標(biāo)準(zhǔn)形 1 11 1 1 1 min (1,2,.) . .(1,2,. ,1) 0,1,2,.,1,2,.1 mn ijij ij n iji j m ijj i ij zc x x

26、aim s txbjn n xim jn 其中其中 ,1 1 11 0,1,. i n mn nij ij cim bab 引入一個虛擬的銷地引入一個虛擬的銷地B Bn+1 n+1（需求量等于 （需求量等于 ），）， 并令各個產(chǎn)地到該虛擬銷地的單位運費并令各個產(chǎn)地到該虛擬銷地的單位運費c ci,n+1 i,n+1=0 =0。 11 mn ij ij ab 運輸問題剖析 產(chǎn)小于銷的運輸問題：產(chǎn)小于銷的運輸問題： 11 mn ij ij ab 引入一個虛擬的產(chǎn)地（產(chǎn)量等于引入一個虛擬的產(chǎn)地（產(chǎn)量等于 ），）， 并令該虛擬產(chǎn)地到各銷地的單位運費為并令該虛擬產(chǎn)地到各銷地的單位運費為0 0。 11 nm

27、 ji ji ba 運輸問題剖析 總供應(yīng)量為總供應(yīng)量為1919千噸，而總需求量為千噸，而總需求量為1515千噸千噸 例例2： A1、A2、A3三個蔬菜生產(chǎn)地生產(chǎn)的蔬菜主要供應(yīng)三個蔬菜生產(chǎn)地生產(chǎn)的蔬菜主要供應(yīng)B1、 B2、B3、B4四個城市。已知三個產(chǎn)地今年的蔬菜產(chǎn)量預(yù)計分四個城市。已知三個產(chǎn)地今年的蔬菜產(chǎn)量預(yù)計分 別為別為7千噸、千噸、5千噸和千噸和7千噸；四個城市今年的蔬菜需求量分別千噸；四個城市今年的蔬菜需求量分別 為為2千噸、千噸、3千噸、千噸、4千噸和千噸和6千噸；從每個蔬菜產(chǎn)地平均運輸千噸；從每個蔬菜產(chǎn)地平均運輸1 千噸蔬菜到各個城市的單位費用千噸蔬菜到各個城市的單位費用(萬元萬元)

28、見下表，你能否替他見下表，你能否替他 們編制一個總運費最省的蔬菜調(diào)運方案？們編制一個總運費最省的蔬菜調(diào)運方案？ 單位運費單位運費 B1B2B3B4 供應(yīng)量供應(yīng)量 A1211347 A2103595 A378127 需求量需求量 2346 運輸問題剖析 需求地需求地 生產(chǎn)地生產(chǎn)地 B1B2B3B4B5供應(yīng)量供應(yīng)量 A12113407 A21035905 A3781207 需求量需求量23464 0 0 -2 2043 0 8 25 7 2 3 3 4 3 2 2 2 3 8 7 最優(yōu)解中最優(yōu)解中x15=2, x25=2，表示兩個產(chǎn)地沒有運出去的蔬菜量。表示兩個產(chǎn)地沒有運出去的蔬菜量。 運輸問題剖析 另：假如例另：假如例2 2中各產(chǎn)地的蔬菜總產(chǎn)量不是中各產(chǎn)地的蔬菜總產(chǎn)量不是1919千噸，千噸， 而是而是1212千噸，就成了一個供不應(yīng)求的運輸問題。千噸，就成了一個供不應(yīng)求的運輸問題。 單位運費單位運費 B1B2B3B4 供應(yīng)量供應(yīng)量 A1211343 A2103594 A378125 需求量需求量 2346 單位運費單位運費 B