第二节用分支定界法求解整数规划 步骤2：如问题B无可行解，】 则问题A也无可 行解；如问题B的最优解符合问题A的整数要求， 则它就是问题A的最优解。对于这两种情况，求解 过程到此结束。如问题B的最优解存在， 但不符合 问题A的整数要求，则转步骤3； 18
18 步骤2：如问题B无可行解，则问题A也无可 行解；如问题B的最优解符合问题A的整数要求， 则它就是问题A的最优解。对于这两种情况，求解 过程到此结束。如问题B的最优解存在，但不符合 问题A的整数要求，则转步骤3； 第二节 用分支定界法求解整数规划
第二节用分支定界法求解整数规划 步骤3：对问题B,任选一个不符合整数要求 的变量进行分支。设选择X=b(其中b不是整数)， 且设[b]为不超过b的最大整数。对问题B分别增加 下面两个约束条件中的一个 X<=[b和X;=>[b+1 从而形成两个后继问题。解这两个后继问题。 转步骤4； 19
19 步骤3：对问题B，任选一个不符合整数要求 的变量进行分支。设选择Xi=b(其中b不是整数)， 且设[b]为不超过b的最大整数。对问题B分别增加 下面两个约束条件中的一个： Xi <= [b]和 Xi => [b]+1 从而形成两个后继问题。解这两个后继问题。 转步骤4； 第二节 用分支定界法求解整数规划
第二节用分支定界法求解整数规划 步骤4：考查所有后继问题， 如其中有某几个 存在最优解，且其最优解满足问题A的整数要求， 则以它们中最优的目标函数值和界Z,作比较。若 比界Z,更优，则以其取代原来的界Z,并称相应的 后继问题为问题C。否则，原来的界Z不变。转步 骤5； 20
20 步骤4：考查所有后继问题，如其中有某几个 存在最优解，且其最优解满足问题A的整数要求， 则以它们中最优的目标函数值和界Zb作比较。若 比界Zb更优，则以其取代原来的界Zb，并称相应的 后继问题为问题C。否则，原来的界Zb不变。转步 骤5； 第二节 用分支定界法求解整数规划
第二节用分支定界法求解整数规划 步骤5： 在不属于C的后继问题中，称存在最 优解且其目标函数值比界z更优的后继问题为待 检查的后继问题 若不存在待检查的后继问题，当问题C存在时， 问题C的最优解就是问题A的最优解；当问题C不 存在时，和界Z对应的可行解就是问题A的最优解。 Z即为问题A的最优解的目标函数值，求解到此结 束。 21
21 步骤5：在不属于C的后继问题中，称存在最 优解且其目标函数值比界zb更优的后继问题为待 检查的后继问题。 若不存在待检查的后继问题，当问题C存在时， 问题C的最优解就是问题A的最优解；当问题C不 存在时，和界Zb对应的可行解就是问题A的最优解。 Zb即为问题A的最优解的目标函数值，求解到此结 束。 第二节 用分支定界法求解整数规划
第二节用分支定界法求解整数规划 若存在待检查的后继问题，则选择其中目标 函数值最优的一个后继问题，改称其为问题B。回 到步骤3。 从分支定界法的原理和步骤可知，它也适用 于求解混合整数规划问题。如在下面的例题中， 假如原问题仅要求x1是整数，那么(H1)的解就是 原问题的最优解 分支定界法是求解整数规划的较好方法，在 实际问题中有着广泛应用
22 若存在待检查的后继问题，则选择其中目标 函数值最优的一个后继问题，改称其为问题B。回 到步骤3。 从分支定界法的原理和步骤可知，它也适用 于求解混合整数规划问题。如在下面的例题中， 假如原问题仅要求x1是整数，那么(H1)的解就是 原问题的最优解。 分支定界法是求解整数规划的较好方法，在 实际问题中有着广泛应用。 第二节 用分支定界法求解整数规划