第5章 運輸模型

1、第5章 運輸模型 5.1 運輸問題及其數(shù)學模型 5.2 5.2 表上作業(yè)法表上作業(yè)法 5.2.1 初始方案的確定 5.2.2 最優(yōu)性檢驗 5.2.3 非最優(yōu)方案的調整 5.2.4 產銷不平衡問題的解法 5.3 運輸模型的應用 運輸模型是線性規(guī)劃諸多模型中較早引起人們關注的一類模型，由美國學者希奇柯克（Hitchcock，1941）和庫普曼（Koopmans，1947）提出。 中國 “圖上作業(yè)法”（1958年） 1975年康托洛維奇和庫普曼因資源配置理論研究獲得諾貝爾經濟學獎（丹茨格）（24、12、4）（日內瓦國際應用系統(tǒng)分析研究所） 運輸模型是線性規(guī)劃諸多模型中的特例，其約束方程組對應的系數(shù)矩

2、陣具有特殊的結構，使得有可能找到比單純形法更為簡便的求解方式。 運輸問題的專門求解方法專門求解方法不僅適用于運輸問題本身，還適用于其他相當多的應用問題（如指派問題），更使其得到人們的高度重視和深入的系統(tǒng)研究。 在經濟建設中經常會碰到大宗物資的調運問題。如煤、鐵、木材、糧食等大宗物資，在全國有若干生產基地，根據(jù)現(xiàn)已有的交通網(wǎng)絡，應該如何制定調運方案，將這些物資運往各消費地點。1）“產地”貨物發(fā)出的地點2）“銷地”貨物接收的地點3）“產量”各產地的可供貨量4）“銷量”各銷地的需求數(shù)量 【運輸問題的描述】 運輸問題就是研究如何組織調運，在滿足各銷地需求的前提下，追求總的運費（或里程、時間等）達到最少

3、？ 運輸問題所建立的模型就稱為運輸模型運輸模型。5.1 運輸問題及其數(shù)學模型【例例1 1】 某飲料集團在國內有3個生產工廠，分布在城市 A1，A2，A3；其一級分銷商有4個，分布在城市B1，B2，B3 ， B4 ?，F(xiàn)已知每月各生產工廠的產量、各分銷商的需求量； 以及從Ai到Bj的每噸飲料的運費cij（見下表）。 銷地銷地產地產地B B1 1B B2 2B B3 3B B4 4產量產量A A1 16 63 32 25 55 5A A2 27 75 58 84 42 2A A3 33 32 29 97 73 3銷量銷量2 23 31 14 4為發(fā)揮集團優(yōu)勢，公司需要統(tǒng)一籌劃運銷問題，求使為發(fā)揮集團

4、優(yōu)勢，公司需要統(tǒng)一籌劃運銷問題，求使運費最小運費最小的的調運方案。調運方案。解：建立該運輸問題的解：建立該運輸問題的LPLP模型如模型如下下343332312423222114131211792348 57523621xxxxxxxxxxxxminBAxjiij）目標函數(shù)：的數(shù)量（噸）到銷地為每月從產地設）決策變量：4,3,2,1;3,2,104132325.3342414332313322212312111343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxtsij）約束條件：運輸問題的一般提法： 設某種物資有m個產地 ，其產量分別為 ；有n

5、個銷地 ，其銷量分別為 ；從 到 的單位運價為 。問應該如何組織調運才能使總的運費最少？miAi, 2 , 1iajbnjBj, 2 , 1iAijcjB設 為把這種物資從Ai運到Bj的數(shù)量，簡稱為Ai至Bj的運量運量；設z為總運費，則一般運輸問題及其數(shù)學模型可以簡潔地表示為下表這種形式，稱為表格形式的一般運輸模型表格形式的一般運輸模型，簡稱表式表式運輸模型運輸模型。ijxp136p136表式運輸模型 銷地銷地產地產地A1A2Am產量產量a1a2amB1B2Bn銷量銷量b1b2bnc11c12c1nc21 c22c2ncm1cm2cmn x11 x12 x1nx21 x22 x2n xm1 x

