谁有做这道题的思路？

starbinbin_csu

其中村⑧距离主干河流最近，且海拔高度最低。乡政府打算拟定一个修建在各村之间互通的新泄洪河道网络计划，将洪水先通过新泄洪河道引入村⑧后，再经村⑧引出到主干河流。要求完成之后，每个村通过新泄洪河道能够达到可泄洪量100万立方米/小时的泄洪能力。





请根据表3中的数据，为该乡提供一个各村之间修建新泄洪河道网络的合理方案，使得总费用尽量节省。（说明：从村A→村B的新泄洪河道，一般要求能够承载村A及上游新泄洪河道的泄洪量。）
其中修建新泄洪河道的费用为，其中Q表示泄洪河道的可泄洪量（万立方米/小时），L表示泄洪河道的长度（公里）


貌似可以改进图论算法，或者可以用Hopfield神经网络，可是不知道该怎么用？有没有谁能够提供一个具体思路。

lin2009

这是最优化问题，先把模型建出来，再试试用1stopt来解。
问题较复杂，可能需要用到1stopt的编程模式，可以转到H20：mathcad/1stopt板块。
http://forum.simwe.com/forum-63-1.html

bainhome

此问题属于图论和网络模型中的最小费用最大流和最优连线的综合问题，源数据曾在不知道那本书中见过，印象中是天然气管道铺设的连线问题。和此泄洪问题方向相反。
赞同楼上，如果没有数学建模之类的成型工具箱，用MATLAB求解此类问题费力不讨好，建议用1stopt或者lingo求解。

starbinbin_csu

4# bainhome
写了一个这样的算法：
1。取海拔最低的点，海拔第二低的点与其连线，组成初始的生成树
2。再选海拔第三低的点，比较其与1和2相连那种方式费用最少。
3。依次下去，有点像动态规划，用matlab变成解出结果输出如下：

经过搜索,得出最优的路径如下：
8<-5
8<-10
8<-7
5<-4
5<-3
5<-6
4<-1
7<-9
7<-2
经计算得，最优花费为:
  583.6321


但是不知道合不合理，麻烦给点意见？
另外我看过用hopfeild神经网络解TSP问题的例子，不知道这里可不可以引入？

starbinbin_csu

3# lin2009
写了一个这样的算法：
1。取海拔最低的点，海拔第二低的点与其连线，组成初始的生成树
2。再选海拔第三低的点，比较其与1和2相连那种方式费用最少。
3。依次下去，有点像动态规划，用matlab变成解出结果输出如下：

经过搜索,得出最优的路径如下：
8<-5
8<-10
8<-7
5<-4
5<-3
5<-6
4<-1
7<-9
7<-2
经计算得，最优花费为:
  583.6321


但是不知道合不合理，麻烦给点意见？
另外我看过用hopfeild神经网络解TSP问题的例子，不知道这里可不可以引入？

qibbxxt

具我所知，神经网络在解决TSP问题方面没有优势，还是演化算法比较好用

starbinbin_csu

7# qibbxxt
那么能不能够给一个演化算法做这个的思路呢？

feynmand

像是一个数学建模的练习题。
这种优化问题，我认为首先要分析题目所包含的各种约束条件，然后建立一个只包含最少约束的模型，在此基础上逐步增加其他约束，在这个过程中需要注意的是要尽可能的修改模型，将模型中不符合约束条件的解剔除，不要最终弄一个看起来很漂亮的模型但是约束条件十几个，放入程序求最优值是很难成功的。通过建立与修改，将最终包括少数几个约束条件的模型编程求解。

具体做此类问题的时候，首先要仔细分析题目中各种因素之间的各种关系，不能指望列一个式子把这些关系做成一个黑箱然后让程序去解决。针对这个问题来说，泄洪渠的造价公式可以看出，如果两个村AB到第三个村C距离相等，而AB之间距离比较近，那么可以在AB间造个水渠然后一起流到C。比如图中的26和8。因为Q可泄洪量带一个开方的指数，2倍的Q只有1。4的造价。还有就是这是修水渠，和海拔高度非常相关，所以需要建立一个“禁忌表”，流出只能流向低海拔的村庄，别修好了以后发现4流到7然后再流到8的情况。因为这个限制条件的存在，可先将算法搜索的区间减小，然后就可以在计算过程中去除很多不必要的搜索。

starbinbin_csu

此题的最终做的结果和大家分享一下：
首先是自己设计了一个算法，不能求得最优解，但是能够搜索到较为接近最优解的解。matlab代码如下：

1. function resem_prim(Q,n,order)
   
2. %参数及符号说明：
   
3. %Q:邻接矩阵
   
4. %n:矩阵的大小
   
5. %order:地势的排序矩阵
   
6. %index:记录迭代进入的层数
   
7. %QQ:最小树的邻接矩阵
   
8. %cost:最小生成路径的花费
   
9. %result:生成树节点矩阵
   
10. %weight:该点的流量/100
    
11. %%%%%%%%%%%%%%%%%%%%%%%%%%主程序%%%%%%%%%%%%%%%%%%%%%%%%%%%
    
12. %% 矩阵处理，按地势排序
    
13. %此例的顺序为8,5,（4,10），7,3，（1,9）2,6
    
14. for i=1:n
    
15.     for j=1:n
    
