《运筹学匈牙利法ppt课件.ppt》由会员分享，可在线阅读，更多相关《运筹学匈牙利法ppt课件.ppt（26页珍藏版）》请在三一办公上搜索。
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、指派问题模型（The
3、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 =1,译
4、俄文：,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,任务比被指派者多被指派者比要完成的任务多有一些被指派者并不
7、能进行某一些的任务 每个被指派者可以同时被指派给多个的任务,（1）人数与工作数不等的处理,当人数工作数时：假想工作数，使得与人数能够匹配, 对应的效率设定为0值。,当工作数人数时：假想人数，使得与工作数能够匹配, 对应的效率设定为0值。,人数和工作数不等的指派问题,（2）一个人可做几项工作的指派问题,A1可同时做三项工作,（3）某项工作一定不能由某人做的指派问题,A1不能做B4;A3不能做B3,（4）若目标函数为求max z的处理(如效益）, max z= - min (-z ) = - min ( z),等价于求解 min z =(-aij)xij,i=1j=1,n n,最大化指派问题,最大化指派问题,学生A，B，C，D的各门成绩如下表，将该四名学生派去参加各门课的单项竞赛。由于竞赛同时举行，故每人只能参加一项，若以他们的成绩作为选派依据，应如何分派最为有利？,练习题,
