运筹学运输问题求解方法

运筹学运输问题求解方法第一页，共20页。运筹学运输问题求解方法第二页，共20页。产销不平衡运输问题的求解方法例5.5

设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同，各化肥厂年产量、各地区年需量及从各化肥厂到各地区运送化肥的单位运价(万元/万t）如5-25所示。试求出总运费最少的化肥调拨方案。运价需求化肥厂

I

II

III

IV产量A1613221750B1413191560C192023-50最低需求3070010

最高需求507030不限第三页，共20页。运价需求化肥厂

I

II

III

IV产量A1613221750B1413191560C192023-50最低需求3070010110(万t)

不限最高需求507030不限160万t分析：产销不平衡；根据现有产量，第IV地区最多能分配到:160-（30+70+0）=60万t(总厂量减去前三个地区最低需求量之和).210万t60万t则最大需求量为：50+70+30+60=210万t;最大需求210万t比供应160万t多50万t,因此需要虚拟一个供应点D，其供应量为50万t，使得供求平衡。第四页，共20页。运价需求化肥厂

I

II

III

IV产量A1613221750B1413191560C192023-50最低需求3070010110

万t

（210）最高需求507030不限（60）运价

需求地

供应地

II

III

供应量A1616

50

B1414

60

C191950

D

M

050

需求量

30

20

M（任意大正数)表示非常高的运价，M不会进入最优解产销平衡表第五页，共20页。运价需求化肥厂

I

II

III

IV产量A1613221750B1413191560C192023-50最低需求3070010110

t

（210）最高需求507030不限（60）运价

需求地

供应地

II

III

供应量A16161350

B14141360

C19192050

D

M

0M50

需求量

30

20

70M（任意大正数)表示非常高的运价，M不会进入最优解产销平衡表第六页，共20页。运价需求化肥厂

I

II

III

IV产量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（任意大正数)表示非常高的运价，M不会进入最优解产销平衡表第七页，共20页。运价

需求地

供应地

II

III

供应量A1616×13221717

50

B1414×13191515

60

C1919×2023MM

50

D

M

0

M0

M

0

50

需求量

30

20

70

30

10

50

*解的退化：在用最小元素法求解初始基本可行解时，当产销平衡表上填上一个数后，单位运价表上要同时划去一行和一列，则此时会出现退化。退化分为两种情况。20求解步骤：利用最小元素法求解运输问题的初始解第八页，共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）格内填入数字后出现处的余量等于处的需量，此时在产销平衡表上填上一个数后，单位运价表上要同时划去一行和一列，并在划去的行或列的任一空格处填上一个0（始终保持表上有m+n-1个数字格）。第九页，共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）格内填入数字后出现处的余量等于处的需量，此时在产销平衡表上填上一个数后，单位运价表上要同时划去一行和一列，并在划去的行或列的任一空格处填上一个0（始终保持表上有m+n-1个数字格）。0第十页，共20页。运价

需求地

供应地

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求解步骤：

利用位势法求解表中所有非基变量的检验数第十一页，共20页。运价

需求地

供应地

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................求解步骤：

利用闭回路法进行第一次方案调整第十二页，共20页。运价

需求地

供应地

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第十三页，共20页。运价

需求地

供应地

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未得最优解，用闭回路法进行第二次调整第十四页，共20页。运价

需求地

供应地

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第十五页，共20页。运价

需求地

供应地

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未得最优解，用闭回路法进行第三次调整第十六页，共20页。运价

需求地

供应地

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第十七页，共20页。运价

需求地

供应地

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未得最优解，用闭回路法进行第四次调整第十八页，共20页。运价

需求地

供应地

II

III

供应量A16

16

1322

17

17

50

B14