2.4运输问题(修改).ppt

1、1,第2.4节 运输问题,一、 运输问题的数学模型 二、 表上作业法 三、产销不平衡的运输问题及其求解方法,2,例1 某公司经销甲产品。它下设三个加工厂。每日的产量分别是：A1为7吨，A2为4吨，A3为9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为：B1为3吨，B2为6吨，B3为5吨，B4为6吨。已知从各工厂到各销售点的单位产品的运价。问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。,单位运价表,产销平衡表,3,一、运输问题的数学模型,已知有m个生产地点 Ai , i=1,2,，m。可供应某种物资，其供应量(产量)分别为：ai，i=1，2，m 有n个销地 B

2、j，j=1,2,n，其需要量分别为 ：bj，j=1,2,n 从 Ai 到 Bj 运输单位物资的运价(单价)为：cij 这些数据可汇总于产销平衡表和单位运价表中，见下表。有时可把这两表合二为一。,4,若用 xij 表示从 Ai 到 Bj 的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案的数学模型为：,5,一、运输问题的数学模型,这就是运输问题的数学模型。它包含mn个变量，(m+n)个约束方程，其系数矩阵的结构比较松散，且特殊。,6,一，运输问题的数学模型,该系数矩阵中对应于变量 xij 的系数向量Pij，其分量中除第i个和第m+j个为1以外，其余的都为零。即 Pij= (0, ,1,0

3、,0,1,0,0)T = ei+ em+j 对产销平衡的运输问题，由于有以下关系式存在：,运输问题是否一定有解？(见后面),运输问题的基变量共有 m + n -1 个，A的秩为 m + n -1？ 最后一行可由前m+n-1行线性表示。其中任何一行都是一样。,7,二，表上作业法,表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。但具体计算和术语有所不同。可归纳为： (1) 找出初始基可行解。即在(mn)产销平衡表上用西北角法或最小元素法，Vogel法给出 m+n-1 个数字，称为数字格。它们就是初始基变量的取值。 (2) 求各非基变量的检验数，即在表上计算空格的检验数，判别是

4、否达到最优解。如已是最优解，则停止计算，否则转到下一步。 (3) 确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。 (4) 重复(2)，(3)直到得到最优解为止。,8,2.1 确定初始基可行解,与一般线性规划问题不同，产销平衡的运输问题总是存在可行解。因有：,必存在xij0，i=1，m，j=1，n， 如： Xij = aibj / d就是可行解。又因0 xijmin(aj，bj)，故运输问题必存在最优解。,9,2.1 确定初始基可行解,确定初始基可行解的方法很多，有西北角法，最小元素法和伏格尔(Vogel)法。一般希望的方法是既简便，又尽可能接近最优解。下面介绍最小元素法：,1

5、0,1.最小元素法 最小元素法的基本思路是以运价最低者优先为原则安排初始的调运方案，即从单位运价表中最小运价处开始确定供销关系。 若产量大于销量，则用加工厂的产量满足对应销地的全部日销量，在对应的空格内填入相应的调运量。并用垂直直线划去销售地所在列，表明该销地的日销量已经全部满足，同时从对应加工厂的日产量中减去调运量。 反之，若产量小于销售量。则把加工厂的日产量全部分配给对应的销售地。在对应空格填入调运量。用水平直线划去加工厂所在行，并从对应销地的日销量中减去调运量。 依次类推，逐步推出初始方案。 由于最小元素法已经考虑到了运价最低者优先为原则，因此所求的初始基本可行解通常比较接近最优解。经过

6、若干次调整即可求得最有解。,11,例1 某公司经销甲产品。下设三个加工厂1，2，3，每天把产品分别运往四个销地1，2，3，4。各加工厂的日产量，各销地的日销量以及从各加工厂运送单位产品至各销售地的运价如下表：,单位：千元/吨,问该公司应如何确定调运方案，在满足各销地需求量的前提下可使得总运费最小？,12,6,5,6,3,销量（吨）,9,5,10,4,7,A3,4,8,2,9,1,3,A2,7,10,3,11,3,A1,产量（吨）,B4,B3,B2,B1,销售地 加工厂,为了用最小元素法确定初始基本可行解，可先画出综合运输表。然后按以下步骤确定初始调运方案。 从全部单位运价中找出最低单位运价（若

