運籌學-運輸問題

1、 運輸問題 運輸問題（運輸問題（Transportation Problem，簡記為，簡記為TP）是一類常見而且極其特殊的線性規(guī)劃問題是一類常見而且極其特殊的線性規(guī)劃問題. .它最早是從它最早是從物資調運工作中提出來的，是物流優(yōu)化管理的重要的物資調運工作中提出來的，是物流優(yōu)化管理的重要的內容之一內容之一 。 從理論上講，運輸問題也可用單純形法來求解，從理論上講，運輸問題也可用單純形法來求解，但是由于運輸問題數(shù)學模型具有特殊的結構，存在一但是由于運輸問題數(shù)學模型具有特殊的結構，存在一種比單純形法更簡便的計算方法種比單純形法更簡便的計算方法 表上作業(yè)法表上作業(yè)法，用表上作業(yè)法來求解運輸問題比用單純

2、形法可節(jié)約計用表上作業(yè)法來求解運輸問題比用單純形法可節(jié)約計算時間與計算費用算時間與計算費用. .但表上作業(yè)法的實質仍是單純形法但表上作業(yè)法的實質仍是單純形法 1 運輸問題及其數(shù)學模型1 1 運輸問題及其數(shù)學模型運輸問題及其數(shù)學模型 設某種物資共有設某種物資共有 m 個產(chǎn)地個產(chǎn)地 A1，A2，Am，各各產(chǎn)地的產(chǎn)量分別是產(chǎn)地的產(chǎn)量分別是a1，a2 ，am；有有n 個銷地個銷地 B1，B2，Bn ，各銷地的銷量分別為各銷地的銷量分別為b1，b2，bn . 假定從產(chǎn)地假定從產(chǎn)地Ai（i =1，2，m）向銷地向銷地Bj（j =1，2，n）運輸單位物資的運價是運輸單位物資的運價是cij，問怎樣調運才能，問

3、怎樣調運才能使總運費最??？使總運費最??？一、一、運輸問題的數(shù)學模型運輸問題的數(shù)學模型 加速物資流轉加速物資流轉 降低流通費用降低流通費用 0,0,0 (1,2,;1,2, )ijijabcim jn 運輸問題 銷地銷地產(chǎn)地產(chǎn)地 B1 B2 Bn產(chǎn)量產(chǎn)量 A1c11c21 c1n a1 A2c21c22 c2n a2 Amcm1cm2 cmn am銷量銷量 b1 b2 bn 運輸表運輸表1 1、產(chǎn)銷平衡問題、產(chǎn)銷平衡問題即即11mnijijab 設設 xij 表示產(chǎn)地表示產(chǎn)地 Ai 運往銷地運往銷地 Bj (i=1,2,m; j=1,2,n) 的運量的運量.11minmnijijijzc x1.

4、 .nijijstxa1,2,im1mijjixb1,2,jn01,2,;1,2,ijxim jn 銷地銷地產(chǎn)地產(chǎn)地 B1 B2 Bn產(chǎn)量產(chǎn)量 A1 x11c11 x12c21 x1n c1n a1 A2 x21c21 x22c22 x2nc2n a2 Am xm1cm1 xm2cm2 xmncmn am銷量銷量 b1 b2 bnNote : cij 在左下在左下角角 xij 在右上角在右上角 1 運輸問題及其數(shù)學模型2 2、產(chǎn)銷不平衡問題、產(chǎn)銷不平衡問題當當11mnijijab11minmnijijijzc x1. .nijijstxa1,2,im1mijjixb1,2,jn01,2,;1,

5、2,ijxim jn當當11mnijijab11minmnijijijzc x1. .nijijstxa1,2,im1mijjixb1,2,jn01,2,;1,2,ijxim jn 運輸問題二、運輸問題數(shù)學模型的特點二、運輸問題數(shù)學模型的特點討論產(chǎn)銷平衡問題討論產(chǎn)銷平衡問題定理定理 1 平衡運輸平衡運輸問題必有可行解，也必有最優(yōu)解問題必有可行解，也必有最優(yōu)解. . 證明證明定理定理 2 平衡運輸問題的約束方程系數(shù)矩陣平衡運輸問題的約束方程系數(shù)矩陣 A 和增廣矩和增廣矩陣陣 的秩相等，且等于的秩相等，且等于 m+n-1 . 即即 A( )( )1R AR Amn定理定理2 說明：說明：基可行解包

6、含基可行解包含m+n-1個基變量個基變量.定理定理 3 平衡運輸問題的約束方程系數(shù)矩陣平衡運輸問題的約束方程系數(shù)矩陣 A 的所有的所有各階子式只取各階子式只取 0，1 或或 -1 三個值三個值.定理定理 4 如果平衡運輸問題中的所有產(chǎn)量如果平衡運輸問題中的所有產(chǎn)量 ai 和銷量和銷量 bj都是整數(shù)，那么，它的任一基可行解都是整數(shù)解都是整數(shù)，那么，它的任一基可行解都是整數(shù)解. .證明證明note定理定理 1 1 的證明的證明Proof :11mnijijabd設(1,2,;1,2, )ijijabxim jnd111(1,2,)nnnijiijjijjjabaxba imdd則取則取顯然有顯然有

