表上作業(yè)法演示

表上作業(yè)法ppt課件目前一頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法單純形法與表上作業(yè)法的關(guān)系：（1）找出初始基可行解（2）求各非基變量的檢驗(yàn)數(shù)（3）判斷是否最優(yōu)解計(jì)算表中空格檢驗(yàn)數(shù)表上給出m+n-1個數(shù)字格判斷方法相同目前二頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法換基:（4）確定換入變量和換出變量找出新的基可行解。（5）重復(fù)（2）、（3）直至求出最優(yōu)解。表上調(diào)整（閉回路調(diào)整）（運(yùn)輸問題必有最優(yōu)解）停止最優(yōu)解？是否目前三頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法舉例說明表上作業(yè)法某部門三個工廠生產(chǎn)同一產(chǎn)品的產(chǎn)量,四個銷售點(diǎn)的銷量及單位運(yùn)價如下表：4122854396111110銷量產(chǎn)量銷地產(chǎn)地目前四頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法第一步：確定初始基可行解

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

就近供應(yīng)，從單價中最小運(yùn)價確定供應(yīng)量，逐步次小，直至得到m+n-1個數(shù)字格。目前五頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法最小元素法舉例4122854396111110銷量產(chǎn)量銷地產(chǎn)地822010100614868000060目前六頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法最小元素法得到的初始調(diào)運(yùn)方案4122854396111110銷量產(chǎn)量銷地產(chǎn)地82101468目前七頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法練習(xí)某部門三個工廠生產(chǎn)同一產(chǎn)品的產(chǎn)量,四個銷售點(diǎn)的銷量及單位運(yùn)價如下表：311174328510109銷量產(chǎn)量銷地產(chǎn)地目前八頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法最小元素法練習(xí)311174328510109銷量產(chǎn)量銷地產(chǎn)地311044036333000030目前九頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法初始調(diào)運(yùn)方案311174328510109銷量產(chǎn)量銷地產(chǎn)地314633最小元素法缺點(diǎn)：會出現(xiàn)顧此失彼（運(yùn)費(fèi)差額問題）考慮運(yùn)價差目前十頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法罰數(shù)（即差額）=次小運(yùn)價-最小運(yùn)價對差額最大處，采用最小運(yùn)費(fèi)調(diào)運(yùn)?！?】伏格爾法思路：第一步：確定初始基可行解

——最小元素法、伏格爾法目前十一頁\總數(shù)五十三頁\編于十一點(diǎn)伏格爾法思路罰數(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)增加不大。運(yùn)輸問題——表上作業(yè)法目前十二頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法結(jié)合例1說明這種方法。4122854396111110銷量產(chǎn)量銷地產(chǎn)地行罰數(shù)①04-4=0第一次目前十三頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法4122854396111110銷量產(chǎn)量銷地產(chǎn)地行罰數(shù)①013-2=1第一次目前十四頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法4122854396111110銷量產(chǎn)量銷地產(chǎn)地行罰數(shù)①011第一次目前十五頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法4122854396111110銷量產(chǎn)量銷地產(chǎn)地行罰數(shù)①011列罰數(shù)2153①第一次目前十六頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法4122854396111110銷量產(chǎn)量銷地產(chǎn)地行罰數(shù)①011列罰數(shù)2153①1480優(yōu)先安排銷地，否則運(yùn)價會更高下次不考慮該列第一次目前十七頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法第二次行罰數(shù)②012列罰數(shù)213②優(yōu)先安排銷地，否則運(yùn)價會更高84122854396111110銷量產(chǎn)量銷地產(chǎn)地148006下次不考慮該行目前十八頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法行罰數(shù)③01列罰數(shù)212③84122854396111110銷量產(chǎn)量銷地產(chǎn)地148006下次不考慮該列802第三次目前十九頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法行罰數(shù)④76列罰數(shù)12④84122854396111110銷量產(chǎn)量銷地產(chǎn)地1480068024120下次不考慮該列第四次目前二十頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法行罰數(shù)⑤00列罰數(shù)2⑤4284122854396111110銷量產(chǎn)量銷地產(chǎn)地1480068024120004第五次0目前二十一頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法例1用伏格爾法得到的初始基可行解4122854396111110銷量產(chǎn)量銷地產(chǎn)地48148122目標(biāo)函數(shù)值用最小元素法求出的目標(biāo)函數(shù)z=246一般說來，伏格爾法得出的初始解的質(zhì)量最好，常用來作為運(yùn)輸問題最優(yōu)解的近似解。目前二十二頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法列罰數(shù)1352①311174328510109銷量產(chǎn)量銷地產(chǎn)地練習(xí)行罰數(shù)①0第一次11優(yōu)先安排銷地，否則運(yùn)價會更高630目前二十三頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法311174328510109銷量產(chǎn)量銷地產(chǎn)地行罰數(shù)②0第二次12列罰數(shù)132630優(yōu)先安排銷地，否則運(yùn)價會更高303②目前二十四頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法311174328510109銷量產(chǎn)量銷地產(chǎn)地行罰數(shù)③0第三次1列罰數(shù)122630303③310目前二十五頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法311174328510109銷量產(chǎn)量銷地產(chǎn)地行罰數(shù)④7第四次6列罰數(shù)12630303④310502目前二十六頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法311174328510109銷量產(chǎn)量銷地產(chǎn)地行罰數(shù)⑤0第五次0列罰數(shù)2630303⑤310502120200目前二十七頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法練習(xí)題用伏格爾法得到的初始基可行解311174328510109銷量產(chǎn)量銷地產(chǎn)地31

5

623用最小元素法求出的目標(biāo)函數(shù)z=86目前二十八頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法第二步：解的最優(yōu)性檢驗(yàn)思路：計(jì)算空格（非基變量）的檢驗(yàn)數(shù)。兩種方法：【1】閉回路法每一空格出發(fā)一定存在且可以找到唯一的閉回路?！?】位勢法由對偶理論，得檢驗(yàn)數(shù)為。目前二十九頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題——表上作業(yè)法【1】閉回路法在給出調(diào)運(yùn)方案的計(jì)算表上，從每一空格出發(fā)找一條閉回路。

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

——對偶變量與原問題檢驗(yàn)數(shù)的關(guān)系目前三十七頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題線性規(guī)劃問題變量的檢驗(yàn)數(shù)為運(yùn)輸問題的對偶問題

——對偶變量與原問題檢驗(yàn)數(shù)的關(guān)系變量的檢驗(yàn)數(shù)為目前三十八頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題設(shè)運(yùn)輸問題的一組基變量為運(yùn)輸問題的對偶問題

——對偶變量與原問題檢驗(yàn)數(shù)的關(guān)系目前三十九頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題由于基變量的檢驗(yàn)數(shù)為零，故有運(yùn)輸問題的對偶問題

——對偶變量與原問題檢驗(yàn)數(shù)的關(guān)系m+n-1個方程m+n個變量有一個自由未知量目前四十頁\總數(shù)五十三頁\編于十一點(diǎn)運(yùn)輸問題方程組有解，且不唯一。求出方程組的解（稱為位勢）而其他變量的檢驗(yàn)數(shù)為運(yùn)輸問題的對偶問題

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

迭代過程中，若某一