,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,主讲人：,制作：,年月,线性规划的运输问题,1,在处理产、供、销的经济活动中，会经常遇到物资调拨的运输问题。如粮棉油、煤炭、钢铁、水泥、化肥、木材等物资要由若干个产地调运到若干个销售地。问题是，怎样制定合理的调用方案才能使总运输费用最少？本章将专门讨论这类特殊形式的线性规划问题。,导,言,第五章 运输问题,2,例 某食品公司经销的主要商品之一是糖果，它下面设有三个加工厂。某个的产量分别为,A,1,7t，A,2,4t，A39t,该公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量为：,B,1,3t，B,2,6t，B,3,5t，B,4,6t,。已知从各个加工厂到各销售部门每吨的运价见下表：,5.1 运输问题的数学模型,3,10,4,7,A,3,8,2,9,1,A,2,10,3,11,3,A,1,B,4,B,3,B,2,B,1,门市部,加工厂,单位：元/t,问：该食品公司应如何调运，在满足各部门销售的情况下，使总的运费支出为最少？,产销平衡的运输问题,3,无论全国或一个地区，在各种生产或生活物资调运中都可以提出入上述问题类似的例子。,现在把问题概括一下，在线性规划中我们研究这样一类运输问题：,5.1 运输问题的数学模型,产销平衡的运输问题,4,设有某种物资要从m个产地（或称发点）A,i,(i=1，2，m),运往n个销地（或称收点）B,j,(j=1，2，n),，A,i,的产量为a,i,，B,j,的销量为b,j,，把,A,i,运到,B,j,的单位运价设为c,ij,，问怎样编制调运方案才能使总运费最少？,假设从A,i,运到B,j,的物资数量为x,ij,，总运费为S，总产量=总销量。那么这个运输问题的数学模型是：,5.1 运输问题的数学模型,产销平衡的运输问题,5,产销平衡的运输问题,5.1 运输问题的数学模型,运输问题的数学模型是:,产销平衡表,产量a,i,产地,销地,销量b,i,1 n,m,b,1,b,2,b,n,a,1,a,2,a,m,x,11,x,12,x,1n,x,21,x,22,x,2n,x,m1,x,m2,x,mn,产地,销地,1 n,m,c,11,c,12,c,1n,c,21,c,22,c,2n,c,m1,c,m2,c,mn,单位运价表,6,产销平衡的运输问题,5.1 运输问题的数学模型,运输问题的数学模型是:,7,C=(c,11,，c,12,，c,1n,，c,21,，c,22,，c,2n,，c,m1,，c,m2,，c,mn,),B=（a,1,，a,2,，a,m,，b,1,，b,2,，b,n,),T,X=(x,11,，x,12,，x,1n,，x,21,，x,22,，x,2n,，x,m1,，x,m2,，x,mn,),T,5.1 运输问题的数学模型,其矩阵形式为,产销平衡的运输问题,8,（1）产量大于销量的情形,5.1 运输问题的数学模型,产销不平衡运输问题的转化,其运输问题的数学模型是,9,由于总量大于总销量，所以多余物资应储存在产地。社某产地,A,i,的多余存储量为,x,i,n+1,，于是运输问题的约束条件方程组为：,则,5.1 运输问题的数学模型,产销不平衡运输问题的转化,10,5.1 运输问题的数学模型,可将不平衡的运输问题（5.3）化为如下的平衡运输问题,产销不平衡运输问题的转化,令,11,（2）产量大于销量的运输问题,这时可增加一个设想的发点A,m+1,，发出量为,并令该发点到收点,B,的运价C,.,（，），同样可将不平衡的运输问题转化为平衡的运输问题。,如无特别说明，本章仅限于对平衡问题的运输问题求解的讨论。,同一般的线性规划问题一样，运输问题的最优解也一定能在它的基本可行解中找到。由于运输问题（.）的约束系数矩阵的前行之和恰好等于后行之和，即矩阵的行向量组线性相关，因此的秩必小于,+,5.1 运输问题的数学模型,产销不平衡运输问题的转化,12,5.1 运输问题的数学模型,产销不平衡运输问题的转化,13,根据以上讨论可知，运输问题（5.2）的基矩阵应由m+n-1个线性无关的列向量组成，这些列向量是约束方程Ax=b中去掉多余方程后剩下的m+n-1个方程的系数列向量，因此在研究运输问题的基时只要在A中找到m+n-1个线性无关的系数列向量就可以了。,运输问题中的约束方程和变量个数一般比较多。例如m=25,n=500时，就有525个约束方程和12500个变量，这样的问题即使使用电子计算机求解也很困难。但根据运输问题具有的特殊结构，有专门为其设计的求解方法，这里不作介绍。对小规模的运输问题的求解，可通过表上作业法和图上作业法去完成。,5.1 运输问题的数学模型,因此秩（A）=m+n-1。同样可得A的增广矩阵 =（a,b）的秩也等于m+n-1。所以（5.2）式的m+n个等式约束中有一个是多余的，于是增广矩阵 的任意一行都可用其余m+n-1行线性表出。这样，运输问题（5.2）中去掉任一个等式约束后就成为标准形式的线性规划问题，便可用单纯形或对偶单纯形方法求解。,产销不平衡运输问题的转化,14,5.2 运输问题的表上作业法,对于小规模的运输问题其求解过程可以在表上进行。,15,5.2 运输问题的表上作业法,表中共有mn个格子，每个格子对应一个变量,求解运输问题的首要任务是，在表上找到m+n-1个格子对应的一组变量，,是一组变量。,为此，先引入以下概念和结论。,16,定义,5.1,5.2 运输问题的表上作业法,称变量组的集合,是一个闭回路。其中i,1,i,2,i,s,互不相同，j,1,j,2,j,s,互不相同,称其中每个变量为闭回路的顶点。,例如，变量组,中的i,1,=4,i,2,=3,i,3,=1,j,1,=5,j,2,=1,j,3,=3 各互不相同，若在表格中把相邻两个顶点，第一个顶点与最后一个顶点用直线段连接起来，就可在下表5.2中画出这个闭回路。,X,45,X,41,X,31,X,33,X,13,X,15,17,定义,5.1,5.2 运输问题的表上作业法,X,11,但变量组x,11,x,12,x,22,x,24,x,44,x,42,x,21,不能构成一条闭回路，因为x,42,不是拐角点。,X,12,X,22,X,24,X,44,X,42,X,42,18,若变量组,是一个闭回路，则这个变量组对应矩阵A中的列向量组线性相关。,证明,矩阵A中的每列只有两个元素为，其余都是。变量x,ij,对应中的列向量是,5.2 运输问题的表上作业法,定理,5.1,第i个分量,第m+j个分量,19,5.2 运输问题的表上作业法,定理,5.1,通过计算闭回路中变量对应中的列向量，得,这表明变量组对应矩阵中列向量组线性相关。,20,变量组 对应矩阵中列向量组,根据以上结论，给出了从表格上判断运输问题的方法。m+n-1个变量是否为一组基变量就看表中m+n-1个变量是否含有闭回路。于是可从表格上方便的求出运输问题的初始基本可行解来.,5.2 运输问题的表上作业法,定理,5.2,线性无关的充要条件是该变量组不含有闭回路。,求解运输问题的表上作业法可按以下步骤进行。,21,一、编制初始调运方案,方法一 最小元素法,令,（1）若a,i,b,j,，则取x,ij,=b,j,而xsj=0(s=1,2,i-1,i+1,m),将b,j,填入(i,j)格内。这时,x,1j,+x,2j,+x,ij,+x,mj,=x,ij,=b,j,例5.1用最小元素法求下列运输问题的初始调运方案,销地,产地,B,1,B,2,B,3,B,4,B,5,产量,a,i,销量,b,j,B,1,B,2,B,3,B,4,B,5,10 20 5 9 10,10 8 25 6,1 15 7 10 4,平衡表,运价表,5.2 运输问题的表上作业法,一、编制初始调运方案,求解运输问题的表上作业法的步骤：,23,销地,产地,B,1,B,2,B,3,B,4,B,5,产量,a,i,销量,b,j,B,1,B,2,B,3,B,4,B,5,10 20 5 9 10,10 8 25 6,1 15 7 10 4,平衡表,运价表,初始基本可行解为,x,12,x,13,x,14,x,22,x,31,x,32,x,35,=1,5,3,4,3,0,5,相应运价为：,c,12,c,13,c,14,c,22,c,31,c,32,c,35,=20,5,9,10,1,15,4,由此表上作业得初始调运方案的总运费为S=1x20+5x5+3x9+4x10+3x1+0 x15+5x4=135（元）,5.2 运输问题的表上作业法,一、编制初始调运方案,求解运输问题的表上作业法的步骤：,1,5,3,4,3,0,5,解,1,5,2,3,4,4,1,5,1,6,7,24,方法二 左上角法(也称西北角法）,令,（1）若a,1,b,1,，则取x,11,=b,1,则取x,11,=b,1，,而x,s1,=0(s=2,3,m),将b,1,填入(1,1)格内。这时,x,11,+x,21,+x,m1,=b,1,5.2 运输问题的表上作业法,一、编制初始调运方案,求解运输问题的表上作业法的步骤：,25,例5.2用左上角法求下列运输问题的初始调运方案,销地,产地,B,1,B,2,B,3,B,4,B,5,产量,a,i,9,销量,b,j,B,1,B,2,B,3,B,4,B,5,10 20 5 9 10,10 8 25 6,1 15 7 10 4,平衡表,运价表,5.2 运输问题的表上作业法,一、编制初始调运方案,求解运输问题的表上作业法的步骤：,26,5.2 运输问题的表上作业法,一、编制初始调运方案,求解运输问题的表上作业法的步骤：,解,销地,产地,B,1,B,2,B,3,B,4,B,5,产量,a,i,9,销量,b,j,B,1,B,2,B,3,B,4,B,5,10 20 5 9 10,10 8 25 6,1 15 7 10 4,平衡表,运价表,1,3,6,2,5,1,3,1,4,4,4,5,0,6,3,5,7,5,初始基本可行解为,x,11,x,12,x,13,x,23,x,33,x,34,x,35,=3,5,1,4,0,3,5,相应运价为：,c,11,c,12,c,13,c,23,c,33,c,34,c,35,=10,20,5,8,7,10,4,由此表上作业得初始调运方案的总运费为S=,S=3x10+5x20+1x5+4x8+0 x7+3x10+5x4=217,（元）,27,