第4章 指派问题.ppt

《第4章 指派问题.ppt》由会员分享，可在线阅读，更多相关《第4章 指派问题.ppt（18页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、运筹学运筹学Operations Research1烟台大学文经学院科研与素质教育部15553500757,gaoqian_高 谦指派问题指派问题assignment problem 2指派问题指派问题assignment problem【例例1】人事部门欲安排四人到四个不同的岗位工作，每个岗位人事部门欲安排四人到四个不同的岗位工作，每个岗位一个人经考核四人在不同岗位的成绩（百分制）如下表所示，一个人经考核四人在不同岗位的成绩（百分制）如下表所示，如何安排他们的工作使总成绩最好。如何安排他们的工作使总成绩最好。表表5-34 工作工作人员人员ABCD甲甲85927390乙乙95877895丙丙8

2、2837990 丁丁86908088【解解】设设数学模型数学模型3数学模型为：数学模型为：甲乙丙丁ABCD图图5.3指派问题指派问题assignment problem 4假设假设m个人恰好做个人恰好做m项工作，第项工作，第i个人做第个人做第j项工作的效率为项工作的效率为cij0，效率矩阵为效率矩阵为cij，如何分配工作使效率最佳（，如何分配工作使效率最佳（min或或max）的数学）的数学模型为模型为 指派问题指派问题assignment problem 5解指派问题的匈牙利算法解指派问题的匈牙利算法匈牙利法的条件是匈牙利法的条件是：问题求最小值、人数与工作数相等及效率：问题求最小值、人数与工

3、作数相等及效率非负非负【定理定理1】如果从分配问题效率矩阵如果从分配问题效率矩阵cij的每一行元素中分别减的每一行元素中分别减去（或加上）一个常数去（或加上）一个常数ui（被称为该行的位势），从每一列分（被称为该行的位势），从每一列分别减去（或加上）一个常数别减去（或加上）一个常数vj（称为该列的位势），得到一个（称为该列的位势），得到一个新的效率矩阵新的效率矩阵bij，其中，其中bij=cijuivj,则则bij的最优解等价于的最优解等价于cij的最优解，这里的最优解，这里cij、bij均非负均非负指派问题指派问题assignment problem【证证】6【定理定理2】若矩阵若矩阵A的元

4、素可分成的元素可分成“0”与非与非“0”两部分，则两部分，则覆盖覆盖“0”元素的最少直线数等于位于不同行不同列的元素的最少直线数等于位于不同行不同列的“0”元元素（称为独立元素）的最大个数素（称为独立元素）的最大个数如果最少直线数等于如果最少直线数等于m，则存在，则存在m个独立的个独立的“0”元素，令这些零元素，令这些零元素对应的元素对应的xij等于等于1，其余变量等于，其余变量等于0，这时目标函数值等于零，这时目标函数值等于零，得到最优解得到最优解两个目标函数相差一个常数两个目标函数相差一个常数 u+v,约束条件不变约束条件不变,因此最优解不变。因此最优解不变。指派问题指派问题assignm

5、ent problem 7【例例2】某汽车公司拟将四种新产品配置到四个工厂生产，四个某汽车公司拟将四种新产品配置到四个工厂生产，四个工厂的单位产品成本（元工厂的单位产品成本（元/件）如下表所示求最优生产配置方件）如下表所示求最优生产配置方案案 产品产品1产品产品2产品产品3产品产品4工厂工厂15869180260工厂工厂27550150230工厂工厂36570170250工厂工厂48255200280指派问题指派问题assignment problem 8第二步第二步：找出矩阵每列的最小元素，再分别从每列中减去，有：找出矩阵每列的最小元素，再分别从每列中减去，有 指派问题指派问题assignm

6、ent problem【解解】问题求最小值。问题求最小值。第一步：找出效率矩阵每行的最小元素，并分别从每行中减去第一步：找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有最小元素，有 9第三步第三步：用最少的直线覆盖所有：用最少的直线覆盖所有“0”，得，得第四步：第四步：这里直线数等于这里直线数等于3（等于（等于4时停时停止运算），要进行下一轮计算止运算），要进行下一轮计算从矩阵未被直线覆盖的数字中找出一个从矩阵未被直线覆盖的数字中找出一个最小数最小数k并且减去并且减去k，矩阵中，矩阵中k5直线相交处的元素加上直线相交处的元素加上k，被直线覆盖而，被直线覆盖而没有相交的元素不变，得到下

7、列矩阵没有相交的元素不变，得到下列矩阵指派问题指派问题assignment problem 第四步等价于第第四步等价于第2、3行减去行减去5，同时第，同时第1列加上列加上5得到的结果得到的结果10第五步第五步：覆盖所有零最少需要：覆盖所有零最少需要4条直线，表明矩阵中存在条直线，表明矩阵中存在4个个不同行不同列的零元素容易看出不同行不同列的零元素容易看出4个个“0”的位置的位置()()()()或或()()()()指派问题指派问题assignment problem 11得到两个最优解得到两个最优解 有两个最优方案有两个最优方案第一种方案第一种方案：第一个工厂加工产品：第一个工厂加工产品1，第二

