運(yùn)籌學(xué)運(yùn)輸問題求解方法

1、特殊運(yùn)輸問題的求解方法特殊運(yùn)輸問題的求解方法例例5.5產(chǎn)銷不平衡運(yùn)輸問題的求解方法產(chǎn)銷不平衡運(yùn)輸問題的求解方法 例例5.5 5.5 設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的農(nóng)用化肥。假定等量的化肥在這些地區(qū)使用效果相同，各化肥廠年產(chǎn)量、各地區(qū)年需量及從各化肥廠到各地區(qū)運(yùn)送化肥的單位運(yùn)價(jià)(萬元/萬t）如5-25所示。試求出總運(yùn)費(fèi)最少的化肥調(diào)撥方案。160萬萬t分析：產(chǎn)銷不平衡；根據(jù)現(xiàn)有產(chǎn)量，第分析：產(chǎn)銷不平衡；根據(jù)現(xiàn)有產(chǎn)量，第IVIV地區(qū)最地區(qū)最多能分配到多能分配到:160-:160-（30+70+030+70+0）=60=60萬萬t(t(總廠量減去總廠量減去前三個(gè)地區(qū)最低需求量之和前三個(gè)地區(qū)最低需求量之和

2、 ). ).210萬萬t60萬萬t則最大需求量為：則最大需求量為：50+70+30+60=21050+70+30+60=210萬萬t;t;最大需求最大需求210210萬萬t t比供應(yīng)比供應(yīng)160160萬萬t t多多5050萬萬t,t,因此需要因此需要虛擬一個(gè)供應(yīng)點(diǎn)虛擬一個(gè)供應(yīng)點(diǎn)D D，其供應(yīng)量為，其供應(yīng)量為5050萬萬t t，使得供求，使得供求平衡。平衡。M（任意大正數(shù)（任意大正數(shù))表示非常高的運(yùn)價(jià)，表示非常高的運(yùn)價(jià)，M不會(huì)進(jìn)入最優(yōu)解不會(huì)進(jìn)入最優(yōu)解1I2I1IV2IV產(chǎn)銷平衡表產(chǎn)銷平衡表M（任意大正數(shù)（任意大正數(shù))表示非常高的運(yùn)價(jià)，表示非常高的運(yùn)價(jià)，M不會(huì)進(jìn)入最優(yōu)解不會(huì)進(jìn)入最優(yōu)解1I2I1IV

3、2IV產(chǎn)銷平衡表產(chǎn)銷平衡表M（任意大正數(shù)（任意大正數(shù))表示非常高的運(yùn)價(jià)，表示非常高的運(yùn)價(jià)，M不會(huì)進(jìn)入最優(yōu)解不會(huì)進(jìn)入最優(yōu)解1I2I1IV2IV產(chǎn)銷平衡表產(chǎn)銷平衡表* *解的退化：解的退化：在用最小元素法求解初始基本可行解時(shí)，當(dāng)產(chǎn)銷平衡表上在用最小元素法求解初始基本可行解時(shí)，當(dāng)產(chǎn)銷平衡表上填上一個(gè)數(shù)后，單位運(yùn)價(jià)表上要同時(shí)劃去一行和一列，則此時(shí)會(huì)出現(xiàn)退填上一個(gè)數(shù)后，單位運(yùn)價(jià)表上要同時(shí)劃去一行和一列，則此時(shí)會(huì)出現(xiàn)退化。退化分為兩種情況?；Ｍ嘶譃閮煞N情況。1I2I1IV2IV20求解步驟：求解步驟：利用最小元素法求解運(yùn)輸問題的初始利用最小元素法求解運(yùn)輸問題的初始解解1I2I1IV2IV2030求解步

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

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

