搜索
可以自己添加指派问题实例分析在现实生活中,有各种性质的指派问题.例如,有若干项工作需要分配给若干人(或部门~设备)去完成;有若干项合同需要若干个投标者来承包;有若干班级需要安排在不同的教师上课等等.诸如此类问题,他们的基本要求实在满足特定的指派要求的同时,是指派方案的中体效果最佳.由于指派问题的多样性我们划分成标准的指派问题和一般的指派问题两大类.一般的指派问题需经过处理使其标准化,在用匈牙利解法求出最优方案.例如:西南交通大学希望学院土木工程系将在全校举行首届测量大赛,个班自己组队一组四人分别为甲~乙~丙~丁四人.在测量工作当中有调整仪器,观测读数,记录数据,数据处理四项任务.但是个人处理问题的能力以时间作为划分标准(如下表所示).但是记录数据不需要多大能力,于是记录数据的人就是在其他三项选完后剩下的工作.(完成各项工作没有错误存在)人员时间(秒)任务调整仪器观测读数数据处理甲120200300乙180300270丙175450180丁160250360分析:由于规定每项任务只能有一个人来完成,即一人一事.此问题为非标准的指派问题我们需要对其进行标准化,再用匈牙利法对其求最优指派方案指派问题的系数矩阵如下:120200300180300270175450180160250360将其化成标准的指派问题矩阵:1202003000-01803002700-01754501800-01602503600-0-120-200-180-0用匈牙利法求解最优方案,矩阵的每行每列均减去他的最小数,使其每行每列至少有个0存在.得到如下矩阵○0012006010090○0√55250○0040501800√√找出一行或则一列只有一个0的所有行或列,并划上.如上图.在没有的行打√,在打√的行找划去的0列打√,在打√的列找划的行打√.一直划到不能再继续为止.再将剩下的元素减去他们中间最小的元素(此例是40)为了保证个元素不为负数因此在划去0的列加上此数字得到如下矩阵:0○012040208050○055250○040○0101400此时每行每一列都只有一个0这次是为此问题的最优方案,将划○0的位置用1代替,其余位置用0表示,0,1分别表示承担和不承担.即:0100000100101000为此问题的最优解,即甲观测读数,丙数据处理,丁调整仪器,剩下一项数据记录由乙来完成.