第三章 運輸問題_1

1、運運學(xué)學(xué)籌籌第三章第三章 運輸問題運輸問題3.1 3.1 運輸問題及其數(shù)學(xué)模型運輸問題及其數(shù)學(xué)模型3.2 3.2 用表上作業(yè)法求解運輸問題用表上作業(yè)法求解運輸問題3.3 3.3 運輸問題的進一步討論運輸問題的進一步討論3.4 3.4 應(yīng)用問題舉例應(yīng)用問題舉例運運學(xué)學(xué)籌籌3 運輸問題運輸問題3.1 3.1 運輸問題及其數(shù)學(xué)模型運輸問題及其數(shù)學(xué)模型 日常生活中人們常需將某些物品（包括自身）由一個空間日常生活中人們常需將某些物品（包括自身）由一個空間位置移動到另一個空間位置位置移動到另一個空間位置運輸運輸 單一品種物資運輸調(diào)度典型應(yīng)用單一品種物資運輸調(diào)度典型應(yīng)用 產(chǎn)地產(chǎn)地A1 （產(chǎn)量（產(chǎn)量a1） 銷

2、地銷地B1 （銷量（銷量b1） 產(chǎn)地產(chǎn)地A2 （產(chǎn)量（產(chǎn)量a2） 銷地銷地B2 （銷量（銷量b2 ） 產(chǎn)地產(chǎn)地Am （產(chǎn)量（產(chǎn)量am） 銷地銷地Bn （銷量（銷量bn ） 運價運價cij 怎樣調(diào)運這些物品使總運費最??？怎樣調(diào)運這些物品使總運費最小？運運學(xué)學(xué)籌籌 決策變量決策變量 Xij 表示由產(chǎn)地表示由產(chǎn)地Ai 到銷地到銷地Bj的物品數(shù)量的物品數(shù)量 Cij為為Ai 到到Bj的單位運價的單位運價12c11cnc121c22cnc21mc2mcmncnmmnmmmnnnbbbaxxxAaxxxAaxxxABBB21212222212111211121銷地產(chǎn)地銷量產(chǎn)量運價表運價表運運學(xué)學(xué)籌籌 產(chǎn)銷平

3、衡問題產(chǎn)銷平衡問題總產(chǎn)量總產(chǎn)量=總銷量總銷量 即即 產(chǎn)銷不平衡問題產(chǎn)銷不平衡問題總產(chǎn)量總產(chǎn)量=總銷量總銷量nijmiiba113.1 3.1 運輸問題及其數(shù)學(xué)模型運輸問題及其數(shù)學(xué)模型運運學(xué)學(xué)籌籌3.1 3.1 運輸問題及其數(shù)學(xué)模型運輸問題及其數(shù)學(xué)模型 典型案例典型案例 某企業(yè)有三個工廠（某企業(yè)有三個工廠（B1,B2,B3）和三座倉庫（）和三座倉庫（A1,A2,A3）根據(jù)生產(chǎn)需要要將倉庫的原材料運輸?shù)焦S。由于工廠和根據(jù)生產(chǎn)需要要將倉庫的原材料運輸?shù)焦S。由于工廠和倉庫位置不同，單位運價倉庫位置不同，單位運價cij也不同，具體數(shù)據(jù)如下表。請也不同，具體數(shù)據(jù)如下表。請您為該企業(yè)安排一個使總運費最小

