整数规划分枝定界法
整数规划 分枝定界法
整数规划在许多线性规划问题中，要求最优解必须取整数.例如、人数车辆船只数等.如果所得的解所求的解是机器的台数、中决策变量为分数或小数则不符合实际问题的要求对于一个规划问题,如果要求全部决策变量都取整数称为纯(或全)整数规划;如果仅要求部分决策变量取整数称为混合整数规划问题.有的问题要求决策变量仅取0或两个值，称为0-1规划问题整数规划简称为IP问题.这里主要讨论的是整数线性规划问题，简称为ILP问题
整 数 规 划 在许多线性规划问题中,要求最优解必须取整数.例如 所求的解是机器的台数、人数车辆船只数等.如果所得的解 中决策变量为分数或小数则不符合实际问题的要求. 对于一个规划问题,如果要求全部决策变量都取整数, 称为纯(或全)整数规划;如果仅要求部分决策变量取整数, 称为混合整数规划问题.有的问题要求决策变量仅取0或l两 个值,称为0-l规划问题. 整数规划简称为IP问题.这里主要讨论的是整数线性规 划问题,简称为ILP问题
对于整数线性规划问题,为了得到整数解,初看起来,似乎只要先不管整数要求,而求线性规划的解,然后将求得的非整数最优解“舍零取整”就可以了.但实际上，这个想法却常常行不通，有时“舍零取整”后的整数解根本就不是可行解，有虽然为可行解，却不是最优解例7.0.1某厂拟用集装箱托运甲乙两种货物，每箱的体积重量、可可获利润以及托运所受限制见表7.1.问每集装箱中两种货物各装多少箱，可使所获利润最大？
对于整数线性规划问题,为了得到整数解,初看起来,似乎只 要先不管整数要求,而求线性规划的解,然后将求得的非整 数最优解“舍零取整”就可以了.但实际上,这个想法却常常行 不通,有时“舍零取整”后的整数解根本就不是可行解,有虽 然为可行解,却不是最优解 . 例7.0.1 某厂拟用集装箱托运甲乙两种货物,每箱的体积、 重量、可获利润以及托 运所受限制见表7.1.问每集装箱中 两种货物各装多少箱,可使所获利润最大?
表 7.1货物/箱体积/米3重量/百斤利润/百元甲乙托运限制/集装箱解设x,分别为甲、乙两种货物的托运箱数.则这是一个纯整数规划问题.其数学模型为max Z = 20x +10x25x +4x2≤242xi +5x2 ≤13s.t3X,X≥0,整数
表 7.1 货物/箱 体积/米3 重量/百斤 利润/百元 甲 乙 托运限制/集 装箱 解 设 分别为甲、乙两种货物的托运箱数.则这是一个 纯整数规划问题 .其数学模型为: 1 2 x , x max 20 1 10 2 Z = x + x + + , 0,整数 2 5 13 5 4 24 . 1 2 1 2 1 2 x x x x x x st （1）
若暂且不考虑x，取整数这一条件.则(1)就变为下列线性规划：max Z = 20x; +10x25x +4x2 ≤24(2)2x +5x2 ≤13S.tX,X ≥0我们将式(2)称为(1)的伴随规划.解(2)得到最优解Z*= 96(3)x = 4.8,x2=0,但它不满足(1)的整数要求.因此它不是(1)的最优解,若把解(3)"舍零取整",如取X,=(5.0,0)T,但它不是式
若暂且不考虑 取整数这一条件.则(1)就变为下列 线性规划 : 1 2 x , x max 20 1 10 2 Z = x + x + + , 0 2 5 13 5 4 24 . 1 2 1 2 1 2 x x x x x x st （2） 我们将式(2)称为(1)的伴随规划.解(2)得到最优解: 4.8, * x1 = 0, * x2 = 96. * Z = （3） 但它不满足(1)的整数要求.因此它不是(1)的最优解,若把 解(3)"舍零取整",如取X1=(5.0,0)T ,但它不是式