运输问题剖析

1、运输问题剖析 第三章第三章 运输问题运输问题 运输问题剖析 本章主要内容本章主要内容 第一节第一节 运输问题的数学模型及其特征运输问题的数学模型及其特征 第二节第二节 运输问题的求解运输问题的求解表上作业法表上作业法 第三节第三节 产销不平衡的运输问题及应用产销不平衡的运输问题及应用 运输问题剖析 第一节第一节 运输问题的数学模型及其特征运输问题的数学模型及其特征 运输问题的定义运输问题的定义 运输问题的数学模型运输问题的数学模型 运输问题的特征运输问题的特征 运输问题剖析 1. 1. 运输问题的定义运输问题的定义 例例1 1： 某集团新购进一批钢材，分别存储在三个仓库，现在某集团新购进一批钢

2、材，分别存储在三个仓库，现在 要将这批钢材运到分布在各地的四个工厂。各仓库的库存量、要将这批钢材运到分布在各地的四个工厂。各仓库的库存量、 各工厂的需求量以及从各仓库往各个工厂每运送一吨钢材所各工厂的需求量以及从各仓库往各个工厂每运送一吨钢材所 需的费用见下表，问如何调运才能使总运费降到最低？需的费用见下表，问如何调运才能使总运费降到最低？ 工厂工厂 B1 工厂工厂 B2 工厂工厂 B3 工厂工厂 B4 库存量库存量 仓库仓库A1291079 仓库仓库A213425 仓库仓库A384257 需求量需求量3846 运输问题剖析 运输问题：有运输问题：有m个供应点向个供应点向n个需求点供应某种物资

3、，这个需求点供应某种物资，这m个个 供应点供应点A1、A2、.Am的供应量分别为的供应量分别为a1、a2、.am；n个个 需求点需求点B1、B2、.Bn的需求量分别为的需求量分别为b1、b2、.bn；已知已知 从任一供应点从任一供应点Ai向任一需求点向任一需求点Bj运输一个单位物资的费用为运输一个单位物资的费用为 cij。问采取什么样的物资调运方案才能使总运费最省？问采取什么样的物资调运方案才能使总运费最省？ B1B2Bn供应量供应量 A1c11c12c1na1 A2c21c22c2na2 Amcm1cm2cmnam 需求量需求量b1b2bn 运输问题剖析 2. 2. 运输问题的数学模型运输问

4、题的数学模型 11 1 1 min (1,2,.) . .(1,2,. ) 0,1,2,.,1,2,. mn ijij ij n iji j m ijj i ij zc x xaim s txbjn xim jn 11 mn ij ij ab （其其中中） 运输问题剖析 运输问题的约束方程组系数矩阵及特征运输问题的约束方程组系数矩阵及特征 111212122212 11.1 11.1 . 11.1 111 11. . .1 111 nnmmmn xxxxxxxxx A 矩阵矩阵A是一个是一个m+n行行mn列的矩阵，它的秩不超过列的矩阵，它的秩不超过m+n-1。 运输问题一般有运输问题一般有m+

5、n-1个基变量。个基变量。 系数矩阵非常稀疏。系数矩阵非常稀疏。 xij的系数列向量为：的系数列向量为： m行 n行 (0.1.0.1.0)T ijimj Pee 运输问题剖析 3. 运输问题的特征运输问题的特征 特征特征1：运输问题一定有可行解；运输问题一定有可行解； 特征特征2：运输问题一定有最优解；运输问题一定有最优解； 特征特征3：运输问题每一组基对应运输问题每一组基对应 m+n-1个基变量；个基变量； 特征特征4：运输问题的运输问题的 m+n-1个基变量构成的变量组不含个基变量构成的变量组不含 闭回路闭回路； 特征特征5：任意一个非基变量和任意一个非基变量和 m+n-1个基变量组成的