8、工厂加工产品，第二工厂加工产品3，第三个工厂加工产品第三个工厂加工产品4，第四个工厂加工产品，第四个工厂加工产品2；第二种方案第二种方案：第一个工厂加工产品：第一个工厂加工产品1，第二工厂加工产品，第二工厂加工产品4，第三个工厂加工产品第三个工厂加工产品3，第四个工厂加工产品，第四个工厂加工产品2；单件产品总成本单件产品总成本Z5815025055513 指派问题指派问题assignment problem 12其它变异问题其它变异问题指派问题指派问题assignment problem 1)最大化指派问题最大化指派问题对于最大化指派问题，假定系数矩阵为，令，再令对于最大化指派问题，假定系数矩

9、阵为，令，再令，这样就把系数矩阵，这样就把系数矩阵C的原最大化指派问题化成系数矩阵为的原最大化指派问题化成系数矩阵为B的最小化指派问的最小化指派问题。两者具有相同的最优解。题。两者具有相同的最优解。2）人数与事数不等的指派问题）人数与事数不等的指派问题对于人数与事数不等的指派问题，通过如下方法，将其化为标准的指派问题：对于人数与事数不等的指派问题，通过如下方法，将其化为标准的指派问题：（1）如果人少事多，增加一些虚拟）如果人少事多，增加一些虚拟“人人”，虚拟，虚拟“人人”做事的费用系数取为做事的费用系数取为0;（2）如果人多事少，增加一些虚拟）如果人多事少，增加一些虚拟“事事”，虚拟，虚拟“事

10、事”做事的费用系数也取做事的费用系数也取为为0；3）一个人可做几件事的指派问题）一个人可做几件事的指派问题可将某个人化作同样几个可将某个人化作同样几个“人人”接受指派，这几个接受指派，这几个“人人”做同一件事的费用做同一件事的费用系数一样。系数一样。4）某事一定不能由某人做的指派问题）某事一定不能由某人做的指派问题可将相应的费用系数取为足够大的数可将相应的费用系数取为足够大的数M。13【例例3】求例求例1的最优分配方案的最优分配方案 指派问题指派问题assignment problem 人事部门欲安排四人到四个不同的岗位工作，每个岗位一个人人事部门欲安排四人到四个不同的岗位工作，每个岗位一个人

11、经考核四人在不同岗位的成绩（百分制）如下表所示，如何安排经考核四人在不同岗位的成绩（百分制）如下表所示，如何安排他们的工作使总成绩最好。他们的工作使总成绩最好。表表5-34 工作工作人员人员ABCD甲甲85927390乙乙95877895丙丙82837990 丁丁8690808814【例例4】某商业集团计划在市内四个点投资四个专业超市，考虑某商业集团计划在市内四个点投资四个专业超市，考虑的商品有电器、服装、食品、家俱及计算机等的商品有电器、服装、食品、家俱及计算机等5个类别通过评个类别通过评估，家具超市不能放在第估，家具超市不能放在第3个点，计算机超市不能放在第个点，计算机超市不能放在第4个点

12、，个点，不同类别的商品投资到各点的年利润（万元）预测值见下表不同类别的商品投资到各点的年利润（万元）预测值见下表该商业集团如何作出投资决策使年利润最大。该商业集团如何作出投资决策使年利润最大。表表 地点地点商品商品1234电器电器120300360400服装服装80350420260食品食品150160380300家具家具90200180计算机计算机220260270指派问题指派问题assignment problem 15【解解】这是求最大值、人数与任务数不相等、不可接受的这是求最大值、人数与任务数不相等、不可接受的配置的一个综合指派问题，分别对表进行转换配置的一个综合指派问题，分别对表进行

13、转换（1）令）令c43=c54=0（2）转换成求最小值问题，令）转换成求最小值问题，令M420，得到效率表（机，得到效率表（机会损失表）会损失表）（3）虚拟一个地点）虚拟一个地点5 指派问题指派问题assignment problem 16 地点地点商品商品 12345电器电器30012060200服装服装3407001600食品食品270260401200家俱家俱3302204202400计算机计算机2001601504200Z=1350 转换后得到下表用匈牙利法求解得到最优解转换后得到下表用匈牙利法求解得到最优解 最优投资方案最优投资方案：地点：地点1投资建设计算机超市，地点投资建设计算机

14、超市，地点2投资建设服投资建设服装超市，地点装超市，地点3投资建设食品超市，地点投资建设食品超市，地点4投资建设电器超市，投资建设电器超市，年利润总额预测值为年利润总额预测值为1350万元万元 指派问题指派问题assignment problem 171 1指派模型的特征指派模型的特征2 2匈牙利法求解指派问题的条件匈牙利法求解指派问题的条件3 3匈牙利法的两个基本定理匈牙利法的两个基本定理4 4指派问题也是一个特殊的运输问题指派问题也是一个特殊的运输问题.5 5将将指指派派（分分配配）问问题题的的效效率率矩矩阵阵每每行行分分别别加加上上一一个个数数后后最优解不变最优解不变.指派问题指派问题assignment problem 18