数学建模-运输问题

整理文档整理文档运输问题

摘要本文主要研究的是货物运输的最短路径问题，利用图论中的Floyd算法、Kruskal算法，以及整数规划的方法建立相关问题的模型，通过 matlab，lingo编程求解出最终结果。关于问题一，是一个两客户间最短路程的问题，因此本文利用Floyd算法对其进行分析。考虑到计算的方便性，首先，我们将两客户之间的距离输入到网络权矩阵中；然后，逐步分析出两客户间的最短距离；最后，利用Matlab软件对其进行编程求解，运行得到结果： 2-3-8-9-10总路程为 85公里。关于问题二，运输公司分别要对10个客户供货，必须访问每个客户，实际上是一个旅行商问题。首先，不考虑送货员返回提货点的情形，本文利用最小生成树问题中的Kruskal算法，结合题中所给的邻接矩阵，很快可以得到回路的最短路线： 1-5-7-6-3-4-8-9-10-2；然后利用问题一的 Floyd算法编程，能求得从客户2到客户 1（提货点）的最短路线是： 2-1，路程为50公里。即最短路线为：1-5-7-6-3-4-8-9-10-2-。但考虑到最小生成树法局限于顶点数较少的情形，不宜进1一步推广，因此本文建立以路程最短为目标函数的整数规划模型；最后，利用LINGO软件对其进行编程求解，求解出的回路与 Kruskal算法求出的回路一致。关于问题三，是在每个客户所需固定货物量的情况下，使得行程之和最短。这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在 50个单位以内即可。因此我们在问题二模型的基础上进行改进，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，对于模型求解出来的结果，本文利用Kruska算法结合题中所给的邻接矩阵进行优化。得到优化结果为：第一辆车：1-5-2-3-4-8-9-1，第二辆车： 1-7-6-9-10-1，总路程为 280公里。关于问题四，在问题一的基础上我们首先用 Matlab软件编程确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一种很理想的运输方案。根据 matlab运行结果分析得出4条最优路线分别为： 1-5-2，1-4-3-8，1-7-6，1-9-10。最短总路线为 245公里，最小总费用为 645。关键词：Floyd算法Kruskal算法整数规划旅行商问题一、问题重述某运输公司为10个客户配送货物，假定提货点就在客户1所在的位置，从第i个客户到第j个客户的路线距离(单位公里)用下面矩阵中的(i,j)(i,j1,L,10)位置上的数表示(其中表示两个客户之间无直接的路线到达)。

12345TOC\o"1-5"\h\z1 0 50 40123452 50 0 303 30 0 154 40 15 05 25 15 456 50 30 30730 508 60 25 209 20 4010 35 20 10 45253050253050355060305025604530552040650601030556002555351025030456030553001015254502020603006 7 8 910客户 10送货，已知送给客户10的货已在运送员的车上，请帮运送员设计一个到客户10的尽可能短的行使路线（假定上述矩阵中给出了所有可能的路线选择） 。现运输公司派了一辆大的货车为这 10个客户配送货物，假定这辆货车一次能装满10个客户所需要的全部货物，请问货车从提货点出发给 10个客户配送完货物后再回到提货点所行使的尽可能短的行使路线？对所设计的算法进行分析。现因资源紧张，运输公司没有大货车可以使用，改用两辆小的货车配送货物。每辆小货车的容量为50个单位，每个客户所需要的货物量分别为8，13，6，9，7，15，10，5，12，9个单位，请问两辆小货车应该分别给那几个客户配送货物以及行使怎样的路线使它们从提货点出发最后回到提货点所行使的距离之和尽可能短？对所设计的算法进行分析。如果改用更小容量的车，每车容量为25个单位，但用车数量不限，每个客户所需要的货物量同第3问，并假设每出一辆车的出车费为100元，运货的价格为1元/公里（不考虑空车返回的费用） ，请问如何安排车辆才能使得运输公司运货的总费用最省？二、问题分析关于问题一，是一个两客户间最短路程的问题，因此本文利用Floyd算法对其进行分析。考虑到计算的方便性，首先，我们将两客户之间的距离输入到网络权矩阵中；然后，逐步分析出两客户间的最短距离；最后，利用 Matlab软件对其进行编程求解。关于问题二，运输公司分别要对10个客户供货，必须访问每个客户，实际上是寻找一条最短的行车路线。首先，不考虑送货员返回提货点的情形，本文利用最小生成树问题中的Kruskal算法，结合题中所给的邻接矩阵，很快可以得到回路的最短路线：v1 v5 v7 v6 v3 v4 v8 v9 v10 v2；然后利用问题一的Floyd算法和程序，能求得从客户2到客户1（提货点）的最短路线是： v2 v1，路程为50公里。但考虑到最小生成树法局限于顶点数较少的情形，不宜进一步推广，因此本文又根据路程最短建立以路程最短为目标函数的整数规划模型；最后，利用LINGO软件对其进行编程求解。关于问题三，是在每个客户所需固定货物量的情况下，使得行程之和最短。这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在 50个单位以内即可。因此我们在问题二模型的基础上进行改进，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，对于模型求解出来的结果，本文利用Kruska算法结合题中所给的邻接矩阵进行优化。关于问题四，我们首先用Matlab软件编程确定提货点到每个客户点间的最

