運(yùn)籌學(xué)運(yùn)輸問題求解方法演示文稿第一頁，共二十頁。運(yùn)籌學(xué)運(yùn)輸問題求解方法第二頁，共二十頁。產(chǎn)銷不平衡運(yùn)輸問題的求解方法例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)撥方案。運(yùn)價(jià)需求化肥廠

I

II

III

IV產(chǎn)量A1613221750B1413191560C192023-50最低需求3070010

最高需求507030不限第三頁，共二十頁。運(yùn)價(jià)需求化肥廠

I

II

III

IV產(chǎn)量A1613221750B1413191560C192023-50最低需求3070010110(萬t)

不限最高需求507030不限160萬t分析：產(chǎn)銷不平衡；根據(jù)現(xiàn)有產(chǎn)量，第IV地區(qū)最多能分配到:160-（30+70+0）=60萬t(總廠量減去前三個(gè)地區(qū)最低需求量之和).210萬t60萬t則最大需求量為：50+70+30+60=210萬t;最大需求210萬t比供應(yīng)160萬t多50萬t,因此需要虛擬一個(gè)供應(yīng)點(diǎn)D，其供應(yīng)量為50萬t，使得供求平衡。第四頁，共二十頁。運(yùn)價(jià)需求化肥廠

I

II

III

IV產(chǎn)量A1613221750B1413191560C192023-50最低需求3070010110

萬t

（210）最高需求507030不限（60）運(yùn)價(jià)

需求地

供應(yīng)地

II

III

供應(yīng)量A1616

50

B1414

60

C191950

D

M

050

需求量

30

20

M（任意大正數(shù))表示非常高的運(yùn)價(jià)，M不會(huì)進(jìn)入最優(yōu)解產(chǎn)銷平衡表第五頁，共二十頁。運(yùn)價(jià)需求化肥廠

I

II

III

IV產(chǎn)量A1613221750B1413191560C192023-50最低需求3070010110

t

（210）最高需求507030不限（60）運(yùn)價(jià)

需求地

供應(yīng)地

II

III

供應(yīng)量A16161350

B14141360

C19192050

D

M

0M50

需求量

30

20

70M（任意大正數(shù))表示非常高的運(yùn)價(jià)，M不會(huì)進(jìn)入最優(yōu)解產(chǎn)銷平衡表第六頁，共二十頁。運(yùn)價(jià)需求化肥廠

I

II

III

IV產(chǎn)量A1613221750B1413191560C192023-50最低需求3070010110

t

（210）最高需求507030不限（60）運(yùn)價(jià)

需求地

供應(yīng)地

II

III

供應(yīng)量A161613221717

50

B141413191515

60

C19192023MM

50

D

M

0

M0

M

0

50

需求量

30

20

70

30

10

50

M（任意大正數(shù))表示非常高的運(yùn)價(jià)，M不會(huì)進(jìn)入最優(yōu)解產(chǎn)銷平衡表第七頁，共二十頁。運(yùn)價(jià)

需求地

供應(yīng)地

II

III

供應(yīng)量A1616×13221717

50

B1414×13191515

60

C1919×2023MM

50

D

M

0

M0

M

0

50

需求量

30

20

70

30

10

50

*解的退化：在用最小元素法求解初始基本可行解時(shí)，當(dāng)產(chǎn)銷平衡表上填上一個(gè)數(shù)后，單位運(yùn)價(jià)表上要同時(shí)劃去一行和一列，則此時(shí)會(huì)出現(xiàn)退化。退化分為兩種情況。20求解步驟：利用最小元素法求解運(yùn)輸問題的初始解第八頁，共二十頁。運(yùn)價(jià)

需求地

供應(yīng)地

II

III

供應(yīng)量A1616×1322×1717

50

B1414×1319×1515

60

C1919×2023×MM

50

D

M

×0

M×0

M

×0

×50

需求量

30

20

70

30

10

50

2030求解步驟：利用最小元素法求解運(yùn)輸問題的初始解*解的退化情況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ù)字格）。第九頁，共二十頁。運(yùn)價(jià)

