03運(yùn)輸問題講稿

1、 1 1 5 5 年年 10 10月月 (transportation problem) 順風(fēng)而呼，聲非加疾也，而聞?wù)哒?。順風(fēng)而呼，聲非加疾也，而聞?wù)哒谩?假輿馬者，非利足也，而致千里；假舟假輿馬者，非利足也，而致千里；假舟 楫者，非能水也，而絕江河。君子生非楫者，非能水也，而絕江河。君子生非 異也，善假于物也。異也，善假于物也。 荀子荀子勸學(xué)勸學(xué) 前面討論了一般線性規(guī)劃問題的數(shù)學(xué)模型的建前面討論了一般線性規(guī)劃問題的數(shù)學(xué)模型的建 立和求解的方法立和求解的方法, , 但在實(shí)際工作中，往往碰到有些但在實(shí)際工作中，往往碰到有些 線性規(guī)劃問題線性規(guī)劃問題, , 它們的約束條件的它們的約束條件的系數(shù)矩陣

2、系數(shù)矩陣具有特具有特 殊的結(jié)構(gòu)，這就使我們有可能找到比單純形法更為殊的結(jié)構(gòu)，這就使我們有可能找到比單純形法更為 簡(jiǎn)單的求解方法簡(jiǎn)單的求解方法, , 從而節(jié)約大量的計(jì)算時(shí)間和費(fèi)用。從而節(jié)約大量的計(jì)算時(shí)間和費(fèi)用。 本章所討論的運(yùn)輸問題就是屬于這樣一類特殊的線本章所討論的運(yùn)輸問題就是屬于這樣一類特殊的線 性規(guī)劃問題，它具有廣泛的應(yīng)用，在實(shí)踐中有重要性規(guī)劃問題，它具有廣泛的應(yīng)用，在實(shí)踐中有重要 的價(jià)值。的價(jià)值。 在經(jīng)濟(jì)建設(shè)中，經(jīng)常會(huì)遇到大宗物資中的運(yùn)輸在經(jīng)濟(jì)建設(shè)中，經(jīng)常會(huì)遇到大宗物資中的運(yùn)輸 問題如煤炭、鋼鐵、木材、糧食等物資問題如煤炭、鋼鐵、木材、糧食等物資, ,在全國有若在全國有若 干生產(chǎn)基地干生

3、產(chǎn)基地, , 根據(jù)已有的交通網(wǎng)根據(jù)已有的交通網(wǎng), , 應(yīng)如何制定調(diào)運(yùn)應(yīng)如何制定調(diào)運(yùn) 方案，將這些物資運(yùn)到各消費(fèi)地點(diǎn)，使總運(yùn)費(fèi)最小。方案，將這些物資運(yùn)到各消費(fèi)地點(diǎn)，使總運(yùn)費(fèi)最小。 一、運(yùn)輸問題典例與數(shù)學(xué)模型一、運(yùn)輸問題典例與數(shù)學(xué)模型 典例、線性規(guī)劃模型、運(yùn)輸表典例、線性規(guī)劃模型、運(yùn)輸表 二、初始基可行解二、初始基可行解 最小元素法、沃格爾法最小元素法、沃格爾法 三、非基變量的檢驗(yàn)數(shù)三、非基變量的檢驗(yàn)數(shù) 閉回路法、對(duì)偶變量法閉回路法、對(duì)偶變量法 四、解的調(diào)整四、解的調(diào)整 確定進(jìn)基變量和離基變量，調(diào)整運(yùn)量確定進(jìn)基變量和離基變量，調(diào)整運(yùn)量 五、產(chǎn)銷不平衡的運(yùn)輸問題五、產(chǎn)銷不平衡的運(yùn)輸問題 六、運(yùn)輸問題

