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

1、运筹学教程 1 2021/6/7 （Branch and Bound， 简称简称B采用采用 新工艺新工艺,(2)式成立式成立; 多余的约束多余的约束 运筹学教程 16 2021/6/7 ),.,2 , 1(, 1 ),.,2 , 1(, 0 10 ),.,2 , 1( 1 pii pii yi pq pibxap p j ijij 个约束条件不选择第 个约束条件选择第 变量个个约束条件，引入选择 个约束条件 约束条件组约束条件组 ),.,2 , 1(. 1 1 pi qpy Mybxa st p i i n j iijij 在约束条件中保证了在在约束条件中保证了在P个个0-1 变量中有变量中有

2、p-q个个1,q个个0;凡取值凡取值 =0的的yi对应的约束条件为原约束对应的约束条件为原约束 条件条件,凡取值凡取值=1的的yi对应的约束对应的约束 条件将自然满足条件将自然满足,因而为多余因而为多余. 运筹学教程 17 2021/6/7 例例 工件排序问题工件排序问题 使用使用4台机床加工台机床加工3件产品件产品.各个产品的机床加工顺序以及产品各个产品的机床加工顺序以及产品i在机床在机床j 上的加工时间上的加工时间 aij见表见表.由于某种原因由于某种原因,产品产品2的加工总工时不得超过的加工总工时不得超过d.现现 在要求各件产品在机床上的加工方案在要求各件产品在机床上的加工方案,使在最段

3、时间内加工完全部产品使在最段时间内加工完全部产品. 产品1a11 a13 a14 机床1 机床3 机床4 产品2a21 a23 a24 机床1 机床2 机床4 产品3 a32 a33 机床2 机床3 运筹学教程 18 2021/6/7 解解 设设xij表示产品表示产品i在机床在机床j 上开始加工的时间上开始加工的时间(i=1,2,3;j=1,2,3,4) 1.同一件产品在不同机床上的加工顺序约束同一件产品在不同机床上的加工顺序约束 同一件产品在下一台机床上的加工的开始时间不早于在上一台机床上加工同一件产品在下一台机床上的加工的开始时间不早于在上一台机床上加工 的结束时间的结束时间,故应有故应有

4、 产品产品1:x11+a11x12 ; x13+a13x14 产品产品2:x21+a21x22 ; x23+a23x24 产品产品3:x32+a32x33 ; 2.每一台机床对不同产品的加工顺序约束每一台机床对不同产品的加工顺序约束 一台机床在工作中一台机床在工作中,如果已经开始加工还没有结束如果已经开始加工还没有结束,则不能开始加工另一件产则不能开始加工另一件产 品品.对于机床对于机床1,先加工先加工1不能加工不能加工2. 为了容纳两种相互排斥的约束条件为了容纳两种相互排斥的约束条件,对于每台机床对于每台机床,分别引入分别引入0-1变量变量: 运筹学教程 19 2021/6/7 ）（ ，先加

5、工另外产品 先加工某种产品 4 , 3 , 2 , 1 1 , 0 jy j 机床机床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的加

6、工总时间约束的加工总时间约束 产品产品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. 运筹学教程 20 2021/6/7 01, )(24 )(22 )(24 )(22 . 523max 10

7、 321 32 21 321 321 321 orxxx dxx cxx bxxx axxx st xxxZ 整数规划例：求解 运筹学教程 21 2021/6/7 解：求解过程可以列表表示： (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 运筹学教程 22 2021/6/7 01, 535 8462 173 . 73min 4321 421 4321 4321 4321 orxxxx xxx xxxx xxxx st xxxx

8、Z 01, 535 8462 173 . 37min 4321 421 4321 4321 3412 orxxxx xxx xxxx xxxx st xxxxZ 运算运算36次次 运算运算30次次 运筹学教程 23 2021/6/7 练习练习1:使用分支定界法求解整数规划使用分支定界法求解整数规划 且为整数, 0, 2126 0 5 . 2max 21 21 21 21 21 xx xx xx xx st xxz 松弛问题的最优解松弛问题的最优解X=(2.75,2.25)T 运筹学教程 24 2021/6/7 Cj21000 CBXBbX1X2X3X4X5 1X22.25 011.50-0.25 0X40.500-210.5 2X12.75 10-0.500.25 Cj-zj00-0.50-0.25 运筹学教程 25 2021/6/7 练习2：使用一等价的整数规划表述下面的问题 6410, 0 62 252 . 73max ，只能等于xy yx yx st yxz 运筹学教程 26 2021/6/7 01, 0 1 6410 62 252 . 73max 4321 4321 4321 oryyyy