《运筹学》课程教学资源（课件讲稿）第三章 运输问题

第三章运输问题 本章主要内容： 运输问题的典例和数学模型 表上作业法 产销不平衡的运输问题 应用举例

第三章 运输问题 运输问题的典例和数学模型 表上作业法 产销不平衡的运输问题 应用举例 本章主要内容：

§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表上作业法 表上作业法是一种求解运输问题的特殊方法，其实质是单 纯形法。 步骤 描述 方法 第一步 求初始基本可行解（初始调运方案） 最小元素法、 元素差额法、 求检验数并判断是否得到最优解当非基变 闭回路法和位 第二步 量的检验数σ全都非负时得到最优解，若 存在检验数σ

§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