運籌學運輸問題求解方法

1、特殊運輸問題的求解方法特殊運輸問題的求解方法例例5.5產(chǎn)銷不平衡運輸問題的求解方法產(chǎn)銷不平衡運輸問題的求解方法 例例5.5 5.5 設(shè)有三個化肥廠供應四個地區(qū)的農(nóng)用化肥。假定等量的化肥在這些地區(qū)使用效果相同，各化肥廠年產(chǎn)量、各地區(qū)年需量及從各化肥廠到各地區(qū)運送化肥的單位運價(萬元/萬t）如5-25所示。試求出總運費最少的化肥調(diào)撥方案。運價運價 需求需求 化肥廠化肥廠 I I II II IIIIII IVIV 產(chǎn)產(chǎn) 量量A A 16161313222217175050B B14141313191915156060C C 191920202323- -5050最低需求最低需求303070700

2、01010 最高需求最高需求505070703030不限不限運價運價 需求需求 化肥廠化肥廠 I I II II IIIIII IVIV 產(chǎn)產(chǎn) 量量A A 16161313222217175050B B14141313191915156060C C 191920202323- -5050最低需求最低需求303070700 01010110(110(萬萬t)t) 不限不限最高需求最高需求505070703030不限不限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=

3、60萬萬t(t(總廠量減去總廠量減去前三個地區(qū)最低需求量之和前三個地區(qū)最低需求量之和 ). ).210萬萬t60萬萬t則最大需求量為：則最大需求量為：50+70+30+60=21050+70+30+60=210萬萬t;t;最大需求最大需求210210萬萬t t比供應比供應160160萬萬t t多多5050萬萬t,t,因此需要因此需要虛擬一個供應點虛擬一個供應點D D，其供應量為，其供應量為5050萬萬t t，使得供求，使得供求平衡。平衡。運價運價 需求需求 化肥廠化肥廠 I I II II IIIIII IVIV 產(chǎn)產(chǎn) 量量A A 16161313222217175050B B14141313

4、191915156060C C 191920202323- -5050最低需求最低需求303070700 01010110110 萬萬t t （210210）最高需求最高需求505070703030不限不限（6060）運價運價 需求需求地地 供應地供應地 IIIIIIIIII 供應供應 量量 A A 16161616 5050 B B14141414 6060 C C 191919195050 D D M M 0 0 5050 需求量需求量 3030 2020 M（任意大正數(shù)（任意大正數(shù))表示非常高的運價，表示非常高的運價，M不會進入最優(yōu)解不會進入最優(yōu)解1I2I1IV2IV產(chǎn)銷平衡表產(chǎn)銷平衡表

5、運價運價 需求需求 化肥廠化肥廠 I I II II IIIIII IVIV 產(chǎn)產(chǎn) 量量A A 16161313222217175050B B14141313191915156060C C 191920202323- -5050最低需求最低需求303070700 01010110110 t t （210210）最高需求最高需求505070703030不限不限（6060）運價運價 需求需求地地 供應地供應地 IIIIIIIIII 供應供應 量量 A A 1616161613 13 5050 B B1414141413 13 6060 C C 1919191920205050 D D M M 0

6、0 M M5050 需求量需求量 3030 2020 70 70 M（任意大正數(shù)（任意大正數(shù))表示非常高的運價，表示非常高的運價，M不會進入最優(yōu)解不會進入最優(yōu)解1I2I1IV2IV產(chǎn)銷平衡表產(chǎn)銷平衡表運價運價 需求需求 化肥廠化肥廠 I I II II IIIIII IVIV 產(chǎn)產(chǎn) 量量A A 16161313222217175050B B14141313191915156060C C 191920202323- -5050最低需求最低需求303070700 01010110110 t t （210210）最高需求最高需求505070703030不限不限（6060）運價運價 需求需求地地 供應

7、地供應地 IIIIIIIIII 供應供應 量量 A A 161616161313222217171717 5050 B B141414141313191915151515 6060 C C 1919191920202323M MM M 5050 D D M M 0 0 M M0 0 M M 0 0 5050 需求量需求量 3030 2020 7070 3030 1010 5050 M（任意大正數(shù)（任意大正數(shù))表示非常高的運價，表示非常高的運價，M不會進入最優(yōu)解不會進入最優(yōu)解1I2I1IV2IV產(chǎn)銷平衡表產(chǎn)銷平衡表運價運價 需求需求地地 供應地供應地 IIIIIIIIII 供應供應 量量 A A

8、 161616 16 1313222217171717 5050 B B141414 14 1313191915151515 6060 C C 191919 19 20202323M MM M 5050 D D M M 0 0 M M0 0 M M 0 0 5050 需求量需求量 3030 2020 7070 3030 1010 5050 * *解的退化：解的退化：在用最小元素法求解初始基本可行解時，當產(chǎn)銷平衡表上在用最小元素法求解初始基本可行解時，當產(chǎn)銷平衡表上填上一個數(shù)后，單位運價表上要同時劃去一行和一列，則此時會出現(xiàn)退填上一個數(shù)后，單位運價表上要同時劃去一行和一列，則此時會出現(xiàn)退化。退化

