清华大学出版社：《运筹学》课程教学资源（PPT课件讲稿，教材第三版）第5章 整数线性规划 第5节 指派问题

min 2151342 行列都有 10414154 C, 零元素 91416139 78119)7 013112 01370 6010116069 05740532 0142)(0100 42 min

行列都有 零元素 4 2 min ( ) 0 1 0 0 0 5 3 2 6 0 6 9 0 13 7 0 0 1 4 2 0 5 7 4 6 0 10 11 0 13 11 2 7 9 4 2 7 8 11 9 9 14 16 13 10 4 14 15 2 15 13 4 ( ) min i j i j b c =               →               →               =

第二步:进行试指派,以寻求最优解。为 此,按以下步骤进行。 经第一步变换后,系数矩阵中每行每列都已有 了0元素;但需找出n个独立的0元素。若能找 出,就以这些独立0元素对应解矩阵(x1)中的 元素为1,其余为0,这就得到最优解。当n较 小时,可用观察法、试探法去找出n个独立0元 素。若n较大时,就必须按一定的步骤去找, 常用的步骤为:

第二步：进行试指派，以寻求最优解。为 此，按以下步骤进行。 • 经第一步变换后，系数矩阵中每行每列都已有 了0元素；但需找出n个独立的0元素。若能找 出，就以这些独立0元素对应解矩阵(xij)中的 元素为1，其余为0，这就得到最优解。当n较 小时，可用观察法、试探法去找出n个独立0元 素。若n较大时，就必须按一定的步骤去找， 常用的步骤为：