運輸問題的數學模型和應用舉例

1、運輸問題的數學模型和應用舉例運輸問題的數學模型表上作業(yè)法產銷不平衡的運輸問題運輸問題應用舉例 運輸問題（Transportation Problem，簡記為TP）是一類常見而且極其特殊的線性規(guī)劃問題.它最早是從物資調運工作中提出來的，是物流優(yōu)化管理的重要的內容之一 。 從理論上講，運輸問題也可用單純形法來求解，但是由于運輸問題數學模型具有特殊的結構，存在一種比單純形法更簡便的計算方法 表上作業(yè)法，用表上作業(yè)法來求解運輸問題比用單純形法可節(jié)約計算時間與計算費用.但表上作業(yè)法的實質仍是單純形法。 1.1 產銷平衡運輸問題的數學模型1 運輸問題的數學模型及其特點 設某種物資共有 m 個產地 A1，A

2、2，Am，各產地的產量分別是a1，a2 ，am；有n 個銷地 B1，B2，Bn ，各銷地的銷量分別為b1 ，b2，bn . 假定從產地Ai（i =1，2，m）向銷地Bj（j =1，2，n）運輸單位物資的運價是cij ，其中 .問怎樣調運才能使總運費最??？ 設 xij 表示產地 Ai 運往銷地 Bj (i=1,2,m; j=1,2,n) 的運量. 銷地產地 B1 B2 Bn產量 A1 x11c11 x12c21 x1n c1n a1 A2 x21c21 x22c22 x2nc2n a2 Am xm1cm1 xm2cm2 xmncmn am銷量 b1 b2 bn 運輸表注意 : cij 在左下角

3、xij 在右上角 1.2 運輸問題數學模型的特點平衡運輸問題的約束方程系數矩陣 A矩陣A有m+n行，每行的特點：前m行有n個1，這n個1連在一起，其余元素為0；后n行每行有m個1，其余元素為0。矩陣A有mn列，每一列只有兩個元素為1，其余元素均為0。列向量Pij =(0,，0，1，0，,0,1,0,0)T，其中兩個元素1分別處于第i行和第m+j行,即將矩陣A分塊，特點是：前m行構成m個mn階矩陣,而且第k個矩陣只有第k行元素全為1，其余元素全為0（k=1，m）；后n行構成m個n階單位陣。其中e1是元素全為1的n維行向量，In為n階單位矩陣。定理 1 平衡運輸問題必有可行解，也必有最優(yōu)解. 又因

4、為 ，對于任一可行解有目標函數值 ，對于求極小化問題，目標函數值有下界，則必有最優(yōu)解. 證明:則取又所以 ，是問題的一個可行解. 證明：定理2 說明：基可行解包含m+n-1個基變量.定理 2 平衡運輸問題的約束方程系數矩陣 A 和增廣矩陣 的秩相等，且等于 m+n-1 . 即 2. 由 的第二至m+n行和前n列及 對應的列交叉處元素構成m+n-1階方陣D 非奇異。前m行相加之和減去后n行相加之和結果是零向量，說明m+n個行向量線性相關，因此 的秩小于m+n； 證明系數矩陣A及其增廣矩陣的秩都是m+n-1 因此 的秩恰好等于m+n-1，又D本身就含于A中，故A的秩也等于m+n-1 可以證明：m+

5、n個約束方程中的任意m+n-1個都是線性無關的。定理 3 平衡運輸問題的約束方程系數矩陣 A 的所有各階子式只取 0，1 或 -1 三個值.定理 4 如果平衡運輸問題中的所有產量 ai 和銷量 bj都是整數，那么，它的任一基可行解都是整數解.Proof :設 x 是 Ax = b 的任一基可行解，B 為對應的基矩陣，則 其中 Bt 是用 b 中對應的 m+n-1元素替換 B 的第t 列元素得到的矩陣. 顯然，由定理 3 知，det Bt 是個整數， det B= ，因此， 都是整數.其基變量為定理 4 如果平衡運輸問題中的所有產量 ai 和銷量 bj都是整數，那么，它的任一基可行解都是整數解.

