年龄趣味问题求解！

shamohu

原题目是H20版的一道优化讨论题（http://forum.simwe.com/thread-885107-1-1.html），觉得是道不错的组合优化题。这边人气旺，看大家有无更好更方便的方法。

1：四人年龄两两相加，分别为45，56，60，71，82，（有两人没有相加），请问年龄各是多少？
2：五人年龄两两相加，分别为45，47，57，60，65，70，72，78，80，（有两人没有相加），请问年龄各是多少？

zhoulon

1）这个难道不是先设几个未知数x、y、z、t代表各自的年龄，然后列出五个线性方程组成的方程组，然后解出这个方程就可以了，呵呵。
2）第二题也是一样吧。
当然这里面有一个隐含条件就是年龄必须是整数，对于其它解去掉即可，不知道对不对，呵呵。

feynmand

1）这个难道不是先设几个未知数x、y、z、t代表各自的年龄，然后列出五个线性方程组成的方程组，然后解出这个方程就可以了，呵呵。
2）第二题也是一样吧。
当然这里面有一个隐含条件就是年龄必须是整数，对于其它解 ...
zhoulon 发表于 2009-6-26 10:26

这么做应该不对吧,比如说方程怎么列?
x+y=45;
x+z=?

---------------
因为我们不知道这些和到底是哪两个数相加得到的。

zhoulon

3# feynmand
呵呵，没有看到后面有两人没有相加，如果两两相加应该是六个方程，
现在已知条件只能列出5个方程。

feynmand

即使是再多一个数据，每两个都相加，在列方程的时候依然不容易确定这6个数分别对应于哪两个人的年龄相加。需要假设x、y、z、t已经按照升序或者降序排列，然后作出推测，但是这个可能性有几种，分别进行计算，然后有整数解的那一组才对。

少了一个两两相加的数据那么这个问题就更加难以求解了。

shamohu

非整数解也是存在的，比如年龄余数为半岁（0.5）。

shunfly

将所有数两两相减，得某两人年龄差，分析未相加两人情况，虽非规划约束求解思路，有点可行的笨办法，也可将该年龄差作原文求解的约束

shamohu

将所有数两两相减，得某两人年龄差，分析未相加两人情况，虽非规划约束求解思路，有点可行的笨办法，也可将该年龄差作原文求解的约束
shunfly 发表于 2009-6-26 22:17

感觉还是比较模糊，有无稍微具体一点的方法？实施结果如何？

fighter-11

5# feynmand
不愧为斑竹，你还是说到点子上了。问题就难在怎么确定方程组。其实第一个小题的最后两人年龄和倒是很好获得，为34。
感觉楼主有点踢馆子的意思，看来大家得加坝劲，让人笑咱坛中无人啊。

ljelly

非整数解也是存在的，比如年龄余数为半岁（0.5）。
shamohu 发表于 2009-6-26 16:29

如果可以这样
1的答案可以是：
9.5   24.5   35.5  46.5

myswine

我也觉得是没有直接列方程这么简单，两两相加是不知道哪两个和哪两个相加呀！！！

zjliu

对于第一个问题我使用遍历的思路写了个程序求解，限制条件是年龄为整数。
结果得到的年龄是为：P1=17岁，P2=28岁，P3=39岁，P4=43岁。
我的程序如下(希望各位能想出更好的算法)：
S=[45;56;60;71;82]; % 两两相加结果
A=[1,1,0,0;...
   0,0,1,1;...
   1,0,0,1;...
   0,1,1,0;...
   0,1,0,1;...
   1,0,1,0]; % 系数矩阵
T=A(1:5,1:end); % 取前5行作为系数矩阵
V=perms(1:5); % 全部排列可能
Xs=[]; % 初始解的结合
for n=1:size(V,1);
    X=pinv(T)*S(V(n,1:end)); % 通过伪逆矩阵计算解
    if max(abs(X-round(X)))<0.01; % 确认解为整数
        D=T*X-S(V(n,1:end)); % 检验结果
        if max(abs(D))<0.01; % 是否满足已知条件
            Xs=[Xs,X]; % 录入解的集合
        end
    end