4、的運輸方案。您為該企業(yè)安排一個使總運費最小的運輸方案。運價運價B1B2B3產(chǎn)量產(chǎn)量A148856A216241682A38162477銷量銷量7210241215運運學(xué)學(xué)籌籌一一 數(shù)學(xué)模型法求解數(shù)學(xué)模型法求解)3 , 2 , 1; 3 , 2 , 1(0411027277825624168162416884min3323133222123121113332312322211312113332312322211312113131jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxczjiijijij運運學(xué)學(xué)籌籌 njmixnjbxmiaxxczijjmiijinjijminjijij,

5、2,1,2,1,0,2,1,2,1,min11113.1 3.1 運輸問題及其數(shù)學(xué)模型運輸問題及其數(shù)學(xué)模型由某一產(chǎn)地運往各個銷由某一產(chǎn)地運往各個銷地的物品數(shù)量之和等地的物品數(shù)量之和等于該產(chǎn)地的產(chǎn)量于該產(chǎn)地的產(chǎn)量由各產(chǎn)地運往某一銷地由各產(chǎn)地運往某一銷地的物品數(shù)量之和等于的物品數(shù)量之和等于該銷地的銷量該銷地的銷量單純形法求解單純形法求解？引入人工變量引入人工變量運運學(xué)學(xué)籌籌111111111111111111mnmmnnxxxxxxxxx212222111211運輸問題數(shù)學(xué)模型的特點運輸問題數(shù)學(xué)模型的特點運運學(xué)學(xué)籌籌運輸問題數(shù)學(xué)模型的特點運輸問題數(shù)學(xué)模型的特點 運輸問題有有限最優(yōu)解運輸問題有有限最

6、優(yōu)解 運輸問題約束條件的系數(shù)矩陣運輸問題約束條件的系數(shù)矩陣 約束條件系數(shù)矩陣每一列只有兩個1，其余為0； 對產(chǎn)銷平衡問題對產(chǎn)銷平衡問題 約束條件均為等式，且產(chǎn)量之和=銷量之和；運運學(xué)學(xué)籌籌求解思路求解思路一一 數(shù)學(xué)模型法數(shù)學(xué)模型法二二 表上作業(yè)法（表上作業(yè)法（運輸單純形法運輸單純形法）1 列出產(chǎn)銷平衡表列出產(chǎn)銷平衡表2 確定初始調(diào)運方案確定初始調(diào)運方案 （1）最小元素法）最小元素法 （2）西北角法）西北角法 （3）沃格爾（）沃格爾（Vogel）法）法3 位勢法判定是否最優(yōu)解位勢法判定是否最優(yōu)解4 解的改進解的改進運運學(xué)學(xué)籌籌1 列出產(chǎn)銷平衡表列出產(chǎn)銷平衡表 產(chǎn)銷平衡及運價表產(chǎn)銷平衡及運價表運價

7、運價B1B2B3產(chǎn)量產(chǎn)量A14x118x128x1356A216x2124x2216x2382A38x3116x3224x3377銷量銷量7210241215運運學(xué)學(xué)籌籌2 確定初始調(diào)運方案確定初始調(diào)運方案（1）最小元素法）最小元素法 減少運費減少運費單位運價最小的供銷業(yè)務(wù)單位運價最小的供銷業(yè)務(wù)運價運價B1B2B3產(chǎn)量產(chǎn)量A14x118x128x1356A216x2124x2216x2382A38x3116x3224x3377銷量銷量721024121556產(chǎn)產(chǎn)地地銷地銷地1616041004161416141000運運學(xué)學(xué)籌籌這時得到該運輸問題的一個初始解：這時得到該運輸問題的一個初始解：x

8、11=56,x22=41,x23=41, x31=16,x32=61,其余為其余為0總運費（目標函數(shù)值）總運費（目標函數(shù)值）=2968元元運價運價B1B2B3產(chǎn)量產(chǎn)量A14x118x128x1356A216x2124x2216x2382A38x3116x3224x3377銷量銷量7210241215561616041004161416141000運運學(xué)學(xué)籌籌2 確定初始調(diào)運方案確定初始調(diào)運方案（2）西北角法）西北角法運價運價B1B2B3產(chǎn)量產(chǎn)量A14x118x128x1356A216x2124x2216x2382A38x3116x3224x3377銷量銷量7210241215561616006

9、6663603641041運運學(xué)學(xué)籌籌至此得到該運輸問題的初始基可行解：至此得到該運輸問題的初始基可行解：x11=56,x21=16,x22=66, x32=36,x33=41,其余為其余為0總運費（目標函數(shù)值）總運費（目標函數(shù)值）=3624元元運價運價B1B2B3產(chǎn)量產(chǎn)量A14x118x128x1356A216x2124x2216x2382A38x3116x3224x3377銷量銷量72102412155616160066663603641041運運學(xué)學(xué)籌籌2 確定初始調(diào)運方案確定初始調(diào)運方案（3）沃格爾（）沃格爾（Vogel）法）法 按最小單位運價優(yōu)先安排物品調(diào)運按最小單位運價優(yōu)先安排物品

10、調(diào)運不得不采用運費不得不采用運費很高的其它供銷點對很高的其它供銷點對整個運輸費增加整個運輸費增加 罰數(shù)罰數(shù)=次小單位運價次小單位運價-最小單位運價最小單位運價 罰數(shù)值較小罰數(shù)值較小不能按最小運價安排運輸造成的損失不大不能按最小運價安排運輸造成的損失不大 罰數(shù)值很大罰數(shù)值很大不按最小運價組織運輸會造成很大損失不按最小運價組織運輸會造成很大損失 運運學(xué)學(xué)籌籌8 總運費總運費=2744元元行罰數(shù)行罰數(shù)123運價運價B1B2B3產(chǎn)量產(chǎn)量A14x118x128x1356A216x2124x2216x2382A38x3116x3224x3377銷量銷量7210241215列列罰罰數(shù)數(shù)12356046408

11、48088887205888885041410414108088以行罰數(shù)最大者分以行罰數(shù)最大者分配運輸方案結(jié)果配運輸方案結(jié)果如何？如何？運運學(xué)學(xué)籌籌2 確定初始調(diào)運方案確定初始調(diào)運方案 比較上述三種方法給出的初始基可行解，以沃比較上述三種方法給出的初始基可行解，以沃格爾法給出的解的目標函數(shù)值最小，最小元素法次格爾法給出的解的目標函數(shù)值最小，最小元素法次之，西北角法解的目標函數(shù)值最大。之，西北角法解的目標函數(shù)值最大。 一般，沃格爾法給出的初始解質(zhì)量最好，常用一般，沃格爾法給出的初始解質(zhì)量最好，常用來作為運輸問題最優(yōu)解的近似解。來作為運輸問題最優(yōu)解的近似解。運運學(xué)學(xué)籌籌3 位勢法判定是否最優(yōu)解位勢

12、法判定是否最優(yōu)解 步驟步驟 （1）在（最小元素法）初始解表上增加一位勢列）在（最小元素法）初始解表上增加一位勢列ui和和位勢行位勢行vj運價運價B1B2B3產(chǎn)量產(chǎn)量uiA14x118x128x1356u1A216x2124x2216x2382u2A38x3116x3224x3377u3銷量銷量7210241215vjv1v2v35616416141運運學(xué)學(xué)籌籌3 位勢法判定是否最優(yōu)解位勢法判定是否最優(yōu)解（2）計算位勢，即建立方程組：）計算位勢，即建立方程組：運價運價B1B2B3產(chǎn)量產(chǎn)量uiA14x118x128x1356u1A216x2124x2216x2382u2A38x3116x3224x

13、3377u3銷量銷量7210241215vjv1v2v35616416141u1+ v1=4u2+ v2=24u2+ v3=16 u3+ v1 =8u3+ v2=16運運學(xué)學(xué)籌籌3 位勢法判定是否最優(yōu)解位勢法判定是否最優(yōu)解（2）計算位勢，即建立方程組：）計算位勢，即建立方程組： 為計算簡便，常任意指定某一位勢為計算簡便，常任意指定某一位勢 等于一個較小的整數(shù)或零。等于一個較小的整數(shù)或零。 這里我們?nèi)我庵付ㄟ@里我們?nèi)我庵付╱2=0，由此可算出：，由此可算出： v2=24, v3=16 , u3=-8,v1=16,u1=-12 將上述位勢表格相應(yīng)圓括號內(nèi)將上述位勢表格相應(yīng)圓括號內(nèi)u1+ v1=4u

