任务四指派问题及其求解方法_运筹学基础（第二版）-QQ阅读男生都市网

上QQ阅读APP看本书，新人免费读10天

设备和账号都新为新人

任务四　指派问题及其求解方法

指派问题又称分配问题，是一类特殊的0—1规划，也是一类特殊的整数规划。指派问题研究如何进行最优安排，使花费的时间、资源最少，或取得的收益最高。

4.1　指派问题的数学模型

n个人被分配去做n件工作，已知第i个人去做第j件工作的效率为cij（i＝1，2，…，n；j＝1，2，…，n）并假设cij≥0。问应如何分配才能使总效率（时间或费用）最高？

设决策变量

那么

例3-4-1　有一份中文说明书，需翻译成英、日、德、俄四种文字，分别记作E、J、G、R，现有甲、乙、丙、丁四人，他们将中文说明书翻译成英、日、德、俄四种文字所需时间如表3-4-1所示，问应该如何分配工作，使所需总时间最少？

表3-4-1

解：建立模型：引入0—1变量，xij＝1表示分配第i人去完成第j项任务，xij＝0表示不分配第i人去完成第j项任务。

4.2　匈牙利法

1955年，库恩提出了指派问题的解法，他引用了匈牙利数学家康尼格一个关于矩阵中0元素的定理：系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数，这个解法也就成了匈牙利法。

匈牙利法的解题步骤如下。

第一步：使分配问题的系数矩阵经变换，在各行各列中都出现0元素。

（1）从系数矩阵的每行元素减去该行的最小元素。

（2）再从所得系数矩阵的每列元素减去该列的最小元素。若某行或某列已经有0元素，就不必再减了。

第二步：进行试分配，以寻找最优解。

（1）从只有一个0元素的行（或列）开始，给这个0元素加括号，然后划去它所在的列（或行）的其他0元素。

（2）给只有一个0元素的列（或行）的0元素加括号，然后划去它所在的行（或列）的其他0元素。

反复进行上述两步，直到所有的0元素都被加了括号或者被划掉为止。

（3）若还有没有加括号的0元素，且同行（或列）的0元素至少有两个，从剩有0元素最少的行（或列）开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的0元素加括号，然后划掉同行同列的其他0元素，可反复进行，直到所有的0元素都加了括号或者划掉为止。

（4）若加括号的0元素的数目m等于矩阵阶数n，那么这分配问题的最优解已得到。若m＜n，则转下一步。

第三步：作最少的直线覆盖所有的0元素，以确定该系数矩阵中能找到最多的独立元素数。

（1）对没有加括号0元素的行，打。

（2）对已打行中所有含0元素的列打。

（3）再对打列中含加括号的0元素的行打。

（4）重复上述两步，直到得不出新的打行列为止。

（5）对没有打行画横线，有打列画纵线，就得到覆盖所有0元素的最少直线数。

第四步：在没有被直线覆盖的部分中找出最小元素，所有未被直线覆盖的元素都减去该最小元素，位于水平直线与铅直直线交叉处的元素都加上这个最小元素，其余元素保持不变，这样就可以得到新的系数矩阵（它的最优解和原问题相同）。返回第二步，继续寻找最优解，若得到n个加括号的0元素，则已经得到最优解。否则回到第三步重复进行。

下面通过例子来具体说明匈牙利法的解题步骤。

用匈牙利法求解例3-4-1。