第三章运输问题研究生

第三章运输问题,北京物资学院信息学院2010年11月,北京物资学院运筹学教学课件,本章主要内容,第一节运输问题的数学模型及其特征第二节运输问题的求解表上作业法第三节产销不平衡的运输问题及应用,第一节运输问题的数学模型及其特征,运输问题的定义运输问题的数学模型运输问题的特征,1.运输问题的定义,例1：某集团新购进一批钢材，分别存储在三个仓库，现在要将这批钢材运到分布在各地的四个工厂。各仓库的库存量、各工厂的需求量以及从各仓库往各个工厂每运送一吨钢材所需的费用见下表，问如何调运才能使总运费降到最低？,运输问题：有m个供应点向n个需求点供应某种物资，这m个供应点A1、A2、.Am的供应量分别为a1、a2、.am；n个需求点B1、B2、.Bn的需求量分别为b1、b2、.bn；已知从任一供应点Ai向任一需求点Bj运输一个单位物资的费用为cij。问采取什么样的物资调运方案才能使总运费最省？,2.运输问题的数学模型,运输问题的约束方程组系数矩阵及特征,矩阵A是一个m+n行mn列的矩阵，它的秩为m+n-1。运输问题应该有m+n-1个基变量。系数矩阵非常稀疏。xij的系数列向量为：,3.运输问题的特征,特征1：运输问题一定有可行解；特征2：运输问题一定有最优解；特征3：运输问题每一组基对应m+n-1个基变量；特征4：运输问题的m+n-1个基变量构成的变量组不含闭回路；特征5：任意一个非基变量和m+n-1个基变量组成的变量组中必定存在一条并且只存在唯一一条闭回路；特征6：如果运输问题中的供应量和需求量都是整数，则任一基解中各变量的取值也都是整数。,闭回路,定义：凡是能够排列成下列序列的一组变量的集合就称为运输问题的一个闭回路。,并称集合中每一个变量为此闭回路的一个顶点；称连接相邻两个变量（顶点）以及连接最后一个顶点和第一个顶点的线段为此闭回路的边。,或,X45,X41,X31,X33,X13,X15,X34,X32,X14,X12,X35,X41,X31,X43,X13,X15,X11,X12,X22,X24,X44,X42,X21,（1）每个顶点都是转折点；（2）闭回路是一条闭合的折线，每一条边都是水平或垂直的；（3）闭回路上同一行（列）的顶点有偶数个。,闭回路上的点对应的系数列向量线性相关。,Pij,Pik,Plk,Pls,Pus,Puj,由于,容易证明,第二节运输问题的求解-表上作业法,第四步：确定进基变量和出基变量，调整非最优的调运方案，获得更好的调运方案；转第二步。,表上作业法的基本步骤：,第一步：编制初始调运方案，即寻找第一个基可行解；,第二步：计算各非基变量的检验数；,第三步：判断当前的调运方案是否是最优方案，如果已经是最优，则算法结束，问题已经解决；否则，转第四步；,第一步：编制初始调运方案,要求得运输问题的初始基可行解，必须保证找到m+n1个基变量.,运输问题的任意m+n-1个变量构成一组基变量的充要条件是变量组中不含闭回路.关键:找出m+n-1个不含闭回路的变量。,西北角法（左上角法）最小元素法Vogel法,问题：如何使得一个选定的变量不包含在闭回路中？,对应的总运费为C1=23+96+32+43+21+56=110,西北角法(左上角法),最小元素法,对应的总运费为C2=95+74+13+22+43+24=100,Vogel法,对应的总运费为C2=23+95+71+25+43+24=88,退化情况的处理,用西北角法求下列运输问题的第一个基可行解,注意：每次只能划去一行或一列，不能同时划去行和列。当只剩下一行（列）时，只能划去列（行）。想一想：为什么？,用最小元素法求下列运输问题的第一个基可行解,第二步：计算各非基变量的检验数,1.闭回路法；2.位势法。,检验数的定义：非基变量的取值每增加1时，总运费的增加量。运输问题的最优性条件：检验数非负,1.闭回路法,基变量不含闭回路，但任何一个非基变量都可以与基变量构成唯一一条闭回路,含义：x14每增加一个单位，总运费增加-6个单位,+1,+1,+1,-1,-1,-1,所有非基变量的检验数见上表,2.位势法,位势：运输问题的对偶变量称为位势。因为m个供应点n个需求点的运输问题有m+n个约束，因此运输问题就有m+n个位势。,行位势:关于供应点Ai的约束对应的对偶变量，记为ui,i=1,2,m。列位势:关于需求点Bj的约束对应的对偶变量，记为vj,j=1,2,n。,定理：运输问题变量xij的检验数,证明：,位势及检验数的求法,由于基变量的检验数为0，所以可以利用m+n-1个基变量求出位势,0,2,9,-6,10,-8,13,0,-6,5,-5,14,3,第四步：调整调运方案,1.确定入基变量：选取最小负检验数对应的非基变量入基,2.确定出基变量和调整量,将进基变量对应的闭回路中的顶点分为奇顶点和偶顶点，令=min闭回路上所有偶顶点对应的运量xij则即为调整量，选取一个运量等于的偶顶点为出基变量。,3.调整：闭回路上奇顶点上的运量增加，偶顶点上的运量减少。闭回路以外顶点的运量不变。,上例中：若选x14进基，则=min6,3,6=3,出基变量为x23,调整后得：,总运费：C=23+93+73+35+24+53=92110,x32进基，则=min3,3=3,出基变量选x34,调整后得：,0,-6,-2,2,9,4,7,5,6,6,1,8,-3,检验数全部非负，已经是最优调运方案；总费用C*=23+90+76+35+43+24=83,0,-6,-5,2,9,7,7,3,5,3,1,11,3,表上作业法计算中应注意的问题,1.解的情况唯一：非基变量检验数全部大于0；无穷多解：至少存在一个非基变量检验数等于0。,2.退化情况：在确定初始基可行解的时候，当填(i,j)格子时，若ai=bj,则xij=ai=bj,但此时只能划去一行或一列，在后面的填充过程中相应格子要填0。,3.调整时，若闭回路上出现两个或两个以上偶顶点取值同时达到最小，只能选一个变量出基。,课堂练习用表上作业法求解下列运输问题.,0,3,10,-1,2,-5,9,1,2,1,-1,10,12,调整量为min3,1=1，出基变量为x23.,最优解:,0,3,10,-2,3,-5,9,0,2,2,1,9,12,由于x11的检验数为0，所以最优解不唯一。,0,3,10,-2,3,-5,9,2,2,1,9,12,0,最优解:,第三节产销不平衡的运输问题及应用,表上作业法是以产销平衡为前提的：,实际中，往往遇到产销不平衡的运输问题,1.产大于销（供过于求）,2.销大于产（供不应求）,产销不平衡运输问题向产销平衡运输问题的转化,产大于销的运输问题：,数学模型,设xin+1是产地Ai的储存量，化成标准形,其中,引入一个虚拟的销地（需求量等于），并令各个产地到虚拟销地的单位运费为0。,产小于销的运输问题：,引入一个虚拟的产地（产量等于），并令该虚拟产地到各销地的单位运费为0。,总供应量为19千吨，而总需求量为15千吨,例2：A1、A2、A3三个蔬菜生产地生产的蔬菜主要供应B1、B2、B3、B4四个城市。已知三个产地今年的蔬菜产量预计分别为7千吨、5千吨和7千吨；四个城市今年的蔬菜需求量分别为2千吨、3千吨、4千吨和6千吨；从每个蔬菜产地平均运输1千吨蔬菜到各个城市的单位费用(万元)见下表，你能否替他们编制一个总运费最省的蔬菜调运方案？,0,0,-2,2,0,4,3,0,8,2,5,7,2,3,8,7,最优解中x15=2,x25=2，表示两个产地没有运出去的蔬菜量。,假如例2中各产地的蔬菜总产量不是19千吨，而是12千吨，就成了一个供不应求的运输问题。,引入一个虚拟产地,例3设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同，已知各化肥厂年产量，各地区年需要量及从各个化肥厂到各地区单位化肥的运价如下表所示，试决定使总运费最省的化肥调拨方案。,这是一个产销不平衡的运输问题，总产量160万吨，四个地区的最低需求量为110万吨，最高需求为无限。根据现有产量，第四个地区每年最多能分配到60万吨，这样最高需求为210万吨，大于总产量。为了求得平衡，在产销平衡表中增加一个假想的化肥厂D，其产量为50万吨。由于各个地区的需求量包含两部分，其中最低需求量不能由假想的化肥厂D供应，令运价为M，而另一部分满足或不满足均可以，故也可以由假想的化肥厂供应，令相应运价为0。把需求是两种情况的看成两个地区，得到这个问题的产销平衡表。,根