14、2+ v2=24u2+ v3=16 u3+ v1 =8u3+ v2=16運運學(xué)學(xué)籌籌（3）計算空格檢驗數(shù)）計算空格檢驗數(shù) 因為因為 0 ，故這個解不是最優(yōu)解，故這個解不是最優(yōu)解運價運價B1B2B3產(chǎn)量產(chǎn)量uiA14x118x128x1356u1（-12）A216x2124x2216x2382u2 （0）A38x3116x3224x3377u3 （-8）銷量銷量7210241215vjv1 （16）v2 （24）v3 （16）56-4416041416116)(jiijijvuc412運運學(xué)學(xué)籌籌4 解的改進解的改進 為負，說明將這個非基變量變?yōu)榛兞繒r運費會更為負，說明將這個非基變量變?yōu)榛兞?/p>

15、時運費會更 小，因而這個解不是最優(yōu)解。小，因而這個解不是最優(yōu)解。 改進方法改進方法 在運輸表中找出這個空格對應(yīng)的閉合回路在運輸表中找出這個空格對應(yīng)的閉合回路Lij，在滿足所，在滿足所有約束條件的前提下，使有約束條件的前提下，使xij盡量增大并相應(yīng)調(diào)整次閉合盡量增大并相應(yīng)調(diào)整次閉合回路上其他頂點的運輸量，以得到另一個更好的基可行回路上其他頂點的運輸量，以得到另一個更好的基可行解。解。 步驟（步驟（1）以）以x12為換入變量，找出它在運輸表中的閉合為換入變量，找出它在運輸表中的閉合回路回路 12運運學(xué)學(xué)籌籌 （2）以空格（）以空格（A1,B2） 為第一個奇數(shù)頂點，沿為第一個奇數(shù)頂點，沿 閉合回路的

