46.1清华算法 定理1如果从效率矩阵{umm中每行元素分别减去一个常数n;, 从每列元素分别减去一个常数v,所得新的效率矩阵bmm 的任务分配问题的最优解等价于原问题的最优解。 证明:略 定理2若方阵中一部分元素为零,一部分元素非零,则覆盖方 阵内所有零元素的最少直线数等于位于不同行、不同列的零 元素的最多个数 证明:略 清华算法的基本思路: ·根据定理1变换效率矩阵,使矩阵中有足够多的零。若 矩阵中存在m个不同行不同列的零,就找到了最优解 若覆盖变换后的效率矩阵零元素的直线少于m条,就尚 未找到最优解,设法进一步变换矩阵,增加新的零9 4.6.1 清华算法 定理 1 如果从效率矩阵{aij}mm中每行元素分别减去一个常数 ui， 从每列元素分别减去一个常数 vj ，所得新的效率矩阵{bij}mm 的任务分配问题的最优解等价于原问题的最优解。 证明：略 定理 2 若方阵中一部分元素为零，一部分元素非零，则覆盖方 阵内所有零元素的最少直线数等于位于不同行、不同列的零 元素的最多个数。 证明：略 清华算法的基本思路： • 根据定理 1 变换效率矩阵，使矩阵中有足够多的零。若 矩阵中存在 m 个不同行不同列的零，就找到了最优解 • 若覆盖变换后的效率矩阵零元素的直线少于m 条，就尚 未找到最优解，设法进一步变换矩阵，增加新的零