6、m2 xmnnjmixbxaxtsxcminijjmiijinjijminjijij, 2 , 1;, 2 , 10. . 1111產銷平衡產銷平衡njmixbxaxtsxcminijjmiijinjijminjijij, 2 , 1;, 2 , 10. . 1111產大于銷產大于銷njmixbxaxtsxcminijjmiijinjijminjijij, 2 , 1;, 2 , 10. . 1111產小于銷產小于銷【運輸模型運輸模型 系數(shù)矩陣系數(shù)矩陣】111111111111111111Am m行行n n行行 【討論】運輸模型系數(shù)矩陣的特征？ 表面任意一個運輸模型系數(shù)矩陣同一個與之規(guī)模相當?shù)?/p>

7、普通LP模型的系數(shù)矩陣相比都大為簡潔，且其中只含有0和1這兩個元素，且0的個數(shù)遠遠多于1的個數(shù)，一般我們把這樣的矩陣稱為稀疏陣稀疏陣。 深層次對任意產銷平衡的運輸模型來說，其系數(shù)陣的前m行之和等于后n行之和。意味著？意味著？ 可以證明：平衡模型的系數(shù)陣和增廣陣的秩均為m+n-1，這也意味著平衡模型的基本可行解所含基變量的個數(shù)必為m+n-1個。 【結論】m+n-1 【討論】上述運輸問題所建立的LP模型如果用傳統(tǒng)的 單純形法進行求解會出現(xiàn)什么情況？ 【友情提示友情提示】 1）表上作業(yè)法僅僅適用于產銷平衡產銷平衡的運輸問題 2）表上作業(yè)法基于一種作業(yè)表 “產銷平衡及運價表”特征？特征？5.2 5.2

8、 表上作業(yè)法表上作業(yè)法 用單純形法求解LP式運輸模型，必須刪掉一個函數(shù)約束，而且計算量很大，但表上作業(yè)法不必如此費力，而是另辟蹊徑。 表上作業(yè)法是一種專門求解運輸問題的特殊方法，其實質仍是單純形法，只是具體計算和術語有所區(qū)別。 與一般的LP問題不同的是，平衡運輸問題總是存在最優(yōu)解。 銷地銷地產地產地B B1 1B B2 2B B3 3B B4 4產量產量A A1 16 63 32 25 55 5A A2 27 75 58 84 42 2A A3 33 32 29 97 73 3銷量銷量2 23 31 14 41010 表上作業(yè)法的基本思想及基本步驟 【基本思想基本思想】類似于單純形法，只是叫法

9、不同而已，如基本 可行解稱為“方案”；迭代稱為“調整改進”等。 【基本步驟基本步驟】 1）確定初始方案； 2）對初始方案進行最優(yōu)性檢驗； 3）調整、改進非最優(yōu)方案； 4）直至得到最優(yōu)方案（惟一方案或多重方案）運輸問題求解思路運輸問題求解思路確定初始方案確定初始方案（初始基本可（初始基本可行解）行解） 輸出最優(yōu)方案輸出最優(yōu)方案改進調整改進調整（換基迭代）（換基迭代）判斷是判斷是否最優(yōu)否最優(yōu)結果結果是是否否5.2.1 5.2.1 初始方案的確定初始方案的確定 確定初始方案的方法有很多，原理各不相同確定初始方案的方法有很多，原理各不相同 左上角法（西北角法、階梯法）最小元素法最小元素法最大差額法最大

