《运筹学课件-第三节-分支定界法》由会员分享，可在线阅读，更多相关《运筹学课件-第三节-分支定界法（28页珍藏版）》请在金锄头文库上搜索。
1、运筹学教程第三节第三节 分支定界法分支定界法 （Branch and Bound， 简称简称B&B） 基本思想如下：基本思想如下：基本思想如下：基本思想如下： 首先不考虑变量的整数约束，求解相应的线性规首先不考虑变量的整数约束，求解相应的线性规首先不考虑变量的整数约束，求解相应的线性规首先不考虑变量的整数约束，求解相应的线性规划问题，得到线性规划的最优解。划问题，得到线性规划的最优解。划问题，得到线性规划的最优解。划问题，得到线性规划的最优解。 设线性规划问题：设线性规划问题：设线性规划问题：设线性规划问题： 最优解为最优解为最优解为最优解为Z Z。则。则。则。则Z Z为为为为I IP P问题
2、解问题解问题解问题解Z*Z*的上界的上界的上界的上界，Z*ZZ*Z。2021/6/71运筹学教程 它的可行域为图中它的可行域为图中它的可行域为图中它的可行域为图中OABCDEOABCDE（示意图），并设最优解位于（示意图），并设最优解位于（示意图），并设最优解位于（示意图），并设最优解位于C C。如果这个最优解中所有的。如果这个最优解中所有的。如果这个最优解中所有的。如果这个最优解中所有的变量都是整数，则已经得到整变量都是整数，则已经得到整变量都是整数，则已经得到整变量都是整数，则已经得到整数规划的最优解。如果其中某数规划的最优解。如果其中某数规划的最优解。如果其中某数规划的最优解。如果其中某
3、一个变量一个变量一个变量一个变量XrXr不是整数，则在可不是整数，则在可不是整数，则在可不是整数，则在可行域中除去一块包含这个最优行域中除去一块包含这个最优行域中除去一块包含这个最优行域中除去一块包含这个最优解但不包含任何整数解的区域解但不包含任何整数解的区域解但不包含任何整数解的区域解但不包含任何整数解的区域I IrXrrXr0.0.约束条件约束条件约束条件约束条件x xj MMjy yj,y,yj=1;=1;如果不生产第如果不生产第如果不生产第如果不生产第j j种产品，种产品，种产品，种产品，x xj=0.=0.约束条件约束条件约束条件约束条件x xj MMjy yj, ,y yj=1=1
4、或或或或0 0。当。当。当。当y yj=1=1不利于目不利于目不利于目不利于目标函数的最大化，因此在最标函数的最大化，因此在最标函数的最大化，因此在最标函数的最大化，因此在最优解必然是优解必然是优解必然是优解必然是y yj=0=0。2021/6/714运筹学教程例例 含有相互排斥的约束条件的问题含有相互排斥的约束条件的问题设工序设工序B的每周工时约束条件为的每周工时约束条件为0.3x1+0.5x2150,式式(1)现有一新的加工方式现有一新的加工方式,相应的每周工时约束条件为相应的每周工时约束条件为0.2x1+0.4x2120 ,式式(2)如果工序如果工序B只能选择一种只能选择一种,那么那么(
5、1)和和(2)变成相互排斥的约束条件变成相互排斥的约束条件.当当y1=1,y2=0;采用采用新工艺新工艺,(2)式成立式成立;多余的约束多余的约束2021/6/715运筹学教程约束条件组约束条件组在约束条件中保证了在在约束条件中保证了在P个个0-1变量中有变量中有p-q个个1,q个个0;凡取值凡取值=0的的yi对应的约束条件为原约束条对应的约束条件为原约束条件件,凡取值凡取值=1的的yi对应的约束条对应的约束条件将自然满足件将自然满足,因而为多余因而为多余.2021/6/716运筹学教程例例 工件排序问题工件排序问题使用使用4台机床加工台机床加工3件产品件产品.各个产品的机床加工顺序以及产品各
6、个产品的机床加工顺序以及产品i在机床在机床j上的加工时间上的加工时间 aij见表见表.由于某种原因由于某种原因,产品产品2的加工总工时不得超过的加工总工时不得超过d.现现在要求各件产品在机床上的加工方案在要求各件产品在机床上的加工方案,使在最段时间内加工完全部产品使在最段时间内加工完全部产品.产品1a11 a13 a14机床1 机床3 机床4产品2a21 a23 a24机床1 机床2 机床4产品3 a32 a33 机床2 机床32021/6/717运筹学教程解解 设设xij表示产品表示产品i在机床在机床j 上开始加工的时间上开始加工的时间(i=1,2,3;j=1,2,3,4)1.同一件产品在不
7、同机床上的加工顺序约束同一件产品在不同机床上的加工顺序约束同一件产品在下一台机床上的加工的开始时间不早于在上一台机床上加工同一件产品在下一台机床上的加工的开始时间不早于在上一台机床上加工的结束时间的结束时间,故应有故应有产品产品1:x11+a11x12 ; x13+a13x14产品产品2:x21+a21x22 ; x23+a23x24 产品产品3:x32+a32x33 ; 2.每一台机床对不同产品的加工顺序约束每一台机床对不同产品的加工顺序约束一台机床在工作中一台机床在工作中,如果已经开始加工还没有结束如果已经开始加工还没有结束,则不能开始加工另一件产则不能开始加工另一件产品品.对于机床对于机
8、床1,先加工先加工1不能加工不能加工2.为了容纳两种相互排斥的约束条件为了容纳两种相互排斥的约束条件,对于每台机床对于每台机床,分别引入分别引入0-1变量变量:2021/6/718运筹学教程机床机床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,后加工产品后加工产品
9、2;当当y1=1,表示机床表示机床1先先加工产品加工产品2,后加工产品后加工产品1.3.产品产品2的加工总时间约束的加工总时间约束产品产品2的开始加工时间的开始加工时间x21,结束加工时间为结束加工时间为x24+a24,所以所以x24+a24-x21d4.目标函数的建立目标函数的建立由于三件产品的加工时间分别为由于三件产品的加工时间分别为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.2021/6/71
10、9运筹学教程二、二、0-10-1型整数规划的解法型整数规划的解法求解思路：求解思路：求解思路：求解思路：检测可行解的目标函数值，根据其目标函数值可以产生一个检测可行解的目标函数值，根据其目标函数值可以产生一个检测可行解的目标函数值，根据其目标函数值可以产生一个检测可行解的目标函数值，根据其目标函数值可以产生一个过滤条件，对于目标函数数值比它差的变量组合删除，这样过滤条件，对于目标函数数值比它差的变量组合删除，这样过滤条件，对于目标函数数值比它差的变量组合删除，这样过滤条件，对于目标函数数值比它差的变量组合删除，这样有效减少运算次数，使最优解快速找到。有效减少运算次数，使最优解快速找到。有效减少
11、运算次数，使最优解快速找到。有效减少运算次数，使最优解快速找到。2021/6/720运筹学教程解：求解过程可以列表表示：(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)62021/6/721运筹学教程在求解在求解在求解在求解0-10-1整数规划问题，为了进一步减少运算量，常按照目标函数中整数规划问题，为了进一步减少运算量，常按照目标函数中整数规划问题，为了进一步减少运算量，常按照目标函数中整数规划问题，为了进一步减少运算量，常按照目标函数中各个变量
12、系数的大小顺序重新排列各个变量，以便于最优解有可能较早各个变量系数的大小顺序重新排列各个变量，以便于最优解有可能较早各个变量系数的大小顺序重新排列各个变量，以便于最优解有可能较早各个变量系数的大小顺序重新排列各个变量，以便于最优解有可能较早出现。出现。出现。出现。对于最大化问题，可以按照从小到大的顺序排列；对于最大化问题，可以按照从小到大的顺序排列；对于最大化问题，可以按照从小到大的顺序排列；对于最大化问题，可以按照从小到大的顺序排列；对于最小化问题，可以按照从大到小的顺序排列；对于最小化问题，可以按照从大到小的顺序排列；对于最小化问题，可以按照从大到小的顺序排列；对于最小化问题，可以按照从大
13、到小的顺序排列；运算运算36次次运算运算30次次2021/6/722运筹学教程练习练习1:使用分支定界法求解整数规划使用分支定界法求解整数规划松弛问题的最优解松弛问题的最优解X=(2.75,2.25)T2021/6/723运筹学教程Cj21000CBXBbX1X2X3X4X51X22.25 011.50-0.250X40.500-210.52X12.75 10-0.500.25Cj-zj00-0.50-0.252021/6/724运筹学教程练习2：使用一等价的整数规划表述下面的问题2021/6/725运筹学教程2021/6/726运筹学教程n小结:n1、分支定界法的计算步骤。n2、0-1型整数规划的应用。n作业:n5.7(1), 5.9(1) 2021/6/727运筹学教程部分资料从网络收集整理而来，供大家参考，感谢您的关注！