4、應(yīng)用六、運(yùn)輸問題應(yīng)用建模建模 2021-6-64 某公司從三個(gè)產(chǎn)地某公司從三個(gè)產(chǎn)地 ， ， 將產(chǎn)品運(yùn)往四個(gè)銷地將產(chǎn)品運(yùn)往四個(gè)銷地 ， ， ，各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地運(yùn)往各銷，各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地運(yùn)往各銷 地的地的運(yùn)費(fèi)單價(jià)運(yùn)費(fèi)單價(jià)如表所示。應(yīng)如何調(diào)運(yùn)可使如表所示。應(yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最小運(yùn)費(fèi)最?。?1 A 2 A 1 B 2 B 3 B 3 A 4 B 銷地 運(yùn)費(fèi)單價(jià) 產(chǎn)地 B1B2B3B4 產(chǎn)量 （噸） A13113107 A219284 A3741059 銷量（噸）365620 一、運(yùn)輸問題典例一、運(yùn)輸問題典例 2 3 2 1 3 4 1 A2=4 A3=9 B1=

5、3 B2=6 B3=5 B4=6 A1=7 供應(yīng)量供應(yīng)量 供應(yīng)地供應(yīng)地運(yùn)價(jià)運(yùn)價(jià) 需求量需求量 需求地需求地 3 11 3 10 1 9 2 8 7 4 10 5 2021-6-66 解：解：從表中可知：總產(chǎn)量從表中可知：總產(chǎn)量 = = 總銷量。這是一個(gè)產(chǎn)銷平衡的總銷量。這是一個(gè)產(chǎn)銷平衡的 運(yùn)輸問題。假設(shè)運(yùn)輸問題。假設(shè) 表示從產(chǎn)地表示從產(chǎn)地 運(yùn)往銷地運(yùn)往銷地 的產(chǎn)的產(chǎn) 品數(shù)量，品數(shù)量， 建立如下表格：建立如下表格： ij x i j . 4 , 3 , 2 , 1; 3 , 2 , 1ji 于是可建立如下的數(shù)學(xué)模型于是可建立如下的數(shù)學(xué)模型： 銷地銷地 運(yùn)費(fèi)單價(jià)運(yùn)費(fèi)單價(jià) 產(chǎn)地產(chǎn)地 B1B2B3B4

6、 產(chǎn)量產(chǎn)量 （噸）（噸） A13113107 A219284 A3741059 銷量（噸）銷量（噸）3656 11 x 12 x 13 x 21 x 22 x 23 x 31 x 32 x 33 x 14 x 24 x 34 x 0 6=+ 5=+ 6=+ 3=+ 9=+ 4=+ 7=+ 5+10+4+7+8+2+9+1+10+3+11+3=min 343332312423222114131211 342414 332313 322212 312111 34333231 24232221 14131211 343332312423222114131211 xxxxxxxxxxxx xxx xx

7、x xxx xxx xxxx xxxx xxxxs.t. xxxxxxxxxxxxz 供應(yīng)地約束供應(yīng)地約束需求地約束需求地約束 （三）模型系數(shù)矩陣特征（三）模型系數(shù)矩陣特征 1.1.共有共有m+nm+n行，分別表示各產(chǎn)地和銷地；行，分別表示各產(chǎn)地和銷地；m m n n列，分列，分 別表示各決策變量別表示各決策變量； 2.2.每列只有兩個(gè)每列只有兩個(gè)1 1，其余為，其余為0 0，分別表示只有一個(gè)產(chǎn)，分別表示只有一個(gè)產(chǎn) 地和一個(gè)銷地被使用。地和一個(gè)銷地被使用。 分析：變量個(gè)數(shù)為分析：變量個(gè)數(shù)為1212，約束個(gè)數(shù)為，約束個(gè)數(shù)為7 7，但由于是產(chǎn)，但由于是產(chǎn) 銷平衡，則約束中有一個(gè)是多余的，于是基變量

8、個(gè)數(shù)銷平衡，則約束中有一個(gè)是多余的，于是基變量個(gè)數(shù) 為為6 6，非基變量個(gè)數(shù)為，非基變量個(gè)數(shù)為12-6=612-6=6。 運(yùn)輸問題的一般提法是這樣的：某種物資有若干個(gè)運(yùn)輸問題的一般提法是這樣的：某種物資有若干個(gè) 產(chǎn)地和銷地，若已知各個(gè)產(chǎn)地的產(chǎn)量、各個(gè)銷地的銷量產(chǎn)地和銷地，若已知各個(gè)產(chǎn)地的產(chǎn)量、各個(gè)銷地的銷量 以及各產(chǎn)地到各銷地的單位運(yùn)價(jià)（或運(yùn)輸距離）。問應(yīng)以及各產(chǎn)地到各銷地的單位運(yùn)價(jià)（或運(yùn)輸距離）。問應(yīng) 如何組織調(diào)運(yùn)，才能使總運(yùn)費(fèi)（或總的運(yùn)輸量）最??？如何組織調(diào)運(yùn)，才能使總運(yùn)費(fèi)（或總的運(yùn)輸量）最?。?將此問題更具體化，假定有將此問題更具體化，假定有m個(gè)產(chǎn)地，個(gè)產(chǎn)地，n個(gè)銷地個(gè)銷地 第第i產(chǎn)地的

9、供應(yīng)量，產(chǎn)地的供應(yīng)量，i=1，2，m。 第第j銷地的需求量，銷地的需求量，j=1，2，n。 從從i產(chǎn)地到產(chǎn)地到j(luò)銷地的單位運(yùn)費(fèi)銷地的單位運(yùn)費(fèi) 產(chǎn)地產(chǎn)地i到銷地到銷地j的調(diào)運(yùn)數(shù)量的調(diào)運(yùn)數(shù)量 為了直觀起見，運(yùn)輸問題常用表格來表示，常用有三種表格為了直觀起見，運(yùn)輸問題常用表格來表示，常用有三種表格: i a j b ij c ij x 10 1、產(chǎn)銷平衡表、產(chǎn)銷平衡表 n j j m i i ba 11 單位單位 運(yùn)價(jià)運(yùn)價(jià) 銷銷 或運(yùn)距或運(yùn)距 地地 產(chǎn)地產(chǎn)地 B1 B2 Bn 產(chǎn)產(chǎn) 量量 A1 A2 Am c11 c12 c1 n c21 c22 c2n cm1 cm2 cm n a1 a2 am

10、銷銷 量量 b1 b2 bn n j j m i i ba 11 2、單位運(yùn)價(jià)表、單位運(yùn)價(jià)表 3、運(yùn)輸表、運(yùn)輸表:產(chǎn)銷平衡表和運(yùn)價(jià)表合二為一產(chǎn)銷平衡表和運(yùn)價(jià)表合二為一 n j j m i i ba 11 如果如果總產(chǎn)量總產(chǎn)量= =總銷量總銷量, ,= =即即 a a1 1 + a + a2 2 + + a + + am m = b = b1 1 + b + b2 2 + +b + +bn n 則稱該運(yùn)輸問題為產(chǎn)銷平衡運(yùn)輸問題；否則，稱產(chǎn)則稱該運(yùn)輸問題為產(chǎn)銷平衡運(yùn)輸問題；否則，稱產(chǎn) 銷不平衡運(yùn)輸問題。我們首先研究產(chǎn)銷平衡問題。銷不平衡運(yùn)輸問題。我們首先研究產(chǎn)銷平衡問題。 設(shè)從設(shè)從A Ai i 到

11、到B Bj j的運(yùn)輸量為的運(yùn)輸量為x xij ij, , 總運(yùn)費(fèi)為 總運(yùn)費(fèi)為Z Z。問怎。問怎 樣編制調(diào)運(yùn)方案才能使總運(yùn)費(fèi)最少？（注意：只研樣編制調(diào)運(yùn)方案才能使總運(yùn)費(fèi)最少？（注意：只研 究單一品種物資運(yùn)輸問題）那么，產(chǎn)銷平衡的運(yùn)輸究單一品種物資運(yùn)輸問題）那么，產(chǎn)銷平衡的運(yùn)輸 問題的數(shù)學(xué)模型是：?jiǎn)栴}的數(shù)學(xué)模型是： minZ= （總運(yùn)費(fèi)極小化）（總運(yùn)費(fèi)極小化） = ai i=1,2,m,（產(chǎn)量約束，某一產(chǎn)地運(yùn)產(chǎn)量約束，某一產(chǎn)地運(yùn) 往各銷地的運(yùn)量之和等于該地產(chǎn)量往各銷地的運(yùn)量之和等于該地產(chǎn)量） = bj j=1,2,n, （銷量約束，各產(chǎn)地運(yùn)往銷量約束，各產(chǎn)地運(yùn)往 某一銷地的運(yùn)量之和等于該銷地需求量

12、某一銷地的運(yùn)量之和等于該銷地需求量） xij 0 非負(fù)約束非負(fù)約束 11 mn i ji j ij cx 1 n i j j x 1 m ij i x 111212122212 111212122212 111 111 111 111 111 111 ,.,.,.,., (0,.,1,.,1,.0) nnmmmn nnmmmn T ijim j xxxxxxxxx A AP PPPPPPPP Pee m 行行 n 行行 1 1、包含、包含 = =，所以系數(shù)矩陣中線性獨(dú)立的列向量，所以系數(shù)矩陣中線性獨(dú)立的列向量 的最大個(gè)數(shù)為（的最大個(gè)數(shù)為（該模型有該模型有m m* *n n個(gè)變量，個(gè)變量， m+

13、nm+n個(gè)約束個(gè)約束，解中基變量個(gè)數(shù)為（解中基變量個(gè)數(shù)為（m+n-1m+n-1）個(gè)。個(gè)。（ 對(duì)于平衡型的運(yùn)輸問題，當(dāng)確定其中的對(duì)于平衡型的運(yùn)輸問題，當(dāng)確定其中的m+n-1m+n-1個(gè)個(gè) 方程后，剩下的一個(gè)方程也就確定了方程后，剩下的一個(gè)方程也就確定了 2 2、在該模型的系數(shù)矩陣中，每列有兩個(gè)元素是、在該模型的系數(shù)矩陣中，每列有兩個(gè)元素是1 1，其，其 余為余為0 0。（。（2mn2mn個(gè)元素不為個(gè)元素不為0 0） 3 3、在目標(biāo)函數(shù)中，由于系數(shù)、在目標(biāo)函數(shù)中，由于系數(shù)0,0,且目標(biāo)為極小且目標(biāo)為極小, ,因此因此 目標(biāo)函數(shù)有下界目標(biāo)函數(shù)有下界( (不會(huì)是無界解不會(huì)是無界解),),又由于約束方程

14、組又由于約束方程組 一定有可行解（可以證明）一定有可行解（可以證明）, ,故故運(yùn)輸問題一定有最優(yōu)運(yùn)輸問題一定有最優(yōu) 解。解。 運(yùn)輸模型的特點(diǎn)：運(yùn)輸模型的特點(diǎn)： l 運(yùn)輸問題是一種特殊的線性規(guī)劃問題，理運(yùn)輸問題是一種特殊的線性規(guī)劃問題，理 論上論上, ,我們可以用單純形法來求解運(yùn)輸問題的我們可以用單純形法來求解運(yùn)輸問題的 解解, , 如果用單純形法求解，先得在各約束條件如果用單純形法求解，先得在各約束條件 上加入一個(gè)人工變量上加入一個(gè)人工變量( (以便求出初始基可行解以便求出初始基可行解) )。 因此，即使是因此，即使是 m = 3m = 3， n = 4 n = 4 這樣的簡(jiǎn)單問這樣的簡(jiǎn)單問

15、題題, , 變量數(shù)就有變量數(shù)就有1919個(gè)之多，計(jì)算起來非常復(fù)雜。個(gè)之多，計(jì)算起來非常復(fù)雜。 但由于運(yùn)輸問題自身的特殊性但由于運(yùn)輸問題自身的特殊性, ,我們使用單純我們使用單純 形原理形原理, ,但不用單純形法。人們?cè)诜治鲞\(yùn)輸規(guī)但不用單純形法。人們?cè)诜治鲞\(yùn)輸規(guī) 劃系數(shù)矩陣特征的基礎(chǔ)上建立了針對(duì)運(yùn)輸問題劃系數(shù)矩陣特征的基礎(chǔ)上建立了針對(duì)運(yùn)輸問題 的表上作業(yè)法。的表上作業(yè)法。 2 2 表上作業(yè)法是求解運(yùn)輸問題的一種簡(jiǎn)便有效的方表上作業(yè)法是求解運(yùn)輸問題的一種簡(jiǎn)便有效的方 法，求解工作在運(yùn)輸表上進(jìn)行，它是單純形法的一種法，求解工作在運(yùn)輸表上進(jìn)行，它是單純形法的一種 簡(jiǎn)化方法，其實(shí)質(zhì)是單純形法，也稱為是運(yùn)