9、分為兩種情況?；?。退化分為兩種情況。1I2I1IV2IV20求解步驟：求解步驟：利用最小元素法求解運輸問題的初始利用最小元素法求解運輸問題的初始解解運價運價 需求需求地地 供應地供應地 IIIIIIIIII 供應供應 量量 A A 161616 16 131322 22 17171717 5050 B B141414 14 131319 19 15151515 6060 C C 191919 19 202023 23 M MM M 5050 D D M M 0 0 M M 0 0 M M 0 0 5050 需求量需求量 3030 2020 7070 3030 1010 5050 1I2I1IV

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

11、IIIIIIIIII 供應供應 量量 A A 161616 16 131322 22 17171717 5050 B B141414 14 131319 19 15151515 6060 C C 191919 19 202023 23 M MM M 5050 D D M M 0 0 M M 0 0 M M 0 0 5050 需求量需求量 3030 2020 7070 3030 1010 5050 1I2I1IV2IV2030求解步驟：求解步驟：利用最小元素法求解運輸問題的初始利用最小元素法求解運輸問題的初始解解* *解的退化情況解的退化情況1 1：在確定供需關(guān)系時，若在（在確定供需關(guān)系時，若在

12、（i,j）格內(nèi)填入數(shù)字后出現(xiàn)處）格內(nèi)填入數(shù)字后出現(xiàn)處 的余量等于的余量等于 處的需量，此時在產(chǎn)銷平衡表上填上一個數(shù)后，單位運價表上要處的需量，此時在產(chǎn)銷平衡表上填上一個數(shù)后，單位運價表上要同時劃去一行和一列，并在劃去的行或列的任一空格處填上一個同時劃去一行和一列，并在劃去的行或列的任一空格處填上一個0（始終保持表（始終保持表上有上有m+n-1個數(shù)字格）。個數(shù)字格）。iAjB0運價運價 需求需求地地 供應地供應地 IIIIIIIIII 供應供應 量量 A A 1616 16 16 131322 22 17 17 1717 5050 B B141414 14 131319 19 15151515

