《《运筹》教学课件整数规划-分枝定界法》由会员分享，可在线阅读，更多相关《《运筹》教学课件整数规划-分枝定界法（18页珍藏版）》请在金锄头文库上搜索。
1、一、分枝定界法的原理：1、分枝 0 1 2 3 4 5 6 7 8松弛问题的可行域增加x13增加x14L1L2x13x14父问题子问题结论1 ：（IP）的最优解一定在某个子问题中父问题的最优值3 ：子问题中的整数解都是（IP）的可行解子问题的最优解2 ：子问题的可行域父问题的可行域2、定界1、（LP）的最优值是(IP)的最优值的上界IP松弛问题L0L1L2通过对（L0）分枝，使（IP）的最优值的上界不断下降，L3L4L5L6下界不断上升，上界=下界得最优值分枝定界法的基本思路：不断降低（IP）最优值的上界，提高下界，当上界等于下界时，得到最优解通过对松弛问题的分枝，分枝定界法计算过程：上界x1
2、x*01x1x*01+1当所有的子问题均被关闭或剪枝后目标函数值最大的整数解既为所求的最优解 0 1 2 3 4 5 6 7 8x13x14z=30x1+20 x24x1+x2=16.52x1+3x2=14.5x22x23x12x13课堂练习：混合型x13x14L0的最优单纯型表：x1x2x3x4常数项检00-5-5Z-155x2012/5-1/55/2x110-1/103/107/2x5x51 0 0 0 1 3000x13x14x12x13x22x23x1x2x3x4解检00-5-5Z-155x2012/5-1/55/2x110-1/103/107/2x5x51 0 0 0 1 3000x
3、1x2x3x4解检00-5-5Z-155x2012/5-1/55/2x110-1/103/107/2x5x50 0 1/10 -3/10 1 -1/2000x1x2x3x4解检00-20/30 -50/3 Z-440/3x2011/30 -2/317/6x11000 1300-1/31-10/3 5/3x4x5x22x2+ x6=2x1x2x3x4x5 解检00-20/30-50/3 Z-440/3x2011/30-2/3 17/6x110 001 3x400-1/31-10/35/3x60 1 0 0 0 1 2x60000x1x2x3x4x5 x6 解检00-20/30-50/3 0 Z-
4、440/3x2011/30-2/3 0 17/6x110 001 0 3x400-1/31-10/305/3x600-1/302/31-5/6x1x2x3x4x5 x6 解检0000-30 -20 Z-130x201000 1 2x110 001 0 3x40001-4-15/2x30010-2-35/2x23X2- x6=3x1x2x3x4x5 解检00-20/30-50/3 Z-440/3x2011/30-2/3 17/6x110 001 3x400-1/31-10/35/3x60 -1 0 0 0 1 -3x60000x1x2x3x4x5 x6 解检00-20/30-50/3 0 Z-4
5、40/3x2011/30-2/3 0 17/6x110 001 0 3x400-1/31-10/305/3x6001/30-2/31-1/6-X2+ x6=-3x1x2x3x4x5 x6 解检00-1500-25 Z-285/2x201000-1 3x110 1/200 3/2 11/4x400-210-55/2x500-1/201-3/21/4x1x2x3x4x5 x6 解检00-1500-25 Z-285/2x201000-1 3x110 1/200 3/2 11/4x400-210-55/2x500-1/201-3/21/4x12x1+ x7=2X700000x710000012x1x2
6、x3x4x5 x6 x7 解检00-20/3000 -50/3 Z-130x2011/3000 -2/3 7/2x110 000 0 1 2x400-1/3100-10/35x5000010-11x6001/3001-2/31/20 0 -1/2 0 0 -3/2 1 -3/4如何选择分枝的节点及分枝变量？1、分枝节点选择的原则：尽快找到好的整数解，减少搜索节点， 提高搜索效率。方法：（1）深探法：（2）广探法：最后打开的节点最先选择选择有最大目标函数值的节点继续向下分枝2、分枝变量选择的原则：寻找那些对问题影响最大的变量首先分枝（1）按目标函数系数选择：选择目标函数系数绝对值最大的变量首先分枝（2）按非整数变量选择：选择与整数值相差最大的非整数变量进行分枝（3）按人为给定的顺序选择x13x14x22x23x12x13
