§3数规划的应用(3) 、指派问题 有n项不同的任务,恰好n个人可分别承担这些任务,但由于每人特长不同,完成各 项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务,怎样把n项任务指派 给n个人,使得完成n项任务的总的效率最高,这就是指派问题。 例6.有四个工人,要分别指派他们完 工作 成四项不同的工作,每人做各项工作所消 工人 18 耗的时间如右表所示,问应如何指派工作, 才能使总的消耗时间为最少。 甲乙丙丁 16 19 解:引入0—1变量x1,并令 x=1(当指派第i人去完成第j项工作时)或0(当不指派第i人去完成第j项工作时) 这可以表示为一个0-1整数规划问题 Minz=15x1+18x12+21x13+24x14+19x21+23x2+22x23+18x2+26x31+17x32+16x3+19x34+19x41 +21x42+23x43+17x4 s.t.x1+x12+x3+x14=1(甲只能干一项工作 x2+x2+x23+x24=1(乙只能干一项工作 x31+x2+x3+x34=1(丙只能干一项工作 x1+x42+x43+x4=1(丁只能干一项工作 x1+x21+x31+x41=1(A工作只能一人干 x12+x2+x2+x42=1(B工作只能一人干 x13+x23+x3+x43=1(C工作只能一人干 x14+x2+x34+x4=1(D工作只能一人干 x1;为0--1变量, ***求解可用《管理运筹学》软件中整数规划方法。例6．有四个工人，要分别指派他们完 成四项不同的工作，每人做各项工作所消 耗的时间如右表所示，问应如何指派工作， 才能使总的消耗时间为最少。 解：引入0—1变量 xij，并令 xij = 1(当指派第 i人去完成第j项工作时)或0（当不指派第 i人去完成第j项工作时)． 这可以表示为一个0--1整数规划问题： Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x44 s.t. x11+ x12+ x13+ x14= 1 (甲只能干一项工作) x21+ x22+ x23+ x24= 1 (乙只能干一项工作) x31+ x32+ x33+ x34= 1 (丙只能干一项工作) x41+ x42+ x43+ x44= 1 (丁只能干一项工作) x11+ x21+ x31+ x41= 1 ( A工作只能一人干) x12+ x22+ x32+ x42= 1 ( B工作只能一人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干) xij 为0--1变量，i,j = 1,2,3,4 * * * 求解可用《管理运筹学》软件中整数规划方法。 §3整数规划的应用(3) 工作 工人 A B C D 甲 15 18 21 24 乙 19 23 22 18 丙 26 17 16 19 丁 19 21 23 17 三、指派问题 有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由于每人特长不同，完成各 项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把 n 项任务指派 给 n 个人，使得完成 n 项任务的总的效率最高，这就是指派问题