[理学]5_05指派问题.ppt

第五节 指派问题 指派问题的数学模型 指派问题解的特点 指派问题的求解方法——匈牙利法 非标准形式的指派问题 * assignment problem 例、有四项任务需分派给甲、乙、丙、丁四个人去做，这四个人都能承担上述四项任务，但完成各项任务所需时间如下表所示。问应如何分派任务可使完成任务的总工时最少？ 9 11 9 7 丁 17 14 17 8 丙 16 14 7 12 乙 7 16 17 9 甲 D C B A 任务人员 一、指派问题的数学模型 解：设决策变量xij,i＝1,2,3,4; j＝1,2,3,4 x44 x43 x42 x41 丁 x34 x33 x32 x31 丙 x24 x23 x22 x21 乙 x14 x13 x12 x11 甲 D C B A 任务人员 x34 x33 x32 x31 丙 x44 x43 x42 x41 丁 x24 x14 D x23 x22 x21 乙 x13 x12 x11 甲 C B A ∑ =1 一项工作由一人做 ∑ =1 ∑ =1 ∑ =1 一人做一项工作 ∑ =1 ∑ =1 ∑ =1 ∑ =1 约束条件： 目标：min （总时间） 总时间 x44 x43 x42 x41 x34 x33 x32 x31 x24 x23 x22 x21 x14 x13 x12 x11 9 11 9 7 丁 17 14 17 8 丙 16 14 7 12 乙 7 16 17 9 甲 D C B A 任务人员 推广——指派问题的数学模型 有n项任务，恰好n个人承担，第i 人完成第j 项任务的花费(时间或费用等)为cij，如何分派使总花费最省？ 第j项工作由一个人做 第i人做一项工作 分派第i人做第j项工作 不分派第i人做第j项工作 二、指派问题的解的特点 可行解： 每行有且仅有一个1； 每列有且仅有一个1； 其余均为0。 例 三、指派问题的求解方法——匈牙利法 源于Konig 的两个定理 定理1—— 若从指派问题的系数矩阵C=(cij)n×n的某行(或某列)各元素分别加上或减去一个常数k，得到一个新矩阵C’=(c’ij) n×n ，则以C’和C为系数矩阵的两个指派问题有相同的最优解 。 证明分析： 指派问题模型1： 效率矩阵C 若C=(cij)n×n的第一行各元素分别加上一个常数k，得到一个新矩阵C’=(c’ij) n×n 指派问题模型2： 效率矩阵C’ 与模型1相比： 约束相同； 目标相差一个常数k。 因此最优解相同。 问：定理1有什么用处？ 一个特例—— 设某个指派问题的效率矩阵 特点：0元素位于不同行不同列 目标值z＝0。因cij≥0， 它必为最优解 定理1的用处—— 尽管一般的效率矩阵中不会有这样的位于不同行不同列的0元素，而定理1则给出了可以将一般的效率矩阵转化成这样矩阵的理论依据。 例 -1 -2 -3 -4 问：如何寻找位于不同行不同列的0元素？ 又称独立0元素 定理2—— 若矩阵A中的元素可分为“0”和“非0”两部分，则覆盖0元素的最少直线数等于位于不同行不同列的0元素的最多个数。 只需在矩阵A中寻找覆盖0元素的最少直线数。 匈牙利法求解指派问题举例1： 例：求解指派问题，效率矩阵 解： 1 变换系数矩阵，使其每行每列都出现0元素。首先每行减去该行最小数，再每列减去该列最小数。 -7 -7 -8 -7 -4 (cij’) 2 寻找独立0元素 ①从第一行开始，若该行只有一个0元素，则给这个0元素加O；同时作一直线覆盖该列元素。若该行无0元素或者有两个及以上0元素（已被覆盖的不计在内），则转下行，直到最后一行为止 表示对这行所代表的人 ，只有一种任务可分派。 表示这列所代表的任务已分派完，不必再考虑别人了。 ②从第一列开始，若该列只有一个0元