§4蓬数规划的分枝定界法(1) 问题(A)Minz=c1x1+c2x2+.+cnx 记问题(B)为去掉整数约束的问题(A) s.t. auX+an x,+...+ain,=b a21x1+a22×x2+…+a2Xn=b2 mi,+am2 x2+.+amn,= b x2,….,xn≥0为整数 在分枝定界法过程中求解问题(B),应有以下情况之一: ①(B)无可行解,则(A)亦无可行解,停止对此问题的计算 ②(B)有最优解,并满足整数约束,即同时为(A)的最优解,那么z同时是当前问题(A)最优 目标值的上界 和下界。停止对这个问题的计算; ③(B)有最优解ⅹ及最优值z但不符合整数条件。这时得到当前问题(A)最优目标值的一个下 界z=z,于是通过以下判断可对此问题进一步计算。 分枝定界法的计算过程 1、对原问题(A),求解松弛问题(B)。根据上面分析,若出现情况①,②则停机。若情况③ 发生,得到(A问题最优值的一个下界。我们任找(A)问题的一个可行解,那么对应的目标 函数值是(A)最优值的一个上界z。即得到z<z<z。(注:找(A问题的可行解往往需 要较大的计算量,这时可简单记z=+∞,而先不必费很大力量去求较好的上界。从以下 分析可以看到,找到一个好的最优目标值上界,将对算法的快速求得目标非常有效。), 转2,进行以下一般步的迭代;§4整数规划的分枝定界法(1) 问题（A） Min z = c1 x1 + c2 x2 + … + cn xn 记 问题（B）为去掉整数约束的问题（A） s.t. a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a22 x2 + … + a2n xn = b2 …… …… am1 x1 + am2 x2 + … + amn xn = bm x1 ，x2 ，… ，xn ≥ 0 为整数 在分枝定界法过程中求解问题(B)，应有以下情况之一： ①(B)无可行解，则(A)亦无可行解，停止对此问题 的计算； ②(B)有最优解，并满足整数约束，即同时为(A)的最优解，那么z *同时是当前问题(A)最优 目标值的上界 和下界。停止对这个问题的计算； ③(B)有最优解 x 及最优值 z 但不符合整数条件。这时得到当前问题(A)最优目标值的一个下 界 z ＝z ,于是通过以下判断可对此问题进一步计算。 分枝定界法的计算过程： 1、对原问题(A)，求解松弛问题(B)。根据上面分析，若出现情况①，②则停机。若情况③ 发生，得到(A)问题最优值的一个下界。我们任找(A)问题的一个可行解，那么对应的目标 函数值是(A)最优值的一个上界 z¯ 。即得到 z ＜ z * ＜z¯。(注：找(A)问题的可行解往往需 要较大的计算量，这时可简单记 z¯＝+，而先不必费很大力量去求较好的上界。从以下 分析可以看到，找到一个好的最优目标值上界，将对算法的快速求得目标非常有效。)， 转2，进行以下一般步的迭代；