7、有两个以上最低单位运价，则可在其中任选其一）。然后比较最低运价所对应的加工厂的日产量和销地的日销量，并且确定第一笔供销关系。,-3,13,6,5,6,3,销量（吨）,9,5,10,4,7,A3,4,8,2,1,9,1,3,A2,7,10,3,11,3,A1,产量（吨）,B4,B3,B2,B1,销售地 加工厂,-3, 在未被划去的单位运价中再找寻最低运价，比较最低运价对应的加工厂的日产量（或剩余量）和销地的日销量（或尚缺量）来确定供销关系。基本原则与中描述过程相同。,-1,14,6,5,6,3,销量（吨）,9,5,3,10,4,6,7,A3,4,8,2,1,9,1,3,A2,7,10,3,3,4

8、,11,3,A1,产量（吨）,B4,B3,B2,B1,销售地 加工厂,-3,-1,重复步骤可逐个确定从加工厂到销地的供销关系。基本原则是在空格内内每填入一个调运量必须划去一行或一列。填入最后一个调运量后则同时划去一行和一列这样在运输表中共计填入了mn1个数字。这些数字对应了一个初始基本可行解。,-6,-4,-3,15,6,5,6,3,销量（吨）,9,5,3,10,4,6,7,A3,4,8,2,1,9,1,3,A2,7,10,3,3,4,11,3,A1,产量（吨）,B4,B3,B2,B1,销售地 加工厂,-3,-1,-6,-4,-3,所填入的mn13416个数字为对应初始基本可行解的 6个初始基

9、变量的值。即 对应的总运费为Z433103112643586（千元）,16,必须补充说明的是：利用最小元素法确定初始调运方案过程中，可能出现最低单位运价对应的产地的产量和销地的销量恰好相等的情形。此时在运输表中填入一个数字后，必须同时划去产地所在行和销地所在列，这和每填入一个数字只划一条直线的基本原则相违背（最后一个数字除外）。这时我们称运输问题出现了退化。 为了使运输表中有mn1个数字格。需要添加一个“0”调运量，它的位置可在同时划去的那行或那列的任一空格处。这个“0”调运量是不可缺少的。因为运输问题的基本解中基变量的个数必须是mn1个。不能多，也不能少。出现了数字为0的数字格只是说明在初始

10、基本可行解中有一个基变量为零。即该初始基本可行解是退化解。,17,2.1 确定初始基可行解,用最小元素法给出初始解时，有可能在产销平衡表上填入一个数字后，在单位运价表上同时划去一行和一列，这时就出现退化。关于退化时的处理详见教材。,18,2.1 确定初始基可行解,2. 伏格尔法（略）,19,2.2最优解的判别 回顾利用单纯形法求解线性规划的步骤： 在求出基本可行解以后，就必须检验该基本可行解是否为最优解，为此给出一个检验标准。在求极大化的线性规划时，若初始基本可行解所有非基变量检验数 （j为非基变量下标） 则初始可行解为最优解，停止计算。否则将进行基变换，对初始基本可行解进行改进。 运输问题初

11、始基本可行解的最优性检验也必须设定一个标准。由于运输问题目标函数是求极小化问题，因此检验标准是计算所有非基变量（空格）的检验数 (i,j为非基变量下标) 如果所有非基变量检验数 则初始基本可行解为最优解。 下面介绍两种计算检验数的方法。,20,1.闭回路法。 利用闭回路的概念计算非基变量的检验数，以判别基本可行解是否为最优解。 定义：若运输表中的一组变量经过适当排列以后，可写成如下形式： 其中 互不相同， 互不相同。 那么这些变量集合就构成了一个闭回路。其中的每一个变量称为这个闭回路的顶点。 由闭回路定义可知，若用水平和垂直的线段将这个变量集合中处于同行同列的相邻顶点相连接。就能构成一个封闭的

12、回路。而且该闭回路的每一条边（水平或垂直）上只包含两个顶点。且都处于每条边的两个端点上。如,21,表中变量集合,变量集合 , 变量集合等均构成闭回路,常见的几种闭回路见表：,22,性质 定理1 运输问题模型中，系数矩阵A的一组系数列向量 线性无关的充分必要条件是 这组向量所对应的变量 不包含闭回路。 本定理证明从略。 变量组 不包含闭回路的含义是该变量组中任何一个变量子集合均不构成闭回路。 由定理可得如下推论： 推论1.若一组变量包含闭回路，那么这组变量所对应得系数列向量线性相关。 推论2.mn1个变量构成基本可行解的基变量的充分必要条件是它们不包含闭回路。,23,定理2 若变量组 (s=m+

13、n-1)是运输问题基本可行解的基变量，是一个非基变量，则变量组 中存在包含的唯一闭回路。 由定理2可知，从任何一个非基变量对应的空格出发，用水平或垂直线向前划，遇到某个基变量对应的数字格，试转90o后继续前进，最后总能找到一条闭回路，回到起始空格。,24,闭回路法。 设是一个非基变量，根据定理2，在运输表中可以找到以为第一个顶点，其他顶点均为基变量的唯一闭回路。 然后沿一个方向将闭回路中奇数顶点对应的值取为正，偶数顶点对应的值为负。求它们的代数和，即为非基变量对应的检验数。 填入相应的空格。做上记号以便与数字格的基变量值（调运量）相区别。,25,2.2 最优解的判别,闭回路法计算检验数的经济解