7、 ， 0ijx 又又111(1,2, )mmmijjijijiiiabbxabjndd所以所以 ，是問題的一個可行解，是問題的一個可行解. 0ijx 0 (1,2,;1,2, )ijcim jn 又因為又因為 ，對于任一可行，對于任一可行解有目標函數(shù)值解有目標函數(shù)值 ，對于求極小化問題，目標函數(shù)，對于求極小化問題，目標函數(shù)值有下界，則必有最優(yōu)解值有下界，則必有最優(yōu)解. 0z 1 運輸問題及其數(shù)學模型Note : 平衡運輸問題有平衡運輸問題有 個變量，個變量， 個約束個約束條件，規(guī)模很大。條件，規(guī)模很大。m nmn111111111111111111A1212111111111111111111

8、mnaaaAbbb111212122212nnmmmnxxxxxxxxxGo back( )+1R Am n定理定理 4 的證明的證明Proof : 設設 x 是是 Ax = b 的任一基可行解，的任一基可行解，1 12211,mnmni ji jijxxxB 為對應的基矩陣，則為對應的基矩陣，則det(1, 2,1)detttti jBxtmnB 其中其中 Bt 是用是用 b 中對應的中對應的 m+n-1元素替換元素替換 B 的第的第t 列列元素得到的矩陣元素得到的矩陣.1212Tmnbaaabbb 顯然顯然，由定理，由定理 3 知，知，det Bt 是個整數(shù)，是個整數(shù)， det B= ，因

9、此，因此， 都是整數(shù)都是整數(shù).1(1, 2,1)tti jxtmn其基變量為其基變量為 運輸問題定義定義 1 1（其中（其中 互不相同，互不相同， 互不相同）互不相同）12, ,si ii12,sjjj形式的變量集合，稱為一個閉回路，其中諸變量稱為形式的變量集合，稱為一個閉回路，其中諸變量稱為這個閉回路的頂點這個閉回路的頂點. B1 B2 B3 B4 B5 A1 x11 x12 x13 x14 x15 A2 x21 x22 x23 x24 x25 A3 x31 x32 x33 x34 x35 A4 x41 x42 x43 x44 x45如：如： 變量集合變量集合111222243431,xxx

10、xxx變量集合變量集合1114444535322221,xxxxxxxx2、每一行（或列）若有閉回路的頂點，則有兩個每一行（或列）若有閉回路的頂點，則有兩個頂點；頂點；3、每兩個頂點格子的連線都是水平的或垂直的；每兩個頂點格子的連線都是水平的或垂直的；4、閉回路中頂點的個數(shù)必為偶數(shù)閉回路中頂點的個數(shù)必為偶數(shù). .閉回路的幾何特征：閉回路的幾何特征：1、每一個頂點格子都是每一個頂點格子都是 90轉角點；轉角點；凡是能排列成凡是能排列成1 11 22 22 311 1, ,s ssi ji ji ji ji ji ji jxxxxxxx，凡是能排列成凡是能排列成1 11 22 22 311 1,

11、,s ssi ji ji ji ji ji ji jxxxxxxx，1 運輸問題及其數(shù)學模型閉回路的代數(shù)性質：閉回路的代數(shù)性質：1 11 22 22 31,s ssi ji ji ji ji ji jxxxxxx性質性質 1 構成閉回路的變量組對應的列向量組構成閉回路的變量組對應的列向量組1 11 22 22 31,s ssi ji ji ji ji ji jpppppp必線性相關必線性相關.證明證明性質性質 2 分組分組構成閉回路，則該變量組對應的列向量組構成閉回路，則該變量組對應的列向量組1 12 2,r ri ji ji jppp是線性相關的是線性相關的.推論推論 1 若變量組對應的列向

12、量組線性無關，則該變若變量組對應的列向量組線性無關，則該變量組一定不包含閉回路量組一定不包含閉回路.若變量組若變量組 中有一個部中有一個部1 12 2*,( )r ri ji ji jxxxGo on性質性質 1 的證明的證明Proof :由直接計算可知由直接計算可知1 11 22 22 310s ssi ji ji ji ji ji jpppppp111111111111111111A111212122212nnmmmnxxxxxxxxx故該向量組線性相關故該向量組線性相關. 運輸問題在變量組在變量組 中，若有某中，若有某1 12 2*,( )r ri ji ji jxxx一個變量一個變量

13、xij 是它所在的行（第是它所在的行（第 i 行）或列（第行）或列（第 j 列）列）中出現(xiàn)于中出現(xiàn)于（*）中的唯一變量，則稱該變量中的唯一變量，則稱該變量 xij 是該變量是該變量組的一個孤立點組的一個孤立點.定義定義 21114444535322221,xxxxxxxx閉回路的特征閉回路的特征性質性質 3 沒有孤立點沒有孤立點 若一變量組中不包含任何閉回路，則該變量組若一變量組中不包含任何閉回路，則該變量組必有孤立點必有孤立點.反證反證孤立點不會是孤立點不會是閉回路上的點閉回路上的點定理定理 5 變量組變量組 對應的列向量組線性無關的充要對應的列向量組線性無關的充要*( )條件是該變量組中不

