数学建模社区-数学中国

标题: 求助大神！急！ [打印本页]

作者: 、后知后觉り. 时间: 2013-7-23 15:28
标题: 求助大神！急！
如何用lingo 求配送公司的车辆（辆数未知）到8个客户的送货的最短路程下面是配送公司到客户的距离矩阵

0,40, 60, 75,90,200,100,160,80,

40,0,65,40, 100,50,75,110,100,

60,65,0,75,100, 100, 75,75,75,

75,40,75,0,100,50, 90,90,150,

90,100,100,100,0,100,75,75,100,

200,50, 100,50,100,0,70,90,75,

100,75, 75, 90,75,70,0,70, 100,

160,110,75,90,75,90,70,0,100,

80,100,75,150,100, 75,100,100,0,

作者: wujianjack2 时间: 2013-7-23 15:57
本帖最后由 wujianjack2 于 2013-7-23 19:06 编辑

第一次回答：
后知后觉，你好！问的问题很好呢！
个人觉得这是一个MST问题，即求最小生成树，可能的程序代码如下：
SETS:
CITY/1..9/:U;
LINK(CITY,CITY):DIST,X;
ENDSETS
N=@SIZE(CITY);
DATA:
DIST=0 40 60 75 90 200 100 160 80
   40 0 65 40 100 50 75 110 100
   60 65 0 75 100 100 75 75 75
   75 40 75 0 100 50 90, 90 150
   90 100 100 100 0 100 75 75 100
   200 50 100 50 100 0 70 90 75
   100 75 75 90 75 70 0 70 100
   160 110 75 90 75 90 70 0 100,
   80 100 75 150 100 75 100 100 0;
!PUT YOUR DATA HERE;
ENDDATA
MIN=@SUM(LINK:DIST*X);
U(1)=0;
@FOR(LINK:@BIN(X));
@FOR(CITY(K)|K#GT#1:@SUM(CITY(I)|I#NE#K:X(I,K))=1;@FOR(CITY(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);););
@SUM(CITY(J)|J#GT#1:X(1,J))>=1;
@FOR(CITY(K)|K#GT#1:U(K)>=1;U(K)<=N-1-(N-2)*X(1,K););
END

运行结果为(仅给出重要结果)：
  Global optimal solution found.
  Objective value:                            480.0000
  Objective bound:                         480.0000
  Infeasibilities:                                  0.000000
  Extended solver steps:                         0
  Total solver iterations:                         35

                     Variable          Value       Reduced Cost
                     X( 1, 2)       1.000000          40.00000
                     X( 1, 3)       1.000000          60.00000
                     X( 2, 4)       1.000000          40.00000
                     X( 2, 6)       1.000000          50.00000
                     X( 3, 9)       1.000000          75.00000
                     X( 6, 7)       1.000000          70.00000
                     X( 7, 5)       1.000000          75.00000
                     X( 7, 8)       1.000000          70.00000
以上结果仅供参考，如有疑问请指出，谢谢支持！

第二次回答：
  关于我之前对问题的理解，可能出现了偏差，抱歉！我再仔细阅读了问题，求最短路程？？距离矩阵中是把配送公司标号为1，客户依次标号为2-9吗？这样求最短路程？直接相加？？很抱歉啊，没理解题意。

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)