运输问题

一、运输问题(TransportationProblem)以知有m个生产地点(source)Ai，i=1，…，m，可供应某种物资，其供应量（产量）(supply)为ai，i=1，…，m；有n个销售地点(destination)Bj，j=1，…，n，需要该种物资，其需要量（产量）(demand)为bj，j=1，…，n；从Ai到Bj运输单位物资的运价（单价）为cij；设Σai=Σbj，这些数据可汇总于如下产销平衡表，现要制定一个使总运费最小的调运方案。第一节运输问题及其数学模型销地产地B1B2…Bn产量A1c11c12…c1na1A2c21c22…c2na2………………Amcm1cm2…cmnam销量b1b2…bnΣaiΣbj产销平衡表(costandrequirementtable)若用xij表示从Ai到Bj的运量，在产销平衡的条件下，要求得总运费最小的调运方案，其数学模型如下（模型Y）mnijiji=1j=1nijij=1mijji=1ijminf=cxx=ai=1,...,mx=bj=1,...,nx=0,i=1,...,m;j=1,...,n该模型中，包含了m×n个变量，（m+n）个约束条件，且有特殊结构的系数矩阵，即mnmmnnxxxxxxxxx21222211121111...111...1m11...1111111n111行行上述矩阵的列向量可用pij来描述，显然pij中除第i个元素和第m+j个元素为1以外，其余元素均为0。一、运输问题数学模型的基本概念–对于运输问题的数学模型（模型Y）有如下定理。–定理3.1运输问题的数学模型必有最优解。–定理3.2运输问题约束方程系数矩阵A的秩为m+n－1，即R（A）=m+n－1。第二节表上作业法----(TransportationSimplexMethod)定义3.1（闭回路的定义）在运输问题的调运表中，凡能排成xi1j1，xi1j2，xi2j3，…，xisjs，xisj1形式的变量集合，称为一个闭回路(closedpath,stepping-stone-path)，其中诸变量称为该闭回路的顶点(corner)。闭回路有如下特点：①每个顶点都是转角；②每行或每列只有且仅有两个顶点；③每个顶点的连线都是水平的或垂直的。B1B2B3B4B5B6B7A1x11x12x13x14x15x16x17A2x21x22x23x24x25x26x27A3x31x32x33x34x35x36x37–定理3.3运输问题m+n－1个变量xi1j1，xi2j2，…，xisjs（s=m+n－1）构成某一基可行解的基变量的充要条件是：不包含以这些变量为顶点的闭回路。–该定理能帮助我们简便地求出基可行解或判别某一可行解是否为基可行解。–表上作业法基本步骤（1）确定初始基可行解（2）最优解的判定；（3）基可行解的转换。（一）初始基可行解的确定–确定初始基可行解的方法很多，如最小元素法、伏格尔法、西北角法等。这里仅介绍既常用又简便的方法——最小元素法(minimumcostmethod)。–这种方法的基本思想就是就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小。一直到求出初始基可行解为止。二、表上作业法最小元素法的步骤1)列出如表3—6所示的调运表（包括单价、产量与销量）；2)在调运表中找出一个单位运价最小的格子，在相应的运量位置上填上尽可能大的数（必须满足约束条件）。3)在填有数字的格子所在行或者列运量应该为0的位置上打“×”，（即表示该运量为0，相应的变量为非基变量）且只能在行或列的方向上打“×”，不能同时在两个方向上打“×”；4)在没有填数，也未打“×”的格子重复上述（2）、（3）步；5)最后剩下的一行或列只能填数，不能打“×”。–例3.2设有某物资从A1，A2，A3处运往B1，B2，B3，B4四个地方，各处供应量、需求量及单位运价见下表。问应如何安排运输方案，才能使总运费最少？销地产地B1B2B3B4产量A1376450A2243320A3838930销量40201525100100销地产地B1B2B3B4产量A120×525503764A220×××202433A3×2010×308389销量40201525（二）最优解的判定(optimalitytesting)–最优解的判定，通常有两种方法，即闭回路法和位势法。1．闭回路法(closedpathmethod)–在表3—6所描述的调运表中，任一非基可变量都可以作出这样的闭回路：该闭回路以选定的非基变量为第一个顶点，其余的顶点都是基变量。可以证明，对于任一非基变量，这样的闭回路只有唯一一条。–在这样的闭回路上，可以对调运方案进行调整，而能使调运方案仍然满足所有约束条件，即满足产销平衡的要求。–在闭回路上，进行一个单位的运量调整所得目标函数的变化即为该非基变量的检验数。若所有非基变量的检验数均大等于零，则问题得到最优解.对表3—6中，所有非基变量的检验数计算如下：x23的检验数σ23=－20，故表3—6中的基可行解不是最优解。非基变量闭回路检验数x12x22x23x24x31x34x12→x13→x33→x32→x12x22→x21→x11→x13→x33→x32→x22x23→x21→x11→x13→x23x24→x21→x11→x14→x24x31→x11→x13→x33→x31x34→x33→x13→x14→x3464－20332．位势法(indexmethod)–位势法原理–对于运输问题minf=CX；AX=b，X≥0–设B为其一可行基，则相应的基可行解的各变量的检验数可用下式计算，即σij=cij－CBB-1pij–又运输问题的对偶问题为maxz=Yb；YA≤C，Y无限制–其中，Y=（u1，…，um，v1，…，vn）为对偶变量，其中的各分量分别对应m+n个条件。–根据对偶理论有Y=CBB-1–因此有σij=cij－Ypij–又因为，pij中除第i个元素和第m+j个元素为1以外，其余元素均为0，即pij=ei+em+j–所以有σij=cij－Ypij=cij－（u1，…，um，v1，…，vn）pij=cij－（ui+vj）–而所有基变量的检验数等于零，因此有cij－（ui+vj）=0–即ui+vj=cij（i，j）∈I（基变量下标集）–由于ui对应与调运表中的第i行，称其为第i行的行位势(rowindex)；vj对应与调运表中的第j列，称其为第j列的列位势(columnindex)；–位势法的具体办法如下：（1）在调运表中，对于每一个基变量都按公式ui+vj=cij列出一个位势方程，形成位势方程组；（2）任决定其中一个位势的数值，然后求出其它位势的数值；（3）按公式σij=cij－（ui+vj）计算非基变量的检验数，若所有非基变量的检验数均大等于零，则调运表中的基可行解就是最优解，否则不是最优解；•用位势法对下表中的基可行解进行最优性检验。u2+v1=2u3+v2=3u3+v3=8•位势方程组为u1+v1=3u1+v3=6u1+v4=4销地产地B1B2B3B4产量行位势A12052550u13764A22020u22433A3201030u38389销量40201525列位势v1v2v3v4–取u1=0，解上述方程组得u1=0u2=－1u3=2–各非基变量的检验数为σ12=c12－（u1+v2）=7－（0+1）=60σ22=c22－（u2+v2）=4－（－1+1）=20σ23=c23－（u2+v3）=3－（－1+6）=－20σ24=c24－（u2+v4）=3－（－1+4）=0σ31=c31－（u3+v1）=8－（2+3）=30σ34=c34－（u3+v4）=9－（2+4）=30–由于σ23=－20，故表中基可行解不是最优解。v1=3v2=1v3=6v4=4（三）基可行解的转换(convertBFsolution)–当调运表中，仍然有非基变量的检验数为负，则说明问题还没有得到最优解，需要进行基可行解的转换。具体办法为：（1）以某一个σij0（若有多个则取最小者）对应的变量xij作为进基变量；（2）以所选的xij为第一个顶点作闭回路，该闭回路除xij外，其余顶点都是基变量，并排序；（3）以顺序为偶数的顶点的基变量最小值min｛（xij）k|k为偶数｝作为调整量，在顺序为奇数的顶点上加上该调整量，在顺序为偶数的顶点上减去该调整量，即可得到新的基可行解。销地产地B1B2B3B4产量A120255025503764A220155202433A32010308389销量40201525这里对表3—6中的基可行解进行转换。由于σ23=－20，故以x23为进基变量，并以x23为第一个顶点作闭回路，如表3—10。•新基可行解的位势方程组为u1+v1=3u1+v4=4•取u1=0，解上述方程组得u1=0u2=－1u3=4•各非基变量的检验数为σ12=7－（0－1）=80σ13=6－（0+4）=20σ22=4－（－1－1）=60σ24=3－（－1+4）=0σ31=8－（4+3）=10σ34=9－（4+4）=10u2+v1=2u2+v3=3u3+v2=3u3+v3=8v1=3v2=－1v3=4v4=4由于所有非基变量的检验数均大等于零，故从表3—11中得到最优解为x11=25，x14=25，x21=15，x23=5，x32=20，x33=10，其它xij=0f*=3×25+4×25+2×15+3×5+3×20+8×10=360此外，由于σ24=0，故此问题有另一最优基可行解。具体求法是在表3—11中，以x24为进基变量作闭回路，进行调整后得到。–由上面分析可知，表上作业法的实质是单纯形方法用于求解运输问题这样一类特殊形式线性规划问题的简化，因而也称它为运输单纯形法。–最后总结表上作业法的解题步骤。（1）编制调运表（包括产销平衡表及单位运价表）；（2）正在调运表上求出初始基可行解；（3）用位势法或闭回路法计算非基变量的检验数。若所有非基变量的检验数≥0，则已得到问题的最优解，停止计算。否则转下一步；（4）选取小于0的检验数中的最小者对应的变量作为进基变量，用闭回路法进行基可行解的转换，得到新的基可行解，转（3）。第三节产销不平衡的运输问题及其求解----TotalSupplynotEqualtoTotalDemand一、产大于销(totalsupplyexceedstotaldemand)–产大于销的运输问题的特征是ΣaiΣbj，其数学模型为：mnijiji=1j=1nijij=1mijji=1ijminf=cxx=ai=1,...,mx=bj=1,...,nx=0,i=1,...,m;j=1,...,n–解此类问题可假想一个销地Bn+1，其需要量为：bn+1=Σai－Σbj；若用xi，n+1表示从Ai到Bn+1的运量，可令ci，n+1=0或等于第Ai产地储存单位物资的费用。因为xi，n+1实际上表示Ai产地没有运出去而库存的物资数量。经处理后，问题变成了产销平衡的运输问题，其数学模型为：这样，m个产地、n个销地的不平衡运输问题，转化成了m个产地、n+1个销地的平衡运输问题，此时可用表上作业法求解。在用最小元素法求解该类问题初始基可行解时，若某列的运价全为零时，则该列最后考虑。mn+1ijiji=1j=1n+1ijij=1mijji=1ijminf=cxx=ai=1,...,mx=bj=1,...,n+1x=0,i=1,...,m;j=1,...,n+1–销大于产的运输问题的特征是ΣaiΣbj，其数学模型为：二、销大于产(totaldemandexceedstotalsupply)mnijiji=1j=1nijij=1mijji=1ijminf=cxx=ai=1,...,mx=bj=1,...,nx=0,i=1