管理運籌學(xué)第七章 運輸問題之表上作業(yè)法

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

2、運可使總運輸費用最?。繂枺簯?yīng)如何調(diào)運可使總運輸費用最?。烤xppt一、運輸問題模型及其求解思路一、運輸問題模型及其求解思路B1B2B3產(chǎn)量產(chǎn)量A1646200A2655300銷量銷量150150200精選ppt一、運輸問題模型及其求解思路一、運輸問題模型及其求解思路v2、產(chǎn)銷平衡運輸問題模型的特點、產(chǎn)銷平衡運輸問題模型的特點v從模型的建立可知：從模型的建立可知：v列數(shù)為列數(shù)為2（產(chǎn)地數(shù)）（產(chǎn)地數(shù)）3（銷地數(shù)）（銷地數(shù)）6；v行數(shù)為行數(shù)為2（產(chǎn)地數(shù)）（產(chǎn)地數(shù)）+3（銷地數(shù)）（銷地數(shù)）5；v再觀察模型的系數(shù)矩陣：再觀察模型的系數(shù)矩陣：精選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對于產(chǎn)銷平衡的運輸問題，若產(chǎn)地為對于產(chǎn)銷平衡的運輸問題，若產(chǎn)地為m個，銷地為個，銷地為n個，個，v則變量個數(shù)為則變量個數(shù)為mn個，線性無關(guān)的約束個，線性無關(guān)的約束條件個數(shù)為條件個數(shù)為m+n-1，v故基本解中的基變量個數(shù)為故基本解中的基變量個數(shù)為m+n-1。精選ppt一、運輸問題模型及其求解思路一、運輸問題模型及其求解思路v3、運輸問

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

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

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

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

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

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

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

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

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

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

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

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

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

17、精選ppt四、方案調(diào)整四、方案調(diào)整B1B2B3B4產(chǎn)量產(chǎn)量A13 （1）11 （2）3 410 37A21 39 （1）2 18 （-1）4A37 （10）4 610 （12）5 39銷量銷量365620最小檢驗數(shù)最小檢驗數(shù)原則，確定原則，確定進(jìn)基變量進(jìn)基變量最小偶點原則，最小偶點原則，確定出基變量和確定出基變量和調(diào)整量調(diào)整量+1-1+1-1精選ppt四、方案調(diào)整四、方案調(diào)整B1B2B3B4產(chǎn)量產(chǎn)量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。重新計算檢驗數(shù)。重新計算檢驗數(shù)。（0）（2）（2）（1）（9）（12）精選ppt四、方案調(diào)整四、方案調(diào)整v經(jīng)過一次基變換，所有經(jīng)過一次基變換，所有 ij 0，已得到最優(yōu)解：，已得到最優(yōu)解： x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3，其它為其它為0。v最優(yōu)值：最優(yōu)值：vf* =35+102+13+81+46+53 = 85精選ppt四、方案調(diào)整四、方案調(diào)整閉回路調(diào)整法步驟：閉回路調(diào)整法步驟：1、入基變量的確定：選負(fù)檢驗數(shù)中最小者、入基變量的確定：選負(fù)檢驗數(shù)中最小者 rk，那么

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

20、、換基調(diào)整：對閉回路的奇數(shù)頂點運量調(diào)整為：為：xij+ ，對各偶數(shù)頂點運量調(diào)整為：，對各偶數(shù)頂點運量調(diào)整為：xij- ，特別特別 xpq- =0，xpq變?yōu)榉腔兞俊Ｗ優(yōu)榉腔兞?。重?fù)以上步驟，直到所有檢驗數(shù)均非負(fù)，即重復(fù)以上步驟，直到所有檢驗數(shù)均非負(fù)，即得到最優(yōu)解。得到最優(yōu)解。精選ppt練習(xí)題練習(xí)題已知如下運價表，用表上作業(yè)法求解：已知如下運價表，用表上作業(yè)法求解：產(chǎn)銷產(chǎn)銷地地B1B2B3B4產(chǎn)量產(chǎn)量A165344A244756A376583銷量銷量243413精選ppt 初始解對應(yīng)目標(biāo)值為初始解對應(yīng)目標(biāo)值為33+41+42+44+8361產(chǎn)銷地產(chǎn)銷地B1B2B3B4產(chǎn)量產(chǎn)量uiA16534

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