清华大学出版社：《运筹学》课程教学资源（PPT课件讲稿，教材第三版）第5章 整数线性规划 第5节 指派问题

运筹学 (第三版) 《运筹学》教材编写组 第5章整数线性规划 第5节 清华大学出版社

运筹学 （第三版） 《运筹学》教材编写组 第5章 整数线性规划 第5节 清华大学出版社

第5章整数线性规划 第5节指派问题 在生活中经常遇到这样的问题,某单位需完成 n项任务,恰好有n个人可承担这些任务。由于 每人的专长不同,各人完成任务不同(或所费 时间),效率也不同。于是产生应指派哪个人 去完成哪项任务,使完成n项任务的总效率最 高(或所需总时间最小)。这类问题称为指派问 题或分派问题( assignment problem)

第5章 整数线性规划 第5节 指 派 问 题 • 在生活中经常遇到这样的问题，某单位需完成 n项任务，恰好有n个人可承担这些任务。由于 每人的专长不同，各人完成任务不同(或所费 时间)，效率也不同。于是产生应指派哪个人 去完成哪项任务，使完成n项任务的总效率最 高(或所需总时间最小)。这类问题称为指派问 题或分派问题(assignment problem)

例7有一份中文说明书,需译成英、日、德、俄 四种文字。分别记作E、J、G、R。现有甲、乙、 丙、丁四人。他们将中文说明书翻译成不同语种 的说明书所需时间如表5-7所示。问应指派何人去 完成何工作,使所需总时间最少? 表5-7 任务E|J|GR 人员 15134 甲乙丙丁 2(97 041415 141613 811|9

例7 有一份中文说明书，需译成英、日、德、俄 四种文字。分别记作E、J、G、R。现有甲、乙、 丙、丁四人。他们将中文说明书翻译成不同语种 的说明书所需时间如表5-7所示。问应指派何人去 完成何工作，使所需总时间最少? 表5-7 任 务 人员 E J G R 甲 乙 丙 丁 2 10 9 7 15 4 14 8 13 14 16 11 4 15 13 9

类似有:有n项加工任务,怎样指派到n台机 床上分别完成的问题;有n条航线,怎样指定 n艘船去航行问题…。对应每个指派问题,需 有类似表5-7那样的数表,称为效率矩阵或系 数矩阵,其元素c;>0(i,j=1,2,…,n)表示 指派第i人去完成第j项任务时的效率(或时间、 成本等)。解题时需引入变量ⅹ:;其取值只能 是1或0。并令 当指派第讠人去完成第j项任务 0,当不指派第i去完成第j项任务

• 类似有：有n项加工任务，怎样指派到n台机 床上分别完成的问题；有n条航线，怎样指定 n艘船去航行问题……。对应每个指派问题，需 有类似表5-7那样的数表，称为效率矩阵或系 数矩阵，其元素cij＞0(i,j=1,2，…，n)表示 指派第i人去完成第j项任务时的效率(或时间、 成本等)。解题时需引入变量xij；其取值只能 是1或0。并令         = 当不指派第 人去完成第 项任务 当指派第 人去完成第 项任务 i j i j xi j 0, 1

当问题要求极小化时数学模型是: 目标函数m==∑∑cx l,j=1,2,…,n 约束条件∑x=1,1=12,…m③ (5-19) 1或0

当问题要求极小化时数学模型是： (5 19) 1 0 1, 1,2, , 1, 1,2, , min −        = = = = = =    或 约束条件 目标函数 i j j i j i i j i j i j i j x x i n x j n z c x   ① ② ③ ④

约束条件②说明第j项任务只能由1人去完成; 约束条件③说明第i人只能完成1项任务 满足约束条件②~④的可行解x;也可写成 表格或矩阵形式,称为解矩阵 如例7的一个可行解矩 0100 显然,解矩阵 0010 (x)中各行各 列的元素之和都 1000 是1。但这不是 0001 最优

显然，解矩阵 (xij)中各行各 列的元素之和都 是1。但这不是 最优。 • 约束条件②说明第j项任务只能由1人去完成； 约束条件③说明第i人只能完成1项任务。 • 满足约束条件②～④的可行解xij也可写成 表格或矩阵形式，称为解矩阵。 • 如例7的一个可行解矩             = 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 ij x

指派问题是0-1规划的特例,也是运输问题 的特例;即n=m,a:=b:=1 ·当然可用整数线性规划,0-1规划或运输 问题的解法去求解,这就如同用单纯形 法求解运输问题一样是不合算的。利用 指派问题的特点可有更简便的解法

指派问题是0-1规划的特例，也是运输问题 的特例；即n=m,aj =bi =1 • 当然可用整数线性规划，0-1规划或运输 问题的解法去求解，这就如同用单纯形 法求解运输问题一样是不合算的。利用 指派问题的特点可有更简便的解法

指派问题的最优解有这样性质,若从系数 矩阵(c;)的一行(列)各元素中分别减去该 行(列)的最小元素,得到新矩阵(;), 那么以(b;)为系数矩阵求得的最优解和用 原系数矩阵求得的最优解相同

• 指派问题的最优解有这样性质，若从系数 矩阵(cij)的一行(列)各元素中分别减去该 行(列)的最小元素，得到新矩阵(bij)， • 那么以(bij)为系数矩阵求得的最优解和用 原系数矩阵求得的最优解相同

利用这个性质,可使原系数矩阵变换为含有很 多0元素的新系数矩阵,而最优解保持不变, 在系数矩阵(b;)中,我们关心位于不同行不同 列的0元素,以下简称为独立的0元素 若能在系数矩阵(b;)中找出n个独立的0元素; 则令解矩阵(x:)中对应这n个独立的0元素的元 素取值为1,其他元素取值为0。将其代入目标 函数中得到z=0,它一定是最小 ·这就是以(b;)为系数矩阵的指派问题的最优解。 也就得到了原问题的最优解

• 利用这个性质，可使原系数矩阵变换为含有很 多0元素的新系数矩阵，而最优解保持不变， 在系数矩阵(bij)中，我们关心位于不同行不同 列的0元素，以下简称为独立的0元素。 • 若能在系数矩阵(bij)中找出n个独立的0元素； 则令解矩阵(xij)中对应这n个独立的0元素的元 素取值为1，其他元素取值为0。将其代入目标 函数中得到zb =0，它一定是最小。 • 这就是以(bij)为系数矩阵的指派问题的最优解。 也就得到了原问题的最优解

以下用例7来说明指派问题的解法 第一步:使指派问题的系数矩阵经变换,在各 行各列中都出现0元素。 (1)从系数矩阵的每行元素减去该行的最小元 系 (2)再从所得系数矩阵的每列元素中减去该列 的最小元素。 若某行(列)已有0元素,那就不必再减了。 例7的计算为

以下用例7来说明指派问题的解法。 第一步：使指派问题的系数矩阵经变换，在各 行各列中都出现0元素。 (1) 从系数矩阵的每行元素减去该行的最小元 素； (2) 再从所得系数矩阵的每列元素中减去该列 的最小元素。 若某行(列)已有0元素，那就不必再减了。 例7的计算为