运筹学基础(第2版)何坚勇运输问题.ppt

《运筹学基础(第2版)何坚勇运输问题.ppt》由会员分享，可在线阅读，更多相关《运筹学基础(第2版)何坚勇运输问题.ppt（125页珍藏版）》请在三一办公上搜索。

1、运输问题是线性规划问题，由于其约束条件的特殊性，产生了特殊的解法。,第五章 运输问题,例:,从3个发点A1，A2,，A3，向4个收点B1，B2，B3，B4发送某种货物。Ai 供应量为14，27，19。Bj 收点的收量为22，13，12，13。由Ai 运往Bj 单位货物的运费为Cij，由Ai 运往Bj 货物的运量为Xij。问如何调配，才能使运费最省？,2,3,2,1,3,4,1,运输问题网络图,s2=A2,s3=A3,B1,B2,B3,B4,s1=A1,供应量,供应地,运价,需求量,需求地,6,7,5,3,8,4,2,7,5,9,10,6,B1,运输问题线性规划模型,供应地约束,需求地约束,5.

2、1运输问题数学模型和特点,5.1.1产销平衡问题的数学模型,问题的提出 从m个发点A1,A2,.Am向n个收点B1,B2.Bn发送某种货物。Ai发点的发量为ai，Bj收点的收量为bj。由Ai 运往Bj 单位货物的运费为Cij，由Ai 运往Bj 货物的运量为Xij。问如何调配，才能使运费最省？,当发点的发量总和为 ai，收点的收量总和为 bj相等时，称此运输问题为平衡运输问题。否则称此运输问题为非平衡运输问题。若没有特别说明，均假定运输问题为平衡的运输问题。,续,Min Z=cijxij i j xij=ai(i=1,2.m)xij=bj(j=1,2n)xij 0(i=1,2.m;j=1,2n)

3、,5.1.1运输问题的数学模型,m,n,j,i,n,m,运输问题的数学模型：其中 ai 0,bj 0,cij 0且共有 m+n 个约束方程。并成立：ai=bj i j,m,n,X=(X11，X12，X1n，X21，X22，X2n，Xm1，Xm2，Xmn)TC=(C11，C12，C1n，C21，C22，C2n，Cm1，Cm2，Cmn)A=(P11，P12，P1n，P21，P22，P2n，Pm1，Pm2，Pmn),由于 ai=bj成立 其m+n个约束方程并不是独立的。实际上只有m+n-1个是独立的。即约束方程系数矩阵的秩为m+n-1。,运输问题解的结构,n,m,i,j,Pij,Pij=ei+em+

4、j(i=1，.，m，j=1，n),ei为第i个分量为1其余分量为0的m+n维向量。em+j为第m+j个分量为1其余分量为0的m+n维分量。,运输问题矩阵描述,min CX；S.T AX=b（5.1.3）x0,其中A为,A(m+n)(mn),X11 X12 X1n X21 X22 X2n.Xm1 Xm2 Xmn 1.1 1 1 1.1 1 1 1 1 1 1 1.1 1 1,A=,n,a1a2.amb1b1.bn,5.1.2运输问题数学模型的特点,(1),有m n列，每列有(m+n)个元素，其中有两个1，其余为0。对于列Pij来说，两个1的位置为i与m+j个分量Pij=ei+e m+jei为第i

