数学建模运输问题.ppt

运输问题模型 Transportation 510 47 A 38291 A 210 311 3 A 1B 4B 3B 2B 1门市部加工厂公司把这些糖果分别运往四个地区的门市部销售, 各地区每天的销售量分别为: B 1—3吨, B 2—6吨, B 3—5吨, B 4—6吨。 A 1—7吨, A 2—4吨, A 3—9吨。某食品公司主要经营糖果。它下面设有三个加工厂, 每天的糖果生产量分别为: 已知从每个加工厂到各销售门市部每吨糖果的运价如上表所示, 该食品公司应如何调运,在满足各门市部销售需要的情况下, 使总的运费支出为最少。: 有某种物资需要调运,这种物资的计量单位可以是重量, 包装单位或其他。已知:有 m 个地点可以供应该种物资(统称产地,用 i =1, …, m 表示); 有n个地点需要该种物资(统称销地,用 j =1, …, n 表示)。 n个销地的需要量(统称销量)为 b 1 , b 2, …, b n(统写为 b j)。从第 i个产地到第 j个销地的单位物资运价为 c i j 。又知 m个产地的可供量(统称产量)为 a 1 , a 2, …, a m(统写为 a i); 上面这些数据通常用产销平衡表和单位运价表来表示。 b n… b 2b 1销量 a 1a 2...a m 12...m 产量 n… 21 销地产地c 11 c 12 …c 1nc 21 c 22 …c 2n. . . . . . . . . c m 1 c m 2 …c mn 12...m 1 2 …n 销地产地产销平衡表单位运价表有时候把两个表写在一起: c 11 c 12 …c 1nc 21 c 22 …c 2n. . . . . . . . . c m 1 c m 2 …c mn 12...m 1 2 …n 销地产地 b n… b 2b 1销量 a 1a 2...a m 12...m 产量 n… 21 销地产地a 1a 2...a m 产量 b 1b 2 …b n销量 c 11 c 12 …c 1nc 21 c 22 …c 2n. . . . . . . . . c m 1 c m 2 …c mn 12...m 1 2 …n ij代表从第 i 个产地调运给第j个销地的物资数量。在产销平衡的条件下,要求解运输问题使总的运费支出最小, 则有如下的运输问题数学模型: 0? ijx ),,1( 1njbx j mi ij?????),,1( 1miax i nj ij?????????? mi nj ij ijxcz 11 mina 1a 2...a m 产量 b 1b 2 …b n销量 x 11 x 12 …x 1nx 21 x 22 …x 2n. . . . . . . . . x m 1 x m 2 …x mn 12...m 1 2 …n 销地产地 a 1a 2...a m 产量 b 1b 2 …b n销量 c 11 c 12 …c 1nc 21 c 22 …c 2n. . . . . . . . . c m 1 c m 2 …c mn 12...m 1 2 …n 销地产地?????????????????????????0 ),,1( ),,1( min 1 1 11 ij j mi ij i nj ij mi nj ij ijx njbx m iax xcz??如果用单纯形法求解, 先要在每个约束条件左端加上一个人工变量, 因此即使象食品公司调运糖果这样简单的数学问题, 变量数就有 3× 4+3+4 =19 个之多,计算起来非常繁杂。运输问题的数学模型结构比较特殊, 它的约束条件变