1、精選ppt第七章第七章 運輸問題運輸問題之表上作業法之表上作業法一、運輸問題模型及其求解一、運輸問題模型及其求解思路思路二、確定初始基本可行解二、確定初始基本可行解三、最優性檢驗三、最優性檢驗四、方案調整四、方案調整五、幾種特殊情況五、幾種特殊情況精選ppt一、運輸問題模型及其求解思路一、運輸問題模型及其求解思路v1、問題的提出：、問題的提出：v某公司從兩個產地某公司從兩個產地A1、A2將物品運往三將物品運往三個銷地個銷地B1、B2、B3。v各產地的產量、各銷地的銷量和各產地各產地的產量、各銷地的銷量和各產地運往各銷地每件物品的運費如下表所示。運往各銷地每件物品的運費如下表所示。v問：應如何調

2、運可使總運輸費用最小？問：應如何調運可使總運輸費用最小？精選ppt一、運輸問題模型及其求解思路一、運輸問題模型及其求解思路B1B2B3產量產量A1646200A2655300銷量銷量150150200精選ppt一、運輸問題模型及其求解思路一、運輸問題模型及其求解思路v2、產銷平衡運輸問題模型的特點、產銷平衡運輸問題模型的特點v從模型的建立可知：從模型的建立可知：v列數為列數為2（產地數）（產地數）3（銷地數）（銷地數）6；v行數為行數為2（產地數）（產地數）+3（銷地數）（銷地數）5；v再觀察模型的系數矩陣：再觀察模型的系數矩陣：精選ppt一、運輸問題模型及其求解思路一、運輸問題模型及其求解思

3、路 1 1 1 0 0 0 200 0 0 0 1 1 1 300 1 0 0 1 0 0 150 0 1 0 0 1 0 150 0 0 1 0 0 1 200前前2行之和后行之和后3行之和行之和精選ppt一、運輸問題模型及其求解思路一、運輸問題模型及其求解思路v對于產銷平衡的運輸問題，若產地為對于產銷平衡的運輸問題，若產地為m個，銷地為個，銷地為n個，個，v則變量個數為則變量個數為mn個，線性無關的約束個，線性無關的約束條件個數為條件個數為m+n-1，v故基本解中的基變量個數為故基本解中的基變量個數為m+n-1。精選ppt一、運輸問題模型及其求解思路一、運輸問題模型及其求解思路v3、運輸問

4、題求解思路、運輸問題求解思路表上作業法表上作業法v由于運輸規劃系數矩陣的特殊性，如果由于運輸規劃系數矩陣的特殊性，如果直接使用線性規劃單純形法求解計算，直接使用線性規劃單純形法求解計算，則無法利用這些有利條件。則無法利用這些有利條件。v人們在分析運輸規劃系數矩陣特征的基人們在分析運輸規劃系數矩陣特征的基礎上建立了針對運輸問題的礎上建立了針對運輸問題的表上作業法表上作業法。精選ppt一、運輸問題模型及其求解思路一、運輸問題模型及其求解思路B1B2B3產量產量A1 6 x11 4 x12 6 x13200A2 6 x21 5 x22 5 x23300銷量銷量150150200v我們關心的量均在運價

5、表和運量表中，我們關心的量均在運價表和運量表中，故將兩表和為故將兩表和為作業表作業表：精選ppt一、運輸問題模型及其求解思路一、運輸問題模型及其求解思路v表上作業法的總體思路和單純形法類似：表上作業法的總體思路和單純形法類似：基本可行解基本可行解是否最優解是否最優解結束結束換基換基是是否否每個步驟每個步驟都充分利都充分利用運輸表用運輸表的特點的特點精選ppt一、運輸問題模型及其求解思路一、運輸問題模型及其求解思路v例：某食品公司下屬的例：某食品公司下屬的A1、A2、A3 ，3個廠個廠生產方便食品，要運輸到生產方便食品，要運輸到B1、B2、B3、B4 ，4個銷售點，數據如下表，求最優運輸方案。個

