第5章 運(yùn)輸模型

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

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

3、的運(yùn)費(fèi)（或里程、時(shí)間等）達(dá) 到最少？ 運(yùn)輸問題所建立的模型就稱為運(yùn)輸模型運(yùn)輸模型。 5.1 運(yùn)輸問題及其數(shù)學(xué)模型 【例例1 1】 某飲料集團(tuán)在國內(nèi)有3個(gè)生產(chǎn)工廠，分布在城市 A1，A2，A3；其一級分銷商有4個(gè)，分布在城市B1，B2，B3 ， B4 ?，F(xiàn)已知每月各生產(chǎn)工廠的產(chǎn)量、各分銷商的需求量； 以及從Ai到Bj的每噸飲料的運(yùn)費(fèi)cij（見下表）。 銷地銷地 產(chǎn)地產(chǎn)地 B B1 1B B2 2B B3 3B B4 4產(chǎn)量產(chǎn)量 A A1 16 63 32 25 55 5 A A2 27 75 58 84 42 2 A A3 33 32 29 97 73 3 銷量銷量2 23 31 14 4 為發(fā)

4、揮集團(tuán)優(yōu)勢，公司需要統(tǒng)一籌劃運(yùn)銷問題，求使為發(fā)揮集團(tuán)優(yōu)勢，公司需要統(tǒng)一籌劃運(yùn)銷問題，求使運(yùn)費(fèi)最小運(yùn)費(fèi)最小的的 調(diào)運(yùn)方案。調(diào)運(yùn)方案。 解：建立該運(yùn)輸問題的解：建立該運(yùn)輸問題的LPLP模型如模型如 下下 343332312423 222114131211 792348 575236 2 1 xxxxxx xxxxxxmin BAx jiij ）目標(biāo)函數(shù)： 的數(shù)量（噸）到銷地為每月從產(chǎn)地設(shè) ）決策變量： 4,3,2,1;3,2,10 4 1 3 2 3 2 5 . 3 342414 332313 322212 312111 34333231 24232221 14131211 jix xxx xxx

5、 xxx xxx xxxx xxxx xxxx ts ij ）約束條件： 運(yùn)輸問題的一般提法： 設(shè)某種物資有m個(gè)產(chǎn)地 ，其產(chǎn)量分別為 ；有n個(gè)銷地 ，其銷量分別為 ； 從 到 的單位運(yùn)價(jià)為 。 問應(yīng)該如何組織調(diào)運(yùn)才能使總的運(yùn)費(fèi)最少？ miA i , 2 , 1 i a j bnjB j , 2 , 1 i A ij c j B 設(shè) 為把這種物資從Ai運(yùn)到Bj的數(shù)量，簡稱 為Ai至Bj的運(yùn)量運(yùn)量；設(shè)z為總運(yùn)費(fèi)，則一般運(yùn)輸問 題及其數(shù)學(xué)模型可以簡潔地表示為下表這種形 式，稱為表格形式的一般運(yùn)輸模型表格形式的一般運(yùn)輸模型，簡稱表式表式 運(yùn)輸模型運(yùn)輸模型。 ij x p136p136 表式運(yùn)輸模型 銷

6、地銷地 產(chǎn)地產(chǎn)地 A1 A2 Am 產(chǎn)量產(chǎn)量 a1 a2 am B1B2Bn 銷量銷量b1b2bn c11c12c1n c21 c22c2n cm1cm2cmn x11 x12 x1n x21 x22 x2n xm1 xm2 xmn njmix bx ax ts xcmin ij j m i ij i n j ij m i n j ijij , 2 , 1;, 2 , 10 . . 1 1 11 產(chǎn)銷平衡產(chǎn)銷平衡 njmix bx ax ts xcmin ij j m i ij i n j ij m i n j ijij , 2 , 1;, 2 , 10 . . 1 1 11 產(chǎn)大于銷產(chǎn)大于銷

