赵青青

【摘要】指派问题是运筹学中的一个重要的线性规划问题，它属于特殊的运输问题。运筹学已经成为各行各业进行管理决策的一个基本工具，其目的是根据实际问题的具体要求，通过定量的分析与运算，对资源运用、筹划及相关决策等问题最初综合最优的合理安排，以使有限的资源发挥更大的效益或作用。而我们所研究的指派问题旨在解决生活中所出现的形形色色的资源配置问题。

【关键词】指派问题 匈牙利算法 资源配置

一、模型的处理

（一）建立模型

指派问题AP：今有n个工人和n件工作，第i个工人做第j件工作的费用（如成本，时间，效能等）为cij，i，j=1，2，…，n.问；应如何制定一个工人和工作之间的指派方案，才能使完成这n件工作的总费用最少？

（二）算法步骤

1.知识准备

步骤1 约化费用矩阵C为C'：将C的每一行的各元素都减去本行最小的元素，每一列的各元素都减去本列的最小元素，转步骤2.

步骤2 找独立格子集Q：若C'的某行（列）只有一个零元素，则将其圈起，并将与其同列的其余零元素畫×，如此重复，直到C'的所有的零元素都被圈起或画×为止.令Q={tij|c'ij=0被圈起）.若|Q|=n，则得指派问题AP的最优解为xij=1.tok∈Q 0，否则，停；否则，转步骤3.

步骤3 找覆盖C'的所有零元素的数目最少的直线；若某行无圈起的零元素，则在此行打√；在打√的列中，对圈起的零元素所在的行打√.如此重复，直到再也不存在可打√的行或列为止.对未打√的行画一横线，对打√的列画一竖线。

继续约化C'：令C'的未被直线覆盖的最小元素θ，将未被直线覆盖的元素所在的行（或列）的各元素都减去θ.为消除负元素，可将负元素所在的列（或行）的各元素都加上θ。……