第二節(jié)表上作業(yè)法

1、管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)11第二節(jié)第二節(jié) 表上作業(yè)法表上作業(yè)法一、表上作業(yè)法一、表上作業(yè)法(其其實質(zhì)就是單純形法實質(zhì)就是單純形法)步驟：步驟：確定初始方案確定初始方案判斷是否最優(yōu)判斷是否最優(yōu)調(diào)整改進(jìn)方案調(diào)整改進(jìn)方案否輸出最優(yōu)方案是管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)22二、初始方案的確定二、初始方案的確定確定方法要求：方法簡單易行、并能給出較確定方法要求：方法簡單易行、并能給出較好的方案，減少迭代次數(shù)。好的方案，減少迭代次數(shù)。1.西北角法：西北角法：此方法是從表的西北角上開始，此方法是從表的西北角上開始，即首先盡量把產(chǎn)地即首先盡量把產(chǎn)地1的物資滿足銷地的物資滿足銷地1的要求，的要求，4管理工程學(xué)院運(yùn)籌學(xué)運(yùn)

2、籌學(xué)33若產(chǎn)地若產(chǎn)地1有剩余再供應(yīng)銷地有剩余再供應(yīng)銷地2；若銷地；若銷地1得不得不到滿足，則不足的部分由產(chǎn)地到滿足，則不足的部分由產(chǎn)地2來供應(yīng)。以來供應(yīng)。以后依次類似。這種方法比較簡單，但沒有考后依次類似。這種方法比較簡單，但沒有考慮使運(yùn)價最少的問題。慮使運(yùn)價最少的問題。2.最小元素法：最小元素法：基本思想是就近供應(yīng)。即從基本思想是就近供應(yīng)。即從單位運(yùn)價表中最小的運(yùn)價處開始確定供銷關(guān)單位運(yùn)價表中最小的運(yùn)價處開始確定供銷關(guān)系，依此類推，一直到給出全部方案為止。系，依此類推，一直到給出全部方案為止。5管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)44 銷地銷地產(chǎn)地產(chǎn)地 B1 B2 產(chǎn)量產(chǎn)量 A1 1 6 1 A2 2

3、20 1 銷量銷量 1 19管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)55 銷地產(chǎn)地 B1B2B3B4產(chǎn)量 A1 437 A2 314 A3 639銷量3656349111023581071不能填不能填4，要，要滿足銷量要求滿足銷量要求3+1=4m+n-1=3+4-1=6個數(shù)字個數(shù)字管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)66為一個初始調(diào)運(yùn)方案，總運(yùn)費(fèi)為為一個初始調(diào)運(yùn)方案，總運(yùn)費(fèi)為86元。元。注注1. 調(diào)運(yùn)方案中，稱填寫數(shù)字處為調(diào)運(yùn)方案中，稱填寫數(shù)字處為數(shù)字格數(shù)字格，它對應(yīng)運(yùn)輸問題解中的基變量取值；稱不填它對應(yīng)運(yùn)輸問題解中的基變量取值；稱不填數(shù)字處為數(shù)字處為空格空格，它對應(yīng)解中非基變量。，它對應(yīng)解中非基變量。注注2. 運(yùn)輸問題

4、中基變量數(shù)一般為運(yùn)輸問題中基變量數(shù)一般為(m+n-1)個，個，故調(diào)運(yùn)方案中有數(shù)字的格也為故調(diào)運(yùn)方案中有數(shù)字的格也為(m+n-1)個。個。管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)77 銷地產(chǎn)地 B1B2B3B4產(chǎn)量 A1 437 A2 33 A3 639銷量36463491110235810710管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)88注注3. 當(dāng)選定最小元素后，發(fā)現(xiàn)該元素所在行當(dāng)選定最小元素后，發(fā)現(xiàn)該元素所在行的產(chǎn)地現(xiàn)有產(chǎn)量等于所在列的銷地銷量，要的產(chǎn)地現(xiàn)有產(chǎn)量等于所在列的銷地銷量，要在同時劃去的該行和該列的任一空格處在同時劃去的該行和該列的任一空格處補(bǔ)填補(bǔ)填一個一個“0” 。即每劃一下填一數(shù)字，即每劃一下填一數(shù)字，不要

