《运筹学》课程教学课件（PPT讲稿）运输问题 Transportation Problem

Chapter3运输规划 (Transportation Problem 本章主要内容： ●运输规划问题的数学模型 ●表上作业法 ·运输问题的应用

Chapter3 运输规划 ( Transportation Problem ) 运输规划问题的数学模型 表上作业法 运输问题的应用 本章主要内容：

运输规划问题的数学模型 Page 2 例3.1某公司从两个产地A1、A2将物品运往三个销地B1,B2, B?,各产地的产量、各销地的销量和各产地运往各销地每件 物品的运费如下表所示，问：应如何调运可使总运输费用最 小？ BI B2 B3 产量 Al 6 4 6 200 A2 6 5 5 300 销量 150 150 200

运输规划问题的数学模型 Page 2 例3.1 某公司从两个产地A1、A2将物品运往三个销地B1 , B2 , B3，各产地的产量、各销地的销量和各产地运往各销地每件 物品的运费如下表所示，问：应如何调运可使总运输费用最 小？ B1 B2 B3 产量 A1 6 4 6 200 A2 6 5 5 300 销量 150 150 200

运输规划问题的数学模型 Page3 解：产销平衡问题：总产量=总销量=500 设x为从产地A运往销地B的运输量，得到下列运输量 表： B1 B2 B3 产量 Al X11 12 X13 200 A2 X21 X22 X23 300 销量 150 150 200 MinC=61t4x12+6x13+6x21+5x22+5x23 s.t.x11+x12+x13=200 x21+x22+x23=300 x11+21=150 x12+x22=150 x13+x23=200 x≥0(i=1、2;j=1、2、3)

运输规划问题的数学模型 Page 3 解：产销平衡问题：总产量= 总销量＝500 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量 表： B1 B2 B3 产量 A1 x11 x12 x13 200 A2 x21 x22 x23 300 销量 150 150 200 Min C = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij ≥ 0 ( i = 1、2；j = 1、2、3）

运输规划问题的数学模型 Page 4 运输问题的一般形式：产销平衡 A1A2、Am表示某物资的m个产地；B1、B2、.、Bn表示 某物质的n个销地；a表示产地A的产量；b;表示销地B的销量； c表示把物资从产地A运往销地B的单位运价。设x为从产地A 运往销地B的运输量，得到下列一般运输量问题的模型： minz= 22x 1=1 2x,-0i=1,m s.t3 2x,=b, j=1,.,n xg≥0，i=1,m;j=1,n

运输规划问题的数学模型 Page 4 运输问题的一般形式：产销平衡 A1、 A2、.、 Am 表示某物资的m个产地； B1、B2、.、Bn表示 某物质的n个销地；ai表示产地Ai的产量； bj 表示销地Bj的销量； cij 表示把物资从产地Ai运往销地Bj的单位运价。设 xij 为从产地Ai 运往销地Bj的运输量，得到下列一般运输量问题的模型： = = = m i n j ij xij 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    

运输规划问题的数学模型 Page 5 变化： 1)有时目标函数求最大。如求利润最大或营业额最大等； 2)当某些运输线路上的能力有限制时，在模型中直接加入 约束条件（等式或不等式约束）； 3)产销不平衡时，可加入假想的产地（销大于产时）或销 地（产大于销时）。 定理：设有个产地n个销地且产销平衡的运输问题，则基变 量数为什n-1

运输规划问题的数学模型 Page 5 变化： 1）有时目标函数求最大。如求利润最大或营业额最大等； 2）当某些运输线路上的能力有限制时，在模型中直接加入 约束条件（等式或不等式约束)； 3）产销不平衡时，可加入假想的产地（销大于产时）或销 地（产大于销时）。 定理: 设有m个产地n个销地且产销平衡的运输问题，则基变 量数为m+n-1

表上作业法 Page 6 表上作业法是一种求解运输问题的特殊方法，其实质是单纯 形法。 步骤 描述 方法 第一步 求初始基行可行解（初始调运方案） 最小元素法、 元素差额法、 求检验数并判断是否得到最优解当非基变量的 第二步 检验数σ]全都非负时得到最优解，若存在检验 闭回路法和位 势法 数¤1<0，说明还没有达到最优，转第三步。 第三步 调整运量，即换基，选一个变量出基，对原运 量进行调整得到新的基可行解，转入第二步

表上作业法 Page 6 表上作业法是一种求解运输问题的特殊方法，其实质是单纯 形法。 步骤 描述 方法 第一步 求初始基行可行解（初始调运方案） 最小元素法、 元素差额法、 第二步 求检验数并判断是否得到最优解当非基变量的 检验数σij全都非负时得到最优解，若存在检验 数σij <0，说明还没有达到最优，转第三步。 闭回路法和位 势法 第三步 调整运量，即换基，选一个变量出基，对原运 量进行调整得到新的基可行解，转入第二步

表上作业法 Page7 例3.2某运输资料如下表所示： 单位销地 运价 B B2 B Ba 产量 产地 41 3 11 3 10 7 A 1 9 2 8 4 A 7 4 10 5 9 销量 3 6 5 6 问：应如何调运可使总运输费用最小？

表上作业法 Page 7 例3.2 某运输资料如下表所示： 单位 销地 运价 产地 产量 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 问：应如何调运可使总运输费用最小？

表上作业法 Page 8 解：第1步求初始方案 方法1：最小元素法 基本思想是就近供应，即从运价最小的地方开始供应（调 运)，然后次小，直到最后供完为止。 B B B, Ba 产量 A 4 3 7 3 11 3 10 A2 3 4 1 9 2 8 A3 6 3 9 4 10 5 销量 6

表上作业法 Page 8 解：第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

表上作业法 Page 9 总的运输费=(3×1)+(6×4)+(4×3)+(1×2)+(3×10)+(3×5)=86元 元素差额法对最小元素法进行了改进，考虑到产地到销 地的最小运价和次小运价之间的差额，如果差额很大，就选最 小运价先调运，否则会增加总运费。例如下面两种运输方案。 10 10 最小元素法： 5 15 2 20 15 15 总运费是=10×8+5×2+15×1=105

表上作业法 Page 9 总的运输费＝(3×1)+(6×4) +(4×3) +(1×2)+(3×10)+(3×5)=86元 元素差额法对最小元素法进行了改进，考虑到产地到销 地的最小运价和次小运价之间的差额，如果差额很大，就选最 小运价先调运，否则会增加总运费。例如下面两种运输方案。 8 5 10 2 1 20 15 15 5 15 10 总运费是z=10×8+5×2+15×1=105 最小元素法：

表上作业法 Page 10 后一种方案考虑到C1与C21之间 10 的差额是8-2-6，如果不先调运 8 10 x21,到后来就有可能x10,这 15 5 20 样会使总运费增加较大，从而先 调运x21,再是x22,其次是x12 15 15 总运费z=10×5+15×2+5×1=85 用元素差额法求得的基本可行解更接近最优解，所 以也称为近似方案

表上作业法 Page 10 8 5 10 2 1 20 15 15 15 5 10 总运费z=10×5+15×2+5×1=85 后一种方案考虑到C11与C21之间 的差额是8－2=6，如果不先调运 x21，到后来就有可能x11≠0，这 样会使总运费增加较大，从而先 调运x21，再是x22，其次是x12 用元素差额法求得的基本可行解更接近最优解，所 以也称为近似方案