运筹学运输问题

运筹学运输问题

第3章 运输问题课时： 学时 讲授6学时 演示实验1学时 学时(讲授 学时,演示实验 学时) 课时：7学时 讲授 学时 演示实验 学时

3.1 典例和数学模型 3.2 表上作业法简介 3.3 产销不平衡运输问题及应用 3.4 应用举例 部分习题解答

ExcelORM1.0下载地址 下载地址: 下载地址 /guanwenzhong

运筹学运输问题

3.1 运输问题典例及数学模型引例( 引例(P111)产销平衡表 产 A1 A2 A3 销 B1 B2 B3 B4x11 x12 x13 x14

min z = 4 x11 + 12 x12 + 4 x13 + 11x14 +产量

2 x21 + 10 x22 + 3x23 + 9 x24 + 8 x31 + 5 x32 + 11x33 + 6 x34

16 x21 x22 x23 x24 10 x31 x32 x33 x34 22 48 销量 8 14 12 14 48 单位运价表B1 A1 A2 A3 4 2 8 B2 B3 B4 12 10 5 4 3 11 11 9 6

设：

xij——从产地 运往销地 的运量 从产地Ai运往销地 从产地 运往销地Bj的运量

x11 + x12 + x13 + x14 = 16 x21 + x22 + x23 + x24 = 10 产量约束 x31 + x32 + x33 + x34 = 22 x11 + x21 + x31 = 8 x12 + x22 + x32 = 14 销量约束 s.t. x13 + x23 + x33 = 12 x14 + x24 + x34 = 14 x ≥ 0, (i = 1, 2,3; j = 1, 2,3, 4) ij

运筹学运输问题

一般情况： 一般情况： 单位运价表(cij) 单位运价表 B1 c11 c21 … cm1 B2 c12 c22 … cm2 … … … … … Bn c1n c2n … cmn

A1 A2 … Am

min z = ∑∑ cij xiji =1 j =1

m

n

产销平衡表B1 A1 A2 … Am x11 X21 … xm1 B2 x12 X22 … xm2 … … … … … Bn x1n X2n … xmn

产量 a1 a2 … am

n ∑ xij = ai i = 1, 2,..., m j =1 m s.t. ∑ xij = b j j = 1, 2,..., n i =1 xij ≥ 0 i = 1, 2,..., m; j = 1, 2,..., n

销量

b1

b2

…

bn

运筹学运输问题

3.2 表上作业法简介表上作业法是一种简便而有效的方法,实质是单纯形法 表上作业法是一种简便而有效的方法 实质是单纯形法. 实质是单纯形法 步骤: 步骤1° ° 给出初始解

2° °

求检验数， 求检验数， 是否最优解？ 是否最优解？ 否

是

找到了最优解

3° °

找出新的解

运筹学运输问题

3.2.1 给出初始解给出初始解有西北角法、 给出初始解有西北角法、最小 元素法和Vogel法,我们只介绍 元素法和 法 我们只介绍 最小元素法. 最小元素法 步骤: 步骤 (1)从单位运价表中 找出最小 从单位运价表中 元素,确定供销关系 确定供销关系; 元素 确定供销关系 (2)根据可供量与需求量两者 根据可供量与需求量两者 的较小值,在产销平衡表对应 的较小值 在产销平衡表对应 格中填上该数字. 格中填上该数字 (3)如需求已满足 则从单位运 如需求已满足,则从单位运 如需求已满足 价表中划去相应的列数字,如 价表中划去相应的列数字 如 可供量已用完,则从单位运价 可供量已用完 则从单位运价 表中划去相应行数字.重复 表中划去相应行数字 重复 (1)~(2)直到单位运价表中数字 直到单位运价表中数字 全部被划去为止.(若有产销相 全部被划去为止 若有产销相 同时划去一行一列,并

在任 同,同时划去一行一列 并在任 同时划去一行一列 一运价处填0). 一运价处填 结果:有数字格 有数字格=产 销 结果 有数字格 产+销-1 最小元素法初始方案

B1 A1 A2 8 A3 销量 8 8 4 2

B2 12

B3 4 10 10 2 5 11 12 10 3

B4

产量 11 16

6

6 9 10

14 14

2 6 22 8 8 14 6

运筹学运输问题

3.2.2 解的检验与调整解的最优性检验——位势法 位势法: 解的最优性检验 位势法 (1)把产销平衡表中初始方案中有数 把产销平衡表中初始方案中有数 字格对应的运价写到检验数表中; 字格对应的运价写到检验数表中 (2)对运输表上的每一行 列)赋予一个 对运输表上的每一行(列 赋予一个 对运输表上的每一行 数值u 称为位势.各格子的位 数值 i(vj),称为位势 各格子的位 称为位势 势等于行位势与列位势之和. 势等于行位势与列位势之和 (3)求出检验数 求出检验数: 求出检验数 σij=cij-(ui+vj) 当所有σ 即为即优.当 当所有 ij≥0,即为即优 当σij<0时,由 即为即优 时由 闭回路法修改方案. 闭回路法修改方案 闭回路法: 闭回路法 (1)找到最小的负检验数 其对应的变 找到最小的负检验数,其对应的变 找到最小的负检验数 量为入基变量. 量为入基变量 (2)从入基变量对应的格子出发 遇到 从入基变量对应的格子出发,遇到 从入基变量对应的格子出发 有数字的格子可以转90° 有数字的格子可以转 °(也可 不转) 直到回到出发点 直到回到出发点,形成闭回 不转),直到回到出发点 形成闭回 路. (3)根据供应量与需求量总量不变的 根据供应量与需求量总量不变的 原则,调整供需关系 调整供需关系. 原则 调整供需关系 A1 A2 A3

