2019/6/20 匈牙利解法的一般步骤 指派问题(assignment problem) 以例3-2说明步： 指(assignment problem) 151 013112 01370 0101 0101 06 c'a 0574 53 811 0142 0142 604 指派问题(assignment problem) 指派问题(assignment problem) 以例32说弱步雕 食 0001 0100 () 000 比时如通0元素的 个数口 =n=4,所以得到最优解 0010 A 指派问题(assignment problem) 非标准形式的指派问题 匈牙利解法的一般步臻 其方法幕在未劫言雄兰 用中，常会到各种 的元素中找出 元。松后在打号行各元 式，然后再用1 都减去这一最小元素，而在打号列的各元豪都加上 中最大 素为m 这一最小元素，以保正原来的0元素不变。这样得到 新系数矩阵（其最优解和原问题相同）。若得到门个 数立的0元素，则已得最优解，否则重复该步票继续 变换系数矩阵。 9 2019/6/20 9 49 以例3-2说明步骤： 2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9 0 13 11 2 6 0 10 11 0 5 7 4 0 1 4 2 2 4 9 7 min （ cij ）= 匈牙利解法的一般步骤 50 指派问题（assignment problem） 匈牙利解法的一般步骤 以例3-2说明步骤： 0 13 11 2 6 0 10 11 0 4 7 4 0 1 4 2 min 0 0 4 2 0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0 = （ c’ij ） 指派问题（assignment problem） 51 以例3-2说明步骤 0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0 此时加圈 0 元素的个数 m = n = 4，所以得到最优解 指派问题（assignment problem） 52 匈牙利解法的一般步骤 以例3-2说明步骤 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 （ xij ）= 指派问题（assignment problem） 53 匈牙利解法的一般步骤 继续变换系数矩阵。其方法是在未被直线覆盖 的元素中找出一个最小元素。然后在打√号行各元素 都减去这一最小元素，而在打√号列的各元素都加上 这一最小元素，以保证原来的 0 元素不变。这样得到 新系数矩阵（其最优解和原问题相同）。若得到 n 个 独立的 0 元素，则已得最优解，否则重复该步骤继续 变换系数矩阵。 指派问题（assignment problem） 54 在实际应用中，常会遇到各种非标准形式的制派问题。一般的 处理方法是先将其转化为标准形式，然后再用匈牙利法求解。 1. 最大化指派问题——设最大化指派问题系数矩阵 C = （ cij ） ， 其中最大元素为 m 。令矩阵 B = （ bij ）= （ m - cij ），则 以 B 为系数矩阵的最小化指派问题和以 C 为系数矩阵的最大 化指派问题有相同最优解。 2. 人数和事数不等的指派问题——若人少事多，则添加一些虚拟 的“人”，其费用系数取 0 ，若人多事少，则添加一些虚拟的 “事”，其费用系数取 0 。 非标准形式的指派问题