運籌學運輸問題求解方法演示文稿

運籌學運輸問題求解方法演示文稿第一頁，共二十頁。運籌學運輸問題求解方法第二頁，共二十頁。產(chǎn)銷不平衡運輸問題的求解方法例5.5

設有三個化肥廠供應四個地區(qū)的農用化肥。假定等量的化肥在這些地區(qū)使用效果相同，各化肥廠年產(chǎn)量、各地區(qū)年需量及從各化肥廠到各地區(qū)運送化肥的單位運價(萬元/萬t）如5-25所示。試求出總運費最少的化肥調撥方案。運價需求化肥廠

I

II

III

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

最高需求507030不限第三頁，共二十頁。運價需求化肥廠

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(總廠量減去前三個地區(qū)最低需求量之和).210萬t60萬t則最大需求量為：50+70+30+60=210萬t;最大需求210萬t比供應160萬t多50萬t,因此需要虛擬一個供應點D，其供應量為50萬t，使得供求平衡。第四頁，共二十頁。運價需求化肥廠

I

II

III

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

萬t

（210）最高需求507030不限（60）運價

需求地

供應地

II

III

供應量A1616

50

B1414

60

C191950

D

M

050

需求量

30

20

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

I

II

III

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

t

（210）最高需求507030不限（60）運價

需求地

供應地

II

III

供應量A16161350

B14141360

C19192050

D

M

0M50

需求量

30

20

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

I

II

III

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

t

（210）最高需求507030不限（60）運價

需求地

供應地

II

III

供應量A161613221717

50

B141413191515

60

C19192023MM

50

D

M

0

M0

M

0

50

需求量

30

20

70

30

10

50

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

需求地

供應地

II

III

供應量A1616×13221717

50

B1414×13191515

60

C1919×2023MM

50

D

M

0

M0

M

0

50

需求量

30

20

70

30

10

50

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

需求地

供應地

II

III

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

需求地

供應地

II

III

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

需求地

供應地

II

III

供應量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求解步驟：利用位勢法求解表中所有非基變量的檢驗數(shù)第十一頁，共二十頁。運價

需求地

供應地

II

III

供應量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....................................................................................................................................................................求解步驟：利用閉回路法進行第一次方案調整第十二頁，共二十頁。運價

需求地

供應地

II

III

供應量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求解步驟：利用閉回路法進方案調整得到下表表2第十三頁，共二十頁。運價

需求地

供應地

II

III

供應量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)解，用閉回路法進行第二次調整第十四頁，共二十頁。運價

需求地

供應地

II

III

供應量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第十五頁，共二十頁。運價

需求地

供應地

II

III

供應量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)解，用閉回路法進行第三次調整第十六頁，共二十頁。運價

需求地

供應地

II

III

供應量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第十七頁，共二十頁。運價

需求地

供應地

II

III

供應量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)解，用閉回路法進行第四次調整第十八頁，共二十頁。運價

需求地

供應地

II

III

供應量A16

16

1322

17

17

50

B14

14

1319

1515

60

C19

19

20

23