管理運(yùn)籌學(xué)-第七章-運(yùn)輸問題之表上作業(yè)法ppt課件

1、第七章 運(yùn)輸問題之表上作業(yè)法,一、運(yùn)輸問題模型及其求解思路 二、確定初始基本可行解 三、最優(yōu)性檢驗(yàn) 四、方案調(diào)整 五、幾種特殊情況,一、運(yùn)輸問題模型及其求解思路,1、問題的提出： 某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3。 各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示。 問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小,一、運(yùn)輸問題模型及其求解思路,一、運(yùn)輸問題模型及其求解思路,2、產(chǎn)銷平衡運(yùn)輸問題模型的特點(diǎn) 從模型的建立可知： 列數(shù)為2（產(chǎn)地?cái)?shù)）3（銷地?cái)?shù)）6； 行數(shù)為2（產(chǎn)地?cái)?shù)）+3（銷地?cái)?shù)）5； 再觀察模型的系數(shù)矩陣,一、運(yùn)輸問題模型及其求解思路,前2行之和后

2、3行之和,一、運(yùn)輸問題模型及其求解思路,對(duì)于產(chǎn)銷平衡的運(yùn)輸問題，若產(chǎn)地為m個(gè)，銷地為n個(gè)， 則變量個(gè)數(shù)為mn個(gè)，線性無關(guān)的約束條件個(gè)數(shù)為m+n-1， 故基本解中的基變量個(gè)數(shù)為m+n-1,一、運(yùn)輸問題模型及其求解思路,3、運(yùn)輸問題求解思路表上作業(yè)法 由于運(yùn)輸規(guī)劃系數(shù)矩陣的特殊性，如果直接使用線性規(guī)劃單純形法求解計(jì)算，則無法利用這些有利條件。 人們?cè)诜治鲞\(yùn)輸規(guī)劃系數(shù)矩陣特征的基礎(chǔ)上建立了針對(duì)運(yùn)輸問題的表上作業(yè)法,一、運(yùn)輸問題模型及其求解思路,我們關(guān)心的量均在運(yùn)價(jià)表和運(yùn)量表中，故將兩表和為作業(yè)表,一、運(yùn)輸問題模型及其求解思路,表上作業(yè)法的總體思路和單純形法類似,每個(gè)步驟都充分利用運(yùn)輸表的特點(diǎn),一、運(yùn)

3、輸問題模型及其求解思路,例：某食品公司下屬的A1、A2、A3 ，3個(gè)廠生產(chǎn)方便食品，要運(yùn)輸?shù)紹1、B2、B3、B4 ，4個(gè)銷售點(diǎn)，數(shù)據(jù)如下表，求最優(yōu)運(yùn)輸方案,二、確定初始基本可行解,1、西北（左上）角法 每次找最西北角的元素，讓其運(yùn)輸量盡可能的滿足一個(gè)約束條件,二、確定初始基本可行解,3,4,2,2,3,6,二、確定初始基本可行解,這樣得到的初始基本可行解為：x11=3, x12=4, x22=2, x23=2, x33=3, x34=6，其余均為0。對(duì)應(yīng)的總運(yùn)費(fèi)為：33+411+29+22+310+65135,二、確定初始基本可行解,2、最小元素法 每次找到剩下的最小運(yùn)價(jià)，讓其對(duì)應(yīng)的運(yùn)輸量盡

4、可能的滿足一個(gè)約束條件,二、確定初始基本可行解,3,4,3,1,6,3,二、確定初始基本可行解,用最小元素法求出的初始基本可行解為： x21 =3, x22 =1, x13 =4, x32 =6, x34=3, x14 =3,其余均為0。對(duì)應(yīng)的總運(yùn)費(fèi)為：31+12+43+64+35+31086,二、確定初始基本可行解,為保證基變量的個(gè)數(shù)有m+n-1個(gè)，注意： 1、每次填完數(shù)，只能劃去一行或一列，只有最后一個(gè)格子例外。 2、用最小元素法時(shí)，可能會(huì)出現(xiàn)基變量個(gè)數(shù)還差兩個(gè)以上但只剩下一行或一列的情況，此時(shí)不能將剩下行或列按空格劃掉，應(yīng)在剩下的空格中標(biāo)上0。（退化的基本可行解,二、確定初始基本可行解,

