数学建模社区-数学中国

标题: 已知犯人8名，要将其中有关联者隔离，怎么做？ [打印本页]

---

作者: 重光兰衣    时间: 2015-11-2 15:23
标题: 已知犯人8名，要将其中有关联者隔离，怎么做？
某案件中捕获了8名犯人，代号分别为A-H，为了防止他们互相串供，必须将其中有关联的人互相隔离，问至少需要几个关押室？
请给出计算方法与程序。

已知犯人之间的牵连情况如下表所示：
犯人——有牵连的犯人
A————B C E G
B————A C H
C————A B D
D————C E H
E————A D F H
F————E G
G————A F H
H————B D E G

新手求解，这个是一定要用图论做吗……

---

作者: ゞ_轻描丶幸福的    时间: 2015-11-2 17:20
可以使用关系矩阵圈0，步骤如下：
step1：写出关系矩阵，有关系为1，无关系为1，自己和自己设定为0
step2：数出每行0的个数
step3：从0最多的行开始（如有相同的则选择这行中0所对应的列中0个数最多的），选择这一行中除行首元素外所对应的0所在列中0个数最多的列（如果相同则可任意选择）与该行逻辑加（1+1=1，1+0=1，0+0=0），该列上所有的0变为1，并将选择出来的行列做标记。标记过的可以不再做运算，因为标记过后对其后的运算没有影响
step4：然后以同样的方法再在该行中选择下一个做加法的列（每次相加时行都用最初未做任何加法时的行）。直到该行中没有没有标记过的0.同时将该行所对应的行首元素所在的列全部的0变为1.
step5：重复234步，直到没有没做标记的0为止
step6：该行首元素与该行做标记的0所对应的元素为最后的结果

