第2节分支定界解法 显然,仍没有得到全部变量是整数的解。因z1>2,故将改为 349那么必存在最优整数解,得到乙*,并且 0<z*<349 令继续对问题B1和B2进行分解。因z1>z2,故先分解B1为两支。增加 条件x2≌2,称为问题B;增加条件x2≥3,称为问题B4。相当于在 图5-3中再去掉x2>2与x3<3之间的区域,进行第二次迭代 问题B1 问题B2 4 123456 清华大学出版社
清华大学出版社 17 第2节 分支定界解法 ❖ 显然，仍没有得到全部变量是整数的解。因z1＞z2，故将 改为 349，那么必存在最优整数解，得到z*，并且 0≤z*≤349 ❖ 继续对问题B1和B2进行分解。因z1＞z2，故先分解B1为两支。增加 条件x2≤2，称为问题B3；增加条件x2≥3，称为问题B4。相当于在 图5-3中再去掉x2＞2与x3＜3之间的区域，进行第二次迭代。 z
第2节分支定界解法 继续对问题B2进行分解 x2 问题B 问题B2 B4> 0123456 清华大学出版社
清华大学出版社 18 第2节 分支定界解法 ❖ 继续对问题B2进行分解
问题B 4.81 x2=1.82 z=0,z=356 z0=356 x1≤4 5 问题B1 问题B2 x1=4.00 x1=5.00 z=0,z=349 x2=2.10 x2=1.57 z1=349 z2=341 x2≤2x2≥3 问题B3 问题B4 解题过程 x1=4.00 x1=142 2=3.00 z3=340 z4=327 x2≤1 x2≥2 问题B3 问题B6 340=z* x1=544 无可行解 x2=1.00 zs=308
清华大学出版社 19 第2节 分支定界解法 解 题 过 程
第2节分支定界解法 令从以上解题过程可得到用分支定界法求解整数线性规划 (最大化)问题的步骤为(将要求解的整数线性规划问题称 为问题A,将与它相应的线性规划问题称为问题B) 令(1)解问题B,可能得到以下情况之一: ①B没有可行解,这时A也没有可行解,则停止 o②B有最优解,并符合问题A的整数条件,B的最优解即为A的最 优解,则停止。 ③B有最优解,但不符合问题A的整数条件,记它的目标函数值 为E0 令(2)用观察法找问题A的一个整数可行解,一般可取x=0, 产1,…,n,试探,求得其目标函数值,并记作三 冷以*表示问题A的最优目标函数值;这时有 z<z<2 清华大学出版社
清华大学出版社 20 第2节 分支定界解法 ❖ 从以上解题过程可得到用分支定界法求解整数线性规划 (最大化)问题的步骤为（将要求解的整数线性规划问题称 为问题A，将与它相应的线性规划问题称为问题B）： ❖ (1) 解问题B，可能得到以下情况之一： ① B没有可行解，这时A也没有可行解，则停止。 ② B有最优解，并符合问题A的整数条件，B的最优解即为A的最 优解，则停止。 ③ B有最优解，但不符合问题A的整数条件，记它的目标函数值 为 ❖ (2) 用观察法找问题A的一个整数可行解，一般可取xj =0， j=1，…，n，试探，求得其目标函数值，并记作 ❖ 以z*表示问题A的最优目标函数值；这时有 0 z z _ * z z z −
第2节分支定界解法 今进行迭代 令第一步:分支,在B的最优解中任选一个不符合整数条件 的变量x,其值为b,以[b]表示小于b的最大整数。构 造两个约束条件 x≤[b,]和x≥[b,]+1 将这两个约束条件,分别加入问题B,求两个后继规划问 题B1和B2。不考虑整数条件求解这两个后继问题 定界,以每个后继问题为一分支标明求解的结果,与其 他问题的解的结果中,找出最优目标函数值最大者作为 新的上界2。从已符合整数条件的各分支中,找出目标函 数值为最大者作为新的下界z,若无可行解,=0 清华大学出版社
清华大学出版社 21 第2节 分支定界解法 ❖ 进行迭代 ❖ 第一步：分支，在B的最优解中任选一个不符合整数条件 的变量xj，其值为bj，以［bj］表示小于bj的最大整数。构 造两个约束条件 xj ≤［bj］和xj ≥［bj］+1 将这两个约束条件，分别加入问题B，求两个后继规划问 题B1和B2。不考虑整数条件求解这两个后继问题。 定界，以每个后继问题为一分支标明求解的结果，与其 他问题的解的结果中，找出最优目标函数值最大者作为 新的上界 。从已符合整数条件的各分支中，找出目标函 数值为最大者作为新的下界 z ，若无可行解， z = 0 。 z