《运筹学》课程教学资源（PPT课件讲稿）运输问题

运输问题 ■运输问题及其数学模型 运输问题的表上作业法 运输问题的进一步讨论 ■指派问题 ■数学试验

运输问题 ◼ 运输问题及其数学模型 ◼ 运输问题的表上作业法 ◼ 运输问题的进一步讨论 ◼ 指派问题 ◼ 数学试验

(1)运输问题是特殊的线性规划问题。 (2)普通运输问题是追求运费最少问题。 (3)目前硏究问题:瓶颈运输问题;特殊运输问题等

⑴ 运输问题是特殊的线性规划问题。 ⑵ 普通运输问题是追求运费最少问题。 ⑶ 目前研究问题：瓶颈运输问题；特殊运输问题等

第一节运输问题及其数学模型 .问题的提出 例1某部门有3个同类型的工厂(产地),生产的产品由4个 销售点出售,各工厂的生产量、各销售点的销售量(假定单 位为t)以及各工厂到销售点的单位运价(元t)示于表32 中,问如何调运才能使总运费最小?

第一节 运输问题及其数学模型 一. 问题的提出 例1 某部门有3个同类型的工厂（产地），生产的产品由4个 销售点出售，各工厂的生产量、各销售点的销售量（假定单 位为t）以及各工厂到销售点的单位运价（元/t）示于表3-2 中，问如何调运才能使总运费最小？

表 3-2 销地 B B B 产地 3 4 12 4 11 16 12 x13 14 2 10 3 9 x 10 8 5 11 6 x 33 x 34 22 销量8 14 12 14 48

销地 产地 产量 4 12 4 11 16 2 10 3 9 10 8 5 11 6 22 销 量 8 14 12 14 48 A 1 A2 B1 B2 B3 B4 A3 表 3 - 2 11 x 12 x 13 x 14 x 21 x 22 x 23 x 24 x 31 x 32 x 33 x 34 x

运输问题的数学模型 运输问题的一般提法是:设某种物资有m个产地A, 29 An,各产地的产量是a,a2…an有n个销地B,B2,…,Bn, 各销地的销量是b,b2,…b,假定从产地4(i=1,2,…,m) 到销地B,(=1,2,…,m)运输单位物品的运价是C,问 怎样调运这些物品才能使总运费最小?

一. 运输问题的数学模型 运输问题的一般提法是：设某种物资有 m 个产地 , A1 , A2  , , Am 各产地的产量是 , , , ; a1 a2  am 有 个销地 , B1 , B2  , , Bn n 各销地的销量是 , , , . b1 b2  bn 假定从产地 A (i 1,2, ,m) i =  到销地 B ( j 1,2, ,n) j =  运输单位物品的运价是 cij ，问 怎样调运这些物品才能使总运费最小？

销地 B B B 产地 l 12 n 12 2 2n A 销量b

销地 产地 产 量 销 量 A1 A2 Am B1 B2 Bn   11 c 12 c n c1 11 x 12 x n x1 21 c 22 c n c2 21 x 22 x n x2 m1 c m2 c mn c m1 x m2 x mn x  b1 b2  n b a1 2 a m a

如果运输问题的总产量等于总销量,即有 ∑a=∑ (31) 则称该运输问题为产销平衡问题;反之,称产销不平衡问题。 产销平衡问题 mIn ∑∑ 的数学模型为: ∑ 32) s1∑ ≥0 j=1,2…n

如果运输问题的总产量等于总销量，即有   = = = m i n j ai bj 1 1 则称该运输问题为产销平衡问题；反之，称产销不平衡问题。 产销平衡问题 的数学模型为： = = = n i m j ij ij z c x 1 1 min 1 1 1,2, , . 1,2, 1,2, , 0 1,2, n ij i j m ij j i ij x a i m s t x b j n i m x j n = =  = =     = =   =    =   （3.1） （3.2）

§2运输问题的表上作业法 例1某部门有3个同类型的工厂(产地),生产的产品由4个 销售点出售,各工厂的生产量、各销售点的销售量(假定单 位为t)以及各工厂到销售点的单位运价(元/)示于表32 中,问如何调运才能使总运费最小?

§2 运输问题的表上作业法 例1 某部门有3个同类型的工厂（产地），生产的产品由4个 销售点出售，各工厂的生产量、各销售点的销售量（假定单 位为t）以及各工厂到销售点的单位运价（元/t）示于表3-2 中，问如何调运才能使总运费最小？

表 3-2 销地 B B B 产地 3 4 12 4 11 16 12 x13 14 2 10 3 9 x 10 8 5 11 6 x 33 x 34 22 销量8 14 12 14 48

销地 产地 产量 4 12 4 11 16 2 10 3 9 10 8 5 11 6 22 销 量 8 14 12 14 48 A 1 A2 B1 B2 B3 B4 A3 表 3 - 2 11 x 12 x 13 x 14 x 21 x 22 x 23 x 24 x 31 x 32 x 33 x 34 x

该运输问题的数学模型为: minz= ∑∑cx=4x1+12x2+4x3+11+2x21 +10x2+3x23+9x24+8x31+5x2+11x3+6x34 x1+x1 12 +x1 16 21 x 23 24 10 + 22 Xu+X x 31 x1,+x2,+x2=14 13 x x Xu+x 14 24 x 14 ≥0,i=1,2,3;j=1,2,34

2 2 2 3 2 4 3 1 3 2 3 3 3 4 2 1 3 1 4 1 1 1 1 2 1 3 1 4 10 3 9 8 5 11 6 min 4 12 4 11 2 x x x x x x x z c x x x x x x i j i j i j + + + + + + + =  = + + + + = =               = = + + = + + = + + = + + = + + + = + + + = + + + = 0, 1, 2,3; 1,2,3,4 14 12 14 8 22 10 16 1 4 2 4 3 4 1 3 2 3 3 3 1 2 2 2 3 2 1 1 2 1 3 1 3 1 3 2 3 3 3 4 2 1 2 2 2 3 2 4 1 1 1 2 1 3 1 4 x i j x x x x x x x x x x x x x x x x x x x x x x x x i j 该运输问题的数学模型为：