分支定界

3.3.1分支定界方法的基本思路分支定界法（BranchandBoundMethod）是求解整数规划的一种常用的有效的方法，分支定界法既可以求解纯整数规划，也可以用于求解混合整数规划。§3.3分支定界方法分支定界法基本思路是先求解整数规划的线性规划问题。如果其最优解不符合整数条件，则求出整数规划的上下界，用增加约束条件的办法，把相应的线性规划的可行域分成子区域（称为分支），再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后得整数规划的最优解。分支定界法包含分支和定界两个过程。分支的目的是为求解整数规划创造了条件，定界可以提高搜索的效率。分支定界法基本思路所谓“分支”就是在处理整数规划问题时，逐步加入对各变量的整数要求限制。先求解整数规划相应的松弛问题(记为P0)，若(P0)的最优解不符合整数条件，假设iixb不符合整数条件，于是增加新的约束条件：iixb和1iixb，分别将其加入到松弛问题(P0)中，从而形成两个分支，称为两个后继子问题。后继子问题的可行域包含整数规划所有的可行解。根据需要，后继子问题可以产生类似的分支，从而把原整数规划问题通过分支迭代求出最优解。所谓“定界”就是在分支过程中，若某个后继子问题最优解恰好是整数规划的可行解，则该后继子问题最优目标函数值成为整数规划的目标函数值的一个“界限”，从而对那些最优目标函数值比上述“界限”还差的后继子问题可以剔除不加考虑。同时在分支过程中出现更好的“界限”，则用它来取代原来的界限，以提高定界的效率。3.3.2分支定界法求解整数规划问题的步骤(以求最大化的整数规划为例)step1确定与整数规划问题(记为问题A)对应的松弛线性规划问题(记为问题B)；step2解问题B，如果问题B没有可行解，则问题A也没有可行解，计算停止；如果问题B有最优解，并符合问题A的整数条件，则问题B的最优解就是问题A的最优解，计算停止。若问题B有最优解，但不符合问题A的整数条件，记问题B的目标函数值为step3用观察法找问题A的—个整数解，一般可取进行试探，求得其目标函数值，并记作以表示问题A的最优目标函数值；这时有0,1,2,,ixinz*z*zzziixbstep4在B的最优解中任选一个不符合整数条件的变量进行分支，设，以表示不超过的最大整数，构造两个约束条件和，将这两个约束条件分别加入问题B中，得到两个后继子问题Bl和B2。不考虑整数条件求解这两个后继子问题。iixbibibiixb1iixb若用分支定界法求解混合整数规划，则分支的过程中只针对有整数要求的变量进行，而不管连续变量的取值如何。step5以每个后继子记问题为一分支标明求解的结果，与其他后继子问题的解的结果进行比较，找出最优目标函数值最大者作为新的上界；从已符合整数条件的各分支中，找出目标函数值最大者作为新的下界；若后继子问题的解不符合整数条件，仍然保持原下界值。zstep6各分支的最优目标函数中若有小于者，则剪掉这支，即以后不再考虑了；若大于，且不符合整数条件，则重复step4。一直到最后为止，从而得到整数规划问题(问题A)的最优整数解。zzzz3.3.3分支定界法的应用举例例3.3.1用分支定界法求解整数规划12121212max2535..436,0,379zxxxxstxxxx全部为整数解:step1确定与整数规划问题（记为问题A）对应的松弛线性规划问题(记为问题B)：step2先求出问题B的解，用单纯形方法得问题B的最优解为：12121212max2535..436,0379zxxxxstxxxx*12012683,2,14171717xxzstep3用观察法找问题A的—个整数解，一般可取，进行试探，求得其目标函数值，以表示问题A的最优目标函数值；这时有12,00xx0z*z*801417zstep4在B的最优解中选一个不符合整数条件的进行分支，构造两个约束条件和，将这两个约束条件分别加入问题B中，得到两个后继子问题B1和。26217x22x23xB2问题Bl:121212212max2535436..2,0379zxxxxxxstxxx问题B2：121212212max2535436..3,0379zxxxxxxstxxx用单纯形方法得后继子问题Bl和B2的最优解分别为：Bl的最优解：*12142,2,144..xxzB2的最优解：*122225,3,135..xxzstep5以后继子问题Bl和B2的解的结果进行比较，找出最优目标函数值最大者作为新的上界；后继子问题Bl和B2的解不符合整数条件，仍然保持原下界值，则问题A的最优目标函数值满足：*z*014.4zstep6因为重复step4，对后继子问题Bl进行分支得其后继子问题B3和B4。用单纯形方法得后继子问题B3和B4的最优解分别为：**12zz问题B3:1212122112max2535436..24,0379zxxxxxxstxxxx问题B4：1212122112max2535436..3,03795zxxxxxxstxxxxB3的最优解：*1234,2,14xxzB4的最优解：*124325,1,1477xxz因为B3的最优解已符合整数条件，*314z成为整数规划问题A的新下界z，同时因为**32zz，所以剪掉后继子问题B2这支。从而问题A的最优目标函数值*z的新的界限满足：*214147z由于**43zz，所以从理论上需要对B4继续进行分支，但考虑到*42147z，即使再分支，问题A的最优目标函数值也不会超过14，从而可以判定*1414z，所以B3的最优解为问题A的最优解，即*1234,2,14xxz。3.4.10-1变量及其应用0-1变量可以数量化地描述诸如开与关、取与弃、有与无等现象，它所反映了离散变量间的逻辑关系以及约束条件的互斥关系等，它可把本来需要分别各种情况加以讨论的问题统一在一个问题中讨论。决策变量仅取值0或1的一类特殊的整数规划称为0-1规划。0-1规划主要用于求解互斥的计划问题、约束条件互斥问题、固定费用问题和指派问题等方面。§3.40－1规划例3.4.1约束条件互斥问题在有互相排斥的约束条件的问题中，如果需要从约束条件1,1,2,,nijjijaxbip中恰好取q个约束条件，如何利用0-1变量进行统一的表达?则约束条件组可表示为解：引进0-1变量，设jy10iiyi若不选择第个约束条件若选择第个约束条件1,2,,ip11,1,2,,0,1;1,2,,nijjiijpiiiaxbMyipypqyip例3.4.2固定支出问题考察n种产品的产品计划问题。假定生产某种产品j就发生单位可变成本jc，另外，不管产品j生产多少，还需支出固定成本jk，但若不生产产品j也就无需支出固定成本。因此，如何制定产品计划，使得总生产成本最小。解：设表示产品j的产量，则产品j的生产成本函数可以写成：jx0()00jjjjjjkcxxCxx＝引进0-1变量，设jy1000jjjxyx＝注意0-1变量约束条件不是线性的，但是可以把它用一个线性约束条件等价地表示为：0,01jjjxMyyorjy则总生产成本的目标函数为：11min()nnjjjjjjjzCxcxky这里M是一个充分大的正数。所以该产品计划问题可以表述成如下规划问题：1min0,1,2,,..01,1,2,,njjjjjjjjzcxkyxMyjnstyorjn例3.4.3.约束条件的右端项可能是r个值rbbb,,,21中的某一个，即rnjjijbbbxa或或或211定义否则约束条件右端为01iiby，那么，约束条件可以化为10,,,1212111或rrriiinjjijyyyyyyybxa例3.4.4.两组条件中满足其中一组若41x，则12x；否则（即41x时），32x定义)2,1(01iiiyi个条件起作用第个条件不起作用第，又M为任意大的正数，则10,13414212122211211或yyyyMyxMyxMyxMyx带绝对值的不等式对于不等式12axbxc可以化为：12caxbxc1212axbxcaxbxc但是，对于不等式12axbxc只能化为：12axbxc或者12axbxc引进0-1变量12,yy化为：12112212121,0,1axbxcMyaxbxcMyyyyy3.4.20-1规划的解法解型整数规划最容易想到的方法，和一般整数规划的情形一样，就是穷举法，即检查变量取值为0或1的每一种组合，比较目标函数值以求得最优解，这就需要检查变量取值的个组合。对于变量个数n较大，这几乎是不可能的。因此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的方法称为隐枚举法（ImplicitEnumeration）。隐枚举法是一种简单方便，常用于手算或求解小规模问题的方法。2n例3.4.3求解型整数规划1231231231223123max3252244..346,01,zxxxxxxxxxstxxxxxxxor解：先试探性求一个可行解123,,100xxx，故为一个可行解，且相应的目标函数值为3z。因为是求极大值问题，故求最优解时，凡是目标值3z的解不必检验是否满足约束条件即可删除，因它肯定不是最优解，于是应增加一个约束条件3z，称该条件为过滤条件(FilteringContraint)。若用全部枚举法，3个变量共有8种可能的组合，我们将这8种组合依次检验它是否满足条件(1)—(4)，对某个组合，若它不满足(1)，即不满足过滤条件，则(2)—(4)即可行性条件不必再检验；若它满足(1)—(4)且相应的目标值严格大于3，则进行迭代运算。从而得最优解***123,,101xxx，最优值*8Z。