5、3,5,3,0,6,3,二、確定初始基本可行解,3,4,0,1,6,3,三、最優(yōu)性檢驗(yàn),檢驗(yàn)數(shù)的意義：非基變量增加一個(gè)單位，使目標(biāo)函數(shù)值增加的數(shù)量。 運(yùn)輸問題中目標(biāo)函數(shù)值要求最小化，因此，當(dāng)所有的檢驗(yàn)數(shù)都大于或等于零時(shí)該調(diào)運(yùn)方案就是最優(yōu)方案；否則不是。 下面介紹兩種計(jì)算檢驗(yàn)數(shù)的方法,三、最優(yōu)性檢驗(yàn),1、閉回路法 閉回路：在已給出基本解的運(yùn)輸表上，從一個(gè)非基變量出發(fā)，沿水平或豎直方向前進(jìn)，只有碰到基變量，才能向右或向左轉(zhuǎn)90o (當(dāng)然也可以不改變方向）繼續(xù)前進(jìn)。 這樣繼續(xù)下去，總能回到出發(fā)的那個(gè)非基變量，由此路線形成的封閉曲線，叫閉回路,三、最優(yōu)性檢驗(yàn),每一個(gè)非基變量都有唯一的閉回路,三、最優(yōu)性

6、檢驗(yàn),觀察x24的閉回路： 若讓第一個(gè)頂點(diǎn)非基變量x24的取值變?yōu)?，為了保持產(chǎn)銷平衡，其閉回路上的頂點(diǎn)運(yùn)量都要調(diào)整，基數(shù)頂點(diǎn)+1，偶數(shù)頂點(diǎn)-1。 上述調(diào)整使總的運(yùn)輸費(fèi)用發(fā)生的變化為 8 10 + 3 2 -1 ，這就說明原方案還不是最優(yōu)方案，需要進(jìn)行調(diào)整,三、最優(yōu)性檢驗(yàn),若讓x111，則總運(yùn)費(fèi)變化：33+211,三、最優(yōu)性檢驗(yàn),如果規(guī)定作為起始頂點(diǎn)的非基變量xij為第 1 個(gè)頂點(diǎn)，其閉回路上的其他頂點(diǎn)依次為第 2 個(gè)頂點(diǎn)、第 3 個(gè)頂點(diǎn)，那么就有該非基變量的檢驗(yàn)數(shù)： ij = (閉回路上的奇數(shù)頂點(diǎn)運(yùn)價(jià)之和) - (閉回路上的偶數(shù)頂點(diǎn)運(yùn)價(jià)之和) 最優(yōu)標(biāo)準(zhǔn)：所有檢驗(yàn)數(shù)0,三、最優(yōu)性檢驗(yàn),檢驗(yàn)數(shù)計(jì)

7、算如下表,1,2,1,1,10,12,三、最優(yōu)性檢驗(yàn),2、位勢(shì)法 閉回路法的缺點(diǎn)：當(dāng)變量個(gè)數(shù)較多時(shí)，尋找閉回路以及計(jì)算兩方面都容易出錯(cuò)。 位勢(shì)法：設(shè)產(chǎn)地Ai對(duì)應(yīng)的位勢(shì)量為ui ，銷地Bj對(duì)應(yīng)的位勢(shì)量為vj， 檢驗(yàn)數(shù)ij =cij ui-vj,三、最優(yōu)性檢驗(yàn),三、最優(yōu)性檢驗(yàn),根據(jù)基變量xij 的檢驗(yàn)數(shù)ij =0 ，對(duì)應(yīng)基變量的運(yùn)價(jià)cij可以分解為ui 和vj，即cij =ui+vj 。 因?yàn)槲粍?shì)量ui ,vj的總數(shù)為m + n 個(gè)，而限定方程只有m+n-1個(gè)（基變量個(gè)數(shù)），所以位勢(shì)量（ ui ,vj ）有無窮多組解，其中總有一個(gè)自由變量。 故可以任意取一個(gè)位勢(shì)量賦以定值，從而確定其它位勢(shì)量的值，