6、变个基变量组成的变 量组中必定存在一条并且只存在唯一一条闭回路；量组中必定存在一条并且只存在唯一一条闭回路； 特征特征6：如果运输问题中的供应量和需求量都是整数，如果运输问题中的供应量和需求量都是整数， 则任一基解中各变量的取值也都是整数。则任一基解中各变量的取值也都是整数。 运输问题剖析 闭回路闭回路 定义：凡是能够排列成下列序列的一组变量的集合就定义：凡是能够排列成下列序列的一组变量的集合就 称为运输问题的一个闭回路。称为运输问题的一个闭回路。 1 12 12 23 21 , s ss i ji ji ji ji ji j xxxxxx 并称集合中每一个变量为此闭回路的一个顶点；称连并称集

7、合中每一个变量为此闭回路的一个顶点；称连 接相邻两个变量（顶点）以及连接最后一个顶点和第接相邻两个变量（顶点）以及连接最后一个顶点和第 一个顶点的线段为此闭回路的边一个顶点的线段为此闭回路的边。 或或 1 11 22 22 31 , s ss i ji ji ji ji ji j xxxxxx 运输问题剖析 B1B2B3B4B5 A1 A2 A3 A4 X45 X41 X31X33 X13X15 运输问题剖析 B1B2B3B4B5 A1 A2 A3 A4 X34 X32 X14X12 运输问题剖析 B1B2B3B4B5 A1 A2 A3 A4 X35 X41 X31 X43 X13X15 运输

8、问题剖析 B1B2B3B4B5 A1 A2 A3 A4 X11X12 X22X24 X44X42 X21 （1 1）每个顶点都是转折点；）每个顶点都是转折点； （2 2）闭回路是一条闭合的折线，每一条边都是水）闭回路是一条闭合的折线，每一条边都是水 平或垂直的；平或垂直的； （3 3）闭回路上同一行（列）的顶点有偶数个。）闭回路上同一行（列）的顶点有偶数个。 运输问题剖析 闭回路上的点对应的系数列向量线性相关。闭回路上的点对应的系数列向量线性相关。 Pij Pik PlkPls Pus Puj ijimj Pee 0 ijiklklsusuj PPPPPP 由于由于 容易证明容易证明 运输问题

9、剖析 第二节第二节 运输问题的求解运输问题的求解-表上作业法表上作业法 第四步：确定进基变量和出基变量，调整非最优的调运第四步：确定进基变量和出基变量，调整非最优的调运 方案，获得更好的调运方案；方案，获得更好的调运方案；转第二步。转第二步。 表上作业法的基本步骤：表上作业法的基本步骤： 第一步：编制初始调运方案，即寻找第一个基可行解第一步：编制初始调运方案，即寻找第一个基可行解； 第二步：计算各非基变量的检验数；第二步：计算各非基变量的检验数； 第三步：判断当前的调运方案是否是最优方案，如果已经第三步：判断当前的调运方案是否是最优方案，如果已经 是最优，则算法结束，问题已经解决；否则，转第四

10、步；是最优，则算法结束，问题已经解决；否则，转第四步； 运输问题剖析 第一步：编制初始调运方案第一步：编制初始调运方案 要求得运输问题的初始基可行解，必须保证找到要求得运输问题的初始基可行解，必须保证找到 m+n1 个基变量个基变量. 运输问题的任意运输问题的任意m+n-1个变量构成一组基变量的充要条个变量构成一组基变量的充要条 件是变量组中不含闭回路件是变量组中不含闭回路. 关键关键:找出找出m+n-1个不含闭回路的变量。个不含闭回路的变量。 西北角法（左上角法）西北角法（左上角法） 最小元素法最小元素法 Vogel 法法 问题：如何使得一个选定的变量不包含在闭回路中？问题：如何使得一个选定

11、的变量不包含在闭回路中？ 运输问题剖析 B1B2B3B4库存量库存量 A1291079 A213425 A384257 需求量需求量3846 6 2 3 1 6 3 对应的总运费为对应的总运费为 C 1= 23 + 93 + 96 + 36 + 32 + 42 + 43 + 23 + 21 + 51 + 56 = 1106 = 110 西北角法西北角法( (左上角法左上角法) ) -3 -3 -6 -6 -2 -2 -3 -3 -1 -1 -6 -6 运输问题剖析 最小元素最小元素法法 B1B2B3B4库存量库存量 A1291079 A213425 A384257 需求量需求量3846 5 2

