表上作業(yè)法演示

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

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

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

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

5

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

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

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

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

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

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

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

迭代過(guò)程中，若某一