单位运价表 B1 4 2 8 B1 A1 A2 A3 8 14 B2 12 10 5 B2 B3 4 3 11 B3 10 12 2 B4 11 9 6 B4 6 4 2 8

第1次调整 次调整 初始方案

位势法检验数计算表 B1 A1 A2 A3 vj [1] [0] 2 [10] [9] 3 4 B2 [2] [1] [2] B3 4 [1] 3 [12] 4 4 B4 11 [-1] 9 ui 0 -2 -1 -5

5 6 11 10 10 11 至此,检验数全部大于 检验数全部大于0,第 次调整后的方案为最优方案 作业P130.1) 次调整后的方案为最优方案.(作业 至此 检验数全部大于 第1次调整后的方案为最优方案 作业

运筹学运输问题

演示实验: 演示实验 Excel求解 求解 winQSB求解 求解销地 产地 A1 A2 A3 销量 B1 4 2 8 8 B2 12 10 5 14 B3 4 3 11 12 B4 11 9 6 14 产量 16 10 22

运筹学运输问题

3.3 产销不平衡运输问题及应用3.3.1 产量大于销量 产销平衡: 产销平衡B1 B2 … Bn A1 c11 c12 … c1n A2 c21 c22 … c2n … … … …… Am cm1 cm2 … cmn 销量 b1 b2 … bnmin z = ∑∑ cij xij ∑ xij = ai i = 1, 2,..., m j =1 m s.t. ∑ xij = b j j = 1, 2,..., n i =1 xij ≥ 0 i = 1, 2,..., m; j = 1, 2,..., n n

用产销平衡的数学模型,其约束 当∑ai>∑bj时, 用产销平衡的数学模型 其约束 会产生矛盾.此时模型应改为 此时模型应改为: 会产生矛盾 此时

模型应改为min z = ∑∑ cij xijm n

Bn+1 0 0 … 0 bn+1

产量 a1 a2 … am

n ∑ xij ≤ ai i = 1, 2,..., m j =1 m s.t. ∑ xij = b j j = 1, 2,..., n i =1 xij ≥ 0 i = 1, 2,..., m; j = 1, 2,..., n

i =1 j =1

m

n

若用表上作业法求之,可设一个假想销地 若用表上作业法求之 可设一个假想销地, 使其销 可设一个假想销地 量为b 量为 n+1=∑ai-∑bj,ci,n+1=0.min z = ∑∑ cij xij n +1 ∑ xij = ai i = 1, 2,..., m j =1 m s.t. ∑ xij = b j j = 1, 2,..., n + 1 i =1 xij ≥ 0 i = 1, 2,..., m; j = 1, 2,..., n + 1 i =1 j =1 m n

i =1 j =1

运筹学运输问题

P121例3.1 例销地 产地 A1 A2 A3 销量 B1 B2 B3 B4 产量 15 25 18 2 20 30 19 4 30 16 25 5 17 10 20 4 5 8 6

最小元素法求初始方案销地 产地 A1 A2 A3 B1 15 B2 20 30 19 B3 30 16 B4 17 B5 产量

05 1

125 18 10

408 4 06 5 1 4

425

420 4

解:添加假想销地 使产销平衡 添加假想销地,使产销平衡 添加假想销地销地 产地 A1 A2 A3 销量 B1 B2 B3 B4 B5 产量 15 25 18 2 20 30 19 4 30 16 25 5 17 10 20 4 0 0 0 4 5 8 6

1销量 2

44

15

1 位势法求检验数销地 B1 B2 产地 A1 15 [4] A2 [16] [20] A3 18 19 vj 15 16

1

B3

B4

B5 0

ui

0 16 10 [6] -6 25 [1] [-3] 3 22 16 0

[8] [1]

运筹学运输问题

单位运价表销地 产地 A1 A2 A3 销量 销地 产地 A1 A2 A3 销地 产地 A1 A2 A3 B1 B2 B3 B4 B5 产量 15 20 30 17 0 25 30 16 10 0 18 19 25 20 0 2 4 5 4 4 5 8 6

求检验数销地 B1 B2 产地 A1 15 [1] [19] [20] A2 [3] 19 A3 vj 15 19 B3 B4 B5 ui 0 -9 0

[5] [-2] 0 16 10 [9] 25 [1] 0 25 19 0 B3 5 B4 1 3 B5 2 2

闭回路法调整方案B1 1 1 4 4 1 4 B2 B3 B4 B5 4

方案调整销地 产地 A1 A2 A3 B1 2 4 B2

求检验数B1 2 4 4 1 4 1 B2 B3 B4 B5 3 销地 B1 B2 B3 B4 B5 产地 A1 15 [1] [7] 17 0 A2 [17] [18] 16 10 [7] [3] 19 [2] [3] 0 A3 vj 15 19 23 17 0 ui 0 -7 0

最 优 方 案

运筹学运输问题

3.3 产销不平衡运输问题及应用3.3.2 产量小于销量 产销平衡: 产销平衡B1 A1 A2 … Am Am+1 销量n

用产销平衡的数学模型,其约束 当∑ai<∑bj时, 用产销平衡的数学模型 其约束 会产生矛盾.此时模型应改为 此时模型应改为: 会产生矛盾 此时模型应改为min z = ∑∑ cij xij n ∑ xij = ai i = 1, 2,..., m j =1 m s.t. ∑ xij ≤ b j j = 1, 2,..., n i =1 xij ≥ 0 i = 1, 2,..., m; j = 1, 2,..., n i =1 j =1 m n

B2 … Bn 产量 c12 c22 … cm2 M b2n

c11 c21 … cm1 M b1m

… … … … … …

c1n a1 c2n a2 … … cmn am M am+1 bn

min z = ∑∑ cij xij ∑ xij = ai i = 1, 2,..., m j =1 m s.t. ∑ xij = b j j = 1, 2,..., n i =1 xij ≥ 0 i = 1, 2,..., m; j = 1, 2,..., n i =1 j =1

若用表上作业法求之,可设一个假想产地 若用表上作业法求之 可设一个假想产地, 使其销 可设一个假想产地 量为a 量为 m+1=∑bj-∑ai,cm+1,j=M.min z = ∑∑ cij xij n ∑ xij = ai i = 1, 2,..., m + 1 j =1 m+1 s.t. ∑ xij = b j j = 1, 2,..., n i =1 xij ≥ 0 i = 1, 2,..., m + 1; j = 1, 2,..., n i =1 j =1 m n

运筹学运输问题

销量

有弹性运输问题( 销量有弹性运输问题(P123例3.2) 例销地 I 产地 A 15 B 14 C 18 最低需求 60 最高需求 100 II 13 13 20 140 140 III IV 产量 100 120 100

最优方案： 最优方案：销地 I’ I’’ II III IV’ 产地 A 100 B 0 40 20 C 60 40 D 60 60 40 140 60 20 销量 IV’’ 产量 100 60 120 100 40 100 100

22 17 18 15 25 — 0 20 60 不限

总产量320万吨，产地I、II、III最低需 总产量320万吨，产地I、II、III最低需 万吨 万吨， 最多可供应120万 求200万吨，产地 最多可供应 万吨 产地IV最多可供应 万 吨。销地 产地 A B C D 销量 I’ I’’ II III IV’ IV’’ 产量 22 18 25 0 17 17 100 15 15 120 M M 100 M 0 100

表上作业法过程讲解 表上作业法略去， 表上作业法略去，返回目录页

15 15 13 14 14 13 18 18 20 M 0 M

60 40 140 60 20 100

运筹学运输问题

P123例3.2表上作业法 例 表上作业法销地 I 产地 A 15 B 14 C 18 最低需求 60 最高需求 100

最小元素法给出初始方案： 最小元素法给出初始方案：II 13 13 20 140 140 III IV 产量 100 120 100 22 17 18 15 25 — 0 20 60 不限 销地 I’ I’’ II III IV’ IV’’ 产地 100 A 60 20 40 B C 60 20 20 D 0 100 60 40 140 60 20 100 销量 20 40 0 产量 100 120 80 20 100 80 20 100

总产量320万吨，产地I、II、III最低需 总产量320万吨，产地I、II、III最低需 万吨 万吨， 最多可供应120万 求200万吨，产地 最多可供应 万吨 产地IV最多可供应 万 吨。销地 产地 A B C D 销量 I’ I’’ II III IV’ IV’’ 产量 22 18 25 0 17 17 100 15 15 120 M M 100 M 0 100

位势法求检验数： 位势法求检验数：销地 产地 A B C D vj I’ I’’ II III IV’ IV’’ ui 0 0 4 -21

15 15 13 14 14 13 18 18 20 M 0 M

(1) (1) 13 (1) (21-M)(-4) 14 14 13 (-3)(19-M)(-6) (0) 18 (3) 25 M(M-25) (M+7)(7)(M+8) 0 (25) 0 14 14 13 21 M-4 21

60 40 140 60 20 100

运筹学运输问题

单位运价表： 单位运价表：销地 产地 A B C D 销量 I’ I’’ II III IV’ IV’’ 产量 22 18 25 0 17 17 100 15 15 120 M M 100 M 0 100 销地 I’ I’’ II III IV’ IV’’ 产量 产地 A 100 100 B 60 0 40 20 120 C 40 60 100 D 0 100 100 60 40 140 60 20 100 销量

15 15 13 14 14 13 18 18 20 M 0 M

60 40 140 60 20 100

闭回路调整方案： 闭回路调整方案：销地 I’ I’’ II III IV’ IV’’ 产地 A 100 B 60 20 40 C 20 60 20 D 0 100 销量 60 40 140 60 20 100 产量 100 120 100 100 销地 产地 A B C D vj I’ I’’ II III IV’ IV’’ ui

(1) (1) 13 (1) (2) (-4) 0 14 14 13 (-3) 15 (-6) 0 (0) 18 (3) 25 (M-) (M-) 4 (M-) (7) (M-) 0 (M-) 0 -21 14 14 13 21 15 21

运筹学运输问题

单位运价表： 单位运价表：销地 产地 A B C D 销量 I’ I’’ II III IV’ IV’’ 产量 22 18 25 0 17 17 100 15 15 120 M M 100 M 0 100 销地 I’ I’’ II III IV’ IV’’ 产地 A 100 B 60 40 20 0 C 40 60 D 0 100 销量 60 40 140 60 20 100 产量 100 120 100 100

15 15 13 14 14 13 18 18 20 M 0 M

60 40 140 60 20 100

闭回路调整

方案： 闭回路调整方案：销地 I’ I’’ II III IV’ IV’’ 产量 产地 A 100 100 B 60 0 40 20 120 C 40 60 100 D 0 100 100 60 40 140 60 20 100 销量 销地 产地 A B C D vj I’ I’’ II III IV’ IV’’ ui

(1) (7) 13 (7) (2) (2) 0 14 (6) 13 (3) 15 15 0 (-6) 18 (-3) 25 (M-) (M-) 10 (M-) (7) (M-) 0 (M-) 0 -15 14 8 13 15 15 15

运筹学运输问题

单位运价表： 单位运价表：销地 产地 A B C D 销量 I’ I’’ II III IV’ IV’’ 产量 22 18 25 0 17 17 100 15 15 120 M M 100 M 0 100 销地 产地 A B C D vj I’ (1) 14 18 (M-) 14 I’’ (1) (0) 18 (1) II III IV’ IV’’ ui

15 15 13 14 14 13 18 18 20 M 0 M

60 40 140 60 20 100

13 (7) (2) (2) 0 13 (3) 15 15 0 (3) (6) (M-) (M-) 4 (M-) 0 (M-) 0 -15 14 13 15 15 15

闭回路调整方案： 闭回路调整方案：销地 I’ I’’ II III IV’ 产地 A 100 B 0 40 20 C 60 40 D 60 60 40 140 60 20 销量 IV’’ 产量 100 60 120 100 40 100 100

最优方案

运筹学运输问题

3.4 应用举例[例3.3](P125) 例 ( )I I II III IV 销量 II III 270 290 300 M 25 IV 280 300 310 250 10 产量 20 25 25 20 250 260 M M M 10 280 M M 25

(1)当月生产当月销售，单位运价 生产成本 )当月生产当月销售，单位运价=生产成本 生产成本+存储成本 (2)前月生产后月销售，单位运价 生产成本 存储成本 )前月生产后月销售，单位运价=生产成本 (3)后月生产前月销售为不可能，运价为 )后月生产前月销售为不可能，运价为M 最小总费用=19200 最小总费用