14、包含任何閉回路條件是該變量組中不包含任何閉回路. .證明證明定理定理 5 的證明的證明Proof :用反證法用反證法設變量組設變量組（*）對應的列向量）對應的列向量組線性無關，但該變量組包含一個以其中某些變量為頂組線性無關，但該變量組包含一個以其中某些變量為頂點的閉回路，點的閉回路，則由性質則由性質 2 知，這些變量對應的列向量必知，這些變量對應的列向量必線性相關，與假設矛盾線性相關，與假設矛盾. .定理定理 5 變量組變量組 對應的列向量組線性無關的充要對應的列向量組線性無關的充要*( )條件是該變量組中不包含任何閉回路條件是該變量組中不包含任何閉回路. .設有一組數(shù)設有一組數(shù) 使得使得12

15、,rkkk1 122120(1)rri ji jri jk pk pk p 由于變量組由于變量組（* *）中不包含任何閉回路，由性質中不包含任何閉回路，由性質 3 可知其中必有孤立點，可知其中必有孤立點， 不妨設不妨設 為孤立點，為孤立點，1 1i jx又不妨設又不妨設 是（是（* *）在第）在第i1 1行上唯一的變量，這時由行上唯一的變量，這時由p pijij的特征，（的特征，（1 1）的左端第）的左端第i1個分量和為個分量和為k1，而右端為，而右端為0，1 1i jx在第在第 j1列上的唯列上的唯一變量如何？一變量如何？2 21200r ri jri jkk pk p，從而（1）變成（2）

16、但但 仍不包含閉回路，其中還有孤立點仍不包含閉回路，其中還有孤立點, ,2 23 3,r ri ji ji jxxx與前面類似分析可證與前面類似分析可證 k2= 0. 同理得同理得 k3 = k4 = kr = 0這就證明了向量組這就證明了向量組（* *）線性無關線性無關.1 運輸問題及其數(shù)學模型推論推論 2 2 平衡運輸問題中的一組平衡運輸問題中的一組 m + n - 1 個變量個變量能構成基變量的充要條件是它不包含任何閉回路能構成基變量的充要條件是它不包含任何閉回路.1 122,(1)ssi ji ji jxxxsmn 該推論給出了運輸問題的基可行解中基變量的一該推論給出了運輸問題的基可行

17、解中基變量的一個基本特征：基變量組不含閉回路個基本特征：基變量組不含閉回路. . 這就是基可行解這就是基可行解在表上的一個表現(xiàn)，利用它來判斷在表上的一個表現(xiàn)，利用它來判斷 m + n 1 個變量個變量是否構成基變量組，就看它是否包含閉回路是否構成基變量組，就看它是否包含閉回路. . 這種方法簡便易行，它比直接判斷這些變量對應這種方法簡便易行，它比直接判斷這些變量對應的列向量是否線性無關要簡便得多的列向量是否線性無關要簡便得多. . 利用基變量的這個特征，將可以導出求平衡運輸利用基變量的這個特征，將可以導出求平衡運輸問題的初始基可行解的一些簡便方法問題的初始基可行解的一些簡便方法. .2 運輸問

18、題的表上作業(yè)法2 2 運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法 表上作業(yè)法（又稱運輸單純形法）是根據(jù)單純形表上作業(yè)法（又稱運輸單純形法）是根據(jù)單純形法的原理和運輸問題的特點，設計的一種在表上運算法的原理和運輸問題的特點，設計的一種在表上運算的求解運輸問題的簡便而有效的方法的求解運輸問題的簡便而有效的方法.主要步驟：主要步驟：1、求一個初始調運方案（初始基可行解）；求一個初始調運方案（初始基可行解）；2、判別當前方案是否為最優(yōu)，若是則迭代停止，否則判別當前方案是否為最優(yōu)，若是則迭代停止，否則 轉下一步；轉下一步；3、改進當前方案，得到新的方案（新的基可行解），改進當前方案，得到新的方案（新的基可

19、行解）， 再返回再返回 2 。 運輸問題一、一、初始方案的確定初始方案的確定1、西北角法西北角法 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 15Ex. 1 50 已知某商品有三個產(chǎn)地已知某商品有三個產(chǎn)地A1、A2、A3和四個銷地和四個銷地B1、B2、B3、B4 ，產(chǎn)量、銷量及單位運價如表，產(chǎn)量、銷量及單位運價如表. .問應問應如何調運，在滿足各銷地需要的情況下，使總的運費如何調運，在滿足各銷地需要的情況下，使總的運費支出為最少？支出為最少？ 解：解：51010205規(guī)則規(guī)則: :從運輸表的

