运筹学-7.ppt

第七章运输问题【教学目标】 1、掌握运输问题数学模型的一般化形式 2、掌握平衡运输问题的表上作业法 3、掌握不平衡运输问题的求解思路及方法 1 第一节运输问题的数学模型引例:某物资有 m个产地 A 1、A 2、…、 A m,联合供应n个销地 B 1、B 2、…、B n,各产地的产量,销地的销量及各产地至各销地的运价如下表所示: 运价销地(元/T) 产地 B 1 B 2 …… B n产量(T) A 1… A mC 11 C 12 ……C 1n ………… C m1 C m2 ……C mna 1…a m 销量( T)b 1 b 2…… b n 问:如何组织调运,可使总运费最省? 2 第一节运输问题的数学模型引例解:设 x ij表从 A i运往 B j地物资的数量(单位: T) 情形 1、∑a i=∑b j(产销平衡运输问题) 则有数学模型如下: Min S= ∑∑c ij x ij st: x 11+ x 12+…+ x 1n = a 1………… x m1+ x m2+…+ x mn = a m x 11+ x 21+…+ x m1 =b 1………… x 1n+ x 2n+…+ x mn =b nx ij ≥ 0( i=1 、…、m; j=1 、…、n ) 3 第一节运输问题的数学模型平衡运输问题数学模型的特点: A= X 11 X 12…… X 1n X 21 X 22…… X 2n…… X m1 X m2…… X mn 1 1 …… 1 1 1 …… 1………… 1 1 …… 1 1 1 …… 1 1 1 …… 1 ………… 1 1 …… 1 4 第一节运输问题的数学模型引例解:设 x ij表从 A i运往 B j地物资的数量(单位: T) 情形 2、∑a i≥∑b j(产销不平衡运输问题) 则有数学模型如下: Min S= ∑∑c ij x ij st: x 11+ x 12+…+ x 1n ≤ a 1………… x m1+ x m2+…+ x mn ≤ a m x 11+ x 21+…+ x m1 =b 1………… x 1n+ x 2n+…+ x mn =b nx ij ≥ 0( i=1 、…、m; j=1 、…、n ) 5 第一节运输问题的数学模型求解产销不平衡运输问题的思路: 转化为产销平衡运输问题 6 第二节运输问题的表上作业法例1:某食品公司下设 3个食品加工厂 A 1、A 2、A 3,联合供应 4个销售公司 B 1、B 2、 B 3 、 B 4 ,各加工厂的产量,销售公司的销售量及各加工厂至各销售公司的食品单位运价如下表所示: 运价销地(元/T) 产地 B 1 B 2 B 3 B 4产量(T) A 1A 2A 3 3 11 3 12 1 9 2 8 7 4 10 5 7 49 销量( T)3 6 5 6 问:如何组织调运,可使总运费最省? 20 207 第二节运输问题的表上作业法例1解: 准备——给出产销平衡表和单位运价表销地产地 B 1 B 2 B 3 B 4发量(T) A 1A 2A 37 49 收量( T)3 6 5 6 B 1 B 2 B 3 B