运筹学分支定界法-0-1整数规划课件.ppt

运筹学教程第三节第三节 分支定界法分支定界法 （Branch and Bound，简称简称B&B）基本思想如下：基本思想如下：基本思想如下：基本思想如下：首先不考虑变量的整数约束，求解相应的线性规首先不考虑变量的整数约束，求解相应的线性规首先不考虑变量的整数约束，求解相应的线性规首先不考虑变量的整数约束，求解相应的线性规划问题，得到线性规划的最优解。划问题，得到线性规划的最优解。划问题，得到线性规划的最优解。划问题，得到线性规划的最优解。设线性规划问题：设线性规划问题：设线性规划问题：设线性规划问题：最优解为最优解为最优解为最优解为Z Z。则。则。则。则Z Z为为为为I IP P问题解问题解问题解问题解Z*Z*的上界的上界的上界的上界，Z*Z*ZZ。运筹学教程 它的可行域为图中它的可行域为图中它的可行域为图中它的可行域为图中OABCDEOABCDE（示意图），并设最优解位于示意图），并设最优解位于示意图），并设最优解位于示意图），并设最优解位于C C。如果这个最优解中所有的如果这个最优解中所有的如果这个最优解中所有的如果这个最优解中所有的变量都是整数，则已经得到整变量都是整数，则已经得到整变量都是整数，则已经得到整变量都是整数，则已经得到整数规划的最优解。如果其中某数规划的最优解。如果其中某数规划的最优解。如果其中某数规划的最优解。如果其中某一个变量一个变量一个变量一个变量XrXr不是整数，则在可不是整数，则在可不是整数，则在可不是整数，则在可行域中除去一块包含这个最优行域中除去一块包含这个最优行域中除去一块包含这个最优行域中除去一块包含这个最优解但不包含任何整数解的区域解但不包含任何整数解的区域解但不包含任何整数解的区域解但不包含任何整数解的区域I Ir r XrXr 0.0.约束条件约束条件约束条件约束条件x xj MMjy yj,y,yj=1;=1;如果不生产第如果不生产第如果不生产第如果不生产第j j种产品，种产品，种产品，种产品，x xj=0.=0.约束条件约束条件约束条件约束条件x xj MMjy yj,y yj=1=1或或或或0 0。当。当。当。当y yj=1=1不利于目不利于目不利于目不利于目标函数的最大化，因此在最标函数的最大化，因此在最标函数的最大化，因此在最标函数的最大化，因此在最优解必然是优解必然是优解必然是优解必然是y yj=0=0。运筹学教程例例 含有相互排斥的约束条件的问题含有相互排斥的约束条件的问题设工序设工序B的每周工时约束条件为的每周工时约束条件为0.3x1+0.5x2150,式式(1)现有一新的加工方式现有一新的加工方式,相应的每周工时约束条件为相应的每周工时约束条件为0.2x1+0.4x2120,式式(2)如果工序如果工序B只能选择一种只能选择一种,那么那么(1)和和(2)变成相互排斥的约束条件变成相互排斥的约束条件.当当y1=1,y2=0;采用采用新工艺新工艺,(2)式成立式成立;多余的约束多余的约束运筹学教程例例 选址问题选址问题 某公司在城市的东、西、南三区建立门市部。拟议某公司在城市的东、西、南三区建立门市部。拟议 中有中有 7 个位置（地点）个位置（地点）Ai（i=1，2，7）可供选择。可供选择。公司规定公司规定 在东区，由在东区，由 A1，A2，A3 三个点中至多选两个；三个点中至多选两个；在南区，由在南区，由 A4，A5 两个点中至少选一个；两个点中至少选一个；在西区，由在西区，由 A6，A7 两个点中至少选一个。两个点中至少选一个。如果选用如果选用 Ai 点，设备投资估计为点，设备投资估计为 bi 元，每年可获利元，每年可获利润估计为润估计为 ci元，但投资总额不能超过元，但投资总额不能超过 B 元。问公司选择元。问公司选择哪几个点可使年总利润最大？哪几个点可使年总利润最大？16运筹学教程建立模型建立模型 引入引入 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，或或117运筹学教程二、二、0-10-1型整数规划的解法型整数规划的解法求解思路：求解思路：求解思路：求解思路：检测可行解的目标函数值，根据其目标函数值可以产生一个检测可行解的目标函数值，根据其目标函数值可以产生一个检测可行解的目标函数值，根据其目标函数值可以产生一个检测可行解的目标函数值，根据其目标函数值可以产生一个过滤条件，对于目标函数数值比它差的变量组合删除，这样过滤条件，对于目标函数数值比它差的变量组合删除，这样过滤条件，对于目标函数数值比它差的变量组合删除，这样过滤条件，对于目标函数数值比它差的变量组合删除，这样有效减少运算次数，使最优解快速找到。有效减少运算次数，使最优解快速找到。有效减少运算次数，使最优解快速找到。有效减少运算次数，使最优解快速找到。运筹学教程解：求解过程可以列表表示：(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运筹学教程在求解在求解在求解在求解0-10-1整数规划问题，为了进一步减少运算量，常按照目标函数中整数规划问题，为了进一步减少运算量，常按照目标函数中整数规划问题，为了进一步减少运算量，常按照目标函数中整数规划问题，为了进一步减少运算量，常按照目标函数中各个变量系数的大小顺序重新排列各个变量，以便于最优解有可能较早各个变量系数的大小顺序重新排列各个变量，以便于最优解有可能较早各个变量系数的大小顺序重新排列各个变量，以便于最优解有可能较早各个变量系数的大小顺序重新排列各个变量，以便于最优解有可能较早出现。出现。出现。出现。对于最大化问题，可以按照从小到大的顺序排列；对于最大化问题，可以按照从小到大的顺序排列；对于最大化问题，可以按照从小到大的顺序排列；对于最大化问题，可以按照从小到大的顺序排列；对于最小化问题，可以按照从大到小的顺序排列；对于最小化问题，可以按照从大到小的顺序排列；对于最小化问题，可以按照从大到小的顺序排列；对于最小化问题，可以按照从大到小的顺序排列；运算运算36次次运算运算30次次运筹学教程练习练习1:使用分支定界法求解整数规划使用分支定界法求解整数规划松弛问题的最优解松弛问题的最优解X=(2.75,2.25)T运筹学教程Cj21000CBXBbX1X2X3X4X51X22.25 011.50-0.250X40.500-210.52X12.75 10-0.500.25Cj-zj00-0.50-0.25运筹学教程练习2：使用一等价的整数规划表述下面的问题运筹学教程运筹学教程n小结:n1、分支定界法的计算步骤。n2、0-1型整数规划的应用。n作业:n5.4(2)(用分支定界法)n5.5(1)