重庆工商大学：《管理运筹学》课程教学课件（讲稿）第三章 运输问题

第三章运输问题运输问题的数学模型运输问题的表上作业法产销不平衡的运输问题及其求解方法

第三章 运输问题 运输问题的数学模型 运输问题的表上作业法 产销不平衡的运输问题及其求解方法

第一节运输问题的数学模型运输问题是一类特殊的线性规划问题，本节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性

第一节 运输问题的数学模型 运输问题是一类特殊的线性规划 问题，本节介绍运输问题的数学模型 及其约束方程组的系数矩阵结构的特 殊性

【引例1】现有A，A，A，三个产粮区，可供应粮食分别为10，8，5（万吨），现将粮食运往B，B,，B，B四个地区，其需要量分别为5，7，8，3（万吨）。产粮地到需求地的运价（元吨）如表3-1所示，问如何安排一个运输计划，使总的运输费用最少。表3-1运价表（元/T）地区B4B1B2B3产量产粮区A132631053288A242915A3578323需要量

【引例1】现有A1 ，A2 ，A3 三个产粮区，可供应 粮食分别为10， 8，5（万吨），现将粮食运往B1 ，B2 ，B3 ，B4 四个地区，其需 要量分别为5，7，8，3（万吨）。产粮地到需求地的运价（元/ 吨）如表3-1所示，问如何安排一个运输计划，使总的运输费用 最少。 B1 B2 B3 B4 产量 地区 产粮区 A1 3 2 6 3 10 A2 5 3 8 2 8 A3 4 1 2 9 5 需要量 5 7 8 3 23 表3-1 运价表（元/T）

设xi-1,2,3；j=1,2,34)为i个产粮地运往第个需求地的运量，这样得到下列运输问题的数学模型：min Z=3x+2x, +6x13 +3x14 +5x21 +3x2 +8x2 +2x24 +4x +X32 +2x3, +9xXu + X21 + X31 = 5X1 + X12 + X13 +Xi4 = 10X12 + X22 + X32 = 7X21 + X22 + X23 + X24 = 8X13 + X23 + X33 = 8X31 +X32 +X33 + X34 = 5X14 + X24 + X34 = 3运量应大于或等于零（非负要求），即x, ≥0,i =1,2,3; j =1,2,3,4

设xij(i=1,2,3；j=1,2,3,4)为i个产粮地运往第j个需求地的运量， 这样得到下列运输问题的数学模型： 11 12 13 14 21 22 23 24 31 32 33 34 min Z  3x  2x  6x  3x  5x  3x  8x  2x  4x  x  2x  9x                  5 8 10 31 32 33 34 21 22 23 24 11 12 13 14 x x x x x x x x x x x x                    3 8 7 5 14 24 34 13 23 33 12 22 32 11 21 31 x x x x x x x x x x x x 运量应大于或等于零（非负要求），即 xij  0,i 1,2,3；j 1,2,3,4

有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数学模型看一个例子：【引例2】有三台机床加工三种零件，计划第i台的生产任务为a，（i=1,2,3)个零件，第j种零件的需要量为b,(i-1,2,3)，第台机床加工第种零件需要的时间为c：，如表3一2所示。问如何安排生产任务使总的加工时间最少？表3一2零件B1B2B3生产任务机床253A150614A26073440A3703050150需要量

有些问题表面上与运输问题没有多大关系，也可以建立与 运输问题形式相同的数学模型 看一个例子： 【引例2】有三台机床加工三种零件，计划第 i 台的生产任务 为a i ( i =1,2,3)个零件，第 j 种零件的需要量为 bj (j=1,2,3)，第 i台机床加工第j种零件需要的时间为cij ，如表3－2所示。问如 何安排生产任务使总的加工时间最少？ B1 B2 B3 生产任务 零件 机床 A1 5 2 3 50 A2 6 4 1 60 A3 7 3 4 40 需要量 70 30 50 150 表3－2

【解】设x（i=1,2,3；j-1,2,3,)为第i台机床加工第j种零件的数量，则此问题的数学模型为minZ= 5x1 +2xi2 +3xi3 +6x21 +4x22 +X23 +7x31 +3x32 +4x3X1 +X12 +X13 =50机床的生产任务X21 + X22 + X23 =60X31 + X32 +X3 = 401 +X21 +X31= 70零件的需求量X12 + X22 +X32 =30Xi3 +X23 +X33 =50Xj, ≥0,i=1,2,3; j=1,2,3

【解】 设 xi j ( i =1,2,3；j=1,2,3,)为第 i 台机床加工第 j 种 零件的数量，则此问题的数学模型为                                          0, 1,2,3 1,2,3 50 30 70 40 60 50 min 5 2 3 6 4 7 3 4 13 23 33 12 22 32 11 21 31 31 32 33 21 22 23 11 12 13 11 12 13 21 22 23 31 32 33 x i j x x x x x x x x x x x x x x x x x x Z x x x x x x x x x ij ； 机床的生产任务 零件的需求量

典型背景一一单一物资运输调度问题设某种物品有：m个产地:A1，A2..’A,产量: αj,α2.., αmn个销地：B1,B2..’B销量：bi,b2.. bn从产地A,到销地B,的单位运价是Cij。求总运费最小的调度方案

典型背景——单一物资运输调度问题 设某种物品有: m个产地： 产量： n个销地： 销量： 从产地 到销地 的单位运价是 。 求总运费最小的调度方案。 A A A m , ,., 1 2 B B B n , ,., 1 2 a a a m , ,., 1 2 n b , b ,., b 1 2 Ai B j cij

决策变量x；表示由日A,到B，的物品数量。销地B1B2B产地产量.nCulC12CinA1XinXi1X12ai.C22A2C21C2nX2nX21X 22a2..CmlCm2CmmAxaXm1Xm2.mnmmbb1b2销量.n

决策变量 表示由 到 的物品数量。 xij Ai Bj c 11 c 12 c 1 n c 21 c 22 c2 n c m 1 c m 2 c mn n m m m mn m n n n b b b A x x x a A x x x a A x x x a B B B . . . . . . . . 1 2 1 2 2 21 22 2 2 1 11 12 1 1 1 2 销量 产量

产销平衡问题一总产量=总销量mn即Za,=Zbji=1i-1产销不平衡问题总产量总销量

产销平衡问题——总产量=总销量 即 产销不平衡问题——总产量=总销量      n i j m i ai b 1 1

产销平衡问题的数学模型mnZNminZ二Cix1有M+N个约束i=1j=1有MN个变量nZ1,2....mx1j= 1mZ1,2.bxi =n：i=10,i=1,2,..., mxi≥j= 1,2... n

                          j n x i m x b j n x a i m z c x ij j m i ij i n j ij m i n j ij ij 1 , 2 ,. 0 , 1 , 2 ,., , 1 , 2 ,., , 1 , 2 ,., min 1 1 1 1 产销平衡问题的数学模型 有M+N个约束 有MN个变量