Question

急求一运筹学题答案！！！！要详细过程！！谢谢！

有四项工作A、B、C、D分配给甲乙丙丁四个人去做，求总效率最大解。

甲完成ABCD四项工作的效率分别是6、2、3、1；

乙的效率是7、4、3、2；

丙的是8、10、7、3；

丁的是7、7、5、4。

Answer 1

因为是极大化指派问题，故选取最大的效率值10（丙B），用该值分别减去各效率值，得：
4 8 7 9
3 6 7 8
2 0 3 7
3 3 5 6
求该问题的极小化问题就是求原问题的极大化问题。
（1）各行减去该行最小值，得
0 4 3 5
0 3 4 5
2 0 3 7
0 0 2 3
（2）各列减去该列最小值，得
0 4 1 2
0 3 2 2
2 0 1 4
0 0 0 0
（3）给第1行第1列的0画圈，同时给第2行第1列、第4行第1列的0画杠
给第3行第2列的0画圈，同时给第4行第2列的0画杠
给第4行第3列的0画圈，同时给第4行第4列的0画杠
（4）画圈0的个数（3）小于矩阵的阶（4），故不是最优解
（5）给没有画圈0的第2行打勾
给第2行的画杠0所在的第1列打勾
给第1列的画圈0所在的第1行打勾
给没打勾的行画一条直线
给打勾的列画一条直线
得到覆盖所有0的最少直线
（6）在未被直线覆盖的元素中，甲C的1最小，令打勾的第1行和第2行各元素都减去这个1，再令打勾的第1列各元素都加上这个1，得
0 3 0 1
0 2 1 1
3 0 1 4
1 0 0 0
（7）清空所有圈、杠、勾和直线，
给第2行第1列的0画圈，同时给第1行第1列的0画杠
给第1行第3列的0画圈，同时给第4行第3列的0画杠
给第3行第2列的0画圈，同时给第4行第2列的0画杠
给第4行第4列的0画圈。
（8）画圈0的个数=矩阵的阶，得最优解
将画圈的0改成1，将所有未画圈的元素改成0
（9）4个1分别在不同行不同列
即甲做C，乙做A，丙做B，丁做D，
总效率最大为：3+7+10+4=24

Answer 2

支持楼上，这学期我们刚学完这种指派问题 题型……