文档介绍：第第五五章章运运输输问问题题?运输问题模型?表上作业法?运输问题扩展例1. 某公司从两个产地 A 1、A 2 将物品运往三个销地 B 1、 B 2、B 3 ,各产地的产量、各销地的销量和各产地运往个销地每件物品的运费如下表所示,问:应如何调运可使总运输费用最小? 引引例例 B 1B 2B 3产量 A 1646200 A 2655300 销量 150 150 200 销地产地解: 产销平衡问题: 总产量= 总销量设x ij为从产地 A i运往销地 B j的运输量,得到下列运输量表: Min z = 6 x 11 + 4 x 12 + 6 x 13 + 6 x 21 + 5 x 22 + 5 x 23 . x 11 + x 12 + x 13 = 200 x 21 + x 22 + x 23 = 300 x 11 + x 21 = 150 x 12 + x 22 = 150 x 13 + x 23 = 200 x ij≥ 0 ( i = 1 ,2;j = 1 ,2,3) 构建数学模型:线性规划模型 B 1B 2B 3产量 A 1x 11x 12x 13200 A 2x 21x 22x 23300 销量 150 150 200 500 销地产地运运输输问问题题的的一一般般形形式式假设某种物品有 m 个产地,用 A i 来表示( i=1,…,m) ,各地的产量分别为 a i( i=1,…,m) ,有 n 个销地,用 B j 来表示( j=1,…,n) ,各地的销量分别为 b j(j=1,…,n) ,从产地 A i 到销地 B j 运输一个单位物资的运价为 C ij ,问该如何调运物品使总运费最小? 4 运输问题的一般模型个销地的量个产地运往第为由第设jix ij 0 1 2 1 2 ij x ,i , , ,m, j , , ,n, ? ? ?? ? 1 1 min (1) m n ij ij i j z c x ? ???? 1 ( 1, , ) (2) n ij i j x a i m ?? ???约束: 1 ( 1, , ) (3) m ij j i x b j n ?? ??? a i——产地 i的产量, b j——销地 j的销量。(4) . (m个产地) ( ) n个销地产销平衡运输问题的模型 0, 1, 2, , , 1, 2, , , ij x i m j n ? ? ?? ? 1 1 min (1) m n ij ij i j z c x ? ???? 1 ( 1, , ) (2) n ij i j x a i m ?? ??? 1 ( 1, , ) (3) m ij j i x b j n ?? ??? 1 1 (4) m n i j i j a b ? ??? ?(5) : ?产量总和等于销量总和。?约束条件系数矩阵的元素等于 0或1。?约束条件系数矩阵的每一列有两个 1 其余都等于0 ,即每一个变量 x ij 在前 m 个约束方程中出现1次,在后 n个约束方程中出现 1次。?所有的约束都是等式约束。?[ ] A A b m n A A ??矩阵的前行之和等于后行之后。因此系数矩阵和的行向量都是线性相关。 1 1 ‥‥‥1 1 1 ‥‥‥1 1 1 ‥‥‥1‥‥‥ 1 1 ‥‥‥ 1