7、 njmix bx ax ts xcmin ij j m i ij i n j ij m i n j ijij , 2 , 1;, 2 , 10 . . 1 1 11 產(chǎn)小于銷產(chǎn)小于銷 【運(yùn)輸模型運(yùn)輸模型 系數(shù)矩陣系數(shù)矩陣】 1 1 1 1 1 1 1 1 1 111 111 111 A m m 行行 n n 行行 【討論】運(yùn)輸模型系數(shù)矩陣的特征？ 表面任意一個(gè)運(yùn)輸模型系數(shù)矩陣同一個(gè)與之規(guī)模相當(dāng) 的普通LP模型的系數(shù)矩陣相比都大為簡潔，且其中只含 有0和1這兩個(gè)元素，且0的個(gè)數(shù)遠(yuǎn)遠(yuǎn)多于1的個(gè)數(shù)，一般 我們把這樣的矩陣稱為稀疏陣稀疏陣。 深層次對任意產(chǎn)銷平衡的運(yùn)輸模型來說，其系數(shù)陣的 前m行之和

8、等于后n行之和。 意味著？意味著？ 可以證明：平衡模型的系數(shù)陣和增廣陣的秩均 為m+n-1，這也意味著平衡模型的基本可行解 所含基變量的個(gè)數(shù)必為m+n-1個(gè)。 【結(jié)論】 m+n-1 【討論】上述運(yùn)輸問題所建立的LP模型如果用傳統(tǒng)的 單純形法進(jìn)行求解會出現(xiàn)什么情況？ 【友情提示友情提示】 1）表上作業(yè)法僅僅適用于產(chǎn)銷平衡產(chǎn)銷平衡的運(yùn)輸問題 2）表上作業(yè)法基于一種作業(yè)表 “產(chǎn)銷平衡及運(yùn)價(jià)表” 特征？特征？ 5.2 5.2 表上作業(yè)法表上作業(yè)法 用單純形法求解LP式運(yùn)輸模型，必須刪掉一個(gè)函數(shù)約 束，而且計(jì)算量很大，但表上作業(yè)法不必如此費(fèi)力， 而是另辟蹊徑。 表上作業(yè)法是一種專門求解運(yùn)輸問題的特殊方法

9、，其 實(shí)質(zhì)仍是單純形法，只是具體計(jì)算和術(shù)語有所區(qū)別。 與一般的LP問題不同的是，平衡運(yùn)輸問題總是存在最 優(yōu)解。 銷地銷地 產(chǎn)地產(chǎn)地 B B1 1B B2 2B B3 3B B4 4產(chǎn)量產(chǎn)量 A A1 1 6 63 32 25 5 5 5 A A2 2 7 75 58 84 4 2 2 A A3 3 3 32 29 97 7 3 3 銷量銷量2 23 31 14 41010 表上作業(yè)法的基本思想及基本步驟 【基本思想基本思想】類似于單純形法，只是叫法不同而已，如基本 可行解稱為“方案”；迭代稱為“調(diào)整改進(jìn)”等。 【基本步驟基本步驟】 1）確定初始方案； 2）對初始方案進(jìn)行最優(yōu)性檢驗(yàn)； 3）調(diào)整、

10、改進(jìn)非最優(yōu)方案； 4）直至得到最優(yōu)方案（惟一方案或多重方案） 運(yùn)輸問題求解思路運(yùn)輸問題求解思路 確定初始方案確定初始方案 （初始基本可（初始基本可 行解）行解） 輸出最優(yōu)方案輸出最優(yōu)方案 改進(jìn)調(diào)整改進(jìn)調(diào)整 （換基迭代）（換基迭代） 判斷是判斷是 否最優(yōu)否最優(yōu) 結(jié)果結(jié)果 是是 否否 5.2.1 5.2.1 初始方案的確定初始方案的確定 確定初始方案的方法有很多，原理各不相同確定初始方案的方法有很多，原理各不相同 左上角法（西北角法、階梯法） 最小元素法最小元素法 最大差額法最大差額法 Russell概算法 銷地銷地 產(chǎn)地產(chǎn)地 B1B2B3B4產(chǎn)量產(chǎn)量 A1 6325 5 A2 7584 2 A3

