运筹学课件第三节分支定界法.ppt

1、第三节 分支定界法 （Branch and Bound， 简称BMIN,上界）；,求极小问题时，LP问题的解是IP问题的下界。每次分支后的子 问题最优解的目标函数值都大于或等于分支前的最优值。如分 支中得到整数解，则最小的整数解为上界。如分支的目标函数 值大于上界，则停止分支。,A X1=3/2,X2=10/3 Z=29/6,B X1=2,X2=23/9 Z=41/9,C X1=1,X2=7/3 Z=10/3,无可行解,D X1=33/14,X2=2 Z=61/14,F X1=2,X2=2 Z=4,E X1=3,X2=1 Z=4,x1 1,x1 2,x2 2,x2 3,x1 2,x1 3,不同

2、的搜索策略会导致不同的搜索树，一般情况下，同一层的两个子问题，先搜索目标函数比较大的较有利（如果是极小问题，则应先搜索目标函数值小的较为有利）。这样可能得到数值比较大的下界，下界越大被剪去的分支越多。 分支定界算法对于混合整数规划特别有效，对没有整数要求的变量就不必分支，这将大大减少分支的数量。,第四节 01型整数规划,一、0-1变量及其应用 某些特殊问题，只做是非选择，故变量设置简化为0或1， 1代表选择，0代表不选择。,一、01规划数学模型,例：固定费用问题 有三种资源被用于生产三种产品，资源量、产品单件费用、 资源消耗量以及生产产品的固定费用。要求制定一个生产计 划，总收益最大。,产品,

3、资源,解：xj是生产第j种产品的产量。 总收益等于销售减去所生产的产品的总费用。建立数学模型时，无法确定某种产品是否生产，不能确定相应的固定费用是否发生，用0-1变量解决此问题。,分析：如果生产第j种产品，xj0. 约束条件xj Mjyj,yj=1; 如果不生产第j种产品，xj=0. 约束条件xjMjyj, yj=1或0。当yj=1不利于目标函数的最大化，因此在最优解必然是yj=0。,例 含有相互排斥的约束条件的问题,设工序B的每周工时约束条件为0.3x1+0.5x2150,式(1) 现有一新的加工方式,相应的每周工时约束条件为0.2x1+0.4x2120 ,式(2) 如果工序B只能选择一种,

4、那么(1)和(2)变成相互排斥的约束条件.,当y1=1,y2=0;采用新工艺,(2)式成立;,多余的约束,约束条件组,在约束条件中保证了在P个0-1变量中有p-q个1,q个0;凡取值=0的yi对应的约束条件为原约束条件,凡取值=1的yi对应的约束条件将自然满足,因而为多余.,例 工件排序问题,使用4台机床加工3件产品.各个产品的机床加工顺序以及产品i在机床j上的加工时间 aij见表.由于某种原因,产品2的加工总工时不得超过d.现在要求各件产品在机床上的加工方案,使在最段时间内加工完全部产品.,解 设xij表示产品i在机床j 上开始加工的时间(i=1,2,3;j=1,2,3,4),1.同一件产品

5、在不同机床上的加工顺序约束 同一件产品在下一台机床上的加工的开始时间不早于在上一台机床上加工的结束时间,故应有 产品1:x11+a11x12 ; x13+a13x14 产品2:x21+a21x22 ; x23+a23x24 产品3:x32+a32x33 ;,2.每一台机床对不同产品的加工顺序约束 一台机床在工作中,如果已经开始加工还没有结束,则不能开始加工另一件产品.对于机床1,先加工1不能加工2. 为了容纳两种相互排斥的约束条件,对于每台机床,分别引入0-1变量:,机床1:x11+a11x21+My1 ; x21+a21x11+M(1-y1) 机床2:x22+a22x32+My2 ; x32

6、+a32x22+M(1-y2) 机床3:x13+a13x33 +My3 ; x33+a33x13+M(1-y3) 机床4:x14+a14x24 +My4 ; x24+a24x14+M(1-y4) 当y1=0,表示机床1先加工产品1,后加工产品2;当y1=1,表示机床1先加工产品2,后加工产品1.,3.产品2的加工总时间约束 产品2的开始加工时间x21,结束加工时间为x24+a24,所以 x24+a24-x21d,4.目标函数的建立 由于三件产品的加工时间分别为x14+a14,x24+a24,x33+a33,全部产品的实际加工时间为:w=max(x14+a14,x24+a24,x33+a33) Minz=W st. Wx14+a14, W x24+a24, W x33+a33.,二、0-1型整数规划的解法,求解思路： 检测可行解的目标函数值，根据其目标函数值可以产生一个过滤条件，对于目标函数数值比它差的变量组合删除，这样有效减少运算次数，使最优解快速找到。,解：求解过程可以列表表示：,在求解0-1整数规划问题，为了进一步减少运算量，常按照目标函数中各个变量系数的大小顺序重新排列各个变量，以便于最优解有可能较早出现。 对于最大化问题，可以按照从小到大的顺序排列； 对于最小化问题，可以按照从大到小的顺序排列；,运算36次,运算30次,练习1:使用