2. 自考
  3. 某公司决定派甲、乙、丙、丁四人去完成A、B、C、D四个项目，每个人分工不同，且每个人只能完成其中的一项工作，假如四个人完成四个项目所需的经费(单位：千元)如下表所示． (1)此类型的问题可以用什么方法解决?与此问题类似的还有哪些? (2)解决此类问题的

某公司决定派甲、乙、丙、丁四人去完成A、B、C、D四个项目，每个人分工不同，且每个人只能完成其中的一项工作，假如四个人完成四个项目所需的经费(单位：千元)如下表所示． (1)此类型的问题可以用什么方法解决?与此问题类似的还有哪些? (2)解决此类问题的

admin2017-10-27  93
问题 某公司决定派甲、乙、丙、丁四人去完成A、B、C、D四个项目，每个人分工不同，且每个人只能完成其中的一项工作，假如四个人完成四个项目所需的经费(单位：千元)如下表所示．

(1)此类型的问题可以用什么方法解决?与此问题类似的还有哪些?
(2)解决此类问题的关键步骤有哪些?
选项
答案(1)与此问题类似的还有旅行商问题，这种类型的问题都可以用匈牙利算法来解决． (2)匈牙利算法的关键步骤如下： ①将费用矩阵的每一行元素减去该行的最小元素，再将每一列的元素减去最小元素(已有0的列就不必减了)． ②找在不同行、不同列的0元素，先在各行中找只有一个0元素前，并在其右上角加“*”号，再将此0元素所在列中的0元素记为Φ，再在各列中找只有一个0的加“*”号，并在此0元素所在行中的0记为Φ，若在不同行、不同列的“0*”有n个，则将与“0*”对应的解取为1，其余元素对应的解取为0，即为原指派问题的最优解．若在不同行、不同列的“0*”不够n个，则经下一步调整． ③在有“0*”的行、列上过“0*”画横线或竖线，有n个“0*”就只能画n条横竖线，还要经过所有的“Φ”再在没有横竖线经过的非0元素中找最小的将没画横线的各行元素均减去这个最小元素，而在画竖线的各列非0元素均加上这个最小元素． ④重做第二步，即可得到最佳指派方案.
解析
转载请注明原文地址:https://www.kaotiyun.com/show/6FFR777K
本试题收录于： 管理数量方法与分析题库经管类分类
0

管理数量方法与分析

经管类

相关试题推荐
随机试题
最新回复(0)