11、 3297 3 銷量銷量 231410 左上角法左上角法 最小元素指？ 最小元素法的基本思想？ 最小元素法 “最小運(yùn)價(jià)最小運(yùn)價(jià)” “就近運(yùn)給就近運(yùn)給” 先給作業(yè)表中最小運(yùn)價(jià)那格安排運(yùn)量，然后劃去該運(yùn)價(jià) 所在的行或列；繼續(xù)這樣做，每次總在表中剩余運(yùn)價(jià)的 最小元素那格確定運(yùn)量，直至求出初始方案為止。 銷地銷地 產(chǎn)地產(chǎn)地 B1B2B3B4產(chǎn)量產(chǎn)量 A1 63255 A2 75842 A3 32973 銷量銷量 231410 (0)(0) 初始方案：初始方案：x x11 11=2,x =2,x13 13=1,x =1,x14 14=2,x =2,x24 24=2,x =2,x31 31=0,x =0,

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

13、進(jìn)，也可以轉(zhuǎn)90繼續(xù)前進(jìn)，如此進(jìn)行下去最 終回到出發(fā)點(diǎn)。 注意：用最小元素法得到的初始方案肯定不會形成閉回路！ 銷地銷地 產(chǎn)地產(chǎn)地 B1B2B3B4產(chǎn)量產(chǎn)量 A1 63255 A2 75842 A3 32973 銷量銷量 231410 B B1 1B B2 2B B3 3B B4 4B B5 5 A A1 1 X11X12 A A2 2 X23X25 A A3 3 X31X35 A A4 4 X42X43 最大差額法 “差額” 行差和列差 “最大差額” 兩最小元素之差（正值） 不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi) 差額越大，說明當(dāng)不能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加的 越多 v5.2.2 5.2.

14、2 最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn) v確定初始方案后，就要對它進(jìn)行最優(yōu)性檢驗(yàn)，即檢驗(yàn) 初始基本可行解對應(yīng)的目標(biāo)函數(shù)值是否達(dá)到最優(yōu)。 v運(yùn)輸問題要求目標(biāo)函數(shù)求最小值，故當(dāng)檢驗(yàn)數(shù) 時(shí)，表示該方案為最優(yōu)。 v計(jì)算檢驗(yàn)數(shù)的方法有 vA 位勢法 vB 閉回路法 0 ij 1 1、位勢法、位勢法 A 兩個(gè)位勢量：產(chǎn)地的位勢量 ；銷地的位勢量 B 兩個(gè)基本公式： 1）該公式僅僅適用于基變量所在格（基格） 2）決策變量的檢驗(yàn)數(shù)計(jì)算公式： jiij vuc jiijij vuc i u j v 銷地銷地 產(chǎn)地產(chǎn)地 B1B2B3B4產(chǎn)量產(chǎn)量 ui A1 6 2 32 1 5 2 50 A2 7584 2 2-1 A3 3

15、0 2 3 97 3-3 銷量銷量2314 vj 6525 -2 217 105 非基變量非基變量x x12 12的檢驗(yàn)數(shù) 的檢驗(yàn)數(shù) 12 12= c = c12 12 u u1 1 v v2 2 = -2 = -2，即讓非基變量，即讓非基變量x x12 12從 從0 0增增 到到1 1，可使總運(yùn)費(fèi)減少，可使總運(yùn)費(fèi)減少2 2百元。百元。 2 2、閉回路法、閉回路法 這里的閉回路是指以非基變量的格子為始點(diǎn)和終點(diǎn)，而 其余頂點(diǎn)均為畫圈數(shù)字（基變量）的一條封閉回路，用 水平或者垂直線向前畫，每碰到一數(shù)字格轉(zhuǎn)90度后繼續(xù) 前進(jìn)，直到回到始點(diǎn)。 偶點(diǎn)（偶點(diǎn)（+ +） 奇點(diǎn)（奇點(diǎn)（- -） 結(jié)論結(jié)論1 1