12、 34 4 3 对应的总运费为对应的总运费为 C 2= 95 + 75 + 74 + 14 + 13 + 23 + 22 + 42 + 43 + 23 + 24 = 1004 = 100 -3 -3 -4 -4 -2 -2-3 -3 -4 -4 -5 -5 运输问题剖析 Vogel 法法 B1B2B3B4库存量库存量 A1291079 A213425 A384257 需求量需求量3846 1 5 4 5 3 3 对应的总运费为对应的总运费为 C 2= 23 + 93 + 95 + 75 + 71 + 21 + 25 + 45 + 43 + 23 + 24 =884 =88 -3 -3 -1 -

13、1 -5 -5 -3 -3 -5 -5 -4 -4 运输问题剖析 B1B2B3B4供应量供应量 A178143 A226535 A314278 需求量需求量2176 1 0 5 2 6 2 退化情况的处理退化情况的处理 -2 -2 -1 -1 -5 -5 -2 -2 -6 -6 用西北角法求下列运输问题的第一个基可行解用西北角法求下列运输问题的第一个基可行解 运输问题剖析 B1B2B3供应量供应量 A11842 A25251 A35737 需求量需求量217 1 7 2 -2 -2 -1 -1 -7 -7 注意：每次只能划去一行或一列，不能同时划去行和列。注意：每次只能划去一行或一列，不能同时

14、划去行和列。 当只剩下一行（列）时，只能划去列（行）。当只剩下一行（列）时，只能划去列（行）。 想一想：为什么？想一想：为什么？ 0 0 用最小元素法求下列运输问题的第一个基可行解用最小元素法求下列运输问题的第一个基可行解 运输问题剖析 第二步：计算各非基变量的检验数第二步：计算各非基变量的检验数 1. 1. 闭回路法闭回路法； 2. 2. 位势法位势法。 检验数的定义：非基变量的取值每增加检验数的定义：非基变量的取值每增加1 1时，总运费的时，总运费的 增加量。增加量。 运输问题的最优性条件：检验数非负运输问题的最优性条件：检验数非负 运输问题剖析 1. 1. 闭回路法闭回路法 基变量不含闭

15、回路，但任何一个非基变量都可以与基变基变量不含闭回路，但任何一个非基变量都可以与基变 量构成唯一一条闭回路量构成唯一一条闭回路 B1B2B3B4库存量库存量 A1291079 A213425 A384257 需求量需求量3846 6 2 3 1 6 3 14141222233334 7934256cccccc 含义：含义：x14 每增加一个单位，总运费增加每增加一个单位，总运费增加-6个单位个单位 +1 +1 +1 -1 -1 -1 运输问题剖析 6 2 3 16 3 所有非基变量的检验数见上表所有非基变量的检验数见上表 B1B2B3B4库存量库存量 A1291079 0-6 A213425

16、5-5 A384257 143 需求需求 量量 3846 运输问题剖析 2. 2. 位势法位势法 位势：运输问题的对偶变量称为位势。位势：运输问题的对偶变量称为位势。 因为因为m个供应点个供应点n个需求点的运输问题有个需求点的运输问题有m+n个约束，个约束， 因此运输问题就有因此运输问题就有m+n个位势。个位势。 行位势行位势:关于供应点关于供应点Ai的约束对应的对偶变量，记为的约束对应的对偶变量，记为 ui, i=1,2,m。 列位势列位势:关于需求点关于需求点Bj的约束对应的对偶变量，记为的约束对应的对偶变量，记为vj, j = 1,2,n。 运输问题剖析 定理定理：运输问题变量运输问题变

17、量xij的检验数的检验数 ijijij cuv 1 11 0 1 (,.,.) 1 0 ijijBijijmnijij cC B Pcuuvvcuv 证明：证明： 运输问题剖析 位势及检验数的求法位势及检验数的求法 由于基变量的检验数为由于基变量的检验数为0，所以可以利用，所以可以利用m+n-1 个基变个基变 量求出位势量求出位势 B1B2B3B4库存量库存量 A1291079 A213425 A384257 需求量需求量3846 6 23 16 3 0 29 -6 10 -8 13 0 -6 5-5 143 运输问题剖析 第四步：调整调运方案第四步：调整调运方案 1. 1. 确定入基变量：选

