運(yùn)籌學(xué)運(yùn)輸問(wèn)題求解方法學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1第一頁(yè)，共21頁(yè)。第1頁(yè)/共21頁(yè)第二頁(yè)，共21頁(yè)。160萬(wàn)t分析(fnx)：產(chǎn)銷不平衡；根據(jù)現(xiàn)有產(chǎn)量，第IV地區(qū)最多能分配到:160-（30+70+0）=60萬(wàn)t(總廠量減去前三個(gè)地區(qū)最低需求量之和 ).210萬(wàn)t60萬(wàn)t則最大需求量為：50+70+30+60=210萬(wàn)t;最大需求210萬(wàn)t比供應(yīng)(gngyng)160萬(wàn)t多50萬(wàn)t,因此需要虛擬一個(gè)供應(yīng)(gngyng)點(diǎn)D，其供應(yīng)(gngyng)量為50萬(wàn)t，使得供求平衡。第2頁(yè)/共21頁(yè)第三頁(yè)，共21頁(yè)。M（任意大正數(shù))表示非常高的運(yùn)價(jià)，M不會(huì)(b hu)進(jìn)入最優(yōu)解1I2I1IV2IV產(chǎn)銷(chnxio)平衡表第3頁(yè)/共21頁(yè)第四

2、頁(yè)，共21頁(yè)。M（任意大正數(shù))表示非常高的運(yùn)價(jià)，M不會(huì)(b hu)進(jìn)入最優(yōu)解1I2I1IV2IV產(chǎn)銷(chnxio)平衡表第4頁(yè)/共21頁(yè)第五頁(yè)，共21頁(yè)。M（任意大正數(shù))表示非常高的運(yùn)價(jià)(yn ji)，M不會(huì)進(jìn)入最優(yōu)解1I2I1IV2IV產(chǎn)銷(chnxio)平衡表第5頁(yè)/共21頁(yè)第六頁(yè)，共21頁(yè)。*解的退化：在用最小元素法求解初始基本可行解時(shí)，當(dāng)產(chǎn)銷平衡表上填上一個(gè)數(shù)后，單位運(yùn)價(jià)(yn ji)表上要同時(shí)劃去一行和一列，則此時(shí)會(huì)出現(xiàn)退化。退化分為兩種情況。1I2I1IV2IV20求解步驟：利用最小元素(yun s)法求解運(yùn)輸問(wèn)題的初始解第6頁(yè)/共21頁(yè)第七頁(yè)，共21頁(yè)。1I2I1IV2IV20

3、30求解步驟：利用(lyng)最小元素法求解運(yùn)輸問(wèn)題的初始解*解的退化情況(qngkung)1：在確定供需關(guān)系時(shí)，若在（i,j）格內(nèi)填入數(shù)字后出現(xiàn)處 的余量等于 處的需量，此時(shí)在產(chǎn)銷平衡表上填上一個(gè)數(shù)后，單位運(yùn)價(jià)表上要同時(shí)劃去一行和一列，并在劃去的行或列的任一空格處填上一個(gè)0（始終保持表上有m+n-1個(gè)數(shù)字格）。iAjB第7頁(yè)/共21頁(yè)第八頁(yè)，共21頁(yè)。1I2I1IV2IV2030求解步驟(bzhu)：利用最小元素法求解運(yùn)輸問(wèn)題的初始解*解的退化情況1：在確定(qudng)供需關(guān)系時(shí)，若在（i,j）格內(nèi)填入數(shù)字后出現(xiàn)處 的余量等于 處的需量，此時(shí)在產(chǎn)銷平衡表上填上一個(gè)數(shù)后，單位運(yùn)價(jià)表上要同時(shí)劃