16、順（或逆）閉合回路的順（或逆） 時針方向前進，對閉合時針方向前進，對閉合 回路上的頂點依次編號回路上的頂點依次編號 （3）偶數(shù)頂點中，找出）偶數(shù)頂點中，找出 運輸量運輸量xij最小的頂點，最小的頂點， 以該格中變量為換出變以該格中變量為換出變量量（4）以）以min xij為調(diào)整量，將回路中奇數(shù)頂點運輸量都增加該數(shù)值，偶數(shù)為調(diào)整量，將回路中奇數(shù)頂點運輸量都增加該數(shù)值，偶數(shù)頂點運輸量都減去該數(shù)值，從而得出一新運輸方案。頂點運輸量都減去該數(shù)值，從而得出一新運輸方案。 該運輸方案總運費比原運輸方案減少該運輸方案總運費比原運輸方案減少ijmin xij（5）基變量個數(shù)仍維持）基變量個數(shù)仍維持5個，目標函

17、數(shù)值：個，目標函數(shù)值： 2968+(-4)56=2744運價運價B1B2B3產(chǎn)量產(chǎn)量A14x118856A21624x221682A38162477銷量銷量72102412155616414161567205運運學(xué)學(xué)籌籌練習(xí)練習(xí) 用位勢法檢驗用西北角法所得初始解是否最優(yōu)解？用位勢法檢驗用西北角法所得初始解是否最優(yōu)解？若不是，對該解進行改進。若不是，對該解進行改進。 總運費總運費=3624元元運價運價B1B2B3產(chǎn)量產(chǎn)量A14x118x128x1356A216x2124x2216x2382A38x3116x3224x3377銷量銷量72102412155616160066663603641041

18、運運學(xué)學(xué)籌籌 表上作業(yè)法是求解運輸問題的一種簡便方法。表上作業(yè)法是求解運輸問題的一種簡便方法。 單純形法與表上作業(yè)法的關(guān)系：單純形法與表上作業(yè)法的關(guān)系：（1）找出初始基可行解）找出初始基可行解 （2）求各非基變量的檢驗數(shù)）求各非基變量的檢驗數(shù)（3）判斷是否最優(yōu)解）判斷是否最優(yōu)解計算表中空格檢驗數(shù)表上給出m+n-1個數(shù)字格判斷方法相同運運學(xué)學(xué)籌籌換基：換基：（4）確定換入變量和換出變量找出新的基可行解。（5）重復(fù)（2）、（3）直至求出最優(yōu)解。表上調(diào)整（閉回路調(diào)整）（運輸問題必有最優(yōu)解）停止最優(yōu)解？是否運運學(xué)學(xué)籌籌說明說明1 有多個檢驗數(shù)均非負，在繼續(xù)進行迭代時，取它們中的任有多個檢驗數(shù)均非負，在繼續(xù)進行迭代時，取它們中的任一變量均可使