运筹学分支定界法 0-1整数规划

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运筹学教程 。 运筹学教程整数规划问题的求解方法整数规划问题的求解方法分支定界法图解整数规划分支定界法图解整数规划 松弛问题松弛问题 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 ， X2 0该整数规划松弛问题的解为：该整数规划松弛问题的解为：（X1 ，X2 ）= （3/2 ，10/3）Z1 = 29/

3、6运筹学教程松弛问题松弛问题 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运筹学教程（3/2 ，10/3）Z1 = 29/6B1 Max Z = X1

4、+ X2 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运筹学教程（3/2 ，10/3）Z1 = 29/6B2：解：解（1，7/3 ）Z21

5、 = 10/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 ）Z

6、11 = 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,X

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

8、品1产品2产品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.01

10、505.03.0.21221121yyMyxxMyxxst当当y1=1,y2=0;采用采用新工艺新工艺,(2)式成立式成立;多余的约束多余的约束运筹学教程例例 选址问题选址问题 某公司在城市的东、西、南三区建立门市部。拟议某公司在城市的东、西、南三区建立门市部。拟议 中有中有 7 个位置（地点）个位置（地点）Ai（i=1，2，7）可供选择。）可供选择。公司规定公司规定 在东区，由在东区，由 A1，A2，A3 三个点中至多选两个；三个点中至多选两个； 在南区，由在南区，由 A4，A5 两个点中至少选一个；两个点中至少选一个； 在西区，由在西区，由 A6，A7 两个点中至少选一个。两个点中至少选一

11、个。 如果选用如果选用 Ai 点，设备投资估计为点，设备投资估计为 bi 元，每年可获元，每年可获利润估计为利润估计为 ci元，但投资总额不能超过元，但投资总额不能超过 B 元。问公司选元。问公司选择哪几个点可使年总利润最大？择哪几个点可使年总利润最大？运筹学教程建立模型建立模型 引入引入 0-1 变量变量 1 当当 Ai 点被选用点被选用 0 当当 Ai 没点被选用没点被选用xi =（i=1，2，7）max z = cixi bixi B x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 xi = 0，或，或1运筹学教程01,)(24)(22)(24)(22.523max

12、103213221321321321orxxxdxxcxxbxxxaxxxstxxxZ整数规划例：求解运筹学教程解：求解过程可以列表表示：(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运筹学教程Cj21000CBXBbX1X2X3X4X51X22.25 011.50-0.250X40.500-210.52X12.75 10-0.500.25Cj-zj00