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

1、运筹学教程 （branch and bound， b&b） 0.maxxbaxstcxz运筹学教程 e d c b sub1 sub2 ir xr ir+1 a x2o x1分枝分枝运筹学教程 sub1sub2 由于这两个子问题的可行域都是原线性规划问题可行域的由于这两个子问题的可行域都是原线性规划问题可行域的子集，这两个子问题的最优解的目标函数值都不会比原线子集，这两个子问题的最优解的目标函数值都不会比原线性规划问题的最优解的目标函数值更大。如果这两个问题性规划问题的最优解的目标函数值更大。如果这两个问题的最优解仍不是整数解，则继续选择一个非整数的变量，的最优解仍不是整数解，则继续选择一个非

2、整数的变量，继续将这个子问题分解为两个更下一级的子问题。这个过继续将这个子问题分解为两个更下一级的子问题。这个过程称为程称为“分支（分支（branch）”。 01.maxxixbaxstcxzrr0.maxxixbaxstcxzrr运筹学教程 。 运筹学教程5整数规划问题的求解方法整数规划问题的求解方法分支定界法图解整数规划分支定界法图解整数规划 松弛问题松弛问题 max z = x1 + x2 14x1 + 9x2 51 - 6x1 + 3x2 1 x1 ， x2 0该整数规划松弛问题的解为：该整数规划松弛问题的解为：（x1 ，x2 ）= （3/2 ，10/3）z1 = 29/6运筹学教程6

3、松弛问题松弛问题 max z = x1 + x2 14x1 + 9x2 51 - 6x1 + 3x2 1 x1 ， x2 0（3/2 ，10/3）z1 = 29/6b1 max z = x1 + x2 14x1 + 9x2 51 - 6x1 + 3x2 1 x1 2 x1 ， x2 0b2 max z = x1 + x2 14x1 + 9x2 51 - 6x1 + 3x2 1 x1 1 x1 ， x2 0b2：解：解（1，7/3 ）z21 = 10/3b1：解：解（2，23/9 ）z11 = 41/912运筹学教程7（3/2 ，10/3）z1 = 29/6b1 max z = x1 + x2

4、14x1 + 9x2 51 - 6x1 + 3x2 1 x1 2 x1 ， x2 0b2：解：解（1，7/3 ）z21 = 17/3b1：解：解（2，23/9 ）z11 = 41/9b11 max z = x1 + x2 14x1 + 9x2 51 - 6x1 + 3x2 1 x1 2 x2 3 x1 ， x2 0b12 max z = x1 + x2 14x1 + 9x2 51 - 6x1 + 3x2 1 x1 2 x2 2 x1 ， x2 0b12：解：解（33/14，2 ）z12 = 61/14运筹学教程8（3/2 ，10/3）z1 = 29/6b2：解：解（1，7/3 ）z21 = 1

5、0/3b12 max z = x1 + x2 14x1 + 9x2 51 - 6x1 + 3x2 1 x1 2 x2 2 x1 ， x2 0b12：解：解（33/14，2 ）z12 = 61/14b121 max z = x1 + x2 14x1 + 9x2 51 - 6x1 + 3x2 1 x1 3 x2 2 x1 ， x2 0b122 max z = x1 + x2 14x1 + 9x2 51 - 6x1 + 3x2 1 2 x1 2 x2 2 x1 ， x2 0b121：解：解（3，1 ）z121 = 4b122：解：解（2，2 ）z122 = 4b1：解：解（2，23/9 ）z11 =

6、 41/9运筹学教程说明:求极小问题时，求极小问题时，lp问题的解是问题的解是ip问题的下界。每次分问题的下界。每次分后的子后的子问题最优解的目标函数值都大于或等于分问题最优解的目标函数值都大于或等于分前的最优值。如分前的最优值。如分中得到整数解，则最小的整数解为上界。如分中得到整数解，则最小的整数解为上界。如分的目标函数的目标函数值大于上界，则停止分值大于上界，则停止分。运筹学教程ax1=3/2,x2=10/3z=29/6bx1=2,x2=23/9z=41/9cx1=1,x2=7/3z=10/3无可行解dx1=33/14,x2=2z=61/14fx1=2,x2=2z=4ex1=3,x2=1z