运筹学运输问题

[例3.4](P127) 例 ( )以余缺为供需的运输问题 线路 1 2 3 4 从工地 E B A D B 1 0 1.5 1.2 1.5 3 到工地 D C F B C 2 1.5 0 2.5 2 2 D 2.5 1.2 2.5 0 2.5 3 需车次数 8 6 3 4 E 2 1.5 2 2.5 0 1.5 F 3 3 2 3 1.5 0

A C D F 缺少车次 2 2.5 3 3

B 1.5 1.2 3 2

E 2 2.5 1.5 8

多余车次 6 4 3

行驶时间表 A A 0 B 1 C 2 D 2.5 E 2 F 3 余缺表工地 A B C D E F

最优调度方案: 最优调度方案

A C 3

B

E 3

多余车次 6 4 3

到达 0 4 6 8 0 3

需求 3 6 0 4 8 0

余缺 -3 -2 6 4 -8 3

D F 缺少车次 3

2 2

2 3 8

行驶里程:23.9公里 公里 行驶里程

运筹学运输问题

[例](P131,3) 例( )

运筹学运输问题

本章小结1.运输问题由一个产销平衡表和一个单位运价表构成 运输问题由一个产销平衡表和一个单位运价表构成. 运输问题由一个产销平衡表和一个单位运价表构成 A1 A2 … A3 销量 B1 x11 x21 … xm1 b1 B2 x12 x22 … xm2 b2 … … … … … … Bn x1n x2n … xmn bn 产量 a1 a2 … am A1 A2 … A3 B1 c11 c21 … cm1 B2 c12 c22 … cm2 … … … … … Bn c1n c2n … cmnX = ( xij ) mn 决策变量矩阵 C = (cij ) mn a = (ai ) m b = (b j ) n 单位运价矩阵 产量行向量 销量列向量