20、西從運輸表的西北角開始北角開始, ,優(yōu)先安排優(yōu)先安排編號小的產(chǎn)地和銷地編號小的產(chǎn)地和銷地的運輸任務的運輸任務. .填了幾個數(shù)字？填了幾個數(shù)字？10505203 51 10254 10675z Note : 在填入一個數(shù)時，如果行和列同時飽和，在填入一個數(shù)時，如果行和列同時飽和， 規(guī)定只劃去一行或一列規(guī)定只劃去一行或一列 BjAi B1 B2 B3 B4 ai A110 5 2 3 50 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 155002 運輸問題的表上作業(yè)法2、最小元素法最小元素法 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A

21、2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 15規(guī)則規(guī)則: :優(yōu)先安排單位運價最小的產(chǎn)地與銷地之間的運輸優(yōu)先安排單位運價最小的產(chǎn)地與銷地之間的運輸 任務任務. .4010255101010405253 51 102 105 10620z Note : 在某行（或列）填入最后一個數(shù)時，如果行和在某行（或列）填入最后一個數(shù)時，如果行和列同時飽和，規(guī)定只劃去該行（或列）列同時飽和，規(guī)定只劃去該行（或列） BjAi B1 B2 B3 B4 ai A1 1 5 3 2 60 A2 4 1 2 3 20 A3 5 6 1 4 10 bj 50 20 10 10001010

22、2050填了幾個數(shù)字？填了幾個數(shù)字？ 運輸問題定理定理 6 用西北角法或最小元素法得到的初始解是用西北角法或最小元素法得到的初始解是平衡平衡運輸問題的基可行解，運輸問題的基可行解， m+n-1 個個填入數(shù)字的格子對應的填入數(shù)字的格子對應的是基變量是基變量.Proof : ijx首先，得到的初始解首先，得到的初始解 為可行解是顯然的為可行解是顯然的. . 其次，由于行列數(shù)共有其次，由于行列數(shù)共有 m+n ，而按填數(shù)字的方法，而按填數(shù)字的方法, ,除填最后一個數(shù)時，劃去一行一列外，每填一個數(shù)劃去除填最后一個數(shù)時，劃去一行一列外，每填一個數(shù)劃去一行或一列一行或一列. 因此因此, , 共填共填 m+n

23、-1 個數(shù)個數(shù). . 最后，證明所填最后，證明所填 m+n-1 個數(shù)對應的變量組不含閉回路個數(shù)對應的變量組不含閉回路.用反證法用反證法若含有閉回路若含有閉回路 不妨設此閉回路如右不妨設此閉回路如右（其他情形同理可證）（其他情形同理可證）1 1i jx4 4i jx3 3i jx2 2i jx 不妨設填不妨設填 后劃去行，故后劃去行，故 必須較必須較 先填，先填，且填后劃去的是列，從而且填后劃去的是列，從而 必須較必須較 先填，且填后劃先填，且填后劃去的是行，而這又說明去的是行，而這又說明 必須較必須較 先填，且填后劃先填，且填后劃去的是列，這又得到去的是列，這又得到 必須較必須較 先填，且填后

24、劃去的先填，且填后劃去的是行，這樣就得到了矛盾，所以，填數(shù)的是行，這樣就得到了矛盾，所以，填數(shù)的 m+nm+n-1 -1 個格個格子對應的變量組不含閉回路，從而，證得了本定理子對應的變量組不含閉回路，從而，證得了本定理. . 1 1i jx4 4i jx2 2i jx3 3i jx1 1i jx2 2i jx4 4i jx3 3i jx1 1i jx2 運輸問題的表上作業(yè)法關鍵關鍵1、填一個數(shù)字劃去一行或一列填一個數(shù)字劃去一行或一列 不產(chǎn)生閉回路；不產(chǎn)生閉回路； 2、填一個數(shù)字填一個數(shù)字只只劃去一行或一列劃去一行或一列 填滿填滿m+n-1-1個數(shù)個數(shù). . BjAi B1 B2 ai A1 8

25、 2 5 A2 3 1 4 bj 6 3 差額差額 6 2 差額差額 5 1315 BjAi B1 B2 ai A1 8 2 5 A2 3 1 4 bj 6 3 8 53 1 1 346z 按最小元素法按最小元素法3423、Vogel 法法 ( (元素差額法元素差額法) )規(guī)則：計算各行各列的最小元素與次小元素的差額，規(guī)則：計算各行各列的最小元素與次小元素的差額，優(yōu)先安排差額最大的所優(yōu)先安排差額最大的所在行或列的單位運價最在行或列的單位運價最小的產(chǎn)地與銷地之間的小的產(chǎn)地與銷地之間的運輸任務運輸任務8 23 42 334Vz 運輸問題二、二、最優(yōu)性檢驗最優(yōu)性檢驗 BjAi B1 B2 B3 B4

26、 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 1540102551010定理定理 7 設設 是平衡運輸問題的是平衡運輸問題的一組基變量，一組基變量， 是非基變量，則在變量組是非基變量，則在變量組 中存在唯一的閉回路中存在唯一的閉回路.1 12 2,(1)s si ji ji jxxxsmn1 12 20,s si ji ji jx xxx0 x1、閉回路法閉回路法+1-1+1-121423 105 BjAi B1 B2 B3 B4 A1 A2 A3檢驗數(shù)表檢驗數(shù)表-5-10 6 6 6ijijijcc奇頂點偶頂點2 運輸問題

