同济大学：《运筹学》课程教学资源（PPT课件讲稿）整数（线性）规划

第十五章整数（线性）规划 ◆分枝定界法 ◆割平面法

第十五章 整数(线性)规划 ◆分枝定界法 ◆割平面法

整数（线性）规划(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，这使 计算机也难以实现。 所以，有必要讨论整数规划的求解方法

上例得到的启示１： （１）化整后未必是可行解 （２）即使是可行解，也未必是最优解 （３）即使该方法结果可以得到最优解， 但如果有n个决策变量，则取舍方案有 ２n种。当n=60时，2 60约等于1018，这使 计算机也难以实现。 所以，有必要讨论整数规划的求解方法

启示2 (1)是否能在LP的约束区域中切去几块不 含整数解的可行域，使整数解作为顶点，这 样求LP问题的最优解，即为整数解 如前例，增加约束x1≤4，则LP问题的 最优解，即为x1=4,x2=1,ZmaX=90,就是 IP问题的解 (2)在LP的可行域中，整数点不多时(12 个)，是否可以用穷举法

启示２： （１）是否能在LP的约束区域中切去几块不 含整数解的可行域，使整数解作为顶点，这 样求LP问题的最优解，即为整数解。 如前例，增加约束x1 ≤4，则LP问题的 最优解，即为x1=4,x2=1,Zmax=90，就是 IP问题的解。 （２）在LP的可行域中，整数点不多时（12 个），是否可以用穷举法