短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一种很理想的运输方案。三、模型假设.假设客户级别平等；.假设不考虑装卸车费用；.假设货车不发生意外事故；.假设运输过程中货物无损失；四、符号说明vij:不同的客户i1.210;j1.210；lj:从客户Vi到客户Vj的距离；1:从第i个客户到第j个客户有直接的路到达；xij0:从第i个客户到第j个客户无直接的路到达；Cj:从第i个客户到第j个客户的距离；aj:第j个客户所需的货物量；z：总路程；五、模型的建立与求解问题一模型的建立与求解模型的建立2到客户10的最短路径，本文利用Floyd算法对此文进行求解。为计算方便，令网络的权矩阵为 D(dj)nn,lj为Vi到Vj的距离其中dij其中dijlij 当（ Vi,Vj） E其他Floyd算法基本步骤为：(1)输入权矩阵D(0)D。(2)计算 D(k) (di(jk))nn (k1,2,3, ,n)其中 dij(k) min[di(jk1),di(kk 1)dj(kk 1)](3)D⑺(djn))nn中元素djn)就是Vi到Vj的最短路长。5.1.2模型的求解在本文计算中n10，对Floyd算法进行编程(程序见附录1)，利用Matlab软件进行求解。运行结果如下：a=0405540255530555070500304535504555658555300155530502535554045150453050203050251545450351030405555503030350255035553025505010250304060304525203025300103020403040351525450203520102520403035300path=

766676696328TOC\o"1-5"\h\z1 5 4 4 51 2 3 3 54 2 3 4 81 3 3 4 51 2 2 4 57 2 3 4 71 5 3 8 59 5 3 4 510 10 4 72 3 3 5请输入起点2请输入终点 10238910由运行结果可以得出运货员从客户v2 v3v7 5 9 95 3 3 37 8 8 88 8 8 87 8 8 107 4 9 97 5 9 95 3 3 37 8 8 88 8 8 87 8 8 107 4 9 97 8 8 107 8 9 97 8 9 105 3 9 10到客户10的最短路径是：v9 v105.2问题二模型的建立与求解模型的建立运输公司为这 10个客户配送货物问题实际上是寻找一条最短的行车路线。当不考虑送货员返回提货点的时候，本文利用最小生成树问题中的Kruskal算法结合题中所给的邻接矩阵，很快可以得到无回路的最短路线。Kruskal算法基本步骤：每步从未选的边中选取边e,使它与已选边不够成圈，且e是未选边中的最小权边，知道选够 n1条边为止。利用最小生成树问题中的Kruskal算法结合题中所给的邻接矩阵，很快可以得到以下最小生成树：v1 v5 v7 v6 v3 v4 v8 v9 v10 v2这两棵生成树不同之处就在于从客户6到达客户8的路径不一样，而实际路程经过计算后是一样的，路线的总行程为175公里。利用问题一的Floyd算法和程序，能求得从客户2到客户 1（提货点）的最短路线是 v2 v1，路程为50公里。这样该回路，即最短的行车路线为：v1 v5 v7 v6 v3 v4 v8 v9 v10 v2 v1行车路线总行程为225公里。以最小生成树法解决此问题速度快，结果较精确，但是只适合数目较少时，不适宜推广，因此本文又根据路程最短建立整数规划模型。为了更好的防止子巡回的产生，根据哈米尔顿回路，须附加一个约束条件：uiujnxij n1, 2ijn当访问客户i后必须要有一个即将访问的确切客户；访问客户j前必须要有一个刚刚访问过的确切客户。依次设立约束条件。

