441指派问题.pptx

指派问题指派问题(assignment problem)(assignment problem)n n指派问题的标准形指派问题的标准形式及其数学模型式及其数学模型n n匈牙利解法匈牙利解法指派问题的标准形式的提出？指派问题的标准形式的提出？n n在我们现实生活中，常有在我们现实生活中，常有在我们现实生活中，常有在我们现实生活中，常有各种性质的指派问题。例各种性质的指派问题。例各种性质的指派问题。例各种性质的指派问题。例如：应如何分配若干项工如：应如何分配若干项工如：应如何分配若干项工如：应如何分配若干项工作给若干个人（或部门）作给若干个人（或部门）作给若干个人（或部门）作给若干个人（或部门）来完成，以达到总体的最来完成，以达到总体的最来完成，以达到总体的最来完成，以达到总体的最佳效果等等。由于指派问佳效果等等。由于指派问佳效果等等。由于指派问佳效果等等。由于指派问题的多样性，我们有必要题的多样性，我们有必要题的多样性，我们有必要题的多样性，我们有必要定义指派问题的标准形式。定义指派问题的标准形式。定义指派问题的标准形式。定义指派问题的标准形式。一、一、指派问题的标准形式及其数学模型指派问题的标准形式及其数学模型n n指派问题的标准形式（以人和事为例）指派问题的标准形式（以人和事为例）n n个人做个人做个人做个人做n n件事，并且要求每人必须而且只做件事，并且要求每人必须而且只做件事，并且要求每人必须而且只做件事，并且要求每人必须而且只做一件事。设第一件事。设第一件事。设第一件事。设第i i人做第人做第人做第人做第j j件事的费用为件事的费用为件事的费用为件事的费用为 C Cij ij（i,ji,j1 1，22，n)n)，使总费用最少。，使总费用最少。，使总费用最少。，使总费用最少。因此，我们可得因此，我们可得因此，我们可得因此，我们可得指派问题的系数指派问题的系数指派问题的系数指派问题的系数矩阵矩阵矩阵矩阵 来表示。来表示。来表示。来表示。对于问题的每个可行解，可用解矩阵对于问题的每个可行解，可用解矩阵对于问题的每个可行解，可用解矩阵对于问题的每个可行解，可用解矩阵n n为了建立标准指派问题的数学模型，我们引入为了建立标准指派问题的数学模型，我们引入为了建立标准指派问题的数学模型，我们引入为了建立标准指派问题的数学模型，我们引入n n 个个个个 0 01 1变量。并且得到该问题的数学模型。变量。并且得到该问题的数学模型。变量。并且得到该问题的数学模型。变量。并且得到该问题的数学模型。cij ij B Bj jAi i B1 1B2 2B3 3B4 4B5 5A1 14 48 87 715151212A2 27 79 9171714141010A3 36 69 912128 87 7A4 46 67 714146 61010A5 56 69 9121210106 6例（同书例（同书例（同书例（同书P114P114，例，例，例，例6 6，价值系数有所不同价值系数有所不同价值系数有所不同价值系数有所不同）建立数学模型建立数学模型这是一个标准的指派问题。若设这是一个标准的指派问题。若设这是一个标准的指派问题。若设这是一个标准的指派问题。若设0 01 1变量变量变量变量8二、匈牙利解法二、匈牙利解法二、匈牙利解法二、匈牙利解法 匈牙利解法的关键是利用了指派问题最优解的如下性质：匈牙利解法的关键是利用了指派问题最优解的如下性质：若从指派问题的系数矩阵若从指派问题的系数矩阵C=C=（c cijij）nnnn的某行（或某列）的某行（或某列）各元素分别各元素分别减去一个常数减去一个常数k k，得到一个新的系数矩阵，得到一个新的系数矩阵C=C=（ccijij ）,则以则以C C和和CC为系数矩阵的两个指派问题有为系数矩阵的两个指派问题有相同的最相同的最优解优解。匈牙利法基于下面的价值系数矩阵：匈牙利法基于下面的价值系数矩阵：c11 c12 c1n （cij）=c21 c22 c2n .cn1 cn2 cnn9 匈牙利法基于这样一个明显的事实：如果系匈牙利法基于这样一个明显的事实：如果系数矩阵的所有元素满足数矩阵的所有元素满足c cijij00，而其中有，而其中有n n个位个位于不同行不同列的一组于不同行不同列的一组0 0元素，则只要令对应于元素，则只要令对应于这些这些0 0元素位置的元素位置的x xijij1 1，其余的，其余的x xijij0 0，就得，就得到最优解。到最优解。0 4 2 0 例如：例如：（cij）=2 0 7 8 3 1 5 0 0 6 0 310以例子说明步骤以例子说明步骤 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 22497min（cij ）=11 0 13 11 2 6 0 10 11 0 5 7 4 0 1 4 2 0 0 4 2min 0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0=（cij ）12 0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0此时加圈此时加圈 0 元素的个数元素的个数 m=n=4，所以得到最优解，所以得到最优解13 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0（xij ）=14例例任务任务人员人员ABCDE甲甲乙乙丙丙丁丁戊戊128715479171410961267761461096910915 12 7 9 7 9 8 9 6 6 6 7 17 12 14 9 15 14 6 6 10 4 10 7 10 976764 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 516 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5 此时加圈此时加圈 0 元素的个数元素的个数 m=4，而而n=5，所以解题没，所以解题没有完成。独立零元素（加圈零有完成。独立零元素（加圈零元素）少于元素）少于 n 个，表示还不能个，表示还不能确定最优确定最优指派方案。此时需确定指派方案。此时需确定能覆盖所有能覆盖所有零元素的最少直线数零元素的最少直线数目的直线集合。方法如下：目的直线集合。方法如下：定理：系数矩阵中独立定理：系数矩阵中独立定理：系数矩阵中独立定理：系数矩阵中独立0 0元素的最多个数等于能覆盖元素的最多个数等于能覆盖元素的最多个数等于能覆盖元素的最多个数等于能覆盖 所有所有所有所有0 0元素的最少直线数（匈牙利数学家康尼格提出元素的最少直线数（匈牙利数学家康尼格提出元素的最少直线数（匈牙利数学家康尼格提出元素的最少直线数（匈牙利数学家康尼格提出的关于矩阵中的关于矩阵中的关于矩阵中的关于矩阵中0 0元素的定理）元素的定理）元素的定理）元素的定理）171)对没有加圈零元素的行打对没有加圈零元素的行打号；号；2)对所有打对所有打号行的含号行的含零元素的列打零元素的列打号；号；3)再对已打再对已打号的列中含加圈零元素的行打号的列中含加圈零元素的行打号；号；4)重复重复2）和）和3），直到再也不能找到可以打），直到再也不能找到可以打号行或列为止；号行或列为止；5)对没有打对没有打号的行画一横线，对打号的行画一横线，对打号的列号的列画一竖线，这样就得到画一竖线，这样就得到能覆盖所有能覆盖所有零元素零元素的最少直线数目的直线集合。的最少直线数目的直线集合。18 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 51)对没有加圈零元素的行打对没有加圈零元素的行打号；号；2)对所有打对所有打号行的含号行的含零元素的列打零元素的列打号；号；3)再对已打再对已打号的列中含加圈零元素的行打号的列中含加圈零元素的行打号；号；4)重复重复2）和）和3），直到再也不能找到可以打），直到再也不能找到可以打号行或列为止；号行或列为止；5)对没有打对没有打号的行画一横线，对打号的行画一横线，对打号的列画一竖线，这样就得到能覆盖号的列画一竖线，这样就得到能覆盖所有零元素的最少直线数目的直线集合。所有零元素的最少直线数目的直线集合。19 继续变换系数矩阵。其方法是在未被直线覆盖的继续变换系数矩阵。其方法是在未被直线覆盖的元素中找出一个最小元素。然后在打元素中找出一个最小元素。然后在打号号行行各元素都各元素都减减去这一最小元素，而在打去这一最小元素，而在打号号列列的各元素都的各元素都加加上这上这一最小元素，以保证原来的一最小元素，以保证原来的 0 元素不变。这样得到新元素不变。这样得到新系数矩阵（其最优解和原问题相同）。若得到系数矩阵（其最优解和原问题相同）。若得到 n 个独个独立的立的 0 元素，则已得最优解，否则重复该步骤继续变元素，则已得最优解，否则重复该步骤继续变换系数矩阵。换系数矩阵。20 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5最小元素最小元素=2 7 0 2 0 2 4 3 0 0 0 0 8 3 5 0 11 8 0 0 4 0 4 1 4 321 7 0 2 0 2 4 3 0 0 0 0 8 3 5 0 11 8 0 0 4 0 4 1 4 3 此时加圈此时加圈 0 元素的个数元素的个数 m=5，而而n=5，独立零元素，独立零元素（加圈零元素）等于（加圈零元素）等于 n 个，个，此此时已得到最优解，其解矩阵为时已得到最优解，其解矩阵为22（xij ）=0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 最优指派：最优指派：甲甲 B乙乙 C丙丙 E丁丁 D戊戊 A