Matlab_枚举法求解指派问题
例：有一份中文说明书，需译成英、日、德、俄四种文字，分别记作E，J，G，R，现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种的说明书所需时间如下表所示。问应指派何人去完成何工作，使所需时间最少？
|
人员 |
任 务 |
|||
|
E |
J |
G |
R |
|
|
甲 |
2 |
15 |
13 |
4 |
|
乙 |
10 |
4 |
14 |
15 |
|
丙 |
9 |
14 |
16 |
13 |
|
丁 |
7 |
8 |
11 |
9 |
指派问题是0-1规划的特例，也是运输问题的特例，可以用0-1规划或运输问题的解法求解。
本题的数学模型为：
本题采用枚举法求解，遍历全部可行解，比较目标函数的值，找出最优解。
程序代码：
m文件：
c=[2 15 13 4;10 4 14 15;9 14 16 13;7 8 11 9];
min=1000;
for i=1:4
for j=1:4
for m=1:4
for n=1:4
if i == j||i == n||i == m||j == m||j==n||m==n
continue;
end
Y = zeros(4,4);
Y(1, i) = 1;
Y(2, j) = 1;
Y(3, m) = 1;
Y(4, n) = 1;
z=c.*Y;
if sum(sum(z))<min
X=Y;
min=sum(sum(z));
end
end
end
end
end
X
min
运行结果：
>> yunchou523（相应的m文件名）
X =
0 0 0 1
0 1 0 0
1 0 0 0
0 0 1 0
min =
28
此题采用枚举法，通过四层循环遍历全部可行解，比较目标函数的值，找出最优解。虽然思路简单，但在数据量较大时，多层循坏提高了时间复杂度，效率较低。