线性规划运输问题

第四章 运输问题Chapter 4Transportation Problem4.1 运输问题的定义设有同一种货物从m个发地1,2,m运往n个收地1,2,n。第i个发地的供应量Supply为sisi0,第j个收地的需求量Demand为djdj0。每单位货物从发地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,xmnTC=c11,c12,c1n,c21,c22,c2n,cm1,cm2,cmnTA=a11,a12,a1n,a21,a22,a2n,am1,am2,amnT=b=s1,s2,sm,d1,d2,dnT则运输问题的线性规划可以写成：min z=CTXs.t.AX=bX0其中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.2171 / 454.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秩Am+n即秩A=m+n-1。在线性规划问题中,约束的系数矩阵要求行满秩的,为了使运输问题系数矩阵行满秩,在A矩阵中增加一个列向量em+n形成增广矩阵这样增广矩阵的秩就等于m+n,因而是行满秩的。并且中任何一个基矩阵,都必定包含单位向量em+n。例4.2.1 设一个运输网络如右图,它的系数矩阵为增广矩阵为12231图4.3增加的单位列向量em+n=e5相当于在在网络图中增加一条边,它与收点3关联,但不与任何发点关联,这条边称为人工边。设这条边上的运输量为xa,增广运输问题对应于第三个收点的约束称为x13+x23+xa=d3由于x13+x23=d3因此,对运输问题的任何一个可行解,都有xa=0。4.2.2 A矩阵的单位模性质运输问题的系数矩阵A具有以下性质：A矩阵中任何一个k阶子矩阵Akk=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,这时显然有det Ak=0。3、 Ak中至少有一列,其中只有一个1。这时可以将detAk按这一列展开,设对应于这个1的代数余子式为Ak-1,则有det Ak=det Ak-1其中Ak-1是k-1阶方阵。对Ak-1同样有det Ak-1=0或者det Ak-1=det Ak-2最后有det Ak=0或者det Ak=det Ak-1=det Ak-2=det A1=0或1。4.2.3基矩阵的三角性设B是的一个基,B中至少有一列只包含一个1,否则,det B=0不成为一个基。将B的行列交换,总可以使B成为其中det Bm+n-10,因而Bm+n-1中也至少有一列只有一个1,对Bm+n-1再进行行列交换,得到依次不断对剩下的方阵进行行列交换,最后可以得到是一个上三角矩阵。例4.2 设一个运输问题的系数增广矩阵为=取其中一个基对B进行行列交换,成为以下上三角矩阵求解相应的方程组由此得到x12=10,x11=15, x23=20,x13=5,xa=0由A的基矩阵的三角性以及A矩阵中仅含有元素0和1,可以知道,如果运输问题各发地的供应量和收地的需求量都是整数,运输问题的任何基础可行解都是整数,因而最优解也是整数。4.3 基在网络图和运输表中的表示kjli图4.4从前一节已经知道,运输问题的一个基是由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=-+=0这些列向量线性相关,显然不能包含在一个基中。3、 组成基的m+n条边必须到达网络的每一个节点。若不然,这m+n条边都不与某一节点k关联,那么相应的基矩阵与节点k对应的一行全为0,即det B=0。B不可能成为一个基。例4.3 对于2个发点3个收点的运输问题,网络图如图4.5a所示。图4.5b、c、d都是这个问题的基,这些基都由m+n-1=2+3-1=4条边组成,都不构成回路,并且与每一个节点关联。正如线性规划矩阵的列向量组成的基一样,一个网络的基的个数是非常多的,以上只是这些基中的几个例子。网络图第一个基 第二个基 第三个基图4.54.4基在运输表中的表示我们已经知道,运输表中的一行对应于一个发地,一列对应于一个收地,表中i行j列相交的格子表示网络从发地节点i到收地节点j的一条边。运输表中同一行i而不同列j和k的两个格子i,ji,k,分别表示网络中从同一发地节点i出发到达不同收地节点j和节点k的两条边；同样,运输表中位于同一列k而不同行i和l的两个格子i,k和l,k分别表示从不同的发地节点出发,到达同一收地节点j的两条边见下表和图。ijkl图4.6jkii,ji,kll,k表4.3如果运输表中有若干个格子,他们中相邻的两个都分别位于同一行或同一列,例如在下表中六个格子i,j,i,k,l,k,l,n,m,n和m,j,将位于同一行和同一列的两个格子连结起来,在运输表中构成一个闭回路。在相应的网络图中,这六个格子对应的六条边也组成一个闭回路。lnmjki图4.7jknii,ji,kll,kl,nmm,jm,n表4.4运输表中的闭回路还可以出现更复杂的情况,如下表和下图所示。lnmjki图4.8jknii,ji,kll,jl,nmm,km,n表4.5综上所述,总结运输表中一个基必须具备的特点：1、 一个基应占表中的m+n-1格；2、 构成基的同行同列格子不能构成闭回路；3、 一个基在表中所占的m+n-1个格子应包括表的每一行和每一列。例4.4 在例4.3.1中的运输网络的几个基分别用网络和运输表的表示如下：12231图4.9系数矩阵、网络图和运输表12311,11,21,322,12,22,3第一个基的矩阵、网络图和运输表12231图4.1012311,11,21,322,112231图4.11 第二个基的矩阵、网络图和运输表12311,11,222,22,312231图4.12第三个基的矩阵、网络图和运输表12311,11,322,22,34.5非基列向量用基向量表示在线性规划中,设B是A矩阵的一个基,且B=aB1,aB2,aBm,则A中的任一非基向量ajjR必定可以用基向量aB1,aB2,aBm唯一地线性表出,其线性组合的系数就是Yj,这是因为Yj=B-1aj即这就是说,向量Yj就是用基向量表出一个非基向量aj的系数。在运输问题中如果确定了一个基,非基向量aij也可以由基向量唯一地表出,由于运输问题的特殊性,表出系数Yij可以很方便地确定。请看下一例子。12231图4.13例4.5 以具有2个发地,3个收地的运输问题为例子,这个运输问题的网络图和系数矩阵如下：取基B=a11,a12,a13,a23,ea,非基向量为a21,基矩阵、网络图中的非基边用虚线表示、基边用实线表示,并取从发地到收地的方向为各边的方向。12231图4.14由于任何一个非基向量总是与基向量实线性相关的,因此在网络图中任一条非基边必定与若干条基边形成闭回路。根据运输矩阵的结构,对任何一个列向量aij,有aij=ei+em+j。在上面的问题中,非基向量a21可以表示为：a21=e2+e2+1=e2+e3基向量a11,a12,a13,a23可以表示为：a11=e1+e2+1=e1+e3a12=e1+e2+2=e1+e4a13=e1+e2+3=e1+e5a23=e2+e2+3=e2+e5因此a21-a11+a13-a23=-+-=0即a21=a11-a13+a23由于基向量a12和ea不在这个回路中,它在a12的表达式中的系数是0,因此非基向量a21用所有基向量的表出形式为：21231图4.15由此可以看出从这个例子可以看出,非基向量由基向量表出的方法和表出的系数可以由该非基向量与有关的基向量形成的回路来确定见上图。选定该非基边的方向作为闭回路的方向,如果一个基边出现在该回路中,并且与回路的方向相同,则表出系数为-1,如果基边的方向和回路的方向相反,则表出系数为+1,如果基边不在回路中,表出系数为0。从给定非基边的起点发地出发,沿着回路方向前进,第一次遇到的基边的方向一定和回路方向相反,第二次遇到的基边方向一定和回路方向相同,同向和反向交替出现,因此,各基边的表出系数一定是+1,-1交替出现。与网络图对应,在运输表中非基向量用基向量表示的方法也可以相应得到。例如以上的运输问题,相应的运输表如下左表所示。12312311,11,21,31BBB22,12,22,32NB表4.6对应于基B=a11,a12,a13,a23,ea的格子为用B表示,非基向量a21相应的格子用N表示,见上面右表。运输表中非基向量用用基向量表出的系数是这样确定的：按任一方向沿着表中的闭回路前进,在第一个转角处基向量的表出系数为+1,下一个转角处基向量的表出系数为-1,以后依次交替变化,由于沿闭回路回到出发的非基向量以前一定要经过奇数次转角,因此最后一个转角处的基向量的表出系数一定也是+1。凡是不在闭回路上或不在闭回路转角处的基向量的表出系数均为0。在上面的表中,非基向量N2,1与基向量B1,1、B1,3、B2,3构成一个闭回路,相应的表出系数依次为+1、-1和+1；基向量B1,2不在闭回路的转角处,表出系数为0。因此,非基向量a21的表出形式为：例4.6设有4个发地,5个收地的运输问题,运输表和网络图如下：134223451图4.16123451BB2B3BBBB4NB表 4.7134223451y=-1y=+1y=+1y=-1y=+1图4.17取其中m+n-1=4+5=9个基向量a11,a12,a14,a21,a31,a33,a34,a35和a45,非基向量a42与基向量构成的闭回路如右图。根据基向量的表出系数由+1开始,+1、-1交替的原则,以上非基向量用这些基向量表出的形式为：a42=a12+a11+a31+a35+a45+0ea如果所有基向量按以下次序排列B=a11,a12,a21,a31,a33,a34,a35,a45,ea因而a42用这些基向量表示的表出系数Y42=-1,+1,0,+1,0,0,-1,+1,0T4.6运输问题单纯形法运输问题单纯形法的基本步骤和线性规划一样,包括以下步骤,但具体实施是在运输表上实现。1、 求得一个初始基础可行解；2、 对非基变量xij计算检验数zij-cij,根据各非基变量的检验数zij-cij值,确定最优性或选择进基变量；3、 当进基变量xij进基时,根据基变量的变化,求出最先降为0的基变量确定为离基变量；4、 进行基变换,获得新的基础可行解并转步骤2。4.6.1 确定初始基础可行解1、 西北角法西北角法是按发地和收地的编号为序,依次顺序供给的原则获得初始基础可行解的一种方法。它是从确定发地1到收地1的运量开始。这个位置按地图的方位来说是西北角,因而得名。从发地1到收地1的运量取发地1的供应量30和收地1的需求量15两者中小的一个安排,如果发地1的供应量没有用完,则将剩余的供应量向收地2发送,依次类推,直到最后一个发地的供应量全部运出,最后一个收地的需求量全部满足为止。例4.7 给出运输表如下。发地1的供应量为30,收地1的需求量为15,在1,1上安排运量15。发地1和收地1的供应量和需求量分别变为15和0。12341101191530-151521312169453118710504141312132515-15203184发地1的供应量为15,收地2的需求量为20,在1,2上安排运量15,发地1的供应量变为0,收地2的需求量变为5；12341101191515-151515213121694531187105041413121325020-153184收地2的需求量为5,发地2的供应量为45,在2,2上安排运量5,发地2的供应量变为40,收地2的需求量变为0；123411011915015152131216945-553118710504141312132505-53184发地2的供应量为40,收地3的需求量为31,在2,3上安排运量31,发地3的供应量变为9,收地3的需求量变为0；123411011915015152131216940-31531311871050414131213250031-3184发地2的供应量为9。收地4的需求量为84,在2,4上安排运量9,发地2的供应量变为0,收地4的需求量变为75；12341101191501515213121699-953193118710504141312132500084-9收地4的需求量为75,发地3的供应量为50,安排3,4上的运量为50,发地3的供应量0,收地4的需求量25；123411011915015152131216905319311871050-50504141312132500075-50发地4的供应量为25,收地4的需求量为25,安排4,4上的运量25,发地4的供应量为0,收地4的需求量为0,供求和需求都得到满足。123411011915015152131216905319311871005041413121325-25=02500025-25=0用西北角法确定初始可行解方法简单,不会出现回路,而且一般情况下基变量的个数恰为m+n-1个退化的情况基变量可能少于m+n-1,处理的方法在4.7节中介绍,而且基变量位于每一行每一列,因而得到的是一个基础可行解。西北角法的缺点是在安排运量时不考虑运价,因而得到的初始解可能离开最优解比较远。以上例子中用西北角法得到的初始解的目标函数值为z=cijxij=1015+1115+125+1631+99+1050+1325=17772、 最小元素法这种方法是按运价由小到大的顺序安排运量。先从各运价中找到最小运价,设为cij,然后比较供应量si和需求量dj,如果sidj,取xij=dj,并将发地i的供应量改为si-dj,将收地j的需求量改为0；如果sidj,取xij=si,并将发地i的供应量改为0,将收地j的需求量改为dj-si；如果si和dj中有一个为0,则不分配运量给xij。分配完最小运价的运量后,用同样的方法分配运价次小的运量,依次类推,直到每一个发地的供应量和每一个收地的需求量都为0。以下是用最小元素法确定运输问题的初始可行解的例子。例4.8 给出运输表如下。最小运价为c33=7,发地3的供应量为50,收地3的需求量为31,安排运量x33=31。发地3和收地3的供应量和需求量分别变为19和0。123411011915302131216945311871050-313141413121325152031-3184对于c32=8,发地3的供应量为19,收地2的需求量为20,安排x32=19,发地3的供应量为0,收地2的需求量为1。123411011915302131216945311871019-191931414131213251520-19084对于c13=9,c24=9,可以任选一个,但是1,3中收地3的需求量为0,安排x24=45,发地2的供应量为0,收地4的需求量为39。123411011915302131216945-454531187100193141413121325151084-45对于c11=10和c34=10,由于发地3的需求量已经为0,安排x11=15,发地1的供应量为15,收地1的需求量为0；12341101191530-1515213121690453118710019314141312132515-151039对于c12=11,安排x12=1,发地1的供应量为14,收地2的需求量为0；12341101191515-1151213121690453118710019314141312132501-1039对于c44=13,安排x44=25,发地4的供应量为0,收地4的需求量为14。123411011915141512131216904531187100193141413121325-252500039-25最后安排x14=14,所有发地和收地的供应量、需求量都等于0。12341101191514-14=0151142131216904531187100193141413121302500014-14=0这样就得到一个运输问题的初始基础可行解。这个初始基础可行解的目标函数值为z=1015+111+1514+945+819+731+1325=1470比用西北角法得到的初始基础可行解的目标函数值小。4.6.2 计算非基变量的检验数zij-cij4.5.2.1闭回路法对于非基变量xij,检验数为其中向量Yij可由该非基变量与基变量形成的闭回路来确定,这个闭回路转角处的基变量对应于y=1,其余的基变量对应于y=0。这样就等于转角处基变量对应的cij依次加减的值。例4.9在例4.7中,用西北角法得到初始基础可行解,计算各非基变量的检验数zij-cij1234110119153015152131216945531931187105050414131213252515203184非基变量1,3相应的闭回路为1234+6110119153015152131216945531931187105050414131213252515203184因此x13的检验数z13-c13=-c13=-9=+6。非基变量1,4相应的闭回路为1234-7110119153015152131216945531931187105050414131213252515203184因此x14的检验数z14-c14=-c14=-15=-7非基变量2,1相应的闭回路为123411011915301515-22131216945531931187105050414131213252515203184因此x21的检验数z21-c21=-c21=-13=-2非基变量3,1相应的闭回路为12341101191530151521312169455319+131187105050414131213252515203184因此x31的检验数z31-c31=-c31=-11=+1用同样的方法可以求得其他非基变量的检验数z32-c32=-c32=-8=+5z33-c33=-c33=-7=+10z41-c41=-c41=-14=+1z42-c42=-c42=-13=+3z43-c43=-c43=-12=+8将以上检验数填入运输表,用表示。1234+3+1+1+8-2+6+5-71101191530151521312169455319+1031187105050414131213252515203184对用最小元素法得到的初始基础可行解,也可以用同样的方法求得各非基变量的检验数zij-cij,计算过程略,计算结果见下表。1234-9-7-12-4+2-6-4-4+11111011915301511421312169454531187105019314141312132525152031844.5.2.2 对偶变量法设运输问题的原始问题为：其中xa是为了使矩阵A满秩而增加的变量。设与前m个约束对应的对偶变量为u1,u2,um,与后n个约束对应的对偶变量为v1,v2,vn。则对偶问题为：max y=s1u1+s2u2+smum+d1v1+d2v2+dnvns.t.u1+v1c11u1+vnc1nu2+v1c21u2+vnc2num+v1cm1um+vncmnvn=0u1,u2,um,v1,v2,vn：unr以上对偶问题,可以简写成：ui+vjcijvn=0ui,vj：unr对偶问题中由m+n个变量,mn+1个约束。对于运输问题的一个基B,如果能够求出相应的对偶变量WT=CBTB-1,就可以计算非基变量xij的检验数zij-cij：zij-cij=CBTB-1aij-cij=WTaij-cij=WT-cij =WTei+WTem+j-cij=ui+vj-cij对于一个确定的基,如果xij是基变量,则xij0。由于单纯形叠代在每一步都满足互补松弛条件,因此对于基变量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-=12v3=7-u3=7-12=-5在求得各对偶变量ui,vj的值以后,再计算检验数zij-cij=ui+vj-cijz13-c13=u1+v3-c13=15+-9=+1z21-c21=u2+v1-c21=9+-13=-9z22-c22=u2+v2-c22=9+-12=-7z23-c23=u2+v3-c23=9+-16=-12z31-c31=u3+v1-c31=12+-11=-4z34-c34=u3+v4-c34=12+0-10=+2z41-c41=u4+v1-c41=13+-14=-6z42-c42=u4+v2-c42=13+-13=-4z43-c43=u4+v3-c43=13+-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时,x12=15,x14=0离基,x32=5。新的运输表成为：1234-7-10-4-4-2-2-2-9+11101191530151521312169454531187105053114414131213252515203184其中,x34成为新的基变量,x14成为新的非基变量。用闭回路法或对偶变量法重新计算各非基变量的检验数zij-cij,得到的结果见上表。其中x13的检验数z13-c13=+10,继续选取x13进基,相应的闭回路为：+11191587531取minx12,x33=min15,31=15,当x13