1010:minZ Cij Xiji1j110Xij1i1,2,,10j110Xij1j1,2,,10i1Xij 0或1 0,1变量s.tTOC\o"1-5"\h\zui uj nXij n12ijnui0 i 1,2, ,105.2.2模型的求解利用Lingo求解模型部分结果（附录 2）：Globaloptimalsolutionfound.Objectivevalue:Objectivebound:Globaloptimalsolutionfound.Objectivevalue:Objectivebound:Infeasibilities:Extendedsolversteps:Totalsolveriterations:VariableX(1,5)X(2,1)X(3,4)X(4,8)X(5,7)X(6,3)X(7,6)X(8,9)X(9,10)X(10,2)225.0000225.00000.000000086ValueReducedCost1.00000025.000001.00000050.000001.00000015.000001.00000020.000001.00000010.000001.00000030.000001.00000025.000001.00000010.000001.00000020.000001.00000020.00000由此可得，行程路线最短的回路:v1 由此可得，行程路线最短的回路:v1 v5 v7 v6v3 v4 v8 v9 v10 v2 v1总路程为 225公里。5.3问题三模型的建立与求解5.3.1模型的建立用两辆容量为50单位的小货车运货，在每个客户所需固定货物量的情况下，要使得行程之和最短。这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在 50个单位以内。此问与问题二有相似之处都要考虑回到提货点的情形,因此本文在模型 2的基础上进行改进,重新建立相应的整数线性规划模型。1010目标函数：minz cij xiji1j110xij 1 (j1,2L10)i110xij 1 (i1,2L10)j1xij 0或1s.tui-uj+nxijn1101036 xijaij50i1j1TOC\o"1-5"\h\z10 10xij 1, xij 1,j2 i25.3.2模型的求解Globaloptimalsolutionfound.Objectivevalue:Objectivebound:Infeasibilities:Extendedsolversteps:Totalsolveriterations:利用Globaloptimalsolutionfound.Objectivevalue:Objectivebound:Infeasibilities:Extendedsolversteps:Totalsolveriterations:155.0000155.00000.2220446E-150224VariableValueReducedCostX(1,5)1.00000025.00000X(2,3)1.00000030.00000X(3,6)1.00000030.00000X(5,2)1.00000015.00000X(6,7)1.00000025.00000X(7,1)1.00000030.00000Globaloptimalsolutionfound.135.0000Objectivevalue:135.0000Objectivebound:135.0000Infeasibilities:0.2220446E-15Extendedsolversteps:0Totalsolveriterations:224VariableValueReducedCostX(1,4)1.00000040.00000X(4,8)1.00000020.00000X(5,1)1.00000025.00000X(8,9)1.00000010.00000X(9,10)1.00000020.00000X(10,5)1.00000020.00000由此可得，两辆车的行车路线及路程:第一辆车： v1 v5 v2 v3 v6 v7 v1，包含的客户有 2,3,6,7，运货总量为 44，路程为 155公里。第二辆车： v1 v4 v8 v9 v10 v5 v1，包含的客户有 4,8，9,10,5运货总量为 42单位，路程为 135公里。总路程为 290公里。5.3.3模型的优化对于模型求解出来的结果，本文利用Kruskal算法结合题中所给的邻接矩阵进行优化。从起始点v1处，进行分析，用两辆小的货车配送货物，为了尽可能的减少两辆车的重复路线， v1到v5、v7的路程最短，让两辆车分开运货，先根据货物承载量 50的限制让其中的一辆车走完路程，再让另一辆车走剩余城市的最短路线，这样走出两条运货路线：第一种情况：第一辆车： v1 v5 v2 v3 v4 v8 v9 v1，包含的客户有5,2,3,4,8从本g型1可解得，从V8回到vi的最短路线是V8 v%,运货总量为 40单位，路程为 145公里。第二辆车： v1v1，包含的客户有 7,6,9,10，v第二辆车： v1v1，包含的客户有 7,6,9,10，运货总量为 46，路程为 135公里。这种情况下总路程为 280公里。第二种情况：第一辆车： v1 v7 v6 v3 v4 v8 v9 v1，包含的客户有7,6,3,4,8从卞g型1可解得，从V8回到vi的最短路线是v8 V9 vi,运货总量为 45单位，路程为 150公里。第二辆车： vi v5 v2 v3 v8 v9 vi0 vi，包含的客户5,2,9,10运货总量为41单位，路程为160。这种情况下总路程为31淤里。对这两种情况对比，分析，可以看出第一种情况优于第二种情况。因此选择第一种情况的路线。5.4问题四模型的建立与求解题目要求我们运费最省，所以要考虑到需要的车最少，以及每辆车行驶的路程最短，而且还要保证送到每个客户手中。根据客户总需求量和货车的容量，所以，公司可派 4辆货车去送货。在此，我们假设：从提货点1到各客户点最短路为 p1j(j2,310)从提货点1到各客户点的最短路程 L1j(j2,310)提货点1到各客户点路径客户所需要货物量的总和 G1j(j2,310)运用matlab程序(见附录4)可得：p12:152 p13:143 p14:14p15:15p16:176p17:17 p18:158p19:19p110:1910从中可以发现： G1j 25，所以我们要继续对其进行分析：首先为了保证送到每个客户手里，所以必须走 56和即0,那样就可以删除P17和P19；然后考虑到货车的路程最短，所以要走 P12,删除P15和P18；最后，就只能走1-4-3-8路线。