2.运输问题数学模型 运输问题数学模型 产销平衡

产大于销

产小于销n

i =1 j =1 i =1 j =1 i =1 j =1 n n n ∑xij = ai i =1,2,..., m ∑xij ≤ ai i =1,2,..., m ∑xij = ai i =1,2,..., m j=1 j=1 j=1 m m m st.∑xij = bj j =1,2,..., n . st.

∑xij = bj j =1,2,..., n . st.∑xij ≤ bj j =1,2,..., n . i=1 i=1 i=1 xij ≥ 0 i =1,2,..., m; j =1,2,..., n xij ≥ 0 i =1,2,..., m; j =1,2,..., n xij ≥ 0 i =1,2,..., m; j =1,2,..., n 3.表上作业法 最小元素法给出初始方案、位势法求检验数、闭回路法调整方案 表上作业法:最小元素法给出初始方案 表上作业法 最小元素法给出初始方案、位势法求检验数、

min z = ∑∑ cij xij

m

n

min z = ∑∑ cij xij

m

min z = ∑∑ cij xij

m

n

4. 依据数学模型，用EXCEL求解。 依据数学模型， 求解。 求解

作业： 作业：P131:4(写出产销平衡表 ( 与单位运价表，不求解) 与单位运价表，不求解)

运筹学运输问题

部分习题解答：3.1(1);(2). 3.2; 3.3; 3.4; 3.5。