3运输问题Word

　　3 运输问题3.1 运输问题及其数学模型 3.2 表上作业法 3.2.1 初始方案的给定 ①最小元素法② Vogel法 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吨。各厂到 各销售部的单位产品的运价如下表。问该公司应 如何调运产品，才能完成运输任务而使运费最省。销地 产地

　　B1 3 1 7

　　B2 11 9 4

　　B3 3 3 10

　　B4 10 8 5

　　A1 A2 A3

　　解：设由产地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)

　　运输问题的典型数学形式：

　　min z cij xiji 1 j 1

　　m

　　n

　　xj 1 m

　　n

　　ij

　　a i , (i 1, 2, , m) b j , ( j 1, 2, , n)

　　xi 1

　　ij

　　xij 0, (i 1, 2, , m;j 1, 2, , n)

　　运输问题一般用表上作业法求解，需建立表格模 型： 销地B1 产地 B2 B3 B4 产量 7 4 9 3 6 5 6 A1 A2 A3 销量

　　产销平衡表

　　销地 产地

　　B1 3 1 7

　　B2 11 9 4

　　B3 3 3 10

　　B4 10 8 5

　　单位运价表

　　A1 A2 A3

　　3.2 表上作业法表上作业法的步骤类似于单纯形法: (1)给出初始调运方案。 (2)检验方案是否最优,若是最优解, 则停止计算;否则转下一步。

　　(3)调整调运方案，得新的方案。(4)重复(2),(3)直到求出最优方案。

　　3.2.1 初始方案的给定 ①最小元素法产销平衡表及初始调运方案销地 B1 产地 A1 A2 A3 销量 B2 B3 B4 产量 7 4 9销地 产地

　　单位运价表B1 3 1 7 B2 11 9 4 B3 3 2 10 B4 10 8 5

　　3 63 6

　　4 15

　　336

　　A1 A2 A3

　　此时，z=86元。

　　表上作业法要求，调运方案的有数字格必须 为m+n-1个，且有数字格不构成闭回路。一般， 用最小元素法给出的方案符合这一要求。

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

　　销地

　　B1 3 3 1

　　B2 11 9 2

　　B3 3 4 10

　　B4 10 8 5

　　5 33

　　66 5

　　2 4 06

　　7 4 9

　　A1 A2 A3

　　出现退化时，要在同时被划去的行或列中任 选一个空格填0,此格作为有数字格。

　　3.2.1 初始方案的给定② Vogel法销地 产地

　　B1 B2 3 1 7 11 9 4

　　B3 3 2 10

　　B4 10 8 5

　　行两最小 元素之差

　　A1 A2 A3列两最 小元素 之差

　　2 5 2 2

　　1 1 1 1

　　3 3 2 2

　　0007 1116 12销地 B1 产地 A1 A2 A3 销量 B2 B3 B4 产量 7 4 9

　　此时，z=85元。

　　33

　　5 66 5

　　2 1 36

　　两种方法确定的初始调运方案对比 最小元素法确定 的初始调运方案销地 B1 产地 A1 A2 A3 销量 B2 B3 B4 产量

　　Vogel法确定的

　　初始调运方案销地 B1 产地

　　A1 A2 A3 销量 B2 B3 B4 产量 7 4 9

　　3

　　63 6

　　4 15

　　3 7 36 4 9

　　33

　　5 66 5

　　2 1 36

　　3.2.2 最优性检验的方法——闭回路法根据基的定义，非基变量可以由基变量唯一地线性 表示。在表上作业法中，这种线性表示关系可以由 闭回路的形式来体现。 任一空格与有限个有效的有数字格有且只有唯一的闭回路销地 产地 A1 A2 A3

　　检验数 表 B1 B2

　　销地

　　B3

　　B4

　　产地

　　B1 3 1 7

　　B2 11 9 4

　　B3 3 2 10

　　B4 10 8 5

　　A1 (1) (2) 3 10 A2 1 (1) 2 (-1) A3 (12) 5 (10) 4

　　若所有检验数非负则是最优 解

