线性规划运输问题.doc

第四章 运输问题Chapter 4Transportation Problem4.1 运输问题的定义设有同一种货物从m个发地1，2，m运往n个收地1，2，n。第i个发地的供应量（Supply）为si（si0），第j个收地的需求量（Demand）为dj（dj0）。每单位货物从发地i运到收地j的运价为cij。求一个使总运费最小的运输方案。我们假定从任一发地到任一收地都有道路通行。如果总供应量等于总需求量，这样的运输问题称为供求平衡的运输问题。我们先只考虑这一类问题。im1jn1c11c1jc1nnci1cijcincm1cmjcmn图4.1图4.1.1是运输问题的网络表示形式。运输问题也可以用线性规划表示。设xij为从发地i运往收地j的运量，则总运费最小的线性规划问题如下页所示。运输问题线性规划变量个数为nm个，每个变量与运输网络的一条边对应，所有的变量都是非负的。约束个数为m+n个，全部为等式约束。前m个约束是发地的供应量约束，后n个约束是收地的需求量约束。运输问题约束的特点是约束左边所有的系数都是0或1，而且每一列中恰有两个系数是1，其他都是0。运输问题是一种线性规划问题，当然可以用第一章中的单纯形法求解。但由于它有特殊的结构，因而有特殊的算法。在本章中，我们将在单纯形法原理的基础上，根据运输问题的特点，给出特殊的算法。在运输问题线性规划模型中，令X=（x11，x12，x1n，x21，x22，x2n，xm1，xm2，xmn）TC=（c11，c12，c1n，c21，c22，c2n，cm1，cm2，cmn）TA=a11，a12，a1n，a21，a22，a2n，am1，am2，amnT=b=（s1，s2，sm，d1，d2，dn）T则运输问题的线性规划可以写成：min z=CTXs.t. AX=b X0其中A矩阵的列向量aij=ei+em+jei和em+j是m+n维单位向量，元素1分别在在第i个分量和第m+j个分量的位置上。A矩阵中的行与运输网络中的节点对应，前m行对应于发地，后n行对应于收地；A矩阵的列与运输网络中的边对应。运输问题除了用网络表示及线性规划表示外，还可以用运输表表示：12n1c11c12c1ns1x11x12x1n2c21c22c2ns2x21x22x2nmcm1cm2cmnsmxm1xm2xmnd1d2dn表 4.1表的行与发地对应，列与收地对应。第i行与第j列交叉的一格与网络的一条边对应（也就是与线性规划约束矩阵的一列对应），每一格的左上角小方格内的数字表明从相应的发地i到收地j的运价cij，每一格右下角表明从相应的发地i到收地j的运量xij。表右方表明各发地的供应量si，表下方表明各需求第的需求量dj。每一行运量之和表示从该发地运往各收地的运量之和，它应该等于该发地的供应量；同样，每一列运量之和表示从各发地运往该收地的运量之和，它应该等于该收地的需求量。运输问题的网络图、线性规划模型以及运输表之间的关系可以用下表表示：网络图线性规划模型运输表节点发点i约束前m个约束表的行收点j后n个约束表的列边从节点i到节点j变量xij，列向量aij表中的一格例4.1 以下的运输问题线性规划、网络图和运输表表示同一运输问题。minz=8x11+5x12+6x13+7x21+4x22+9x23s.t.x11+x12+x13=15x21+x22+x23=25x11+x21=10x12+x22=20x13+x23=10x11,x12,x13,x21,x22,x230122311525102010856749图4.2123185615x11x12x13274925x21x22x23102010表 4.24.2 运输问题约束矩阵的性质4.2.1 约束矩阵的秩运输问题约束矩阵A的秩为m+n-1。证明：因为A矩阵的前m行和后n行之和分别等于向量（1，1，1），因此秩Am+n。考虑A的一个子矩阵A=a1n，a2n，amn，a11，a12，a1n，即A=删除A中的第m+n行和第m+n列，得到A=容易看出，秩A=m+n-1。由此m+n-1=秩A秩A秩Adj，取xij=dj，并将发地i的供应量改为si-dj，将收地j的需求量改为0；如果si0。由于单纯形叠代在每一步都满足互补松弛条件，因此对于基变量xij0，相应的对偶约束条件ui+vjcij的松弛变量一定等于0，即ui+vj=cij由于基变量一共有m+n-1个，因此对偶问题一共有m+n-1个等式约束，再加上vn=0，一共有m+n个等式，因此可以确定m+n个对偶变量的值，并且由对偶约束等式的特点，可以由vn=0开始，逐个递推求得ui和vj。求出ui、vj的值以后，就可以进一步计算各非基变量的检验数zij-cij=ui+vj-cij。例4.9用对偶变量法计算例4.7中用西北角法得到的初始基础可行解的各非基变量的检验数zij-cij。123411011915u1=8151521312169u2=953193118710u3=1050414131213u4=1325v1=2v2=3v3=7v4=0对于表中的7个基变量，相应的对偶问题的约束条件为：u1+v1=c11=10u1+v2=c12=11u2+v2=c22=12u2+v3=c23=16u2+v4=c24=9u3+v4=c34=10u4+v4=c44=13以及 v4=0从v4=0开始依次可以得到：u4=13-v4=13-0=13u2=9-v4=9-0=9u3=10-v4=10-0=10v2=12-u2=12-9=3v3=16-u2=16-9=7u1=11-v2=11-3=8v1=10-u1=10-8=2在求得各对偶变量ui，vj的值以后，再计算检验数zij-cij=ui+vj-cijz13-c13=u1+v3-c13=8+7-9=+6z14-c14=u1+v4-c14=8+0-15=-7z21-c21=u2+v1-c21=9+2-13=-2z31-c31=u3+v1-c31=10+2-11=+1z32-c32=u3+v2-c32=10+3-8=+5z33-c33=u3+v3-c33=10+7-7=+10z41-c41=u4+v1-c41=13+2-14=+1z42-c42=u4+v2-c42=13+3-13=+3z43-c43=u4+v3-c43=13+7-12=+8将以上结果记在运输表上，得到1234+3+1+1+8-2+6+5-71101191530151521312169455319+1031187105050414131213252515203184这个结果与用闭回路法得到的结果完全相同。例4.10 用对偶变量法计算例4.7中用最小元素法得到的初始基础可行解的各非基变量的检验数zij-cij。123411011915u11511421312169u2453118710u31931414131213u425v1v2v3v4对于表中的7个基变量，相应的对偶问题的约束条件为：u1+v1=c11=10u1+v2=c12=11u1+v4=c14=15u2+v4=c24=9u3+v2=c32=8u3+v3=c33=7u4+v4=c44=13以及v4=0从v4=0开始依次可以得到：u4=13-v4=13-0=13u1=15-v4=15-0=15u2=9-v4=9-0=9v1=10-u1=10-15=-5v2=11-u1=11-15=-4u3=8-v2=8-(-4)=12v3=7-u3=7-12=-5在求得各对偶变量ui，vj的值以后，再计算检验数zij-cij=ui+vj-cijz13-c13=u1+v3-c13=15+(-5)-9=+1z21-c21=u2+v1-c21=9+(-5)-13=-9z22-c22=u2+v2-c22=9+(-4)-12=-7z23-c23=u2+v3-c23=9+(-5)-16=-12z31-c31=u3+v1-c31=12+(-5)-11=-4z34-c34=u3+v4-c34=12+0-10=+2z41-c41=u4+v1-c41=13+(-5)-14=-6z42-c42=u4+v2-c42=13+(-4)-13=-4z43-c43=u4+v3-c43=13+(-5)-12=-4将以上结果记在运输表上，得到1234-9-7-12-4+2-6-4-4+11101191530151142131216945453118710501931414131213252515203184这个结果与用闭回路法得到的结果完全相同。4.6.3 确定进基变量由单纯形法原理可以知道，凡检验数zij-cij0的非基变量都可以进基。通常总是选取检验数zij-cij0中最大的进基。例如在上一运输表中，选取z34-c34=2，即x34进基。4.6.4 确定离基变量设进基变量为xpq，离基变量可根据下式求出：其中（p，q）是进基变量的下标，（i，j）是与基变量对应的下标，当前基中各基变量的值，yij是非基变量xpq用基变量表出的系数Ypq中与基变量（i，j）对应的元素。由前面的讨论可以知道，Ypq中元素取值为0或1，而且闭回路转角处相应的yij的值+1，-1相间变化。因此以上求极小化的式子相当于在闭回路中，对yij取+1的那些基变量的值取最小的一个，即上式表示，当非基变量（p，q）进基时，导致xst=0离基。例如在运输表1234-4+1+2-4-6-4-12-7110119153015114-92131216945453118710501931414131213252515203184中，当x34进基时，沿闭回路1115+211481019取minx14,x32=min14,19=14，因此当x34=14进基时，x14=0离基。4.6.5 进行基变换当进基变量xpq的值由0变为，离基变量xst的值由变为0时，其余基变量的值也要相应变化：由上式可以看出，只有y=1的那些（即在闭回路转角上的）基变量，当xpq值增大时才相应改变，其余基变量都保持不变。对应于y=+1转角上的基变量减少，对应于y=-1转角上的基变量增加。例如，在以下运输表中，当x34进基时，基变量x12=1增加，x14=14和x32=19减少，当进基变量x34=14时，x1