27、的表上作業(yè)法2、位勢法（對偶變量法）位勢法（對偶變量法）求檢驗數(shù)的求檢驗數(shù)的方法方法11minmnijijijzc x1. .nijijstxa1,2,im1mijjixb1,2,jn01,2,1,2,ijximjn11minmnijijijzc x1nijijxa2,3,im1mijjixb1,2,jn01,2,1,2,ijximjn111211nxxxa. .st0 x00a x約束方程的系數(shù)矩陣的秩為約束方程的系數(shù)矩陣的秩為m+n -1x0必為基變必為基變量量, x0= 0約束方程的系數(shù)矩陣的秩為約束方程的系數(shù)矩陣的秩為m+n對任意的對任意的 a0， 與原問題等價與原問題等價1212,m

28、nyu uuv vv11maxmniijjijaub v10. .1,2,1,2,ijijijstuvcimuajnu v無符號限制由于由于01010ijipmj ijijijcyp1212,ijmnijcu uuv vvpijijcuv001au010000pxj 的檢驗數(shù)的檢驗數(shù) 1jjBjjjcc Bpcyp1 12 2,(1)s si ji ji jxxxsmn設：為基變量，由于基變量設：為基變量，由于基變量的檢驗數(shù)等于零的檢驗數(shù)等于零111 1222 210sss siji jiji jiji juvcuvcuvcua有解，不唯有解，不唯一一ui 稱為行位勢稱為行位勢，vj 稱為行位

29、勢稱為行位勢 運輸問題ijijcuv BjAi B1 B2 B3 B4 ui A1 4010 25 5 2 5 3 A2 4 3 10 1 10 2 A3 10 5 6 3 4 vj BjAi B1 B2 B3 B4 A1 A2 A3檢驗數(shù)表檢驗數(shù)表-5-10 6 6 6-2-120273見見 Ex. 1 最小元素法得到的初始基可行解最小元素法得到的初始基可行解2121241411cccc21241411cuvuvuv2121cuv4275 3333333( 2)( 1)6cuv 10053-12-5323232cuv6( 5)56 若若 ，則此時的運輸方案為最優(yōu)的，則此時的運輸方案為最優(yōu)的0

30、ij2 運輸問題的表上作業(yè)法三、三、基可行解的改進基可行解的改進 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 1540102551010 BjAi B1 B2 B3 B4 A1 A2 A3檢驗數(shù)表檢驗數(shù)表-5-10 6 6 6選擇進基變量選擇進基變量min0,1,1stijijimjn 則取非基變量則取非基變量 xst 為進基變量為進基變量確定出基變量確定出基變量調整量調整量 minijklxx閉回路上偶頂點則基變量則基變量 xkl 出基（運量擦去）出基（運量擦去）調整方法：在該閉回路上，奇

31、點運量加調整方法：在該閉回路上，奇點運量加 ，偶點減去，偶點減去 能轉運多少？能轉運多少？153010 6 5 4 2010 1-5 6 520 6 6 4 5 6 因為因為 ，所以此運輸方案為最優(yōu)，所以此運輸方案為最優(yōu)方案方案0ijNote : 若在閉回路上有幾個偶點處的運量等于若在閉回路上有幾個偶點處的運量等于 ，則，則可任取其中一個作為出基變量（運量擦去），其余幾可任取其中一個作為出基變量（運量擦去），其余幾個點的值調整后變?yōu)閭€點的值調整后變?yōu)?. (0. (但應填入，說明這些變量還但應填入，說明這些變量還在基內，這時就出現(xiàn)了退化在基內，這時就出現(xiàn)了退化) )問：問：從從A2到到B4的單

32、位運價的單位運價c24在什么范圍變化時，所得在什么范圍變化時，所得最優(yōu)調運方案不變最優(yōu)調運方案不變. . c12在什么范圍變化呢？在什么范圍變化呢？四、四、 踏石法踏石法1)、找入變量、找入變量l從從 中找最小者，對應中找最小者，對應 xij 就是入變量就是入變量2)、以、以 非基變量非基變量xij 為起點，尋找由原基變量構成的為起點，尋找由原基變量構成的閉合回路閉合回路l該回路只在每個拐角各有一個基變量，中間允許穿越某些基該回路只在每個拐角各有一個基變量，中間允許穿越某些基變量；因此，閉合回路中必有偶數(shù)個變量變量；因此，閉合回路中必有偶數(shù)個變量(包括包括 xij )，且回路，且回路中每行每列

33、只有兩個變量中每行每列只有兩個變量3)、求入基變量、求入基變量 xij 的最大值及新基變量的解的最大值及新基變量的解l從從 xij出發(fā)，沿任一個方向對回路拐角上的基變量依此標出發(fā)，沿任一個方向對回路拐角上的基變量依此標“ ”和和“+”，表示，表示“ ”和和“+” xij ，從而迭代后仍滿足分配的，從而迭代后仍滿足分配的平衡平衡l標有標有“ ”的變量中最小者就是的變量中最小者就是出基變量出基變量，對應，對應xij*的值就是所的值就是所求入基變量求入基變量 xij 的最大值。的最大值。l標有標有“ ”的變量減去的變量減去 xij*，標有標有“+”的變量加上的變量加上 xij* 4)、用位勢法求新基

