PDF《3. 运输问题》

3.

运输问题 3.1 运输问题及其数学模型 3.2 表上作业法 3.2.1 最小元素法 3.2.2 位势法 3.2.3 闭回路法 3.3 产销不平衡的运输问题 3.4 应用举例 3.1 运输问题及其模型 例 某公司经销一种产品,它下设三个工厂、四个 销售部.三个工厂的日产量分别为:A1―7吨, A2―4吨,A3―9吨;

各销售部的日销量分别为: B1―3吨,B2―6吨,B3―5吨,B4―6吨.各厂到 各销售部的单位产品的运价如右表.问该公司应 如何调运产品,才能完成运输任务而使运费最 省. 销地产地B1B2B3B4A1A2A3317119433101085用线性规划法处理此问 题.设由产地i到销地j的运量 为xij,模型为: min z= 3x11+11x12+3x13+10x14 +x21 +9x22 +2x23 +8x24 +7x31 +4x32+10x33+5x34 x11+x12+x13+x14=7 x21+x22+x23+x24=4 x31+x32+x33+x34=9 x11+x21+x31=3 x12+x22+x32=6 x13+x23+x33=5 x14+x24+x34=6 xij≥0 (i=1,2,3;

j=1,2,3,4) 运输问题一般用表上作业 法求解,需建立表格模型: 单位运价表 销地 产地 B1 B2 B3 B4 产量 A1 A2 A3

7 4

9 销量

3 6

5 6 产销平衡表 销地产地B1 B2 B3 B4 A1 A2 A3

3 1

7 11

9 4

3 3

10 10

8 5 3.1 运输问题及其模型

(二) ? ? ? ? ? ? ? ? ? ? ? ≥ = = = = = ∑ ∑ ∑ ∑ = = = =

0 , ,

1 , ,

1 min

1 1

1 1 ij m i j ij n j i ij m i n j ij ij x n j b x m i a x x c z L L 有m个生产地点生产或供应某种物资,有n个 销售地点销售地点销售或需求该种物资,若i 个产地生产产量为ai,第j个销地销售量为bj, 并且有Σai=Σbj,而第i个产地到第j个销地单 位运价为cij,使总运费达到最小的运输问题的 数学模型为: 3.2 表上作业法 表上作业法的步骤类似于单纯形法: (1)给出初始调运方案. (2)检验方案是否最优,若是最优解, 则停止计算;

否则转下一步. (3)调整调运方案,得新的方案. (4)重复(2),(3)直到求出最优方案. 3.2.1 给出初始调运方案最常用的方法 ――最小元素法 表上作业法要求,数字格必须为m+n-1 个,且有数字格不构成闭回路. 销地产地B1 B2 B3 B4 产量 A1 A2 A3

7 4

9 销量3656销地 产地 B1 B2 B3 B4 A1 A2 A3

3 1

7 11

9 4

3 2

10 10

8 5

3 1

4 6

3 3 最小元素法中的退化情况 销地 产地 B1 B2 B3 B4 产量 A1 A2 A3

7 4

9 销量

3 6

5 6 销地 产地 B1 B2 B3 B4 A1 A2 A3

3 3

1 11

9 2

3 4

10 10

8 5

3 6

0 5

4 2 出现退化时,要在同时被划去的行列中 任选一个空格填0,此格作为有数字格. 3.2.1 给出初始调运方案的另一种方法 ――vogel法4(1)从单位运价表中的每行每列中分别找出两个最小元素之差,所有差值 中最大的一个所在的行或列中最小的元素所在位置即为进行调动的位置

4 (2)在产销平衡表上对应的调运位置尽最大可能调运

4 (3)在单位运价表中划掉己满足的行或列的运价

4 (4)重复上述步骤,直至所有的运价都被直线覆盖掉,即得到一初始方案

6 5

6 3

9 3

6 4

1 3

7 2

5 3

2 1

4 3

2 1 销量 产量 Α Α Α Β Β Β Β

2 2

2 3

1 1

1 1

5 2

2 2

2 1

5 10

4 3

6 1

1 1

8 2

9 1

7 0

0 0

10 3

11 3

3 2

1 4

3 2

1 两个最小元素之差 两个最小元素之差 Α Α Α Β Β Β Β 销地 产地 B1 B2 B3 B4 ui A1 A2 A3

1 4

3 2

10 5 vj 位势表

1 0

2 1

9 -4

8 (2) (9) (8) (9) (-3) (-2) 销地产地 B1 B2 B3 B4 A1 A2 A3

3 1

7 11

9 4

3 2

10 10

8 5 检验数表 若所有检验数非负则是最优解 3.2.2 最优性检验的方法――位势法 销地 产地 B1 B2 B3 B4 产量 A1 A2 A3

3 6

4 1

3 3

7 4

9 销量

3 6

5 6 销地 产地 B1 B2 B3 B4 A1 A2 A3

1 10

2 1

12 -1 (1)从一个检验数为负数且最小的空格出发,和其它 数字格构成闭回路.可证,此闭回路存在且唯一. (2)在闭回路上进行运量调整,使选定空格处的运量 尽可能地增加. 销地 产地 B1 B2 B3 B4 产量 A1 A2 A3

3 6

4 1

3 3

7 4

9 销量

3 6

5 6 销地 产地 B1 B2 B3 B4 产量 A1 A2 A3

3 6

5 0

2 1

3 7

4 9 销量

3 6

5 6 (3)运量调整后,必然使某个数字格变成零.把一个 变成零的数字格抹去,得新的调运方案. 3.2.3 方案调整的方法闭回路法 销地 产地 B1 B2 B3 B4 产量 A1 A2 A3

1 4

3 2

10 5 销量 位势表

1 0

2 1

9 -4

8 (2) (9) (8) (9) (-3) (-2) 销地 产地 B1 B2 B3 B4 A1 A2 A3

3 1

7 11

9 4

3 2

10 10

8 5 检验数表 销地 产地 B1 B2 B3 B4 产量 A1 A2 A3

3 6

4 1

3 3

7 4

9 销量

3 6

5 6 销地产地 B1 B2 B3 B4 A1 A2 A3

1 10

2 1

12 -1 有检验数为负,不是最优解. 3.2.4 表上作业法举例 销地 产地 B1 B2 B3 B4 产量 A1 A2 A3

1 4

3 10

8 5 销量 位势表

1 0

1 2

8 -3

7 (3) (9) (7) (1) (-2) (-2) 销地 产地 B1 B2 B3 B4 A1 A2 A3

3 1

7 11

9 4

3 2

10 10

8 5 检验数表 销地 产地 B1 B2 B3 B4 产量 A1 A2 A3

3 6

5 2

1 3

7 4

9 销量

3 6

5 6 销地 产地 B1 B2 B3 B4 A1 A2 A3

0 9

2 2

1 12 表上作业法举例(续) 检验数都非负,得最优解. 表上作业法是以产销平衡为前提的,即当实际 问题产销不平衡时,需要转化为产销平衡的运 输问题,具体来说有两种情况: (1)产大于销,即∑∑==>

njjmiiba11此时增加一个假想的销地n+1,该销地的销量 为 ,而各产地到假想销地的单位运价定 为0,就转化成产销平衡的运输问题. ∑ ∑ = = ? n j j m i i b a

1 1 (2)销大于产,即∑∑==........