运筹学 (第三版) 《运筹学》教材编写组 第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的计算为