6、法求解表中所有非基變量的檢驗(yàn)數(shù)利用位勢(shì)法求解表中所有非基變量的檢驗(yàn)數(shù))(vucjiijij2262221615141211，MMMMMM2242029243332312422，M2323252404645434135，1I2I1IV2IV2030503020010050.求解步驟：求解步驟：利用閉回路法進(jìn)行第一次方案調(diào)整利用閉回路法進(jìn)行第一次方案調(diào)整30-20213131為換出變量，調(diào)整量為為換入變量，最小，故選取檢驗(yàn)數(shù)XXM1I2I1IV2IV20305030200103020求解步驟：求解步驟：利用閉回路法進(jìn)方案調(diào)整得到下表表利用閉回路法進(jìn)方案調(diào)整得到下表表2221723191615141

7、211，MMMMMMM2342025213332242221，MM242426414645434135，1I2I1IV2IV20305030200103020.求解步驟：求解步驟：表表2未得最優(yōu)解，用閉回路法進(jìn)行第二次調(diào)整未得最優(yōu)解，用閉回路法進(jìn)行第二次調(diào)整20-23363333為換出變量，調(diào)整量為為換入變量，最小，故選取檢驗(yàn)數(shù)XXM1I2I1IV2IV2030503020010500求解步驟：求解步驟：利用閉回路法進(jìn)方案調(diào)整得到下表表利用閉回路法進(jìn)方案調(diào)整得到下表表3226041615141211，22-432-23532242221M，1134224645434136，MMMM1I2I1I

8、V2IV2030503020010500.求解步驟：求解步驟： 表表3未得最優(yōu)解，用閉回路法進(jìn)行第三次調(diào)整未得最優(yōu)解，用閉回路法進(jìn)行第三次調(diào)整04-343232為換出變量，調(diào)整量為為換入變量，最小，故選取檢驗(yàn)數(shù)XX1I2I1IV2IV2030503020010500求解步驟：求解步驟：利用閉回路法進(jìn)方案調(diào)整得到下表表利用閉回路法進(jìn)方案調(diào)整得到下表表41210441615141211，22-47223534242221M，4-3-24234645434136，MMMM1I2I1IV2IV2030503020010500.求解步驟：求解步驟： 表表4未得最優(yōu)解，用閉回路法進(jìn)行第四次調(diào)整未得最優(yōu)解，

9、用閉回路法進(jìn)行第四次調(diào)整204-424646為換出變量，調(diào)整量為為換入變量，最小，故選取檢驗(yàn)數(shù)XX1I2I1IV2IV20305030200103020求解步驟：求解步驟：利用閉回路法進(jìn)方案調(diào)整得到下表表利用閉回路法進(jìn)方案調(diào)整得到下表表5227441615141211，22-14223534242221M，MMMM4542413635332222，經(jīng)檢驗(yàn)，所有非基變量的檢驗(yàn)數(shù)均為非負(fù)，因而表經(jīng)檢驗(yàn)，所有非基變量的檢驗(yàn)數(shù)均為非負(fù)，因而表5給出的基本可行解，給出的基本可行解，即為問題的最優(yōu)解。即為問題的最優(yōu)解。 1I2I1IV2IV3002030103020502050204050 最少總運(yùn)費(fèi)為：

10、最少總運(yùn)費(fèi)為：Z=1950+1350+1320+1540=2460萬元。萬元?？偨Y(jié)總結(jié)產(chǎn)銷不平衡運(yùn)輸問題的求解方法產(chǎn)銷不平衡運(yùn)輸問題的求解方法:（1）產(chǎn)大于銷的問題：增加虛銷地，銷量為產(chǎn)銷之差，但實(shí)際沒有運(yùn)輸，故單位運(yùn)）產(chǎn)大于銷的問題：增加虛銷地，銷量為產(chǎn)銷之差，但實(shí)際沒有運(yùn)輸，故單位運(yùn)價(jià)為價(jià)為0，這樣將該問題轉(zhuǎn)化為產(chǎn)銷平衡問題，然后用表上作業(yè)法求解。，這樣將該問題轉(zhuǎn)化為產(chǎn)銷平衡問題，然后用表上作業(yè)法求解。（2）產(chǎn)小于銷的問題：增加虛產(chǎn)點(diǎn)，產(chǎn)量為銷產(chǎn)之差，但實(shí)際沒有運(yùn)輸，故單位運(yùn)）產(chǎn)小于銷的問題：增加虛產(chǎn)點(diǎn)，產(chǎn)量為銷產(chǎn)之差，但實(shí)際沒有運(yùn)輸，故單位運(yùn)價(jià)為價(jià)為0，這樣將該問題轉(zhuǎn)化為產(chǎn)銷平衡問題，然

11、后用表上作業(yè)法求解。，這樣將該問題轉(zhuǎn)化為產(chǎn)銷平衡問題，然后用表上作業(yè)法求解。本次求解過程遇到的問題及解決思路本次求解過程遇到的問題及解決思路:（1） 同一個(gè)地區(qū)有兩種需求情況：同一個(gè)地區(qū)有兩種需求情況：凡是需求分兩種情況的地區(qū)凡是需求分兩種情況的地區(qū),可以看成兩個(gè)銷地：一個(gè)銷地為了保證最低可以看成兩個(gè)銷地：一個(gè)銷地為了保證最低需求，對(duì)應(yīng)的虛供應(yīng)點(diǎn)的單位運(yùn)價(jià)取任意大整數(shù)需求，對(duì)應(yīng)的虛供應(yīng)點(diǎn)的單位運(yùn)價(jià)取任意大整數(shù)M(M不會(huì)進(jìn)入最優(yōu)解）。不會(huì)進(jìn)入最優(yōu)解）。若已知某需求地若已知某需求地 對(duì)某供應(yīng)地對(duì)某供應(yīng)地 沒有需求，則其相對(duì)應(yīng)的單位運(yùn)價(jià)取沒有需求，則其相對(duì)應(yīng)的單位運(yùn)價(jià)取任意大整數(shù)任意大整數(shù)M(M不會(huì)進(jìn)入最優(yōu)解）。不會(huì)進(jìn)入最優(yōu)解）。（2）表上作業(yè)法計(jì)算中的退化問題：）表上作業(yè)法計(jì)算中的退化問題：在用最小元素法求解初始可行解時(shí)，在（在用最小元素法求解初始可行解時(shí)，在（i,j）格內(nèi)填入數(shù)字后出現(xiàn)）