表上作業(yè)法課件

第二節(jié)運(yùn)輸問題的表上作業(yè)法由上節(jié)介紹運(yùn)輸問題的數(shù)學(xué)模型及其約束方程組的系數(shù)矩陣結(jié)構(gòu)的特殊性，本節(jié)將由此給出運(yùn)輸問題的比單純形法更為簡便的求解方法—表上作業(yè)法。.單純形法與表上作業(yè)法的關(guān)系：（1）找出初始基可行解（2）求各非基變量的檢驗(yàn)數(shù)（3）判斷是否最優(yōu)解計(jì)算表中空格檢驗(yàn)數(shù)表上給出m+n-1個(gè)數(shù)字格判斷方法相同.換基:（4）確定換入變量和換出變量找出新的基可行解。（5）重復(fù)（2）、（3）直至求出最優(yōu)解。表上調(diào)整（閉回路調(diào)整）（運(yùn)輸問題必有最優(yōu)解）停止最優(yōu)解？是否.舉例說明表上作業(yè)法某部門三個(gè)工廠生產(chǎn)同一產(chǎn)品的產(chǎn)量,四個(gè)銷售點(diǎn)的銷量及單位運(yùn)價(jià)如下表：4122854396111110銷量產(chǎn)量銷地產(chǎn)地.第一步：確定初始基可行解

——最小元素法、伏格爾法【1】最小元素法思路：

就近供應(yīng)，從單價(jià)中最小運(yùn)價(jià)確定供應(yīng)量，逐步次小，直至得到m+n-1個(gè)數(shù)字格。

.最小元素法舉例4122854396111110銷量產(chǎn)量銷地產(chǎn)地822010100614868000060.最小元素法得到的初始調(diào)運(yùn)方案4122854396111110銷量產(chǎn)量銷地產(chǎn)地82101468.練習(xí)某部門三個(gè)工廠生產(chǎn)同一產(chǎn)品的產(chǎn)量,四個(gè)銷售點(diǎn)的銷量及單位運(yùn)價(jià)如下表：311174328510109銷量產(chǎn)量銷地產(chǎn)地.最小元素法練習(xí)311174328510109銷量產(chǎn)量銷地產(chǎn)地311044036333000030.初始調(diào)運(yùn)方案311174328510109銷量產(chǎn)量銷地產(chǎn)地314633最小元素法缺點(diǎn)：會出現(xiàn)顧此失彼（運(yùn)費(fèi)差額問題）考慮運(yùn)價(jià)差.罰數(shù)（即差額）=次小運(yùn)價(jià)-最小運(yùn)價(jià)對差額最大處，采用最小運(yùn)費(fèi)調(diào)運(yùn)。【2】伏格爾法思路：第一步：確定初始基可行解

——最小元素法、伏格爾法.伏格爾法思路罰數(shù)（即差額）的解釋：差額大，則不按最小運(yùn)費(fèi)調(diào)運(yùn)，運(yùn)費(fèi)增加大。差額小，則不按最小運(yùn)費(fèi)調(diào)運(yùn)，運(yùn)費(fèi)增加不大。.結(jié)合例1說明這種方法。4122854396111110銷量產(chǎn)量銷地產(chǎn)地行罰數(shù)①04-4=0第一次.4122854396111110銷量產(chǎn)量銷地產(chǎn)地行罰數(shù)①013-2=1第一次.4122854396111110銷量產(chǎn)量銷地產(chǎn)地行罰數(shù)①011第一次.4122854396111110銷量產(chǎn)量銷地產(chǎn)地行罰數(shù)①011列罰數(shù)2153①第一次.4122854396111110銷量產(chǎn)量銷地產(chǎn)地行罰數(shù)①011列罰數(shù)2153①1480優(yōu)先安排銷地，否則運(yùn)價(jià)會更高下次不考慮該列第一次.第二次行罰數(shù)②012列罰數(shù)213②優(yōu)先安排銷地，否則運(yùn)價(jià)會更高84122854396111110銷量產(chǎn)量銷地產(chǎn)地148006下次不考慮該行.行罰數(shù)③01列罰數(shù)212③84122854396111110銷量產(chǎn)量銷地產(chǎn)地148006下次不考慮該列802第三次.行罰數(shù)④76列罰數(shù)12④84122854396111110銷量產(chǎn)量銷地產(chǎn)地1480068024120下次不考慮該列第四次.行罰數(shù)⑤00列罰數(shù)2⑤4284122854396111110銷量產(chǎn)量銷地產(chǎn)地1480068024120004第五次0.例1用伏格爾法得到的初始基可行解4122854396111110銷量產(chǎn)量銷地產(chǎn)地48148122目標(biāo)函數(shù)值用最小元素法求出的目標(biāo)函數(shù)z=246一般說來，伏格爾法得出的初始解的質(zhì)量最好，常用來作為運(yùn)輸問題最優(yōu)解的近似解。.列罰數(shù)1352①311174328510109銷量產(chǎn)量銷地產(chǎn)地練習(xí)行罰數(shù)①0第一次11優(yōu)先安排銷地，否則運(yùn)價(jià)會更高630.311174328510109銷量產(chǎn)量銷地產(chǎn)地行罰數(shù)②0第二次12列罰數(shù)132630優(yōu)先安排銷地，否則運(yùn)價(jià)會更高303②.311174328510109銷量產(chǎn)量銷地產(chǎn)地行罰數(shù)③0第三次1列罰數(shù)122630303③310.311174328510109銷量產(chǎn)量銷地產(chǎn)地行罰數(shù)④7第四次6列罰數(shù)12630303④310502.311174328510109銷量產(chǎn)量銷地產(chǎn)地行罰數(shù)⑤0第五次0列罰數(shù)2630303⑤310502120200.練習(xí)題用伏格爾法得到的初始基可行解311174328510109銷量產(chǎn)量銷地產(chǎn)地31

