运筹学3.运输问题

运筹学3.运输问题

第三章 运输问题本章主要内容： 运输问题的数学模型 运输问题的求解—表上作业法 运输问题应用—建模

运筹学3.运输问题

第一节

运输问题的数学模型

第二节 第三节

表上作业法产销不平衡的运输问题

第四节

应用举例

运筹学3.运输问题

第一节一、数学模型例1销地 产地 A1 A2 bj B1 6 6 150

运输问题的数学模型B2 4 5 150 B3 6 5 200 ai 200 300 500 产地：货物发出的地点 销地：货物接收的地点 产量：各产地的可供货量

销量：各销地的货物需求量

s .t .

x11 x12 x13 200 x 21 x 22 x 23 300 x11 x 21 150 x12 x 22 150 x13 x 23 200 x ij 0; i 1,2; j 1,2,3

设xij 表示Ai 到B j的运量。则MinZ 6 x11 4 x12 6 x13 6 x21 5 x22 5 x23

运输问题就是研究如何组织调运，既 满足各产地的产量和各销地的需求， 又使得总运费最小。

运筹学3.运输问题

二、运输问题的一般数学模型 有m个地区生产某种物资，有n个地区需要该类物资 令a1, a2, …, am表示各产地产量, b1, b2, …, bn表示各销地的销量 设xij表示产地 i 运往销地 j 的物资量，cij表示对应的单位运费 产销平衡表 销地 1 2 产地 1 2 … m 销量 b1 b2 … bn4

单位运价表 销地 1 2 产地 a1 a2 … am 1 2 … m c11 c12 … c1n c21 c22 … c2n…...

… n

… n

cm1 cm2 … cmn

运筹学3.运输问题

MinZ cijijxijij w xi 1 j 1

m

n

s .t .

n x ij a i i 1,2, , m 产量约束 一般满足产销平衡： 产地约束 m n jm1 ai b j x b j 1,2, , n 销量约束 i 1 j 1 j ij i 1 x ij 0

产量约束：由某一产地运往各个销售地的物品数 量之和等于该产地的产量。 销量约束：由各个产地运往某一销售地的物品数 量之和等于该销售地的销量。5

运筹学3.运输问题

产大于销

MinZ cij xiji 1 j 1

m

n

a bi 1 i j 1

m

n

j

s .t .

销地 1 2

… n a1 a2 … am

产地1 2 … m 销量 b1 b2 … bn

n i 1, 2, , m xij ai j 1 m j 1, 2, , n xij b j i 1 xij 0

运筹学3.运输问题

产小于销(销大于产)

MinZ cij xiji 1 j 1

m

n

a bi 1 i j 1

m

n

j

s .t .

销地 1 2 产地 1 2 … m 销量

… n a1 a2 … am

n xij ai j 1 m xij b j i 1 xij 0

i 1, 2, , m j 1, 2, , n

b1 b2 … bn7

运筹学3.运输问题

定理1 运输问题的数学模型必有最优解。 首先，运输问题一定有可行解；其次，任何单位运 价cij≥0,从而对于任一可行解，必有目标函数值大于 或等于零，即目标函数有下界。 所以，求解运输问题时，不需要进行无最优解的判别。x11 x12 x1n x21 x22 x2 n x11

x12 x1n x21 x22 x2 n xm 1 xm 2 xmn bn a1 a2 xm1 xm 2 xmn am b1 b2

产量平衡 (m个)

销量平衡 (n个)

运筹学3.运输问题

三、变量xij的系数列向量的特征在例1中，运输问题的系数矩阵为：x11 x12 x13 x21 x22 x23

1 0 1 0 0

1 0 0 1 0

1 0 0 0 1

0 1 1 0 0

0 1 0 1 0

0 1 0 0 1

r ( A) 2 3 1 4 0 1 i 位置 Pij ei em j 1 m j位置 0 9

1.一般情况下,运输问题 决策变量xij的系数列向量为: 2.系数矩阵的元素等于0或1。

运筹学3.运输问题

x11 x12 x1n x21 x22 x 2n x11 x12 x1n x21 x22 x2 n xm 1 xm 2 xmn

a1 a2 xm1 xm 2 xmn am b1 b2 bn

3.运输问题系数矩阵的秩为m+n-1。 3.运输问题基变量的个数为m+n-1。

运筹学3.运输问题

四、闭回路1. 概念 例2销地 产地 A1 A2 A3 bj 3 B1 3 1 B2 11 B3 3 B4 10 ai 7 4 9 20

④9 2

③8 5

③7 4

①10

⑥6 5

③6

1)数字格

2)空格

3)闭回路

闭回路：以某空格为起点，用水平或垂直线划，只有当碰到某 恰当的数字格后，才能转900继续前进，直到回到起始空格为 止。11

运筹学3.运输问题

销地 产地 A1 A2 A3 bj

B1 3

B2 11

B3 3

B4 10

ai 7 4 9 20

④1 9 2

③85

③7 4

①10

⑥3 6 5

③6

运筹学3.运输问题

销地 产地 A1 A2 A3 bj

B1 3

B2 11

B3 3

B4 10

ai 7 4 9 20

④1 9 2

③85

③7 4

①10

⑥3 6 5

③6

运筹学3.运输问题

销地 产地 A1 A2 A3 bj

B1 3

B2 11

B3 3

B4 10

ai 7 4 9 20

④1 9 2

③85

③7 4

①10

⑥3 6 5

③6

运筹学3.运输问题

销地 产地 A1 A2 A3 bj

B1

B2

B3

B4

ai 7 4 9 20

31

11

3

10

④9 2

③8

③7 4

①10 5

⑥3 6 5

③6

运筹学3.运输问题

销地 产地 A1 A2 A3 bj

B1

B2

B3

B4

ai 7 4 9 20

31

11

3

10

④9 2

③8

③7 4

①10 5

⑥3 6 5

③6