运筹学第17讲

1、第四节第四节 指派问题指派问题 在实际中经常会遇到这样的问题，有在实际中经常会遇到这样的问题，有n n 项不同的任项不同的任务，需要务，需要n n 个人分别完成其中的一项，但由于任务的个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务性质和各人的专长不同，因此各人去完成不同的任务的效率也就不同。于是产生了一个问题，应指派哪个的效率也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成人去完成哪项任务，使完成 n n 项任务的总效率最高，项任务的总效率最高，这类问题称为指派问题或分派问题。这类问题称为指派问题或分派问题。 如果完成任务的效率表现为资源消耗

2、，考虑的是如果完成任务的效率表现为资源消耗，考虑的是如何分配任务使得目标极小化；如果完成任务的效率如何分配任务使得目标极小化；如果完成任务的效率表现为生产效率的高低，则考虑的是如何分配使得目表现为生产效率的高低，则考虑的是如何分配使得目标函数极大化。标函数极大化。 利用不同资源完成不同计划活动的效率通常用表利用不同资源完成不同计划活动的效率通常用表格形式表示为效率表，表格中数字组成格形式表示为效率表，表格中数字组成效率矩阵效率矩阵。例例1 1、 有一份中文说明书，需译成英、日、德、俄四种有一份中文说明书，需译成英、日、德、俄四种文字，分别记作文字，分别记作A A、B B、C C、D D。现有甲