　　3.2.2 最优性检验的方法——位势法x11 1 1 x12 1 x1n x21 1 1 1 1 0 1 p ij 1 0

　　x22 1

　　x2 n 1

　　xm1

　　xm 2

　　xmn 1 1

　　1 1 1 1 1 1 1

　　0 1 ij cij Y * P ij cij (u1 , u 2 , , u m , v1 , v2 , vn ) 1 0 cij (ui v j )

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

　　销地 产地

　　B1 3 1 7

　　B2 11 9 4

　　B3 3 2 10

　　B4 10 8 5

　　3

　　7 4 9

　　A1 A2 A3

　　位势表销地 B1 产地 A1 A2 A3 vj B2 B3 B4 ui

　　检验数表销地 产地

　　B1 1 10

　　B2 2 1

　　B3

　　B4 -1

　　10 1 (2) (9) 3 1 (8) 2 (9) 0 (-3) 4 (-2) 5 -4

　　A1 A2 A3

　　12

　　1

　　8

　　2

　　9

　　3.2.3 方案调整的方法——闭回路法销地 B1 产地 A1 A2 A3 销量 B2 B3 4 1 6 3 6 5 B4 3 3 6 产量 7 4 9产地 A1 A2 A3 销量 销地 B1 B2 B3 5 0 6 3 6 5 B4 2 1 3 6 产量 7 4 9

　　3

　　3

　　(1)从一个检验数为负数且最小的空格出发，和其它 数字格构成闭回路。 (2)在闭回路上进行运量调整，使选定空格处的运量 尽可能地增加。 (3)运量调整后，必然使某个数字格变成零。把一个 变成零的数字格抹去，得新的调运方案。

　　3.2.4 表上作业法举例销地 B1 产地 A1 A2 A3 销量 B2 B3 4 1 6 3 6 5 B4 3 3 6 产量

　　销地 产地3 7 4 9

　　B1 3 1 7

　　B2 11 9 4

　　B3 3 2 10

　　B4 10 8 5

　　A1 A2 A3

　　位势表销地 B1 产地 A1 A2 A3 vj B2 B3 B4 ui

　　检验数表销地 产地

　　B1 1 10

　　B2 2 1

　　B3

　　B4 -1

　　10 1 (2) (9) 3 1 (8) 2 (9) 0 (-3) 4 (-2) 5 -4

　　A1 A2 A3

　　12

　　1

　　8

　　2

　　9

　　有检验数为负,不是最优解。

　　表上作业法举例(续)销地 B1 产地 A1 A2 A3 销量 B2 B3 5 3 6 3 6 5 B4 2 1 3 6 产量

　　销地 产地7 4 9

　　B1 3 1 7

　　B2 11 9 4

　　B3 3 2 10

　　B4 10 8 5

　　A1 A2 A3

　　位势表销地 B1 产地 A1 A2 A3 vj B2 B3 B4 10 8 5 ui

　　检验数表销地 产地

　　B1 0 9

　　B2 2 2

　　B3 1 12

　　B4

　　(3) (9) 3 1 (7) (1) (-2) 4 (-2)

　　20

　　-3

　　A1 A2 A3

　　1

　　7

　　1

　　8

　　检验数都非负，得最优解。

　　3.3 产销不平衡的运输问题表上作业法是以产销平衡为

　　前提的，即当实际 问题产销不平衡时，需要转化为产销平衡的运 输问题，具体来说有两种情况： (1)产大于销，即 a b 此时增加一个假想的销地n+1,该销地的销 a b ,而各产地到假想销地的单位运价 量为 一般定为0,就转化成产销平衡的运输问题。 (2)销大于产，即 a b 此时增加一个假想的产地m+1,该产地的产 量为 b a ,而假想产地到各销地的单位运价 一般定为0,就转化成产销平衡的运输问题。m n i 1 i j 1 jm n i 1 i j 1 j

　　m

　　n

　　i 1

　　i

　　j 1

　　j

　　n

　　m

　　j 1

　　j

　　i 1

　　i

