第四章 运输问题.ppt

1,第四章运输问题特殊线性规划,2,在经济建设中，经常遇到大宗物资的调运问题，如煤、钢材、粮食等物资的调运。如果在我们考虑范围之内有若干个生产基地和若干消费地点，根据已有的公路网，如何制定调运方案，使总的运费最小。这就是运输问题。运输问题是一个特殊的线性规划问题，特殊在它的约束条件具有特殊的结构。因为运输问题是线性规划问题，因而当然可以用单纯形法来解，又因为它具有特殊性，因而它还具有比单纯形法更为简便的解法表上作业法。这就是我们专门研究运输问题的目的。1运输问题的表示,3,下面我们先通过一个简单的例子来说明运输问题及其模型运输问题的一般描述和运输问题模型的一般形式引例有三家工厂，都将产品运往三个不同的商店（见下图）。每个工厂每周的生产能力和每家商店的平均需求量如下表1、2所示。,工厂1,工厂3,工厂2,商店1,商店3,商店2,表1,表2,4,显然，每周的供应总量与需求总量是相等的，这样的问题就是产销平衡问题。由于运货距离和公路的路况不同，各个工厂运往各商店货物的运输费用是不同的，费用如下表所示。我们的问题是确定由哪家工厂运送多少件产品到哪家商店，使得总费用最小？,单位产品的运输费用（元）,5,在产销平衡条件下，我们也可以把工厂的供应量，商店的需求量和单位产品的运价放在一个表中表示，如下表所示。,6,模型建立决策变量用双下标决策变量Xij表示从第i家工厂（i=1，2，3）运送到每j家商店（j=1，2，3）的数量。目标函数利用运输费用表中的数据，我们希望其值为最小：MinZ=由工厂1运出产品的总费用-3X11+2X12+3X13+由工厂2运出产品的总费用-10X21+5X22+8X23+由工厂3运出产品的总费用-X31+3X32+10X33即：MinZ=3X11+2X12+3X13+10X21+5X22+8X23+X31+3X32+10X33,7,约束条件主要是对工厂的产量约束和商店的销量约束。由于产量与销量相同，因而有：对工厂1必须有X11+X12+X13=50对工厂2必须有X21+X22+X23=70对工厂3必须有X31+X32+X33=20对商店1必须有X11+X21+X31=50对商店2必须有X12+X22+X32=60对商店3必须有X13+X23+X33=30,8,于是，解此问题的线性最优化模型是：MinZ=3X11+2X12+3X13+10X21+5X22+8X23+X31+3X32+10X33X11+X12+X13=50X21+X22+X23=70X31+X32+X33=20X11+X21+X31=50X12+X22+X32=60X13+X23+X33=30Xij0i=1，2，3j=1，2，3,s.t.,9,运输问题的一般形式为：已知有m个生产地点Ai，i=1，2，m，可供应某种物资，其供应量是ai，i=1，2，m。有n个销地Bj，需求量是bj，j=1，2，n。从Ai到Bj运送单位物资的运价为cij，i=1，2，m；j=1，2，n，问如何安排运输可使总运费最小？用Xij表示从Ai到Bj的运量，在产销平衡条件下，可知ai=bj。如果ai与bj不等，就称此运输问题为非平衡运输问题。产销平衡运输问题的一般模型为：,10,MinS=cijxijijxij=ai(i=1,2.m)jxij=bj(j=1,2n)ixij0(i=1,2,m;j=1,2,n),s.t.,11,当产大于销即aibj时，运输问题的数学模型可以写为:MinZ=CijXijxijai（i=1，2，m）xij=bj（j=1，2，n）xij0（i=1，2，m；j=1，2，n）,12,由于总的产量大于销量，就要考虑每个产地的多余物资就地储存的问题。这可以理解为将所有产地的剩余物资运送至一个假想的销地Bn+1，运费为0，这时的总费用与没有假想之前的总费用是一致的，故MinZ=MinZ。因此解决这种问题的办法是增加一个假想的销地Bn+1，它的需求量是ai-bj，就可以将产大于销的问题转化为产销平衡问题。,13,当销大于产即aibj时，和产大于销类似，增加一个虚拟的产地Am+1，它的产量设为bj-ai，该产地到各个销地的单位运输费用为0，这样得到的最优解和没有虚拟之前是一致的，因而也可以将它转化为产销平衡问题。通过上述讨论可知，对于产销不平衡的问题，我们总是可以通过增加假想的销地和虚拟的产地将其化为产销平衡问题。因此我们只要解决了产销平衡问题，也就可以解决产销不平衡的问题了。下面我们只考虑产销平衡问题。,14,运输问题数学模型的特点：1：所有约束条件中决策变量的系数均等于1。2：运输问题有有限最优解。3：运输问题约束条件系数矩阵为,A=,111111111111111111,（m+n）（mn）,15,4：运输问题约束条件的系数矩阵中对应于变量Xij的系数向量Pij，其分量除第i个和第m+j个等于1以外，其余的都为零5：对于产销平衡运输问题，由于ai=bj成立，因而其m+n个约束方程并不是独立的。实际上只有m+n-1个是独立的。即约束方程系数矩阵的秩为m+n-1。而且它总存在基可行解。,16,平衡运输问题的求解表上作业法：表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法，其步骤可归纳为：(1)找出初始基可行解(2)求各非基变量的检验数，判别是否达到最优解，如果是最优解，停止。否则转下一步。(3)确定换入变量和换出变量，找出新的基可行解。(4)重复(2)(3),直到得到最优解为止。下面我们就按照表上作业法的步骤，先确定初始基可行解，然后进行调整达到最优解。,17,2初始基可行解,下面以一个例子来说明找初始基可行解的方法，下图表示一个运输问题的产销平衡表和单位运价表(二表合一)。（单位：元/吨吨）,18,一般来说，找运输问题的初始基可行解主要有三种方法，下面我们依次来说明。1：西北角法(1)从图的西北角开始，填入a1与b1较小的值b1=3，即从A1运给B13吨货物，B1已经满足，划去b1列。,19,（2）向a1，b1较大方向移动一格（或向右，或向下）此时向右移动一格（A1，B2）B2需要6吨，而A1只有4吨，在（A1，B2）处填4，A1已发完，划去A1行。,20,（3）继续进行,21,（4）继续进行,22,（5）继续进行,23,（6）继续进行,24,（7）得到初始方案：X11=3，X12=4，X22=2，X23=2，X33=3，X34=6，总运费=3*3+11*4+9*2+2*2+10*3+5*6=135（元）,25,2:最小元素法用西北角法很容易得到初始基可行解，但是得到的解往往离最优解相差很远。我们通常希望就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小，一直到给出初始基可行解为止。这种方法称为最小元素法。仍以刚才的例子来看。,26,（1）从最小元素1开始，即A2优先满足B13个单位，B1已经满足，划去B1列,27,（2）再从最小元素2开始，即A2优先满足B31个单位，A2已经满足，划去A2行，,28,（3）再从最小元素3开始，即A1优先满足B34个单位，B3已经满足，划去B3列，,29,（4）再从最小元素4开始即A3优先满足B26个单位，B2已经满足，划去B2列,30,（5）再以最小元素5开始，A3满足B43个单位，A3已满足，划去A3行。,31,（6）最后以元素10开始，A1满足B43个单位，A1和B4都满足，划去A1行和B4列。,32,（7）得到初始方案：X13=4，X14=3，X21=3，X23=1，X32=6X34=3总运费=3*4+10*3+1*3+2*1+4*6+5*3=86（元）,33,3：差值法（伏格尔法）最小元素法的缺点是：为了节省一处的费用，有时造成其它处要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小费用就近供应，就考虑次小费用，这就有一个差额，差额越大，说明不按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小调运方案。基于此，伏格尔法的步骤是：每次从当前运价表上，计算各行各列中最小费用与次小费用这两个运价的差值，优先取最大差值的行或列中最小的运价来确定运输关系，直到求出初始方案。,34,仍然考虑先前的例子,伏格尔法的步骤如下：,35,（1）先分别计算出各行各列最小费用与次小费用的差额，并填入该表的最右列和最下行。,36,（2）从行差额和列差额中选出最大者，选择它所在的行或列中的最小元素所在的格作为优先的运输方案。在这里优先选A3满足B26个单位，B2列已满足，划去B2列。,37,（3）计算剩余元素的行差额和列差额，并选出最大者，选择它所在的行或列中的最小元素所在的格作为优先的运输方案。在这里优先选A3供应B43个单位，A3行已满足，划去A3行。,38,（4）继续进行。在这里优先选A2供应B13个单位，B1列已满足，划去B1列。,39,（5）继续进行,40,（6）继续进行,41,（7）继续进行得最终结果为：,42,（8）得到初始方案：X13=5，X14=2，X21=3，X24=1，X32=6，X34=3总运费=3*5+10*2+1*3+8*1+4*6+5*3=85（元）,43,西北角法得到初始方案：X11=3，X12=4，X22=2，X23=2，X33=3，X34=6，总运费=3*3+11*4+9*2+2*2+10*3+5*6=135（元）最小元素法得到初始方案：X13=4，X14=3，X21=3，X23=1，X32=6，X34=3总运费=3*4+10*3+1*3+2*1+4*6+5*3=86（元）差值法得到初始方案：X13=5，X14=2，X21=3，X24=1，X32=6，X34=3总运费=3*5+10*2+1*3+8*1+4*6+5*3=85（元）,44,需要注意的是三种方法给出的初始方案均是运输问题的基可行解。这是因为在产销平衡表上填了m+n-1个数字，即给出了m+n-1个基变量的值，而且这m+n-1个基变量对应的系数列向量是线性独立的。由以上可见，三种方法除了在确定供求关系的原则不同外，其余步骤相同，伏格尔法确定的初始基可行解比最小元素法和西北角法确定的初始基可行解都更接近最优解。本例中伏格尔法给出的初始解就是最优解。,45,3闭回路法上节介绍的三种方法都可以给出运输问题的初始基可行解，但这个初始基可行解未必是最优解。判断它是否是最优解的方法是计算空格(非基变量)的检验数，因为运输问题的目标函数是要求实现最小化，因而所有的检验数大于等于零时基可行解为最优解。闭回路方法就是求检验数的一个方法。闭回路方法是在初始调运方案表中，从任意空格出发，沿着纵向或横向行进，遇到适当填有数据的方格后90度转弯，继续行进，总能回到原来空格。这个封闭的曲线称为闭回路。可以证明：每个空格对应着唯一的闭回路。,46,下面以前面用最小元素法得到的初始调运方案为例作闭回路。对于A1和B1交叉处的空格，它的闭回路如下表所示。,47,再如对于A1和B2交叉处，它的闭回路如下表所示。,48,A3和B1交叉处的空格的闭回路为：,49,用闭回路法计算非基变量（空格点）的检验数的计算方法是：空格Xij的检验数=偶数次拐角点运价之和减去奇数次拐角点运价之和，如(A1，B1)处的检验数为：3-3+2-1=1,50,用同样的方法可以计算出其余各个空格的检验数(基变量的检验数为0)，括弧中数字，列表如下：,51,要判断一个调运方案是否已是最优，就要判断方案所对应的基础可行解是否最优。在单纯形法中，根据非基变量（空格）的检验数来判别。若检验数中没有负值，则已求得最优。当在表中空格处出现负检验数时，表明调运方案不是最优解，这时就要进行调解。当有两个和两个以上的负检验数时，一般选其中最小的负检验数，以它对应的空格作为调入格。调入的方法是选择最小的负检验数空格所对应的变量为进基变量，在进基变量的回路中，比较奇数拐角点的运量，选择一个具有最小运量的基变量作为出基变量，并调整运量=min(奇数拐角点的运量)。,52,在上述表中，(A2,B4)空格处的检验数为负，以它为进基变量，它的闭回路如下表所示。,53,奇数拐点处运量的最小值为t=min(3,1)，因而为了保持平衡，将奇数拐点处的运量减去t，偶数拐点处的运量加t，调整后的运输方案如下表所示,54,调整以后，再计算各个空格的检验数，如果所有的检验数均大于等于零，则这个运输方案就是最优解；如果还有某个空格的检验数为负数，则再以这个空格为调入格，作相应的基变换，直到所有的检验数为非负。这里上述得到的表中所有的检验数为非负，因而上述运输方案是最优方案。,在闭回路法中，为了计算一个空格点处的检验数，就要画出该空格的闭回路，当空格点较多时，计算很繁。此时我们还可以用另外一种方法计算每个空格的检验数，这就是位势法,55,位势法的基本思想是：设一组新的变量ui和vj(i=1,2,m;j=1,2,n)是对应运输问题的m+n个约束条件的对偶变量，B是原问题的初始基矩阵，则有单纯形法知而每个决策变量Xij的系数向量所以有，于是检验数当然基变量的检验数为0，因而所以我们可以根据基变量对应的单位运输费用算出ui与vj的值，再根据ui与vj的值算出非基变量的检验数。,56,用最小元素法得到的初始调运方案(下表)，我们可以根据基变量对应的单位运输费用计算出ui和vj。计算方程是：u1+v3=4；u1+v4=3；u2+v1=3；u2+v3=1；u3+v2=6；u3+v4=3.六个方程有七个未知数，因此有一个为自由变量，通常我们令u1=0，此时得到下表,57,然后根据ui和v