16、輸單純形簡(jiǎn)化方法，其實(shí)質(zhì)是單純形法，也稱為是運(yùn)輸單純形 法，但具體計(jì)算和術(shù)語有所不同。法，但具體計(jì)算和術(shù)語有所不同。 基本可行解基本可行解 是否最優(yōu)解是否最優(yōu)解結(jié)束結(jié)束 換基 是是 否否 運(yùn)輸問題的求解思路 求解思路：求解思路：這里求解運(yùn)輸問題的思想和單純形法完這里求解運(yùn)輸問題的思想和單純形法完 全一樣，即首先確定一個(gè)初始基本可行解，然后根據(jù)最全一樣，即首先確定一個(gè)初始基本可行解，然后根據(jù)最 優(yōu)性判別準(zhǔn)則來檢查這個(gè)基本可行解是不是最優(yōu)的。如優(yōu)性判別準(zhǔn)則來檢查這個(gè)基本可行解是不是最優(yōu)的。如 果是，則計(jì)算結(jié)束；如果不是，則進(jìn)行換基，直至求出果是，則計(jì)算結(jié)束；如果不是，則進(jìn)行換基，直至求出 最優(yōu)解為

17、止。最優(yōu)解為止。 l計(jì)算步驟：計(jì)算步驟： 1 1、按照某種規(guī)則，找出初始基可行解。、按照某種規(guī)則，找出初始基可行解。（最小元素（最小元素 法、法、 2 2、檢驗(yàn)是否最優(yōu)。、檢驗(yàn)是否最優(yōu)。（閉回路法、位勢(shì)法）（閉回路法、位勢(shì)法） 3 3、確定換入變量和換出變量，找出新的基可行解。、確定換入變量和換出變量，找出新的基可行解。 ( (閉回路調(diào)整法閉回路調(diào)整法) ) 4 4、重復(fù)、重復(fù)2 2、3 3步，直到求得最優(yōu)解為止。步，直到求得最優(yōu)解為止。 注意：五個(gè)方法注意：五個(gè)方法 21 一、確定初始基本可行解（一、確定初始基本可行解（ 按照某種規(guī)則，找出初始基可行解。按照某種規(guī)則，找出初始基可行解。即在即

18、在 (m(m n) n) 產(chǎn)銷平產(chǎn)銷平 衡表上給出衡表上給出m+n-1m+n-1個(gè)有數(shù)字的格個(gè)有數(shù)字的格，且行和等于該產(chǎn)地產(chǎn)量，列，且行和等于該產(chǎn)地產(chǎn)量，列 和等于該銷地銷售量。和等于該銷地銷售量。（最小元素法、（最小元素法、 解釋：解釋：運(yùn)輸問題實(shí)際上有運(yùn)輸問題實(shí)際上有m+n-1m+n-1個(gè)基變量。在個(gè)基變量。在m mn n的產(chǎn)銷平衡的產(chǎn)銷平衡 表上給出表上給出m+n-1m+n-1個(gè)數(shù)字格，個(gè)數(shù)字格，其相對(duì)應(yīng)的調(diào)運(yùn)量的值即為基變量其相對(duì)應(yīng)的調(diào)運(yùn)量的值即為基變量 的值的值。 那么在該例中，應(yīng)有那么在該例中，應(yīng)有 3+4-1=63+4-1=6個(gè)基變量。個(gè)基變量。 1 1、最小元素法。、最小元素法

19、?；舅枷耄壕徒?yīng)，即從單位運(yùn)價(jià)基本思想：就近供應(yīng)，即從單位運(yùn)價(jià) 表中最小的運(yùn)價(jià)開始，盡最大可能用完一個(gè)產(chǎn)地的產(chǎn)表中最小的運(yùn)價(jià)開始，盡最大可能用完一個(gè)產(chǎn)地的產(chǎn) 量，或滿足一個(gè)銷地的銷量，來確定產(chǎn)銷關(guān)系量，或滿足一個(gè)銷地的銷量，來確定產(chǎn)銷關(guān)系, ,得到滿得到滿 足者用線劃去。逐次尋找最小元素依次類推足者用線劃去。逐次尋找最小元素依次類推, ,直到給出直到給出 初始方案為止。優(yōu)先滿足運(yùn)價(jià)最低的供銷業(yè)務(wù)稱最小初始方案為止。優(yōu)先滿足運(yùn)價(jià)最低的供銷業(yè)務(wù)稱最小 元素法。元素法。 23 解：先畫出這個(gè)問題的運(yùn)輸表表如下解：先畫出這個(gè)問題的運(yùn)輸表表如下 24 第一步：從單位運(yùn)價(jià)表中找出最小運(yùn)價(jià)為第一步：從單