13、6060 C C 1919 19 19 20 20 2323M M M M 5050 D D M M 0 0 M M 0 0 M M 0 0 5050 需求量需求量 3030 2020 7070 3030 1010 5050 1I2I1IV2IV2030503020010050求解步驟：求解步驟：利用位勢法求解表中所有非基變量的檢驗數(shù)利用位勢法求解表中所有非基變量的檢驗數(shù))(vucjiijij2262221615141211，MMMMMM2242029243332312422，M2323252404645434135，運價運價 需求需求地地 供應地供應地 IIIIIIIIII 供應供應 量量

14、A A 1616 16 16 131322 22 17 17 1717 5050 B B141414 14 131319 19 15151515 6060 C C 1919 19 19 20 20 2323M M M M 5050 D D M M 0 0 M M 0 0 M M 0 0 5050 需求量需求量 3030 2020 7070 3030 1010 5050 1I2I1IV2IV2030503020010050.求解步驟：求解步驟：利用閉回路法進行第一次方案調(diào)整利用閉回路法進行第一次方案調(diào)整30-20213131為換出變量，調(diào)整量為為換入變量，最小，故選取檢驗數(shù)XXM運價運價 需求需

15、求地地 供應地供應地 IIIIIIIIII 供應供應 量量 A A 1616 16 16 131322 22 17 17 1717 5050 B B1414 14 14 131319 19 15151515 6060 C C 1919 19 19 20 20 2323M M M M 5050 D D M M 0 0 M M 0 0 M M 0 0 5050 需求量需求量 3030 2020 7070 3030 1010 5050 1I2I1IV2IV20305030200103020求解步驟：求解步驟：利用閉回路法進方案調(diào)整得到下表表利用閉回路法進方案調(diào)整得到下表表22217231916151

16、41211，MMMMMMM2342025213332242221，MM242426414645434135，運價運價 需求需求地地 供應地供應地 IIIIIIIIII 供應供應 量量 A A 1616 16 16 131322 22 17 17 1717 5050 B B1414 14 14 131319 19 15151515 6060 C C 1919 19 19 20 20 2323M M M M 5050 D D M M 0 0 M M 0 0 M M 0 0 5050 需求量需求量 3030 2020 7070 3030 1010 5050 1I2I1IV2IV20305030200

17、103020.求解步驟：求解步驟：表表2未得最優(yōu)解，用閉回路法進行第二次調(diào)整未得最優(yōu)解，用閉回路法進行第二次調(diào)整20-23363333為換出變量，調(diào)整量為為換入變量，最小，故選取檢驗數(shù)XXM運價運價 需求需求地地 供應地供應地 IIIIIIIIII 供應供應 量量 A A 1616 16 16 131322 22 17 17 1717 5050 B B1414 14 14 131319 19 15151515 6060 C C 1919 19 19 20 20 2323M M M M 5050 D D M M 0 0 M M 0 0 M M 0 0 5050 需求量需求量 3030 2020

18、7070 3030 1010 5050 1I2I1IV2IV2030503020010500求解步驟：求解步驟：利用閉回路法進方案調(diào)整得到下表表利用閉回路法進方案調(diào)整得到下表表3226041615141211，22-432-23532242221M，1134224645434136，MMMM運價運價 需求需求地地 供應地供應地 IIIIIIIIII 供應供應 量量 A A 1616 16 16 131322 22 17 17 1717 5050 B B1414 14 14 131319 19 15151515 6060 C C 1919 19 19 20 20 2323M M M M 5050

19、 D D M M 0 0 M M 0 0 M M 0 0 5050 需求量需求量 3030 2020 7070 3030 1010 5050 1I2I1IV2IV2030503020010500.求解步驟：求解步驟： 表表3未得最優(yōu)解，用閉回路法進行第三次調(diào)整未得最優(yōu)解，用閉回路法進行第三次調(diào)整04-343232為換出變量，調(diào)整量為為換入變量，最小，故選取檢驗數(shù)XX運價運價 需求需求地地 供應地供應地 IIIIIIIIII 供應供應 量量 A A 1616 16 16 131322 22 17 17 1717 5050 B B1414 14 14 131319 19 15151515 6060

20、 C C 1919 19 19 20 20 2323M M M M 5050 D D M M 0 0 M M 0 0 M M 0 0 5050 需求量需求量 3030 2020 7070 3030 1010 5050 1I2I1IV2IV2030503020010500求解步驟：求解步驟：利用閉回路法進方案調(diào)整得到下表表利用閉回路法進方案調(diào)整得到下表表41210441615141211，22-47223534242221M，4-3-24234645434136，MMMM運價運價 需求需求地地 供應地供應地 IIIIIIIIII 供應供應 量量 A A 1616 16 16 131322 22

21、17 17 1717 5050 B B1414 14 14 131319 19 15151515 6060 C C 1919 19 19 20 20 2323M M M M 5050 D D M M 0 0 M M 0 0 M M 0 0 5050 需求量需求量 3030 2020 7070 3030 1010 5050 1I2I1IV2IV2030503020010500.求解步驟：求解步驟： 表表4未得最優(yōu)解，用閉回路法進行第四次調(diào)整未得最優(yōu)解，用閉回路法進行第四次調(diào)整204-424646為換出變量，調(diào)整量為為換入變量，最小，故選取檢驗數(shù)XX運價運價 需求需求地地 供應地供應地 IIIII

22、IIIII 供應供應 量量 A A 1616 16 16 131322 22 17 17 1717 5050 B B1414 14 14 131319 19 15151515 6060 C C 1919 19 19 20 20 23 23 M M M M 5050 D D M M 0 0 M M 0 0 M M 0 0 5050 需求量需求量 3030 2020 7070 3030 1010 5050 1I2I1IV2IV20305030200103020求解步驟：求解步驟：利用閉回路法進方案調(diào)整得到下表表利用閉回路法進方案調(diào)整得到下表表5227441615141211，22-14223534

23、242221M，MMMM4542413635332222，經(jīng)檢驗，所有非基變量的檢驗數(shù)均為非負，因而表經(jīng)檢驗，所有非基變量的檢驗數(shù)均為非負，因而表5給出的基本可行解，給出的基本可行解，即為問題的最優(yōu)解。即為問題的最優(yōu)解。 運價運價 需求需求 化肥廠化肥廠 I I II II IIIIII IVIV 產(chǎn)產(chǎn) 量量A A 16161313222217175050B B14141313191915156060C C 191920202323- -5050最低需求最低需求303070700 01010110110萬萬 t t （210210）最高需求最高需求505070703030不限不限（6060）運

24、價運價 需求需求地地 供應地供應地 IIIIIIIIII 供應供應 量量 A A 161616161313222217171717 5050 B B141414141313191915151515 6060 C C 1919191920202323M MM M 5050 D D M M 0 0 M M0 0 M M 0 0 5050 需求量需求量 3030 2020 7070 3030 1010 5050 1I2I1IV2IV3002030103020502050204050 最少總運費為：最少總運費為：Z=1950+1350+1320+1540=2460萬元。萬元?？偨Y(jié)總結(jié)產(chǎn)銷不平衡運輸問題的求解方法產(chǎn)銷不平衡運輸問題的求解方法:（1