需求地

供應(yīng)地

II

III

供應(yīng)量A1616×1322×1717

50

B1414×1319×1515

60

C1919×2023

MM

50

D

M

×0

M×0

M

×0

×50

需求量

30

20

70

30

10

50

2030求解步驟：利用最小元素法求解運(yùn)輸問題的初始解*解的退化情況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ù)字格）。0第十頁，共二十頁。運(yùn)價(jià)

需求地

供應(yīng)地

II

III

供應(yīng)量A16

×16×1322×17×17

×50

B1414×1319×1515

60

C19

×19×20×23M×M

50

D

M

×0

M×0

M

×0

×50

需求量

30

20

70

30

10

50

2030503020010050求解步驟：利用位勢法求解表中所有非基變量的檢驗(yàn)數(shù)第十一頁，共二十頁。運(yùn)價(jià)

需求地

供應(yīng)地

II

III

供應(yīng)量A16

×16×1322×17×17

×50

B1414×1319×1515

60

C19

×19×20×23M×M

50

D

M

×0

M×0

M

×0

×50

需求量

30

20

70

30

10

50

2030503020010050....................................................................................................................................................................求解步驟：利用閉回路法進(jìn)行第一次方案調(diào)整第十二頁，共二十頁。運(yùn)價(jià)

需求地

供應(yīng)地

II

III

供應(yīng)量A16

×16×1322×17×17

×50

B14

×14×1319×1515

60

C19

19×20×23M×M

50

D

M

×0

M×0

M

×0

×50

需求量

30

20

70

30

10

50

20305030200103020求解步驟：利用閉回路法進(jìn)方案調(diào)整得到下表表2第十三頁，共二十頁。運(yùn)價(jià)

需求地

供應(yīng)地

II

III

供應(yīng)量A16

16

13221717

50

B14

14

13191515

60

C19

19

20

23MM

50

D

M

0

M

0

M

0

50

需求量

30

20

70

30

10

50

20305030200103020..................................................................................求解步驟：表2未得最優(yōu)解，用閉回路法進(jìn)行第二次調(diào)整第十四頁，共二十頁。運(yùn)價(jià)

需求地

供應(yīng)地

II

III

供應(yīng)量A16

16

13221717

50

B14

14

13191515

60

C19

19

20

23MM

50

D

M

0

M

0

M

0

50

需求量

30

20

70

30

10

50

2030503020010500求解步驟：利用閉回路法進(jìn)方案調(diào)整得到下表表3第十五頁，共二十頁。運(yùn)價(jià)

需求地

供應(yīng)地

II

III

供應(yīng)量A16

16

13221717

50

B14

14

13191515

60

C19

19

20

23MM

50

D

M

0

M

0

M

0

50

需求量

30

20

70

30

10

50

2030503020010500........................................................................求解步驟：表3未得最優(yōu)解，用閉回路法進(jìn)行第三次調(diào)整第十六頁，共二十頁。運(yùn)價(jià)

需求地

供應(yīng)地

II

III

供應(yīng)量A16

16

13221717

50

B14

14

13191515

60

C19

19

20

23MM

50

D

M

0

M

0

M

0

50

需求量

30

20

70

30

10

50

2030503020010500求解步驟：利用閉回路法進(jìn)方案調(diào)整得到下表表4第十七頁，共二十頁。運(yùn)價(jià)

需求地

供應(yīng)地

II

III

供應(yīng)量A16

16

13221717

50

B14

14

13191515

60

C19

19

20

23MM

50

D

M

0

M

0

M

0

50

需求量

30

20

70

30

10

50

2030503020010500...................................................................................................................................求解步驟：表4未得最優(yōu)解，用閉回路法進(jìn)行第四次調(diào)整第十八頁，共二十頁。運(yùn)價(jià)

需求地

供應(yīng)地

II

III

供應(yīng)量A16

16

1322

17

17

50

B14

14

1319

1515

60

C19

19

20

23