20、位運(yùn)價(jià)表中找出最小運(yùn)價(jià)為1，這表示先將，這表示先將 A2 的產(chǎn)品供應(yīng)的產(chǎn)品供應(yīng) B1 。由于。由于A2 每天生產(chǎn)每天生產(chǎn)4噸，噸，B1 每天只需要每天只需要 3噸，即噸，即 A2 除每日能滿足除每日能滿足B1 的需要外還余的需要外還余1噸。因此在產(chǎn)噸。因此在產(chǎn) 銷平衡表銷平衡表 (A2 , B1) 交叉處填上交叉處填上3，表示，表示 A2 調(diào)運(yùn)調(diào)運(yùn)3噸給噸給B1 ， 再在單位運(yùn)價(jià)表中將再在單位運(yùn)價(jià)表中將B1 這一列運(yùn)價(jià)劃去，表示這一列運(yùn)價(jià)劃去，表示 B1 的需求的需求 已滿足，不需要繼續(xù)調(diào)運(yùn)已滿足，不需要繼續(xù)調(diào)運(yùn) (即即x21 =3=min(a2,b1)=min(4 , 3). 第二步第二步:

21、 從上述未劃去的單位運(yùn)價(jià)表的元素中找出最小的從上述未劃去的單位運(yùn)價(jià)表的元素中找出最小的 運(yùn)價(jià)運(yùn)價(jià)2 ，即，即A2 把剩余的產(chǎn)品供應(yīng)給把剩余的產(chǎn)品供應(yīng)給B3 ；B3 每天需要每天需要5 噸噸 ，A2 只剩余只剩余 1 噸，因此在上述產(chǎn)銷平衡表的噸，因此在上述產(chǎn)銷平衡表的 (A2 , B3) 交交 叉處填上叉處填上 1，劃去上述運(yùn)價(jià)表中，劃去上述運(yùn)價(jià)表中A2 這一行運(yùn)價(jià)，表示這一行運(yùn)價(jià)，表示 A2 25 的產(chǎn)品已分配完畢。的產(chǎn)品已分配完畢。 第三步第三步: 從上述第二步所得的單位運(yùn)價(jià)表未劃去的元素中從上述第二步所得的單位運(yùn)價(jià)表未劃去的元素中 找出最小元素為找出最小元素為 3。這表示將。這表示將 A

22、1 的產(chǎn)品供應(yīng)的產(chǎn)品供應(yīng) B3 ， A1 每每 天生產(chǎn)天生產(chǎn)7 噸，噸，B3 尚缺尚缺 4 噸，因此在產(chǎn)銷平衡表的噸，因此在產(chǎn)銷平衡表的(A1 , B3) 交叉處填上交叉處填上 4，由于，由于B3 的需求已滿足，將第二步的單位的需求已滿足，將第二步的單位 運(yùn)價(jià)表中的運(yùn)價(jià)表中的 B3 這一列運(yùn)價(jià)劃去。這一列運(yùn)價(jià)劃去。 如此，一步步進(jìn)行下去，直到單位運(yùn)價(jià)表中所有元素如此，一步步進(jìn)行下去，直到單位運(yùn)價(jià)表中所有元素 都劃去為止，最終在產(chǎn)銷平衡表上就可以得到一個(gè)初始調(diào)都劃去為止，最終在產(chǎn)銷平衡表上就可以得到一個(gè)初始調(diào) 運(yùn)方案。這個(gè)方案的總運(yùn)費(fèi)為運(yùn)方案。這個(gè)方案的總運(yùn)費(fèi)為 86 元，如下表元，如下表 26

23、 B1B2B3B4產(chǎn)量 A17 A2 4 A39 銷量3656 311310 192 74105 8 3 4 1 63 3 總的運(yùn)輸費(fèi)總的運(yùn)輸費(fèi)(31)+(64) +(43) +(12)+(310)+(35)=86元元 1436 6 2 5 27 銷地銷地 產(chǎn)地產(chǎn)地 B1B2B3B4產(chǎn)量產(chǎn)量 A1437 A2314 A3639 銷量銷量3656 最小元素法求解結(jié)果最小元素法求解結(jié)果 注意：注意： 1 1、在調(diào)運(yùn)方案中，稱填寫數(shù)字處為、在調(diào)運(yùn)方案中，稱填寫數(shù)字處為有數(shù)字的格有數(shù)字的格，它對(duì)，它對(duì) 應(yīng)運(yùn)輸問題解中的應(yīng)運(yùn)輸問題解中的基變量的取值基變量的取值（含填數(shù)字（含填數(shù)字0 0的格），的格），

24、為為m+n-1m+n-1個(gè)個(gè)；稱不填數(shù)字處為；稱不填數(shù)字處為空格空格，對(duì)應(yīng)解中，對(duì)應(yīng)解中非基變量非基變量。 2 2、補(bǔ)補(bǔ)“0”0”問題。問題。當(dāng)在當(dāng)在中間中間步驟步驟的未劃去的單位運(yùn)價(jià)表的未劃去的單位運(yùn)價(jià)表 中尋找最小元素時(shí)，發(fā)現(xiàn)該元素所在行的剩余產(chǎn)量等于中尋找最小元素時(shí)，發(fā)現(xiàn)該元素所在行的剩余產(chǎn)量等于 該元素所在列的剩余銷售量。這時(shí)在產(chǎn)銷平衡表相應(yīng)的該元素所在列的剩余銷售量。這時(shí)在產(chǎn)銷平衡表相應(yīng)的 位置填上一個(gè)數(shù)，而在單位運(yùn)價(jià)表中就要位置填上一個(gè)數(shù)，而在單位運(yùn)價(jià)表中就要同時(shí)劃去一行同時(shí)劃去一行 和一列和一列。為了使調(diào)運(yùn)方案中有數(shù)字的格仍為（。為了使調(diào)運(yùn)方案中有數(shù)字的格仍為（m+n-1m+n-

25、1） 個(gè)個(gè)( (即保證基變量的個(gè)數(shù)為即保證基變量的個(gè)數(shù)為m+n-1m+n-1個(gè)個(gè)) )，需要在，需要在同時(shí)劃去同時(shí)劃去 的行或列的任一空格位置添上一個(gè)的行或列的任一空格位置添上一個(gè)“0”0”（劃去的行或（劃去的行或 列不再考慮）列不再考慮），這個(gè)，這個(gè)“0”0”表示該變量是基變量，只不表示該變量是基變量，只不 過它取值為過它取值為0 0，即此時(shí)的調(diào)運(yùn)方案是一個(gè)退化的基可行，即此時(shí)的調(diào)運(yùn)方案是一個(gè)退化的基可行 解。如下例或教材表解。如下例或教材表3-123-12。 3 3、同時(shí)存在兩個(gè)或兩個(gè)以上相等的最小運(yùn)價(jià)時(shí)，任選其一。、同時(shí)存在兩個(gè)或兩個(gè)以上相等的最小運(yùn)價(jià)時(shí)，任選其一。 B1B2B3B4 A

26、153104 A21696 A3201057 銷地銷地 產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量 A15049 A2314 A377 銷量銷量3584 123 4 5 6 6 例：補(bǔ)例：補(bǔ)0問題問題 在這個(gè)例子中，當(dāng)在填入第三數(shù)字的格在這個(gè)例子中，當(dāng)在填入第三數(shù)字的格 ( A1, B4 ) 時(shí)時(shí), 在填入在填入 4 之后，恰好產(chǎn)銷平衡，就必須在單位運(yùn)價(jià)之后，恰好產(chǎn)銷平衡，就必須在單位運(yùn)價(jià) 表中同時(shí)劃去第一行和第四列。為了使有數(shù)字的格不表中同時(shí)劃去第一行和第四列。為了使有數(shù)字的格不 減少，減少，( 有數(shù)字的格的總數(shù)應(yīng)為有數(shù)字的格的總數(shù)應(yīng)為m + n 1個(gè)個(gè) )可以在空可以在空 格格( A1, B1 )

27、、 ( A1, B3 ) 、 ( A2, B4 ) 、( A3, B4 )中任選中任選 一個(gè)格添加一個(gè)一個(gè)格添加一個(gè)“0”；同樣，這個(gè)添加的；同樣，這個(gè)添加的“0”格當(dāng)格當(dāng) 作基變量，取值為作基變量，取值為0。我們這里是在。我們這里是在 ( A1, B3 ) 處填處填0 （即初始調(diào)運(yùn)方案是一個(gè)退化的基可行解）。（即初始調(diào)運(yùn)方案是一個(gè)退化的基可行解）。 銷地 產(chǎn)地 B1 B2 B3 B4 B5 產(chǎn)量 ai 銷量bj B1 B2 B3 B4 B5 10 20 5 9 10 10 8 25 6 21 15 7 10 4 平衡表平衡表運(yùn)價(jià)表運(yùn)價(jià)表 例（參考）例（參考）此題目沒有補(bǔ)此題目沒有補(bǔ)0，按照規(guī)

28、則也可以做對(duì)，按照規(guī)則也可以做對(duì) 銷地銷地 產(chǎn)地產(chǎn)地 B1 B2 B3 B4 B5 產(chǎn)量產(chǎn)量 ai 銷量銷量bj B1 B2 B3 B4 B5 10 20 5 9 10 10 8 25 6 21 15 7 10 4 平衡表平衡表運(yùn)價(jià)表運(yùn)價(jià)表 初始基本可行解為初始基本可行解為 x12,x13,x14,x22,x31,x32,x35=1,5,3,4,3,0,5, 相應(yīng)運(yùn)價(jià)為：相應(yīng)運(yùn)價(jià)為： c12,c13,c14,c22,c31,c32,c35=20,5,9,10,1,15,4, 由此表上作業(yè)得初始調(diào)運(yùn)方案的總運(yùn)費(fèi)為由此表上作業(yè)得初始調(diào)運(yùn)方案的總運(yùn)費(fèi)為 Z=1x20+5x5+3x9+4x10+3x1

29、+0 x15+5x4=135（元）（元） 153 4 305 解解 1 5 23 4 4 1 5 1 6 7 初始基可行解初始基可行解最小元素法（最小元素法（1） 例例 最小元素法（最小元素法（2） 最小元素法（最小元素法（3） 最小元素法（最小元素法（4） 最小元素法（最小元素法（5） 最小元素法（最小元素法（6） 39 401 41 2 42 3 43 4 5 44 同時(shí)同時(shí) 劃去劃去A A3 3行和行和B B4 4列得到初始方案列得到初始方案 6 6 45 思路：思路：最小元素法的缺點(diǎn)是，為了節(jié)省一最小元素法的缺點(diǎn)是，為了節(jié)省一 處的費(fèi)用，有時(shí)造處的費(fèi)用，有時(shí)造成在其它地方要花多幾倍的成

30、在其它地方要花多幾倍的 運(yùn)費(fèi)。沃格爾法考慮到，一產(chǎn)地的產(chǎn)品，假如運(yùn)費(fèi)。沃格爾法考慮到，一產(chǎn)地的產(chǎn)品，假如 不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)。不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)。 這就有一個(gè)差額，差額越大，說明不能按最小這就有一個(gè)差額，差額越大，說明不能按最小 運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加就越多。因此，對(duì)于差運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加就越多。因此，對(duì)于差 額最大處額最大處 ，就優(yōu)先采用最小運(yùn)費(fèi)調(diào)運(yùn)。，就優(yōu)先采用最小運(yùn)費(fèi)調(diào)運(yùn)。 48 用例子來說明伏格爾法的具體實(shí)施過程，步驟如下：用例子來說明伏格爾法的具體實(shí)施過程，步驟如下： 第一步：在單位運(yùn)價(jià)表中增加一行和一列，列的格位置相應(yīng)第一步：在單位運(yùn)價(jià)表中增