4、去一行和一列，并在劃去的行或列的任一空格處填上一個(gè)0（始終保持表上有m+n-1個(gè)數(shù)字格）。iAjB0第8頁(yè)/共21頁(yè)第九頁(yè)，共21頁(yè)。1I2I1IV2IV2030503020010050求解步驟(bzhu)：利用位勢(shì)法求解表中所有非基變量的檢驗(yàn)數(shù))(vucjiijij2262221615141211，MMMMMM2242029243332312422，M2323252404645434135，第9頁(yè)/共21頁(yè)第十頁(yè)，共21頁(yè)。1I2I1IV2IV2030503020010050.求解步驟(bzhu)：利用閉回路法進(jìn)行第一次方案調(diào)整30-20213131為換出變量，調(diào)整量為為換入變量，最小，故選

5、取檢驗(yàn)數(shù)XXM第10頁(yè)/共21頁(yè)第十一頁(yè)，共21頁(yè)。1I2I1IV2IV20305030200103020求解(qi ji)步驟：利用閉回路法進(jìn)方案調(diào)整得到下表表2221723191615141211，MMMMMMM2342025213332242221，MM242426414645434135，第11頁(yè)/共21頁(yè)第十二頁(yè)，共21頁(yè)。1I2I1IV2IV20305030200103020.求解步驟：表2未得最優(yōu)解，用閉回路法進(jìn)行(jnxng)第二次調(diào)整20-23363333為換出變量，調(diào)整量為為換入變量，最小，故選取檢驗(yàn)數(shù)XXM第12頁(yè)/共21頁(yè)第十三頁(yè)，共21頁(yè)。1I2I1IV2IV2030

6、503020010500求解步驟：利用閉回路(hul)法進(jìn)方案調(diào)整得到下表表3226041615141211，22-432-23532242221M，1134224645434136，MMMM第13頁(yè)/共21頁(yè)第十四頁(yè)，共21頁(yè)。1I2I1IV2IV2030503020010500.求解步驟： 表3未得最優(yōu)解，用閉回路(hul)法進(jìn)行第三次調(diào)整04-343232為換出變量，調(diào)整量為為換入變量，最小，故選取檢驗(yàn)數(shù)XX第14頁(yè)/共21頁(yè)第十五頁(yè)，共21頁(yè)。1I2I1IV2IV2030503020010500求解步驟：利用閉回路法進(jìn)方案調(diào)整得到(d do)下表表41210441615141211，2

7、2-47223534242221M，4-3-24234645434136，MMMM第15頁(yè)/共21頁(yè)第十六頁(yè)，共21頁(yè)。1I2I1IV2IV2030503020010500.求解步驟： 表4未得最優(yōu)解，用閉回路(hul)法進(jìn)行第四次調(diào)整204-424646為換出變量，調(diào)整量為為換入變量，最小，故選取檢驗(yàn)數(shù)XX第16頁(yè)/共21頁(yè)第十七頁(yè)，共21頁(yè)。1I2I1IV2IV20305030200103020求解(qi ji)步驟：利用閉回路法進(jìn)方案調(diào)整得到下表表5227441615141211，22-14223534242221M，MMMM4542413635332222，經(jīng)檢驗(yàn)，所有非基變量的檢驗(yàn)數(shù)

8、均為非負(fù)，因而表5給出的基本可行(kxng)解，即為問(wèn)題的最優(yōu)解。 第17頁(yè)/共21頁(yè)第十八頁(yè)，共21頁(yè)。1I2I1IV2IV3002030103020502050204050 最少總運(yùn)費(fèi)(yn fi)為：Z=1950+1350+1320+1540=2460萬(wàn)元。第18頁(yè)/共21頁(yè)第十九頁(yè)，共21頁(yè)?？偨Y(jié)(zngji)產(chǎn)銷不平衡(pnghng)運(yùn)輸問(wèn)題的求解方法:（1）產(chǎn)大于銷的問(wèn)題：增加虛銷地，銷量為產(chǎn)銷之差，但實(shí)際沒(méi)有運(yùn)輸，故單位運(yùn)價(jià)為0，這樣(zhyng)將該問(wèn)題轉(zhuǎn)化為產(chǎn)銷平衡問(wèn)題，然后用表上作業(yè)法求解。（2）產(chǎn)小于銷的問(wèn)題：增加虛產(chǎn)點(diǎn)，產(chǎn)量為銷產(chǎn)之差，但實(shí)際沒(méi)有運(yùn)輸，故單位運(yùn)價(jià)為0，這樣(zhyng)將該問(wèn)題轉(zhuǎn)化為產(chǎn)銷平衡問(wèn)題，然后用表上作業(yè)法求解。本次求解過(guò)程遇到的問(wèn)題及解決思路:（1） 同一個(gè)地區(qū)有兩種需求情況：凡是需求分兩種情況的地區(qū),可以看成兩個(gè)銷地：一個(gè)銷地為了保證最低需求，對(duì)應(yīng)的虛供應(yīng)點(diǎn)的單位運(yùn)價(jià)取任意大整數(shù)M(M不會(huì)進(jìn)入最優(yōu)解）。若已知某需求地 對(duì)某供應(yīng)地 沒(méi)有需求，則其相對(duì)應(yīng)的單位運(yùn)價(jià)取任意大整數(shù)M(M不會(huì)進(jìn)入最優(yōu)解）。（2）表上作業(yè)法計(jì)算中的退化問(wèn)題：在用最小元素法求解初始可行解時(shí)，在（i,j）格內(nèi)填入