管理运筹学讲义 第3章 运输问题6学时

第三章运输问题TransportationProblem,3.1运输问题的数学模型3.2表上作业法3.3运输问题的变体3.4应用举例,运输问题是一种特殊的线性规划问题,需用一种更为简单且特殊的方法(表上作业法)来求解.,运输问题:人们在从事生产活动中，不可避免地要进行物资的调运工作。如某时期内将生产地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，应如何制定一个运输方案，使总的运输费用最小。,3.1运输问题的数学模型,一、引例例3-1：现有A1，A2，A3三个产粮区，可供应粮食分别为10，8，5（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需要量分别为5，7，8，3（万吨）。产粮地到需求地的运价如表31所示，问如何安排一个运输计划，使总的运输费用最少。,运价表（元/吨）,表31,3.1.1运输问题的数学模型,解:设xij(i=1,2,3；j=1,2,3,4)为i个产粮地运往第j个需求地的运量，这样得到下列运输问题的数学模型：,运量应大于或等于零（非负要求），即:,Minz=3x11+2x12+6x13+3x14+5x21+3x22+8x23+2x24+4x31+x32+2x33+9x34,xij0,i=1,2,3;j=1,2,3,4,有些问题表面上与运输问题没有多大关系，但经过转换，也可以建立与运输问题形式相同的数学模型.,例3-2：有三台机床加工三种零件，计划第i台的生产任务为ai（i=1，2，3）个零件，第j种零件的需求量为bj（j=1，2，3），第i台机床加工第j种零件需要的时间为cij，如表3-2所示。问如何安排任务使总的加工时间最少？,表32,解：设xij为第i机床加工第j种零件的数量，则有：,二、运输问题的一般数学模型形式,设有m个产地（记作A1，A2，,Am），生产某种物资，其产量分别为a1,a2，am；有n个销地（记作B1，B2，Bn），其需要量分别为b1,b2，bn；且产销平衡，即。从第i个产地到j个销地的单位运价为cij，在满足各地需要的前提下，求总运费最小的调运方案。,设xij(i=1,2,，m；j=1,2,n)为第i个产地到第j个销地的运量，产销平衡运输问题的数学模型为：,3.1.2运输问题数学模型的特征,一、运输问题数学模型的几个假设每一个出发地都有一定的供应量（supply）配送到目的地，每一个目的地都有一定的需求量（demand），接收从出发地发出的产品。几个所谓的假设分别为：需求假设；可行解特性；成本假设；整数解性质。,（1）需求假设：每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之相类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足，即:总供应量总需求量。（2）可行解特性:当且仅当供应量的总和等于需求量的总和时，运输问题才有可行解。,（3）成本假设:从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系，因此这个成本就等于配送的单位成本乘以所配送的数量。（4）整数解性质:只要它的供应量和需求量都是整数，任何有可行解的运输问题必然有所有决策变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件。,二、运输问题数学模型的特征,（1）运输问题一定有有限最优解,（2）所有结构约束条件都是等式约束（3）各产地产量之和等于各销地销量之和,其系数列向量的结构是：,（4)运输问题约束条件的系数矩阵特点,3.1.3运输问题的解,一、基可行解的满足条件由于运输问题是一种线性规划问题，为了进行迭代计算，要求每步得到的运输方案X=(xij)是它的基可行解，即满足以下两点要求。（1）解X必须满足模型中所有约束条件；（2）基变量对应的约束方程组的系数列向量线性无关；（3）非零变量的个数不大于独立的约束方程的个数，即不大于m+n-1个，从而在运输表上填有数字的格子数不大于m+n-1个；（4）为使迭代顺利进行，基变量的个数在迭代过程中应保持为m+n-1个。,下表中填有数字的格为基变量，它们对应的约束方程组的系数列向量线型无关：,【定理1】设有m个产地n个销地且产销平衡的运输问题，则基变量数为m+n-1。,证:因为产销平衡，即，将前m个约束方程两边相加得,再将后n个约束相加得,显然前m个约束方程之和等于后n个约束方程之和，则该m+n个约束方程是现性相关的，系数矩阵:,中任意m+n阶行列式等于零，取第一行到m+n1行与对应的列（共m+n-1列）组成的m+n1阶子式,故r(A)=m+n1,所以运输问题有m+n1个基变量。,为了在mn个变量中找出m+n1个变量作为一组基变量，就是要在A中找出m+n-1个线性无关的列向量，下面引用闭回路的概念寻找这些基变量。,为一个闭回路，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。在表33及表34中的变量组构成两个闭回路。,x23,x43,x11,x12,x25,x31,x42,表33,表33中闭回路的变量集合是x11,x12,x42,x43,x23,x25,x35,x31共有8个顶点，这8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。,二、闭回路的求法,表34,一条回路中的顶点数一定是偶数，回路遇到顶点必须转90度与另一顶点连接，表33中的变量x32及x33不是回闭路的顶点，只是连线的交点。,表34中闭回路是,例如变量组,A不能组成一条闭回路，但A中包含有闭回路,B的变量数是奇数，显然不是闭回路，也不含有闭回路；,【定理2】若变量组B包含有闭回路，则B中的变量对应的列向量线性相关。,证:由线性代数知，向量组中部分向量组线性相关则该向量组线性相关，显然，将C中列向量分别乘以正负号线性组合后等于零(可从前的例子中看出线性组合为0)，即,因而C中的列向量线性相关，所以B中列向量线性相关。,由定理2可知，当一个变量组中不包含有闭回路，则这些变量对应的系数向量线性无关。求运输问题的一组基变量，就是要找到m+n1个变量，使得它们对应的系数列向量线性无关，由定理2，找这样的一组变量是很容易的，只要m+n1个变量中不包含闭回路，就可得到一组基变量。因而有：,【定理3】m+n1个变量组构成基变量的充要条件是它不包含任何闭回路。,定理3告诉了一个求基变量的简单方法，同时也可以判断一组变量是否可以作为某个运输问题的基变量。这种方法是直接在运价表中进行的，不需要在系数矩阵A中去寻找，从而给运输问题求初始基可行解带来极大的方便。,例3-3：m=3,n=4，在运价表Cij的格子的右上方填上相应的xij，如表3-5所示。,表35,这个运输问题的基变量数目是3+41=6。变量组中：有7个变量，显然不能构成一组基变量，又如：中有6个变量，但包含有一条闭回路：故不能构成一组基变量。变量组：有6个变量且不含有任何闭回路，故可以构成此问题的一组基变量。,作业：,本节介绍了具有m个产地n个销地的平衡运输问题时：1.具有m+n1个基变量;2.闭回路的概念;3.怎样判断m+n1个变量是否构成一组基变量。,.2表上作业法,表上作业法也称为运输单纯形法，是直接在运价表上求最优解的一种方法，它的步骤是：第一步：求初始基行可行解（初始调运方案），常用的方法有最小元素法、元素差额法（Vogel近似法）、左上角法。第二步：求检验数并判断是否得到最优解，常用求检验的方法有闭回路法和位势法，当非基变量的检验数ij全都非负时得到最优解，若存在检验数lk0，说明还没有达到最优，转第三步。第三步：调整运量，即换基，选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步。,例-4某公司有三个生产同类产品的加工厂（产地），生产的产品由四个销售点（销地），各加工工厂的生产量，各销售点的销售量（假定单位均为吨）以及各加工工厂到各销售点的单位运价（元/吨）如下表所示，问产品如何调运才能使总运量最小？,上述问题属产销平衡运输问题（为48）。,表3-7,现用xij表示由第i个加工厂运往第j个销售点的物品数量，则可得该问题的数学模型如下：,3.2.1求出初始基可行解,一、最小元素法最小元素法的思想是就近优先运送，即优先满足最小运价Cij对应的变量xij的赋值。然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到安排完所有的供销业务,得到一个完整的调运方案为止,就得到了一个初始调运方案或初始基可行解。,最小元素法,8,2,10,14,8,6,表3-8,8,2,10,14,8,6,初始解：x13=10，x14=6,x21=8,x23=2，x32=14,x34=8Z（0）=246,二、西北角法(优先满足西北角上空格的赋值),初始解：x11=8，x12=8，x22=6，x23=4，x33=8，x34=14Z（0）=372,8,8,6,4,8,14,表3-9,三、运费差额法（Vogel近似法）最小元素法只考虑了局部运输费用最小，对整个产销系统的总运输费用来说可能离最优值较远。有时为了节省某一处的运费，而在其它处可能运费很大。因此，运费差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额(罚数)，如果差额很大，就选最小运价先调运，否则会增加总运费。,基于以上想法，运费差额法求初始基可行解的步骤：第一步：求出每行次小运价与最小运价之差，记为ui（产地的罚数），i=1,2,m；同时求出每列次小运价与最小运价之差，记为vj（销地的罚数），j=1，2，n；第二步：找出所有行、列差额的最大值，即L=maxui，vj，差额L对应行或列的最小运价处优先调运；第三步：这时必有一列或一行调运完毕，在剩下的运价中再求最大差额，进行第二次调运，依次进行下去，直到最后全部调运完毕，就得到一个初始调运方案。用运费差额法求得的基本可行解更接近最优解，所以也称为近似方案。,沃格尔法,14,12,表3-10,初始解：x12=12,x14=4,x1=8,x4=2,x32=14，x34=Z（0）=,求运输问题的初始方案还有很多方法，如左下角法、右上角法等。常用的方法是Vogel近似法、最小元素法。,求出一组基可行解后，判断是否为最优解，仍然是用检验数来判断，记xij的检验数为ij由第一章知，求最小值的运输问题的最优判别准则是：所有非基变量的检验数都非负，则运输方案最优（即为最优解）。求检验数的方法有两种，闭回路法和位势法。,3.2.2解的最优性检验,一、闭回路法求检验数,求某一非基变量(空格)的检验数的方法是：在基本可行解矩阵中，以该非基变量为起点，以基变量为其它顶点，找一条闭回路，由起点开始，分别在顶点上交替标上代数符号+、-、+、-、，以这些符号分别乘以相应的运价，其代数和就是这个非基变量的检验数。(只要求得的基变量是正确的且数目为m+n1，则某个非基变量的闭回路存在且唯一，因而检验数唯一。),8,2,10,14,8,6,最小元素法给出的初始表来求检验数：,1,2,1,-1,10,12,表3-11,二、对偶变量法（位势法)求检验数,（1）原理分析位势法求检验数是根据对偶理论推导出来的一种方法。设平衡运输问题为:,设前m个约束对应的对偶变量为ui,i=1,2,m，后n个约束对应的对偶变量为vj,j=1,2,n则运输问题的对偶问题是:,加入松驰变量ij将约束化为等式:,ui+vj+ij=cij,记原问题基变量XB的下标集合为I，由第二章对偶性质6知，原问题xij的检验数是对偶问题的松弛变量ij的一组基本解。当（i，j）时ij=0，因而有,解上面第一个方程，将ui、vj代入第二个方程求出ij。,（2）用位势法求检验数的步骤,对初始调运方案，定义一组新的变量（对偶变量）ui和vj(i=1,2,m;j=1,2,n)，即在在运输表上增加位势列和位势行。称ui与vj为相应的各行与各列的位势。计算位势。对于基变量xij有：ui+vj=cij计算空格的检验数（基变量的检验数为零）非基变量的检验数为：,0,2,3,1,-4,9,10,1,2,1,-1,10,12,运用位势法对沃格尔法求出的初始表求检验数。,表3-12,3.2.3调整运量,前面讲过，当某个检验数小于零时，基可行解不是最优解，总运费还可以下降，这时需调整运输量，改进原运输方案，使总运输费用减少，改进运输方案的步骤是：第一步：确定进基变量。第二步：确定出基变量。在进基变量xik的闭回路中，将标有偶数或负号顶点的最小运量作为调整量，对应的基变量为出基变量。（打上“”以示作为非基变量。）第三步：调整运量。在进基变量的闭回路中标有偶数或正号的变量中加上调整量，标有奇数或负号的变量减去调整量，其余变量不变，得到一组新的基可行解，然后求所有非基变量的检验数重新检验,直到得出最优解。,对最小元素法得到的解（表3-11）进行改进。,表3-11,对最小元素法得到的解（表3-11）进行改进。,-1,对最小元素法得到的解（表3-11）进行改进。,对最小元素法得到的解（表3-11）进行改进。,8,2,12,14,8,4,Z（2）=246+2（-1）=244,8,2,12,14,8,4,0,2,2,2,-3,8,9,0,2,2,1,9,12,再用位势法继续求检验数,3.2.4调整运量,一、换入变量的选取；二、运输问题的多重最优解；三、退化的解决方法。,本节讲解了平衡运输问题的求解方法：表上作业法表上作业法主要分三个步骤：1.求初始运输方案，用最小元素法或运费差额法（Vogel近似法）2.求检验数，用闭回路法或位势法3.调整运量，用闭回路法,运输问题的变体,Exit,.3运输问题的变体,.3.求极大值问题.3.不平衡运输问题.3.需求量不确定的运输问题,设数学模型为：,3.3.1求极大值的运输问题,第一种方法：将极大化问题转化为极小化问题。设极大化问题的运价表为C=（Cij）mn，用一个较大的数M（MmaxCij）去减每一个Cij得到矩阵C/=（Cij）mn，其中C/ij=MCij0,将C/作为极小化问题的运价表，用表上作业法求最优解，目标函数值为：,例3-5：下列矩阵C是Ai（i=1，2，3）到Bj的吨公里利润,运输部门如何安排运输方案使总利润最大。,8149,用最小元素法求初始方案得,11=8,12=4,21=2,23=2全部非负,得到最优运输方案X,最大利润：Z=89+1010+68+54=240,第二种方法:所有非基变量的检验数ij0时最优，求初始运输方案可采用最大元素法.如上例,用最大元素得到的初始运输方案:,8149,求检验数:11=8,12=4,21=2,23=2,全部非正,得到最优解运输方案,结果与第一种方法相同。,3.3.2不平衡运输问题,不平衡运输问题：当总产量与总销量不相等时,称为不平衡运输问题。这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。,一、当总产量大于销量,数学模型为,由于总产量大于总销量，必有部分产地的产量不能全部运送完，可增加一个假想的销地Bn+1,由于实际并不存在，实际上是就地库存。设由产地运送到假想销地的物品数量为xi,n+1（相当于松弛变量）（i=1,2，m），则假想销地的销量bn+1为：,bn+1作为一个虚设的销地Bn+1的销量，各产地Ai到Bn+1的运价为零，即Ci，n+1=0,（i=1，m）。则平衡问题的数学模型为：,具体求解时,只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可,当销大于产时,即,数学模型为,二、当总产量小于销量,由于总销量大于总产量,故一定有些需求地未能完全满足,这时虚设一个产地Am+1，产量为：,xm+1,j是Am+1运到Bj的运量，也是Bj不能满足需要的数量。Am+1到Bj的运价为零,即Cm+1,j=0(j=1,2,n),销大于产平衡问题的数学模型为：,具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1，i即可。,例3-6:确定如下运输表总运费最小的调运方案。,解:增加一假想销地B5,因为有：,例3-7：求下列表中极小化运输问题的最优解。,所以是一个产大于销的运输问题。表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180160=20，Ci5=0，i=1，2，3，4。表的右边增添一列，这样我们可得新的运价表：,下表为计算结果。可看出：产地A4还有20个单位没有运出。,上例中，假定B1的需要量是20到60之间，B2的需要量是50到70，试求极小化问题的最优解。,3.4.3需求量不确定的运输问题(扩展),先作如下分析：（1）总产量为180，B1，B4的最低需求量20+50+35+45=150，这时属产大于销；（2）B1，B4的最高需求是60+70+35+45=210，这时属销大于产；（3）虚设一个产地A5，产量是210180=30，A5的产量只能供应B1或B2。,（4）将B1与B2各分成两部分，的需求量是20，的需求量是40，的需求量分别是50与20，因此必须由A1，A4供应，可由A1、A5供应。（5）上述A5不能供应某需求地的运价用大M表示，A5到j的运价为零。得到下表的产销平衡表。,得到这样的平衡表后，即可应用QSB软件计算得到最优方案。,表中x131=0是基变量,说明这组解是退化基本可行解,空格处的变量是非基变量。B1，B2，B3，B4实际收到产品数量分别是50，50，35和45个单位。,例3-8P&T公司的配送问题P&T公司是一家由家族经营的小公司。它收购生菜并在食品罐头厂中把它们加工成为罐头，然后再把这些罐头食品分销到各地卖出去。这个公司的一个主要产品是豌豆罐头。这些豌豆罐头在三个食品罐头厂加工，然后用卡车把它们运送到美国西部的四个分销仓库。如下图所示：,3.4应用举例,公司目前做法-当前的运输策略：,许多年来，公司一直用下面的策略将每个罐头加工工厂的罐头食品运送到各个仓库。当前的运输策略：（1）因为贝林翰的罐头厂距离仓库最远，所以把它的产品运送到最近的一个仓库。也就是萨克拉门托的那个仓库。如果还有剩余的话，就把它们运送到盐湖城的仓库中去。（2）因为澳尔巴古的仓库距离食品罐头厂最远，所以就要从最近的一个罐头厂（艾尔贝李的罐头厂）中运送产品到澳尔巴古。如果还有剩余的话，就要运送到赖皮特城的仓库中。（3）用尤基尼的罐头厂满足其他仓库的剩余需求。,公司目前做法,对于即将来临的收获季度，每一个罐头厂的产量都进行了估计，并且每一个仓库都从豌豆罐头总供应量中分配了一定的比例。当前的运输计划如下：,至,单位：车,P&T公司的单位卡车的运输成本,单位：元,即将来临的季节中，当前运输计划下的总运输成本：总的运输成本=75（464元）5（352元）65(416元）55（690元）十15（388元）85（685元）165，595（元）,改进运输计划!,最优解如下*起至销点发点1234-102005528045003007030总费用为152535元,费用的减少额=165，595152，535=13，060元,例3-9:某厂按合同规定须于当年每个季度末分别提供10,15,25,20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如下表所示。又如果生产出来的柴油机当季交不出货的，每台每积压一个季度需储存、维护等费用0.15万元。要求在完成合同的情况下，做出使该厂全年生产（包括储存、维护）费用最小的决策。,I10.810.9511.1011.25II11.1011.2511.40III11.0011.15IV11.30,i,j,IIIIIIIV,cij值（万元）,设用ai表示该厂第i季度的生产能力，bj表示第j季度的合同供应量，则问题可写成：,minz=cijxij,44i=1j=1,xijaixijbixij0,4j=1,4i=1,例3-10.某航运公司承担六个港口城市、的四条固定航线的物资运输任务。已知各条航线的起点、终点城市及每天航班数见下表1。假定各条航线使用相同型号的船只，又各城市间的航程天数见下表2。又知每条船只每次装卸货的时间各需天，则该航运公司至少应配备多少条船，才能