2.4运输问题(修改)解析

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,返回总目录,第2.4节 运输问题,一、运输问题的数学模型,二、表上作业法,三、产销不平衡的运输问题及其求解方法,1,例1 某公司经销甲产品。它下设三个加工厂。每日的产量分别是：A1为7吨，A2为4吨，A3为9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为：B1为3吨，B2为6吨，B3为5吨，B4为6吨。从各工厂到各销售点的单位产品的运价。问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。,单位运价表,产销平衡表,2,一,、,运输问题的数学模型,有m个生产地点 Ai,i=1,2,，m。可供给某种物资，其供给量(产量)分别为：ai，i=1，2，m,有n个销地 Bj，j=1,2,n，其需要量分别为：bj，j=1,2,n,从 Ai 到 Bj 运输单位物资的运价(单价)为：cij,这些数据可汇总于产销平衡表和单位运价表中，见下表。有时可把这两表合二为一。,销地,产地,1 2 n,产量,1,2,m,a,1,a,2,a,m,销量,b,1,b,2,b,n,3,假设用 xij 表示从 Ai 到 Bj 的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案的数学模型为：,4,一、运输问题的数学模型,这就是运输问题的数学模型。它包含mn个变量，(m+n)个约束方程，其系数矩阵的构造比较松散，且特殊。,5,一，运输问题的数学模型,该系数矩阵中对应于变量 xij 的系数向量Pij，其重量中除第i个和第m+j个为1以外，其余的都为零。即,Pij=(0,1,0,0,1,0,0)T=ei+em+j,对产销平衡的运输问题，由于有以下关系式存在：,运输问题是否确定有解？(见后面),运输问题的基变量共有 m+n-1 个，A的秩为 m+n-1？,最终一行可由前m+n-1行线性表示。其中任何一行都是一样。,6,二，表上作业法,表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。但具体计算和术语有所不同。可归纳为：,(1)找出初始基可行解。即在(mn)产销平衡表上用西北角法或最小元素法，Vogel法给出 m+n-1 个数字，称为数字格。它们就是初始基变量的取值。,(2)求各非基变量的检验数，即在表上计算空格的检验数，判别是否到达最优解。如已是最优解，则停顿计算，否则转到下一步。,(3)确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。,(4)重复(2)，(3)直到得到最优解为止。,7,2.1 确定初始基可行解,与一般线性规划问题不同，产销平衡的运输问题总是存在可行解。因有：,必存在,x,ij,0，,i,=1，,m,，,j,=1，,n,，,如：,X,ij,=a,i,b,j,/d,就是可行解。又因0,x,ij,min(,a,j,，,b,j,)，故运输问题必存在最优解。,8,2.1 确定初始基可行解,确定初始基可行解的方法很多，有西北角法，最小元素法和伏格尔(Vogel)法。一般希望的方法是既简便，又尽可能接近最优解。下面介绍最小元素法：,9,1.最小元素法,最小元素法的根本思路是以运价最低者优先为原则安排初始的调运方案，即从单位运价表中最小运价处开头确定供销关系。,假设产量大于销量，则用加工厂的产量满足对应销地的全部日销量，在对应的空格内填入相应的调运量。并用垂直直线划去销售地所在列，说明该销地的日销量已经全部满足，同时从对应加工厂的日产量中减去调运量。,反之，假设产量小于销售量。则把加工厂的日产量全部安排给对应的销售地。在对应空格填入调运量。用水平直线划去加工厂所在行，并从对应销地的日销量中减去调运量。,依次类推，逐步推出初始方案。,由于最小元素法已经考虑到了运价最低者优先为原则，因此所求的初始根本可行解通常比较接近最优解。经过假设干次调整即可求得最有解。,10,例1,某公司经销甲产品。下设三个加工厂,1,，,2,，,3,，每天把产品分别运往四个销地,1,，,2,，,3,，,4,。各加工厂的日产量，各销地的日销量以及从各加工厂运送单位产品至各销售地的运价如下表：,销地,产地,B,1,B,2,B,3,B,4,日产量（吨）,A,1,3,11,3,10,7,A,2,1,9,2,8,4,A,3,7,4,10,5,9,日销量（吨）,3,6,5,6,单位：千元/吨,问该公司应如何确定调运方案，在满足各销地需求量的前提下可使得总运费最小？,11,6,5,6,3,销量吨,9,5,10,4,7,A,3,4,8,2,9,1,3,A,2,7,10,3,11,3,A,1,产量吨,B,4,B,3,B,2,B,1,销售地,加工厂,为了用最小元素法确定初始根本可行解，可先画出综合运输表。然后按以下步骤确定初始调运方案。,从全部单位运价中找出最低单位运价假设有两个以上最低单位运价，则可在其中任选其一。然后比较最低运价所对应的加工厂的日产量和销地的日销量，并且确定第一笔供销关系。,-3,12,6,5,6,3,销量吨,9,5,10,4,7,A,3,4,8,2,1,9,1,3,A,2,7,10,3,11,3,A,1,产量吨,B,4,B,3,B,2,B,1,销售地,加工厂,-3,在未被划去的单位运价中再找寻最低运价，比较最低运价对应的加工厂的日产量或剩余量和销地的日销量或尚缺量来确定供销关系。根本原则与中描述过程一样。,-1,13,6,5,6,3,销量吨,9,5,3,10,4,6,7,A,3,4,8,2,1,9,1,3,A,2,7,10,3,3,4,11,3,A,1,产量吨,B,4,B,3,B,2,B,1,销售地,加工厂,-3,-1,重复步骤可逐个确定从加工厂到销地的供销关系。根本原则是在空格内内每填入一个调运量必需划去一行或一列。填入最终一个调运量后则同时划去一行和一列这样在运输表中共计填入了mn1个数字。这些数字对应了一个初始根本可行解。,-6,-4,-3,14,6,5,6,3,销量吨,9,5,3,10,4,6,7,A,3,4,8,2,1,9,1,3,A,2,7,10,3,3,4,11,3,A,1,产量吨,B,4,B,3,B,2,B,1,销售地,加工厂,-3,-1,-6,-4,-3,所填入的mn13416个数字为对应初始根本可行解的,6个初始基变量的值。即,对应的总运费为Z433103112643586千元,15,必需补充说明的是：利用最小元素法确定初始调运方案过程中，可能消逝最低单位运价对应的产地的产量和销地的销量恰好相等的情形。此时在运输表中填入一个数字后，必需同时划去产地所在行和销地所在列，这和每填入一个数字只划一条直线的根本原则相违反最终一个数字除外。这时我们称运输问题消逝了退化。,为了使运输表中有mn1个数字格。需要添加一个“0”调运量，它的位置可在同时划去的那行或那列的任一空格处。这个“0”调运量是不行缺少的。由于运输问题的根本解中基变量的个数必需是mn1个。不能多，也不能少。消逝了数字为0的数字格只是说明在初始根本可行解中有一个基变量为零。即该初始根本可行解是退化解。,16,2.1 确定初始基可行解,用最小元素法给出初始解时，有可能在产销平衡表上填入一个数字后，在单位运价表上同时划去一行和一列，这时就消逝退化。关于退化时的处理详见教材。,17,2.1 确定初始基可行解,2.伏格尔法略,18,2.2最优解的判别,回忆利用单纯形法求解线性规划的步骤：,在求出根本可行解以后，就必需检验该根本可行解是否为最优解，为此给出一个检验标准。在求极大化的线性规划时，假设初始根本可行解全部非基变量检验数,j为非基变量下标,则初始可行解为最优解，停顿计算。否则将进展基变换，对初始根本可行解进展改进。,运输问题初始根本可行解的最优性检验也必需设定一个标准。由于运输问题目标函数是求微小化问题，因此检验标准是计算全部非基变量空格的检验数,(i,j为非基变量下标),假设全部非基变量检验数,则初始根本可行解为最优解。,下面介绍两种计算检验数的方法。,19,1.闭回路法。,利用闭回路的概念计算非基变量的检验数，以判别根本可行解是否为最优解。,定义：假设运输表中的一组变量经过适当排列以后，可写成如下形式：,其中 互不一样，互不一样。,那么这些变量集合就构成了一个闭回路。其中的每一个变量称为这个闭回路的顶点。,由闭回路定义可知，假设用水平和垂直的线段将这个变量集合中处于同行同列的相邻顶点相连接。就能构成一个封闭的回路。而且该闭回路的每一条边水平或垂直上只包含两个顶点。且都处于每条边的两个端点上。如,20,表中变量集合,变量集合 ,变量集合等均构成闭回路,B,1,B,2,B,3,B,4,B,5,B,6,B,7,B,8,B,9,产量,A,1,a,1,A,2,a,2,A,3,a,3,A,4,a,4,销量,b,1,b,2,b,3,b,4,b,5,b,6,b,7,b,8,b,9,常见的几种闭回路见表：,21,性质,定理1 运输问题模型中，系数矩阵A的一组系数列向量,线性无关的充分必要条件是,这组向量所对应的变量 不包含闭回路。,本定理证明从略。,变量组 不包含闭回路的含义是该变量组中任何一个变量子集合均不构成闭回路。,由定理可得如下推论：,推论1.假设一组变量包含闭回路，那么这组变量所对应得系数列向量线性相关。,推论2.mn1个变量构成根本可行解的基变量的充分必要条件是它们不包含闭回路。,22,定理2 假设变量组 (s=m+n-1)是运输问题根本可行解的基变量，是一个非基变量，则变量组,中存在包含的唯一闭回路。,由定理2可知，从任何一个非基变量对应的空格动身，用水平或垂直线向前划，遇到某个基变量对应的数字格，试转90o后连续前进，最终总能找到一条闭回路，回到起始空格。,23,闭回路法。,设是一个非基变量，依据定理2，在运输表中可以找到以为第一个顶点，其他顶点均为基变量的唯一闭回路。,然后沿一个方向将闭回路中奇数顶点对应的值取为正，偶数顶点对应的值为负。求它们的代数和，即为非基变量对应的检验数。,填入相应的空格。做上记号以便与数字格的基变量值调运量相区分。,24,2.2 最优解的判别,闭回路法计算检验数的经济解释为：在已给出初始解的表中，可从任一空格动身，如(A1，B1)。假设让A1的产品调运1吨给B1。为了保持产销平衡，就要依次作调整：在(A1，B3)处削减1吨，(A2，B3)处增加1吨，(A2，B1)处削减1吨，即构成了以(A1，B1)空格为起点，其他为数字格的闭回路。如表中的虚线所示。在这表中闭回路各顶点所在格的右上角数字是单位运价。,25,2.2 最优解的判别,可见这调整的方案使运费增加,(+1)3+(1)3+(+1)2+(1)=1(元)这说明假设这样调整运量将增加运费。将“1”这个数填入(A1，B1)格，这就是检验数。,26,6,5,6,3,销量吨,9,5,3,10,4,6,7,A,3,4,8,2,1,9,1,3,A,2,7,10,3,3,4,11,3,A,1,产量吨,B,4,B,3,B,2,B,1,销售地,加工厂,例2 在例1中用最小元素法求出初始根本可行解为下表所示。试用闭回路法求各非基变量空格的检验数,解：非基变量为起点的闭回路为，如表所示。因此所对应的检验数,27,6,5,6,3,销量吨,9,5,3,10,12,4,6,7,10,A,3,4,8,-,2,1,9,1,3,A,2,7,10,3,3,4,11,3,A,1,产量吨,B,4,B,3,B,2,B,1,销售地,加工厂,而非基变量 对应的检验数：,其他非基变量的检验数用同样方法求解，结果下表。,本例中 ，则必存在对现行调运方案的改进方法。可使得总费用进一步降低。,28,2.2 最优解的判别,当检验数还存在负数时，说明原方案不是最优解，要连续改进，改进方法见2.3小节。,29,2.2 最优解的判别,2.位势法略,30,2.3 改进的方法闭回路调整法,当在表中空格处消逝负检验数时，说明未得最优解。假设有两个和两个以上的