31、加一行和一列，列的格位置相應(yīng) 填入該行的次小運(yùn)費(fèi)與最小運(yùn)費(fèi)之差，我們稱之為行差額。行的填入該行的次小運(yùn)費(fèi)與最小運(yùn)費(fèi)之差，我們稱之為行差額。行的 格位置相應(yīng)填入該列的次小運(yùn)費(fèi)與最小運(yùn)費(fèi)之差，我們稱之為列格位置相應(yīng)填入該列的次小運(yùn)費(fèi)與最小運(yùn)費(fèi)之差，我們稱之為列 差額。如此可得表差額。如此可得表 銷地銷地 產(chǎn)地產(chǎn)地 B1B2B3B4行差額行差額 A13113100 A219281 A3741051 列差額列差額2513 49 第二步：從行差額和列差額中選出最大者，選擇它所在第二步：從行差額和列差額中選出最大者，選擇它所在 的行或列中的最小元素。比較該元素所在的行和列的產(chǎn)的行或列中的最小元素。比較該元

32、素所在的行和列的產(chǎn) 量，取它們最小者填入產(chǎn)銷平衡表相應(yīng)的位置。同時(shí)在量，取它們最小者填入產(chǎn)銷平衡表相應(yīng)的位置。同時(shí)在 單位運(yùn)價(jià)表中劃去一行或一列。由表可知單位運(yùn)價(jià)表中劃去一行或一列。由表可知 B2 的列差額最大。的列差額最大。 B2 列中最小元素為列中最小元素為 4（即（即 A3 行），可確定行），可確定 A3 產(chǎn)品優(yōu)先供應(yīng)產(chǎn)品優(yōu)先供應(yīng) B2 。 比較它們的產(chǎn)量和銷量，可知在單位運(yùn)價(jià)表中劃去比較它們的產(chǎn)量和銷量，可知在單位運(yùn)價(jià)表中劃去 B2 列。在產(chǎn)列。在產(chǎn) 銷平衡表的銷平衡表的( A3 , B2 ) 空格處填入空格處填入 6。 第三步：對(duì)上述未劃去的元素再分別計(jì)算出各行、各列第三步：對(duì)上述未

33、劃去的元素再分別計(jì)算出各行、各列 的差額。重復(fù)第一、二步的工作，直到給出初始解為止。的差額。重復(fù)第一、二步的工作，直到給出初始解為止。 本問題利用伏格爾方法給出的初始調(diào)運(yùn)方案如下表所示。本問題利用伏格爾方法給出的初始調(diào)運(yùn)方案如下表所示。 50 銷地銷地 產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量 A1527 A2314 A3639 銷量銷量3656 51 2021-6-651 銷地 產(chǎn)地 B1 B2 B3 B4 A1 5 2 0 0 0 7 A2 3 1 1 1 1 6 A3 6 3 1 2 2 2 2 5 1 1 1 1 3 3 2 2 20 20 3 113 10 29 47 1 10 8 5 1

34、2 34 5 6 6 總的運(yùn)輸費(fèi)總的運(yùn)輸費(fèi)(31)+(64) +(53) +(18)+(210)+(35)=85元元 m + n 1 m + n 1 個(gè)。）個(gè)。） 3、方法特點(diǎn)：方法特點(diǎn)：解的質(zhì)量比較好，常用作求運(yùn)輸問題解的質(zhì)量比較好，常用作求運(yùn)輸問題 的的近似最優(yōu)解。近似最優(yōu)解。一般來說，比用最小元素法所求出的一般來說，比用最小元素法所求出的 初始解更接近于最優(yōu)解。在產(chǎn)地和銷地?cái)?shù)量不多時(shí)，初始解更接近于最優(yōu)解。在產(chǎn)地和銷地?cái)?shù)量不多時(shí)， 此法給出的初始方案有時(shí)就是最優(yōu)方案。本例用伏格此法給出的初始方案有時(shí)就是最優(yōu)方案。本例用伏格 爾方法給出的初始解就是最優(yōu)解。爾方法給出的初始解就是最優(yōu)解。 5

35、3 54 1 55 1 56 2 57 2 58 3 4 60 61 按照上述最小元素法和沃格爾法兩種方法所產(chǎn)按照上述最小元素法和沃格爾法兩種方法所產(chǎn) 生的一組變量的取值將滿足下面條件：生的一組變量的取值將滿足下面條件： (1)(1)所得的變量均為非負(fù)，且所得的變量均為非負(fù)，且基變量總數(shù)恰好為基變量總數(shù)恰好為 （m + n 1m + n 1） 個(gè)個(gè)； (2)(2)所有的所有的約束條件均得到滿足約束條件均得到滿足； (3) (m + n 1 )(3) (m + n 1 )個(gè)個(gè)基變量對(duì)應(yīng)的系數(shù)列向量是基變量對(duì)應(yīng)的系數(shù)列向量是 線性獨(dú)立的線性獨(dú)立的。（所得的變量不構(gòu)成閉回路）。（所得的變量不構(gòu)成閉回

36、路） 因此是基可行解因此是基可行解 最優(yōu)性檢驗(yàn)就是檢查所得到的方案是不是最優(yōu)方最優(yōu)性檢驗(yàn)就是檢查所得到的方案是不是最優(yōu)方 案。檢查的方法與單純形方法中的原理相同，即計(jì)案。檢查的方法與單純形方法中的原理相同，即計(jì) 算檢驗(yàn)數(shù)。由于目標(biāo)要求極小，因此，當(dāng)所有的檢算檢驗(yàn)數(shù)。由于目標(biāo)要求極小，因此，當(dāng)所有的檢 驗(yàn)數(shù)都大于或等于零時(shí)該調(diào)運(yùn)方案就是最優(yōu)方案；驗(yàn)數(shù)都大于或等于零時(shí)該調(diào)運(yùn)方案就是最優(yōu)方案； 否則就不是最優(yōu)，需要進(jìn)行調(diào)整。否則就不是最優(yōu)，需要進(jìn)行調(diào)整。 方法方法：求各：求各非基變量的檢驗(yàn)數(shù)非基變量的檢驗(yàn)數(shù)，即在表上，即在表上求空格的求空格的 檢驗(yàn)數(shù)檢驗(yàn)數(shù)，當(dāng)所有，當(dāng)所有 ij ij 0 0，得到最

37、優(yōu) ，得到最優(yōu)解。如果達(dá)到最優(yōu)解。如果達(dá)到最優(yōu) 解，則停止計(jì)算，否則，轉(zhuǎn)入下一步；解，則停止計(jì)算，否則，轉(zhuǎn)入下一步； 1 1、閉回路法、閉回路法 l2 2、對(duì)偶變量法、對(duì)偶變量法( (位勢(shì)法位勢(shì)法) ) 二、基可行解的最優(yōu)性檢驗(yàn)二、基可行解的最優(yōu)性檢驗(yàn) 1 1）某）某空格空格的閉回路的閉回路： 因?yàn)槿我夥腔蛄烤梢驗(yàn)槿我夥腔蛄烤?表示為基向量的唯一線性組合表示為基向量的唯一線性組合) )（參考（參考P110.4P110.4） 閉回路示意圖閉回路示意圖 1、閉回路法（、閉回路法（cycle method） 2 2）若把閉回路的各變量格看作節(jié)點(diǎn)，在表中可以畫出如下形式）若把閉回路的各變量格看

