实际生活中经常会遇到这样一类问题：将不同的任务分派给不同的人去完成，每个人完成的效率不同，需要考虑如何分配才能使得总效率最高。这类问题统称指派问题。其中的“任务”可以是任何类型的活动，“人”则可以是任何类型的资源。所以，指派问题在资源配置、项目选址、物流管理、生产调度以及军事作战等各方面有着极为广泛的应用。
1. 问题的提出—— 指派问题
拟分配n个人去做n项工作，每人做且仅做一项工作，若分配第i人去做第j项工作，需花费cij单位时间，问应如何分配工作才能使工人花费的总时间最少？称C=(cij)为指派问题的系数矩阵。
2. 模型的分析和假设
引入0-1变量xij，若第i个人做了第j项工作，则为1，否则为0。由于此问题要求“每项工作仅需要一个人去完成，每个人仅需完成一项工作”，所以最优解方阵的每行、每列仅有一个“1”，其余元素全为0。
3. 模型的建立
上述指派问题的数学模型为
这是一个0-1整数规划模型。
若指派矩阵为
求解此规划问题。
4. 模型的求解
对于指派问题等0-1整数规划，可以直接利用MATLAB求解，但使用MATLAB软件求解数学规划问题有一个缺陷，即必须把所有的决策变量化成一维决策向量。
MATLAB程序如下：
(www.xing528.com)
5. 结果的分析
第一个人做第五项工作，第二个人做第三项工作，第三个人做第二项工作，第四个人做第四项工作，第五个人做第一项工作，这是最优的分配方案，这时总花费时间为21小时。其他的分配方案都会比该方案花费的时间要多。
在现实生活中，常常会遇到各种非标准的指派问题，通常是先将它们化为标准的指派问题，再求解。
（1）最大化指派模型。比如每个人完成工作的效率是利润、业绩等，此时工作效率最大为目标函数，也即
（2）人和任务数不等的指派问题。若人数少于任务数，可以添加一些虚拟的“人”，这些虚拟的人完成各项任务的效率为0，也就是实际上不会发生；若人数多于任务数，则可以添加一些虚拟的“任务”，这些虚拟的任务被每个人完成的效率同样为0。
（3）一个人可能完成多项任务。此时，可将这个人看作相同的几个人来接受指派，只需令其完成同一任务的效率相等。
（4）某项任务一定不能由某人完成。此时，将相应的效率取足够大，也就是这个人不可能完成这项任务。
习题1.2
1. 某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出，从钢管厂进货时得到的原料钢管长度都是1 850 mm。现有一客户需要15根290 mm、28根315 mm、21根350 mm和30根455 mm的钢管，为了简化生产过程，规定所使用的切割模式的种类不能超过4种，使用频率最高的一种切割模式按照一根原料钢管价值的1/10增加费用，使用频率次之的切割模式按照一根原料钢管价值的2/10增加费用，以此类推，且每种切割模式下的切割次数不能太多（一根原料钢管最多生产5根产品）。此外，为了减少余料浪费，每种切割模式下的余料浪费不能超过100 mm。为了使总费用最小，应如何下料?
2. 某市要建5个消防站，决定由5个建筑公司分别承建，已知建筑公司Ai (i=1,2,3,4,5)建设消防站B j (j=1,2,3,4,5)的建筑报价为ci j(i ,j=1,2,3,4,5)，如表1.2.4所示，如何分配建造计划才能使总费用最小？
表1.2.4 建造费用报价数据
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