5、漏不要漏掉基變量掉基變量“0”。管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)993. Vogel法法(元素差額法元素差額法)。用最小元素法給定用最小元素法給定初始方案只能從局部觀點考慮就近供應(yīng)，劃初始方案只能從局部觀點考慮就近供應(yīng)，劃去的行或列可能存在次小元素，從而造成總?cè)サ男谢蛄锌赡艽嬖诖涡≡?，從而造成總體的不合理。體的不合理。Vogel法是從運(yùn)價表中各行和法是從運(yùn)價表中各行和各列最小和次小元素之差來確定產(chǎn)銷關(guān)系。各列最小和次小元素之差來確定產(chǎn)銷關(guān)系。4管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)1010Vogel法步驟：法步驟： 在運(yùn)價表上寫出每行和每列運(yùn)價中最小元素和次在運(yùn)價表上寫出每行和每列運(yùn)價中最小元素和次小元素之差。小

6、元素之差。 從所有行差額和列差額中選取差額最大的一行或從所有行差額和列差額中選取差額最大的一行或一列進(jìn)行分配，并對該行一列進(jìn)行分配，并對該行(或列或列)最小元素格填數(shù)，。最小元素格填數(shù)，。 重新計算差額，重復(fù)上述手續(xù)。重新計算差額，重復(fù)上述手續(xù)。 剩最后一行或一列按余額分配，只填數(shù)即可，確剩最后一行或一列按余額分配，只填數(shù)即可，確保有數(shù)字個數(shù)為保有數(shù)字個數(shù)為m+n-1個。個。管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)1111 銷地產(chǎn)地B1 B2 B3 B4兩個最小元素之差A(yù)1A2A33 11 3 101 9 2 87 4 10 5兩個最小元素之差0112 5 1 3 0122 1 3 012 1 2 76 1

7、2 銷地產(chǎn)地 B1 B2 B3 B4產(chǎn)量 A1 A2 A3 5 23 1 6 3749銷量3 6 5 6管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)1212三、最優(yōu)性檢驗與方案的調(diào)整三、最優(yōu)性檢驗與方案的調(diào)整1.閉回路法。最優(yōu)性檢驗：閉回路法。最優(yōu)性檢驗：運(yùn)輸問題運(yùn)輸問題 中的中的閉閉回路回路是指調(diào)運(yùn)方案中由一個是指調(diào)運(yùn)方案中由一個空格空格和若干個和若干個有有數(shù)字格數(shù)字格的水平和垂直連線包圍成的封閉回路。的水平和垂直連線包圍成的封閉回路。 構(gòu)建閉回路來計算解中各非基變量構(gòu)建閉回路來計算解中各非基變量(對應(yīng)空格對應(yīng)空格)的檢驗數(shù)。的檢驗數(shù)。管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)1313 修正量6563 銷 量9 A34 A27

8、A1 修正量產(chǎn)量B4B3B2B1產(chǎn)地產(chǎn)地銷地銷地31131019287410530 3,40 60 11,4 30 3 3 0 3, 0 0 管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)1414（a） （b） （c） （d） （e）14管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)1515 銷地產(chǎn)地 B1B2B3B4產(chǎn)量 A1 437 A2 314 A3 639銷量3656349111023581071+-+-11= c11- c13+ c23-c21 = 3-3+2-1=131= c31- c21+ c23-c31 + c14-c34 = 10管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)1616 銷地產(chǎn)地B1 B2 B3 B4 A1 A2 A31 2

