4指派问题

4指派问题一、模型njixnjxnixxczijniijnjijninjijij,,1,10,,11,,11min1111或二、匈牙利算法(一)算法思想对价值系数矩阵C，将它的某一行(或某一列)的各元素都减去一个常数k，得到的新的价值系数矩阵，构成一个新的分派问题，则这个新问题的最优解与原分派问题的最优解相同，目标函数相差常数k。若mn，转下步。(二)算法步骤1、转换系数矩阵，在各行各列中都出现零元素(1)每行各元素减去该行最小元素；(2)每列各元素减去该列最小元素。2、试分派n较小时，可用观察法、试探法找n个独立元素，n较大时，用下法(1)从只有一个0元素的行(列)开始，对0元素加框，化去其所在列(行)的其它0元素，记作(2)反复进行(1)，直到不再有0元素可圈和划去。(3)当同行(列)有两个或两个以上0元素时，试探法。1ijx(4)若元素的数目m=n，已得最优解，即令元素对应其它元素对应。0ijx91187131614915144104131522497241047501110062111300042282479422814331221443312214zcccczxxxx013706069053201003、以最少的直线划去所有0元素(1)对没有加的行打(2)对已打的行中所有含的0元素列打(3)再对打有的列中含的0元素行打(4)对打的列和未打的行划直线(5)重复以上步骤，直至全部完成n较小时，可用观察法，n较大时，用下法00未覆盖的列覆盖的列未覆盖的行覆盖的行-不变不变+-+即所有未被覆盖的元素都减去，单重覆盖(一条线)的元素不变，双重覆盖(同时被纵横两条线覆盖)的元素增加。(3)转24、修改价值系数c(1)求出未被覆盖部分中最小元素(2)将未覆盖行的元素都减去，将各覆盖列的元素都加上例1568453466155798675767462841552124012355000243120215240612401235500024312021524060130023560002531203141305例2：六项任务由四个工厂担任，每个工厂可担任一至两项任务，并知各个工厂担任各项任务的费用如下，问应如何分配任务，使总费用最少。373655618427275346648732解每个工厂可担任两项任务，可设想每个工厂有两个分厂，于是问题变为由八个单位担任六项任务的分派问题3736550037365500618427006184270027534600275346006487320064873200结论任务指派例3有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如下表，问如何分配任务使完成四项任务的总工时耗费最少？1,0,,2,11,,2,11)(min1111ijmiijmjijmimjijijxmjxmixxaxf任务工时ABCD人员人员甲109781乙58771丙54651丁23451任务1111第一步：变换效率矩阵，使每行每列至少有一个零–行变换：找出每行最小元素，从该行各元素中减去之–列变换：找出每列最小元素，从该列各元素中减去之2210020112300023321012012230)1(023543)2(56)4(5778)5(8)7(910换变列换变行第二步：检查覆盖所有零元素的直线是否为m条划线规则1、逐行检查，若该行只有一个未标记的零，对其加框标记，将框标记元素同行同列上其它的零打上叉标记。若该行有二个以上未标记的零，可暂不标记，转下一行检查，直到所有行检查完；32003200032103211020102001220122逐逐行列检检查查221*0*02)0(1123)0(*0)0(2311000202012000241答：最优分配方案为x13=x21=x34=x42=1，其余为0，即甲C，乙A，丙D，丁B，OBJ=20420002102020001142000210202000114200021020200011逐行逐列标记最优解关于匈牙利算法的适用条件•要求所有aij0–若某些aij0，则令bij=Max(aij)-aij进行变换，使所有bij0•目标函数为min型–对于max型目标函数，将效率矩阵中所有aij反号，则等效于求min型问题；再利用上述方法进行变换，使所有bij0，即则可采用匈牙利法特殊问题切记•若人数与工作数不等，要求每人只完成一项工作，则用“0”来补全空位。•若一个人可以做几件事情，则可转化为相同的“几个人”来接受指派，其费用系数相同。•若某人不能从事某项工作，则将其价值系数设为M。•若原问题求利润的最大值，则先将效率矩阵变换（即从中找出最大值，减去所有价值系数，形成新的效率矩阵），再按照匈牙利法求解。从A、B、C、D、E5人中挑选4人去完成4项工作，已知每人完成各项工作的费用如下表。规定每项工作只能由其中一人单独完成，而每人最多只能承担其中一项工作，又假定A必须保证分配一项工作，D因为某种原因不能承担第4项工作，在上述条件下，如何分配工作，使完成这4项工作的费用最少？人工作ABCDEⅠ1023159Ⅱ5101524Ⅲ15514715Ⅳ20151368课堂练习：