34、變量的檢驗數(shù)、用位勢法求新基變量的檢驗數(shù)l若所有若所有 ，則達到最優(yōu)，算法停止；，則達到最優(yōu)，算法停止； 否則返回否則返回 1）。）。()0ijijijcuv()0ijijijcuv 補充補充 例題例題 踏石法，以最低費用法所得初始解開始（注意：踏石法，以最低費用法所得初始解開始（注意：對基變量對基變量x xij ij有：有：c cij ij=u=ui i+v+vj j，任取一個任取一個u ui i或或v vj j=0=0，計算出，計算出u ui i、v vj j) )所有所有 cij (ui+vj) =0，達到最優(yōu)。，達到最優(yōu)。答：最優(yōu)解如上分配表，答：最優(yōu)解如上分配表，OBJ=98OBJ=

35、121OBJ=101五、五、 運輸問題迭代中的一些具體問題運輸問題迭代中的一些具體問題 1 ) 閉合回路的畫法閉合回路的畫法l從從入基入基變量變量xij出發(fā)，遇到某個基變量則選一個方向拐角，若不能再出發(fā)，遇到某個基變量則選一個方向拐角，若不能再遇到其它基變量，則返回上一拐角，換一個方向走，采用深探法遇到其它基變量，則返回上一拐角，換一個方向走，采用深探法l閉合回路不一定是矩形閉合回路不一定是矩形 2 ) 產(chǎn)銷不平衡產(chǎn)銷不平衡l供過于求，即供過于求，即 ai bj ，增加一個虛收點增加一個虛收點Dn+1，bn+1= ai - bj , 令令 wi,n+1=0, i=1,2,ml供小于求，即供小于

36、求，即 ai bj ，增加一個虛發(fā)點增加一個虛發(fā)點Wm+1，am+1= bj - ai , 令令 wm+1,j=0, j=1,2,n 3 ) 關于退化問題關于退化問題(1)、初始解退化初始解退化。即初始基變量的個數(shù)少于。即初始基變量的個數(shù)少于m+n 1。必須補足基變。必須補足基變量的個數(shù)，否則不能正常解出量的個數(shù)，否則不能正常解出m+n個個ui和和 vjl所補基變量的值為所補基變量的值為 0 ，補充的原則：，補充的原則：(1)盡量先選運費小的實變量；盡量先選運費小的實變量；(2)補充后不能有某個基變量獨占一行一列補充后不能有某個基變量獨占一行一列六、六、 關于退化問題關于退化問題(2)、迭代過

37、程中出現(xiàn)退化迭代過程中出現(xiàn)退化l閉合回路中標有閉合回路中標有“ ”的基變量同時有多個達到最小的基變量同時有多個達到最小l變換后，有多個原基變量變?yōu)樽儞Q后，有多個原基變量變?yōu)?0，選運費最大者為出，選運費最大者為出基基變量，變量，其余保留在新的基礎解中其余保留在新的基礎解中l(wèi)退化較嚴重時，可能會出現(xiàn)多次迭代只有值為退化較嚴重時，可能會出現(xiàn)多次迭代只有值為 0 的基變量在的基變量在轉移。此時，一要耐心，二要正確選擇出變量轉移。此時，一要耐心，二要正確選擇出變量踏石法迭代中需注意的問題：踏石法迭代中需注意的問題：(1)、錯誤地將分配表中基變量的解代入到運費表中、錯誤地將分配表中基變量的解代入到運費表

38、中(2)、不能正確畫閉合回路、不能正確畫閉合回路(3)、初始解退化，未能補足基變量的個數(shù)初始解退化，未能補足基變量的個數(shù)。因此在位勢法。因此在位勢法中多次令某個中多次令某個ui或或 vj為為 0；(4)、在位勢法中只能令一個在位勢法中只能令一個 ui 或或 vj 為為 0；若不能求出全部；若不能求出全部 ui和和 vj ，說明基變量未選夠數(shù)或未選對，說明基變量未選夠數(shù)或未選對 運輸問題七、七、 補充：運輸問題的圖上作業(yè)法補充：運輸問題的圖上作業(yè)法 圖上作業(yè)法是在交通圖上進行物資調運方案編制和圖上作業(yè)法是在交通圖上進行物資調運方案編制和調整的一種科學方法。在鐵路特別是公路運輸中使用很調整的一種科