3、、乙、丙、丁四。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？间如下表所示，问如何分派任务，可使总时间最少？ 任务任务人员人员ABCD甲甲67112乙乙4598丙丙31104丁丁5982一、指派问题的数学模型一、指派问题的数学模型设决策变量设决策变量 1 1 分配第分配第i i 个人译第个人译第j j 件语言件语言 xij = 0 相反相反 ( i,j=1.2.3.4)其数学模型为：其数学模型为： )4.3.2.1,1(0)4.3.2.1( 1)4.3.2.1( 1min414141

4、41jixjxixxcZijiijjijijijij或一般指派问题一般指派问题 设设n n 个人被分配去做个人被分配去做n n 件工作，规定每个人只做件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第一件工作，每件工作只有一个人去做。已知第I I 个人个人去做第去做第j j 件工作的的效率（件工作的的效率（ 时间或费用）为时间或费用）为C Cijij( (i i=1.2=1.2n n; ;j j=1.2=1.2n n) )并假设并假设C Cijij 0 0。问应如何分。问应如何分配才能使总效率（配才能使总效率（ 时间或费用）最高？时间或费用）最高？设决策变量设决策变量 1 分配第分

5、配第i 个人去做第个人去做第j 件工作件工作 xij = 0 相反相反 ( i,j=1.2. n )标准形式指派问标准形式指派问题数学模型为：题数学模型为： ).2.1,1(0).2.1( 1).2.1( 1min1111njixnjxnixxcZijniijnjijninjijij或或二、指派问题的解法二、指派问题的解法 匈牙利法匈牙利法 匈牙利数学家克尼格匈牙利数学家克尼格（ Konig ）求解指派问题的求解指派问题的计算方法被称为匈牙利法计算方法被称为匈牙利法，他证明了如下两个定理：他证明了如下两个定理： 指派问题是指派问题是0-1 规划的特例，也是运输问题的特例，规划的特例，也是运输问

6、题的特例，当然可用整数规划，当然可用整数规划，0-1 规划或运输问题的解法去求规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算解，这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法，这就是的。利用指派问题的特点可有更简便的解法，这就是匈牙利法匈牙利法 定理定理1 1 如果从分配问题效率矩阵如果从分配问题效率矩阵 a aijij 的每一行的每一行元素中分别减去（或加上）一个常数元素中分别减去（或加上）一个常数 u ui i ( (被称为该被称为该行的位势行的位势) )，从每一列分别减去（或加上）一个常数，从每一列分别减去（或加上）一个常数 v

7、vj j（被称为该列的位势），得到一个新的效率矩阵（被称为该列的位势），得到一个新的效率矩阵 b bijij ，若其中，若其中 b bij ij = = a aijij- -u ui i- -v vj j，则，则 b bijij 的最优解的最优解等价于等价于 a aijij 的最优解。的最优解。 定理定理2 2 若矩阵若矩阵 A A 的元素可分成的元素可分成“ 0 0 ”与非与非“ 0 0 ”两部分，则覆盖两部分，则覆盖“ 0 0 ”元素的最少直线数等于位于元素的最少直线数等于位于不同行不同列的不同行不同列的“ 0 0 ”元素的最大个数。元素的最大个数。 第一步：变换指派问题的系数矩阵第一步：

8、变换指派问题的系数矩阵（cij）为为(bij)，使使在在(bij)的各行各列中都出现的各行各列中都出现0 0元素，即元素，即 (1) (1) 从从（cij）的每行元素都减去该行的最小元素；的每行元素都减去该行的最小元素； (2) (2) 再从所得新系数矩阵的每列元素中减去该列的再从所得新系数矩阵的每列元素中减去该列的最小元素。最小元素。 第二步：进行试指派，以寻求最优解。第二步：进行试指派，以寻求最优解。 在在(bij)中找尽可能多的独立中找尽可能多的独立0元素元素( (不同行不同列不同行不同列) )，若能找出若能找出n n个独立个独立0元素，就以这元素，就以这n个独立个独立0元素对应解元素对

9、应解矩阵矩阵(xij)中的元素为中的元素为1，其余为其余为0，这就得到最优解。找这就得到最优解。找独立独立0 0元素，常用的步骤为：元素，常用的步骤为： (1)(1)从只有一个从只有一个0元素的行元素的行( (列列) )开始，给这个开始，给这个0元素元素加圈，记作加圈，记作 。然后划去然后划去 所在列所在列( (行行) )的其它的其它0元素，元素，记作记作 ；这表示这列所代表的任务已指派完，不必再这表示这列所代表的任务已指派完，不必再考虑别人了。考虑别人了。 (2)(2)给只有一个给只有一个0 0元素的列元素的列( (行行) )中的中的0 0元素加圈，记作元素加圈，记作；然后划去然后划去 所在

10、行的所在行的0 0元素，记作元素，记作 (3)(3)反复进行反复进行(1)(1)，(2)(2)两步，直到尽可能多的两步，直到尽可能多的0 0元素元素都被圈出和划掉为止都被圈出和划掉为止。 (4)(4)若仍有没有划圈的若仍有没有划圈的0 0元素，且同行元素，且同行( (列列) )的的0 0元素元素至少有两个，则从剩有至少有两个，则从剩有0 0元素最少的行元素最少的行( (列列) )开始，比较开始，比较这行各这行各0 0元素所在列中元素所在列中0 0元素的数目，选择元素的数目，选择0 0元素少的那元素少的那列的这个列的这个0 0元素加圈元素加圈( (表示选择性多的要表示选择性多的要“礼让礼让”选择

11、选择性少的性少的) )。然后划掉同行同列的其它。然后划掉同行同列的其它0 0元素。可反复进元素。可反复进行，直到所有行，直到所有0 0元素都已圈出和划掉为止。元素都已圈出和划掉为止。 （5 5）若）若 元素的数目元素的数目m m 等于矩阵的阶数等于矩阵的阶数n n，那么这，那么这指派问题的最优解已得到。若指派问题的最优解已得到。若m m n n, , 则转入下一步。则转入下一步。 第三步：作最少的直线覆盖所有第三步：作最少的直线覆盖所有0 0元素。元素。 (1)(1)对没有对没有的行打的行打号；号； (2)(2)对已打对已打号的行中所有含号的行中所有含元素的列打元素的列打号；号； (3)(3)

12、再对打有再对打有号的列中含号的列中含 元素的行打元素的行打号；号； (4)(4)重复重复(2)(2)，(3)(3)直到得不出新的打直到得不出新的打号的行、列号的行、列为止；为止； (5)(5)对没有打对没有打号的行画横线，有打号的行画横线，有打号的列画纵号的列画纵线，这就得到覆盖所有线，这就得到覆盖所有0 0元素的最少直线数元素的最少直线数 l 。l 应等应等于于m m，若不相等，说明试指派过程有误，回到第二步，若不相等，说明试指派过程有误，回到第二步(4)(4)，另行试指派；若，另行试指派；若 lm nm n，须再变换当前的系，须再变换当前的系数矩阵，以找到数矩阵，以找到n n个独立的个独立

13、的0 0元素，为此转第四步。元素，为此转第四步。第四步：变换矩阵第四步：变换矩阵( (b bijij) )以增加以增加0 0元素。元素。在没有被直线覆盖的所有元素中找出最小元素，在没有被直线覆盖的所有元素中找出最小元素，然后未被直线覆盖的元素都减去这最小元素；被然后未被直线覆盖的元素都减去这最小元素；被直线覆盖两次的元素加上这最小元素（以保证系直线覆盖两次的元素加上这最小元素（以保证系数矩阵中不出现负元素），其他不变。新系数矩数矩阵中不出现负元素），其他不变。新系数矩阵的最优解和原问题仍相同。转回第二步。阵的最优解和原问题仍相同。转回第二步。 例例1 1、 有一份中文说明书，需译成英、日、德、

14、俄四种有一份中文说明书，需译成英、日、德、俄四种文字，分别记作文字，分别记作A A、B B、C C、D D。现有甲、乙、丙、丁四。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？间如下表所示，问如何分派任务，可使总时间最少？ 任务任务人员人员ABCD甲甲67112乙乙4598丙丙31104丁丁5982求解过程如下：求解过程如下：第一步，变换系数矩阵：第一步，变换系数矩阵：2142 289541013895421176)( ijc 0673390245100954 01733402401

15、004545第二步，试指派：第二步，试指派：找到找到 3 3 个独立零元素个独立零元素 但但 m m = 3 3 n = 4 00102350960607130 2410475011100621113042 00102350960607130 0100000100101000 第三步，作最少的直线覆盖所有第三步，作最少的直线覆盖所有0 0元素：元素：立零元素的个数独立零元素的个数m m等于最少直线数等于最少直线数l，即即lm=3n=4； 第四步，变换矩阵第四步，变换矩阵( (bij) )以增加以增加0 0元素：没有被直线覆盖元素：没有被直线覆

16、盖的所有元素中的最小元素为的所有元素中的最小元素为1 1，然后打，然后打各行都减去各行都减去1 1；打打各列都加上各列都加上1 1，得如下矩阵，并转第二步进行试指，得如下矩阵，并转第二步进行试指派：派： 6244251343000 0 00 0100001000011000得到得到4 4个独个独立零元素，立零元素， 所以最优解所以最优解矩阵为：矩阵为：0624425134315 6244251343 三、非标准的指派问题三、非标准的指派问题 1. 1. 指派问题中人数和工作任务不相等时指派问题中人数和工作任务不相等时 当人数多于工作任务数时，可以添加假想任务使当人数多

17、于工作任务数时，可以添加假想任务使得人数与工作任务数相同，因为工作任务是假想的，得人数与工作任务数相同，因为工作任务是假想的，因此完成这些任务的时间是零。当任务数多于人数时，因此完成这些任务的时间是零。当任务数多于人数时，可添加假想的人。这样的方法和运输问题中处理的方可添加假想的人。这样的方法和运输问题中处理的方法类似。法类似。 2. 2. 当问题目标变为求极大时当问题目标变为求极大时mimjijijxaz11max可改写为可改写为mimjijijxaz11)(min此时效率矩阵中元素都变为了负值，可利用定理此时效率矩阵中元素都变为了负值，可利用定理1 1，使效率矩阵中全部元素都变为非负的，就

18、可以利用匈使效率矩阵中全部元素都变为非负的，就可以利用匈牙利法进行求解。牙利法进行求解。 3. 3. 某某“任务任务”一定不能由某一定不能由某“人员人员”做的指派问题做的指派问题对于极小化的指派问题，某对于极小化的指派问题，某“任务任务”一定不能由某一定不能由某“人员人员”做的指派问题，可令相应效率系数为充分大做的指派问题，可令相应效率系数为充分大的的M M一、案例分析一、案例分析二、二、WINQSB软件应用软件应用第五节第五节 案例分析及案例分析及WINQSB软件应用软件应用人力资源分配问题人力资源分配问题 某个中型百货商场对售货人员（周工资某个中型百货商场对售货人员（周工资200200元）

19、的需求经统计如下表元）的需求经统计如下表 为了保证销售人员充分休息，销售人员为了保证销售人员充分休息，销售人员每周工作每周工作5 5天，休息天，休息2 2天。问应如何安排销天。问应如何安排销售人员的工作时间，使得所配售货人员的售人员的工作时间，使得所配售货人员的总费用最小？总费用最小？星期星期一一二二三三四四五五六六七七人数人数1212151512121414161618181919模型假设模型假设每天工作每天工作8 8小时，不考虑夜班的情况；小时，不考虑夜班的情况；每个人的休息时间为连续的两天时间；每个人的休息时间为连续的两天时间；每天安排的人员数不得低于需求量，但可以每天安排的人员数不得低

20、于需求量，但可以超过需求量超过需求量问题分析问题分析因素：不可变因素：需求量、休息时间、单位费用；因素：不可变因素：需求量、休息时间、单位费用；可变因素：安排的人数、每人工作的时间、总费用可变因素：安排的人数、每人工作的时间、总费用方案：确定每天工作的人数，由于连续休息方案：确定每天工作的人数，由于连续休息2 2天，当确天，当确定每个人开始休息的时间就等于知道工作的时间，定每个人开始休息的时间就等于知道工作的时间，因而确定每天开始休息的人数就知道每天开始工作因而确定每天开始休息的人数就知道每天开始工作的人数，从而求出每天工作的人数。的人数，从而求出每天工作的人数。变量：每天开始休息的人数变量：

21、每天开始休息的人数 约束条件约束条件 ： 1.1.每人休息时间每人休息时间2 2天，自然满足。天，自然满足。 3.3.变量非负约束：变量非负约束：7,.,2 , 1, 0ixi 目标函数：总费用最小，总费用与使用的总目标函数：总费用最小，总费用与使用的总人数成正比。由于每个人必然在且仅在某人数成正比。由于每个人必然在且仅在某一天开始休息，所以总人数等于一天开始休息，所以总人数等于模型模型7,.,2 , 1, 019181614121512. .200min5432174321763217652117654765436543271ixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxtsxiii 校篮球队教练要确定比赛的首发阵容。全队共有校篮球队教练要确定比赛的首发阵容。全队共有7 7名球员，根名球员，根据技术水平，对每名运动员的控球（据技术水平，对每名运动员的控球（ball-handingball-handing）、投篮）、投篮（shootingshooting）、蓝板（）、蓝板（rebounding