8、一般取u1 0,三、最優(yōu)性檢驗(yàn),10,3,9,2,vj,20,6,5,6,3,銷量bj,5,9,5 3,10,4 6,7,A3,1,4,8,2 1,9,1 3,A2,0,7,10 3,3 4,11,3,A1,ui,產(chǎn)量ai,B4,B3,B2,B1,1,2,1,1,10,12,檢驗(yàn)數(shù)計(jì)算總結(jié),1、閉回路法計(jì)算式： ij = (閉回路上的奇數(shù)頂點(diǎn)運(yùn)價(jià)之和) - (閉回路上的偶數(shù)頂點(diǎn)運(yùn)價(jià)之和) 2、位勢(shì)法計(jì)算式： ij = cij - ui vj,四、方案調(diào)整,最小檢驗(yàn)數(shù)原則，確定進(jìn)基變量,最小偶點(diǎn)原則，確定出基變量和調(diào)整量,1,1,1,1,四、方案調(diào)整,得到新的基變量：x13 = 5, x14 =

9、 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3。重新計(jì)算檢驗(yàn)數(shù),0,2,2,1,9,12,四、方案調(diào)整,經(jīng)過一次基變換，所有ij 0，已得到最優(yōu)解： x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3，其它為0。 最優(yōu)值： f* =35+102+13+81+46+53 = 85,四、方案調(diào)整,閉回路調(diào)整法步驟： 1、入基變量的確定：選負(fù)檢驗(yàn)數(shù)中最小者 rk，那么 xrk 作為進(jìn)基變量；（使總運(yùn)費(fèi)盡快減少） 2、出基變量的確定：在進(jìn)基變量xrk 的閉回路上，選取偶數(shù)頂點(diǎn)上調(diào)運(yùn)量最小的值，將其對(duì)應(yīng)的運(yùn)量作為出基變量

10、。（剛好有一個(gè)基變量出基，其它基變量都為正,四、方案調(diào)整,即求=Minxij閉回路上的偶數(shù)頂點(diǎn)的xij= xpq。那么確定xpq為出基變量，為調(diào)整量； 3、換基調(diào)整：對(duì)閉回路的奇數(shù)頂點(diǎn)運(yùn)量調(diào)整為：xij+，對(duì)各偶數(shù)頂點(diǎn)運(yùn)量調(diào)整為：xij-，特別 xpq-=0，xpq變?yōu)榉腔兞俊?重復(fù)以上步驟，直到所有檢驗(yàn)數(shù)均非負(fù)，即得到最優(yōu)解,練習(xí)題已知如下運(yùn)價(jià)表，用表上作業(yè)法求解,初始解對(duì)應(yīng)目標(biāo)值為33+41+42+44+8361,3,4,2,1,0,3,0,3,4,1,3,3,4,3,2,3,0,1,2,4,0,3,0,2,4,0,3,4,1,3,3,2,3,2,3,2,1,2,已達(dá)到最優(yōu)，最優(yōu)目標(biāo)值為44+42+44+5355,五、運(yùn)輸問題的幾種特殊情況,1、多個(gè)最優(yōu)方案的情況： 若最優(yōu)表中有非基變量的檢驗(yàn)數(shù)為0，則為多個(gè)最優(yōu)方案的情況。 這種情況下，可將檢驗(yàn)數(shù)為0的非基變量作為進(jìn)基變量，即可得到另一個(gè)最優(yōu)方案,五、運(yùn)輸問題的幾種特殊情況,如上例中的最優(yōu)方案就不唯一,0,2,2,1,9,12,檢驗(yàn)數(shù)為0者進(jìn)基,最小偶點(diǎn)為出基變量和調(diào)整量,2,2,2,2,五、運(yùn)輸問題的幾種特殊情況,得到另一個(gè)最優(yōu)方案： x11 = 2, x13 = 5, x21 = 1, x24 = 3, x32 = 6, x34 = 3, 其余 xij = 0； 最優(yōu)值仍然為 f* = 8