5

623用最小元素法求出的目標(biāo)函數(shù)z=86.第二步：解的最優(yōu)性檢驗(yàn)思路：計(jì)算空格（非基變量）的檢驗(yàn)數(shù)。兩種方法：【1】閉回路法每一空格出發(fā)一定存在且可以找到唯一的閉回路。【2】位勢法由對偶理論，得檢驗(yàn)數(shù)為。.【1】閉回路法在給出調(diào)運(yùn)方案的計(jì)算表上，從每一空格出發(fā)找一條閉回路。

以某空格為起點(diǎn)，用水平或垂直線向前劃，當(dāng)碰到一數(shù)字格時(shí)，可以轉(zhuǎn)90度（也可以越過）后，繼續(xù)前進(jìn)，直到回到起始空格為止。.每一空格出發(fā)一定存在且可以找到唯一的閉回路。因m+n-1個(gè)數(shù)字格（基變量）對應(yīng)的系數(shù)向量是一個(gè)基。則任一空格（非基變量）對應(yīng)的系數(shù)向量均可由這個(gè)基線性表示。.閉回路法的經(jīng)濟(jì)解釋若令分析：——運(yùn)費(fèi)的增量即增加1個(gè)單位的檢驗(yàn)數(shù)=相應(yīng)的運(yùn)費(fèi)增量.4122854396111110銷量產(chǎn)量銷地產(chǎn)地82101468從初始表分析：要保證產(chǎn)銷平衡，則稱為閉回路+1-1+1-1.4122854396111110銷量產(chǎn)量銷地產(chǎn)地8210146821.檢驗(yàn)數(shù)表4122854396111110銷量產(chǎn)量銷地產(chǎn)地82101468211-11012表中的解不是最優(yōu)解。.或稱對偶變量法【2】位勢法.運(yùn)輸問題的對偶問題可寫為運(yùn)輸問題的對偶問題

——對偶變量與原問題檢驗(yàn)數(shù)的關(guān)系.線性規(guī)劃問題變量的檢驗(yàn)數(shù)為運(yùn)輸問題的對偶問題

——對偶變量與原問題檢驗(yàn)數(shù)的關(guān)系變量的檢驗(yàn)數(shù)為.設(shè)運(yùn)輸問題的一組基變量為運(yùn)輸問題的對偶問題

——對偶變量與原問題檢驗(yàn)數(shù)的關(guān)系.由于基變量的檢驗(yàn)數(shù)為零，故有運(yùn)輸問題的對偶問題

——對偶變量與原問題檢驗(yàn)數(shù)的關(guān)系m+n-1個(gè)方程m+n個(gè)變量有一個(gè)自由未知量.方程組有解，且不唯一。求出方程組的解（稱為位勢）而其他變量的檢驗(yàn)數(shù)為運(yùn)輸問題的對偶問題

——對偶變量與原問題檢驗(yàn)數(shù)的關(guān)系求運(yùn)輸問題檢驗(yàn)數(shù)的一種方法.最小元素法得到的初始基可行解311174328510109銷量產(chǎn)量銷地產(chǎn)地314633為基變量。則有..銷地產(chǎn)地000000311174328510109-11021211存在負(fù)檢驗(yàn)數(shù)，說明不是最優(yōu)解。檢驗(yàn)數(shù)表.第三步：解的調(diào)整當(dāng)在表中空格處出現(xiàn)負(fù)檢驗(yàn)數(shù)時(shí)，表示未得最優(yōu)解。若有兩個(gè)和兩個(gè)以上的負(fù)檢驗(yàn)數(shù)，一般選其中最小的負(fù)檢驗(yàn)數(shù)，以它對應(yīng)的空格為調(diào)入格。即選擇最小檢驗(yàn)數(shù)對應(yīng)的非基變量為換入變量。.第三步：解的調(diào)整調(diào)整位置（A2，B4）非空，回路角上的格至少為空，且保證數(shù)字的非負(fù)性。4122854396111110銷量產(chǎn)量銷地產(chǎn)地82101468-1（-）（-）（+）（+）2222.調(diào)整后的解為：4122854396111110銷量產(chǎn)量銷地產(chǎn)地821214482209112此時(shí)的解為最優(yōu)解。有無窮多最優(yōu)解.幾點(diǎn)說明：當(dāng)檢驗(yàn)數(shù)為負(fù)的變量超過兩個(gè)，選擇最小者對應(yīng)的變量換入；在最優(yōu)解的表中，若有非基變量的檢驗(yàn)數(shù)=0，則該運(yùn)輸問題有無窮多最優(yōu)解；.幾點(diǎn)說明：退化一

迭代過程中，若某一格填數(shù)時(shí)需同時(shí)劃去一行和一列，此時(shí)出現(xiàn)退化。為保證m+n-1個(gè)非空格，需在上述的行或列中填入數(shù)字0。.退化情況一：某部門三個(gè)工廠生產(chǎn)同一產(chǎn)品的產(chǎn)量,四個(gè)銷售點(diǎn)的銷量及單位運(yùn)價(jià)如下表：4122854396111110銷量產(chǎn)量銷地產(chǎn)地8800.幾點(diǎn)說明：退化二閉回路上出現(xiàn)兩個(gè)或兩個(gè)以上的具有（-）標(biāo)記的相等的最小值。只能選一個(gè)作為調(diào)入格，經(jīng)調(diào)整后，得退化解。則在另一數(shù)字格上填入0。.退化情況二：

閉回路法調(diào)整，