14、释为：在已给出初始解的表中，可从任一空格出发，如(A1，B1)。若让A1的产品调运1吨给B1。为了保持产销平衡，就要依次作调整： 在(A1，B3)处减少1吨，(A2，B3)处增加1吨，(A2，B1)处减少1吨，即构成了以(A1，B1)空格为起点，其他为数字格的闭回路。如表中的虚线所示。在这表中闭回路各顶点所在格的右上角数字是单位运价。,26,2.2 最优解的判别,可见这调整的方案使运费增加 (+1)3+(1)3+(+1)2+( 1)=1(元) 这表明若这样调整运量将增加运费。将“1”这个数填入(A1，B1)格，这就是检验数。,27,6,5,6,3,销量（吨）,9,5,3,10,4,6,7,A3

15、,4,8,2,1,9,1,3,A2,7,10,3,3,4,11,3,A1,产量（吨）,B4,B3,B2,B1,销售地 加工厂,例2 在例1中用最小元素法求出初始基本可行解为下表所示。试用闭回路法求各非基变量（空格）的检验数 解：非基变量为起点的闭回路为，如表所示。因此所对应的检验数,28,6,5,6,3,销量（吨）,9,5,3,10,12,4,6,7,10,A3,4,8,-,2,1,9,1,3,A2,7,10,3,3,4,11,3,A1,产量（吨）,B4,B3,B2,B1,销售地 加工厂,而非基变量 对应的检验数： 其他非基变量的检验数用同样方法求解，结果下表。 本例中 ，则必存在对现行调运方

16、案的改进办法。可使得总费用进一步降低。,29,2.2 最优解的判别,当检验数还存在负数时，说明原方案不是最优解，要继续改进，改进方法见2.3小节。,30,2.2 最优解的判别,2. 位势法（略）,31,2.3 改进的方法闭回路调整法,当在表中空格处出现负检验数时，表明未得最优解。若有两个和两个以上的负检验数时，一般选其中最小的负检验数，以它对应的空格为调入格。即以它对应的非基变量为换入变量。以(2，4)为调入格。以此格为出发点，作一闭回路，如下表所示。,32,2.3 改进的方法闭回路调整法,(2，4)格的调入量是选择闭回路上具有(-1)的数字格中的最小者。即=min(1,3)=1(其原理与单纯

17、形法中按规划来确定换出变量相同)。然后按闭回路上的正、负号，加入和减去此值，得到调整方案，如下表所示。,33,2.3 改进的方法闭回路调整法,对上表给出的解，再用闭回路法或位势法求各空格的检验数，见下表。表中的所有检验数都非负，故此表中的解为最优解。这时得到的总运费最小是85元。,34,2.4 表上作业法计算中的问题,1. 无穷多最优解 2. 退化,35,三 产销不平衡的运输问题及其求解方法,前面所讲表上作业法，都是以产销平衡为前提条件的；但是实际问题中产销往往是不平衡的。就需要把产销不平衡的问题化成产销平衡的问题。 当产大于销时,36,三、产销不平衡的运输问题及其求解方法,运输问题的数学模型

18、可写成,=,37,三、产销不平衡的运输问题及其求解方法,1.由于总的产量大于销量，就要考虑多余的物资在哪一个产地就地储存的问题。设xi, n+1是产地Ai的储存量，于是有：,38,三，产销不平衡的运输问题及其求解方法,令,当 i=1,，m，j=1,，n时,当 i=1,，m，j=n+1时,将其分别代入，得到,39,三、 产销不平衡的运输问题及其求解方法,40,三、 产销不平衡的运输问题及其求解方法,由于该模型中有,所以这是一个产销平衡的运输问题。 当产大于销时，只要增加一个假想的销地j=n+1(实际上是储存)，该销地总需要量为：,而在单位运价表中从各产地到假想销地的单位运价为， Ci,n+1=0就转化成一个产销平衡的运输问题。,41,三、 产销不平衡的运输问题及其求解方法,2.当销大于产时，可以在