运筹学匈牙利法

0－1整数规划是一种特殊形式的整数规划，这时的决策变量xi只取两个值0或1，通常用来表示逻辑性选择的决策。一般的解法为隐枚举法。例求解下列0－1规划问题10,,(4)64(3)3(2)44(1)22523max3213221321321321或xxxxxxxxxxxxxxxxZ0－1整数规划的应用√√√√8√×√√××√√√×√√√√√√3√√√√-2√√√√5√√√√0x1.x2.x3满足约束条件（是∨否×）Z值(1)(2)(3)(4)(0.0.0)(0.0.1)(0.1.0)(1.0.0)(0.1.1)(1.0.1)(1.1.0)(1.1.1)一、0－1整数规划——枚举法10,,(4)64(3)3(2)44(1)22523max3213221321321321或xxxxxxxxxxxxxxxxZ√√√√8首先，找到一个可行解，并计算其目标函数值；然后，以其目标值作为一个过滤条件，优于其值的再判断约束条件，直到找到最优解。二、0－1整数规划——隐枚举法√√√√86133-2√√√√5√√√√0x1.x2.x3满足约束条件（是∨否×）过滤条件(1)(2)(3)(4)(0.0.0)(0.0.1)(0.1.0)(1.0.0)(0.1.1)(1.0.1)(1.1.0)(1.1.1)10,,(4)64(3)3(2)44(1)22523max3213221321321321或xxxxxxxxxxxxxxxxZ√√√√8312532maxxxxZ思考：如果将目标函数变为下式会改进吗？三、指派问题的匈牙利法指派问题（TheAssignmentProblem）1、指派问题的形式表述给定了一系列所要完成的任务（tasks）以及一系列完成任务的被指派者（assignees），所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务2、指派问题的假设被指派者的数量和任务的数量是相同的每一个被指派者只完成一项任务每一项任务只能由一个被指派者来完成每个被指派者和每项任务的组合有一个相关成本目标是要确定怎样进行指派才能使得总成本最小设n个人被分配去做n件工作，每人只能完成一项任务，每项任务只能由一人完成。已知第i个人去做第j件工作的的效率为Cij(i=1.2…n;j=1.2…n)并假设Cij≥0。问应如何分配才能使总效率（时间或费用）最高？)..2.1,1(0)..2.1(1)..2.1(1min1111njixnjxnixxcZijniijnjijninjijij或3、指派问题模型（TheModelforAssignmentProblem）项任务个人取完成第不分配第项任务个人取完成第分配第ji0ji1ijx典型问题例1：有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一项工作。问：如何分配，能使所需的总时间最少？甲乙丙丁工作人译英文译日文译德文译俄文2109715414813141611415139建立模型设xij=10若第i项工作交与第j个人完成若第i项工作不交与第j个人完成4141minijijijxcf译英文：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=1xij=0或1(i=1,2,3,4;j=1,2,3,4)甲乙丙丁工作人译英文译日文译德文译俄文21097154148131416114151394、指派问题的匈牙利解法9118713161491514410413152241047501110062111302497第1步：变换指派问题的系数矩阵（cij），使各行各列中都出现0元素(1)从（cij）的每行元素都减去该行的最小元素；(2)再从所得新系数矩阵无零元素的列中减去该列的最小元素。4200102350960607130在变化后的效率矩阵中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。第2步：进行试指派，即确定独立零元素（1）从有唯一的零元素的行或列开始确定独立零元素，并用表示，并划掉其所在行或列的其他零。直到尽可能多的零元素都被圈出和划掉为止。0（2）若独立零元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到。若mn,则转入下一步。0100000100101000ijx911871316149151441041315200102350960607130例2有甲、乙、丙、丁四个工人，要分别派他们完成四乡不同的任务，分别记作A、B、C、D。他们完成各项任务所需时间如下表所示，问如何分派任务，可使总时间最少？任务人员ABCD甲67112乙4598丙31104丁5982第1步，变换系数矩阵：2142289541013895421176)(ijc06733902451009540173340240100454-5第2步，确定独立零元素找到3个独立零元素，但m=3n=4求解过程如下第3步，作最少的直线覆盖所有零元素：(5)对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有零元素的最少直线数(1)对没有独立零元素的行打√号；√(2)对已打√号的行中所有含划掉零元素的列打√号；√(3)再对打有√号的列中含独立零元素的行打√号；(4)重复(2)，(3)直到得不出新的打√号的行、列为止；√第4步：在没有被直线覆盖的所有元素中找出最小元素，然后将所在行（或列）都减去这最小元素；017334024010045410623402401013430062440250100343在出现负数的列（或行）都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第2步。2142289541013895421176)(ijc06733902451009540173340240100454-5√√106234024010134300624402501003430100001000011000ijx√5、指派问题的变形VariantsofAssignmentProblem任务比被指派者多被指派者比要完成的任务多有一些被指派者并不能进行某一些的任务每个被指派者可以同时被指派给多个的任务（1）人数与工作数不等的处理当人数工作数时：假想工作数，使得与人数能够匹配,对应的效率设定为0值。当工作数人数时：假想人数，使得与工作数能够匹配,对应的效率设定为0值。人数和工作数不等的指派问题1012966177118129614291215784101296617711812961429121578400000（2）一个人可做几项工作的指派问题78329824763195232154321BBBBBAAA31952319527832982476319525432111321BBBBBAAAAAA1可同时做三项工作（3）某项工作一定不能由某人做的指派问题452782946178298247639525432154321BBBBBAAAAA452782946178298247639525432154321MMAAAAABBBBBA1不能做B4;A3不能做B3（4）若目标函数为求maxz的处理(如效益）∵maxz=-min(-z)=-min(z)∴等价于求解minz=∑∑(-aij)xiji=1j=1nn最大化指派问题610129610617711781296101429121215784最大化指派问题最大值617101712179176171017617171771711177178171217917617101714172179171217121715177178174171175811711010610958117315855210913最小化指派问题学生A，B，C，D的各门成绩如下表，将该四名学生派去参加各门课的单项竞赛。由于竞赛同时举行，故每人只能参加一项，若以他们的成绩作为选派依据，应如何分派最为有利？练习题数学物理化学英语A89926881B87886578C95708572D75788996