10、差額法 Russell概算法銷地銷地產地產地B1B2B3B4產量產量A163255A275842A332973銷量銷量231410左上角法左上角法 最小元素指？ 最小元素法的基本思想？最小元素法“最小運價最小運價”“就近運給就近運給” 先給作業(yè)表中最小運價那格安排運量，然后劃去該運價所在的行或列；繼續(xù)這樣做，每次總在表中剩余運價的最小元素那格確定運量，直至求出初始方案為止。銷地銷地產地產地B1B2B3B4產量產量A163255A275842A332973銷量銷量231410(0)(0)初始方案：初始方案：x x1111=2,x=2,x1313=1,x=1,x1414=2,x=2,x2424=2

11、,x=2,x3131=0,x=0,x3232=3=3，Z=38Z=38【結論結論】最小元素法確定初始方案的4條原則 運量選擇時必須遵循產、銷量比較取其小的原則 確定某格的運量后，其所在行或列其余格運量為0，并劃去滿足約束的行或列，同時滿足只能劃去其中之一 中間遇到0運量也必須畫上 最后一個格產地、銷地同時滿足，同時劃去最小元素法確定的有效的有效的初始方案滿足 初始作業(yè)表中有 m+n-1m+n-1 個畫圈數(shù)字（運量） 畫圈數(shù)字（運量）恰好符合產銷平衡運輸問題的約束條件 作業(yè)表中不存在以畫圈數(shù)字為頂點的閉回路【閉回路閉回路】從表中任一畫圈數(shù)字所在格出發(fā)，沿水平或垂直方 向前進，當碰到另一個畫圈數(shù)字

12、后，可沿原方向繼 續(xù)前進，也可以轉90繼續(xù)前進，如此進行下去最 終回到出發(fā)點。 注意：用最小元素法得到的初始方案肯定不會形成閉回路！銷地銷地產地產地B1B2B3B4產量產量A163255A275842A332973銷量銷量231410B B1 1B B2 2B B3 3B B4 4B B5 5A A1 1X11X12A A2 2X23X25A A3 3X31X35A A4 4X42X43 最大差額法 “差額” 行差和列差 “最大差額” 兩最小元素之差（正值） 不能按最小運費就近供應，就考慮次小運費 差額越大，說明當不能按最小運費調運時，運費增加的越多v5.2.2 5.2.2 最優(yōu)性檢驗最優(yōu)性檢

13、驗v確定初始方案后，就要對它進行最優(yōu)性檢驗，即檢驗初始基本可行解對應的目標函數(shù)值是否達到最優(yōu)。v運輸問題要求目標函數(shù)求最小值，故當檢驗數(shù) 時，表示該方案為最優(yōu)。v計算檢驗數(shù)的方法有 vA 位勢法vB 閉回路法0ij 1 1、位勢法、位勢法 A 兩個位勢量：產地的位勢量 ；銷地的位勢量 B 兩個基本公式：1）該公式僅僅適用于基變量所在格（基格）2）決策變量的檢驗數(shù)計算公式：jiijvucjiijijvuciujv銷地銷地產地產地B1B2B3B4產量產量uiA162 321 52 50A2758422-1A330 23 973-3銷量銷量2314vj6525-2217105非基變量非基變量x x1

14、212的檢驗數(shù)的檢驗數(shù) 1212= c= c12 12 u u1 1 v v2 2 = -2= -2，即讓非基變量，即讓非基變量x x1212從從0 0增增到到1 1，可使總運費減少，可使總運費減少2 2百元。百元。 2 2、閉回路法、閉回路法 這里的閉回路是指以非基變量的格子為始點和終點，而其余頂點均為畫圈數(shù)字（基變量）的一條封閉回路，用水平或者垂直線向前畫，每碰到一數(shù)字格轉90度后繼續(xù)前進，直到回到始點。 偶點（偶點（+ +） 奇點（奇點（- -） 結論結論1 1：閉回路都是唯一的。：閉回路都是唯一的。 結論結論2 2：任一非基變量的檢驗數(shù)都等于它的閉回路上所有：任一非基變量的檢驗數(shù)都等于