18、取最小负检验数对应的非基变量确定入基变量：选取最小负检验数对应的非基变量 入基入基 2. 2. 确定出基变量和调整量确定出基变量和调整量 将进基变量对应的闭回路中的顶点分为奇顶点和偶顶点，将进基变量对应的闭回路中的顶点分为奇顶点和偶顶点， 令令= min 闭回路上所有偶顶点对应的运量闭回路上所有偶顶点对应的运量xij 则则即为调即为调 整量，选取一个运量等于整量，选取一个运量等于的偶顶点为出基变量。的偶顶点为出基变量。 3.调整：闭回路上奇顶点上的运量增加调整：闭回路上奇顶点上的运量增加，偶顶点上的运偶顶点上的运 量减少量减少。闭回路以外顶点的运量不变。闭回路以外顶点的运量不变。 运输问题剖析

19、 上例中：若选上例中：若选x14进基，进基， 则则 =min6,3,6=3, 出基变量为出基变量为x23,调整后得：调整后得： B1B2B3B4库存库存 量量 A1291079 0-6 A213425 5-5 A384257 143 需求量需求量3846 6 23 16 3 运输问题剖析 总运费：总运费： C = 23 + 93 + 73 + 35 + 24 + 53 = 92 110 x32进基，则进基，则 =min3,3=3, 出基变量选出基变量选x34,调整调整 后得：后得： B1B2B3B4库存量库存量 A1291079 A213425 A384257 需求需求 量量 3846 3 5

20、 43 33 0 -6 -2 2947 5 6 6 1 8-3 运输问题剖析 检验数全部非负，已经是最优调运方案；检验数全部非负，已经是最优调运方案； 总费用总费用 C*= 23 + 90 + 76 + 35 + 43 + 24 = 83 B1B2B3B4库存量库存量 A1291079 A213425 A384257 需求量需求量3846 0 5 43 36 0 -6 -5 29 77 3 5 31 113 运输问题剖析 表上作业法计算中应注意的问题表上作业法计算中应注意的问题 1.1.解的情况解的情况 唯一：非基变量检验数全部大于唯一：非基变量检验数全部大于0 0； 无穷多解：至少存在一个非

21、基变量检验数等于无穷多解：至少存在一个非基变量检验数等于0 0。 2.退化情况：退化情况： 在确定初始基可行解的时候，当填在确定初始基可行解的时候，当填(i,j)格子时，格子时， 若若ai=bj, 则则xij=ai=bj, 但此时只能划去一行或一列，但此时只能划去一行或一列， 在后面的填充过程中相应格子要填在后面的填充过程中相应格子要填0。 3.调整时，若闭回路上出现两个或两个以上偶顶点调整时，若闭回路上出现两个或两个以上偶顶点 取值同时达到最小，只能选一个变量出基。取值同时达到最小，只能选一个变量出基。 运输问题剖析 课堂练习课堂练习 用表上作业法求解下列运输问题用表上作业法求解下列运输问题

22、. . B1B2B3B4供应量供应量 A13113107 A219284 A3741059 需求量需求量3656 运输问题剖析 B1B2B3B4供应量供应量 A13113107 A219284 A3741059 需求量需求量 3656 4 31 36 3 运输问题剖析 B1B2B3B4供应量供应量 A13113107 A219284 A3741059 需求量需求量 3656 4 31 36 3 0 310 -1 2 -5 9 12 1-1 10 12 调整量为调整量为 min3,1=1，出基变量为出基变量为x23. 运输问题剖析 B1B2B3B4供应量供应量 A13113107 A219284

23、 A3741059 需求量需求量 3656 5 3 1 36 2 最优解最优解: : 131421243234 5,2,3,1,6,3,0 3 510 21 38 14 65 385 ij xxxxxxx f 其其余余 总总费费用用 0 310 -2 3 -5 9 02 21 912 由于由于x11的检验数为的检验数为0，所以最优解不唯一。，所以最优解不唯一。 运输问题剖析 B1B2B3B4供应量供应量 A13113107 A219284 A3741059 需求量需求量 3656 5 1 3 36 2 0 310 -2 3 -5 9 2 21 912 0 最优解最优解: : 111321243