6、銷售點，數據如下表，求最優運輸方案。B1B2B3B4產量產量A13113107A219284A3741059銷量銷量365620精選ppt二、確定初始基本可行解二、確定初始基本可行解v1、西北（左上）角法、西北（左上）角法v每次找最西北角的元素，讓其運輸量盡每次找最西北角的元素，讓其運輸量盡可能的滿足一個約束條件。可能的滿足一個約束條件。精選ppt二、確定初始基本可行解二、確定初始基本可行解B1B2B3B4產量產量A13113107A219284A3741059銷量銷量365620342236精選ppt二、確定初始基本可行解二、確定初始基本可行解這樣得到的初始基本可行解為：這樣得到的初始基本可

7、行解為：x11=3, x12=4, x22=2, x23=2, x33=3, x34=6，其，其余均為余均為0。對應的總運費為：對應的總運費為：33+411+29+22+310+65135精選ppt二、確定初始基本可行解二、確定初始基本可行解v2、最小元素法、最小元素法v每次找到剩下的最小運價，讓其對應的每次找到剩下的最小運價，讓其對應的運輸量盡可能的滿足一個約束條件。運輸量盡可能的滿足一個約束條件。精選ppt二、確定初始基本可行解二、確定初始基本可行解B1B2B3B4產量產量A13113107A219284A3741059銷量銷量365620343163精選ppt二、確定初始基本可行解二、確

8、定初始基本可行解用最小元素法求出的初始基本可行解為：用最小元素法求出的初始基本可行解為： x21 =3, x22 =1, x13 =4, x32 =6, x34=3, x14 =3,其余均為其余均為0。對應的總運費為：對應的總運費為：31+12+43+64+35+31086精選ppt二、確定初始基本可行解二、確定初始基本可行解v為保證基變量的個數有為保證基變量的個數有m+n-1個，注意：個，注意：v1、每次填完數，只能劃去一行或一列，只有、每次填完數，只能劃去一行或一列，只有最后一個格子例外。最后一個格子例外。v2、用最小元素法時，可能會出現基變量個數、用最小元素法時，可能會出現基變量個數還差

9、兩個以上但只剩下一行或一列的情況，還差兩個以上但只剩下一行或一列的情況，此時不能將剩下行或列按空格劃掉，應在剩此時不能將剩下行或列按空格劃掉，應在剩下的空格中標上下的空格中標上0。（退化的基本可行解）。（退化的基本可行解）精選ppt二、確定初始基本可行解二、確定初始基本可行解B1B2B3B4產量產量A13113108A219283A3741059銷量銷量365620353063精選ppt二、確定初始基本可行解二、確定初始基本可行解B1B2B3B4產量產量A13113104A219284A3741059銷量銷量365317340163精選ppt三、最優性檢驗三、最優性檢驗v檢驗數的意義：非基變量

10、增加一個單位，檢驗數的意義：非基變量增加一個單位，使目標函數值增加的數量。使目標函數值增加的數量。v運輸問題中目標函數值要求最小化，因運輸問題中目標函數值要求最小化，因此，當所有的檢驗數都大于或等于零時此，當所有的檢驗數都大于或等于零時該調運方案就是最優方案；否則不是。該調運方案就是最優方案；否則不是。v下面介紹兩種計算檢驗數的方法：下面介紹兩種計算檢驗數的方法：精選ppt三、最優性檢驗三、最優性檢驗v1、閉回路法、閉回路法v閉回路：在已給出基本解的運輸表上，從一閉回路：在已給出基本解的運輸表上，從一個非基變量出發，沿水平或豎直方向前進，個非基變量出發，沿水平或豎直方向前進，只有碰到基變量，才

