4-4.1指派问题.ppt

指派问题(assignment problem) 指派问题的标准形式及其数学模型 匈牙利解法 指派问题的标准形式的提出？ 在我们现实生活中，常有各种性质的指派问题。例如：应如何分配若干项工作给若干个人（或部门）来完成，以达到总体的最佳效果等等。由于指派问题的多样性，我们有必要定义指派问题的标准形式。 一、指派问题的标准形式及其数学模型 指派问题的标准形式（以人和事为例） n个人做n件事，并且要求每人必须而且只做一件事。设第i人做第j件事的费用为 Cij（i,j＝1，2……，n)，使总费用最少。 为了建立标准指派问题的数学模型，我们引入n2个 0－1变量。并且得到该问题的数学模型。 来表示。 建立数学模型 这是一个标准的指派问题。若设0－1变量 二、匈牙利解法 匈牙利解法的关键是利用了指派问题最优解的如下性质： 若从指派问题的系数矩阵C=（cij）n×n的某行（或某列）各元素分别减去一个常数k，得到一个新的系数矩阵C’= （c’ij ）,则以C和C’为系数矩阵的两个指派问题有相同的最优解。 以例子说明步骤 变化后，新系数矩阵各行各列都出现0元素 观察法、试探法找出n个独立0元素 n个独立0元素所对应的变量取值为1，其余变量取值为0 例 继续变换系数矩阵。其方法是在未被直线覆盖的元素中找出一个最小元素。然后在打√号行各元素都减去这一最小元素，而在打√号列的各元素都加上这一最小元素，以保证原来的 0 元素不变。这样得到新系数矩阵（其最优解和原问题相同）。若得到 n 个独立的 0 元素，则已得最优解，否则重复该步骤继续变换系数矩阵。 * * * * 因此，我们可得指派问题的系数矩阵 对于问题的每个可行解，可用解矩阵 6 10 12 9 6 A5 10 6 14 7 6 A4 7 8 12 9 6 A3 10 14 17 9 7 A2 12 15 7 8 4 A1 B5 B4 B3 B2 B1 cij Bj Ai 书P114,例6。注：价值系数有所不同 匈牙利法基于下面的价值系数矩阵： c11 c12 … c1n （cij）= c21 c22 … c2n ………………. cn1 cn2 … cnn 一般为该行（列）的最小元素 含有很多0元素 匈牙利法基于这样一个明显的事实：如果系数矩阵的所有元素满足cij≥0，而其中有n个位于不同行不同列的一组0元素（独立0元素），则只要令对应于这些0元素位置的xij＝1，其余的xij＝0，就得到最优解。 0 4 2 0 例如： （cij）= 2 0 7 8 3 1 5 0 0 6 0 3 匈牙利数学家康尼格关于矩阵中0元素的定理：系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数 2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9 0 13 11 2 6 0 10 11 0 5 7 4 0 1 4 2 2 4 9 7 min （ cij ）= 0 13 11 2 6 0 10 11 0 5 7 4 0 1 4 2 0