试题详情
简答题 某公司决定派甲、乙、丙、丁四人去完成A、B、C、D四个项目，每个人分工不同，且每个人只能完成其中的一项工作，假如四个人完成四个项目所需的经费（单位：千元）如下表所示。 （1）此类型的问题可以用什么方法解决？ （2）决此类问题的关键步骤有哪些？
  • （1）用匈牙利算法来解决。
    （2）步骤： 
    ①将费用矩阵的每一行元素减去该行的最小元素，再将每一列的元素减去最小元素（已有0的列就不必减）。②找在不同行、不同列的0元素，先在各行中找只有一个0元素的，并在其右上角加“*”号，再将次0元素记为Ф，再在各列中找只有一个0的加“*”号，并在此0元素所在行中的0记为Ф，若在不同行、不同列的“0”有n个，则将与“0”对应的解取为1，其余元素对应的解取为0，即为原指派问题的最优解，若在不同行、不同列的“0”不够n个，则经下一步调整。 
    ③在有“0”的行、列上过“0”画横线或竖线，有n个“0”就只能画n条横竖线，还要经过所有的Ф。再在没有横竖线经过的非0元素中找最小的将没画横线的各行元素均减去这个最小元素，而在画竖线的各列非0元素均加上这个最小元素。 
    重做第二步，即可得到最佳指派方案。

  • 关注下方微信公众号，在线模考后查看

热门试题