以给出的数据为例
1、写出关系矩阵并标出0的个数
A B C D E F G H 0的个数
A 0 1 1 0 1 0 1 0 4
B 1 0 1 0 0 0 0 1 5
C 1 1 0 1 0 0 0 0 5
D 0 0 1 0 1 0 0 1 5
E 1 0 0 1 0 1 0 1 4
F 0 0 0 0 1 0 1 0 6
G 1 0 0 0 0 1 0 1 5
H 0 1 0 1 1 0 1 0 4
最多的为F，F行中所对应的有0的列为ABCDH，其中BCD列都为5个0
在这三个中任意选择一个，在此选择B，标记F行B列的0.
F行与B列相加
[00001010]
+[10100001]
=[10101011]
将B列除标记的0外所有的0变为1，得到新的矩阵
A B C D E F G H 0的个数
A 0 1 1 0 1 0 1 0 4
B 1 1 1 0 0 0 0 1 4
C 1 1 0 1 0 0 0 0 5
D 0 1 1 0 1 0 0 1 4
E 1 1 0 1 0 1 0 1 3
F 1 0 1 0 1 0 1 1
G 1 1 0 0 0 1 0 1 4
H 0 1 0 1 1 0 1 0 4
F行剩下D列，，标记F行D列的0。同样用F行与D列相加
[10101011]
+[00101001]
=[10101011]
将D列除标记的0外所有的0变为1，得到新的矩阵
A B C D E F G H 0的个数
A 0 1 1 1 1 0 1 0 3
B 1 1 1 1 0 0 0 1 3
C 1 1 0 1 0 0 0 0 5
D 0 1 1 1 1 0 0 1 3
E 1 1 0 1 0 1 0 1 3
F 1 0 1 0 1 0 1 1
G 1 1 0 1 0 1 0 1 3
H 0 1 0 1 1 0 1 0 4
该行中出F列无未标记的0
将F列全部的0变为1得到新矩阵
A B C D E F G H 0的个数
A 0 1 1 1 1 1 1 0 2
B 1 1 1 1 0 1 0 1 2
C 1 1 0 1 0 1 0 0 4
D 0 1 1 1 1 1 0 1 2
E 1 1 0 1 0 1 0 1 3
F 1 0 1 0 1 1 1 1
G 1 1 0 1 0 1 0 1 3
H 0 1 0 1 1 1 1 0 3
重新选择行
C行0最多
C行中有EGH列为0，E列为4个0，G为5个0，H为3个0，选择G列，标记C行G列的0
C行加最初的G列
[11010100]
+[10000101]
=[11010101]
将G列全部0变为1
得到新矩阵
A B C D E F G H 0的个数
A 0 1 1 1 1 1 1 0 2
B 1 1 1 1 0 1 1 1 1
C 1 1 0 1 0 1 0 1
D 0 1 1 1 1 1 1 1 1
E 1 1 0 1 0 1 1 1 2
F 1 0 1 0 1 1 1 1
G 1 1 0 1 0 1 1 1 2
H 0 1 0 1 1 1 1 0 3
选择E列做加法，标记C行E列的0
[11010101]
+[10010101]
=[11010101]
E列所有0变为1，C行除C列外没有没标记的0，将C列全部0变为1
得到新矩阵
A B C D E F G H 0的个数
A 0 1 1 1 1 1 1 0 2
B 1 1 1 1 1 1 1 1 0
C 1 1 1 1 0 1 0 1
D 0 1 1 1 1 1 1 1 1
E 1 1 1 1 1 1 1 1 0
F 1 0 1 0 1 1 1 1
G 1 1 1 1 1 1 1 1 0
H 0 1 1 1 1 1 1 0 2
A行与H行0最多，A行中对应有H列为0且对应H列0的个数为2。H行对应有A列为0且A列0的个数为3。所以选择A行。
A行与H列相加，标记A行H列的0
[01101110]
+[01011010]
=[01111110]
将H列所有0变为1，A行中除A列为0外均为1，所以将A列所有0变为1
得到新矩阵
A B C D E F G H 0的个数
A 1 1 1 1 1 1 1 0
B 1 1 1 1 1 1 1 1 0
C 1 1 1 1 0 1 0 1
D 1 1 1 1 1 1 1 1 0
E 1 1 1 1 1 1 1 1 0
F 1 0 1 0 1 1 1 1
G 1 1 1 1 1 1 1 1 0
H 1 1 1 1 1 1 1 1 0
矩阵中没有没标记过的0
计算结束。
得出结果为最少为3个
分配方案为
A-H
C-E-G
F-B-D．

这种方法使用纯数学计算的方法得到最后的结果。每次选择都是以0最多为准，减少了过多消除无关联量的情况。
另外，不需要太多的逻辑分析，完全依赖矩阵简单的特殊计算，比较容易在计算机上编程实现。

---

作者: liwenhui    时间: 2017-6-2 20:59
标题: 整数规划


楼上的回答很好，能解决问题，但只是一种算法逻辑，没能很好地体现数学建模的方法特点。这类问题除图论方法之外，还有多种方法可以求解，我能想到的至少有：1、整数规划 2、动态规划；两种。这里先使用整数规划来解决，使用LINGO编写了一个模型如附件所示，求解的结果为：

1.   Global optimal solution found.
   
2.   Objective value:                              3.000000
   
3.   Objective bound:                              3.000000
   
4.   Infeasibilities:                              0.000000
   
5.   Extended solver steps:                               1
   
6.   Total solver iterations:                           135
   
7. 
   
8. 
   
9.                        Variable           Value        Reduced Cost
   
10.                          Y( R1)        1.000000            0.000000
    
11.                          Y( R2)        0.000000            0.000000
    
12.                          Y( R3)        0.000000            0.000000
    
13.                          Y( R4)        0.000000            0.000000
    
14.                          Y( R5)        1.000000            0.000000
    
15.                          Y( R6)        1.000000            0.000000
    
16.                          Y( R7)        0.000000            0.000000
    
17.                          Y( R8)        0.000000            0.000000
    
18.                        Z( A, A)        1.000000            0.000000
    
19.                        Z( A, B)        1.000000            0.000000
    
20.                        Z( A, C)        1.000000            0.000000
    
