运筹学匈牙利法PPT课件

01整数规划是一种特殊形式的整数规划，这时的决策变量xi只取两个值0或1，通常用来表示逻辑性选择的决策。一般的解法为隐枚举法。,例求解下列01规划问题,01整数规划的应用,8,3,-2,5,0,一、01整数规划枚举法,8,首先，找到一个可行解，并计算其目标函数值；然后，以其目标值作为一个过滤条件，优于其值的再判断约束条件，直到找到最优解。,二、01整数规划隐枚举法,8,6,1,3,3,-2,5,0,8,思考：如果将目标函数变为下式会改进吗？,三、指派问题的匈牙利法,指派问题（TheAssignmentProblem）,1、指派问题的形式表述给定了一系列所要完成的任务（tasks）以及一系列完成任务的被指派者（assignees），所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务,2、指派问题的假设被指派者的数量和任务的数量是相同的每一个被指派者只完成一项任务每一项任务只能由一个被指派者来完成每个被指派者和每项任务的组合有一个相关成本目标是要确定怎样进行指派才能使得总成本最小,设n个人被分配去做n件工作，每人只能完成一项任务，每项任务只能由一人完成。已知第i个人去做第j件工作的的效率为Cij(i=1.2n;j=1.2n)并假设Cij0。问应如何分配才能使总效率（时间或费用）最高？,3、指派问题模型（TheModelforAssignmentProblem）,典型问题,例1：有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一项工作。,问：如何分配，能使所需的总时间最少？,建立模型,设xij=,1,0,若第i项工作交与第j个人完成,若第i项工作不交与第j个人完成,译英文：,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,乙：,x12+x22+x32+x42=1,丙：,x13+x23+x33+x43=1,丁：,x14+x24+x34+x44=1,xij=0或1(i=1,2,3,4;j=1,2,3,4),4、指派问题的匈牙利解法,2,4,9,7,第1步：变换指派问题的系数矩阵（cij），使各行各列中都出现0元素,(1)从（cij）的每行元素都减去该行的最小元素；,(2)再从所得新系数矩阵无零元素的列中减去该列的最小元素。,4,2,在变化后的效率矩阵中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。,第2步：进行试指派，即确定独立零元素,（2）若独立零元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到。若m人数时：假想人数，使得与工作数能够匹配,对应的效率设定为0值。,人数和工作数不等的指派问题,（2）一个人可做几项工作的指派问题,A1可同时做三项工作,（3）某项工作一定不能由某人做的指派问题,A1不能做B4;A3不能做B3,（4）若目标函数为求maxz的处理(如效益）,maxz=-min(-z)=-min(z),等价于求解minz=(-aij)xij,i=1j=1,nn,最大化指派问题,最大化指派问题,学生A，B，C，D的