6、定義 1 將變量 在調運表中所對應的空格記作 ，下文將稱為格點 或格 ，而 的系數列向量 也稱作格點 所對應的系數列向量，若 為基變量，則 稱為基格，否則是非基格。 凡是能排列成（其中 互不相同， 互不相同）形式的變量集合，稱為一個閉回路，其中諸變量稱為這個閉回路的頂點.定義 2 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如：變量集合變量集合或格組或格組3、每一行（或列）若有閉回路的頂點，則有兩個頂點；4、每兩個頂點格子的連線

7、都是水平的或垂直的；1、閉回路中頂點的個數必為大于或等于4的偶數.閉回路的幾何特征：2、每一個頂點格子都是 90轉角點； 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思考： 下面的折線構成的封閉曲線連接的頂點變量哪些不可能是閉回路？為什麼？（a） （b） （c） （d） （e）閉回路的代數性質：性質 1 構成閉回路的變量組對應的列向量組必線性相關.證明由直接計算可知故該向量組線性相關.性質 2 分組構成閉回路，則該變量組對應的列

8、向量組是線性相關的.推論 1 若變量組對應的列向量組線性無關，則該變量組一定不包含閉回路.若變量組 中有一個部性質2的證明可借助性質1和高等代數中“若向量組中部分向量線性相關，則整個向量組就線性相關”的定理得到。在變量組 中，若有某一個變量 xij 是它所在的行（第 i 行）或列（第 j 列）中出現于（*）中的唯一變量，則稱該變量 xij 是該變量組的一個孤立點.定義 3閉回路的特征注：孤立點不會是閉回路上的點。 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

9、x42 x43 x44 x45性質 3 若一變量組中不包含任何閉回路，則該變量組必有孤立點.注：性質3的逆命題不一定成立。變量組 中雖有孤立點 ，但包含閉回路 。證明 :用反證法設變量組（*）對應的列向量組線性無關，但該變量組包含一個以其中某些變量為頂點的閉回路，則由性質 2 知，這些變量對應的列向量必線性相關，與假設矛盾.定理 5 變量組 對應的列向量組線性無關的充要條件是該變量組中不包含任何閉回路.設有一組數 使得 由于變量組（*）中不包含任何閉回路，由性質 3 可知其中必有孤立點，不妨設 為孤立點，但 仍不包含閉回路，其中還有孤立點,與前面類似分析可證 k2= 0. 同理得 k3 = k

10、4 = kr = 0這就證明了向量組（*）線性無關.又不妨設 是（*）在第i1行上唯一的變量，這時由pij的特征，（1）的左端第i1個分量和為k1，而右端為0，推論 2 平衡運輸問題中的一組 m + n - 1 個變量能構成基變量的充要條件是它不包含任何閉回路. 該推論給出了運輸問題的基可行解中基變量的一個基本特征：基變量組不含閉回路. 這就是基可行解在表上的一個表現，利用它來判斷 m + n 1 個變量是否構成基變量組，就看它是否包含閉回路.這種方法簡便易行，它比直接判斷這些變量對應的列向量是否線性無關要簡便得多. 利用基變量的這個特征，將可以導出求平衡運輸問題的初始基可行解的一些簡便方法.

11、 表上作業(yè)法（又稱運輸單純形法）是根據單純形法的原理和運輸問題的特點，設計的一種在表上運算的求解運輸問題的簡便而有效的方法.2 表上作業(yè)法主要步驟：1、求一個初始調運方案（初始基可行解）；2、判別當前方案是否為最優(yōu)，若是則迭代停止，否則 轉下一步；3、改進當前方案，得到新的方案（新的基可行解）， 再返回 2 。 已知某商品有三個產地A1、A2、A3和四個銷地B1、B2、B3、B4 ，產量、銷量及單位運價如表.問應如何調運，在滿足各銷地需要的情況下，使總的運費支出為最少？ 一、初始方案的確定1、西北角法 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 2