16.         temp(i,j)=Q(order(i),order(j));
    
17.     end
    
18. end
    
19. Q=temp;
    
20. %% 搜索初始化
    
21. QQ=[inf,Q(1,2);Q(2,1),inf];
    
22. %cost=QQ(1,2)*100^0.51*0.66;
    
23. weight=zeros(1,size(order,2));
    
24. weight(1)=2;%该
    
25. weight(2)=1;
    
26. %% 逐层搜索
    
27. for i=3:n
    
28.     weight(i)=weight(i)+1;
    
29.     [QQ,cost,weight]=compare(QQ,Q,i,weight);
    
30.      
    
31. %     QQ(i,:)=inf;
    
32. %     QQ(:,i)=inf;
    
33. %     QQ(match,i)=Q(match,i);
    
34. %     QQ(i,match)=Q(match,i);
    
35. end
    
36. %cost=cost+100.^0.51*0.66*QQ(10,1);
    
37. %% 结果输出
    
38. disp('经过搜索,得出最优的路径如下：');
    
39. for i=1:n
    
40.     for j=i+1:n
    
41.         if QQ(i,j)~=inf
    
42.             disp([num2str(order(i)) '->' num2str(order(j))]);
    
43.         end
    
44.     end
    
45. end
    
46. disp('经计算得，最优花费为:');
    
47. disp(cost);
    
48. QQ
    
49. %%%%%%%%%%%%%%%%%%%%%%%%%%主程序%%%%%%%%%%%%%%%%%%%%%%%%%%%
    
50. %% 寻优函数
    
51. function [QQ,min_cost,weight]=compare(QQ,Q,i,weight)
    
52. min_cost=inf;
    
53. test_QQ=QQ;
    
54. test_weight=weight;
    
55. for j=1:i-1
    
56.     test_QQ(i,j)=Q(i,j);
    
57.     test_QQ(j,i)=Q(j,i);
    
58.     test_QQ=fulllize(test_QQ);
    
59.     test_weight=change(test_weight,j,test_QQ);
    
60.     if cost(test_QQ,test_weight)<min_cost
    
61.         min_cost=cost(test_QQ,weight);
    
62.         flag=j;
    
63.     end
    
64.     test_QQ=QQ;
    
65.     test_weight=weight;
    
66. end
    
67. weight=change(weight,flag,QQ);
    
68. QQ(i,flag)=Q(i,flag);
    
69. QQ(flag,i)=Q(flag,i);
    
70. QQ=fulllize(QQ);
    
71. 
    
72. %% 计算花费的函数
    
73. function cost=cost(QQ,weight)
    
74. cost=0;
    
75. for i=1:size(QQ,2)
    
76.     for j=i+1:size(QQ,2)
    
77.         if QQ(i,j)~=inf
    
78.             cost=cost+(weight(j)*100).^0.51*0.66*QQ(i,j);
    
79.         end
    
80.     end
    
81. end
    
82. %% 处理矩阵的函数
    
83. function QQ=fulllize(QQ)
    
84. for i=1:size(QQ,1)
    
85.     for j=1:size(QQ,2)
    
86.         if QQ(i,j)==0
    
87.             QQ(i,j)=inf;
    
88.         end
    
89.     end
    
90. end
    
91. %% 改变矩阵
    
92. function weight=change(weight,j,QQ)
    
93. weight(j)=weight(j)+1;
    
94. for i=j-1:-1:1
    
95.     if(QQ(j,i)~=inf)
    
96.         weight=change(weight,i,QQ);
    
97.     end
    
98. end

复制代码

还尝试利用lingo11.0进行求解，能够求解得到全局最优解，不过求解速度比较慢，不适合作为一个普适的算法，lingo代码如下：

1. sets:
   
2.         site/1..10/:m;
   
3.       links(site,site):x,L;       
   
4. endsets
   
5. data:
   
6.   L=          0     8     8    14    11     9    16    17     8    14
   
7.      8     0    14     8     9    11    22    15    17    18
   
8.      8    14     0    17    12     6    10    15    15    11
   
9.     14     8    17     0     5    12    22     9    12    16
   
10.     11     9    12     5     0     7    17     7     9    12
    
11.      9    11     6    12     7     0    11    10    10     8
    
12.     16    22    10    22    17    11     0    18    15    11
    
13.     17    15    15     9     7    10    18     0     3     7
    
14.      8    17    15    12     9    10    15     3     0     6
    
15.     14    18    11    16    12     8    11     7     6     0;
    
16. enddata
    
17. 
    
18. [OBJ]min=0.66*@sum(site(i)|i#Le#9:@sum(site(j)|j#GT#i:x(i,j)^0.51*L(i,j))*m(i)^0.51);
    
19. !约束一;
    
20. m(1)=100;
    
21. @for(site(i)|i#Le#9 #and# i#ge#2:m(i)-100=@sum(site(k)|k#le#i-1:x(k,i)*m(k)));
    
22. @for(site(i)|i#le#9:@sum(site(j)|j#gt#i:x(i,j))>=1);
    
23. @for(site(i)|i#le#9:@for(site(j)|j#le#10 #and# j#gt#i:@bin(x(i,j))));
    

复制代码

前种算法搜不到精确的最优解，后种方法效率不高，要是村庄再多一点的话要算很长的时间。

不知道大家有什么意见？