21.                        Z( A, D)        0.000000            0.000000
    
22.                        Z( A, E)        1.000000            0.000000
    
23.                        Z( A, F)        0.000000            0.000000
    
24.                        Z( A, G)        1.000000            0.000000
    
25.                        Z( A, H)        0.000000            0.000000
    
26.                        Z( B, A)        1.000000            0.000000
    
27.                        Z( B, B)        1.000000            0.000000
    
28.                        Z( B, C)        1.000000            0.000000
    
29.                        Z( B, D)        0.000000            0.000000
    
30.                        Z( B, E)        0.000000            0.000000
    
31.                        Z( B, F)        0.000000            0.000000
    
32.                        Z( B, G)        0.000000            0.000000
    
33.                        Z( B, H)        1.000000            0.000000
    
34.                        Z( C, A)        1.000000            0.000000
    
35.                        Z( C, B)        1.000000            0.000000
    
36.                        Z( C, C)        1.000000            0.000000
    
37.                        Z( C, D)        1.000000            0.000000
    
38.                        Z( C, E)        0.000000            0.000000
    
39.                        Z( C, F)        0.000000            0.000000
    
40.                        Z( C, G)        0.000000            0.000000
    
41.                        Z( C, H)        0.000000            0.000000
    
42.                        Z( D, A)        0.000000            0.000000
    
43.                        Z( D, B)        0.000000            0.000000
    
44.                        Z( D, C)        1.000000            0.000000
    
45.                        Z( D, D)        1.000000            0.000000
    
46.                        Z( D, E)        1.000000            0.000000
    
47.                        Z( D, F)        0.000000            0.000000
    
48.                        Z( D, G)        0.000000            0.000000
    
49.                        Z( D, H)        1.000000            0.000000
    
50.                        Z( E, A)        1.000000            0.000000
    
51.                        Z( E, B)        0.000000            0.000000
    
52.                        Z( E, C)        0.000000            0.000000
    
53.                        Z( E, D)        1.000000            0.000000
    
54.                        Z( E, E)        0.000000            0.000000
    
55.                        Z( E, F)        1.000000            0.000000
    
56.                        Z( E, G)        0.000000            0.000000
    
57.                        Z( E, H)        1.000000            0.000000
    
58.                        Z( F, A)        0.000000            0.000000
    
59.                        Z( F, B)        0.000000            0.000000
    
60.                        Z( F, C)        0.000000            0.000000
    
61.                        Z( F, D)        0.000000            0.000000
    
62.                        Z( F, E)        1.000000            0.000000
    
63.                        Z( F, F)        1.000000            0.000000
    
64.                        Z( F, G)        1.000000            0.000000
    
65.                        Z( F, H)        0.000000            0.000000
    
66.                        Z( G, A)        1.000000            0.000000
    
67.                        Z( G, B)        0.000000            0.000000
    
68.                        Z( G, C)        0.000000            0.000000
    
69.                        Z( G, D)        0.000000            0.000000
    
70.                        Z( G, E)        0.000000            0.000000
    
71.                        Z( G, F)        1.000000            0.000000
    
72.                        Z( G, G)        1.000000            0.000000
    
73.                        Z( G, H)        1.000000            0.000000
    
74.                        Z( H, A)        0.000000            0.000000
    
75.                        Z( H, B)        1.000000            0.000000
    
76.                        Z( H, C)        0.000000            0.000000
    
77.                        Z( H, D)        1.000000            0.000000
    
78.                        Z( H, E)        1.000000            0.000000
    
79.                        Z( H, F)        0.000000            0.000000
    
80.                        Z( H, G)        1.000000            0.000000
    
81.                        Z( H, H)        1.000000            0.000000
    
82.                       X( R1, A)        0.000000            0.000000
    
83.                       X( R1, B)        0.000000            0.000000
    
84.                       X( R1, C)        1.000000            0.000000
    
85.                       X( R1, D)        0.000000            0.000000
    
86.                       X( R1, E)        1.000000            0.000000
    