16、：閉回路都是唯一的。：閉回路都是唯一的。 結(jié)論結(jié)論2 2：任一非基變量的檢驗(yàn)數(shù)都等于它的閉回路上所有：任一非基變量的檢驗(yàn)數(shù)都等于它的閉回路上所有 偶點(diǎn)運(yùn)價(jià)的總和與所有奇點(diǎn)的運(yùn)價(jià)總和之差。偶點(diǎn)運(yùn)價(jià)的總和與所有奇點(diǎn)的運(yùn)價(jià)總和之差。 5.2.3 非最優(yōu)方案的調(diào)整 當(dāng)作業(yè)表中出現(xiàn)負(fù)檢驗(yàn)數(shù)時(shí)，表明此方案仍不是最優(yōu) 方案，需要進(jìn)行調(diào)整，調(diào)整時(shí)仍用閉回路法閉回路法。 （1 1）進(jìn)基變量的確定）進(jìn)基變量的確定 若同時(shí)有多個(gè)負(fù)檢驗(yàn)數(shù)一樣最小，則選其中最小運(yùn)價(jià) 所對應(yīng)的那個(gè)進(jìn)基。 （2 2）離基變量的確定）離基變量的確定 在進(jìn)基變量的閉回路上，按確定離基變量，同時(shí)也確 定了調(diào)整量t。若有多個(gè)奇點(diǎn)的運(yùn)量值一樣，則選

17、其中 最大運(yùn)價(jià)所對應(yīng)的那個(gè)離基。 （3 3）非最優(yōu)方案的調(diào)整）非最優(yōu)方案的調(diào)整 所有偶點(diǎn)的運(yùn)量 + t 所有奇點(diǎn)的運(yùn)量 - t 0 ijij min 為奇點(diǎn) ijpqij xxxmint x x12 12 進(jìn)基 進(jìn)基 最小調(diào)整量為最小調(diào)整量為2 2，即，即t=2t=2， x x11 11 離基 離基 銷地 產(chǎn)地 B1B2B3B4產(chǎn)量 A1 6 2 3 x12 2 1 5 2 5 A2 7584 2 2 A3 3 0 2 3 97 3 銷量2314 + + - - + + - - 銷地銷地 產(chǎn)地產(chǎn)地 B B1 1B B2 2B B3 3B B4 4產(chǎn)量產(chǎn)量 A A1 1 6 6 3 3 2 2

18、1 1 5 5 2 2 5 5 A A2 2 7 75 58 84 4 2 2 2 2 A A3 3 3 3 2 2 9 97 7 3 3 銷量銷量2 23 31 14 4 調(diào)整后新方案：調(diào)整后新方案：x x12 12=2,x =2,x13 13=1,x =1,x14 14=2,x =2,x24 24=2,x =2,x31 31=2,x =2,x32 32=1 =1，Z=34Z=34 2 2 1 定理定理1(惟一最優(yōu)解的判定定理惟一最優(yōu)解的判定定理) 如果在表上作業(yè)法得到的最終表如果在表上作業(yè)法得到的最終表 中中,非基變量的檢驗(yàn)數(shù)全都大于零非基變量的檢驗(yàn)數(shù)全都大于零,則該運(yùn)輸問題存在惟一最優(yōu)解

19、則該運(yùn)輸問題存在惟一最優(yōu)解。 定理定理2(多重最優(yōu)解的判定定理多重最優(yōu)解的判定定理)對于一個(gè)運(yùn)輸問題對于一個(gè)運(yùn)輸問題,在得到的第一在得到的第一 個(gè)最優(yōu)解的最終表中個(gè)最優(yōu)解的最終表中,若至少存在一個(gè)檢驗(yàn)數(shù)為零的非基變量若至少存在一個(gè)檢驗(yàn)數(shù)為零的非基變量,并并 且在以這個(gè)非基變量為出發(fā)點(diǎn)的閉回路上且在以這個(gè)非基變量為出發(fā)點(diǎn)的閉回路上,在需要減少運(yùn)輸量的在需要減少運(yùn)輸量的 頂點(diǎn)中頂點(diǎn)中,最小運(yùn)量不等于零最小運(yùn)量不等于零,那么該運(yùn)輸問題存在多重最優(yōu)解那么該運(yùn)輸問題存在多重最優(yōu)解。 運(yùn)輸問題的多重解運(yùn)輸問題的多重解 運(yùn)輸問題多重解運(yùn)輸問題多重解 B1B2B3B4產(chǎn)量 A13113107 A219284 A3741059 銷量3656 5.2.4 產(chǎn)銷不平衡問題的解法 A 產(chǎn)大于銷 虛設(shè)銷地（經(jīng)濟(jì)意義：貯存）虛設(shè)銷地（經(jīng)濟(jì)意義：貯存） B 產(chǎn)小于銷 虛設(shè)產(chǎn)地（經(jīng)濟(jì)意義：脫銷）虛設(shè)產(chǎn)地（