最小匹配算法的lingo程序

1、最小匹配算法的lingo程序1.2从中列出任惹两奇顶点距离设蹈个奇阶顶点为矿，叫，“,冗,，从矩阵中可得到如下任意两奇顶点间的距 离KA VI ：打其中：上为f中到叫的最短通路长.据此，可得到配时新个顶点的0T规划算 法.1.3 01规划求解模型I殳变量表示顶点舟和叫的配对关系1,和叫配对时，J 1 o. 7； V不配对时 TOC o 1-5 h z Ja- I则有 Tnimr = N S Li i i - 1/2 M，:一 j f 1t 2 ）j -2，艺3）SIi - 1? *T-云 M k + 习- = 1 性=2,2广 1）（ 4 ）j工】f ； 4、*i0 就 L （i = 1,2,

2、，2g-九 j = 2,3,，2g）式（l）是目株函数，表示在网络中重复边的总和最小式H）,式（3）,式（4）表示任一 顶点只能与其他个顶点有匹配关系.根据上面方法，假设图中奇顶点数为n=6，重新编号为v1, v2, v6,对应找出这些顶点之间每对最短距离矩阵e,再做一个同行同列的决策变量矩阵x=（xij），显然x中下三角矩阵（包括主对角线）上元素均为0，那么所求的目标即是矩阵点乘e.*x中上三角元素和的最小值，约束即是每行在上三角矩阵中元素之和等于1.为方便借用matlab随机矩阵命令产生数据e，虽然e应为对称数据，而a非对称，不过我们只需a的上三角矩阵数据，因此我们只利用a的上三角数据，这

3、样并不影响求解。matlab中输入： a=rand(6)a =0.20280.74680.52520.37950.18970.69790.19870.44510.20260.83180.19340.37840.60380.93180.67210.50280.68220.86000.27220.46600.83810.70950.30280.85370.19880.41860.01960.42890.54170.59360.01530.84620.68130.30460.15090.4966将数据a拷到lingo数据段e：sets:v/1.6/;vv(v,v):e,x;endsetsdata:e

4、=0.20280.74680.52520.37950.18970.69790.19870.44510.20260.83180.19340.37840.60380.93180.67210.50280.68220.86000.27220.46600.83810.70950.30280.85370.19880.41860.01960.42890.54170.59360.01530.84620.68130.30460.15090.4966;enddatamin=sum(vv:e*x);for(vv(i,j)|i#ge#j:x(i,j)=0);for(v(i):sum(v(k):x(k,i)+sum(v(j):x(i,j)=1);for(vv:bin(x);部分结果显示：Global optimal solution found.Objective bound:1.070900Infeasibilities:0.000000Extended solver steps:0Total solver iterations:0VariableValueReduced CostX( 1, 5)1.0000000.1897000X( 2, 6)1.0000000.3784000