图i四辆货车路线图经过计算可得下表：表1:4辆车的情况表每辆车的路线每辆车的路程每辆车所载的货物量1-5-240201-4-3-880201-7-655251-9-107021所以，可得到目标函数:minz4*1001*L1jminz4*1001*(40805570)645六、模型的评价与推广6.1模型的评价模型的优点(1)在整个模型的建立过程中，本文考虑的比较全面客观，使模型具有较强的说服力，结果更合理。(2)根据问题的特点，综合运用了多个软件，如lingo、matlab等等，使得在解决问题的过程中，更方便简单。模型的缺点这种寻路方法有其局限性，只适用于一些顶点较少的情况，顶点多，寻找起来较为麻烦。6.2模型的推广模型的建立比较客观，在现实中也可以广泛的应用，与现实情况紧密相连；比如：最优路径问题与哈密顿回路问题，这些在现实中应用范围已经很广了。七、参考文献胡运权，运筹学教程第四版，北京：清华大学出版社， 2012。朱道元，数学建模案例精选，北京：科学出版社，2005。姜启源，谢金星。叶俊．数学模型北京：高等教育出版杜，2004。吴祈宗．运筹学与最优化方法 fM．北京：机械工业出版社， 2003。附录附录1：clear;clc;M=10000;%不能直接到达是将距离赋值给 Ma(1,:)=[0,50,M,40,25,M,30,M,50,M];a(2,:)=[50,0,30,M,35,50,M,60,M,M];a(3,:)=[M,30,0,15,M,30,50,25,M,60];a(4,:)=[40,M,15,0,45,30,55,20,40,65];a(5,:)=[25,15,M,45,0,60,10,30,M,55];a(6,:)=[M,50,30,30,60,0,25,55,35,M];a(7,:)=[30,M,50,M,10,25,0,30,45,60];a(8,:)=[M,60,25,20,30,55,30,0,10,M];a(9,:)=[20,M,M,40,M,15,25,45,0,20];a(10,:)=[35,20,10,45,20,M,60,M,30,0];犍立a矩阵path=zeros(length(a));%建立一个与矩阵 a同大小的全零矩阵fori=1:10forj=1:10path(i,j)=j;%用path矩阵记录走过的点endendfork=1:10fori=1:10forj=1:10ifa(i,j)>a(i,k)+a(k,j)a(i,j)=a(i,k)+a(k,j);path(i,j)=path(i,k);%floyd算法endendendenda,pathi1=input('请输入起点 ');i2=input('请输入终点 ');disp(i1);whilei1~=i2i1=path(i1,i2);disp(i1);end;附录2：MODEL:SETS:CUSTOMERS/1..10/:U;LINK(CUSTOMERS,CUSTOMERS):DIST,X;ENDSETSDATA:DIST=0501000004025100000301000005010000050030100000355010000060100001000001000003001510000030502510000060401000015045305520406525151000004506010301000005510000050303060025553510000003010000050100000102503045601000006025203055300101000002010000010000040100000152545020352010452010000060100000300;ENDDATAN=@SIZE(CUSTOMERS);MIN=@SUM(LINK:DIST*X);@FOR(CUSTOMERS(K):@SUM(CUSTOMERS(I)|I#NE#K:X(I,K))=1;@SUM(CUSTOMERS(J)|J#NE#K:X(K,J))=1;@FOR(CUSTOMERS(J)|J#GT#1#AND#J#NE#K:U(J)>=U(K)+X(K,J)-(N-2)*(1-X(K,J))+(N-3)*X(J,K)););@FOR(LINK:@BIN(X));@FOR(CUSTOMERS(K)|K#GT#1:U(K)<=N-1-(N-2)*X(1,K);U(K)>=1 +(N-2)*X(K,1));ENDGlobaloptimalsolutionfound.Objectivevalue: 225.0000Objectivebound: 225.0000Infeasibilities: 0.000000Extendedsolversteps: 0Totalsolveriterations: 86VariableValueReducedCostN10.000000.000000U(1)0.0000000.000000U(2)9.0000000.000000U(3)4.0000000.000000U(4)5.0000000.000000U(5)1.0000000.000000U(6)3.0000000.000000U(7)2.0000000.000000U(8)6.0000000.000000U(9)7.0000000.000000U(10)8.0000000.000000DIST(1,1)0.0000000.000000DIST(1,2)50.000000.000000DIST(1,3)100000.00.000000DIST(1,4)40.000000.000000整理文档整理文档DIST(1,5)25.000000.000000DIST(1,6)100000.00.000000DIST(1,7)30.000000.000000DIST(1,8)100000.00.000000DIST(1,9)50.000000.000000DIST(1,10)100000.00.000000DIST(2,1)50.000000.000000DIST(2,2)0.0000000.000000DIST(2,3)30.000000.000000DIST(2,4)100000.00.000000DIST(2,5)35.000000.000000DIST(2,6)50.000000.000000DIST(2,7)100000.00.000000DIST(2,8)60.000000.000000DIST(2,9)10000.000.000000DIST(2,10)100000.00.000000DIST(3,1)100000.00.000000DIST(3,2)30.000000.000000DIST(3,3)0.0000000.000000DIST(3,4)15.000000.000000DIST(3,5)100000.00.000000DIST(3,6)30.000000.000000DIST(3,7)50.000000.000000DIST(3,8)25.000000.000000DIST(3,9)100000.00.000000DIST(3,10)60.000000.000000DIST(4,1)40.000000.000000DIST(4,2)10000.000.000000DIST(4,3)15.000000.000000DIST(4,4)0.0000000.000000DIST(4,5)45.000000.000000DIST(4,6)30.000000.000000DIST(4,7)55.000000.000000DIST(4,8)20.000000.000000DIST(4,9)40.000000.000000DIST(4,10)65.000000.000000DIST(5,1)25.000000.000000DIST(5,2)15.000000.000000DIST(5,3)100000.00.000000DIST(5,4)45.000000.000000DIST(5,5)0.0000000.000000DIST(5,6)60.000000.000000DIST(5,7)10.000000.000000DIST(5,8)30.000000.000000DIST(5,9)100000.00.000000DIST(5,10)55.000000.000000DIST(6,1)100000.00.000000DIST(6,2)50.000000.000000DIST(6,3)30.000000.000000DIST(6,4)30.000000.000000DIST(6,5)60.000000.000000DIST(6,6)0.0000000.000000DIST(6,7)25.000000.000000DIST(6,8)55.000000.000000DIST(6,9)35.000000.000000DIST(6,10)1000000.0.000000DIST(7,1)30.000000.000000DIST(7,2)100000.00.000000DIST(7,3)50.000000.000000DIST(7,4)100000.00.000000DIST(7,5)10.000000.000000DIST(7,6)25.000000.000000DIST(7,7)0.0000000.000000DIST(7,8)30.000000.000000DIST(7,9)45.000000.000000DIST(7,10)60.000000.000000DIST(8,1)100000.00.000000DIST(8,2)60.000000.000000DIST(8,3)25.000000.000000DIST(8,4)20.000000.000000DIST(8,5)30.000000.000000DIST(8,6)55.000000.000000DIST(8,7)30.000000.000000DIST(8,8)0.0000000.000000DIST(8,9)10.000000.000000DIST(8,10)100000.00.000000DIST(9,1)20.000000.000000DIST(9,2)100000.00.000000DIST(9,3)100000.00.000000DIST(9,4)40.000000.000000DIST(9,5)100000.00.000000DIST(9,6)15.000000.000000DIST(9,7)25.000000.000000DIST(9,8)45.000000.000000DIST(9,9)0.0000000.000000DIST(9,10)20.000000.000000DIST(10,1)35.000000.000000DIST(10,2)20.000000.000000

DIST(10,3)10.000000.000000DIST(10,4)45.000000.000000DIST(10,5)20.000000.000000DIST(10,6)100000.00.000000DIST(10,7)60.000000.000000DIST(10,8)100000.00.000000DIST(10,9)30.000000.000000DIST(10,10)0.0000000.000000X(1,1)0.0000000.000000X(1,2)0.00000050.00000X(1,3)0.000000100000.0X(1,4)0.00000040.00000X(1,5)1.00000025.00000X(1,6)0.000000100000.0X(1,7)0.00000030.00000X(1,8)0.000000100000.0X(1,9)0.00000050.00000X(1,10)0.000000100000.0X(2,1)1.00000050.00000X(2,2)0.0000000.000000X(2,3)0.00000030.00000X(2,4)0.000000100000.0X(2,5)0.00000035.00000X(2,6)0.00000050.00000X(2,7)0.000000100000.0X(2,8)0.00000060.00000X(2,9)0.00000010000.00X(2,10)0.000000100000.0X(3,1)0.000000100000.0X(3,2)0.00000030.00000X(3,3)0.0000000.000000X(3,4)1.00000015.00000X(3,5)0.000000100000.0X(3,6)0.00000030.00000X(3,7)0.00000050.00000X(3,8)0.00000025.00000X(3,9)0.000000100000.0X(3,10)0.00000060.00000X(4,1)0.00000040.00000X(4,2)0.00000010000.00X(4,3)0.00000015.00000X(4,4)0.0000000.000000X(4,5)0.00000045.00000X(4,6)0.00000030.00000

X(4,7)0.00000055.00000X(4,8)1.00000020.00000X(4,9)0.00000040.00000X(4,10)0.00000065.00000X(5,1)0.00000025.00000X(5,2)0.00000015.00000X(5,3)0.000000100000.0X(5,4)0.00000045.00000X(5,5)0.0000000.000000X(5,6)0.00000060.00000X(5,7)1.00000010.00000X(5,8)0.00000030.00000X(5,9)0.000000100000.0X(5,10)0.00000055.00000X(6,1)0.000000100000.0X(6,2)0.00000050.00000X(6,3)1.00000030.00000X(6,4)0.00000030.00000X(6,5)0.00000060.00000X(6,6)0.0000000.000000X(6,7)0.00000025.00000X(6,8)0.00000055.00000X(6,9)0.00000035.00000X(6,10)0.0000001000000.X(7,1)0.00000030.00000X(7,2)0.000000100000.0X(7,3)0.00000050.00000X(7,4)0.000000100000.0X(7,5)0.00000010.00000X(7,6)1.00000025.00000X(7,7)0.0000000.000000X(7,8)0.00000030.00000X(7,9)0.00000045.00000X(7,10)0.00000060.00000X(8,1)0.000000100000.0X(8,2)0.00000060.00000X(8,3)0.00000025.00000X(8,4)0.00000020.00000X(8,5)0.00000030.00000X(8,6)0.00000055.00000X(8,7)0.00000030.00000X(8,8)0.0000000.000000X(8,9)1.00000010.00000X(8,10)0.000000100000.0

X(9,1)0.00000020.00000X(9,2)0.000000100000.0X(9,3)0.000000100000.0X(9,4)0.00000040.00000X(9,5)0.000000100000.0X(9,6)0.00000015.00000X(9,7)0.00000025.00000X(9,8)0.00000045.00000X(9,9)0.0000000.000000X(9,10)1.00000020.00000X(10,1)0.00000035.00000X(10,2)1.00000020.00000X(10,3)0.00000010.00000X(10,4)0.00000045.00000X(10,5)0.00000020.00000X(10,6)0.000000100000.0X(10,7)0.00000060.00000X(10,8)0.000000100000.0X(10,9)0.00000030.00000X(10,10)0.0000000.000000RowSlackorSurplusDualPrice10.0000000.0000002225.0000-1.00000030.0000000.00000040.0000000.000000510.000000.000000612.000000.000000713.000000.00000080.0000000.000000911.000000.0000001010.000000.0000001114.000000.0000001215.000000.0000001316.000000.000000140.0000000.000000150.0000000.000000163.0000000.000000174.0000000.000000180.0000000.000000192.0000000.000000201.0000000.000000215.0000000.000000226.0000000.000000230.0000000.000000240.0000000.000000250.0000000.0000002613.000000.000000270.0000000.000000285.0000000.000000290.0000000.000000306.0000000.0000003110.000000.0000003211.000000.0000003312.000000.000000340.0000000.000000350.0000000.0000003612.000000.000000370.0000000.000000384.0000000.000000396.0000000.000000405.0000000.000000410.0000000.0000004210.000000.0000004311.000000.000000440.0000000.000000450.0000000.0000004616.000000.0000004711.000000.0000004812.000000.0000004910.000000.000000500.0000000.0000005113.000000.0000005214.000000.0000005315.000000.000000540.0000000.000000550.0000000.0000005614.000000.000000570.0000000.0000005810.000000.000000596.0000000.000000600.0000000.0000006111.000000.0000006212.000000.0000006313.000000.000000640.0000000.000000650.0000000.0000006615.000000.000000

6710.000000.0000006811.000000.000000690.0000000.000000700.0000000.0000007112.000000.0000007213.000000.0000007314.000000.000000740.0000000.000000750.0000000.0000007611.000000.000000776.0000000.000000780.0000000.000000793.0000000.000000805.0000000.000000814.0000000.000000820.0000000.0000008310.000000.000000840.0000000.000000850.0000000.0000008610.000000.000000875.0000000.000000886.0000000.000000892.0000000.000000904.0000000.000000913.0000000.000000920.0000000.000000930.0000000.000000940.0000000.000000950.0000000.000000960.0000000.000000974.0000000.000000985.0000000.000000991.0000000.0000001003.0000000.0000001012.0000000.0000001026.0000000.0000001030.0000000.0000001040.0000000.0000001050.0000000.0000001065.0000000.0000001073.0000000.0000001084.0000000.0000001094.0000000.0000001100.0000000.0000001110.0000000.0000001126.0000000.0000001132.0000000.0000001147.0000000.0000001151.0000000.0000001163.0000000.0000001175.0000000.0000001182.0000000.0000001196.0000000.0000001201.0000000.0000001217.0000000.000000附录3：model:sets:v/1..10/:u,D;link(v,v):C,y,x;endsetsmin=@sum(link:C*x);@sum(v(I)|I#ne#1:x(I,1))=1;@sum(v(I)|I#ne#1:x(1,I))=1;@FOR(v(K):@sum(v(I)|I#ne#K:x(I,K))<1;@sum(v(J)|J#ne#K:x(K,J))<1);@FOR(v(K):@bin(@sum(v(I)|I#ne#K:x(I,K)));@bin(@sum(v(J)|J#ne#K:x(K,J))));@sum(v(I)|I#ne#6