第十五章整数(线性)规划 ◆分枝定界法 ◆割平面法
第十五章 整数(线性)规划 ◆分枝定界法 ◆割平面法
整数(线性)规划(Integer Programming,P) 在线性规划问题的讨论中,有些最优解是小数,但 某些常要求最优解是整数(即整数解) 如决策变量是: 机器的台数、人数、车辆数等等 如果在问题中所有变量有整数限制,称:纯整数规划 或全整数规划) 如果问题中仅部分变量有整数限制,称:混合整数规划; 如果在问题中决策变量仅取0,1,称:0-1规划
整数(线性)规划 (Integer Programming, IP) 在线性规划问题的讨论中,有些最优解是小数,但 某些常要求最优解是整数(即整数解) 如决策变量是: 机器的台数、人数、车辆数等等 如果在问题中所有变量有整数限制,称:纯整数规划 (或全整数规划); 如果问题中仅部分变量有整数限制,称:混合整数规划; 如果在问题中决策变量仅取0,1,称:0-1规划
例1(装载问题)某长拟用集装箱托运甲乙两种货物, 每箱的体积、重量、可获利润,及托运限制如表, 问两种货物各托运多少箱,可获利最大。 货物 每箱体积 每箱重量 每箱利润 (百斤) 甲 5 2 20 乙 4 5 10 托运限制 24 13
例1(装载问题)某长拟用集装箱托运甲乙两种货物, 每箱的体积、重量、可获利润,及托运限制如表, 问两种货物各托运多少箱,可获利最大。 货物 每箱体积 每箱重量 (百斤) 每箱利润 甲 5 2 20 乙 4 5 10 托运限制 24 13
解:设x1,x2分别为甲、乙两种货物托运箱 数,则: max Z三20X1+10X2 s.t. 5x1+4X2≤24 2X1+5x2≤13 x1≥0,x2≥0.x1,x2为整数 这是一个纯整数规划问题
解: 设x1,x2分别为甲、乙两种货物托运箱 数,则: max Z = 20 x1 + 10 x2 s.t. 5x1 + 4x2 ≤ 24 2 x1 + 5x2 ≤ 13 x1 ≥ 0,x2 ≥ 0 .x1,x2为整数 这是一个纯整数规划问题
例2(背包问题,投资问题 假设有人要出发旅行,他拟考虑带七种。每种物品的重量与 价值,如表。现在假设他最多能带35kg物品,问该带哪几 件物品,总价值最大? 物品 重量a 价值C 1 2 34 12 12 3 3 9 4 3 15 5 15 90 6 13 26 7 16 112
例2(背包问题,投资问题) 假设有人要出发旅行,他拟考虑带七种。每种物品的重量与 价值,如表。现在假设他最多能带35 kg物品,问该带哪几 件物品,总价值最大? 物品 重量aj 价值Cj 1 3 12 2 4 12 3 3 9 4 3 15 5 15 90 6 13 26 7 16 112
解: 如果带第种物品 否 max=∑c j=1 s.t. ∑ax≤8 x,=0或1 (0=1~7) 这是一个0-1规划问题
解: = 否 如果带第 种物品 0 1 j xj 0或1 ( 1 ~ 7) . . max 7 1 7 1 = = = = = x j st a x b Z C x j j j j j j j 这是一个0-1规划问题
对P问题,可能会认为,只要求出不受整数约 束的解,然后“舍入化整”,就可得到整数最 优 解,是这样吗? 其实,这样的方法常常是行不通的。 下面通过整数规划的求解来说明
对IP问题,可能会认为,只要求出不受整数约 束的解,然后“舍入化整”,就可得到整数最 优 解,是这样吗? 其实,这样的方法常常是行不通的。 下面通过整数规划的求解来说明
图解法 类似于工维的线性规划问题的图解法,二维的整数规 ×2 划问题也有相应的图解法。 装载问题为例: max Z=20X1+10X2 s.t.5x1+4x2≤24 2X1+5x2≤13 1≥0,x2≥0.x1,X2为整 数 最优:x1=4,x2=1,Zmax=90 求解得:x1=4.8,x2=0,Zmax=96 考虑化整 X1=5,X2=0,不可行 X1=4,x2=0,Z=80
图解法 类似于二维的线性规划问题的图解法,二维的整数规 划问题也有相应的图解法。 装载问题为例: max Z = 20 x1 + 10 x2 s.t. 5x1 + 4x2 ≤ 24 2 x1 + 5x2 ≤ 13 x1 ≥ 0,x2 ≥ 0 .x1,x2为整 数 5 2 1 0 1 2 3 4 3 L1 L2 x1 x2 A B C 求解得:x1=4.8,x2=0,Zmax=96 考虑化整 x1=5,x2=0,不可行 x1=4,x2=0,Z=80 最优:x1=4,x2=1,Zmax=90
上例得到的启示1 (1)化整后未必是可行解 2 即使是可行解,也未必是最优解 3) 即使该方法结果可以得到最优解, 但如果有n个决策变量,则取舍方案有 2n种。当n=60时,260约等于1018,这使 计算机也难以实现。 所以,有必要讨论整数规划的求解方法
上例得到的启示1: (1)化整后未必是可行解 (2)即使是可行解,也未必是最优解 (3)即使该方法结果可以得到最优解, 但如果有n个决策变量,则取舍方案有 2n种。当n=60时,2 60约等于1018,这使 计算机也难以实现。 所以,有必要讨论整数规划的求解方法
启示2 (1)是否能在LP的约束区域中切去几块不 含整数解的可行域,使整数解作为顶点,这 样求LP问题的最优解,即为整数解 如前例,增加约束x1≤4,则LP问题的 最优解,即为x1=4,x2=1,ZmaX=90,就是 IP问题的解 (2)在LP的可行域中,整数点不多时(12 个),是否可以用穷举法
启示2: (1)是否能在LP的约束区域中切去几块不 含整数解的可行域,使整数解作为顶点,这 样求LP问题的最优解,即为整数解。 如前例,增加约束x1 ≤4,则LP问题的 最优解,即为x1=4,x2=1,Zmax=90,就是 IP问题的解。 (2)在LP的可行域中,整数点不多时(12 个),是否可以用穷举法