《指派问题研究报告》由会员分享，可在线阅读，更多相关《指派问题研究报告（17页珍藏版）》请在金锄头文库上搜索。
1、,指派问题 assignment problem,指派问题 assignment problem,【例1】人事部门欲安排四人到四个不同的岗位工作，每个岗位一个人经考核四人在不同岗位的成绩（百分制）如下表所示，如何安排他们的工作使总成绩最好。,【解】设,数学模型,数学模型为：,甲,乙,丙,丁,A,B,C,D,图5. 3,指派问题 assignment problem,假设m个人恰好做m项工作，第i个人做第j项工作的效率为cij0，效率矩阵为cij ，如何分配工作使效率最佳（min或max）的数学模型为,指派问题 assignment problem,【定理2】若矩阵A的元素可分成“0”与非“0”
2、两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素（称为独立元素）的最大个数,如果最少直线数等于m，则存在m个独立的“0”元素，令这些零元素对应的xij等于1，其余变量等于0，这时目标函数值等于零，得到最优解,两个目标函数相差一个常数 u+v,约束条件不变,因此最优解不变。,指派问题 assignment problem,【例2】某汽车公司拟将四种新产品配置到四个工厂生产，四个工厂的单位产品成本（元/件）如下表所示求最优生产配置方案,指派问题 assignment problem,第二步：找出矩阵每列的最小元素，再分别从每列中减去，有,指派问题 assignment prob
3、lem,【解】问题求最小值。 第一步：找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有,第三步：用最少的直线覆盖所有“0”，得,第四步：这里直线数等于3（等于4时停止运算），要进行下一轮计算 从矩阵未被直线覆盖的数字中找出一个最小数k并且减去k，矩阵中k5 直线相交处的元素加上k，被直线覆盖而没有相交的元素不变，得到下列矩阵,指派问题 assignment problem,第四步等价于第2、3行减去5，同时第1列加上5得到的结果,第五步：覆盖所有零最少需要4条直线，表明矩阵中存在4个不同行不同列的零元素容易看出4个“0”的位置,( ),( ),( ),( ),或,( ),( ),(
4、),( ),指派问题 assignment problem,得到两个最优解,有两个最优方案 第一种方案：第一个工厂加工产品1，第二工厂加工产品3，第三个工厂加工产品4，第四个工厂加工产品2； 第二种方案：第一个工厂加工产品1，第二工厂加工产品4，第三个工厂加工产品3，第四个工厂加工产品2； 单件产品总成本 Z5815025055513,指派问题 assignment problem,其它变异问题,指派问题 assignment problem,1 ) 最大化指派问题 对于最大化指派问题，假定系数矩阵为，令，再令，这样就把系数矩阵C的原最大化指派问题化成系数矩阵为B的最小化指派问题。两者具有相同
5、的最优解。 2）人数与事数不等的指派问题 对于人数与事数不等的指派问题，通过如下方法，将其化为标准的指派问题： （1）如果人少事多，增加一些虚拟“人”，虚拟“人”做事的费用系数取为0; （2）如果人多事少，增加一些虚拟“事”，虚拟“事”做事的费用系数也取为0； 3）一个人可做几件事的指派问题 可将某个人化作同样几个“人”接受指派，这几个“人”做同一件事的费用系数一样。 4）某事一定不能由某人做的指派问题 可将相应的费用系数取为足够大的数M。,【例3】 求例1的最优分配方案,指派问题 assignment problem,人事部门欲安排四人到四个不同的岗位工作，每个岗位一个人经考核四人在不同岗位
6、的成绩（百分制）如下表所示，如何安排他们的工作使总成绩最好。,【例4】某商业集团计划在市内四个点投资四个专业超市，考虑的商品有电器、服装、食品、家俱及计算机等5个类别通过评估，家具超市不能放在第3个点，计算机超市不能放在第4个点，不同类别的商品投资到各点的年利润（万元）预测值见下表该商业集团如何作出投资决策使年利润最大。,指派问题 assignment problem,【解】 这是求最大值、人数与任务数不相等、不可接受的配置的一个综合指派问题，分别对表进行转换 （1）令c43=c54=0 （2）转换成求最小值问题，令M420，得到效率表（机会损失表） （3）虚拟一个地点5,指派问题 assignment problem,Z=1350,转换后得到下表用匈牙利法求解得到最优解,最优投资方案：地点1投资建设计算机超市，地点2投资建设服装超市，地点3投资建设食品超市，地点4投资建设电器超市，年利润总额预测值为1350万元,指派问题 assignment problem,1指派模型的特征 2匈牙利法求解指派问题的条件 3匈牙利法的两个基本定理 4指派问题也是一个特殊的运输问题. 5将指派（分配）问题的效率矩阵每行分别加上一个数后最优解不变.,指派问题 assignment problem,
