数学建模6.5指派问题.ppt

指派问题 设有n项任务要分给n个人去完成 每人完成一项 由于每个人的专长不同 故完成不同任务所需的成本也不同 若第i个人完成第j项任务的成本为cij 则如何分配这些工作任务 使总成本为最小 这类问题称为指派问题 矩阵C cij 称为成本矩阵 设置变量 z 总成本 数学模型 每项任务由一人完成 每人只承担一项任务 总成本最小 解矩阵的特征 全部元素仅取0或1每行有且仅有一个1每列有且仅有一个1 性质 从原成本矩阵C的任一行 列 中各元素加 减 一个常数 得到新的成本矩阵 则此两成本矩阵的指派问题的最优解是相同的 证明 设矩阵C的第i行对应的常数为di 即f与z仅差一个常数 所以两目标在相同的约束条件下 最优解是相同的 求解的思想方法 若利用以上性质 能把成本矩阵变换到存在n个独立的0元素 在不同行不同列 且保持每个Cij非负 这时让这n个0元素的位置对应的xij 1 其余位置的xij 0 就得最优解 因为它是目标值为0的可行解 且总有 匈牙利数学家康尼格 D Konig 的定理 若在成本矩阵C中最多能找到k个独立0 则必可画k条直线把C的全部0覆盖 匈牙利法 步骤 1 把成本矩阵的各行每一元素分别减去该行中的最小元素 再检查每列中是否都有0 若不是 则把没有0的列的每一元素分别减去该列中的最小元素 2 如果能在矩阵中找到n个独立的0元素 就可以进行指派 即对应于这n个0元素的位置的xij 1 其余位置的xij 0 结束 3 当独立的0个数k n时 可用k条直线覆盖全部0 然后从未被覆盖的各元素中 选出最小的元素a 把未被覆盖的各元素减去这个最小元素 而两直线交叉处的元素加上这个最小元素 这种操作相当于 未被覆盖的行都减a 被覆盖的列都加a 4 重复第 3 步 直做到能在矩阵中找到n个独立的0为止 这样就可以进行指派 最大化指派问题 不平衡时的处理办法 虚拟法 以上方法只适用于 人数 任务数当人数 任务数时n 人数 m 任务数若n m 则虚拟n m个任务 相应Cij 0若n m 则虚拟m n个人 相应Cij 0这样就化为人数与任务数相等的情况 在C中找出最多独立0的步骤 设Wi表示第i行0的数目 Lj表示第j列0的数目 1 统计Wi和Lj i j 1 2 n 2 按W1 W2 Wn L1 L2 Ln顺序找出第一个最小正数 选中该行 列 首个0 3 删除该0所在的行与列 对应的Wi 0 Lj 0 4 重复步骤1 3 直到全部Wi 0为止 这样就找到4个独立0 如果按自上而下从左到右顺序找 这样只找到3个独立0 画覆盖线的方法 刚才每个独立0 都画了两条线 把覆盖0数目少的一条拿走 保留另一条 这样 4条线就覆盖了全部0 用伏格尔 Vogel 法求解指派问题的原理 求解最小化的指派问题 就是在成本矩阵C中找出n个独立的cij 使它们的和最小 最小化的指派问题 可视作平衡运输问题 其中ai 1 bj 1 i 1 n j 1 n 基本步骤 1 计算每行 列两个最小Cij的差 差 次小 最小 注 当最小值不唯一或只剩一个数时 差 0 2 找出最大差值所在的行或列 3 选定该行或列的最小Cij 4 删掉该行和该列 5 在剩余的Cij中重复1 4步n次 就可选出n个独立的Cij 3 1 4 5 1 7 6 2 9 1 10 4 2 5 2 5 9 2 这个解是最优解 最小总成本为24 计算机模拟结果 经编程进行了大量的计算机模拟得出统计结果 用伏格尔法求解指派问题 约有2 3能