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

第三节分支定界法（BranchandBound，简称B如果不生产第j种产品，xj=0.约束条件xjMjyj,yj=1或0。当yj=1不利于目标函数的最大化，因此在最优解必然是yj=0。,14,例含有相互排斥的约束条件的问题,设工序B的每周工时约束条件为0.3x1+0.5x2150,式(1)现有一新的加工方式,相应的每周工时约束条件为0.2x1+0.4x2120,式(2)如果工序B只能选择一种,那么(1)和(2)变成相互排斥的约束条件.,当y1=1,y2=0;采用新工艺,(2)式成立;,多余的约束,15,约束条件组,在约束条件中保证了在P个0-1变量中有p-q个1,q个0;凡取值=0的yi对应的约束条件为原约束条件,凡取值=1的yi对应的约束条件将自然满足,因而为多余.,16,例工件排序问题,使用4台机床加工3件产品.各个产品的机床加工顺序以及产品i在机床j上的加工时间aij见表.由于某种原因,产品2的加工总工时不得超过d.现在要求各件产品在机床上的加工方案,使在最段时间内加工完全部产品.,17,解设xij表示产品i在机床j上开始加工的时间(i=1,2,3;j=1,2,3,4),1.同一件产品在不同机床上的加工顺序约束同一件产品在下一台机床上的加工的开始时间不早于在上一台机床上加工的结束时间,故应有产品1:x11+a11x12;x13+a13x14产品2:x21+a21x22;x23+a23x24产品3:x32+a32x33;,2.每一台机床对不同产品的加工顺序约束一台机床在工作中,如果已经开始加工还没有结束,则不能开始加工另一件产品.对于机床1,先加工1不能加工2.为了容纳两种相互排斥的约束条件,对于每台机床,分别引入0-1变量:,18,机床1:x11+a11x21+My1;x21+a21x11+M(1-y1)机床2:x22+a22x32+My2;x32+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=Wst.Wx14+a14,Wx24+a24,Wx33+a33.,19,二、0-1型整数规划的解法,求解思路：检测可行解的目标函数值，根据其目标函数值可以产生一个过滤条件，对于目标函数数值比它差的变量组合删除，这样有效减少运算次数，使最优解快速找到。,20,解：求解过程可以列表表示：,21,在求解0-1整数规划问题，为了进一步减少运算量，常按照目标函数中各个变量系数的大小顺序重新排列各个变量，以便于最优解有可能较早出现。对于最大化问题，可以按照从小到大的顺序排列；对于最小化问题，可以按照从大到小的顺序排列；,运算36次,运算30次,22,练习1:使用分支定界法求解整数规划,松弛问题的最优解X=(2.75,2.25)T,23,24,练习2：使用一等价的整数规划表述下面的问题,25,26,小结:1、分支定界法的计