数学建模运输问题

1、 运输问题模型运输问题模型 Transportation 一问题的提出一问题的提出 门市部门市部 加工厂加工厂 B1B2B3B4 A1311310 A21928 A374105 公司把这些糖果分别运往四个地区的门市部销售，公司把这些糖果分别运往四个地区的门市部销售， 各地区每天的销售量分别为：各地区每天的销售量分别为： B1 13 3吨，吨，B26 6吨，吨，B35 5吨，吨，B46 6吨。吨。 A17 吨，吨，A24吨，吨，A39吨。吨。 某食品公司主要经营糖果。某食品公司主要经营糖果。 它下面设有三个加工厂，它下面设有三个加工厂， 每天的糖果生产量分别为：每天的糖果生产量分别为： 已知从每

2、个加工厂到各销售门市部每吨糖果的运价如上表所示，已知从每个加工厂到各销售门市部每吨糖果的运价如上表所示， 该食品公司应如何调运，在满足各门市部销售需要的情况下，该食品公司应如何调运，在满足各门市部销售需要的情况下， 使总的运费支出为最少。使总的运费支出为最少。 二问题的概述二问题的概述 在线性规划中研究这样一类问题：在线性规划中研究这样一类问题： 有某种物资需要调运，这种物资的计量单位可以是重量，有某种物资需要调运，这种物资的计量单位可以是重量， 包装单位或其他。包装单位或其他。 已知已知: : 有有m 个地点可以供应该种物资（统称产地，用个地点可以供应该种物资（统称产地，用 i =1,m 表

3、示）；表示）； 有有 n 个地点需要该种物资（统称销地，用个地点需要该种物资（统称销地，用 j =1,n 表示）。表示）。 n 个销地的需要量（统称销量）为个销地的需要量（统称销量）为b1 , b2, , bn（统写为（统写为 b j ）。）。 从第从第 i 个产地到第个产地到第 j 个销地的单位物资运价为个销地的单位物资运价为c i j 。 又知又知 m 个产地的可供量（统称产量）为个产地的可供量（统称产量）为a1 , a2, , am（统写为（统写为a i ）；）； 上面这些数据通常用产销平衡表和单位运价表来表示。上面这些数据通常用产销平衡表和单位运价表来表示。 销地销地 产地产地 12n

4、产量产量 1 2 . . . m a1 a2 . . . am 销量销量b1b2bn 销地销地 产地产地 1 2 n 1 2 . . . m c11 c12 c1n c21 c22 c2n . . . . . . . . . cm1 cm2 cmn 产销平衡表产销平衡表 单位运价表单位运价表 有时候把两个表写在一起有时候把两个表写在一起: : 销地销地 产地产地 1 2 n 1 2 . . . m c11 c12 c1n c21 c22 c2n . . . . . . . . . cm1 cm2 cmn 销地销地 产地产地 12n 产产 量量 1 2 . . . m a1 a2 . . . a

