运筹学课件第一节运输问题及其数学模型

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运筹学教程,第三章 运输问题,模型及其特点,求解思路及相关理论,求解方法表上作业法,运输问题的推广,1、,产销不平衡的运输问题,2、,转运问题,第一节 运输问题及其数学模型,一、运输问题的数学模型,1、运输问题的一般提法：,某种物资有若干产地和销地，现在需要把这种物资从各个产地运到各个销地，产量总数等于销量总数。已知各产地的产量和各销地的销量以及各产地到各销地的单位运价（或运距），问应如何组织调运，才能使总运费（或总运输量）最省？,单位,根据具体问题选择确定,。,表 有关信息,单位 运价 销,或运距 地产地,B,1,B,2,B,n,产 量,A,1,A,2,A,m,x,11,c,11,x,12,c,12,x,13,c,1 n,X,21,c,21,x,22,c,22,c,2n,x,m1,c,m1,x,m2,c,m2,x,mn,c,m n,a,1,a,2,a,m,销 量,b,1,b,2,b,n,2、运输问题的数学模型,设x,ij,为从产地A,i,运往销地B,j,的物资数量（i=1，m；j=1，n），由于从A,i,运出的物资总量应等于A,i,的产量a,i,，因此x,ij,应满足：,同理，运到B,j,的物资总量应该等于B,j,的销量b,j,，所以x,ij,还应满足：,总运费为：,运输问题的数学模型,二、运输问题数学模型的特点,1约束方程组的系数矩阵具有特殊的结构,系数矩阵A，形式如下：,m行,n行,2.运输问题的基变量总数是m+n-1,写出增广矩阵,每一列只有两个元素为1，其余元素均为0；列向量P,ij,=(0,，0，1，0，,0,1,0,0),T,，其中两个元素1分别处于第i行和第m+j行。,将该矩阵分块，特点是：前m行构成m个mn阶矩阵，而且第k个矩阵只有第k行元素全为1，其余元素全为0(k=1，m）；后n行构成m个n阶单位阵,证明系数矩阵A及其增广矩阵的秩都是m+n-1,前m行相加之和减去后n行相加之和结果是零向量，说明m+n个行向量线性相关，因此,的秩小于m+n,；？,因此 的秩恰好等于m+n-1，又D本身就含于A中，故A的秩也等于m+n-1,由 的第二至m+n行和前n列及 对应的列交叉处元素构成m+n-1阶方阵D 非奇异；？,可以证明,：,m+n个约束方程中的任意m+n-1个都是线性无关的,。,第二节表上作业法求解运输问题,表上作业法的基本思想是:先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，如图所示。,表上作业法和单纯形法的求解思想完全一致，但是具体作法更加简捷。,确定初始,方案,(初 始,基本可行解),改进调整,（换基迭代）,否,判定是否,最 优？,是,结 束,最优方案,运输问题求解思路图,一、初始方案的确定,1、作业表（产销平衡表）,初始方案就是初始基本可行解。,将运输问题的有关信息表和决策变量调运量结合在一起构成“作业表”（产销平衡表）。,下表是两个产地、三个销地的运输问题作业表。,调 销地,运,量,产地,B,1,B,2,B,3,产 量,A,1,c,11,X,11,c,12,X,12,c,13,X,13,a,1,A,2,c,21,X,21,c,22,X,22,c,23,X,23,a,2,销 量,b,1,b,2,b,3,表 运输问题作业表（产销平衡表）,其中x,ij,是决策变量，表示待确定的从第i个产地到第j个销地的调运量，c,ij,为从第i个产地到第j个销地的单位运价或运距。,2、确定初始方案的步骤：,（1）选择一个x,ij,，令x,ij,=mina,i,，b,j,=,将具体数值填入x,ij,在表中的位置；,（,2）调整产销剩余数量：从a,i,和b,j,中分别减去x,ij,的值，若a,i,-x,ij,=0，则划去产地A,i,所在的行，即该产地产量已全部运出无剩余，而销地B,j,尚有需求缺口b,j,-a,i,；若b,j,-x,ij,=0，则划去销地B,j,所在的列，说明该销地需求已得到满足，而产地A,i,尚有存余量a,i,-b,j,；,（3）当作业表中所有的行或列均被划去，说明所有的产量均已运到各个销地，需求全部满足，x,ij,的取值构成初始方案。否则，在作业表剩余的格子中选择下一个决策变量，返回步骤（2）,。,按照上述步骤产生的一组变量必定不构成闭回路，其取值非负，且总数是m+n-1个，因此构成运输问题的基本可行解。,对x,ij,的选择采用不同的规则就形成各种不同的方法，比如每次总是在作业表剩余的格子中选择运价（或运距）最小者对应的x,ij,，则构成最小元素法，若每次都选择左上角格子对应的x,ij,就形成西北角法（也称左上角法）和沃格尔法（vogel）,3、,举例,例某部门有3个生产同类产品的工厂，生产的产品由4个地点销售，各个供应地、目的地的生产量、销售量以及各个供应地到目的地的运费见表，求使总运输量最少的调运方案。,1、最小元素法,B1,B2,B3,B4,产量,A1,16,A2,10,A3,22,销量,8,14,12,14,48,产地,销地,4,12,10,2,8,5,11,3,4,11,9,6,8,2,10,14,8,6,Z=10,X4+6X11+8X2+2X3+14X5+8X6=246,最小元素法的基本思想是“就近供应”；,运价表,上找最小，,平衡表,上定产销；,满足销量划去“列”，修改“行产”要记牢；,（满足产量划去“行”，修改“列销”要记牢）,余表再来找最小。,B1,B2,B3,B4,产量,A1,16,A2,10,A3,22,销量,8,14,12,14,48,2、西北角法,4,3,9,4,11,12,11,6,8,5,10,2,8,8,6,4,8,14,Z=8,X4+8X12+6X10+4X3+8X11+14X6=372,西北角法则不考虑运距（或运价），每次都选剩余表格的左上角（即西北角）元素作为基变量，其它过程与最小元素法相同,3、沃格尔法,每个供应地 到销售地（或每个销售地 到供应地）的单位运价中找出最小运价和次小单位运价，运价之差为供应地到销售地的罚数。,如果罚数的数值不大，当不能按照最小单位运输时造成的损失不大；如果罚数的数值大，当不能按照最小单位运输时造成的损失大，应该尽量按照最小单位运输；,计算步骤,1、计算每一行和每一列的罚数，称为行罚数和列罚数。,2、将计算的行罚数和列罚数添加到表格中。,3、根据行罚数和列罚数（行等于列）找最大的罚数，确定罚数所在的行或列，按照最小单位法进行表上作业。,销,产,B1,B2,B3,B4,产量,行罚数,1,2,3,4,5,A1,16,0,0,0,7,0,A2,10,1,1,1,6,0,A3,22,1,2,销量,8,14,12,14,48,列,罚,数,1,2,5,1,3,2,2,1,3,3,2,1,2,4,1,2,5,2,4,9,4,11,6,11,5,8,12,2,3,10,14,8,8,12,2,4,Z=12x4+4x11+8x2+2x9+14x5+8x6=244,一般用作近似解,小结:,1、讲解运输问题及其数学模型。,2、三种表上作业法求解运输问题的计算步骤。,