11、能向右或向左轉只有碰到基變量，才能向右或向左轉90o (當當然也可以不改變方向）繼續前進。然也可以不改變方向）繼續前進。v這樣繼續下去，總能回到出發的那個非基變這樣繼續下去，總能回到出發的那個非基變量，由此路線形成的封閉曲線，叫閉回路。量，由此路線形成的封閉曲線，叫閉回路。精選ppt三、最優性檢驗三、最優性檢驗v每一個非基變量都有唯一的閉回路每一個非基變量都有唯一的閉回路B1B2B3B4產量產量A13113 410 37A21 392 184A374 6105 39銷量銷量365620精選ppt三、最優性檢驗三、最優性檢驗v觀察觀察x24的閉回路：的閉回路：v若讓第一個頂點非基變量若讓第一個頂

12、點非基變量x24的取值變為的取值變為1，為了保持產銷平衡，其閉回路上的頂點運量為了保持產銷平衡，其閉回路上的頂點運量都要調整，基數頂點都要調整，基數頂點+1，偶數頂點，偶數頂點-1。v上述調整使總的運輸費用發生的變化為上述調整使總的運輸費用發生的變化為 8 10 + 3 2 -1 ，這就說明原方案還不是最優，這就說明原方案還不是最優方案，需要進行調整。方案，需要進行調整。精選ppt三、最優性檢驗三、最優性檢驗B1B2B3B4產量產量A13113 410 37A21 392 184A374 6105 39銷量銷量365620v若讓若讓x111，則總運費變化：，則總運費變化：33+211 。精選p

13、pt三、最優性檢驗三、最優性檢驗v如果規定作為起始頂點的非基變量如果規定作為起始頂點的非基變量xij為第為第 1 個頂點，其閉回路上的其他頂點依次為第個頂點，其閉回路上的其他頂點依次為第 2 個頂點、第個頂點、第 3 個頂點個頂點，那么就有該非基，那么就有該非基變量的檢驗數：變量的檢驗數：v ij = (閉回路上的奇數頂點運價之和閉回路上的奇數頂點運價之和) - (閉回閉回路上的偶數頂點運價之和路上的偶數頂點運價之和)v最優標準：所有檢驗數最優標準：所有檢驗數0精選ppt三、最優性檢驗三、最優性檢驗B1B2B3B4產量產量A13 113 410 37A21 39 2 18 4A37 4 610

14、 5 39銷量銷量365620v檢驗數計算如下表：檢驗數計算如下表：（1）（2）（1）（-1）（10）（12）精選ppt三、最優性檢驗三、最優性檢驗v2、位勢法、位勢法v閉回路法的缺點：當變量個數較多時，尋找閉回路法的缺點：當變量個數較多時，尋找閉回路以及計算兩方面都容易出錯。閉回路以及計算兩方面都容易出錯。v位勢法：設產地位勢法：設產地Ai對應的位勢量為對應的位勢量為ui ，銷地，銷地Bj對應的位勢量為對應的位勢量為vj， 檢驗數檢驗數 ij =cij ui-vj。精選ppt三、最優性檢驗三、最優性檢驗B1B2B3B4產量產量uiA13 11 3 410 37u1A21 39 2 184u2

15、A37 4 6105 39u3銷量銷量365620vjv1v2v3v4精選ppt三、最優性檢驗三、最優性檢驗v根據基變量根據基變量xij 的檢驗數的檢驗數 ij =0 ，對應基變量，對應基變量的運價的運價cij可以分解為可以分解為ui 和和vj，即，即cij =ui+vj 。v因為位勢量因為位勢量ui ,vj的總數為的總數為m + n 個，而限定個，而限定方程只有方程只有m+n-1個（基變量個數），所以位個（基變量個數），所以位勢量（勢量（ ui ,vj ）有無窮多組解，其中總有一個）有無窮多組解，其中總有一個自由變量。自由變量。v故可以任意取一個位勢量賦以定值，從而確故可以任意取一個位勢量賦

16、以定值，從而確定其它位勢量的值，一般取定其它位勢量的值，一般取u1 0。精選ppt三、最優性檢驗三、最優性檢驗10392vj206563銷量銷量bj-595 310 4 67 A3-148 2 19 1 3A20710 33 411 3 A1ui產量產量aiB4B3B2B1（1）（2）（1）（-1）（10）（12）精選ppt檢驗數計算總結檢驗數計算總結v1、閉回路法計算式：、閉回路法計算式：v ij = (閉回路上的奇數頂點運價之和閉回路上的奇數頂點運價之和) - (閉回閉回路上的偶數頂點運價之和路上的偶數頂點運價之和)v2、位勢法計算式：、位勢法計算式：v ij = cij - ui vj

17、精選ppt四、方案調整四、方案調整B1B2B3B4產量產量A13 （1）11 （2）3 410 37A21 39 （1）2 18 （-1）4A37 （10）4 610 （12）5 39銷量銷量365620最小檢驗數最小檢驗數原則，確定原則，確定進基變量進基變量最小偶點原則，最小偶點原則，確定出基變量和確定出基變量和調整量調整量+1-1+1-1精選ppt四、方案調整四、方案調整B1B2B3B4產量產量aiA13 11 3 5 10 2 7A21 39 2 8 14A37 4 610 5 39銷量銷量bj365620v得到新的基變量：得到新的基變量：x13 = 5, x14 = 2, x21 =

18、3, x24 = 1, x32 = 6, x34 = 3。重新計算檢驗數。重新計算檢驗數。（0）（2）（2）（1）（9）（12）精選ppt四、方案調整四、方案調整v經過一次基變換，所有經過一次基變換，所有 ij 0，已得到最優解：，已得到最優解： x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3，其它為其它為0。v最優值：最優值：vf* =35+102+13+81+46+53 = 85精選ppt四、方案調整四、方案調整閉回路調整法步驟：閉回路調整法步驟：1、入基變量的確定：選負檢驗數中最小者、入基變量的確定：選負檢驗數中最小者 rk，那么

19、，那么 xrk 作為進基變量；（使總運費盡作為進基變量；（使總運費盡快減少）快減少）2、出基變量的確定：在進基變量、出基變量的確定：在進基變量xrk 的閉回的閉回路上，選取偶數頂點上調運量最小的值，將路上，選取偶數頂點上調運量最小的值，將其對應的運量作為出基變量。（剛好有一個其對應的運量作為出基變量。（剛好有一個基變量出基，其它基變量都為正）基變量出基，其它基變量都為正）精選ppt四、方案調整四、方案調整即求即求 =Minxij 閉回路上的偶數頂點的閉回路上的偶數頂點的xij= xpq。那么確定那么確定xpq為出基變量，為出基變量， 為調整量；為調整量；3、換基調整：對閉回路的奇數頂點運量調整

20、、換基調整：對閉回路的奇數頂點運量調整為：為：xij+ ，對各偶數頂點運量調整為：，對各偶數頂點運量調整為：xij- ，特別特別 xpq- =0，xpq變為非基變量。變為非基變量。重復以上步驟，直到所有檢驗數均非負，即重復以上步驟，直到所有檢驗數均非負，即得到最優解。得到最優解。精選ppt練習題練習題已知如下運價表，用表上作業法求解：已知如下運價表，用表上作業法求解：產銷產銷地地B1B2B3B4產量產量A165344A244756A376583銷量銷量243413精選ppt 初始解對應目標值為初始解對應目標值為33+41+42+44+8361產銷地產銷地B1B2B3B4產量產量uiA16534

21、4A244756A376583銷量銷量243413vj3421030341334(3)(2)(3)(0)(-1)(-2)精選ppt產銷地產銷地B1B2B3B4產量產量uiA165344A244756A376583銷量銷量243413vj4030240341332(3)(2)(3)(2)(1)(2) 已達到最優，最優目標值為已達到最優，最優目標值為44+42+44+5355精選ppt五、運輸問題的幾種特殊情況五、運輸問題的幾種特殊情況v1、多個最優方案的情況：、多個最優方案的情況：v若最優表中有非基變量的檢驗數為若最優表中有非基變量的檢驗數為0，則為多，則為多個最優方案的情況。個最優方案的情況。v這種情況下，可將檢驗數為這種情況下，可將檢驗數為0的非基變量作為的非基變量作為進基變量，即可得到另一個最優方案。進基變量，即可得到另