12、0 A3 5 6 3 4 10 bj 50 25 10 15例 1 50解：51010205規(guī)則:從運輸表的西北角開始,優(yōu)先安排編號小的產地和銷地的運輸任務.填了幾個數字？注意 : 在填入一個數時，如果行和列同時飽和， 規(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 15500 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 15505101020550例1的初始調運方案（西

13、北角法）2、最小元素法 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 15規(guī)則:優(yōu)先安排單位運價最小的產地與銷地之間的運輸 任務，即就近供應。40102551010注意 : 在某行（或列）填入一個數時，如果行和列同時飽和，規(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 100010102050填了幾個數字？定理 6 用西北角法或最小元素法得到的初始解是平衡運輸問題的基可行

14、解， m+n-1 個填入數字的格子對應的是基變量.證明 :首先，得到的初始解 為可行解是顯然的. 其次，由于行列數共有 m+n ，而按填數字的方法,除填最后一個數時，劃去一行一列外，每填一個數劃去一行或一列. 因此, 共填 m+n-1 個數. 最后，證明所填 m+n-1 個數對應的變量組不含閉回路.用反證法若含有閉回路 不妨設此閉回路如右（其他情形同理可證） 不妨設填 后劃去行，故 必須較 先填，且填后劃去的是列，從而 必須較 先填，且填后劃去的是行，而這又說明 必須較 先填，且填后劃去的是列，這又得到 必須較 先填，且填后劃去的是行，這樣就得到了矛盾，所以，填數的 m+n-1 個格子對應的變

15、量組不含閉回路，從而，證得了本定理. 關鍵1、填一個數字劃去一行或一列 不產生閉回路； 2、填一個數字只劃去一行或一列 填滿m+n-1個數. BjAi B1 B2 ai A1 8 2 5 A2 3 1 4 bj 6 3 315按最小元素法3、伏格爾法 (元素差額法) 最小元素法的缺點：為了節(jié)省一處的費用，有時造成在其它處要花幾倍的運費。所以我們考慮若一產地的產品不能按最小運費就近供應，就考慮次小運費，這就有一個差額，差額越大，說明不能按最小運費調運時，運費增加越多。 因而，對差額最大處，就優(yōu)先采用最小運費調運，這就是伏格爾法的基本思想 BjAi B1 B2 ai A1 8 2 5 A2 3 1

16、 4 bj 6 3 差額 6 2 差額 5 1315 BjAi B1 B2 ai A1 8 2 5 A2 3 1 4 bj 6 3 342注：伏格爾法給出的初始解比用最小元素法給出的初始解更接近最優(yōu)解。優(yōu)先安排差額最大的所在行或列的單位運價最小的產地與銷地之間的運輸任務規(guī)則：計算各行各列的最小元素與次小元素的差額， 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 155052040例1的初始調運方案（伏格爾法）101510二、最優(yōu)性檢驗定理 7 設 是平衡運輸問題的一組基變量， 是非基變量，則格

17、組 中必存在唯一的閉回路.證明 : （1）存在性：設與變量組 所對應的系數列向量組為 ，則它們一定線性相關，據定理5 ，變量組 所對應的格子組必包含閉回路，而且這個閉回路必包含非基變量 所對應的非基格 。否則，就說基格組（或一部分）構成了閉回路，這與基的定義和定理5相矛盾。（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

18、10 15401025510101、閉回路法+1-1+1-1 BjAi B1 B2 B3 B4 A1 A2 A3檢驗數表-5-10 6 6 6檢驗數檢驗數 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+1-1+1-1閉回路的經濟解釋:在已給出的初始解的表中，可以從任意一個空格出發(fā)，如 ，若讓 的產品調運1個單位給 ，為了保持產銷平衡，就要依次調整：在 處減少一個單位，在 處增加一個單位，在 減少一個單位，即構成了以空格 為起點，其它為數字格的閉回路。可見這樣調整得運

19、費的改變量為：2、位勢法（對偶變量法）約束方程的系數矩陣的秩為m+n -1由于xj 的檢驗數 ui 稱為行位勢，vj 稱為列位勢解上面第一個方程，將ui、vj代入第二個方程求出 。 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檢驗數表-5-10 6 6 6-2-120273見 例 1 最小元素法得到的初始基可行解10053-12-5 若 ，則此時的運輸方案為最優(yōu)的 定理 8 檢驗數 與初始給定 的取值無關。 （下面的證明摘自教材最優(yōu)化方法書后參

20、考文獻1）證明： 引理1 引理2 由此定理可知，我們用位勢法求檢驗數時給定初始的Vn=0是合理的，從而計算出的ij 是唯一的。三、基可行解的改進 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檢驗數表-5-10 6 6 6選擇進基變量則取非基變量 xst 為進基變量確定出基變量調整量則基變量 xkl 出基（運量擦去）調整方法：在該閉回路上，奇點運量加 ，偶點減去 153010 6 5 4 2010 1-5 6 520

21、 6 6 4 5 6 因為 ，所以此運輸方案為最優(yōu)方案 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 1550252020例1的最優(yōu)調運方案101510model:!3發(fā)點4收點產銷平衡的運輸問題;sets: cd/1.3/: capacity; xd/1.4/: demand; links(cd,xd): cost, variable;endsets!目標函數; min=sum(links: cost* variable);!需求約束; for(xd(j): sum(cd(i): varia

22、ble(i, j)=demand(j);!產量約束; for(cd(i): sum(xd(j): variable(i, j)=capacity(i);!這里是數據;data: capacity= 70 20 10 ; demand=50 25 10 15;cost= 10 5 2 3 4 3 1 2 5 6 3 4;enddataend求解例1的lingo源代碼求解例1的lingo輸出報告練習1 某公司經銷甲產品。它下設三個加工廠。每日的產量分別是：A1為7噸，A2為4噸，A3為9噸。該公司把這些產品分別運往四個銷售點。各銷售點每日銷量為：B1為3噸，B2為6噸，B3為5噸，B4為6噸。產銷

23、平衡表見表1。已知從各工廠到各銷售點的單位產品的運價為表2所示。問該公司應如何調運產品，在滿足各銷點的需要量的前提下，使總運費為最少。 表1 產銷平衡表表2 單位運價表 BOOK P122 例例表3 最優(yōu)調運方案表4 檢驗數表所以調運的總運費最小是85元。解：求初始基本可行解時，當minai,bj=ai=bj 時，此時要同時劃去第i行及第j列，為了確保調運表上仍有m+n-1個基變量的取值，需要在所劃去的第i行或第j列任一空格上加0,表示這個格中的基變量的取值是0，這樣就出現了退化解。 若在閉回路上有幾個偶點處的運量等于，則可任取其中一個作為出基變量（運量擦去），其余幾個點的值調整后變?yōu)?，但應

24、填入，說明這些變量還在基內，這時就出現了退化。(1)有無窮多最優(yōu)解.最終解中有非基變量檢驗數為零時，以此非基變量為換入變量，可求得另一基最優(yōu)解。基最優(yōu)解的任一凸組合都是最優(yōu)解。 BOOK P136 例表上作業(yè)法計算中的兩個問題(2)退化解.解中非零基變量個數小于m+n-1時，為退化解。一般在下面兩種情況下出現： BOOK P138 例1.4.5+例設數學模型為 關于極大化運輸問題的求解例2 下列矩陣C是Ai到Bj的噸公里利潤, 產量、銷量及其單位利潤合并于下表，問運輸部門如何安排運輸方案使總利潤最大？ cij BjAi B1 B2 B3 ai A12 58 9 A29107 10 A3654

25、12 bj 8 14 9方法I：將極大化問題轉化為極小化問題。設極大化問題的運價表為C=（cij）mn，用一個較大的數M（Mmaxcij）去減每一個cij得到矩陣C/=（c/ij）mn ，其中c/ij=Mcij0， 將C/作為極小化問題的運價表，用表上作業(yè)法求出最優(yōu)解，目標函數值為： cij BjAi B1 B2 B3 ai A12 58 9 A29107 10 A3654 12 bj 8 14 9 BjAi B1 B2 B3 ai A1 8 5 2 9 A21 03 10 A3 4 5 6 12 bj 8 14 9用最小元素法求初始運輸方案910840 BjAi B1 B2 B3 A1 8

26、4 A2 2 2 A3檢驗數表 由于檢驗數全部非負,因此該初始運輸方案也是最優(yōu)運輸方案, 則最大利潤為： Z=89+1010+68+54=240方法II: 所有非基變量的檢驗數ij0時最優(yōu).求初始運輸方案可采用最大元素法.如上例,用最大元素得到的初始運輸方案:8 14 9求檢驗數:11=8,12=4,21=2,23=2,全部非正,得到最優(yōu)解運輸方案,結果與第一種方法相同.當當3 產銷不平衡的運輸問題當可以虛設一個產地 Am+1, 其產量為 并假設產地 Am+1 運往各銷地的單位運價為 cm+1, j = 0 ( j = 1 , 2 , , n ) . 則原問題可轉化為平衡運輸問題： 產大于銷，

27、可通過虛設銷地，類似建立平衡運輸模型例3已知運輸問題由表給出，試建立運輸模型 . 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本題產量為25，銷量為29，是銷大于產問題 虛設一個產地 A3，由于并沒有生產，所以運價為零，得運輸模型. 如果各銷地不滿足時，單位缺貨費為 4，3，7，則運輸模型為437 已知運輸問題由表給出，如果產地 Ai 的產量必須運走，試建立運輸模型 . BjAi B1 B2 B3 ai A14 23 10 A2564

28、 15 A3345 20 最低需求量 10 10 10例4 BjAi B1 B2 B3 B4 ai A14 23 10 A2564 15 A3345 20 bj 10 10 10 15解:這是一個產大于銷的運輸問題.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 三個銷地的最低需求為

29、30，最高需求不限. 根據現有產量，B3 至多能得到 25. 建立運輸模型 .練習2 設有三個化肥廠(A，B，C)供應四個地區(qū)(，)的農用化肥。假定等量的化肥在這些地區(qū)使用效果相同。各化肥廠年產量，各地區(qū)年需要量及從各化肥廠到各地區(qū)運送單位化肥的運價如表1所示。試求出總的運費最節(jié)省的化肥調撥方案。BOOK P145 例解：這是一個產銷不平衡的運輸問題，總產量為160萬噸，四個地區(qū)的最低需求為110萬噸，最高需求為無限。根據現有產量，第個地區(qū)每年最多能分配到60萬噸，這樣最高需求為210萬噸，大于產量。為了求得平衡，在產銷平衡表中增加一個假想的化肥廠D，其年產量為50萬噸。由于各地區(qū)的需要量包含

30、兩部分，如地區(qū)，其中30萬噸是最低需求，故不能由假想化肥廠D供給，令相應運價為M(任意大正數)，而另一部分20萬噸滿足或不滿足均可以，因此可以由假想化肥廠D供給，按前面講的，令相應運價為0。對凡是需求分兩種情況的地區(qū)，實際上可按照兩個地區(qū)看待。這樣可以寫出這個問題的產銷平衡和單位運價表(表2)。產銷平衡表和單位運價表合并于下面的表2根據表上作業(yè)法計算，可以求得這個問題的最優(yōu)方案如表3所示 某制冰廠每年1 4 季度必須供應冰塊 15、20、25、10（千噸）.已知該廠各季度冰 塊的生產能力及冰塊的單位成本如表. 如果生產出來的冰塊不在當季度使用，每千噸冰塊存儲一個季度費用為4（千元）.又設該制冰

31、廠每年第3季度末對貯冰庫進行清庫維修.問應如何安排冰塊的生產，可使該廠全年生產、存儲費用最少？4 運輸問題應用舉例例 5 (生產調度問題)季 度 生產能力（千噸） 單位成本（千元） 1 25 5 2 18 7 3 16 8 4 15 5季 度 生產能力（千噸） 單位成本（千元） 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 某航運公司承擔六個港口城市 A、B、C、D、E、F 的四條固定航線的物資運輸任務.

32、已知各條航線的起點、終點城市及每天航班數見表1，假定各條航線使用相同型號的船只，又各城市間的航程天數見表2.例6(空車調度問題) 又知每條船只每次裝卸貨的時間各需一天，則該航運公司至少應配備多少條船，才能滿足所有航線的運貨需求？航線起點城市終點城市每天航班數1ED32BC23AF14DB1表1 到從ABCDEFA0121477B1031388C23015557851703F7852030表2解：該公司所需配備船只分兩部分.1、載貨航程需要的周轉船只數航線起點城市終點城市每天航班數1ED32BC23AF14DB1表1 到從ABCDEFA0121477B1031388C2

33、3015557851703F7852030表2 如航線1，在港口E 裝貨1 天，E 至 D 航程17天，在D 卸貨1天，總計19天. 每天3 航班，故該航線周轉船只需57條.航線裝貨天數航程天數卸貨天數小計航班數需周轉船只數11171193572131521031719194113115115累計共需周轉船只數91條.2、各港口間調度所需船只數港口城市每天到達每天需求余缺數A01-1B12-1C202D312E03-3F101 港口每天到達與需要的船只不同，如表.為使配備船只數最少，應做到周轉的空船數為最少. 建立運輸模型，C、D、F 為空船的產地，A、B、E 為銷地，單位運