线性规划运输问题

127第四章运输问题Chapter4TransportationProblem§4.1运输问题的定义设有同一种货物从m个发地1，2，…，m运往n个收地1，2，…，n。第i个发地的供应量（Supply）为si（si≥0），第j个收地的需求量（Demand）为dj（dj≥0）。每单位货物从发地i运到收地j的运价为cij。求一个使总运费最小的运输方案。我们假定从任一发地到任一收地都有道路通行。如果总供应量等于总需求量，这样的运输问题称为供求平衡的运输问题。我们先只考虑这一类问题。图4.1.1是运输问题的网络表示形式。运输问题也可以用线性规划表示。设xij为从发地i运往收地j的运量，则总运费最小的线性规划问题如下页所示。运输问题线性规划变量个数为nm个，每个变量与运输网络的一条边对应，所有的变量都是非负的。约束个数为m+n个，全部为等式约束。前m个约束是发地的供应量约束，后n个约束是收地的需求量约束。运输问题约束的特点是约束左边所有的系数都是0或1，而且每一列中恰有两个系数是1，其他都是0。运输问题是一种线性规划问题，当然可以用第一章中的单纯形法求解。但由于它有特殊的结构，因而有特殊的算法。在本章中，我们将在单纯形法原理的基础上，根据运输问题的特点，给出特殊的算法。im1jn1c11c1jc1nnci1cijcincm1cmjcmn图4.1第四章运输问题1280xxxxxxxxxdxxxdxxxdxxxsxxxsxxxsxxx.t.sxcxcxcxcxcxcxcxcxczminmn2m1mn22221n11211nmnn2n122m221211m2111mmn2m1m2n222211n11211mnmn2m2m1m1mn2n222222121n1n112121111在运输问题线性规划模型中，令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，…，amn]T=行行nm111111111111111111b=（s1，s2，…，sm，d1，d2，…，dn）T则运输问题的线性规划可以写成：minz=CTXs.t.AX=bX≥0其中A矩阵的列向量aij=ei+em+jei和em+j是m+n维单位向量，元素1分别在在第i个分量和第m+j个分量的位置上。A矩阵中的行与运输网络中的节点对应，前m行对应于发地，后n行对应于收地；A矩阵的列与运输网络中的边对应。第四章运输问题129运输问题除了用网络表示及线性规划表示外，还可以用运输表表示：12…n1c11c12…c1ns1x11x12…x1n2c21c22…c2ns2x21x22…x2n…………………………mcm1cm2…cmnsmxm1xm2…xmnd1d2…dn表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,x23≥0第四章运输问题130123185615x11x12x13274925x21x22x23102010表4.2122311525102010856749图4.2第四章运输问题131§4.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’=列列行行nmnm111111111111删除A’中的第m+n行和第m+n列，得到A’’=列列行行1nm1nm111111111容易看出，秩A’’=m+n-1。由此m+n-1=秩A’’≤秩A’≤秩Am+n第四章运输问题132即秩A=m+n-1。在线性规划问题中，约束的系数矩阵要求行满秩的，为了使运输问题系数矩阵行满秩，在A矩阵中增加一个列向量em+n形成增广矩阵1000nmAeAA这样增广矩阵A的秩就等于m+n，因而是行满秩的。并且A中任何一个基矩阵，都必定包含单位向量em+n。例4.2.1设一个运输网络如右图，它的系数矩阵为3212123x22x21x13x12x11xdddss100100010010001001111000000111A增广矩阵为32121ex23x22x21x13x12x11xdddss11001000010010000100101110000000111A增加的单位列向量em+n=e5相当于在在网络图中增加一条边，它与收点3关联，但不与任何发点关联，这条边称为人工边。设这条边上的运输量为xa，增广运输问题对应于第三个收点的约束称为x13+x23+xa=d3由于12231图4.3第四章运输问题133x13+x23=d3因此，对运输问题的任何一个可行解，都有xa=0。4.2.2A矩阵的单位模性质运输问题的系数矩阵A具有以下性质：A矩阵中任何一个k阶子矩阵Ak（k=1，2，…m+n），都有detAk=0或±1。证明：在A中任取一个k阶方阵Ak，有以下三种情况：1、Ak中任何一列都有两个1，这时Ak上部的行属于A矩阵的前m行，而下部的行属于A矩阵的后n行，Ak上部的各行之和以及Ak下部各行之和都等于向量（1，1，…，1），因而Ak的行线性相关，即detAk=0。2、Ak中至少有一列元素全为0，这时显然有detAk=0。3、Ak中至少有一列，其中只有一个1。这时可以将detAk按这一列展开，设对应于这个1的代数余子式为Ak-1，则有detAk=±detAk-1其中Ak-1是k-1阶方阵。对Ak-1同样有detAk-1=0或者detAk-1=±detAk-2最后有detAk=0或者detAk=±detAk-1=±detAk-2=…=±detA1=0或±1。4.2.3基矩阵的三角性设B是A的一个基，B中至少有一列只包含一个1，否则，detB=0不成为一个基。将B的行列交换，总可以使B成为第四章运输问题1341nmT'001BPB其中detBm+n-1≠0，因而Bm+n-1中也至少有一列只有一个1，对Bm+n-1再进行行列交换，得到2nmTT''0010001BQPB依次不断对剩下的方阵进行行列交换，最后可以得到1000100101RB是一个上三角矩阵。例4.2设一个运输问题的系数增广矩阵为A=2510152030dddss1100100001001000010010111000000011132121ex23x22x21x13x12x11xb取其中一个基2510152030dddss100110100000100000100110132121ax12x11x23x13xbB第四章运输问题135对B进行行列交换，成为以下上三角矩阵1015203025ddssd10000010000010001010001112121312x11x23x13xaxbB求解相应的方程组1015203025xxxxx100000100000100110100011112112313a10x15x20x30xxx25xxx1211231211132313a由此得到x12=10，x11=15，x23=20，x13=5，xa=0由A的基矩阵的三角性以及A矩阵中仅含有元素0和1，可以知道，如果运输问题各发地的供应量和收地的需求量都是整数，运输问题的任何基础可行解都是整数，因而最优解也是整数。第四章运输问题136§4.3基在网络图和运输表中的表示从前一节已经知道，运输问题的一个基是由m+n个列向量组成的，其中包括一个单位向量em+n。在网络图上，这m+n个列向量对应m+n条边，其中与单位向量对应的是从最后一个收地出发的人工边。网络图中的一个基具有以下性质：1、一个基由m+n条边组成，其中一条是人工边，其余m+n-1条边是原网络中的边。2、组成基的边不能形成闭合回路。若不然，如果组成一个基的若干条边（i，j），（k，j），（i，l），（k，l）组成一个闭合回路，则这些边对应的系数矩阵中的列向量aij，akj，ail，akl的线性组合aij-akj+ail-akl=(ei+em+j)-(ek+em+k)-(ei+em+l)+(ek+em+l)=0这些列向量线性相关，显然不能包含在一个基中。3、组成基的m+n条边必须到达网络的每一个节点。若不然，这m+n条边都不与某一节点k关联，那么相应的基矩阵k0000B节点与节点k对应的一行全为0，即detB=0。B不可能成为一个基。例4.3对于2个发点3个收点的运输问题，网络图如图4.5（a）所示。图4.5（b）、（c）、（d）都是这个问题的基，这些基都由m+n-1=2+3-1=4条边组成，都不构成回路，并且与每一个节点关联。正如线性规划矩阵的列向量组成的基一样，一个网络的基的个数是非常多的，以上只是这些基中的几个例子。kjli图4.4第四章运输问题137(a)网络图(b)第一个基(c)第二个基(d)第三个基图4.5第四章运输问题138§4.4基在运输表中的表示我们已经知道，运输表中的一行对应于一个发地，一列对应于一个收地，表中i行j列相交的格子表示网络从发地节点i到收地节点j的一条边。运输表中同一行i而不同列j和k的两个格子（i，j）（i，k），分别表示网络中从同一发地节点i出发到达不同收地节点j和节点k的两条边；同样，运输表中位于同一列k而不同行i和l的两个格子（i，k）和（l，k）分别表示从不同的发地节点出发，到达同一收地节点j的两条边（见下表和图）。jki（i，j）（i，k）l（l，k）表4.3如果运输表中有若干个格子，他们中相邻的两个都分别位于同一行或同一列，例如在下表中六个格子（i