5、m 销量销量b1b2bn 销地销地 产地产地 1 2 n 产产 量量 1 2 . . . m c11 c12 c1n c21 c22 c2n . . . . . . . . . cm1 cm2 cmn a1 a2 . . . am 销量销量b1 b2 bn 三运输问题模型三运输问题模型 设设 xij 代表从第代表从第 i 个产地调运给个产地调运给 第第 j 个销地的物资数量。个销地的物资数量。 在产销平衡的条件下在产销平衡的条件下，要求解，要求解 运输问题使总的运费支出最小，运输问题使总的运费支出最小， 则有如下的运输问题数学模型：则有如下的运输问题数学模型： 0 ij x ),1( 1 nj

6、bx j m i ij ),1( 1 miax i n j ij m i n j ijij xcz 11 min 销地销地 产地产地 1 2 n 产产 量量 1 2 . . . m x11 x12 x1n x21 x22 x2n . . . . . . . . . xm1 xm2 xmn a1 a2 . . . am 销量销量b1 b2 bn 销地销地 产地产地 1 2 n 产产 量量 1 2 . . . m c11 c12 c1n c21 c22 c2n . . . . . . . . . cm1 cm2 cmn a1 a2 . . . am 销量销量b1 b2 bn 0 ),1( ),1(

7、 min 1 1 11 ij j m i ij i n j ij m i n j ijij x njbx miax xcz 如果用单纯形法求解，如果用单纯形法求解， 先要在每个约束条件左端加上一个人工变量，先要在每个约束条件左端加上一个人工变量， 因此即使象食品公司调运糖果这样简单的数学问题，因此即使象食品公司调运糖果这样简单的数学问题， 变量数就有变量数就有 34+3+4=19=19个之多，计算起来非常繁杂。个之多，计算起来非常繁杂。 运输问题的数学模型结构比较特殊，运输问题的数学模型结构比较特殊， 它的约束条件变量的系数矩阵具有如下的形式：它的约束条件变量的系数矩阵具有如下的形式： 运输问

8、题的数学模型包含运输问题的数学模型包含 mn个变量，个变量， ( (m+n) )个约束条件。个约束条件。 说明：说明： 0 ),1( ),1( min 1 1 11 ij j m i ij i n j ij m i n j ijij x njbx miax xcz 产销不平衡的运输问题产销不平衡的运输问题 m i n j ji ba 11 1 1产大于销产大于销 1 1）数学模型）数学模型 销地销地 产地产地 1 2 n 产产 量量 1 2 . . . m x11 x12 x1n x21 x22 x2n . . . . . . . . . xm1 xm2 xmn a1 a2 . . . am

9、销量销量b1 b2 bn m i n j ijij xcz 11 min 0 ),1( ),1( 1 1 ij m i jij n j iij x njbx miax s.t. 产大于销时，增加一个假想的销地产大于销时，增加一个假想的销地 j = = n+1+1（库存），（库存）， 2 2）求解方法）求解方法: : 转化为产销平衡问题转化为产销平衡问题 该销地的总需求量为该销地的总需求量为 m i n j ji ba 11 而在单位运价表中从各产地到假想销地的单位运价为而在单位运价表中从各产地到假想销地的单位运价为 就转化为一个产销平衡的运输问题。就转化为一个产销平衡的运输问题。 具体做法如下

10、：具体做法如下： 销地销地 产地产地 1 2 n产量产量 1 2 . . . m c11 c12 c1n c21 c22 c2n . . . . . . . . . cm1 cm2 cmn a1 a2 . . . am 销量销量 b1 b2 bn n+1 0 0 . . . 0 库存库存 0 1, ni c m i n j ji ba 11 2.2.销大于产销大于产 销地销地 产地产地 1 2 n 产产 量量 1 2 . . . m x11 x12 x1n x21 x22 x2n . . . . . . . . . xm1 xm2 xmn a1 a2 . . . am 销量销量b1 b2 bn

11、 0 ),1( ),1( . min 1 1 11 ij j m i ij i n j ij m i n j ijij x njbx miax ts xcz 1 1）数学模型）数学模型 m i i n j j ab 11 销大于产时，在产销平衡表中增加一个假想的产地销大于产时，在产销平衡表中增加一个假想的产地 i = m+1， 该地产量为该地产量为 在单位运价表中，在单位运价表中， 从假想产地到各销地的单位运价为从假想产地到各销地的单位运价为 就转化为产销平衡的运输问题。就转化为产销平衡的运输问题。 具体做法如下：具体做法如下： 销地销地 产地产地 1 2 n产量产量 1 2 . . . m

12、c11 c12 c1n c21 c22 c2n . . . . . . . . . cm1 cm2 cmn a1 a2 . . . am 销量销量 b1 b2 bn m+1 0 0 0 短缺短缺 0 ,1 jm c 2 2）求解方法）求解方法: : 转化为产销平衡问题转化为产销平衡问题 应用实例应用实例 设有设有A1 1、A2 2、A3 3三个产地生产某种物资，产量分别为三个产地生产某种物资，产量分别为7 7、5 5、7 7吨，吨， B1 1、B2 2、B3 3、B4 4四个销地需要该物资，销量分别为四个销地需要该物资，销量分别为2 2、3 3、4 4、6 6吨。吨。 又知各产销地之间的单位运

13、价见下表，又知各产销地之间的单位运价见下表， 试决定总运费最少的调运方案。试决定总运费最少的调运方案。 销地销地 产地产地 B1 1 B2 2 B3 3 B4 4 A1 1 A2 2 A3 3 2 2 11 11 3 3 4 4 10 10 3 3 5 5 9 9 7 7 8 8 1 1 2 2 解：解： 产地总产量为产地总产量为1919吨，吨， 销地总销量为销地总销量为1515吨，吨， 这是一个产大于销的运输问题。这是一个产大于销的运输问题。 首先转化为产销平衡的运输问题，首先转化为产销平衡的运输问题， 其产销平衡表和单位运价表分别见下两表。其产销平衡表和单位运价表分别见下两表。 销地销地

14、产地产地 B1 1 B2 2 B3 3 B4 4 库存库存 产产 量量 A1 1 A2 2 A3 3 7 7 5 5 7 7 销量销量 2 3 4 6 2 3 4 6 4 4 A17吨，吨，A25吨，吨，A37 7吨。吨。 B12吨，吨，B23吨，吨，B34吨，吨，B46 6吨。吨。 销地销地 产地产地 B1 1 B2 2 B3 3 B4 4 A1 1 A2 2 A3 3 2 2 11 11 3 3 4 4 10 10 3 3 5 5 9 9 7 7 8 8 1 1 2 2 销地销地 产地产地 B1 1 B2 2 B3 3 B4 4 库存库存 A1 1 A2 2 A3 3 2 2 11 11

15、3 3 4 4 0 0 10 10 3 3 5 5 9 9 0 0 7 7 8 8 1 1 2 2 0 0 用表上作业法计算，用表上作业法计算， 求得最优调运方案为：求得最优调运方案为： 销地销地 产地产地 B1 1 B2 2 B3 3 B4 4 库存库存产量产量 A1 1 A2 2 A3 3 2 2 3 3 2 2 3 3 2 2 4 3 4 3 7 5 7 销量销量 2 3 4 6 2 3 4 6 4 4 销地销地 产地产地 B1 1 B2 2 B3 3 B4 4 A1 1 A2 2 A3 3 2 2 11 11 3 3 4 4 10 10 3 3 5 5 9 9 7 7 8 8 1 1

16、2 2 销地销地 产地产地 B1 1 B2 2 B3 3 B4 4 产量产量 A1 1 A2 2 A3 3 x11 11 x12 12 x13 13 x14 14 x21 21 x22 22 x23 23 x24 24 x31 31 x32 32 x33 33 x34 34 7 7 5 5 7 7 销量销量 2 3 4 62 3 4 6 0 6 4 3 2 7 5 7 . min 342414 332313 322212 312111 34333231 24232221 14131211 3 1 4 1 ij ij ijij x xxx xxx xxx xxx xxxx xxxx xxxx t

17、s xcz LINGOLINGO求解求解 Global optimal solution found at iteration: 8 Objective value: 35.00000 设有三个电视机厂供应四个地区某种型号的电视机。设有三个电视机厂供应四个地区某种型号的电视机。 各厂家的年产量、各厂家的年产量、 各地区的年销售量以及各地区的年销售量以及 各地区的单位运价各地区的单位运价 如右表，如右表， 试求出总的运费最省的试求出总的运费最省的 电视机调拨方案。电视机调拨方案。 销地销地 厂家厂家 B1 B2 B3 B4 产量产量 (万台万台) A1 A2 A3 6 3 12 6 4 3 9

18、9 10 13 10 10 12 10 最低需求（万台）最低需求（万台） 最高需求（万台）最高需求（万台） 6 14 0 5 10 14 6 不限不限 销地销地 厂家厂家 B1 B1 B2 B3 B4 B4 产量产量 （万台）（万台） A1 A2 A3 6 6 3 12 6 6 4 4 3 9 9 9 10 13 10 10 10 12 10 销量销量 6 4 14 6 5 7 12 A410MMM000 M M 销地销地 厂家厂家 B1 B1 B2 B3 B4 B4 产量产量 （万台）（万台） A1 A2 A3 A4 10 6 2 4 2 5 3 6 4 10 12 10 10 销量销量 6

19、 4 14 6 5 3+4 总运价总运价:172元元LingoLingo求解求解 销地销地 厂家厂家 B1 B1 B2 B3 B4 B4 产量产量 （万台）（万台） A1 A2 A3 A4 10 4 4 4 2 5 3 6 4 10 12 10 10 销量销量 4 6 14 6 5 3+4 Global optimal solution found at iteration: 8 Objective value: 172.0000 10 14131211 xxxx 12 232221 xxx 10 34333231 xxxx 106 312111 xxx 14 322212 xxx 6 332

20、313 xxx 5 3414 xx 销地销地 厂家厂家 B1 B2 B3 B4 产量产量 (万台万台) A1 A2 A3 6 3 12 6 4 3 9 9 10 13 10 10 12 10 最低需求（万台）最低需求（万台） 最高需求（万台）最高需求（万台） 6 14 0 5 10 14 6 不限不限 销地销地 厂家厂家 1 2 3 4 1 2 3 x11 x12 x13 x14 x21 x22 x23 x24 x31 x32 x33 x34 3433323124 23222114131211 10131091000 93461236min xxxxx xxxxxxxz 0 5 6 14 10

21、6 10 12 10 . 10131091000 93461236min 3414 332313 322212 312111 34333231 232221 14131211 3433323124 23222114131211 ij x xx xxx xxx xxx xxxx xxx xxxx ts xxxxx xxxxxxxz LingoLingo求解求解 Global optimal solution found at iteration: 16 Objective value: 172.0000 销地销地 厂家厂家 B1 B2 B3 B4 产量产量 (万台万台) A1 A2 A3 6 3

22、 12 6 4 3 9 9 10 13 10 10 12 10 最低需求（万台）最低需求（万台） 最高需求（万台）最高需求（万台） 6 14 0 5 10 14 6 不限不限 销地销地 厂家厂家 B1 B2 B3 B4 产量产量 (万台万台) A1 A2 A3 10 8 4 2 8 10 12 10 最低需求（万台）最低需求（万台） 最高需求（万台）最高需求（万台） 6 14 0 5 10 14 6 不限不限 中转调运问题中转调运问题 1.已知甲、乙两处分别有已知甲、乙两处分别有100吨和吨和85吨同种物资外运，吨同种物资外运， A、B、C三处各需要物资三处各需要物资55，60，70吨。吨。

23、物资可以直接运到目的地，也可以经某些中转点转运。物资可以直接运到目的地，也可以经某些中转点转运。 已知各处之间的单位运价如下表，试确定一个最优的调运方案。已知各处之间的单位运价如下表，试确定一个最优的调运方案。 甲甲乙乙 甲甲 乙乙 0 10 12 0 ABC 甲甲 乙乙 10 15 14 12 12 18 ABC A B C 0 10 8 14 0 12 11 4 0 甲甲乙乙 甲甲 乙乙 0 10 12 0 ABC 甲甲 乙乙 10 15 14 12 12 18 ABC A B C 0 10 8 14 0 12 11 4 0 ABC 甲甲 乙乙 10 15 14 12 12 18 100

24、85 556070 销地销地 产地产地 甲甲乙乙ABC产量产量 甲甲 乙乙 A B C 0 10 10 14 12 12 0 15 12 18 10 15 0 10 8 14 12 14 0 12 12 18 11 4 0 销量销量 甲甲乙乙ABC产量产量 甲甲 乙乙 A B C 85 100 55 130 85 100 45 25 115 185 185 130 125 115 销量销量85100185185185 185 185 130 125 115 85 100 185185 185 用用LingoLingo求解求解甲甲A :55吨，吨，甲甲C C :45 :45吨吨; ; 乙乙B 6

25、060吨吨 2525吨吨C Global optimal solution found at iteration: 10 Objective value: 2210.000 进一步讨论：不考虑中转调运。进一步讨论：不考虑中转调运。 ABC 甲甲 乙乙 10 15 14 12 12 18 100 85 556070 用用LingoLingo求解求解 Global optimal solution found at iteration: 3 Objective value: 2235.000 ABC 甲甲 乙乙 30 2560 70100 85 556070 门市部门市部 加工厂加工厂 B1B2B

26、3B4 A1311310 A21928 A374105 公司把这些糖果分别运往四个地区公司把这些糖果分别运往四个地区 的门市部销售，各地区每天的销售量分别为：的门市部销售，各地区每天的销售量分别为： B1 13 3吨，吨，B26 6吨，吨，B35 5吨，吨，B46 6吨。吨。 A17 吨，吨，A24吨，吨，A39吨。吨。 2.某食品公司主要经营糖果。某食品公司主要经营糖果。 它下面设有三个加工厂，它下面设有三个加工厂， 每天的糖果生产量分别为：每天的糖果生产量分别为： 假设有四个中转站假设有四个中转站, , 每个加工厂生产的糖果在运往销地的过程中每个加工厂生产的糖果在运往销地的过程中 可以在产

27、地、中转站和销地之间转运。可以在产地、中转站和销地之间转运。 已知各产地、销地和中转站之间的单位运价如表所示，已知各产地、销地和中转站之间的单位运价如表所示， 试确定总运费最少的调运方案。试确定总运费最少的调运方案。 产产 地地中中 转转 地地销销 地地 A1A2A3T1T2T3T4B1B2B3B4 产产 地地 A1 A2 A3 0 1 3 1 0 - 3 - 0 2 3 1 1 5 - 4 - 2 3 2 3 3 1 7 11 9 4 3 2 10 10 8 5 中中 转转 站站 T1 T2 T3 T4 2 1 4 3 3 5 - 2 1 - 2 3 0 1 3 2 1 0 1 1 3 1

28、0 2 2 1 2 0 2 4 1 1 8 5 8 - 4 2 2 2 6 7 4 6 销销 地地 B1 B2 B3 B4 3 11 3 10 1 9 2 8 7 4 10 5 2 8 4 6 4 5 2 7 1 8 2 4 1 - 2 6 0 1 4 2 1 0 2 1 4 2 0 3 2 1 3 0 B1 13 3吨，吨，B26 6吨，吨，B35 5吨，吨，B46 6吨吨 总销量：总销量：2020吨吨 A17 吨，吨，A24吨，吨，A39吨吨 总产量：总产量：2020吨吨 销地销地 产地产地 A1A2A3T1T2T3T4B1B2B3B4 产产 量量 A1 A2 A3 0 1 3 1 0 -

29、 3 - 0 2 3 1 1 5 - 4 - 2 3 2 3 3 1 7 11 9 4 3 2 10 10 8 5 T1 T2 T3 T4 2 1 4 3 3 5 - 2 1 - 2 3 0 1 3 2 1 0 1 1 3 1 0 2 2 1 2 0 2 4 1 1 8 5 8 - 4 2 2 2 6 7 4 6 B1 B2 B3 B4 3 11 3 10 1 9 2 8 7 4 10 5 2 8 4 6 4 5 2 7 1 8 2 4 1 - 2 6 0 1 4 2 1 0 2 1 4 2 0 3 2 1 3 0 销量销量 20 20 20 20 20 20 20 17 14 15 14 1

30、3 16 1120 20 20 2020 20 20 20 用用LingoLingo求解求解 Global optimal solution found at iteration: 41 Objective value: 68.00000 Variable Value Reduced Cost VOLUME( WH1, C1) 13.00000 0.000000 VOLUME( WH1, C2) 7.000000 0.000000 VOLUME( WH2, C2) 9.000000 0.000000 VOLUME( WH2, C8) 11.00000 0.000000 VOLUME( WH3,

31、 C3) 11.00000 0.000000 VOLUME( WH3, C6) 9.000000 0.000000 VOLUME( WH4, C4) 20.00000 0.000000 VOLUME( WH5, C5) 20.00000 0.000000 VOLUME( WH6, C6) 11.00000 0.000000 VOLUME( WH6, C8) 4.000000 0.000000 VOLUME( WH6, C10) 5.000000 0.000000 VOLUME( WH7, C7) 20.00000 0.000000 VOLUME( WH8, C8) 5.000000 0.000

32、000 VOLUME( WH8, C9) 6.000000 0.000000 VOLUME( WH8, C11) 6.000000 0.000000 VOLUME( WH9, C9) 14.00000 0.000000 VOLUME( WH10, C10) 15.00000 0.000000 VOLUME( WH11, C11) 14.00000 0.000000 销地销地 产地产地 A1A2A3T1T2T3T4B1B2B3B4 产产 量量 A1 A2 A3 13 1 3 7 9 - 3 - 11 2 3 1 1 5 - 4 - 9 3 2 3 3 11 7 11 9 4 3 2 10 10

33、8 5 T1 T2 T3 T4 2 1 4 3 3 5 - 2 1 - 2 3 20 1 3 2 1 20 1 1 3 1 11 2 2 1 2 20 2 4 4 1 8 5 8 - 4 2 5 2 6 7 4 6 B1 B2 B3 B4 3 11 3 10 1 9 2 8 7 4 10 5 2 8 4 6 4 5 2 7 1 8 2 4 1 - 2 6 8 1 4 2 6 14 2 1 4 2 15 3 6 1 3 14 销量销量 20 20 20 20 20 20 20 17 14 15 14 13 16 1120 20 20 2020 20 20 20 Global optimal so

34、lution found at iteration: 41 Objective value: 68.00000 直接调运：直接调运：8585元元 6 14 B4 6 14 B2 15 5 B3 20 T4 20 T2 11 9 T3 11 A3 7 9 A2B1T1A1 B1 B2 B3 B4 T1 T2 T3 T4 A1 A2 A3 8 4 20 11 13 销地销地 产地产地 B1 13 3吨，吨，B26 6吨，吨，B35 5吨，吨，B46 6吨吨A17 吨，吨，A24吨，吨，A39吨吨 6 6 7 A1（7） A2（4+7） B1（11+4） 11 B2（6） B4（6） A3（9） T

35、3（9） 9 4 5 B3（5） （设备生产计划）（设备生产计划） 某公司按照合同规定需要在当年每个季度末分别提供某公司按照合同规定需要在当年每个季度末分别提供 1010、1515、2525、2020台同一规格的某种机器设备。台同一规格的某种机器设备。 已知该公司各季度的生产能力以及生产每台设备的成本下表。已知该公司各季度的生产能力以及生产每台设备的成本下表。 如果生产的设备当季度不交货，如果生产的设备当季度不交货， 则每台积压一个季度所需的存储、维护等费用为则每台积压一个季度所需的存储、维护等费用为0.150.15万元。万元。 试确定在完成合同任务的条件下，试确定在完成合同任务的条件下， 使公司全年生产费用最小的设备生产计划。使公司全年生产费用最小的设备生产计划。 季度季度生产能力（万台）生产能力（万台）单位成本（万元）单位成本（万元） 1 1 2 2 3 3 4 4 2525 3535 3030 1010 10.810.8 11.111.1 11.01