最小匹配算法的lingo程序

1、最小匹配算法的lingo程序1.2從中列出任惹兩奇頂點(diǎn)距離設(shè)蹈個奇階頂點(diǎn)為礦，叫，“,冗,，從矩陣中可得到如下任意兩奇頂點(diǎn)間的距 離KA VI ：打其中：上為f中到叫的最短通路長.據(jù)此，可得到配時新個頂點(diǎn)的0T規(guī)劃算 法.1.3 01規(guī)劃求解模型I殳變量表示頂點(diǎn)舟和叫的配對關(guān)系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 + 習(xí)- = 1 性=2,2廣 1）（ 4 ）j工】f ； 4、*i0 就 L （i = 1,2,

2、，2g-九 j = 2,3,，2g）式（l）是目株函數(shù)，表示在網(wǎng)絡(luò)中重復(fù)邊的總和最小式H）,式（3）,式（4）表示任一 頂點(diǎn)只能與其他個頂點(diǎn)有匹配關(guān)系.根據(jù)上面方法，假設(shè)圖中奇頂點(diǎn)數(shù)為n=6，重新編號為v1, v2, v6,對應(yīng)找出這些頂點(diǎn)之間每對最短距離矩陣e,再做一個同行同列的決策變量矩陣x=（xij），顯然x中下三角矩陣（包括主對角線）上元素均為0，那么所求的目標(biāo)即是矩陣點(diǎn)乘e.*x中上三角元素和的最小值，約束即是每行在上三角矩陣中元素之和等于1.為方便借用matlab隨機(jī)矩陣命令產(chǎn)生數(shù)據(jù)e，雖然e應(yīng)為對稱數(shù)據(jù)，而a非對稱，不過我們只需a的上三角矩陣數(shù)據(jù)，因此我們只利用a的上三角數(shù)據(jù)，這

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將數(shù)據(jù)a拷到lingo數(shù)據(jù)段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);部分結(jié)果顯示：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