87.                       X( R1, F)        0.000000            0.000000
    
88.                       X( R1, G)        1.000000            0.000000
    
89.                       X( R1, H)        0.000000            0.000000
    
90.                       X( R2, A)        0.000000            0.000000
    
91.                       X( R2, B)        0.000000            0.000000
    
92.                       X( R2, C)        0.000000            0.000000
    
93.                       X( R2, D)        0.000000            0.000000
    
94.                       X( R2, E)        0.000000            0.000000
    
95.                       X( R2, F)        0.000000            0.000000
    
96.                       X( R2, G)        0.000000            0.000000
    
97.                       X( R2, H)        0.000000            0.000000
    
98.                       X( R3, A)        0.000000            0.000000
    
99.                       X( R3, B)        0.000000            0.000000
    
100.                       X( R3, C)        0.000000            0.000000
     
101.                       X( R3, D)        0.000000            0.000000
     
102.                       X( R3, E)        0.000000            0.000000
     
103.                       X( R3, F)        0.000000            0.000000
     
104.                       X( R3, G)        0.000000            0.000000
     
105.                       X( R3, H)        0.000000            0.000000
     
106.                       X( R4, A)        0.000000            0.000000
     
107.                       X( R4, B)        0.000000            0.000000
     
108.                       X( R4, C)        0.000000            0.000000
     
109.                       X( R4, D)        0.000000            0.000000
     
110.                       X( R4, E)        0.000000            0.000000
     
111.                       X( R4, F)        0.000000            0.000000
     
112.                       X( R4, G)        0.000000            0.000000
     
113.                       X( R4, H)        0.000000            0.000000
     
114.                       X( R5, A)        0.000000            0.000000
     
115.                       X( R5, B)        1.000000            0.000000
     
116.                       X( R5, C)        0.000000            0.000000
     
117.                       X( R5, D)        1.000000            0.000000
     
118.                       X( R5, E)        0.000000            0.000000
     
119.                       X( R5, F)        0.000000            0.000000
     
120.                       X( R5, G)        0.000000            0.000000
     
121.                       X( R5, H)        0.000000            0.000000
     
122.                       X( R6, A)        1.000000            0.000000
     
123.                       X( R6, B)        0.000000            0.000000
     
124.                       X( R6, C)        0.000000            0.000000
     
125.                       X( R6, D)        0.000000            0.000000
     
126.                       X( R6, E)        0.000000            0.000000
     
127.                       X( R6, F)        1.000000            0.000000
     
128.                       X( R6, G)        0.000000            0.000000
     
129.                       X( R6, H)        1.000000            0.000000
     
130.                       X( R7, A)        0.000000            0.000000
     
131.                       X( R7, B)        0.000000            0.000000
     
132.                       X( R7, C)        0.000000            0.000000
     
133.                       X( R7, D)        0.000000            0.000000
     
134.                       X( R7, E)        0.000000            0.000000
     
135.                       X( R7, F)        0.000000            0.000000
     
136.                       X( R7, G)        0.000000            0.000000
     
137.                       X( R7, H)        0.000000            0.000000
     
138.                       X( R8, A)        0.000000            0.000000
     
139.                       X( R8, B)        0.000000            0.000000
     
140.                       X( R8, C)        0.000000            0.000000
     
141.                       X( R8, D)        0.000000            0.000000
     
142.                       X( R8, E)        0.000000            0.000000
     
143.                       X( R8, F)        0.000000            0.000000
     
144.                       X( R8, G)        0.000000            0.000000
     
145.                       X( R8, H)        0.000000            0.000000
     

复制代码

可以看到，最少需要3个房间，安排方案是：
C E G
B D
A F H

PRISONER.lg4

2017-6-2 20:57 上传

点击文件名下载附件

下载积分: 体力 -2 点

8.5 KB, 阅读权限: 60, 下载次数: 0, 下载积分: 体力 -2 点

售价: 50 点体力  [记录]  [购买]

囚房安排

---

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

Powered by Discuz! X2.5