　　产销不平衡的运输问题举例设有三个化肥厂供应四个地区的农用化肥。 各化肥厂年产量，各地区年需要量及从各化肥 厂到各地区运送化肥的单位运价如又表：地区 化费厂

　　Ⅰ 16 14 19 30 50

　　Ⅱ 13 13 20 70 70

　　Ⅲ 22 19 23 0 30

　　Ⅳ 17 15 10 不限

　　产量

　　A B C 最低需求 最高需求

　　50 60 50

　　试求出总运费最省的化肥调运方案。

　　解：三个厂的总产量为160万吨，四个地区的 最低需求为110万吨，最高需求为无限。地区Ⅳ 每年最多能分配到60万吨，这样四个地区最高 需求为210万吨，销大于产。于是，增加虚产地 D,产量为50万吨。还要把地区Ⅰ和Ⅳ的产量 分为两部分。建立如下表格模型：产地 Ⅰ′ Ⅰ″ Ⅱ Ⅲ Ⅳ′ 销地 50 A 20 10 B C 30 20 0 30 D 销量 30 20 70 30 10Ⅳ″ 产量

　　销地

　　50 产地 30 60 A 50 B 20 50 C 50 D

　　Ⅰ′ Ⅰ″ Ⅱ Ⅲ Ⅳ′ Ⅳ″ 16 16 13 22 17 14 14 13 19 15 19 19 20 23 M M 0 M 0 M 17 15 M 0

　　3.4 应用举例例 某厂按合同规定须于当年每个季度末分 别提供10、15、25、20台同一规格的柴油机。 已知该厂各季度的生产能力及生产每台柴油机 的成本如右表。又知如果生产出来的柴油机当 季度不交货，每台每季度的存储维护费为0.15万 元。试安排全年生产计划，使总费用最低。 季度 生产能力 单位成本 Ⅰ 25 台 10.8 万元 Ⅱ 35 台 11.1 万元 Ⅲ 30 台 11.0 万元 Ⅳ 10 台 11.3 万元

　　解：各季 度都产出产品， 都可看作产地； 各季度都有定 货，都可看作 销地。这是一个产 大于销的运输 问题，需增加 虚销地D。表 格模型如下：

　　产销平衡表销地 产地 Ⅰ Ⅱ Ⅲ Ⅳ 销量 Ⅰ Ⅱ Ⅲ Ⅳ D

　　10 15 0 5 2010 15 25

　　产量 25 30 35 30 10 10 10 20 30

　　单位运价表销地 Ⅰ 产地 Ⅰ Ⅱ Ⅲ Ⅳ Ⅱ Ⅲ Ⅳ D

　　10.8 10.95 11.10 11.25 0 M 11.10 11.25 11.40 0 M M 11.00 11.15 0 M M M 11.30 0

　　例 某航运公司承担六 个港口城市A,B,C,D, E,F间四条航线的货物 运输任务。各航线的 起点、终点、日航班 数如下：航线 起点 终点 日航班数 1 E D 3 2 B C 2 3 A F 1 4 D B 1

　　假定各航线使用的船只 相同，各城市间的航程 天数如下：到 A 从 A B C D E F 0 1 2 14 7 7 B 1 0 3

　　13 8 8 C 2 3 0 15 5 5 D 14 13 15 0 17 20 E 7 8 5 17 0 3 F 7 8 5 20 3 0

　　又知每条船每次装卸货时间各需1天，问该公 司至少应配备多少条船？

　　解 所需船只分成两部分： 为使配备船只数尽 (1)载货航行需要的船只数. 可能少，建立如下运 输模型: 3*19+2*5+9+15=91条. A B E 产量 (2)各港口间调度需要的船 1 1 C 2 只数. 1 1 D 2 各港口每天船只的余 1 F 1 缺数为: 销量 1 1 3城市 到达 A 0 B 1 C 2 D 3 E 0 F 1 发出 1 2 0 1 3 0 余缺数 -1 -1 2 2 -3 1

　　A C D F 2 15 7

　　B 3 13 8

　　E 5 17 3

　　调度需要的船只数为 2+5+13+17+3=40条