(i)对问题B1再进行分枝得问题B1和B12,它们的最优解为 B1:x1=4,x2=2,-1=340 B2:x1=1.43,x2=3.00,-12=32714 再定界:340≤z≤341,并将B2剪枝 (iv)对问题B2再进行分枝得问题B21和B2,它们的最优解为 B21:x1=544,x2=1.00,=2=308 B2无可行解。 将B21B2剪枝 于是可以断定原问题的最优解为: x1=4,x2=2,xz=340 从以上解题过程可得用分枝定界法求解整数规划(最大化)问题的步骤为 开始,将要求解的整数规划问题称为问题A,将与它相应的线性规划问题称为问 题B。 (i)解问题B可能得到以下情况之一: (a)B没有可行解,这时A也没有可行解,则停止 (b)B有最优解,并符合问题A的整数条件,B的最优解即为A的最优解,则 停止 (c)B有最优解,但不符合问题A的整数条件,记它的目标函数值为三。 (i)用观察法找问题A的一个整数可行解,一般可取x,=0,j=1,…,n,试探, 求得其目标函数值,并记作z。以z表示问题A的最优目标函数值;这时有 三≤z≤2 进行迭代 第一步:分枝,在B的最优解中任选一个不符合整数条件的变量x,其值为b 以[b表示小于b的最大整数。构造两个约束条件 ≤[b,]和x≥[b]+ 将这两个约束条件,分别加入问题B,求两个后继规划问题B1和B2。不考虑整数条件 求解这两个后继问题。 定界,以每个后继问题为一分枝标明求解的结果,与其它问题的解的结果中,找出 最优目标函数值最大者作为新的上界2。从已符合整数条件的各分支中,找出目标函数 值为最大者作为新的下界z,若无作用=0。 第二步:比较与剪枝,各分枝的最优目标函数中若有小于三者,则剪掉这枝,即 以后不再考虑了。若大于z,且不符合整数条件,则重复第一步骤。一直到最后得到 z=三为止。得最优整数解x/,j=l…,n §30-1型整数规划 0-1型整数规划是整数规划中的特殊情形,它的变量x仅取值0或1。这时x称 为0-1变量,或称二进制变量。x仅取值0或1这个条件可由下述约束条件:-13- （iii）对问题 B1 再进行分枝得问题 B11 和 B12 ，它们的最优解为 B11 : x1 = 4, x2 = 2,z11 = 340 B12 : x1 =1.43,x2 = 3.00,z12 = 327.14 再定界： 340 341 *  z  ，并将 B12 剪枝。 （iv）对问题 B2 再进行分枝得问题 B21 和 B22 ，它们的最优解为 B21 : x1 = 5.44,x2 =1.00,z22 = 308 B22 无可行解。 将 21 22 B ,B 剪枝。 于是可以断定原问题的最优解为： 4, 2, 340 * x1 = x2 = z = 从以上解题过程可得用分枝定界法求解整数规划（最大化）问题的步骤为： 开始，将要求解的整数规划问题称为问题 A ，将与它相应的线性规划问题称为问 题 B 。 （i）解问题 B 可能得到以下情况之一： （a） B 没有可行解，这时 A 也没有可行解，则停止． （b） B 有最优解，并符合问题 A 的整数条件， B 的最优解即为 A 的最优解，则 停止。 （c） B 有最优解，但不符合问题 A 的整数条件，记它的目标函数值为 z 。 （ii）用观察法找问题 A 的一个整数可行解，一般可取 xj = 0, j = 1,  ,n ，试探， 求得其目标函数值，并记作 z 。以 * z 表示问题 A 的最优目标函数值；这时有 z  z  z * 进行迭代。 第一步：分枝，在 B 的最优解中任选一个不符合整数条件的变量 j x ，其值为 j b ， 以 [ ] bj 表示小于 j b 的最大整数。构造两个约束条件 [ ] j bj x  和 xj  [bj ] +1 将这两个约束条件，分别加入问题 B ，求两个后继规划问题 B1 和 B2 。不考虑整数条件 求解这两个后继问题。 定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出 最优目标函数值最大者作为新的上界 z 。从已符合整数条件的各分支中，找出目标函数 值为最大者作为新的下界 z ，若无作用 z = 0 。 第二步：比较与剪枝，各分枝的最优目标函数中若有小于 z 者，则剪掉这枝，即 以后不再考虑了。若大于 z ，且不符合整数条件，则重复第一步骤。一直到最后得到 z = z * 为止。得最优整数解 x j , j 1, ,n * =  。 §3 0−1 型整数规划 0−1 型整数规划是整数规划中的特殊情形，它的变量 j x 仅取值 0 或 1。这时 j x 称 为 0−1 变量，或称二进制变量。 j x 仅取值 0 或 1 这个条件可由下述约束条件：