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

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

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

3、20 1 銷量銷量 1 19管理工程學院運籌學運籌學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ù)字管理工程學院運籌學運籌學66為一個初始調(diào)運方案，總運費為為一個初始調(diào)運方案，總運費為86元。元。注注1. 調(diào)運方案中，稱填寫數(shù)字處為調(diào)運方案中，稱填寫數(shù)字處為數(shù)字格數(shù)字格，它對應運輸問題解中的基變量取值；稱不填它對應運輸問題解中的基變量取值；稱不填數(shù)字處為數(shù)字處為空格空格，它對應解中非基變量。，它對應解中非基變量。注注2. 運輸問題

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

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

6、元素之差。 從所有行差額和列差額中選取差額最大的一行或從所有行差額和列差額中選取差額最大的一行或一列進行分配，并對該行一列進行分配，并對該行(或列或列)最小元素格填數(shù)，。最小元素格填數(shù)，。 重新計算差額，重復上述手續(xù)。重新計算差額，重復上述手續(xù)。 剩最后一行或一列按余額分配，只填數(shù)即可，確剩最后一行或一列按余額分配，只填數(shù)即可，確保有數(shù)字個數(shù)為保有數(shù)字個數(shù)為m+n-1個。個。管理工程學院運籌學運籌學1111 銷地產(chǎn)地B1 B2 B3 B4兩個最小元素之差A1A2A33 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管理工程學院運籌學運籌學1212三、最優(yōu)性檢驗與方案的調(diào)整三、最優(yōu)性檢驗與方案的調(diào)整1.閉回路法。最優(yōu)性檢驗：閉回路法。最優(yōu)性檢驗：運輸問題運輸問題 中的中的閉閉回路回路是指調(diào)運方案中由一個是指調(diào)運方案中由一個空格空格和若干個和若干個有有數(shù)字格數(shù)字格的水平和垂直連線包圍成的封閉回路。的水平和垂直連線包圍成的封閉回路。 構(gòu)建閉回路來計算解中各非基變量構(gòu)建閉回路來計算解中各非基變量(對應空格對應空格)的檢驗數(shù)。的檢驗數(shù)。管理工程學院運籌學運籌學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 管理工程學院運籌學運籌學1414（a） （b） （c） （d） （e）14管理工程學院運籌學運籌學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管理工程學院運籌學運籌學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)濟意義，判斷何時為最優(yōu)解？管理工程學院運籌學運籌學17172.2.位勢法（對偶變量法）位勢法（對偶變量法） 當一個運輸問題的產(chǎn)地和銷地數(shù)很多時，用閉回路法計算檢驗數(shù)計算量很大。位勢法是一種比較簡單的求檢驗數(shù)的方法。管理工程學院運籌學運籌學1818運輸問題（m+n）個約束條件對于（m+n）個對偶變量，設為Y=(u1, , um,v1, , vn) T ，xij的檢驗數(shù)為 )()(,(111jiijjminmijijTijijBijijijijvuceeuvuucPYcPBCczc管理工程學

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

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

12、框圖四、表上作業(yè)法求解運輸問題的步驟框圖分析實際問題列出分析實際問題列出產(chǎn)銷平衡表及單位運價表產(chǎn)銷平衡表及單位運價表確定初始調(diào)運方案確定初始調(diào)運方案(最小元素法或最小元素法或Vogel法法)求檢驗數(shù)求檢驗數(shù)(閉回路法或位勢法閉回路法或位勢法)所有檢驗數(shù)所有檢驗數(shù)0否否找出絕對值最大的負檢驗數(shù)找出絕對值最大的負檢驗數(shù)再用閉回路調(diào)整，再用閉回路調(diào)整，得出新的調(diào)運方案得出新的調(diào)運方案是是得到最優(yōu)方案得到最優(yōu)方案得出總的運價得出總的運價圖圖3-1 表上作業(yè)法表上作業(yè)法計算步驟框圖計算步驟框圖管理工程學院運籌學運籌學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 管理工程學院運籌學運籌學2828步步2，用位勢法求出上述方案的檢驗數(shù)如下表所示：，用位勢法求出上述方案的檢驗數(shù)如下表所示：13c21c14c34c A3 A2 A1B4B3B2B1產(chǎn)地產(chǎn)地銷地銷地311310192874105346133 iujv031 2105 932c23c1211 1012管理工程學院運籌學運籌學2929步步3，用閉回路調(diào)整方案得到新的方案，并用位勢法求檢驗，用閉回路調(diào)整方案得到新的方案，并用位勢法求檢驗數(shù)如下表：數(shù)如下表：1441 A3 A2 A1B4B3B2B1產(chǎn)地產(chǎn)地銷地銷地311310928710536133 iujv031 2105 9121 10124-230310