3第三章_运输问题

第三章运输问题运输问题的数学建模及表上作业法不平衡问题的数学处理3.1、运输问题的数学模型在经济建设中，经常会遇到大宗物资调拨中的运输问题。如煤炭、钢铁、木材、粮食等物资,在全国有若干生产基地，根据已有的交通网，应如何制定调运方案，将这些物资运到各消费地点，而使总运费最小。这类问题可用以下数学语言来描述：运输问题：假设有m个生产地点，可以供应某种物资(以后称为产地)，用Ai表示，i=1,2,,m；有n个销售地，用Bj表示，j=1,2,,n；产地的产量和销售地的销售量分别为ai,i=1,2,,m和bj，j=1,2,,n，从Ai到Bj运输单位物资的运价为cij，这些数据可汇总于如表3.1。表3.1销地产地B1B2Bn产量A1c11c12c1na1A2c21c22c2na2Amcm1cm2cmnam销量b1b2bn要求使总运费最小的调运方案。如果运输问题的总产量等于其总销量，即njjmiiba11则称该运输问题为产销平衡运输问题；反之，称为产销不平衡运输问题。下面建立在产销平衡情况下的运输问题的数学模型。解:假设xij表示从Ai到Bj的运量,则所求的数学模型为:njmixmiaxnjbxxcZijinjijjmiijminjijij,,2,1;,,2,10,,2,1,,2,1min1111在该模型中，目标函数表示运输总费用，要求其极小化；第一个约束条件的意义是由各产地运往某一销地的物品数量之和等于该销地的销量；第二个约束条件表示由某一产地运往销地的物品数量之和等于该产地的产量；第三个约束条件表示变量的非负条件。设有三个电视机厂。生产同一种彩色电视机，日生产能力分别是：50，60，50，供应四个门市部，日销售量分别是：40，40，60，20台，从各分厂运往个门市部的运费如表1-23所示，试安排一个运费最低的运输计划。门市部工厂1234供应总计12397612359796711506050需求总计40406020供求平衡的运输问题：供：50+60+50=160需：40+40+60+20=160数学模型04,3,2,1,3,2,1,..min31413141ijjiijijijijijijxjbxiaxtsxcz设有三个电视机厂。生产同一种彩色电视机，日生产能力分别是：50，80，50，供应四个门市部，日销售量分别是：40，40，60，20台，从各分厂运往个门市部的运费如表所示，试安排一个运费最低的运输计划。门市部工厂1234供应12397612359796711508050需求40406020供应量＝180，需求量＝160，供需不平衡，供大于求。数学模型？供大于求的情况•数学模型0,,2,1,,,2,1,..min1111ijjmiijinjijminjijijxnjbxmiaxtsxcz特点与处理办法•特点•处理办法：设置一个虚销售点n+1，使•且，因而化为平衡问题。njjmiiba11njjmiinbab11101,nic设有三个电视机厂。生产同一种彩色电视机，日生产能力分别是：50，80，50，供应四个门市部，日销售量分别是：40，40，60，20台，从各分厂运往个门市部的运费如表所示，试安排一个运费最低的运输计划。门市部工厂12345供应总计12397612359796711000508050需求总计4040602020供应量＝180，需求量＝180，供需平衡。设有三个电视机厂。生产同一种彩色电视机，日生产能力分别是：50，60，50，供应四个门市部，日销售量分别是：40，70，60，20台，从各分厂运往个门市部的运费如表所示，试安排一个运费最低的运输计划。门市部工厂1234供应总计12397612359796711506050需求总计40706020供应量＝160，需求量＝190，供需不平衡，需求大于供应。求大于供•数学模型0,,2,1,,,2,1,..min1111ijjmiijinjijminjijijxnjbxmiaxtsxcz特点与处理办法•特点•处理办法：增加一个虚产地m+1，使且，化为平衡问题。njjmiiba11miinjjmaba1110,1jmc设有三个电视机厂。生产同一种彩色电视机，日生产能力分别是：50，60，50，供应四个门市部，日销售量分别是：40，70，60，20台，从各分厂运往个门市部的运费如表所示，试安排一个运费最低的运输计划。门市部工厂1234供应总计123497601235097906711050605030需求总计40706020供应量＝190，需求量＝190，供需平衡。这就是运输问题的数学模型，它包含mn个变量，m+n个约束条件，是一个线性规划问题。如果用单纯形法求解，首先应在每个约束条件上加入一个人工变量(以便求出初始基可行解)。即使是m=4，n=5这样的简单问题,变量个数就有29个之多，利用单纯形法进行计算是非常复杂的。有必要针对运输问题的某些特点，来寻求更为简单方便的求解方法。3.2、表上作业法1、表上作业法的基本概念与重要结论针对运输问题的数学模型结构的特殊性，它的约束方程组的系数矩阵具有如下特点：（1）在该矩阵中，它的元素等于0或1；（2）每列只有两个元素为1，其余都是0；（3）对应于每一个变量，在前m个约束方程中只出现一次，在后n个约束方程中也只出现一次。根据这个特点，在单纯形法的基础上，下面设计出一种专门用来求解运输问题的方法，称为表上作业法。101010010101110000001100000011,,,,,,,,,1221111Axxxxxxmnmnn运输问题的解代表着一个运输方案，其中每一个变量xij的值表示由Ai调运数量为xij的物品给Bj。当用单纯形法进行求解时，首先应当知道它的基变量的个数；其次，要知道这样一组基变量应当是由哪些变量来组成。运输问题的解X必须要满足模型中的所有约束条件；基变量对应的约束方程组的系数列向量必须是线性无关的；解中基变量应由m+n-1个变量组成(即基变量的个数=产地个数+销售地个数–1)，原因是在运输问题中虽然有m+n个约束条件，但由于总产量等于总销量，有m+n-1个约束条件是线性独立的。怎样的m+n-1个变量会构成一组基变量？需要引入一些基本概念，通过对这些基本概念的分析和讨论，结合单纯形算法的基本结果，便可得出所需要的结论。凡是能排成111222231,,,,,,sssijijijijijijxxxxxx互不相同，且,1mik,,1sk),,1,1,,,1slnjjjls且互不相同形成的变量的集合称之为一个闭回路。而把出现在闭回路中的变量称为这个闭回路的顶点。例3.1设m=3，n=4，如表3.2所示。销地产地B1B2B3B4A1x11x12A2x21x24A3x32x34x11、x12、x32、x34、x24、x21构成一个闭回路。这里有：i1=1，i2=3，i3=2；j1=1，j2=2，j3=4。若把闭回路的顶点在表中画出，并且把相邻两个变量用一条直线相连（今后就称这些直线为闭回路的边）。而表3.3，即顶点为{x12、x32、x34、x14}和表3.4，即顶点为{x11、x12、x22、x24、x34、x31}也分别构成两个闭回路。例3.1设m=3，n=4，如表3.2所示。表3.3销地产地B1B2B3B4A1x12x14A2A3x32x34表3.4销地产地B1B2B3B4A1x11x12A2x22x24A3x31x34从上面的例子中不难看出，如果把一个闭回路的所有顶点都在表中画出，并且把相邻的顶点都用一条直线连接起来，就可以得到一条封闭的折线，折线的每一条边或者是水平的，或者是垂直的。定理3.1：m+n-1个变量构成基变量的充分必要条件是它不包含有任何闭回路。该定理给出了运输问题基的一个重要特征，因为利用它可以判断m+n-1个变量是否构成基变量，它比直接判断这些变量所对应的系数列向量组是否线性无关要简单和直观。)1(,,,2211nmsxxxssjijiji2、表上作业法表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形算法。只是具体计算和术语有所不同，可归纳为：（1）找出初始基可行解；（2）求各非基变量的检验数；（3）确定换入变量和换出变量，找出新基可行解。（4）重复（2）、（3）步，直到求得最优解为止。（1）、确定初始基可行解确定初始基可行解即首先给出初始的调运方案，介绍其中的两种方法：①方法一：最小元素法：最小元素法的基本思想就是就近供应。即从单位运价表中最小的运价开始确定产销关系，依次类推，直到给出初始方案为止。下面由例题来说明最小元素法确定初始基可行解的具体步骤。例3.2：某公司有3个生产同类产品的工厂，生产的产品由4个销售点销售，各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价如表3.5所示。问该公司应如何调运产品，在满足各销售点的需要量的前提下，使总的运费为最小。初始可行解（最小元素法）门市工厂1234供应123403020301030506050需求40306030就近供应的思想：从单位运价表中选取最低运价的空格开始供求分配。供应量大于需求量，取值为需求量，划去该空格的列；供应量小于需求量，取值供应量，划去该空格的行。然后根据划去一列或行的单位运价表，再选择最小运价的空格进行。门市工厂1234供应12397612359796711506050需求40306030表3.5销地产地B1B2B3B4产量A13113107A219284A3741059销量3656解：第一步：从单位运价表中找出最小运价为1，这表示先将A2的产品供应给B1。由于A2每天生产4吨，B1每天只需要3吨，即A2除每日能满足B1的需要外还余1吨。因此在产销平衡表(A2,B1)交叉处填上3，表示A2调运3吨给B1，再在单位运价表中将B1这一列运价划去，表示B1的需求已满足，不需要继续调运(即x21=3=min(a2,b1)=min(4,3))。第二步:从上述未划去的单位运价表的元素中找出最小的运价2，即A2把剩余的产品供应给B3；B3每天需要5吨，A2只剩余1吨，因此在上述产销平衡表的(A2,B3)交叉处填上1，划去上述运价表中A2这一行运价，表示A2的产品已分配完毕。表3.6销地产地B1B2B3B4产量A13113107A219284A3741059销量3656第三步:从上述第二步所得的单位运价表未划去的元素中找出最小元素为3。这表示将A1的产品供应B3，A1每天生产7吨，B3尚缺4吨，因此在产销平衡表的(A1,B3)交叉处填上4，由于B3的需求已满足，将单位运价表中的B3这一列运价划去。如此，一步步进行下去，直到单位运价表中所有元素都划去为止，最终在产销平衡表上就可以得到一个初始调运方案。这个方案的总运费为86元，如表3.7所示。销地产地B1B2B3B4产量A1437A2314A3639销量3656两种特殊情况：一是当在中间步骤的未划去的单位运价表中寻找最小元素时，有多个元素同时达到最小，这时从这些最小元素中任意选择一个作为基变量；二是当在中间步骤的未划去的单位运价表中寻找最小元素时，发现该元素所在行的剩余产量等于该元素所在列的剩余销售量。这时在产销平衡表相应的位置填上一个数，而在单位运价表中就要同时划去一行和一列。为了使调运方案中有数字的格仍为（m+n–1）个，需要在同时划去的行或列的任一空格位