运筹学指派问题.pdf

: .
运筹学-指派问题（Assig方法是
在未被直线覆盖的元素中找出一个最小元素，然后在打“”行各元素
中都减去这一元素，而在打“”列的各元素都加上这一最小元素，以
保持原来0元素不变（消除负元素）。得到新的系数矩阵。（它的最优
解和原问题相同，为什么？）由解矩阵可得指派方案和最优值为32。例2 某大型工程有五个工程项目，决定向社会公开招标，有五家
建筑能力相当的建筑公司分别获得中标承建。已知建筑公司Ai（I=1
，2，3，4，5）的报价cij（百万元）见表，问该部门应该怎样分配建
造任务，才能使总的建造费用最小？ : .
运筹学-指派问题（Assignment Problem）
1. 标准指派问题的提法及模型
指派问题的标准形式是：有n个人和n件事，已知第i个人做第j件
事的费用为cij（i，j=1，2，…，n），要求确定人和事之间的一一对
应的指派方案，使完成这n件事的总费用最小。
2
设n 个0-1变量
若指派第i个人做第j件事
(i,j=1,2,…, n)
若不指派第i个人做第j件事
数学模型为: : .
运筹学-指派问题（Assignment Problem）
1. 标准指派问题的提法及模型
指派问题的标准形式是：有n个人和n件事，已知第i个人做第j件
事的费用为cij（i，j=1，2，…，n），要求确定人和事之间的一一对
应的指派方案，使完成这n件事的总费用最小。
2
设n 个0-1变量
若指派第i个人做第j件事
(i,j=1,2,…, n)
若不指派第i个人做第j件事
数学模型为: : .
其中矩阵C称为是效率矩阵或系数矩阵。
其解的形式可用0-1矩阵的形式来描述，即 (xij)nn。
标准的指派问题是一类特殊的整数规划问题，又是特殊的0-1
规划问题和特殊的运输问题。1955年W. W. Kuhn利用匈牙利数学