指派问题运筹4-27.ppt

指派问题在实际中经常会遇到这样的问题,有n项不同的任务,需要n个人分别完成其中的一项,但由于任务的性质和各人的专长不同,因此各人去完成不同的任务的效率(或花费的时间或费用)也就不同。于是产生了一个问题:应指派哪个人去完成哪项任务,使完成n项任务的总效率最高(或所需时间最少),这类问题称为指派问题或分派问题。例7:有一份中文说明书,要分别译成英、日、德、俄四种文字,分别记作E、J、G、R,交与甲、乙、丙、,他们完成翻译不同语种的说明书所需的时间(h),使四个人分别完成这四项任务总时间为最小?任务人员EJGR甲215134乙1041415丙9141613丁78119一、指派问题的数学模型(一)举例这是一个标准型的指派问题类似有:有n项加工任务,怎样指派到n台机床上分别完成;有n条航线,怎样指定n艘船分别去航行…..等。对应每个指派问题,需有类似上表那样的数表,表中数据称为效率矩阵或系数矩阵,其元素cij>0(i,j=1,2,…n),表示指派第i人去完成第j项任务时的效率(或时间、成本等)效率矩阵或系数矩阵C=(cij)n×n=c11c12…c1nc21c22…c2n………………nC=(cij)4×4=2 15 13 410 4 14 159 14 16 137 8 11 9则该指派问题的数学模型为:求解题时通常需引入0-1变量:∑xij=1(i=1,2,3,4)表示第i人只能完成一项任务xij=1(j=1,2,3,4)表示第j项任务只能由一人去完成。满足约束条件的解称为可行解,可写成矩阵形式,叫作解矩阵。如本例的一个可行解矩阵(但不一定是最优解)指派问题的解矩阵应具有如下特点:(1)解矩阵(xij)中各行各列的元素之和都是1;(2)可行解(最优解)中恰含有4个非零元,即4个1;(3)可行解(最优解)矩阵中的1恰取于不同行不同列。可以看到指派问题既是0-1规划问题,也是运输问题,所以也可用整数规划,0-1规划,或运输问题的解法去求解。(二):设m个人被指派去做m件工作,规定每个人只做一件工作,每件工作只有一个人去做。已知第i个人去做第j件工作的的效率(时间或费用)为cij(i=…m;j=…m),并假设cij≥0。问应如何指派才能使总效率最高或总时间﹑总费用最低?设[cij]表示指派问题的效率矩阵,令则指派问题的数学模型一般形式为:xij为第i个人指派去做第j项任务;cij为第i个人为完成第j项任务时的工时消耗,或称效率;{cij}n—一般形式