7、=4运筹学教程 运筹学教程第四节第四节 0101型整数规划型整数规划tnttnttnjjjjjjjjnaaaaxxaeaexaaeeeex）选择（）选择（选择选择有两种选择每项有限要素变量描述。种选择，用每项要素有问题含有较多的要素，当决策不选取方案当决策选取方案选取某个特定方案,.1,)0,.,1 , 1 (:,.1,) 1,.,1 , 1 (),.(, 0, 1,.2, 1102, 0, 11运筹学教程一、一、01规划数学模型规划数学模型例：固定费用问题有三种资源被用于生产三种产品，资源量、产品单件费用、资源消耗量以及生产产品的固定费用。要求制定一个生产计划，总收益最大。消耗产品1产品2产

8、品3资源量a248500b234300c123100单件费用 456固定费用 100150200单件售价 81012产品资源运筹学教程解：xj是生产第j种产品的产量。总收益等于销售减去所生产的产品的总费用。建立数学模型时，无法确定某种产品是否生产，不能确定相应的固定费用是否发生，用0-1变量解决此问题。34,50,100,01010032300432500842.200150100654max0, 00, 1321333222111321321321321321mmmxmyxymxymxymxxxxxxxxxxstyyyxxxzxjxjyjjjjjjj件，例如根据第三个约束条的上界为或且为整数

9、）种产品（不生产第）种产品（生产第分析：jj jjjjjjjjjj运筹学教程例例 含有相互排斥的约束条件的问题含有相互排斥的约束条件的问题设工序设工序b的每周工时约束条件为的每周工时约束条件为0.3x1+0.5x2150,式式(1)现有一新的加工方式现有一新的加工方式,相应的每周工时约束条件为相应的每周工时约束条件为0.2x1+0.4x2120 ,式式(2)如果工序如果工序b只能选择一种只能选择一种,那么那么(1)和和(2)变成相互排斥的约束条件变成相互排斥的约束条件.不采用新加工方式采用新加工方式不采用原加工方式采用原加工方式bbybby,1,0,1,02111204.02.01505.03

10、.0.21221121yymyxxmyxxst当当y1=1,y2=0;采用采用新工艺新工艺,(2)式成立式成立;多余的约束多余的约束运筹学教程),.,2 , 1(, 1),.,2 , 1(, 010),.,2 , 1(1piipiiyipqpibxappjijij个约束条件不选择第个约束条件选择第变量个个约束条件，引入选择个约束条件约束条件组约束条件组),.,2 , 1(.11piqpymybxastpiinjiijij在约束条件中保证了在在约束条件中保证了在p个个0-1变量中有变量中有p-q个个1,q个个0;凡取值凡取值=0的的yi对应的约束条件为原约束对应的约束条件为原约束条件条件,凡取值

11、凡取值=1的的yi对应的约束对应的约束条件将自然满足条件将自然满足,因而为多余因而为多余.运筹学教程例例 工件排序问题工件排序问题使用使用4台机床加工台机床加工3件产品件产品.各个产品的机床加工顺序以及产品各个产品的机床加工顺序以及产品i在机床在机床j上的加工时间上的加工时间 aij见表见表.由于某种原因由于某种原因,产品产品2的加工总工时不得超过的加工总工时不得超过d.现现在要求各件产品在机床上的加工方案在要求各件产品在机床上的加工方案,使在最段时间内加工完全部产品使在最段时间内加工完全部产品.产品1a11 a13 a14机床1 机床3 机床4产品2a21 a23 a24机床1 机床2 机床

12、4产品3 a32 a33 机床2 机床3运筹学教程解解 设设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.每一台机床对不同产品的加工顺序约

13、束每一台机床对不同产品的加工顺序约束一台机床在工作中一台机床在工作中,如果已经开始加工还没有结束如果已经开始加工还没有结束,则不能开始加工另一件产则不能开始加工另一件产品品.对于机床对于机床1,先加工先加工1不能加工不能加工2.为了容纳两种相互排斥的约束条件为了容纳两种相互排斥的约束条件,对于每台机床对于每台机床,分别引入分别引入0-1变量变量:运筹学教程）（，先加工另外产品先加工某种产品4 , 3 , 2 , 11, 0jyj机床机床1:x11+a11x21+my1 ; x21+a21x11+m(1-y1) 机床机床2:x22+a22x32+my2 ; x32+a32x22+m(1-y2)机

14、床机床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-x21d4.目标函数的建立目标函数的建立由于三件产品的加工时间分别为由于三件产品的加工时间分别为x14+a14,x

15、24+a24,x33+a33,全部产品的实际全部产品的实际加工时间为加工时间为:w=max(x14+a14,x24+a24,x33+a33)minz=w st. wx14+a14, w x24+a24, w x33+a33.运筹学教程01,)(24)(22)(24)(22.523max103213221321321321orxxxdxxcxxbxxxaxxxstxxxz整数规划例：求解运筹学教程解：求解过程可以列表表示：(x1,x2,x3)z值 约束条件过滤条件abcd(0,0,0)0z 0(0,0,1)5z 5(0,1,0)-2(0,1,1)3(1,0,0)3(1,0,1)8z 8(1,1,0)1(1,1,1)6运筹学教程01,5358462173.73min4321421432143214321orxxxxxxxxxxxxxxxstxxxxz01,5358462173.37min4321421432143213412orxxxxxxxxxxxxxxxstxxxxz运算运算36次次运算运算30次次运筹学教程练习练习1:使用分支定界法求解整数规划使用分支定界法求解整数规划且为整数, 0,212605.2max2121212121xxxxxxxxstxxz松弛问题的最优解松弛问题的最优解x=(2.75,2.25)t运筹学教程cj21000cbxbbx1x2x3x