end
Xs=round(sort(Xs,1)); % 按大小顺序排列，并取整(去除浮点小数值)
Xs=unique(Xs','rows') % 去掉相同的解

messenger

有简单的算法，只是太简单的，就没什么编程乐趣了。

比如，求年龄的整数解的情况。

所给条件满足下列方程：

x1+x2=45      (1)

x1+x3=56      (2)

x1+x4=60      (3)

x2+x3=71      (4)

x2+x4=82      (5)

假设是x3与x4的年龄没有相加，这里的x1、x2、x3、x4泛指各人的年龄，没有什么顺序。

从这5个方程中可以看出，如果方程(1)+(2)+(4)，结果为2*(x1+x2+x3)=45+56+71


如果方程(1)+(3)+(5)，结果为2*(x1+x2+x5)=45+60+82


由上面两个方程可以看出来，其中的三个方程加在一起，是三个年龄的2倍。所以如果想得到整数解，则其中三个方程相加，得到的结果必须为偶数。

所给的45、56、60、71、82五个数中，只有56、60、82都为偶数，所以这三个数是符合条件的一组数。

另外一组数，必须是45、71与其它一个偶数的组合。因为45、71都为奇数，如果想结果为偶数，不可能单独取一个奇数与二个偶数相加。

这样，一共就有4种组合：56、60、82；45、71、56；45、71、60；45、71、82。

假设2*(x1+x2+x3)=56+60+82=198，则

x1+x2+x3=99    (6)

x1=99-56=43

x2=99-60=39

x3=99-82=17


假设2*(x1+x2+x4)=45+71+56=172，则

x1+x2+x4=86    (7)

x1=86-45=41

x2=86-71=15

x4=86-56=30

与方程(6)结果不同，不是解，舍掉。


假设2*(x1+x2+x4)=45+71+60=176，则

x1+x2+x4=88    (7)

x1=88-45=43

x2=88-71=17

x4=88-60=28

其中两个解与方程(6)结果相同，是解。



假设2*(x1+x2+x4)=45+71+82=198，则

x1+x2+x4=99    (7)

x1=99-45=54

x2=99-71=28

x4=99-82=17

与方程(6)结果不同，不是解，舍掉。



最后得，17 28 39 43



其实，分析起来麻烦，算起来就简单了。





[a1,a2,a3]=solve('x1+x2-56','x1+x3-60','x2+x3-82')

[b1,b2,b3]=solve('x1+x2-45','x1+x4-71','x2+x4-56')

[c1,c2,c3]=solve('x1+x2-45','x1+x4-71','x2+x4-60')

[d1,d2,d3]=solve('x1+x2-45','x1+x4-71','x2+x4-82')



五人的以及年龄为半数的也可以类似

zhoulon

12# zjliu
这个解给的不错，我记得以前我在求解一个问题的特征值的时候就是系数矩阵方程多一个，然后舍掉了一个进而求解出来的，现在看看你的求解好像有点想起来了，呵呵。

shamohu

多谢各位的参与！messenger的推理求解方法很不错！下面给出另一种优化求解方法，供大家参考！

以五人情况为例：五人年龄两两相加，分别为45，47，57，60，65，70，72，78，80，（有两人没有相加），请问年龄各是多少？

设x1,x2,x3,x4,x5为五人年龄，L为一维数组, 即L=[45，47，57，60，65，70，72，78，80]，p1,p2,...p9为整数，范围=[1,9]，则问题转化为方程组求解（x4和x5没有相加）：
x1+x2=L[p1];
x1+x2=L[p2];
。。。
x3+x4=L[p9];

上述方程组除x1,x2,x3,x4,x5为未知数外，还有p1,p2,...p9也为待求数，即9个方程14个参数。将方程组求解转化成函数优化问题：

Min. (x1+x2-L[p1])^2+(x1+x3-L[p2])^2+...(x3+x4-L[p9])^2;
约束条件为p1,p2,..p9的值不能相同，只能且必须出现一次。

1stOpt求解代码：
Algorithm = SM3[100];
Constant L = [45，47，57，60，65，70，72，78，80];
Parameter x(5)=[0,80], p(9)=[1,9,0];
StartProgram [Pascal];
Procedure MainModel;
var temb : double;
    m, j, k, k1: integer;
Begin
    temb := 0;
    k := 0;
    for m := 1 to 3 do begin        //求目标函数
        for j := m to 4 do begin
            inc(k);
            temb := temb + sqr(x[m]+x[j+1]-L[p[k]]);
        end;
    end;
    k := 0;
    for m := 1 to 8 do begin     //约束条件：如有重复，记录重复次数k
        k1 := round(p[m]);
        for j := m to 8 do
            if k1 = round(p[j+1]) then inc(k);
    end;
    ObjectiveResult :=temb+k*1000;  //目标函数 + 罚函数
End;
EndProgram;

得结果：
x1        31
x2        29
x3        16
x4        49
x5        41
p1        4
p2        2
p3        9
p4        7
p5        1
p6        8
p7        6
p8        5
p9        3

实际上这个问题可推广到任何数（小数，整数，混合整数等），如五个数两两相加为（其中一组未加）[46,47.8,57.9,61.2,65.7,71.3,73.1,79.1,80.9]，将上面代码中：

Constant L = [45，47，57，60，65，70，72，78，80];

改为
Constant L = [46,47.8,57.9,61.2,65.7,71.3,73.1,79.1,80.9];即可,得结果：

x1        16.3
x2        31.5
x3        29.7
x4        41.6
x5        49.4
p1        2
p2        1
p3        3
p4        5
p5        4
p6        7
p7        9
p8        6
p9        8


再例，如果两两相加为[58+19/30,47+13/30,80+1/6,73+7/15,45+19/30,78+11/30,71+2/3,67+1/6,60+7/15]，可得结果：

x1        30.2166666667
x2        17.2166666667
x3        28.4166666667
x4        49.95
x5        43.25
p1        2
p2        1
p3        3
p4        4
p5        5
p6        8
p7        9
p8        6
p9        7

当两两相加的数含有小数时，根据奇偶数来判断推理难道就要大一些了。

FreddyMusic

四人年龄问题

方法：13 楼的分析是基础。

Mathematica 解线性方程组 + 编程：

1. 
   
2. list=Permutations[{45,56,60,71,82}];
   
3. ans={};
   
4. Module[{a,b,c,d,k1,k2,k3,k4,k5,sol,n},
   
5. n=1;
   
6. Do[
   
7. {k1,k2,k3,k4,k5}=list[[n]];
   
8. sol=Solve[{a +b==k1,a+c==k2,a+d==k3,b+c==k4},{a,b,c,d}];
   
9. If[k5==(b+d)/.sol[[1]],ans=Append[ans,list[[n]]]];
   
10. n++,
    
11. {120}]
    
12. ]
    
13. ans
    

复制代码

Out[16]= {{60,45,56,71,82},{60,45,71,56,82},{60,56,45,82,71},{60,56,82,45,71},{60,71,45,82,56},{60,71,82,45,56},{60,82,56,71,45},{60,82,71,56,45},{82,45,56,60,71},{82,45,60,56,71},{82,56,45,71,60},{82,56,71,45,60},{82,60,45,71,56},{82,60,71,45,56},{82,71,56,60,45},{82,71,60,56,45}}

1. 
   
2. Flatten[Table[{k1,k2,k3,k4,k5}=ans[];
   
3. {a,b,c,d}/.Solve[{a +b==k1,a+c==k2,a+d==k3,b+c==k4},{a,b,c,d}],{i,Length@ans}],1]
   

复制代码

Out[23]= {{17,43,28,39},{49/2,71/2,41/2,93/2},{17,43,39,28},{71/2,49/2,41/2,93/2},{49/2,71/2,93/2,41/2},{43,17,28,39},{71/2,49/2,93/2,41/2},{43,17,39,28},{67/2,97/2,23/2,45/2},{71/2,93/2,19/2,49/2},{67/2,97/2,45/2,23/2},{93/2,71/2,19/2,49/2},{71/2,93/2,49/2,19/2},{97/2,67/2,23/2,45/2},{93/2,71/2,49/2,19/2},{97/2,67/2,45/2,23/2}}

以上是排列组合的答案。

简化一下，基本是
{17, 43, 28, 39}
{49/2, 71/2, 41/2, 93/2}
{67/2, 97/2, 45/2, 23/2}
=======================================
共3 组答案

FreddyMusic

五人年龄问题：

以上方法推广。

1. 
   
2. list=Permutations[{45,47,57,60,65,70,72,78,80}];
   
3. 
   
4. ans={};
   
5. Module[{a,b,c,d,e,k1,k2,k3,k4,k5,k6,k7,k8,k9,sol,n},
   
6. n=1;
   
7. Do[
   
8. {k1,k2,k3,k4,k5,k6,k7,k8,k9}=list[[n]];
   
9. sol=Solve[{a +b==k1,a+c==k2,a+d==k3,a+e==k4,b+c==k5},{a,b,c,d,e}];
   
10. If[(k6==(b+d)/.sol[[1]])&&(k7==(b+e)/.sol[[1]])&&(k8==(c+d)/.sol[[1]])&&(k9==(c+e)/.sol[[1]]),ans=Append[ans,list[[n]]]];
    
11. n++,
    
12. {362880}]
    
13. ]
    
14. ans
    
15. 
    
16. Flatten[Table[{k1,k2,k3,k4,k5,k6,k7,k8,k9}=ans[];
    
17. {a,b,c,d,e}/.Solve[{a +b==k1,a+c==k2,a+d==k3,a+e==k4,b+c==k5},{a,b,c,d,e}],{i,Length@ans}],1]
    
18. 
    

复制代码

所得整数答案基本相同

{{16,29,31,41,49},{16,29,31,49,41},{29,16,31,41,49},{29,16,31,49,41},{16,31,29,41,49},{16,31,29,49,41},{31,16,29,41,49},{31,16,29,49,41},{29,31,16,41,49},{29,31,16,49,41},{31,29,16,41,49},{31,29,16,49,41}}

FreddyMusic

x1        16.3
x2        31.5
x3        29.7
x4        41.6
x5        49.4


x1        30.2166666667
x2        17.2166666667
x3        28.4166666667
x4        49.95
x5        43.25

shamohu 发表于 2009-7-9 15:06

我不认为这是正确答案，因为可以演示，并且很容易反驳。

小数和分数
x1        30.2166666667
x2        17.2166666667
x3        28.4166666667

两两相加 肯定不是整数。

shamohu

以上是排列组合的答案。

简化一下，基本是
{17, 43, 28, 39}
{49/2, 71/2, 41/2, 93/2}
{67/2, 97/2, 45/2, 23/2}
FreddyMusic 发表于 2009-7-12 04:43

{93/2,71/2,49/2,19/2}应该也是一组吧？

shamohu

我不认为这是正确答案，因为可以演示，并且很容易反驳。

小数和分数
x1        30.2166666667
x2        17.2166666667
x3        28.4166666667

两两相加 肯定不是整数。
FreddyMusic 发表于 2009-7-12 05:10

看15楼的原题，原例子两两相加数据本身就不是整数，而是对于任意实数。