39、學方法。在鐵路特別是公路運輸中使用很多且有很好的效果。多且有很好的效果。 在交通圖中，用在交通圖中，用表示表示產(chǎn)地（發(fā)點），并將產(chǎn)量記產(chǎn)地（發(fā)點），并將產(chǎn)量記在圓圈內；用在圓圈內；用表示銷地表示銷地（收點），并將銷量記在方（收點），并將銷量記在方框內?？騼取?06040402463目標：噸公里數(shù)目標：噸公里數(shù)( (費用費用) )最小的調運方案最小的調運方案 . . 物資調運的流向用與交通線平行的箭線表示，規(guī)定物資調運的流向用與交通線平行的箭線表示，規(guī)定畫在前進方向的右邊，調運量加括號記在箭線的右邊。畫在前進方向的右邊，調運量加括號記在箭線的右邊。(20)(20)(40)補充：運輸問題的圖上作業(yè)

40、法20303020243對流：物資在同一線路上往返運輸對流：物資在同一線路上往返運輸.(20)(20)(30)(30)(10)這是對流這是對流20303020243(20)(20)(30)(30)106030(10)(20)1、無圈無圈的交通的交通圖圖2020502010 對于無圈圖，每條對于無圈圖，每條邊都是割邊，去掉它網(wǎng)邊都是割邊，去掉它網(wǎng)絡將不連通，所以，每絡將不連通，所以，每條邊上的運量是不得不條邊上的運量是不得不只要每條邊上不產(chǎn)生對流，即為最優(yōu)方案只要每條邊上不產(chǎn)生對流，即為最優(yōu)方案 運輸問題206040402463(20)(20)(40)2、有一個圈的交通圖有一個圈的交通圖圈長：圈

41、上每一條邊的長度之和（記為圈長：圈上每一條邊的長度之和（記為 l）l =15 先用先用“丟邊破圈丟邊破圈”方法，得到無圈圖，再產(chǎn)生一方法，得到無圈圖，再產(chǎn)生一個個沒有對流的方案。沒有對流的方案。內圈長內圈長 l內內：流向在圈內的邊的長度之和：流向在圈內的邊的長度之和l內內= 8外圈長外圈長 l外外：流向在圈外的邊：流向在圈外的邊的長度之和的長度之和l外外= 4是最優(yōu)解碼？是最優(yōu)解碼？8,2ll 內不是最優(yōu)的.稱為迂回稱為迂回調整方案：調整方案：對內圈各流量中最小調運量，進行反向調運對內圈各流量中最小調運量，進行反向調運(40)(20)(20)結論：結論：內外圈長都小于圈長的一半的無對流的調運方

42、案內外圈長都小于圈長的一半的無對流的調運方案 為最優(yōu)方案為最優(yōu)方案67.22llll外內此時為最優(yōu)調運方案補充：運輸問題的圖上作業(yè)法3、有多個、有多個圈圈的交通的交通圖圖106030202050203020有幾個圈？ 如有一個圈的情形，對每一個圈先用如有一個圈的情形，對每一個圈先用“丟邊破圈丟邊破圈”方方法，得到無圈圖，再產(chǎn)生一個沒有對流的方案。再進行法，得到無圈圖，再產(chǎn)生一個沒有對流的方案。再進行檢查、調整。檢查、調整。只需檢查13個圈嗎？會循環(huán)嗎？ 一般不夠！因為對一個圈進行調整后，會對已檢一般不夠！因為對一個圈進行調整后，會對已檢查的圈有影響查的圈有影響. 不會！因為每次目標不會！因為每

43、次目標函數(shù)下降值大于一個固定函數(shù)下降值大于一個固定值（如值（如 1） 運輸問題4、產(chǎn)銷不平衡運輸問題產(chǎn)銷不平衡運輸問題當當11mnijijab111minmnijijijzc x1. .nijijstxa1,2,1im m11mijjixb1,2,jn01,2,1;1,2,ijxim mjnNote : 通常建立運輸模通常建立運輸模型指的是平衡運輸模型型指的是平衡運輸模型可以虛設一個產(chǎn)地可以虛設一個產(chǎn)地 Am+1, 其產(chǎn)量為其產(chǎn)量為111nmmjijiaba 并假設產(chǎn)地并假設產(chǎn)地 Am+1 運往各銷地的單運往各銷地的單位運價為位運價為 cm+1, j = 0 ( j = 1 , 2 , , n

44、 ) . 則原問題可轉則原問題可轉化為平衡運輸問題：化為平衡運輸問題： 產(chǎn)大于銷，可通產(chǎn)大于銷，可通過虛設銷地，類似過虛設銷地，類似建立平衡運輸模型建立平衡運輸模型2 運輸問題的表上作業(yè)法Ex. 2已知運輸問題由表給出，試建立運輸模型已知運輸問題由表給出，試建立運輸模型 . Bj Ai B1 B2 B3 ai A14 25 10 A2638 15 bj 8 7 14解解: Bj Ai B1 B2 B3 ai A14 25 10 A2638 15 A3000 4 bj 8 7 14本題產(chǎn)量為本題產(chǎn)量為25，銷量為，銷量為29，是銷大于產(chǎn)問題，是銷大于產(chǎn)問題 虛設一個產(chǎn)地虛設一個產(chǎn)地 A3，由于并