38、作節(jié)點(diǎn)，在表中可以畫出如下形式 的閉回路：的閉回路： （幾種常見形式）（幾種常見形式） 65 表表3-153-15（以非基變量（以非基變量 x x22 22 為起始頂點(diǎn)的閉回路） 為起始頂點(diǎn)的閉回路） 銷地銷地 產(chǎn)地產(chǎn)地 B B1 1B B2 2B B3 3B B4 4產(chǎn)量產(chǎn)量 3 3 11 11 3 3 4 4 10 10 3 3 7 7 1 1 3 3 9 9 2 2 1 1 8 8 4 4 7 7 4 4 6 6 10 10 5 5 3 3 9 9 銷量銷量3 36 65 56 6 20(20(產(chǎn)銷平衡產(chǎn)銷平衡) ) A1 A2 A3 66 空空 格格閉閉 回回 路路 (A1 , B1)

39、(1,1) (1,3) (2,3) (2,1)(1,1) (A1 , B2)(1,2) (1,4) (3,4) (3,2)(1,2) (A2 , B2)(2,2) (2,3) (1,3) (1,4) (3,4) (3,2) (2,2) (A2 , B4)(2,4) (2,3) (3,3) (1,4)(2,4) (A3 , B1)(3,1) (3,4) (1,4) (1,3) (2,3) (2,1) (3,1) (A3 , B3)(3,3) (3,4) (1,4) (1,3) (3,3) 3)3)顯然，閉回路上一組變量對(duì)應(yīng)約束條件的系數(shù)列向顯然，閉回路上一組變量對(duì)應(yīng)約束條件的系數(shù)列向 量線性相關(guān)

40、。因此，在運(yùn)輸問題的基可行解迭代過程量線性相關(guān)。因此，在運(yùn)輸問題的基可行解迭代過程 中，中，不允許出現(xiàn)不允許出現(xiàn)全部頂點(diǎn)由填數(shù)字格構(gòu)成的閉回路全部頂點(diǎn)由填數(shù)字格構(gòu)成的閉回路。 推論：推論：產(chǎn)銷平衡運(yùn)輸問題的產(chǎn)銷平衡運(yùn)輸問題的 m + n -1 m + n -1 個(gè)變量構(gòu)成個(gè)變量構(gòu)成 基變量的充分必要條件是它不含閉回路。基變量的充分必要條件是它不含閉回路。 這個(gè)推論給出了運(yùn)輸問題基解的重要性質(zhì)，因?yàn)槔@個(gè)推論給出了運(yùn)輸問題基解的重要性質(zhì)，因?yàn)槔?用它來判斷用它來判斷 m+n-m+n-1 1個(gè)變量是否構(gòu)成基變量比直接判斷個(gè)變量是否構(gòu)成基變量比直接判斷 這些變量所對(duì)應(yīng)的系數(shù)列向量組是否線性無關(guān)要簡(jiǎn)單

41、這些變量所對(duì)應(yīng)的系數(shù)列向量組是否線性無關(guān)要簡(jiǎn)單 和直觀。和直觀。 2021-6-668 4）閉回路計(jì)算檢驗(yàn)數(shù)的方法及經(jīng)濟(jì)解釋）閉回路計(jì)算檢驗(yàn)數(shù)的方法及經(jīng)濟(jì)解釋 閉回路法計(jì)算檢驗(yàn)數(shù)：閉回路法計(jì)算檢驗(yàn)數(shù)：就是對(duì)于代表非基變量的空格就是對(duì)于代表非基變量的空格 （其調(diào)運(yùn)量為零），把它的調(diào)運(yùn)量調(diào)整為（其調(diào)運(yùn)量為零），把它的調(diào)運(yùn)量調(diào)整為1 1，由于產(chǎn)銷平衡的，由于產(chǎn)銷平衡的 要求要求, ,必須對(duì)這個(gè)空格的閉回路中的各頂點(diǎn)的調(diào)運(yùn)量加上或減必須對(duì)這個(gè)空格的閉回路中的各頂點(diǎn)的調(diào)運(yùn)量加上或減 少少1 1。最后計(jì)算出由。最后計(jì)算出由這些變化給整個(gè)運(yùn)輸方案的總運(yùn)輸費(fèi)帶來這些變化給整個(gè)運(yùn)輸方案的總運(yùn)輸費(fèi)帶來 的變化。以

42、這個(gè)變化的數(shù)值，作為各空格（非基變量）的檢的變化。以這個(gè)變化的數(shù)值，作為各空格（非基變量）的檢 驗(yàn)數(shù)。驗(yàn)數(shù)。 2021-6-669 銷地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 （+） 4 （-） 3 7 A2 （-） 3 1 （+） 4 A3 63 9 銷量 3 6 5 6 10 8 5 3 11 3 10 29 47 1 從非基變量從非基變量 出發(fā)，找到一個(gè)閉回路如上表所示?；芈酚兴某霭l(fā)，找到一個(gè)閉回路如上表所示。回路有四 個(gè)頂點(diǎn)，除個(gè)頂點(diǎn)，除 外，其余都為基變量。外，其余都為基變量。 調(diào)整調(diào)運(yùn)量：調(diào)整調(diào)運(yùn)量： ，運(yùn)費(fèi)增加了，運(yùn)費(fèi)增加了3 3元；元； ，運(yùn)費(fèi)減少，運(yùn)費(fèi)減少3 3元元 ，運(yùn)

43、費(fèi)增加，運(yùn)費(fèi)增加2 2元；元； ，運(yùn)費(fèi)減少，運(yùn)費(fèi)減少1 1元元 調(diào)整后，調(diào)整后，總運(yùn)費(fèi)增加總運(yùn)費(fèi)增加：3-3+2-1=13-3+2-1=1元。元。 說明如果讓說明如果讓 為基變量，運(yùn)費(fèi)就會(huì)增加，其增加值為基變量，運(yùn)費(fèi)就會(huì)增加，其增加值1 1作為作為 的的檢驗(yàn)數(shù)檢驗(yàn)數(shù)， 1 11 x 1 23 x 1 13 x 11 x 1 21 x 11 x 11 x 11 x (1)(1) 同樣，可以計(jì)算出以非基變量同樣，可以計(jì)算出以非基變量 x x22 22 為起始頂點(diǎn)的閉回路調(diào) 為起始頂點(diǎn)的閉回路調(diào) 整使總的運(yùn)輸費(fèi)用發(fā)生的變化為整使總的運(yùn)輸費(fèi)用發(fā)生的變化為9 2 + 3 10 + 5 4 9 2 + 3

44、 10 + 5 4 1 1 ，即總的運(yùn)費(fèi)增加，即總的運(yùn)費(fèi)增加 1 1 個(gè)單位，這就說明這個(gè)調(diào)整不能改個(gè)單位，這就說明這個(gè)調(diào)整不能改 善目標(biāo)值。善目標(biāo)值。 從上面的討論可以看出，從上面的討論可以看出，當(dāng)某個(gè)非基變量增加一個(gè)單位時(shí)，當(dāng)某個(gè)非基變量增加一個(gè)單位時(shí)， 有若干個(gè)基變量的取值受其影響。有若干個(gè)基變量的取值受其影響。 這樣，利用單位產(chǎn)品變化（運(yùn)輸?shù)膯挝毁M(fèi)用）可計(jì)這樣，利用單位產(chǎn)品變化（運(yùn)輸?shù)膯挝毁M(fèi)用）可計(jì) 算出它們對(duì)目標(biāo)函數(shù)的綜合影響，其作用與線性規(guī)劃算出它們對(duì)目標(biāo)函數(shù)的綜合影響，其作用與線性規(guī)劃 單純形方法中的檢驗(yàn)數(shù)完全相同。故也稱這個(gè)單純形方法中的檢驗(yàn)數(shù)完全相同。故也稱這個(gè)綜合影綜合影

