运筹学第三版之第三章运输问题

运输问题(TransportationProblem)是一类特殊的线性规划问题.最早研究这类问题的是美国学者希奇柯克(Hitchcock)，后来由柯普曼(Koopman)详细加以讨论。,在第一章线性规划模型的应用中，我们介绍了运输问题，建立了其数学模型，这类问题属线性规划问题，当然可以使用单纯形法进行求解，但是，由于运输问题的约束系数矩阵有其特殊的结构和性质，因而有比单纯形法更有效的方法来求解。,第三章运输问题,运输问题的数学模型,表上作业法,产销不平衡的运输问题,求初始基可行解的方法：西北角法、最小元素法、元素差额法,基可行解的改进方法：闭回路调整法、位势法,例：某运输问题的资料如下：,一、运输问题的数学模型,试制定一个调运方案，使得总运费最省？,数学模型的一般形式已知资料如下：,当产销平衡时，其模型如下：,(3.1),当产大于销时，其模型是：,(3.2),当产小于销时，其模型是：,(3.3),运输问题的特征：1、平衡运输问题必有可行解，也必有最优解；,证设,m行,n行,第i行,第m+j行,3、运输问题的基可行解中应包括m+n1个基变量。,前2m行,后n行,闭回路：凡是能排列成,形式的变量,集合，若用一条封闭折线将它们连接起来形成的图形称为一个闭回路，其中诸变量称为闭回路的顶点，连接相邻两个顶点及最后一个顶点与第一个顶点的线段称为闭回路的边。,闭回路具有以下性质：,(1)每一个顶点都是转角点；,基格：闭回路的顶点,闭回路在基格处可以直行，也可以拐弯，在空格处必须直行，不能拐弯。,(2)每一条边都是水平线或垂直线，闭回路是由这些水平线或垂直线构成的一条封闭折线；,(3)每一行(或列)若有闭回路的顶点，则必有两个。,空格：基格外的格。,闭回路的性质：,充要条件是它不含闭回路。,则加入空格后的m+n个格中必含有唯一的闭回路。,二、初始基可行解的求法(表上作业法),运输问题(3.1)的解法主要有图上作业法和表上作业法两种。表上作业法又称为运输单纯形法，它是根据单纯形法的原理和运输问题的特征，设计出来的一种便于在表上运算的方法，作为一种迭代方法，它的主要步骤：,(1)求一个初始基可行解(又称初始调运方案)；(2)判别当前的基可行解是否为最优解，若是，则迭代停止；否则，转下一步；(3)改进当前的基可行解，得新的基可行解，再返回(2),此法是纯粹的人为的规定，没有理论依据和实际背景，但它易操作，特别适合在计算机上编程计算，因而备受欢迎。,1、西北角法（或左上角法）：,遵循的原则：优先安排运价表上编号最小的产地和销地之间(即运价表的西北角位置)的运输业务。,例1设有某物资共有3个产地A1,A2,A3,其产量分别为9,5,7个单位，另有4个销地B1,B2,B3,B4,其销量分别为3,8,4,6,已知由产地Ai运往销地Bj的单位运价见下表，问应如何调运,才能使总运费最省？,1、求初始调运方案：,首先安排产地A1与销地B1之间的运输业务，即从运价表上西北角(或左上角)位置x11开始分配运输量，并使x11取尽可能大的数值。现在产地A1的产量为9,而销地B1的需求量为3.故安排产地A1运送3个单位的货物给销地B1,即取x11=mina1,b1=min3,9=3，当产地A1运出3个单位货物后，还剩9-3=6个单位，此时销地B1的需求量已得到满足，此时A2,A3不可能再运送货物给销地B1了，此时将B1列划去；再在剩下的运价表上，重复上述过程，即决定x12,3,0,6,6,0,2,2,0,3,3,0,1,1,6,0,6,0,0,A1运送6个单位货物给B2,此时A1的供应量为0，划去A1行，B2的需求量为2.用同样的方法得初始基可行解X(0)的各分量为：,相应的目标函数值,2、最小元素法,遵循原则：优先安排单位运价最小的产地与销地之间的运输业务。,依次安排最小元素、次小元素，从而得到一个初始基可行解。用此方法制定出来的调运方案，其总运费一般会比用西北角法制定的调运方案要省。,例2用最小元素法制定例1的初始调运方案。,第1个最小元素为c21=1,此时比较A2的产量和B1的销量此时取其最小值，x21=min5,3=3,则安排A2运送3个单位货物给B1,此时A2剩余2个单位，B1的需求量已满足，将B1列划去；再在剩余表格中找最小元素c24=2,此时令x24=min2,6=2则安排A2运送2个单位货物给B4,则A2的供应量已尽，B4余4个单位，则将A2行划去；再在剩余表格中重复以上过程，最终得初始调运方案。,3,0,2,2,0,4,4,0,3,3,0,5,4,5,0,5,0,0,西北角法与最小元素法的比较,西北角法的最大优点是实现简单，特别适合编制程序上机计算，但缺点是所制定的初始方案往往离最优解较远，后面的调整量较大。而最小元素法的最大优点是制定的初始方案一般离最优解较近，后面调整量较小。但要在一张大型的运价表上每次搜索最小元素，其计算量也是很可观的。当然，当问题的规模不大，用手工计算时，可以通过人的判断力，很快找到最小元素，因此，用手工计算时，一般采用最小元素法求初始调运方案较好。,3、元素差额法,元素差额法是在最小元素法的基础上改进的一种求初始方案的方法，在分配运量以确定产销关系时，不是从最小元素开始，而是从运价表中各行和各列的最小元素和次小元素之差额来确定产销关系，(按最大差额所在行或列中的最小元素安排产地与销地之间的运输业务)因此称为元素差额法。,3,0,6,1,5,1,2,1,1,2,2,1,2,1,2,3,3,5,8,2,2,2,5,0,0,3,4,5,2,2,1,3,0,5,9,7,2,5,0,1,1,0,0,初始调运方案为,1闭回路求检验数,对于给定的调运方案(基可行解)，从非基变量xij出发作一条闭回路，要求该闭回路上其余的顶点均为基变量，并从xij开始将该闭回路上的顶点顺序编号(顺时针或逆时针均可)称编号为奇数的点为奇点，编号为偶数的点为偶点，则xij处对应的检验数为奇点处运价的总和与偶点处运价的总和之差。(理论依据：xij处的运量增加一个单位，则闭回路同行中顶点处运量减少一个单位,同列中顶点处运量增加一个单位，依此类推，直至考虑闭回路所有顶点.),闭回路的做法：从空格出发，遇基格可直行亦可拐弯，遇空格必须直行不可拐弯，目的是保证闭回路的顶点为基格。,最优性判别与基可行解的改进,检验数的求法,3,2,4,3,4,5,用最小元素法求出的例1的初始调运方案见下表,-4,x11的检验数为2-7+2-1=-4,3,2,4,3,4,5,用最小元素法求出的例1的初始调运方案见下表,x13的检验数为10-2+4-9=3,3,3,2,4,3,4,5,用最小元素法求出的例1的初始调运方案见下表,x22的检验数为3-9+7-2=-1,-1,3,2,4,3,4,5,用最小元素法求出的例1的初始调运方案见下表,x23的检验数为4-2+7-9+4-2=2,2,3,2,4,3,4,5,用最小元素法求出的例1的初始调运方案见下表,x31的检验数为8-1+2-7+9-4=7,7,3,2,4,3,4,5,用最小元素法求出的例1的初始调运方案见下表,x34的检验数为5-7+9-4=3,3,3,2,4,3,4,5,用最小元素法求出的例1的初始调运方案见下表,-4,3,-1,2,7,3,2位势法求检验数,首先写出运输问题的对偶问题,由于运输问题的约束条件共有m+n个，前m个是关于产地的产量限制，后n个是关于销地销量的限制。因此对偶问题中的对偶变量也应有m+n个，前m个记为u1,u2,um,后n个记为v1,v2,vn,并记,运输问题的对偶问题,单纯形法中有一个重要的规定，即基变量对应的检验数为零，根据这一原理，可以建立关于ui,vj的方程组，可以很快求出ui,vj.,设给定了一个初始调运方案，其基变量为,于是得到如下的方程组,这个方程组共有m+n-1个方程，可以证明此方程有解，而要确定的未知数共有m+n个，故其中必有一个自由未知量，取它为任意常数，就可以把其余的未知量解出来。例如取uij=0,就可以决定其余的ui和vj,3,2,4,3,4,5,用位势法求例1中的初始基可行解对应的检验数,9,5,7,7,5,6,由于闭回路法和位势法中，检验数的定义方式与单纯形法完全一致，因此最优性判别条件也完全一致。注意运输问题中的目标函数是求极小值，于是,定理对于运输问题的一个基可行解，若所有的检验数,则此基可行解必为最优解。,基可行解的改进,确定出基变量的方法利用闭回路调整法：,从进基变量xrs出发作一条闭回路，并从xrs出发将该闭回路上的顶点顺序编号，则调整量为,调整的方法是：在该闭回路上，将奇点处的运量加上，偶点处的运量减去，而表中的其余点处的运量不变，这样得到新的基可行解，,进基变量的选择和单纯形法一样,3,2,4,3,4,5,对例1继续求解,9,5,7,7,5,6,4,3,1,5,9,5,7,7,6,2,3,5,4,3,6,0,9,5,7,7,6,2,3,5,由于检验数全非负，故现有的基可行解即为最优解，且最优调运方案为,1、产大于销：模型,方法是先将原问题变成平衡问题，需假设一个销地(Bn+1)(实际上考虑产地的存量)，,三、产销不平衡的运输问题及其求解方法,模型为：,2、销大于产：同样假设一个产地即可，变化同上。,单位运价表中的单位运价为,40,30,30,20,30,20,20,用最小元素法求初始方案,例题：,已知某运输问题的资料如下表所示,1、表中的产量、销量单位为：吨，运价单位为：元/吨,试求出最优运输方案.,练习1：,2、如将A2的产量改为17，其它资料不变，试求最优调运方案。,解：1、用最小元素法求初始方案,运费为108元/吨,2、用位势法判断：,成本表,u1+v3=5u2+v4=1u1+v4=3u3+v2=2u2+v1=1u3+v4=4令：u10,u10v13u22v21u31v35v43,(ui+vj),cij,表中还有负数，说明没有得到最优解，调整运输方案。,ij,(ui+vj),2,2,2,2,新的运送方案,新的成本表,(ui+vj)1,总的运费105元/吨,表中还有负数，说明没有得到最优解，继续调整运输方案。,cij,(ui+vj)1,(ij)1,cij,(ui+vj)2,(ij)2,表中没有负数，说明已经得到最优解。但有无穷多最优解。,0,成本表,u1+v1=2u2+v4=1u1+v3=5u3+v2=2u2+v1=1u3+v3=7令：u10,u10v12u21v20u32v35v42,(ui+vj),cij,ij,2.,成本表,u1+v3=5u2+v3=2u1+v5=0u2+v4=1u2+v1=1u3+v2=2u3+v4=4令：u10,u10v14u2-3v22u30v35v44v50,(ui+vj),cij,ij,成本表,u1+v1=2u2+v4=1u1+v3=5u3+v2=2u1+v5=0u3+v4=4u2+v3=2令：u10,u10v12u2-3v22u30v35v44v50,(ui+vj),cij,ij,C=75,已知资料如下表所