2019/6/20 3.4指派间题(assignment problem) 例32意立横遥 看第项工作交与个人完成 指深问题的标准形式及其数学棋型 【。无第项工作不交与衡个人完城 指派问题的标准形式（以人和事为例）是： 有n个人和n件事，已知第i人做第j 译英文 甲：++ Cj=1, 这件率的总费用最少.如例32 0域1-234P23, 公包 A幻 一般模型 匈牙利解法 潮深同的标准形式，令 标准的指派问题是一类特的01整数规划问 大-日深个光盘务 题，可以用多种相应的解法来求解。但是， 都没有充分利用指派问愿的特殊性质来有效减少计算 量，1955年，库愿(W.W.Kuhn)利用甸牙利数学家 minz=ic 康尼格(D.K6nig)的关于矩阵中独立零元素的定理， 1,j=1,2,,n 提出了指派问愿的一种解法，由此，习惯上称之为图 牙利解法。 公 Ag兰 匈牙利解法 匈牙利解法的一般步骤 步课一：变换系数矩阵。使其年行及年列至少有一 甸牙利解法的关键是利用了指派问题最优解的 个零元素，同时不出现负元素。 如下性质： 步硬二：进行试指派，即确定独立零元素。 若从指派问题的系数矩阵C=(c1)nXn的 步骤三：继线变换系数矩阵，然后返回步骤二， 某行（或某列）各元素分别减去一个常囊k,得到 个新的系数矩阵C'=(c,)则以C和C为系数矩 阵的两个指派问愿有相同的最优解。 A △g 82019/6/20 8 43 指派问题的标准形式及其数学模型 指派问题的标准形式（以人和事为例）是： 有 n 个人和 n 件事，已知第 i 人做第 j 事 的费用为 Cij（i，j = 1，2，…，n），要求确 定人和事之间的一一对应的指派方案，使完成 这件事的总费用最少。如例3-2. 3.4 指派问题（assignment problem） 例3-2 建立模型： 设 xij= 1 0 译英文： 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 =1 xij =0或1 (i=1,2,3,4; j=1,2,3,4) Min z= aijxij (aij---效率) i=1j=1 4 4 若第i项工作交与第j个人完成 若第i项工作不交与第j个人完成 45 一般模型 指派问题的标准形式，令 1 当指派第 i 人完成第 j 项任务 0 当不指派第 i 人完成第 j 项任务 xij = min z = ∑∑cijxij ∑xij = 1， j = 1，2，…，n ∑xij = 1， i = 1，2，…，n xij = 1 或 0 46 匈牙利解法 标准的指派问题是一类特殊的 0-1 整数规划问 题，可以用多种相应的解法来求解。但是，这些方法 都没有充分利用指派问题的特殊性质来有效减少计算 量。1955年，库恩（W.W.Kuhn）利用匈牙利数学家 康尼格（D.König）的关于矩阵中独立零元素的定理， 提出了指派问题的一种解法，由此，习惯上称之为匈 牙利解法。 47 匈牙利解法的关键是利用了指派问题最优解的 如下性质： 若从指派问题的系数矩阵 C = （ cij ）n×n 的 某行（或某列）各元素分别减去一个常数 k ，得到一 个新的系数矩阵C’ = （ c’ij ）则以 C 和 C’ 为系数矩 阵的两个指派问题有相同的最优解。 匈牙利解法 48 步骤一： 变换系数矩阵。使其每行及每列至少有一 个零元素，同时不出现负元素。 步骤二： 进行试指派，即确定独立零元素。 步骤三： 继续变换系数矩阵，然后返回步骤二。 匈牙利解法的一般步骤