表上作業(yè)法課件

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

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

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

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

——最小元素法、伏格爾法.伏格爾法思路罰數(shù)（即差額）的解釋：差額大，則不按最小運費調(diào)運，運費增加大。差額小，則不按最小運費調(diào)運，運費增加不大。.結(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)先安排銷地，否則運價會更高下次不考慮該列第一次.第二次行罰數(shù)②012列罰數(shù)213②優(yōu)先安排銷地，否則運價會更高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目標函數(shù)值用最小元素法求出的目標函數(shù)z=246一般說來，伏格爾法得出的初始解的質(zhì)量最好，常用來作為運輸問題最優(yōu)解的近似解。.列罰數(shù)1352①311174328510109銷量產(chǎn)量銷地產(chǎn)地練習行罰數(shù)①0第一次11優(yōu)先安排銷地，否則運價會更高630.311174328510109銷量產(chǎn)量銷地產(chǎn)地行罰數(shù)②0第二次12列罰數(shù)132630優(yōu)先安排銷地，否則運價會更高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.練習題用伏格爾法得到的初始基可行解311174328510109銷量產(chǎn)量銷地產(chǎn)地31

5

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

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

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

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

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

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

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

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

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