15、它的閉回路上所有偶點運價的總和與所有奇點的運價總和之差。偶點運價的總和與所有奇點的運價總和之差。 5.2.3 非最優(yōu)方案的調整 當作業(yè)表中出現(xiàn)負檢驗數(shù)時，表明此方案仍不是最優(yōu)方案，需要進行調整，調整時仍用閉回路法閉回路法。（1 1）進基變量的確定）進基變量的確定若同時有多個負檢驗數(shù)一樣最小，則選其中最小運價所對應的那個進基。（2 2）離基變量的確定）離基變量的確定在進基變量的閉回路上，按確定離基變量，同時也確定了調整量t。若有多個奇點的運量值一樣，則選其中最大運價所對應的那個離基。（3 3）非最優(yōu)方案的調整）非最優(yōu)方案的調整所有偶點的運量 + t 所有奇點的運量 - t0ijijmin為奇點i

16、jpqijxxxmint x x12 12 進基進基最小調整量為最小調整量為2 2，即，即t=2t=2， x x11 11 離基離基銷地產地B1B2B3B4產量A162 3 x1221 52 5A275842 2A330 23 973銷量2314+ +- -+ +- -銷地銷地產地產地B B1 1B B2 2B B3 3B B4 4產量產量A A1 16 6 3 3 2 21 1 5 52 2 5 5A A2 27 75 58 84 42 2 2 2A A3 33 3 2 2 9 97 73 3銷量銷量2 23 31 14 4 調整后新方案：調整后新方案：x x1212=2,x=2,x1313

17、=1,x=1,x1414=2,x=2,x2424=2,x=2,x3131=2,x=2,x3232=1=1，Z=34Z=34 22 1 定理定理1(惟一最優(yōu)解的判定定理惟一最優(yōu)解的判定定理) 如果在表上作業(yè)法得到的最終表如果在表上作業(yè)法得到的最終表中中,非基變量的檢驗數(shù)全都大于零非基變量的檢驗數(shù)全都大于零,則該運輸問題存在惟一最優(yōu)解則該運輸問題存在惟一最優(yōu)解。 定理定理2(多重最優(yōu)解的判定定理多重最優(yōu)解的判定定理)對于一個運輸問題對于一個運輸問題,在得到的第一在得到的第一個最優(yōu)解的最終表中個最優(yōu)解的最終表中,若至少存在一個檢驗數(shù)為零的非基變量若至少存在一個檢驗數(shù)為零的非基變量,并并且在以這個非基

18、變量為出發(fā)點的閉回路上且在以這個非基變量為出發(fā)點的閉回路上,在需要減少運輸量的在需要減少運輸量的頂點中頂點中,最小運量不等于零最小運量不等于零,那么該運輸問題存在多重最優(yōu)解那么該運輸問題存在多重最優(yōu)解。 運輸問題的多重解運輸問題的多重解運輸問題多重解運輸問題多重解B1B2B3B4產量A13113107A219284A3741059銷量3656 5.2.4 產銷不平衡問題的解法 A 產大于銷 虛設銷地（經濟意義：貯存）虛設銷地（經濟意義：貯存） B 產小于銷 虛設產地（經濟意義：脫銷）虛設產地（經濟意義：脫銷） 虛設的產地的產量或銷地的銷量等于產銷量之差的絕對值，且其運價全部為0。 用最小元素法確定初始方案時，盡管虛設產地或銷地對應的運價為0，均為最小，但我們先不考慮它，先給有實際運輸任務的其他產銷地之間安排運量，這樣處理往往能獲得較好的初始方案，減少調整的次數(shù)（為什么？）。 5.3 運輸模型的應用 短缺資源的分配問題 轉運問題 生產調度問題（*） 這里所說的生產調度問題生產調度問題是指對某產品在一個總的計劃周期內的某項既定總生產指標（總產量），應怎樣分解到各個生產周期，才能既保證在總計劃期內完成該項總生產指標，又能使總生產費用最少。案例 拖拉機生產調度問題前進拖拉機廠與農機供銷站簽訂了一項生產100臺某種