45、響響為該非基變量對(duì)應(yīng)的檢驗(yàn)數(shù)。為該非基變量對(duì)應(yīng)的檢驗(yàn)數(shù)。閉回路方法原理就是閉回路方法原理就是 通過尋找閉回路來找到非基變量的檢驗(yàn)數(shù)。通過尋找閉回路來找到非基變量的檢驗(yàn)數(shù)。 檢驗(yàn)數(shù)：檢驗(yàn)數(shù)：非基變量增加一個(gè)單位引起的成本變化量非基變量增加一個(gè)單位引起的成本變化量 按上述作法，按上述作法，可計(jì)算出表中的所有非基變量的檢驗(yàn)可計(jì)算出表中的所有非基變量的檢驗(yàn) 數(shù)，把它們填入相應(yīng)位置的方括號(hào)內(nèi)數(shù)，把它們填入相應(yīng)位置的方括號(hào)內(nèi)，如下表所示。，如下表所示。 71 銷地銷地 產(chǎn)地產(chǎn)地 B B1 1B B2 2B B3 3B B4 4產(chǎn)量產(chǎn)量 A A1 1 3 3 (1)(1) 1111 (2)(2) 3 3 4

46、 4 10 10 3 3 7 7 A A2 21 1 3 3 9 9 (1) 2 2 1 1 8 8 (-1) 4 4 A A3 37 7 (10)(10) 4 4 6 6 10 10 (12)(12) 5 5 3 3 9 9 銷量銷量3 36 65 56 6 20(20(產(chǎn)銷平衡產(chǎn)銷平衡) ) 初始基本可行解及檢驗(yàn)數(shù)初始基本可行解及檢驗(yàn)數(shù) 72 空空 格格閉閉 回回 路路檢驗(yàn)數(shù)檢驗(yàn)數(shù) (A1 , B1)(1,1) (1,3) (2,3) (2,1)(1,1)1 (A1 , B2)(1,2) (1,4) (3,4) (3,2)(1,2)2 (A2 , B2)(2,2) (2,3) (1,3)

47、(1,4) (3,4) (3,2) (2,2) 1 (A2 , B4)(2,4) (2,3) (3,3) (1,4)(2,4)-1 (A3 , B1)(3,1) (3,4) (1,4) (1,3) (2,3) (2,1) (3,1) 10 (A3 , B3)(3,3) (3,4) (1,4) (1,3) (3,3)12 在一個(gè)閉回路上，如果規(guī)定作為起始頂點(diǎn)在一個(gè)閉回路上，如果規(guī)定作為起始頂點(diǎn) 的非基變量（空格）為第的非基變量（空格）為第 1 1 個(gè)頂點(diǎn)，閉回路個(gè)頂點(diǎn)，閉回路 的其他頂點(diǎn)依次為第的其他頂點(diǎn)依次為第 2 2 個(gè)頂點(diǎn)、第個(gè)頂點(diǎn)、第 3 3 個(gè)頂個(gè)頂 點(diǎn)點(diǎn)，那么就有，那么就有 ij i

48、j = ( = (閉回路上的奇數(shù)次頂點(diǎn)單位運(yùn)費(fèi)之閉回路上的奇數(shù)次頂點(diǎn)單位運(yùn)費(fèi)之 和和) - () - (閉回路上的偶數(shù)次頂點(diǎn)單位運(yùn)費(fèi)之和閉回路上的偶數(shù)次頂點(diǎn)單位運(yùn)費(fèi)之和) ) 其中其中 ij ij 為非基變量的下角指標(biāo)。為非基變量的下角指標(biāo)。 5 例例：非基變量非基變量xij的檢驗(yàn)數(shù)的檢驗(yàn)數(shù)cij -zij閉回路法閉回路法(1) 5 閉回路法閉回路法(2) 5 5 閉回路法閉回路法(3) 75 5 閉回路法閉回路法(4) 9 57 5 閉回路法閉回路法(5) -11 57 9 5 閉回路法閉回路法(6) -3 57 9 -11 80 收收點(diǎn)點(diǎn) 發(fā)發(fā)點(diǎn)點(diǎn) B1B2B3B4發(fā)發(fā)量量 A16 25

49、2344 A244 27 35 16 A37658 3 3 收收量量243413 81 收收點(diǎn)點(diǎn) 發(fā)發(fā)點(diǎn)點(diǎn) B1B2B3B4發(fā)發(fā)量量 A16 25 2344 A244 27 35 16 A37658 3 3 收收量量243413 82 收收點(diǎn)點(diǎn) 發(fā)發(fā)點(diǎn)點(diǎn) B1B2B3B4發(fā)發(fā)量量 A16 25 2344 A244 27 35 16 A37658 3 3 收收量量243413 83 收收點(diǎn)點(diǎn) 發(fā)發(fā)點(diǎn)點(diǎn) B1B2B3B4發(fā)發(fā)量量 A16 25 2344 A244 27 35 16 A37658 3 3 收收量量243413 84 收收點(diǎn)點(diǎn) 發(fā)發(fā)點(diǎn)點(diǎn) B1B2B3B4發(fā)發(fā)量量 A16 25 2344

50、 A244 27 35 16 A37658 3 3 收收量量243413 85 收收點(diǎn)點(diǎn) 發(fā)發(fā)點(diǎn)點(diǎn) B1B2B3B4發(fā)發(fā)量量 A16 25 2344 A244 27 35 16 A37658 3 3 收收量量243413 86 收收點(diǎn)點(diǎn) 發(fā)發(fā)點(diǎn)點(diǎn) B1B2B3B4發(fā)發(fā)量量 A16 25 2344 A244 27 35 16 A37658 3 3 收收量量243413 87 收收點(diǎn)點(diǎn) 發(fā)發(fā)點(diǎn)點(diǎn) B1B2B3B4發(fā)發(fā)量量 A16 25 2344 A244 27 35 16 A37658 3 3 收收量量243413 88 收收點(diǎn)點(diǎn) 發(fā)發(fā)點(diǎn)點(diǎn) B1B2B3B4發(fā)發(fā)量量 A16 25 2344 A24

51、4 27 35 16 A37658 3 3 收收量量243413 89 收收點(diǎn)點(diǎn) 發(fā)發(fā)點(diǎn)點(diǎn) B1B2B3B4發(fā)發(fā)量量 A16 25 2344 A244 27 35 16 A37658 3 3 收收量量243413 90 收收點(diǎn)點(diǎn) 發(fā)發(fā)點(diǎn)點(diǎn) B1B2B3B4發(fā)發(fā)量量 A16 25 2344 A244 27 35 16 A37658 3 3 收收量量243413 91 收收點(diǎn)點(diǎn) 發(fā)發(fā)點(diǎn)點(diǎn) B1B2B3B4發(fā)發(fā)量量 A16 25 2344 A244 27 35 16 A37658 3 3 收收量量243413 92 收收點(diǎn)點(diǎn) 發(fā)發(fā)點(diǎn)點(diǎn) B1B2B3B4發(fā)發(fā)量量 A16 25 2344 A244 27

