2. 计算机
  3. 某公司要把4个有关能源工程项目承包给4个互不相关的外商投标者，规定每个承包商只能且必须承包一个项目，在总费用最小的条件下确定各个项目的承包者，总费用为( ) (各承包商对工程的报价如表所示)。

某公司要把4个有关能源工程项目承包给4个互不相关的外商投标者，规定每个承包商只能且必须承包一个项目，在总费用最小的条件下确定各个项目的承包者，总费用为( ) (各承包商对工程的报价如表所示)。

admin2016-05-11  63
问题 某公司要把4个有关能源工程项目承包给4个互不相关的外商投标者，规定每个承包商只能且必须承包一个项目，在总费用最小的条件下确定各个项目的承包者，总费用为(   ) (各承包商对工程的报价如表所示)。
选项 A、70
B、69
C、71
D、68
答案A
解析 本题为运筹学中标准的指派问题．
    下面用匈牙利法求解：
    (1)行变换，找出每一行(每一列)的最小值，然后让每一行(每一列)都减去这个数。
    (2)试指派，找独立的零元素。独立零元素个数为m，矩阵的阶数为n，当m=n时，问题得解。
    第1步：构建矩阵：

第2步：找出各行中的最小值，各行分别减去本行的最小值。

    第3步：用“*”标记出各行独立是“0”的，非独立是“0”的标记为“#”，因为此题的“*”的数量为3，效用矩阵为N=4，所以需要继续求解。

第4步：对没有“*”的行做标记“￥”；对已经做了标记的行中所有含“#”的列做标记“￥”；重复第3步和第4步，直到得不出新的的打“￥”标记的行、列为止。对没有标记“￥”的标上用红色粗体，有标记“￥”的列用“红色粗体”，这就覆盖到了“0”元素的最少直线数L。

    第5步：因为直线的数目L=3，小于4，还需要继续变换矩阵；找出剩下数字中的最小值，在这里为“1”；
    对这个矩阵进行变换以增加0元素。为此在没有被直线覆盖的部分中找出最小元素。然后在标记“￥”行各个元素中减去这个最小元素，而在标记“￥”的各元素都加上这个最小元素，即标记“￥”的列数值不变。若得到N个独立的0元素，则已经得到最优解。否则回到第4步重复进行。
    因为此次变换仍然没有4个独立的“0”，所以重复上步骤。

    最后得到标记“#”的数字，求和就是最优解。15+18+16+21=70。
转载请注明原文地址:https://kaotiyun.com/show/oaGZ777K
本试题收录于： 信息系统项目管理师上午综合知识考试题库软考高级分类
0

信息系统项目管理师上午综合知识考试

软考高级

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