24、234 2,5,1,3,6,3,0 3 23 51 18 34 65 385 ij xxxxxxx f 其其余余 总总费费用用 运输问题剖析 第三节第三节 产销不平衡的运输问题及应用产销不平衡的运输问题及应用 表上作业法是以产销平衡为前提的：表上作业法是以产销平衡为前提的： 11 mn ij ij ab 实际中，往往遇到产销不平衡的运输问题实际中，往往遇到产销不平衡的运输问题 1.1.产大于销（供过于求）产大于销（供过于求） 11 mn ij ij ab 2.2.销大于产（供不应求）销大于产（供不应求） 11 mn ij ij ab 运输问题剖析 产销不平衡运输问题向产销平衡运输问题的转化产销

25、不平衡运输问题向产销平衡运输问题的转化 产大于销的运输问题：产大于销的运输问题： 11 mn ij ij ab 11 1 1 min (1,2,.) . .(1,2,. ) 0,1,2,.,1,2,. mn ijij ij n iji j m ijj i ij zc x xaim s txbjn xim jn 数学模型数学模型 运输问题剖析 设设xi, n+1 是产地是产地Ai 的库存量，化成标准形的库存量，化成标准形 1 11 1 1 1 min (1,2,.) . .(1,2,. ,1) 0,1,2,.,1,2,.1 mn ijij ij n iji j m ijj i ij zc x x

26、aim s txbjn n xim jn 其中其中 ,1 1 11 0,1,. i n mn nij ij cim bab 引入一个虚拟的销地引入一个虚拟的销地B Bn+1 n+1（需求量等于 （需求量等于 ），）， 并令各个产地到该虚拟销地的单位运费并令各个产地到该虚拟销地的单位运费c ci,n+1 i,n+1=0 =0。 11 mn ij ij ab 运输问题剖析 产小于销的运输问题：产小于销的运输问题： 11 mn ij ij ab 引入一个虚拟的产地（产量等于引入一个虚拟的产地（产量等于 ），）， 并令该虚拟产地到各销地的单位运费为并令该虚拟产地到各销地的单位运费为0 0。 11 nm

27、 ji ji ba 运输问题剖析 总供应量为总供应量为1919千吨，而总需求量为千吨，而总需求量为1515千吨千吨 例例2： A1、A2、A3三个蔬菜生产地生产的蔬菜主要供应三个蔬菜生产地生产的蔬菜主要供应B1、 B2、B3、B4四个城市。已知三个产地今年的蔬菜产量预计分四个城市。已知三个产地今年的蔬菜产量预计分 别为别为7千吨、千吨、5千吨和千吨和7千吨；四个城市今年的蔬菜需求量分别千吨；四个城市今年的蔬菜需求量分别 为为2千吨、千吨、3千吨、千吨、4千吨和千吨和6千吨；从每个蔬菜产地平均运输千吨；从每个蔬菜产地平均运输1 千吨蔬菜到各个城市的单位费用千吨蔬菜到各个城市的单位费用(万元万元)

28、见下表，你能否替他见下表，你能否替他 们编制一个总运费最省的蔬菜调运方案？们编制一个总运费最省的蔬菜调运方案？ 单位运费单位运费 B1B2B3B4 供应量供应量 A1211347 A2103595 A378127 需求量需求量 2346 运输问题剖析 需求地需求地 生产地生产地 B1B2B3B4B5供应量供应量 A12113407 A21035905 A3781207 需求量需求量23464 0 0 -2 2043 0 8 25 7 2 3 3 4 3 2 2 2 3 8 7 最优解中最优解中x15=2, x25=2，表示两个产地没有运出去的蔬菜量。表示两个产地没有运出去的蔬菜量。 运输问题剖析 另：假如例另：假如例2 2中各产地的蔬菜总产量不是中各产地的蔬菜总产量不是1919千吨，千吨， 而是而是1212千吨，就成了一个供不应求的运输问题。千吨，就成了一个供不应求的运输问题。 单位运费单位运费 B1B2B3B4 供应量供应量 A1211343 A2103594 A378125 需求量需求量 2346 单位运费单位运费 B