表上作業(yè)法.PPT

1、管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)11第二節(jié)第二節(jié) 表上作業(yè)法表上作業(yè)法一、表上作業(yè)法一、表上作業(yè)法(其其實(shí)質(zhì)就是單純形法實(shí)質(zhì)就是單純形法)步驟：步驟：確定初始方案確定初始方案判斷是否最優(yōu)判斷是否最優(yōu)調(diào)整改進(jìn)方案調(diào)整改進(jìn)方案否輸出最優(yōu)方案是管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)22二、初始方案的確定二、初始方案的確定確定方法要求：方法簡(jiǎn)單易行、并能給出較確定方法要求：方法簡(jiǎn)單易行、并能給出較好的方案，減少迭代次數(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)。以后依次類似。這種方法比較簡(jiǎn)單，但沒有考后依次類似。這種方法比較簡(jiǎn)單，但沒有考慮使運(yùn)價(jià)最少的問題。慮使運(yùn)價(jià)最少的問題。2.最小元素法：最小元素法：基本思想是就近供應(yīng)。即從基本思想是就近供應(yīng)。即從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)處開始確定供銷關(guān)單位運(yùn)價(jià)表中最小的運(yùn)價(jià)處開始確定供銷關(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個(gè)數(shù)字個(gè)數(shù)字管理工程學(xué)院運(yùn)籌學(xué)運(yùn)籌學(xué)66為一個(gè)初始調(diào)運(yùn)方案，總運(yùn)費(fèi)為為一個(gè)初始調(diào)運(yùn)方案，總運(yùn)費(fèi)為86元。元。注注1. 調(diào)運(yùn)方案中，稱填寫數(shù)字處為調(diào)運(yùn)方案中，稱填寫數(shù)字處為數(shù)字格數(shù)字格，它對(duì)應(yīng)運(yùn)輸問題解中的基變量取值；稱不填它對(duì)應(yīng)運(yùn)輸問題解中的基變量取值；稱不填數(shù)字處為數(shù)字處為空格空格，它對(duì)應(yīng)解中非基變量。，它對(duì)應(yīng)解中非基變量。注注2. 運(yùn)輸問題

4、中基變量數(shù)一般為運(yùn)輸問題中基變量數(shù)一般為(m+n-1)個(gè)，個(gè)，故調(diào)運(yùn)方案中有數(shù)字的格也為故調(diào)運(yùn)方案中有數(shù)字的格也為(m+n-1)個(gè)。個(gè)。管理工程學(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)量等于所在列的銷地銷量，要在同時(shí)劃去的該行和該列的任一空格處在同時(shí)劃去的該行和該列的任一空格處補(bǔ)填補(bǔ)填一個(gè)一個(gè)“0” 。即每劃一下填一數(shù)字，即每劃一下填一數(shù)字，不要

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

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

10、學(xué)運(yùn)籌學(xué)1919步驟：步驟： 單位運(yùn)價(jià)表中，單位運(yùn)價(jià)用cij表示 求行位勢(shì)ui和列位勢(shì)vj ，cij= ui+ vj計(jì)算檢驗(yàn)數(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對(duì)應(yīng)的空格找到該空格的閉回路，并從空格開始正、負(fù)相間地編號(hào)找到標(biāo)負(fù)號(hào)處的最小運(yùn)量1. 在該閉回路的運(yùn)量上

11、，標(biāo)正號(hào)處加 ，標(biāo)負(fù)號(hào)處減管理工程學(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)輸問題的步驟框圖分析實(shí)際問題列出分析實(shí)際問題列出產(chǎn)銷平衡表及單位運(yùn)價(jià)表產(chǎn)銷平衡表及單位運(yùn)價(jià)表確定初始調(diào)運(yùn)方案確定初始調(diào)運(yùn)方案(最小元素法或最小元素法或Vogel法法)求檢驗(yàn)數(shù)求檢驗(yàn)數(shù)(閉回路法或位勢(shì)法閉回路法或位勢(shì)法)所有檢驗(yàn)數(shù)所有檢驗(yàn)數(shù)0否否找出絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)找出絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)再用閉回路調(diào)整，再用閉回路調(diào)整，得出新的調(diào)運(yùn)方案得出新的調(diào)運(yùn)方案是是得到最優(yōu)方案得到最優(yōu)方案得出總的運(yùn)價(jià)得出總的運(yùn)價(jià)圖圖3-1 表上作業(yè)法表上作業(yè)法計(jì)算步驟框圖計(jì)算步驟框圖管理工程學(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ì)法求出上述方案的檢驗(yàn)數(shù)如下表所示：，用位勢(shì)法求出上述方案的檢驗(yàn)數(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)整方案得到新的方案，并用位勢(shì)法求檢驗(yàn)，用閉回路調(diào)整方案得到新的方案，并用位勢(shì)法求檢驗(yàn)數(shù)如下表：數(shù)如下表：1441 A3 A2 A1B4B3B2B1產(chǎn)地產(chǎn)地銷地銷地311310928710536133 iujv031 2105 9121 10124-230310