9、1 -110 1211=1；12=2； 22=1； 24=-1； 31=10； 33=12如何根據(jù)檢驗數(shù)的經(jīng)濟(jì)意義，判斷何時為最優(yōu)解？管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)1717 位勢法（對偶變量法）位勢法（對偶變量法） 當(dāng)一個運(yùn)輸問題的產(chǎn)地和銷地數(shù)很多時，用閉回路法計算檢驗數(shù)計算量很大。位勢法是一種比較簡單的求檢驗數(shù)的方法。管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)1818運(yùn)輸問題（m+n）個約束條件對于（m+n）個對偶變量，設(shè)為Y=(u1, , um,v1, , vn) T ，xij的檢驗數(shù)為 )()(,(111jiijjminmijijTijijBijijijijvuceeuvuucPYcPBCczc管理工程學(xué)院運(yùn)籌

10、學(xué)運(yùn)籌學(xué)1919步驟：步驟： 單位運(yùn)價表中，單位運(yùn)價用cij表示 求行位勢ui和列位勢vj ，cij= ui+ vj計算檢驗數(shù)ij=cij-(ui+vj)管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)202013c21c14c34c A3 A2 A1B4B3B2B1產(chǎn)地產(chǎn)地銷地銷地311310192874105346133 iujv031 2105 932c23c1211 1012管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)21213 3 方案的調(diào)整方案的調(diào)整閉回路法調(diào)整法步驟：閉回路法調(diào)整法步驟： 找到mn =minij |ij 0對應(yīng)的空格找到該空格的閉回路，并從空格開始正、負(fù)相間地編號找到標(biāo)負(fù)號處的最小運(yùn)量1. 在該閉回路的運(yùn)量

11、上，標(biāo)正號處加 ，標(biāo)負(fù)號處減管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)2222 銷地產(chǎn)地 B1B2B3B4產(chǎn)量 A1 437 A2 314 A3 639銷量3656349111023581071+-+-管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)2323 銷地產(chǎn)地 B1B2B3B4產(chǎn)量 A1 527 A2 3 14 A3 639銷量3656 349111023581071管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)2424 注意：閉回路調(diào)整中的問題注意：閉回路調(diào)整中的問題 比如比如+-+-232=2052052管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)2525 比如比如+-+-032=0230管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)2626四、表上作業(yè)法求解運(yùn)輸問題的步驟框圖四、表上

12、作業(yè)法求解運(yùn)輸問題的步驟框圖分析實際問題列出分析實際問題列出產(chǎn)銷平衡表及單位運(yùn)價表產(chǎn)銷平衡表及單位運(yùn)價表確定初始調(diào)運(yùn)方案確定初始調(diào)運(yùn)方案(最小元素法或最小元素法或Vogel法法)求檢驗數(shù)求檢驗數(shù)(閉回路法或位勢法閉回路法或位勢法)所有檢驗數(shù)所有檢驗數(shù)0否否找出絕對值最大的負(fù)檢驗數(shù)找出絕對值最大的負(fù)檢驗數(shù)再用閉回路調(diào)整，再用閉回路調(diào)整，得出新的調(diào)運(yùn)方案得出新的調(diào)運(yùn)方案是是得到最優(yōu)方案得到最優(yōu)方案得出總的運(yùn)價得出總的運(yùn)價圖圖3-1 表上作業(yè)法表上作業(yè)法計算步驟框圖計算步驟框圖管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)2727例例1 解：解：步步1，用最小元素法求出初始方案如下表所示：，用最小元素法求出初始方案如下表

13、所示： 修正量6563 銷 量9 A34 A27 A1 修正量產(chǎn)量B4B3B2B1產(chǎn)地產(chǎn)地銷地銷地31131019287410530 3,40 60 11,4 30 3 3 0 3, 0 0 管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)2828步步2，用位勢法求出上述方案的檢驗數(shù)如下表所示：，用位勢法求出上述方案的檢驗數(shù)如下表所示：13c21c14c34c A3 A2 A1B4B3B2B1產(chǎn)地產(chǎn)地銷地銷地311310192874105346133 iujv031 2105 932c23c1211 1012管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)2929步步3，用閉回路調(diào)整方案得到新的方案，并用位勢法求檢驗，用閉回路調(diào)整方案得到新的方案，并用位勢法求檢驗數(shù)如下表：數(shù)如下表：1441 A3 A2 A1B4B3B2B1產(chǎn)地產(chǎn)地銷地銷地311310928710536133 iujv031 2105 9121 10124-230310