操作课件ch5分配问题.ppt

指派问题 assignment problem ;一种特殊的线性规划问题，我们也经常遇到指派人员做某项工作的情况。指派问题的许多应用都用来帮助管理人员解决如何为一项将要开展进行的工作指派人员的问题。其他的一些应用如为一项任务指派机器、设备或者是工厂 。;指派问题的形式表述: 给定了一系列所要完成的任务（tasks）以及一系列完成任务的被指派者（assignees），所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务。;指派问题的假设: 被指派者的数量和任务的数量是相同的 每一个被指派者只完成一项任务 每一项任务只能由一个被指派者来完成 每个被指派者和每项任务的组合有一个相关成本 目标是要确定怎样进行指派才能使得总成本最小 ;指派问题 assignment problem ;数学模型为：;假设m个人恰好做m项工作，第i个人做第j项工作的效率为cij≥0，效率矩阵为[cij]（如表5-34），如何分配工作使效率最佳（min或max）的数学模型为 ;2 解指派问题的匈牙利算法;【定理5.2】若矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素（称为独立元素）的最大个数．;匈牙利法;;某汽车公司拟将四种新产品配置到四个工厂生产，四个工厂的单位产品成本（元/件）如表5-35所示．求最优生产配置方案． ;第二步：找出矩阵每列的最小元素，再分别从每列中减去，有 ;第三步：用最少的直线覆盖所有“0”，得;第五步：覆盖所有零最少需要4条直线，表明矩阵中存在4个不同行不同列的零元素．容易看出4个“0”的位置 ;得到两个最优解 ;5.4.3 其它变异问题;丁的蛙泳成绩退步到1’15”2；戊的自由泳成绩进步到57”5, 组成接力队的方案是否应该调整？;cij(秒)~队员i 第j 种泳姿的百米成绩;模型求解 ;丁蛙泳c43 =69.6?75.2，戊自由泳c54=62.4 ? 57.5, 方案是否调整？ ;某商业集团计划在市内四个点投资四个专业超市，考虑的商品有电器、服装、食品、家俱及计算机等5个类别．通过评估，家具超市不能放在第3个点，计算机超市不能放在第4个点，不同类别的商品投资到各点的年利润（万元）预测值见表5-36．该商业集团如何作出投资决策使年利润最大。 ;【解】 这是求最大值、人数与任务数不相等、不可接受的配置的一个综合指派问题，分别对表5-36进行转换． （1）令c43=c54=0 （2）转换成求最小值问题，令M＝420， C`ij=M-cij，得到效率表（机会损失表）,即转换后得到表5-37 （3）虚拟一个地点5 ;用匈牙利法求解得到最优解 ;1．指派模型的特征 2．匈牙利法求解指派问题的条件 3．匈牙利法的两个基本定理 4．指派问题也是一个特殊的运输问题. 5．将指派（分配）问题的效率矩阵每行分别加上一个数后最优解不变.