《运筹》教学课件整数规划第四章（二）分枝定界法.ppt

《《运筹》教学课件整数规划第四章（二）分枝定界法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、分枝定界法一、分枝定界法的原理：1、分枝··················012345678·松弛问题的可行域增加x1≤3增加x1≥4L1L2x1≤3x1≥4父问题子问题结论1：（IP）的最优解一定在某个子问题中父问题的最优值≤3：子问题中的整数解都是（IP）的可行解子问题的最优解2：子问题的可行域父问题的可行域∩2、定界1、（LP）的最优值是(IP)的最优值的上界IP松弛问题L0L1L2通过对（L0）分枝，使（IP）的最优值的上界不断下降，L3L4L5L6下界不断上升，上界=下界得最优值分枝定界法的基本思路：不断降低（IP）最优值的上界，提高下界，当上界等

2、于下界时，得到最优解通过对松弛问题的分枝，分枝定界法计算过程：上界x1≤[x*01]x1≥[x*01]+1当所有的子问题均被关闭或剪枝后目标函数值最大的整数解既为所求的最优解··················012345678·x1≤3x1≥4z=30x1+20x24x1+x2=16.52x1+3x2=14.5x2≤2x2≥3x1≤2x1≥3课堂练习：混合型x1≤3x1≥4L0的最优单纯型表：x1x2x3x4常数项检00-5-5Z-155x2012/5-1/55/2x110-1/103/107/2x5x5100013000x1≤3x1≥4x1≤2x1≥3x2

3、≤2x2≥3x1x2x3x4解检00-5-5Z-155x2012/5-1/55/2x110-1/103/107/2x5x5100013000x1x2x3x4解检00-5-5Z-155x2012/5-1/55/2x110-1/103/107/2x5x5001/10-3/101-1/2000x1x2x3x4解检00-20/30-50/3Z-440/3x2011/30-2/317/6x110001300-1/31-10/35/3x4x5x2≤2x2+x6=2x1x2x3x4x5解检00-20/30-50/3Z-440/3x2011/30-2/317/6x110001

4、3x400-1/31-10/35/3x60100012x60000x1x2x3x4x5x6解检00-20/30-50/30Z-440/3x2011/30-2/3017/6x11000103x400-1/31-10/305/3x600-1/302/31-5/6x1x2x3x4x5x6解检0000-30-20Z-130x20100012x11000103x40001-4-15/2x30010-2-35/2x2≥3X2-x6=3x1x2x3x4x5解检00-20/30-50/3Z-440/3x2011/30-2/317/6x1100013x400-1/31-10/3

5、5/3x60-10001-3x60000x1x2x3x4x5x6解检00-20/30-50/30Z-440/3x2011/30-2/3017/6x11000103x400-1/31-10/305/3x6001/30-2/31-1/6-X2+x6=-3x1x2x3x4x5x6解检00-1500-25Z-285/2x201000-13x1101/2003/211/4x400-210-55/2x500-1/201-3/21/4x1x2x3x4x5x6解检00-1500-25Z-285/2x201000-13x1101/2003/211/4x400-210-55/2x

6、500-1/201-3/21/4x1≤2x1+x7=2X700000x710000012x1x2x3x4x5x6x7解检00-20/3000-50/3Z-130x2011/3000-2/37/2x110000012x400-1/3100-10/35x5000010-11x6001/3001-2/31/200-1/200-3/21-3/4如何选择分枝的节点及分枝变量？1、分枝节点选择的原则：尽快找到好的整数解，减少搜索节点，提高搜索效率。方法：（1）深探法：（2）广探法：最后打开的节点最先选择选择有最大目标函数值的节点继续向下分枝2、分枝变量选择的原则：寻找那些

7、对问题影响最大的变量首先分枝（1）按目标函数系数选择：选择目标函数系数绝对值最大的变量首先分枝（2）按非整数变量选择：选择与整数值相差最大的非整数变量进行分枝（3）按人为给定的顺序选择x1≤3x1≥4x2≤2x2≥3x1≤2x1≥3