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