图 图11 由图10的最短增广链,可对应地作出定向图11,容易求出图11S到t的最短定向路为 0D-7 ⊙8B89A80t 相应地,图10中的最短增广链为: 假如求上述最短定向路的计算量为o(n3),则求出最优匹配的计算量为o(n) 解分配问题亦可在表上进行,采用标号法求增广链和最大匹配,然后通过简单的矩阵变换, 逐步找出最优分配,这种形式的解法叫作匈牙利方法(详见管梅谷等,线性规划) 还可以用下面将介绍的分枝定界法、最小调整法求最优匹配。 还有二次分配问题。例如,对厂址和厂房要求一个总的分配(一对一),使得厂址之间的距离 各乘以相应工厂的运输量所得的和最小。 此问题很难解决,无有效算法,也几乎无有效的启发式算法可以利用。 (Ⅲ)排序问题和分枝定界法 在许多可能的顺序中找一个最优顺序,分配加上加工顺序的限制,就成排序问题,如A与B 两车床加工n件产品,加工时间分别为t:(A)和t(B),i=1,2,…,n。A先加工,然后B再加工,问 如何安排所用时间最少? 由于加工顺序是A先B后,故应尽量减少B的等待时间,因此不难理解其最优方案应是每次 从{t;(A),t;(B)}中取出一个最小值,若它属于{t:(A)},则应排在最先加工,若属于{t:(B)}, 则应排在最后加工,然后对已确定加工顺序的数据从{t(A),t1(B)}中去掉,在余集上重复上述过 程,依次排列,便得最优排序,此问题亦可用动态规划的方法求解。 上述是2×n的同顺序排序问题,对于一般的m×n(m>3)的同顺序排序问题以及不同顺序的排 序问题,要用“分枝定界法”求解,现将该方法简介如下: 分枝定界法 欲求 nIn f(X) X∈A 考虑求 min f(X) (3) X∈B 其中要求A≌B,称(3)为(2)的松弛问题,它要好解些。若(3)的最优解XB∈A,则X=XB;13 A B C D 1 2 3 4 1 4 3 2 A B C D 1 2 3 4 1 4 3 2 8 9 6 8 8 6 7 -8 -6 9 -8 8 -6 -7 0 0 0 0 S t 图 10 图 11 由图 10 的最短增广链，可对应地作出定向图 11，容易求出图 11S 到 t 的最短定向路为： S 0 D -7 4 8 B -8 3 9 A -8 1 0 t 相应地，图 10 中的最短增广链为： D 4 B 3 A 1 假如求上述最短定向路的计算量为 3 o n( ) ,则求出最优匹配的计算量为 4 o n( )。 解分配问题亦可在表上进行，采用标号法求增广链和最大匹配，然后通过简单的矩阵变换， 逐步找出最优分配，这种形式的解法叫作匈牙利方法（详见管梅谷等[13]，线性规划） 还可以用下面将介绍的分枝定界法、最小调整法求最优匹配。 还有二次分配问题。例如，对厂址和厂房要求一个总的分配（一对一），使得厂址之间的距离 各乘以相应工厂的运输量所得的和最小。 此问题很难解决，无有效算法，也几乎无有效的启发式算法可以利用。 （Ⅲ）排序问题和分枝定界法 在许多可能的顺序中找一个最优顺序，分配加上加工顺序的限制，就成排序问题，如 A 与 B 两车床加工 n 件产品，加工时间分别为 ti(A)和 ti(B)，i＝1,2,…,n。A 先加工，然后 B 再加工，问 如何安排所用时间最少？ 由于加工顺序是 A 先 B 后，故应尽量减少 B 的等待时间，因此不难理解其最优方案应是每次 从｛ti(A)，ti(B)｝中取出一个最小值，若它属于｛ti(A)｝，则应排在最先加工，若属于｛ti(B)｝， 则应排在最后加工，然后对已确定加工顺序的数据从｛ti(A)，ti(B)｝中去掉，在余集上重复上述过 程，依次排列，便得最优排序，此问题亦可用动态规划的方法求解。 上述是 2×n 的同顺序排序问题，对于一般的 m×n(m>3)的同顺序排序问题以及不同顺序的排 序问题，要用“分枝定界法”求解，现将该方法简介如下： 分枝定界法 欲求 min ( ) f X X A  （2） 考虑求 min ( ) f X X B  （3） 其中要求 A  B，称（3）为（2）的松弛问题，它要好解些。若（3）的最优解 o X A B  ，则 o o X X A B = ；