第三章运输问题 本章主要内容： 运输问题的典例和数学模型 表上作业法 产销不平衡的运输问题 应用举例
第三章 运输问题 运输问题的典例和数学模型 表上作业法 产销不平衡的运输问题 应用举例 本章主要内容：
§1运输问题的典例和数学模型 [例1]某食品公司从三个加工厂A1、A2、A将其生产 的糖果运往四个门市部B1、B2、B3、B销售，各加工 厂每天的生产量、各门市部每天的销售量和各加工厂运 往各门市部每吨糖果的运价如下表所示，问：该食品公 司应如何调运可使总运输费用最小？ Br B2 B B 产量 Ai 3 11 3 10 7 A2 1 9 2 8 A 7 10 5 0 销量 3 6 5 6
§1 运输问题的典例和数学模型 [例1] 某食品公司从三个加工厂A1、A2 、 A3将其生产 的糖果运往四个门市部B1 、B2 、 B3 、 B4销售，各加工 厂每天的生产量、各门市部每天的销售量和各加工厂运 往各门市部每吨糖果的运价如下表所示，问：该食品公 司应如何调运可使总运输费用最小？ B1 B2 B3 B4 产量 A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 销量 3 6 5 6
§1运输问题的典例和数学模型 解：产销平衡问题：总产量=总销量=20 设X为从产地A运往销地B的运输量，得到下列运输量表： B B2 B3 Ba 产量 Xm(3) X2(11) X3(3) X4(10) A2 X21() X22(9) X23(2) X24(8) A X31(7 X32(4) X33(10) X34(5) 销量 3 6 5 6 MinZ=3x11+11x12+3x13+1014+x21+9x22+2x23+8x24+ 7x31+4x32+10x33+5x34 x11+x21+x31=3 S.t.1+X12+X13+x14=7 x12+22+x32=6 21+x22+x23+24=4 x13+23+x33=5 31+32+33+x34=9 七14+24+x34=6 ≥0(i=1,.,3;j=1,4)
§1 运输问题的典例和数学模型 解：产销平衡问题：总产量 = 总销量＝20 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表： Min Z = 3x11+ 11x12+ 3x13 + 10x14 + x21+ 9x22+ 2x23 +8 x24 + 7x31+ 4x32+ 10x33 +5 x34 B1 B2 B3 B4 产量 A1 X11 (3) X12 (11) X13 (3) X14 (10) 7 A2 X21 (1) X22 (9) X23 (2) X24 (8) 4 A3 X31 (7) X32 (4) X33 (10) X34 (5) 9 销量 3 6 5 6 s.t. x11+ x12 + x13 +x14 = 7 x21 + x22+ x23 +x24 = 4 x31 + x32+ x33 +x34 = 9 x11 + x21+ x31=3 x12 + x22 +x32= 6 x13 + x23 +x33= 5 x14 + x24 +x34= 6 xij ≥ 0 ( i = 1 , ., 3；j = 1, .,4）
§1运输问题的典例和数学模型 运输问题的一般形式：产销平衡 AA2、Am表示某物资的m个产地；B1B2、Bn表示 某物资的n个销地；a:表示产地A的产量；b表示销地B,的销量； C表示把物资从产地A运往销地B的单位运价。设x为从产地A: 运往销地B的运输量，得到下列一般运输量问题的模型： min :-22c i=1i=1 ∑xg=a,i=l,m ∑x,=b j=1,.,n xg≥0，i=1,mj=1,n
§1 运输问题的典例和数学模型 运输问题的一般形式：产销平衡 A1、 A2、.、 Am 表示某物资的m个产地； B1、B2、.、Bn 表示 某物资的n个销地；ai 表示产地Ai的产量； bj 表示销地Bj 的销量； cij 表示把物资从产地Ai运往销地Bj的单位运价。设 xij 为从产地Ai 运往销地Bj的运输量，得到下列一般运输量问题的模型： m i n j i j xi j z c 1 1 min x i m j n x b j n x a i m s t ij j m i ij n j ij i 0, 1, , ; 1, , 1, , 1, , . 1 1
§1运输问题的典例和数学模型 变化： )有时目标函数求最大。如求利润最大或营业额最大等； 2)当某些运输线路上的能力有限制时，在模型中直接加入 约束条件（等式或不等式约束）； 3)产销不平衡时，可加入假想的产地（销大于产时）或销 地（产大于销时）。 定理：设有m个产地n个销地且产销平衡的运输问题，则基变 量数为m+n-1
§1 运输问题的典例和数学模型 变化： 1）有时目标函数求最大。如求利润最大或营业额最大等； 2）当某些运输线路上的能力有限制时，在模型中直接加入 约束条件（等式或不等式约束)； 3）产销不平衡时，可加入假想的产地（销大于产时）或销 地（产大于销时）。 定理: 设有m个产地n个销地且产销平衡的运输问题，则基变 量数为m+n-1
§1运输问颗的典例和数学模型 学习要点： 1.掌握运输问题模型结构； 2.了解运输问题模型特点
学习要点： 1.掌握运输问题模型结构； 2.了解运输问题模型特点。 §1 运输问题的典例和数学模型
§2表上作业法 表上作业法是一种求解运输问题的特殊方法，其实质是单 纯形法。 步骤 描述 方法 第一步 求初始基本可行解（初始调运方案） 最小元素法、 元素差额法、 求检验数并判断是否得到最优解当非基变 闭回路法和位 第二步 量的检验数σ全都非负时得到最优解，若 存在检验数σ，<0，说明还没有达到最优， 势法 转第三步。 调整运量，即换基，选一个变量出基，对 第三步 原运量进行调整得到新的基可行解，转入 第二步
§2 表上作业法 表上作业法是一种求解运输问题的特殊方法，其实质是单 纯形法。 步骤 描述 方法 第一步 求初始基本可行解（初始调运方案） 最小元素法、 元素差额法、 第二步 求检验数并判断是否得到最优解当非基变 量的检验数σij全都非负时得到最优解，若 存在检验数σij <0，说明还没有达到最优， 转第三步。 闭回路法和位 势法 第三步 调整运量，即换基，选一个变量出基，对 原运量进行调整得到新的基可行解，转入 第二步
§2表上作业法 例用表上作业法求解例1中的问题： 单位销地 运价 B B2 B3 B 产量 产地 A 3 11 3 10 7 西 1 9 2 8 4 4 10 5 9 销量 3 6 5 6 问：应如何调运可使总运输费用最小？
§2 表上作业法 例 用表上作业法求解例1中的问题： 单位 销地 运价 产地 产量 3 11 3 10 7 1 9 2 8 4 7 4 10 5 9 销量 3 6 5 6 1 2 3 4 B B B B 3 2 1 A A A 问：应如何调运可使总运输费用最小？
§2表上作业法 解：第1步求初始方案一 方法1：最小元素法 基本思想是就近供应，即从运价最小的地方开始供应（调 运)，然后次小，直到最后供完为止。 B B2 B 产量 A 7 3 4 A3 9 销量 3 6 5 6 总的运输费=3×1)+(6×4)+(4×3)+(1×2)+(3×10)+(3×5)=86元
§2 表上作业法 解：第1步 求初始方案 —— 方法1：最小元素法 基本思想是就近供应，即从运价最小的地方开始供应（调 运），然后次小，直到最后供完为止。 B1 B2 B3 B4 产量 A1 7 A2 4 A3 9 销量 3 6 5 6 3 11 3 10 1 9 2 7 4 10 5 8 3 4 1 6 3 3 总的运输费＝(3×1)+(6×4) +(4×3) +(1×2)+(3×10)+(3×5)=86元
§2表上作业法 方法2：Vogel法（元素差额法） 1)从运价表中分别计算出各行和各列的最小运费和次最小运 费的差额，并填入该表的最右列和最下行。 Br B2 B B 产量 行差额 11 10 7 A2 2 8 A3 10 5 9 销量 3 6 5 6 列差额 2 5 3
§2 表上作业法 方法2：Vogel法（元素差额法） 1）从运价表中分别计算出各行和各列的最小运费和次最小运 费的差额，并填入该表的最右列和最下行。 B1 B2 B3 B4 产量 行差额 A1 7 0 A2 4 1 A3 9 1 销量 3 6 5 6 列差额 2 5 1 3 3 11 3 10 1 9 2 7 4 10 5 8