52、 35 16 A37658 3 3 收收量量243413 93 收收點(diǎn)點(diǎn) 發(fā)發(fā)點(diǎn)點(diǎn) B1B2B3B4發(fā)發(fā)量量 A16 25 2344 A244 27 35 16 A37658 3 3 收收量量243413 94 收收點(diǎn)點(diǎn) 發(fā)發(fā)點(diǎn)點(diǎn) B1B2B3B4發(fā)發(fā)量量 A16 25 2344 A244 27 35 16 A37658 3 3 收收量量243413 95 收收點(diǎn)點(diǎn) 發(fā)發(fā)點(diǎn)點(diǎn) B1B2B3B4發(fā)發(fā)量量 A16 25 2344 A244 27 35 16 A37658 3 3 收收量量243413 96 收點(diǎn)收點(diǎn) 發(fā)點(diǎn)發(fā)點(diǎn) B1 B2 B3 B4 發(fā)量發(fā)量 A1 6 2 5 2 3(-5) 4(

53、-2) 4 A2 4 (-1) 4 2 7 3 5 1 6 A3 7(-1) 6(-1) 5(-5) 8 3 3 收量收量 2 4 3 4 13 顯然，當(dāng)所有非基變量的檢驗(yàn)數(shù)均大于或等于顯然，當(dāng)所有非基變量的檢驗(yàn)數(shù)均大于或等于 零時(shí)，調(diào)運(yùn)方案就是最優(yōu)方案，因?yàn)榇藭r(shí)對(duì)現(xiàn)行方零時(shí)，調(diào)運(yùn)方案就是最優(yōu)方案，因?yàn)榇藭r(shí)對(duì)現(xiàn)行方 案作任何調(diào)整都將導(dǎo)致總的運(yùn)輸費(fèi)用增加。案作任何調(diào)整都將導(dǎo)致總的運(yùn)輸費(fèi)用增加。 閉回路法的主要缺點(diǎn)是：閉回路法的主要缺點(diǎn)是：用閉回路法求檢驗(yàn)數(shù)用閉回路法求檢驗(yàn)數(shù) 時(shí)，需要給每一空格找一條閉回路。當(dāng)產(chǎn)銷點(diǎn)很多時(shí)，需要給每一空格找一條閉回路。當(dāng)產(chǎn)銷點(diǎn)很多 時(shí)，尋找閉回路以及計(jì)算兩方面都會(huì)

54、產(chǎn)生困難。時(shí)，尋找閉回路以及計(jì)算兩方面都會(huì)產(chǎn)生困難。 在運(yùn)輸問題的數(shù)學(xué)模型中（在運(yùn)輸問題的數(shù)學(xué)模型中（P P98 98），設(shè) ），設(shè)u u1 1 ，u u2 2， u um m ( (與 與 前前m m個(gè)等式對(duì)應(yīng)個(gè)等式對(duì)應(yīng)) )， ，v v1 1 ，v v2 2 v vn n ( (與后與后n n個(gè)等式對(duì)應(yīng)個(gè)等式對(duì)應(yīng)) )分分 別為對(duì)應(yīng)運(yùn)輸問題的別為對(duì)應(yīng)運(yùn)輸問題的m+nm+n個(gè)約束條件的對(duì)偶變量。步驟個(gè)約束條件的對(duì)偶變量。步驟 如下：如下： step1 step1 從任意從任意基變量（填數(shù)字格）基變量（填數(shù)字格）對(duì)應(yīng)的對(duì)應(yīng)的 c cij ij開始 開始, ,利利 用公式用公式c cij ij=

55、u =ui i+v+vj j 依次找出依次找出(m+n-1)(m+n-1)個(gè)個(gè)u ui i,v,vj j；任意給出一任意給出一 個(gè)個(gè)u ui i或或v vj j 值，推算出其它位勢(shì)值。值，推算出其它位勢(shì)值。稱這些稱這些u ui i,v,vj j為該基為該基 本可行解對(duì)應(yīng)的位勢(shì)；（本可行解對(duì)應(yīng)的位勢(shì)；（填數(shù)字格中按填數(shù)字格中按c cij ij=u =ui i+v+vj j確立確立 ui i,vj j ，方程組的解稱為位勢(shì)，方程組的解稱為位勢(shì)） step2step2 計(jì)算計(jì)算非基變量（空格）非基變量（空格）的檢驗(yàn)數(shù)：的檢驗(yàn)數(shù)： ij ij=c =cij ij- - （u ui i+v+vj j），

56、），填入括號(hào)內(nèi)填入括號(hào)內(nèi) 2.2.位勢(shì)法（位勢(shì)法（dual variable method,dual variable method,對(duì)偶變量法）對(duì)偶變量法） 第一步：第一步：在表上增加一行和一列，列中填入行位勢(shì)在表上增加一行和一列，列中填入行位勢(shì)ui ， 行中填入列位勢(shì)行中填入列位勢(shì)vj 。 按按 ui + vj = cij ( i , j ) 基變量指標(biāo)集，列出方程組基變量指標(biāo)集，列出方程組 先令先令u1= 0 ，由，由u1 + v3 = c13 = 3 可得可得v3 = 3 ，由，由u1 + v4 = c14 = 10 可得可得v4 = 10；在；在v4 = 10時(shí)，由時(shí)，由u3 + v

57、4 = c34 = 5 可得可得 u3 = -5 。以。以 此類推可確定所有的此類推可確定所有的 ui 、vj 的值。的值。 100 銷地銷地 產(chǎn)地產(chǎn)地 B1B2B3B4行位勢(shì)行位勢(shì) ui A1 3 11 3 4 10 3 0 A2 1 3 9 2 1 8 -1 A3 7 4 6 10 5 3 -5 列位勢(shì)列位勢(shì) vj 29310 初始基本可行解及位勢(shì)值初始基本可行解及位勢(shì)值 第二步：按第二步：按 ij = cij (ui + vj ) ,( i , j ) 非基變量指標(biāo)集，非基變量指標(biāo)集， 計(jì)算所有的空格檢驗(yàn)數(shù)計(jì)算所有的空格檢驗(yàn)數(shù)。如：。如： 11 = c11 (u1 + v1 ) =3 (

58、 0 + 2 ) = 1 12 = c12 (u1 + v2 ) = 11 - ( 0 + 9 ) = 2 這些計(jì)算可直接在表上進(jìn)行。為了方便，特設(shè)計(jì)這些計(jì)算可直接在表上進(jìn)行。為了方便，特設(shè)計(jì) 計(jì)算表，如下表。右上角框內(nèi)的數(shù)為單位運(yùn)價(jià)。計(jì)算表，如下表。右上角框內(nèi)的數(shù)為單位運(yùn)價(jià)。 102 銷地銷地 產(chǎn)地產(chǎn)地 B1B2B3B4行位勢(shì)行位勢(shì) ui A1 3 (1) 11 (2) 3 (0) 10 (0) 0 A2 1 (0) 9 (1) 2 (0) 8 (-1) -1 A3 7 (10) 4 (0) 10 (12) 5 (0) -5 列位勢(shì)列位勢(shì) vj 29310 在上表中還有負(fù)的檢驗(yàn)數(shù)，說明還未得

59、到最優(yōu)解，還得進(jìn)一步在上表中還有負(fù)的檢驗(yàn)數(shù)，說明還未得到最優(yōu)解，還得進(jìn)一步 進(jìn)行改進(jìn)。進(jìn)行改進(jìn)。 103 B1B2B3B4ui A1 A2 A3 vj 311310 192 74105 8 注意：基變量的檢驗(yàn)數(shù)注意：基變量的檢驗(yàn)數(shù) i j=Ci j -（ui+vj）=0 4 3 63 1 3 例：位勢(shì)法求檢驗(yàn)數(shù)例：位勢(shì)法求檢驗(yàn)數(shù) 104 B1B2B3B4ui A1 A2 A3 vj 311310 192 74105 8 令令u1=0 u1+v3=3 u1+ v4 =10 u2+ v3=2 u2+v1=1 u3+v2=4 u3+ v4=5 4 3 63 1 3 105 l2l10l3l9lvj

60、l-5 lA3 l-1lA2 l0 lA1 luilB4lB3lB2lB1 4 3 6 3 1 3 當(dāng)存在非基變量的檢驗(yàn)數(shù)當(dāng)存在非基變量的檢驗(yàn)數(shù) ij 0，說明現(xiàn)行方案，說明現(xiàn)行方案 為最優(yōu)方案，否則目標(biāo)成本還可以進(jìn)一步減小。為最優(yōu)方案，否則目標(biāo)成本還可以進(jìn)一步減小。 注意：非基變量的檢驗(yàn)數(shù)注意：非基變量的檢驗(yàn)數(shù) i j=ci j -（ui+vj） 11=c11 -（u1+v1）=3-(0+2)=1 31=c31 -（u3+v1）=7-(2-5)=10 24=c24 -（u2+v4）=8-(10-1)=-1 22=c22 -（u2+v2）=9-(9-1)=1 12=c12 -（u1+v2）=1