5、个分量为1其余分量为0的m+n维单位向量e m+j为第m+j分量为1，其余分量为0的m+j分量为0的m+n维单位向量。,如,（2）,A有(m+n)行，每行前m行有n个1并连在一起，其余为零。,E 0.00 E.0 0 0 E I I I,A=,E=(1，1，1，.，）,（3）运输问题有最优解,证明由于 ai=bj=d成立,令Xij=ai bj/d 5.1.6I=1，2，mJ=1，2，n代入5.1.1,n,m,i,j,续,Xi j=ai bj/d=bj(ai/d)=ai(i=1，2，m)Xi j=ai bj/d=ai(bj/d)=bj(j=1，2，n)ai 0，bj0，所以Xij 0,n,j=1

6、,n,j=1,n,j=1,m,m,m,i=1,i=1,i=1,xu,5.1.6是运输问题的可行解。由定理2.4.6可得运输问题必有基本可行解。由Xi j 的定义知，Xi j min(ai，bj）可行域是有界的。必有最优解。,（4）矩阵A的秩为（m+n-1）,A是一个（m+n）（m*n）型矩阵一般来说：（m+n）（m*n）因此秩最大为（m+n）又前m方程与后n个方程和相等。故r（A），实际是等于（m+n-1）。,A(m+n)(mn),X11 X12 X1n X21 X22 X2n.Xm1 Xm2 Xmn 1.1 1 1 1.1 1 1 1 1 1 1 1.1 1 1,A=,n,a1a2.amb1

7、b1.bn,A(m+n)(mn),p11 p 12 p 1n p 21 p 31 p m10 0.0 1 1.1 1 1.1 1.1,A=,证明,p11 p 12 p 1n p 21 p 31 p m1线性无关，而p ij与 p ij 只差一个分量。由向量相关理论可知：一组线性无关向量组在相同的位置上加相同多的分量后得到的新向量也线性无关。因此 p11 p 12 p 1n p 21 p 31 p m1也线性无关。r(A)=(m+n-1),5.2表上作业法,由于运输问题的特殊性，因此求解运输问题往往不用单纯形法。而用表上作业法。1、用西北角法或最小元素法确定基本可行解。2、用位势法求解检验数3、

8、用闭回路调整法求最优解,调运表,发点,收点,例5.2.1表5.3,收点,发点,5.2运价表,收点,发点,1、西北角法,(I，j)，从（1，1）开始，比较a1，b1。X11=min（a1，b1）=b1=3,表5.3,收点,发点,表5.4,X11=min（a1，b1）=b1=3X12=min（a1，b2）=a1=4X22=min（a2，b2）=b2=2X23=min（a2，b3）=min（2，5）=a2=2X33=min（a3，b 3）=min（9，3）=b3=3X34=min（a3，b4）=6,表5.5,Z=33+411+29+22+310+65=133(万),2、最小元素法(表5.6-7),3

9、,6,4,1,3,3,C21=1，X21=min（a2，b1）=b1=3C23=2，X23=min（a2，b3）=min（1，5）=a2=1C13=3，X13=min（a1，b3）=min（7，4）=b3=4 C32=4，X32=min（a2，b2）=b2=6C34=5，X34=min（a3，b 4）=min（3，6）=a3=3C14=10，X14=min（a 1，b4）=a1=b4=3Z=43+310+31+12+64+35=86(元),5.2.2位势法求检验数,ij=Cij-Zij=Cij-CBB-1 Pij 5.2.1(i=1，2.m；j=1，2n),Max f=aiui+bjvj st

10、 ui+vj Cij(i=1，2.m)(j=1，2n)ui，vj 无正负,W=(u1，um，v1，vn）5.2.3Ui=(xi1,xi2,xi3,xi4.xin),vj=(x1j,x2j,xxmj),m,I=1,j=1,n,Min Z=cijxij i j xij=ai(i=1,2.m)xij=bj(j=1,2n)xij 0(i=1,2.m;j=1,2n),5.1.1运输问题的数学模型,m,n,j,i,n,m,运输问题线性规划模型,供应地约束,需求地约束,5.2.3代5.2.1,ij=Cij-WPij=Cij-(u1，um，v1，vn)(ei+e m+j)=Cij-(ui+vj）5.2.4(i

11、=1，2.m；j=1，2n),A=,n,X11 X12 X1n X21 X22 X2n.Xm1 Xm2 Xmn 1.1 1 1 1.1 1 1 1 1 1 1 1.1 1 1,基变量的:Cij-(ui+vj）=0（i，j）JB（5.2.5）因为为已知，而（5.2.5）有（m+n）个未知量令 Vn=0（5.2.6）非基变量检验数:ij=Cij-(ui+vj）(i，j）JN（5.2.7）,A、公式求检验数,表5.5,Z=33+411+29+22+310+65=133(万),5.2.1例表5.5,基变量:X11，X12，X22，X23，X33，X34C11-(u1+v1）=0C12-(u1+v2）=

12、0C22-(u2+v2）=0C23-(u2+v3）=0C33-(u3+v3）=0C34-(u3+v4）=0V4=0,代入Cij,3-(u1+v1）=011-(u1+v2）=09-(u2+v2）=02-(u2+v3）=010-(u3+v3）=05-(u3+v4）=0V4=0解出：u1=-1，u2=-3，u3=5，v1=4，v2=12，u3=5，,代入公式5.2.7,ij=Cij-(ui+vj）(i，j）JN 5.2.713=C13-(u1+v3）=3-(-1+5)=-114=C14-(u1+v4）=10-(-1+0)=1121=C21-(u2+v1）=1-(-3+4)=0,代入公式5.2.7,i

13、j=Cij-(ui+vj）(I，j）JN 5.2.724=C24-(u2+v4）=8-(-3+0)=1131=C31-(u3+v1）=7-(5+4)=-232=C32-(u3+v2）=4-(5+12)=-13ij0，故不是最优解,B、检验数表格求解,1、作表格（3+1)(4+1）的表2、第(3+1)行为vj行，(4+1)列为 ui列3、右上角标出Cij，其中非基变量用框住。,表5.8,7,1,7,4非,3,10,8,V4=0，基变量:X11，X12，X22，X23，X33，X34 Cij-(ui+vj）=0（i，j）JB(5.2.5)Cij=(ui+vj）ui=Cij-vj）(5.2.10)因

14、为：V4=0，C34=(u3+v4）=u3=5，V3=C33-u3=10-5=5C23=(u2+v3），u2=C23-v3=2-5=-3,计算：,V4=0，基变量:X11，X12，X22，X23，X33，X34 Cij-(ui+vj）=0（I，j）JB 5.2.5 Cij=(ui+vj）5.2.10 因为：V4=0，C34=(u3+v4）=u3=5，,表5.9,7,1,7非,4,3,10,8,Cij=(ui+vj）5.2.10 C22=(u2+v2）v2=C22-u2=9-（-3）=12u1=C12-v2=11-12=-1V1=C11-u1=3-（-1）=4,表5.10,7,1,7,4,3,1

15、0,8,ij=Cij-(ui+vj）(i，j）JN(5.2.7)13=C13-(u1+v3）=3-(-1+5)=-114=C14-(u1+v4）=10-(-1+0)=1121=C21-(u2+v1）=1-(-3+4)=024=C24-(u2+v4）=8-(-3+0)=1131=C31-(u3+v1）=7-(5+4)=-232=C32-(u3+v2）=4-(5+12)=-13有ij0，故不是最优解,例5.2.2,以例5.2.1的最小元素法求得的基本可行解为例。见表5.7用位势法计算检验数。,最小元素法(表5.6-7),3解,6,4,1,3,3,表5.11,7,7非,8,3,11,9,10,5.2

16、.3用闭回路法调整当前基本可行解,定义5.2.将变量Xij在调运表中所对应的空格记做(i，j)称为格点。而Xij系数列向量Pij也称作格点(i，j)所对应的系数列向量，若Xij为基变量，则(i，j)称为基格，否则为非基格。,表5.6.7，基格(1，3)，(1，4)(2，1)(2，3)非基格(1，1)，(2，4)(3，1)(2，3),(表5.6-7),3,6,4,1,3,3,定义5.2.2,定义5.2.2若一组格点经过适当的排序后，能写成以下形式：(I1，j1)，(I1，j2)，(I2，j2)(I2,，j3)，(I3，j3).(Is,，js)，(Is，ji)1则这组格点构成了闭回路。,闭回路特点

17、,(1)格点数大于4,(2),形式A：第1格与第2格行号同，第2与第3格列号同，第3、第4格行号同，第4、第5格列号同最后一格与第一格列号同。形式B：第1格、第2格列号同。第2格、第3格行号同最后一格与第一格行号同。,（3）,连线构成闭回路，一行或一列只包含两个格点，都处在每条边的端点上。,5.12,格组(1，1)，(1，2)(3，2)(3，1)格组(1，3)，(1，4)(2，4)(2，5)(3，5)(3，3)格组(1，6)，(1，7)(4，7)(4，9)(2，9)(2，6),表5.12，,格组(1，1)，(1，2)(3，2)(3，1)格组(1，3)，(1，4)(2，4)(2，5)(3，5)(

18、3，3)格组(1，6)，(1，7)(4，7)(4，9)(2，9)(2，6),5.13,包含了闭回路，非构成闭回路成,格组(1，1)，(1，2)(1，4)(3，4)(3，2)格组(2，5)，(2，6)(2，7)(3，7)(3，6)(3，5),表5.10,7,1,7,4,3,10,8,表5.5,Z=33+411+29+22+310+65=133(万),表5.14,Z=33+411+29+22+310+65=133(元),ij=min ij|ij0=32=-13（I，j）JN,表5.5初始方案，5.10 检验数不大于0,32=-13,=minXij|(i，j)为闭回路上所有偶数号格点=min(2，3

19、)=2=X22,表5.15,X(1)=(3，4，0，0，0，0，4，0，0，2，1，6）TZ(1)=33+114+24+42+101+56=109(元)Z(0)=133(元),产销平衡运输问题的算法其步骤如下,第l步：,用西北角规则或最小元素法求初始基本可行解。,第2步,用位势法求非基变量的检验数。若最优准则。ij0 得到满足，则当前基本可行解就是最优解（当前调运方案就是最优调运方案），计算停止。否则转第3步。,第3步：,取一个检验数最小的非基变量作进基变量，其对应的格为进基格（编号为第1格）。以进基格为起始点作出一个其余顶点均为基格的闭回路，在该闭回路上，从所有偶数号格点的调运量中选出最小值

20、作为调整量，该格即为离基格，对应的变量为离基变量。,第4步,对闭回路上的运输量作出调整：所有奇数号格的调运量加上调整量；所有偶数号格的调运量减去调整量，其余的Xij取值不变，这样就得到了一个新的调运方案转第2步。,例 5.2.3,判断以表5.15所体现的X(1)是否为最优解。若不是，试求出最优解。解:对X(1)用位势法求其检验数，为此建立表5.16，计算ui，vj及ij,表5.15,X(1)=(3，4，0，0，0，0，4，0，0，2，1，6）TZ(1)=33+114+24+42+101+56=109(元)Z(0)=133(元),表5.16,1,7,1,7,3,10,8,9,ij=min ij|

21、ij0=13=-14（i，j）JN非优，建闭回路。,表5.17,X(2)=(3，3，1，0，0，0，4，0，0，3，0，6）TZ(2)=33+113+31+24+43+56=95(元)Z(1)=109(元),=minXij|(I，j)为闭回路上所有偶数号格点=min(1，4)=1=X33,再判断 X(2)是否为最优解。建立表 5.18，计算ui，vj及ij,表5.18,7,1,7,10,8,9,10,不都大于0,也不是最 优解ij=min ij|ij0=24=-3（i，j）JN非优，建闭回路。,表5.19,X(3)=(3，0，4，0，0，0，1，3，0，6，0，3）TZ(3)=33+34+21

22、+83+46+53=86(元)Z(2)=95(元),=minXij|(i，j)为闭回路上所有偶数号格点=min(6，3，4)=3=X12,再判断 X(3)是否为最优解建立表 5.20，计算ui，vj及ij,表5.20,7,1,7,10,9,11,10,不都大于0,也不是最 优解ij=min ij|ij0=21=-1（i，j）JN非优，建闭回路。,表5.21,X(4)=(2，0，5，0，1，0，0，3，0，6，0，3）TZ(4)=32+35+11+83+46+53=85(元)Z(3)=86(元),表5.22,7,7,10,9,11,10,2,都大于0，是最 优解,X 11=2，X 13=5，X

23、21=1，X 24=3，X 32=6，X 34=3，X I4=0,5.2.4表上作业法计算中的两个问题,1、无穷多个最优解2、退化问题,1、无穷多个最优解,某个非基变量检验数等于零,表 5.23,X(5=(0，0，5，2，3，0，0，1，0，6，0，3）TZ(5)=35+102+13+81+46+53=85(元),表22中14=0，作闭回路,2、退化问题,（1）在确定初始可行解时，若已确定的空格（i，j）处要填上调运量Xij，而此时刚好有ai=bj，Xij=ai=b j，说明此时Ai的发运量已经用完，而Bi的需求已满足。因此要画掉第i行，j列。,x,为了保证调运表上有（m+n-1）个基变量的值

24、，就要在第i行，j列中任找一个空格（i，j1）或（i1，j），设置调运量为Xij1=0，或 Xi1j=0。,例5.2.4,下表为34运输问题的Cij及发运量和需求量，试用最小素法求该问题的一个可行解。,例5.2.4调运表,例5.2.4调运方案,(2)在用闭回路调整时出现退化,=minXij|(i，j)为闭回路上所有偶数号格点如果两个或两个以上偶数格点Xij都为极小值，则只能取一个为离基格，其余作为基格。出现了退化问题,例5.2.5,表5.26为34问题的基本可行解及发运量和需求量。表5.27为基本可行解的检验数。用闭回路法对其作出调整。,表5.26,表5.27,表5.28,min=ij=24闭

25、回路如图=minXij|(i，j)为闭回路上所有偶数号格点=minX34,X12,X23=X12=X23=3,表5.28,min=ij=24闭回路如图=minXij|(i，j)为闭回路上所有偶数号格点=minX34,X12,X23=X12=X23=3,作业答案,P170,5.2,题5.11基本可行解,X11=min（a1，b1）=b1=6X12=min（a1，b2）=a1=1X22=min（a2，b2）=b2=5X23=min（a2，b3）=min（2，5）=a2=3X33=min（a3，b 3）=0X34=min（a 3，b4）=3,表5.11,7,4,8,4非,7,3,7,V4=0，基变量

26、:X11，X12，X22，X23，X33，X34 Cij-(ui+vj）=0（I，j）JB 5.2.5 Cij=(ui+vj）ui=Cij-vj）5.2.10 因为：V4=0，C34=(u3+v4）=u3=9，V3=C33-u3=2-9=-7C23=(u2+v3），u2=C23-v3=10-(-7)=17,表5.12检验数,7,4,8,4非,7,3,7,ij=Cij-(ui+vj）(I，j）JN 5.2.713=C13-(u1+v3）=7-(-7+16)=-214=C14-(u1+v4）=3-(16+0)=-1321=C21-(u2+v1）=4-(-11+17)=-224=C24-(u2+v4

27、）=7-(17+0)=-1031=C31-(u3+v1）=8-(9-11)=1032=C32-(u3+v2）=4-(9-8)=-3有ij0，故不是最优解,题5.13闭回路,=minXij|(I，j)为闭回路上所有偶数号格点=min1，3，3=1,表5.14VU,7,4,8,4非,7,8,7,V4=0，基变量:X11，X12，X22，X23，X33，X34 Cij-(ui+vj）=0（I，j）JB 5.2.5 Cij=(ui+vj）ui=Cij-vj）5.2.10 因为：V4=0，C34=(u3+v4）=u3=9，V3=C33-u3=2-9=-7C23=(u2+v3），u2=C23-v3=10-

28、(-7)=17,表5.15检验数,7,4,8,4非,7,7,ij=Cij-(ui+vj）(I，j）JN 5.2.713=C13-(u1+v3）=7-(-7+3)=1112=C12-(u1+v2）=8-(3-8)=1321=C21-(u2+v1）=4-(2+17)=-1524=C24-(u2+v4）=7-(17+0)=-1031=C31-(u3+v1）=8-(9+2)=-332=C32-(u3+v2）=4-(9-8)=3有ij0，故不是最优解,8非,题5.16闭回路,=minXij|(I，j)为闭回路上所有偶数号格点=min2，2，6=2,表5.17检验数,7,8,4非,7,7,ij=Cij-(

29、ui+vj）(I，j）JN 5.2.713=C13-(u1+v3）=7-(-7+3)=1112=C12-(u1+v2）=8-(3+7)=-223=C23-(u2+v3）=10-(2-7)=1524=C24-(u2+v4）=7-(2+0)=531=C31-(u3+v1）=8-(9+2)=-332=C32-(u3+v2）=4-(9+7)=-12有ij0，故不是最优解,8非,10,题5.18闭回路,=minXij|(I，j)为闭回路上所有偶数号格点=min0，4，6=0,表5.19检验数,7,8,7,7,ij=Cij-(ui+vj）(I，j）JN 5.2.713=C13-(u1+v3）=7-(5+3

30、)=-112=C12-(u1+v2）=8-(3+7)=-223=C23-(u2+v3）=10-(2+5)=324=C24-(u2+v4）=7-(2+0)=531=C31-(u3+v1）=8-(2-3)=934=C34-(u3+v4）=9-(0-3)=12有ij0，故不是最优解,8非,10,9,题5.20闭回路,=minXij|(I，j)为闭回路上所有偶数号格点=min4，6=4,表5.21检验数,7,8,7,7,ij=Cij-(ui+vj）(I，j）JN 5.2.713=C13-(u1+v3）=7-(5+3)=-111=C11-(u1+v1）=5-(3+0)=223=C23-(u2+v3）=1

31、0-(2+5)=324=C24-(u2+v4）=7-(-4+0)=331=C31-(u3+v1）=8-(0-1)=934=C34-(u3+v4）=9-(0-1)=10有ij0，故是最优解,10,9,5,题5.22闭回路,X(1)=(0，4，0，0，6，2，0，0，0，0，3，0）TZ(1)=84+33+64+92+32=89,5.2最小元素法,题5.21基本可行解,1,2,3,4,5,6,7,表5.22UV,20,30,20,40,20,30,40,55,V5=0，基变量:X11，X12，X22，X23，X24，X32，X35 Cij-(ui+vj）=0（I，j）JB 5.2.5 Cij=(u

32、i+vj）ui=Cij-vj）5.2.10 因为：V5=0，C35=(u3+v4）u3=25，V2=C32-u3=35-25=10C22=(u2+v2），u2=C22-v2=40-10=30V3=C23-u2=15-30=-15,表5.23检验数,20,30,20,40,ij=Cij-(ui+vj）(I，j）JN 5.2.713=C13-(u1+v3）=20-(-15+5)=3014=C14-(u1+v4）=20-(5+0)=1515=C15-(u1+v5）=40-(5+0)=3521=C21-(u2+v1）=20-(5+30)=-1525=C25-(u2+v5）=30-(30+0)=031=

33、C31-(u3+v1）=30-(25+5)=033=C33-(u3+v3）=40-(25-15)=3034=C34-(u3+v4）=55-(25+0)=30有ij0，故不是最优解,20,30,40,55,题5.24基本可行解,ij=min ij|ij0=21=-15（I，j）JN非优，建闭回路,X(1)=(15，35，0，0，0，10，0，60，30，0，0，80，0，0，70）TZ(1)=1510+3515+1025+6015+3030+8035+7025=7225,表5.25检验数,40,30,20,40,ij=Cij-(ui+vj）(I，j）JN 5.2.713=C13-(u1+v3）=

34、20-(0+5)=1514=C14-(u1+v4）=20-(5+15)=015=C15-(u1+v5）=40-(5+0)=3522=C22-(u2+v2）=40-(15+10)=1525=C25-(u2+v5）=30-(15+0)=1531=C31-(u3+v1）=30-(25+5)=033=C33-(u3+v3）=40-(25+0)=1534=C34-(u3+v4）=55-(25+15)=15有ij0，故是最优解,20,30,40,55,题5.11基本可行解,表5.11,7,4,8,4非,7,3,2,V4=0，基变量:X11，X12，X22，X23，X33，X34 Cij-(ui+vj）=0

35、（I，j）JB 5.2.5 Cij=(ui+vj）ui=Cij-vj）5.2.10 因为：V4=0，C34=(u3+v4）=u3=9，u2=C24-V4=7-0=7C23=(u2+v3），u2=C23-v3=10-(-7)=17,表5.11 未画掉的格,7,4,8,4非,7,3,2,V4=0，基变量:X11，X12，X22，X23，X33，X34 Cij-(ui+vj）=0（I，j）JB 5.2.5 Cij=(ui+vj）ui=Cij-vj）5.2.10 因为：V4=0，C34=(u3+v4）=u3=9，u2=C24-V4=7-0=7C23=(u2+v3），u2=C23-v3=10-(-7)=

36、17,表5.11,7,4,8,4非,7,3,2,ij=Cij-(ui+vj）(I，j）JN 5.2.713=C13-(u1+v3）=7-(6+3)=-214=C14-(u1+v4）=3-(6+0)=-321=C21-(u2+v1）=4-(-1+7)=-233=C24-(u2+v4）=2-(9+3)=-1031=C31-(u3+v1）=8-(9-1)=032=C32-(u3+v2）=4-(9+2)=-7有ij0，故不是最优解,题5.11基本可行解,Z(1)=65+18+59+310+0*7+39=140Z(2)=65+18+59+30+3*7+32=109,表5.11,7,4,8,4非,7,3,

37、10,ij=Cij-(ui+vj）(I，j）JN 5.2.713=C13-(u1+v3）=7-(6+3)=-214=C14-(u1+v4）=3-(6+0)=-321=C21-(u2+v1）=4-(-1+7)=-233=C24-(u2+v4）=2-(9+3)=-1031=C31-(u3+v1）=8-(9-1)=032=C32-(u3+v2）=4-(9+2)=-7有ij0，故不是最优解,表5.12,7,4,8,4非,7,3,7,ij=Cij-(ui+vj）(I，j）JN 5.2.713=C13-(u1+v3）=7-(-7+16)=-214=C14-(u1+v4）=3-(-16+0)=1921=C21-(u2+v1）=4-(-11+17)=-224=C24-(u2+v4）=7-(-17+0)=2431=C31-(u3+v1）=8-(9-11)=1032=C32-(u3+v2）=4-(9-8)=-3有ij0，故不是最优解,表5.13,Z=33+411+29+22+310+65=133(元),ij=min ij|ij0=32=-13（I，j）JN,表5.5初始方案，5.10 检验数不大于0,32=-13,=minXij|(I，j)为闭回路上所有偶数号格点=min(2，3)=2=X22,