数学建模社区-数学中国

标题: 13*20矩阵最小和 [打印本页]

作者: 十二分的追求 时间: 2014-9-6 10:59
标题: 13*20矩阵最小和
每行选一个，每列只能选一个（即不同行不同列，选13个数值的和最小），怎么做？最好MATLAB的解决方案。（菜鸟）
谢谢！！！

作者: 847717213 时间: 2014-9-7 00:54
我大概是这么想的，穷举的话应该需要20！/7！，量级挺大。现成的算法也没想到能套用上的。
可以尝试如下算法：
1找出每行最小值
2将每行元素都减去每行最小值，得出损失矩阵（即，若不用最小值会损失多少）
3对损失矩阵中次小元素（即除了0以外的最小元素）进行排序，得出最大的元素所在行，将最小元素定下来，作为结果集合中的元素
4然后将3中最小元素所在行和列都填成一个极大值，比如远远超过矩阵中最大值的一个值。
5对A进行1-4步骤直至A矩阵只剩一个元素
应该可以求出一个较优解，是不是最优很难说，需要证明
(matlab算法及编程咨询，画图，解方程组，最优化：http://shop108557885.taobao.com)

作者: 847717213 时间: 2014-9-7 00:55
我大概是这么想的，穷举的话应该需要20！/7！，量级挺大。现成的算法也没想到能套用上的。
可以尝试如下算法：
1找出每行最小值
2将每行元素都减去每行最小值，得出损失矩阵（即，若不用最小值会损失多少）
3对损失矩阵中次小元素（即除了0以外的最小元素）进行排序，得出最大的元素所在行，将最小元素定下来，作为结果集合中的元素
4然后将3中最小元素所在行和列都填成一个极大值，比如远远超过矩阵中最大值的一个值。
5对A进行1-4步骤直至A矩阵只剩一个元素
应该可以求出一个较优解，是不是最优很难说，需要证明
(matlab算法及编程咨询，画图，解方程组，最优化：shop108557885.taobao.com)

作者: 啊nong 时间: 2014-9-7 08:49
可以参考0——1规划问题

作者: 梦@di?~ 时间: 2014-9-8 13:33
A=[1 32 43 43 21 54 23;2 32 15 667 43 34 2;3 34 46 79 89 67 43;2 34 45 23 4 6 5]; %换成相应要求的矩阵
[n,m]=size(A);
s=0;
for i=1:n
b(i,1)=0;
b(i,2)=max(A(i,

);
for j=1:m
      while (A(i,j)<b(i,2) && b(i,2)~=j)  %满足最小且不同列
         b(i,2)=A(i,j);
         b(i,1)=j;
      end
end
s=s+b(i,2);
end
s

作者: mingtingqing 时间: 2014-10-6 15:29
可以参考下2楼的想法

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