分支定界法的解题步骤 1.将要求解的整数规划称为问题A,与之对应的线性 规划称为问题B。 2.解问题B,可能得到以下情况之一 B没有可行解,问题A也没有可行解,则停止。 B有最优解,并符合问题A的整数条件,B的最 优解即为A最优解。 B有最优解,但不符合问题A的整数条件,记其 目标函数值为Z+。 3.用观察法找问题A的一个整数可行解,一般可取x=0 产0,1,…,进行试探,求得其目标函数值,并记为Z, 若观察不到,则可记Z=-0若以Z表示问题A最优目 标函数值;这肘有Z<Z≤Z+
1. 将要求解的整数规划称为问题A，与之对应的线性 规划称为问题B。 2. 解问题B，可能得到以下情况之一： ü B没有可行解，问题A也没有可行解，则停止。 ü B有最优解，并符合问题A的整数条件，B的最 优解即为A最优解。 ü B有最优解，但不符合问题A的整数条件，记其 目标函数值为Z+ 。 3. 用观察法找问题A的一个整数可行解，一般可取xj=0， j=0,1,…,n进行试探，求得其目标函数值，并记为Z-， 若观察不到,则可记Z-=-∞。若以Z*表示问题A最优目 标函数值；这时有Z-≤Z*≤ Z+
分支定界法的解题步骤 4.分支:在B的最优解中任选一个不符合整数条件的变量x, 其值为b,以[b表示小于b的最大整数。枸造两个约束 条件:≤b,xb+1将这两个约束条件分别加入问 题B,得到B的两个分枝:问题B1与B2。对每个分枝问题 求解,得到以下几种可能: 分枝无可行解—该分枝是“树叶” IL求得该分枝的最优解,且满足A的整数条件。将该 最优解的目标函数值作为新的下界Z,该分枝也是 树叶”。 IL求得该分枝的最优解,且不满足A的整数条件,但 其目标函数值不大于当前下界Z,则该分枝是“枯 枝”,需要剪枝
4. 分支:在B的最优解中任选一个不符合整数条件的变量xj， 其值为bj，以[bj]表示小于bj 的最大整数。构造两个约束 条件:xj ≤[bj]，xj ≥[bj]+1。将这两个约束条件分别加入问 题B，得到B的两个分枝:问题B1与 B2 。对每个分枝问题 求解,得到以下几种可能: I. 分枝无可行解——该分枝是 “ 树叶” 。 II. 求得该分枝的最优解，且满足A的整数条件。 将该 最优解的目标函数值作为新的下界Z-，该分枝也是 “树叶” 。 III.求得该分枝的最优解，且不满足 A的整数条件，但 其目标函数值不大于当前下界Z-，则该分枝是“枯 枝” ，需要剪枝
分支定界法的解题步骤 ⅣV.求得不满足A整教条件的该分枝的最优解,且其 目标函教值大于当前下界Z,则该分枝需要继续 进行分枝。 若得到的是前三种情形之一,表明該分枝情况已探明, 不需要继续分枝。 若求解一对分枝的结果表明这一对分枚都需要继续分 枝,则可先对目标函数值大的那个分枝进行分枝计算,且 沿着该分枝一直继续进行下去,直到全部探明情况为止; 再返过来求解目标函数值较小的鄄个分枝
IV. 求得不满足A整数条件的该分枝的最优解，且其 目标函数值大于当前下界Z-，则该分枝需要继续 进行分枝。 若得到的是前三种情形之一，表明该分枝情况已探明， 不需要继续分枝。 若求解一对分枝的结果表明这一对分枝都需要继续分 枝，则可先对目标函数值大的那个分枝进行分枝计算，且 沿着该分枝一直继续进行下去，直到全部探明情况为止； 再返过来求 解目标函数值较小的那个分枝
分支定界法的解题步骤 5.定界: L.修改下界:每求出一次符合整数条件的可行解肘, 都要考虑修改下界,选择迤今为止最好的整教可 行解相应的目标函数值作下界Z。 ∏L修改上界:每求解完一对分枚,都要考虑修改上 界。上界的值Z应是迄今为止所有朱被分枚的问 题的目标函数值中最大的一个。 6.在每解完一对分枝、修改完上、下界后,若巳有Z=Z+, 此肘所有分枝均巳查明,即得到了问题A的最优值。若仍 有Z+>Z,则说明仍有分枝没查明,需要继姎分枝,回 到第4步
5. 定界: I. 修改下界:每求出一次符合整数条件的可行解时， 都要考虑修改下界，选择迄今为止最好的整数可 行解相应的目标函数值作下界 Z-。 II. 修改上界 :每求解完一对分枝，都要考虑修改上 界。上界的值Z+应是迄今为止所有未被分枝的问 题的目标函数值中最大的一个。 6. 在每解完一对分枝、修改完上、下界后,若已有Z-= Z+ ， 此时所有分枝均已查明,即得到了问题A 的最优值。若仍 有 Z+ > Z-，则说明仍有分枝没查明，需要继续分枝，回 到第4步
分支定界法 倒4-3求解下列整数规划问题 Marf(x=4x+3x 1.2x+08x,≤10 s2x+25x,≤25 ,2≥0且为整数
例4-3 求解下列整数规划问题 ï î ï í ì ³ + £ + £ = + , 0且为整数 2 2.5 25 1.2 0.8 10 ( ) 4 3 1 2 1 2 1 2 1 2 x x x x x x st Maxf x x x