运筹学匈牙利法.ppt

1、01 整数规划是一种特殊形式的整数规划，这时的决策变量xi 只取两个值0或1， 通常用来表示逻辑性选择的决策。一般的解法为隐枚举法。,例 求解下列01 规划问题,01 整数规划的应用, 8, , , , 3, -2, 5, 0,一、01 整数规划枚举法, 8,首先，找到一个可行解，并计算其目标函数值；然后，以其目标值作为一个过滤条件，优于其值的再判断约束条件，直到找到最优解。,二、01 整数规划隐枚举法, 8,6,1,3,3,-2, 5, 0, 8,思考：如果将目标函数变为下式会改进吗？,三、指派问题的匈牙利法,指派问题（The Assignment Problem）,1、指派问题的形式表述

2、给定了一系列所要完成的任务（tasks）以及一系列完成任务的被指派者（assignees），所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务,2、指派问题的假设 被指派者的数量和任务的数量是相同的 每一个被指派者只完成一项任务 每一项任务只能由一个被指派者来完成 每个被指派者和每项任务的组合有一个相关成本 目标是要确定怎样进行指派才能使得总成本最小,设n 个人被分配去做n 件工作，每人只能完成一项任务，每项任务只能由一人完成。已知第i 个人去做第j 件工作的的效率为Cij(i=1.2n;j=1.2n)并假设Cij 0。问应如何分配才能使总效率（ 时间或费用）最高？,3、指派问题模型 （

3、The Model for Assignment Problem）,典型问题,例1：有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一项工作。,问：如何分配，能使所需的总时间最少？,建立模型,设 xij=,1,0,若第i项工作交与第j个人完成,若第i项工作不交与第j个人完成,译英文：,x11+ x12 + x13 + x14 =1,译日文：,x21+ x22 + x23 + x24 =1,译德文：,x31+ x32 + x33 + x34

4、=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,在变化后的效率矩阵中找尽

5、可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。,第2步：进行试指派，即确定独立零元素,（2）若独立零元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到。若m n, 则转入下一步。,例2 有甲、乙、丙、丁四个工人，要分别派他们完成四乡不同的任务，分别记作A、B、C、D。他们完成各项任务所需时间如下表所示，问如何分派任务，可使总时间最少？,第1步，变换系数矩阵：,-5,第2步，确定独立零元素,找到 3 个独立零元素， 但 m = 3 n = 4,求解过程如下,第3步，作最少的直线覆盖所有零元素：,(5)对没有打号

6、的行画横线，有打号的列画纵线，这就得到覆盖所有零元素的最少直线数,(1)对没有独立零元素的行打号；,(2)对已打号的行中所有含划掉零元素的列打号；,(3)再对打有号的列中含独立零元素的行打号；,(4)重复(2)，(3)直到得不出新的打号的行、列为止；,第4步：在没有被直线覆盖的所有元素中找出最小元素，然后将所在行（或列）都减去这最小元素；,在出现负数的列（或行）都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第2步。,-5,5、指派问题的变形 Variants of Assignment Problem,任务比被指派者多 被指派者比要完成的任务多 有一些被指派者并不能进行某一些的任务 每个被指派者可以同时被指派给多个的任务,（1）人数与工作数不等的处理,当人数工作数时：假想工作数，使得与人数能够匹配, 对应的效率设定为0值。,当工作数人数时：假想人数，使得与工作数能够匹配, 对应的效率设定为0值。,人数和工作数不等的指派问题,（2）一个人可做几项工作的指派问题,A1可同时做三项工作,（3）某项工作一定不能由某人做的指派问题,A1不能做B4; A3不能做B3,（4）若目标函数为求max z的处理(如效益）, max z= - min (-z ) = - min ( z),等价于求解 min z =(-aij)xij,i=1