第三章运输问题(研究生)

第三章运输问题北京物资学院信息学院2010年11月北京物资学院运筹学教学课件本章主要内容第一节运输问题的数学模型及其特征第二节运输问题的求解—表上作业法第三节产销不平衡的运输问题及应用第一节运输问题的数学模型及其特征1.运输问题的定义2.运输问题的数学模型3.运输问题的特征1.运输问题的定义例1：某集团新购进一批钢材，分别存储在三个仓库，现在要将这批钢材运到分布在各地的四个工厂。各仓库的库存量、各工厂的需求量以及从各仓库往各个工厂每运送一吨钢材所需的费用见下表，问如何调运才能使总运费降到最低？工厂B1工厂B2工厂B3工厂B4库存量仓库A1291079仓库A213425仓库A384257需求量3846运输问题：有m个供应点向n个需求点供应某种物资，这m个供应点A1、A2、…...Am的供应量分别为a1、a2、…...am；n个需求点B1、B2、…...Bn的需求量分别为b1、b2、…...bn；已知从任一供应点Ai向任一需求点Bj运输一个单位物资的费用为cij。问采取什么样的物资调运方案才能使总运费最省？B1B2…Bn供应量A1c11c12…c1na1A2c21c22…c2na2………………Amcm1cm2…cmnam需求量b1b2…bn2.运输问题的数学模型1111min(1,2,......)..(1,2,......)0,1,2,......,1,2,......mnijijijnijijmijjiijzcxxaimstxbjnximjn11mnijijab（其中）运输问题的约束方程组系数矩阵及特征11121212221211.......111.......1.........11.......111111............................1111nnmmmnxxxxxxxxxA1.矩阵A是一个m+n行mn列的矩阵，它的秩为m+n-1。2.运输问题应该有m+n-1个基变量。3.系数矩阵非常稀疏。4.xij的系数列向量为：m行n行(0....1...0....1...0)TijimjPee3.运输问题的特征特征1：运输问题一定有可行解；特征2：运输问题一定有最优解；特征3：运输问题每一组基对应m+n-1个基变量；特征4：运输问题的m+n-1个基变量构成的变量组不含闭回路；特征5：任意一个非基变量和m+n-1个基变量组成的变量组中必定存在一条并且只存在唯一一条闭回路；特征6：如果运输问题中的供应量和需求量都是整数，则任一基解中各变量的取值也都是整数。闭回路定义：凡是能够排列成下列序列的一组变量的集合就称为运输问题的一个闭回路。112122321,,,,,,sssijijijijijijxxxxxx并称集合中每一个变量为此闭回路的一个顶点；称连接相邻两个变量（顶点）以及连接最后一个顶点和第一个顶点的线段为此闭回路的边。或111222231,,,,,,sssijijijijijijxxxxxxB1B2B3B4B5A1A2A3A4X45X41X31X33X13X15B1B2B3B4B5A1A2A3A4X34X32X14X12B1B2B3B4B5A1A2A3A4X35X41X31X43X13X15B1B2B3B4B5A1A2A3A4X11X12X22X24X44X42X21（1）每个顶点都是转折点；（2）闭回路是一条闭合的折线，每一条边都是水平或垂直的；（3）闭回路上同一行（列）的顶点有偶数个。闭回路上的点对应的系数列向量线性相关。PijPikPlkPlsPusPujijimjPee0ijiklklsusujPPPPPP由于容易证明第二节运输问题的求解--表上作业法第四步：确定进基变量和出基变量，调整非最优的调运方案，获得更好的调运方案；转第二步。表上作业法的基本步骤：第一步：编制初始调运方案，即寻找第一个基可行解；第二步：计算各非基变量的检验数；第三步：判断当前的调运方案是否是最优方案，如果已经是最优，则算法结束，问题已经解决；否则，转第四步；第一步：编制初始调运方案要求得运输问题的初始基可行解，必须保证找到m+n–1个基变量.运输问题的任意m+n-1个变量构成一组基变量的充要条件是变量组中不含闭回路.关键:找出m+n-1个不含闭回路的变量。1西北角法（左上角法）2最小元素法3Vogel法问题：如何使得一个选定的变量不包含在闭回路中？B1B2B3B4库存量A1291079A213425A384257需求量3846623163对应的总运费为C1=2×3+9×6+3×2+4×3+2×1+5×6=110西北角法(左上角法)-3-3-6-6-2-2-3-3-1-1-6-6最小元素法B1B2B3B4库存量A1291079A213425A384257需求量3846523443对应的总运费为C2=9×5+7×4+1×3+2×2+4×3+2×4=100-3-3-4-4-2-2-3-3-4-4-5-5Vogel法B1B2B3B4库存量A1291079A213425A384257需求量3846154533对应的总运费为C2=2×3+9×5+7×1+2×5+4×3+2×4=88-3-3-1-1-5-5-3-3-5-5-4-4B1B2B3B4供应量A178143A226535A314278需求量2176105262退化情况的处理-2-2-1-1-5-5-2-2-6-6用西北角法求下列运输问题的第一个基可行解B1B2B3供应量A11842A25251A35737需求量217172-2-2-1-1-7-7注意：每次只能划去一行或一列，不能同时划去行和列。当只剩下一行（列）时，只能划去列（行）。想一想：为什么？00用最小元素法求下列运输问题的第一个基可行解第二步：计算各非基变量的检验数1.闭回路法；2.位势法。检验数的定义：非基变量的取值每增加1时，总运费的增加量。运输问题的最优性条件：检验数非负1.闭回路法基变量不含闭回路，但任何一个非基变量都可以与基变量构成唯一一条闭回路B1B2B3B4库存量A1291079A213425A384257需求量3846623163141412222333347934256cccccc含义：x14每增加一个单位，总运费增加-6个单位+1+1+1-1-1-1623163所有非基变量的检验数见上表B1B2B3B4库存量A12910790-6A2134255-5A384257143需求量38462.位势法位势：运输问题的对偶变量称为位势。因为m个供应点n个需求点的运输问题有m+n个约束，因此运输问题就有m+n个位势。行位势:关于供应点Ai的约束对应的对偶变量，记为ui,i=1,2,…m。列位势:关于需求点Bj的约束对应的对偶变量，记为vj,j=1,2,…,n。定理：运输问题变量xij的检验数ijijijcuv11101(,...,,...)10ijijBijijmnijijcCBPcuuvvcuv证明：位势及检验数的求法由于基变量的检验数为0，所以可以利用m+n-1个基变量求出位势B1B2B3B4库存量A1291079A213425A384257需求量3846623163029-610-8130-65-5143第四步：调整调运方案1.确定入基变量：选取最小负检验数对应的非基变量入基2.确定出基变量和调整量将进基变量对应的闭回路中的顶点分为奇顶点和偶顶点，令θ=min{闭回路上所有偶顶点对应的运量xij}则θ即为调整量，选取一个运量等于θ的偶顶点为出基变量。3.调整：闭回路上奇顶点上的运量增加θ，偶顶点上的运量减少θ。闭回路以外顶点的运量不变。上例中：若选x14进基，则=min{6,3,6}=3,出基变量为x23,调整后得：B1B2B3B4库存量A12910790-6A2134255-5A384257143需求量3846623163总运费：C=2×3+9×3+7×3+3×5+2×4+5×3=92110x32进基，则=min{3,3}=3,出基变量选x34,调整后得：B1B2B3B4库存量A1291079A213425A384257需求量38463543330-6-2294756618-3检验数全部非负，已经是最优调运方案；总费用C*=2×3+9×0+7×6+3×5+4×3+2×4=83B1B2B3B4库存量A1291079A213425A384257需求量38460543360-6-529773531113表上作业法计算中应注意的问题1.解的情况唯一：非基变量检验数全部大于0；无穷多解：至少存在一个非基变量检验数等于0。2.退化情况：在确定初始基可行解的时候，当填(i,j)格子时，若ai=bj,则xij=ai=bj,但此时只能划去一行或一列，在后面的填充过程中相应格子要填0。3.调整时，若闭回路上出现两个或两个以上偶顶点取值同时达到最小，只能选一个变量出基。课堂练习用表上作业法求解下列运输问题.B1B2B3B4供应量A13113107A219284A3741059需求量3656B1B2B3B4供应量A13113107A219284A3741059需求量3656431363B1B2B3B4供应量A13113107A219284A3741059需求量36564313630310-12-59121-11012调整量为min{3,1}=1，出基变量为x23.B1B2B3B4供应量A13113107A219284A3741059需求量3656531362最优解:1314212432345,2,3,1,6,3,0351021381465385ijxxxxxxxz其余总费用0310-23-590221912由于x11的检验数为0，所以最优解不唯一。B1B2B3B4供应量A13113107A219284A3741059需求量36565133620310-23-592219120最优解:1113212432342,5,1,3,6,3,032351183465385ijxxxxxxxz其余总费用第三节产销不平衡的运输问题及应用表上作业法是以产销平衡为前提的：11mnijijab实际中，往往遇到产销不平衡的运输问题1.产大于销（供过于求）11mnijijab2.销大于产（供不应求）11mnijijab产销不平衡运输问题向产销平衡运输问题的转化产大于销的运输问题：11mnijijab1111min(1,2,......)..(1,2,......)0,1,2,......,1,2,......mnijijijnijijmijjiijzcxxaimstxbjnximjn数学模型设xin+1是产地Ai的储存量，化成标准形111111min(1,2,......)..(1,2,......,1)0,1,2,......,1,2,......1mnijijijnijijmijjiijzcxxaimstxbjnnximjn其中,11110,1,...inmnnijijcimbab引入一个虚拟的销地（需求量等于），并令各个产地到虚拟销地的单位运费为0。11mnijijab产小于销的运输问题：11mnijijab引入一个虚拟的产地（产量等于），并令该虚拟产地到各销地的单位运费为0。11nmjijiba总供应量为19千吨，而总需求量为15千吨例2：A1、A2、A3三个蔬菜生产地生产的蔬菜主要供应B1、B2、B3、B4四个城市。已知三个产地今年的蔬菜产量预计分别为7千吨、5千吨和7千吨；四个城市今年的蔬菜需求量分别