45、沒有生產(chǎn)，所以運價為，由于并沒有生產(chǎn)，所以運價為零，得運輸模型零，得運輸模型. . 如果各銷地不滿足時，單位缺貨費為如果各銷地不滿足時，單位缺貨費為 4，3，7，則，則運輸模型為運輸模型為437 運輸問題 BjAi B1 B2 B3 ai A14 23 10 A2564 15 A3345 20 最低最低需求量需求量 10 10 10Ex. 3 已知運輸問題由表給出，如果產(chǎn)地已知運輸問題由表給出，如果產(chǎn)地 Ai 的產(chǎn)量的產(chǎn)量必須運走必須運走，試建立運輸模型試建立運輸模型 . BjAi B1 B2 B3 B4 ai A14 23 10 A2564 15 A3345 20 bj 10 10 10 1

46、5解解:這是一個產(chǎn)大于銷的運輸問題這是一個產(chǎn)大于銷的運輸問題. .234虛設一銷地虛設一銷地 B4 ,銷量銷量 b4 = 15 . BjAi B1 B2 B3 ai A14 23 10 A2564 15 A3345 20 最低最低需求量需求量 10 10 10 最高最高需求量需求量 20 10不限不限 BjAi B1 B2 B3 ai A14 23 10 A2564 15 A3345 20 bj 10 10 10 443B3B15351015A4M100MM0 三個銷地的最低需求為三個銷地的最低需求為 30，最高需求不限最高需求不限. . 根據(jù)根據(jù)現(xiàn)有產(chǎn)量，現(xiàn)有產(chǎn)量，B3 至多能得到至多能得到

47、 25. 建立運輸模型建立運輸模型 .2說明什么？說明什么？ 運輸問題3 運輸問題應用舉例運輸問題應用舉例Ex. 4 (生產(chǎn)調度問題生產(chǎn)調度問題) 某制冰廠每年某制冰廠每年1 4 季度必須供季度必須供應并塊應并塊 15、20、25、10（千噸）（千噸）. .已知該廠各季度冰已知該廠各季度冰 塊的生產(chǎn)能力及冰塊的單位成本如表塊的生產(chǎn)能力及冰塊的單位成本如表. . 如果生產(chǎn)出來如果生產(chǎn)出來的冰塊不在當季度使用，每千噸冰塊存儲一個季度的冰塊不在當季度使用，每千噸冰塊存儲一個季度費用為費用為4（千元）（千元）. .又設該制冰廠每年第又設該制冰廠每年第3季度末對貯季度末對貯冰庫進行清庫維修冰庫進行清庫維

48、修. .問應如何安排冰塊的生產(chǎn)，可使問應如何安排冰塊的生產(chǎn)，可使該廠全年生產(chǎn)、該廠全年生產(chǎn)、存儲費用最少？存儲費用最少？季季 度度 生產(chǎn)能力（千噸）生產(chǎn)能力（千噸） 單位成本（千元）單位成本（千元） 1 25 5 2 18 7 3 16 8 4 15 53 運輸問題應用舉例季季 度度 生產(chǎn)能力（千噸）生產(chǎn)能力（千噸） 單位成本（千元）單位成本（千元） 1 25 5 2 18 7 3 16 8 4 15 5 Bj Ai B1 B2 B3 B4 ai A1 25 A2 18 A3 16 A4 15 bj 15 20 25 10 解：解：5B54913M0MMMMM0005118179137 運輸問

49、題Ex. 5 ( (運量有界的運輸問題運量有界的運輸問題) ) 6 5 7 bj 10762 A2 84 53 A1 ai B3 B2 B1 BjAi表表 1 1 5 2 4 A2 3 3 4 A1 B3 B2 B1 dij表表 2 2 表表1 給出一個運輸問題給出一個運輸問題. .現(xiàn)在規(guī)定產(chǎn)地現(xiàn)在規(guī)定產(chǎn)地 Ai 至銷地至銷地 Bj 的運量不能超過的運量不能超過 dij , , 由表由表 2 2 給定給定. . 試建立運輸問題試建立運輸問題 . .解解： 虛設虛設 Dij (i=1,2; j=1,2,3) 6 6個點，個點，Dij 既作產(chǎn)地，既作產(chǎn)地，又作銷地，其產(chǎn)量、銷量都為又作銷地，其產(chǎn)量

50、、銷量都為 dij . . 產(chǎn)地產(chǎn)地 Ai 的物資只可的物資只可運送給運送給 Dij , 而而 Dij 的物資只可運送給的物資只可運送給 Bj ,或送給自身或送給自身.3 運輸問題應用舉例 BjAi D11 D12 D13 D21 D22 D23 B1 B2 B3 ai A1 D11 D12 D13 A2 D21 D22 D23 bj 6 5 7 bj 10762 A2 84 53 A1 ai B3 B2 B1 BjAi表表 1 1 5 2 4 A2 3 3 4 A1 B3 B2 B1 dij表表 2 2 8 104330000305040000206074334254257563321303124244214 運輸問題Ex. 6 ( (空車調度問題空車調度問題) ) 某航運公司承擔六個港口城市某航運公司承擔六個港口城市 A、B、C、D、E、F 的四條固定航線的物資運輸任的四條固定航線的物資運輸任務務. . 已知各條航線的起點、終點城市及每