西安建筑科技大学精品课程：《运筹学》电子教案_第四章 整数规划

第4章整数规划 4.1问题的提出 实际中很多问题的优化是用线性规划解决的,除特殊要求,其最优解非负即可,对 某些问题,最优解必须加整数要求。例如运货派出的车数,购买机器的台数,分配工作 需要的人数等。为整数要求的线性规划,称为整数规划( Integer Programming),简称 IP。IP的所有变量都要求是整数的,成为全整数规划( All Integer Programming),要 求变量非0即1的,称为0-1规划(0-1 Programming),下面就是一个整数规划的例 例4.1某公司承建一项工程需要大型设备,有两种型号可供选择,若选用第一种 类型,需配备司机一人,助手一人,施工一个小时可获利润20元,若选用第二种类型, 需配备司机一人,助手三人,施工一个小时可获利润30元。该公司可驾驶这类大型设 备的司机最多只能抽调五人,合适的助手只有六人。为了获得最大利润,应该怎样选用 大型设备? 设:选用“A”型设备x台,选用“B”型设备x2台,最优化模型为(舍去名数) x2 图4-1 max==20x, +30x (1) 约束条件{x +3x,≤6 (2) x,x2≥0 (3) x1,x2为整数 (4 对例1,若去掉整数要求,是一个典型的线性规划问题。其最优解是(图4-1的B

第 4 章 整数规划 4.1 问题的提出 实际中很多问题的优化是用线性规划解决的，除特殊要求，其最优解非负即可，对 某些问题，最优解必须加整数要求。例如运货派出的车数，购买机器的台数，分配工作 需要的人数等。为整数要求的线性规划，称为整数规划（Integer Programming），简称 IP。IP 的所有变量都要求是整数的，成为全整数规划（All Integer Programming），要 求变量非 0 即 1 的，称为 0—1 规划（0—1 Programming），下面就是一个整数规划的例 子。 例 4.1 某公司承建一项工程需要大型设备，有两种型号可供选择，若选用第一种 类型，需配备司机一人，助手一人，施工一个小时可获利润 20 元，若选用第二种类型， 需配备司机一人，助手三人，施工一个小时可获利润 30 元。该公司可驾驶这类大型设 备的司机最多只能抽调五人，合适的助手只有六人。为了获得最大利润，应该怎样选用 大型设备？ 设：选用“A”型设备 1 x 台，选用“B”型设备 2 x 台，最优化模型为（舍去名数）： , 9 1 2 2       C D B 1 x 2 x 1 2 x x + = 5 1 2 x x + = 3 6 0 A 图 4-1 1 2 1 2 1 2 1 2 1 2 max 20 30 5 3 6 , 0 , z x x x x x x x x x x = +  + ≤   + ≤  ≥    约束条件 为整数 （ （5） （1） 2） （3） （4） 对例 1，若去掉整数要求，是一个典型的线性规划问题。其最优解是（图 4-1 的 B

x1=4,x2=,max2=105 初看起来,这个最优解可以简单地舍入取得整数解,满足整数约束,即 x1=5,x2=1(或x1=4,x2=0)由图4-1知,它不是可行解,更谈不上最优解,这种方法不 可取。 那么,有约束条件(1)、(2)知,为保证解的可行性,必须使x≤5,x2≤2,则x的 取值可以是0,1,2,3,4,5,共计六个,x,的取值有0,1,2,共计三个。所以,该 问题的整数解共有3×6=18个,在它们中找处所有可行解,(由图4-1,可行域内除B点 以外的其它11个“点”都是整数可行解),分别代入目标函数,Z值最大所对应的解, 就是IP的最优解(D点x=3,x2=1,maxz=90)。 对于小型问题,变量很少,可行的整数解组合不太多,这种枚举的方法是可行的, 也是有效的。对于大型问题,可行的整数解是很多的,不宜采用此方法。例如指派问题, 其n=10时,指派方案就有10个,超过300万,若用枚举法,一开始就失去了优化原则。 4.2分枝定界法 分枝定界法( Branch and Bound methed)是由Land和Doig提出修正的,可用于 全部整数规划和部分整数规划。它首先求得相应的LP整数解(最优值=0),若有变量不 合整数约束要求,就任选其一,设xx=bx+fk(其中为bk整数,f为小数部分),把 原问题(可行域)分为两个分枝,既x≤b和x≥b+1,然后解分枝问题,若得到满 足约束的整数解,解题就到此为止。对极大化问题而言,其最优值Z以20为上界。若 仍未得到合于整数要求的解,就对分枝继续分解,直到求得最优整数解。 例4.2求 max z= 2x+x x 3x,≤0 x1+2x2≤2 6 x,x20,且为整数 不考虑整数约束,解相应LP得最优解表(表4-1)

点）: 1 2 1 1 4 , max 105 2 2 x x = = ， z = 初看起来，这个最优解可以简单地舍入取得整数解，满足整数约束，即 由图 4-1 知，它不是可行解，更谈不上最优解，这种方法不 可取。 1 2 x x = = 5, 1 1 2 （或x x = 4, = 0） 那么，有约束条件（1）、（2）知，为保证解的可行性，必须使 x x 1 ≤ 5, 2 ≤ 2，则 1 x 的 取值可以是 0，1，2，3，4，5，共计六个， 2 x 的取值有 0，1，2，共计三个。所以，该 问题的整数解共有3 6 × =18 个，在它们中找处所有可行解，（由图 4-1，可行域内除 B 点 以外的其它 11 个“点”都是整数可行解），分别代入目标函数，Z 值最大所对应的解， 就是 IP 的最优解（D 点 x x 1 2 = = 3, 1,max z = 90）。 对于小型问题，变量很少，可行的整数解组合不太多，这种枚举的方法是可行的， 也是有效的。对于大型问题，可行的整数解是很多的，不宜采用此方法。例如指派问题， 其 n=10 时，指派方案就有10!个，超过 300 万，若用枚举法，一开始就失去了优化原则。 4.2 分枝定界法 分枝定界法（Branch and Bound Methed）是由 Land 和 Doig 提出修正的，可用于 全部整数规划和部分整数规划。它首先求得相应的 LP 整数解（最优值 ），若有变量不 合整数约束要求，就任选其一，设 0 z ' K K K x = b + f （其中为 ' Kb 整数， Kf 为小数部分），把 原问题（可行域）分为两个分枝，既 ' K K x ≤ b 和 ，然后解分枝问题，若得到满 足约束的整数解，解题就到此为止。对极大化问题而言，其最优值 ' K K x b ≥ +1 Z '以 0 Z 为上界。若 仍未得到合于整数要求的解，就对分枝继续分解，直到求得最优整数解。 例 4.2 求： 1 2 1 2 1 2 1 2 1 2 max 2 5 3 0 . . 6 2 21 , Z x x x x x x s t x x x x = +  + ≤  − + ≤  + ≤    ≥ 0,且为整数 不考虑整数约束，解相应 LP 得最优解表（表 4-1）:

表4-1 2 0 0 基底 b9-41 0 X 0 0 0 最优解对应于图4-2的B点,它不满足整数约束要求,选x,使x≤2和x2≥3,把 可行域R分为两个部分R213及R2(2),原问题就被分为两个分枝,舍去了2<x1<3不合整 数约束的部分(见图4-3),第一个分枝(即R)增加新约束x≤2为2x4x54图 中第二分枝(即R)增加新约束x≥3为2455、1 4,新约束加入松弛变量x(或 x)后,分别列入原问题的最优解表,利用对偶单纯形法,求得最优解: 6x,+ xI x1+x,=5 R1 xI 图4-2

表 4-1 Cj 2 1 0 0 0 基底 b 1 x 2 x 3 x 4 x 5 x 2 x 9 4 0 1 3 2 0 1 4 − 4 x 1 2 0 0 −2 1 1 2 1 x 11 4 1 0 1 2 − 0 1 4 C Z j j − 3 7 4 0 0 1 2 − 0 1 4 − 最优解对应于图 4-2 的 B 点，它不满足整数约束要求，选 1 x ，使 ，把 可行域 1 2 x ≤ 2 3 和x ≥ R1分为两个部分 R2(1) 及R2(2)，原问题就被分为两个分枝，舍去了 不合整 数约束的部分（见图 4-3），第一个分枝（即 1 2 ≺ x ≺ 3 R2(1) ）增加新约束 1 x ≤ 2 为 3 5 1 1 2 4 x x − 3 4 ≤ − 图 中第二分枝（即 R2(2)）增加新约束 x1 ≥ 3为 3 5 1 1 2 4 x x 1 4 − + ≤ − ，新约束加入松弛变量 6 x（或 7 x ）后，分别列入原问题的最优解表，利用对偶单纯形法，求得最优解： 0 2 x 1 2 6 2 x x + = 21 1 2 −x x + = 0 C B 1 2 x x + = 5 R1 1 x 图 4-2

R(1) 2 图4-3 分枝2(1)(x1≤2) 分枝2(2)(x1≥3) max2= maxZ=7 xI x2=2(x5=5) 第二分枝(2(2)不合整数约束要求,需继续分解。把分枝(2(2)(即R2)分为两 部分,即x2≤1,和x2≥2,显然,x≥2分枝无可行解,x2≤1的分枝最优解是: maxZ=7,x=3,x2=1仍不合整数要求。以后的分枝及最优解见分枝树,图4-4 分枝树的第四层得到原问题的整数最优解: x=3,x2=1,maxZ=7 现在回头讨论一下,在分枝2(1)得到整数解后,为什么还要对分枝(2(2)继续分解? 因为分枝(2(2)的新分枝(3(1),其最优值(对极大化)的上界是7,大于分枝(2(2)的 最优值6,则新分枝(3(1)的最优值有可能大于6,所以要对分枝(2(2)继续分解。事实 上,分枝树已经给出答案。假设分枝(2(2)的值不是72,而是6或者更小,则新分枝的 最优值决不会大于6,那么就要舍去分枝(2(2),不再对其进行分解工作

2 x 3 C B 2 1 R1 (1) ( ) 2R 2 A 0 1 2 3 1 x 图 4-3 分枝 2(1) （ x1 ≤ 2 ） 分枝 2(2) （ x1 ≥ 3） 1 3 2 5 max 6 2 ( 1) 2 ( 5) Z x x x x = = = = = 1 4 2 4 1 max 7 2 1 3 ( ) 2 1 1 1 ( 1 2 2 Z x x x x = = = = = ) 第二分枝(2(2))不合整数约束要求，需继续分解。把分枝(2(2))（即 R2(2) ）分为两 部分，即 x2 ≤1,和x2 ≥ 2 ，显然， x2 ≥ 2分枝无可行解， 2 x ≤1的分枝最优解是： 1 2 1 1 max 7 , 3 , 1 3 6 Z x = = x = 仍不合整数要求。以后的分枝及最优解见分枝树，图 4-4。 分枝树的第四层得到原问题的整数最优解： 1 2 x x = = 3, 1,max Z = 7 现在回头讨论一下，在分枝 得到整数解后，为什么还要对分枝 继续分解？ 因为分枝 的新分枝 ，其最优值（对极大化）的上界是 2(1) (2(2)) (2(2)) (3(1)) 1 2 (2 7 ，大于分枝 的 最优值 6，则新分枝(3 的最优值有可能大于 6，所以要对分枝 继续分解。事实 上，分枝树已经给出答案。假设分枝(2 的值不是 (2(2)) (1)) (2)) (2)) 1 2 7 ，而是 6 或者更小，则新分枝的 最优值决不会大于 6，那么就要舍去分枝(2(2))，不再对其进行分解工作

原问题,不考虑整数约東 d2 x≤2 x≥3 分枝2(1)(R2a1) 分枝2(2)(R(2) Z=6 x Z=7 1 2 分枝3(1) 分枝3(2) 「无可行解 x1= 6 ≤3 4 分枝4(1) 分枝4(2) Z=7 x 无可行解 图4-4分枝树 4.3割平面法 割平面法(又称 Gomory法)的基本思想,是新增加一些线性(不等式)约束条件, 称为割平面,去“切割”相应的LP可行域,并使切掉部分都是非整数解,所有整数解 被保留下来。当这种割平面足够多时,使相应的LP(被保留下来的可行域)和原IP具 有相同的最优解。那么,相应LP的最优解也就是原IP的最优解。 4.3.1全部整数型运算方法 例43

原问题，不考虑整数约束 3 7 4 Z = 1 2 3 1 2 , 2 4 4 x = = x | | 1 x ≤ 2 1 x ≥ 3 分枝 2(1) 2(1) ( ) R Z = 6 1 2 2 2 x x = = 分枝 2(2) 2(2) ( ) R 1 7 2 Z = 1 2 3 1 1 2 x x = = 2 x ≤1 | | 2 x ≥ 2 分枝3(1) 1 7 3 Z = 1 2 1 3 6 1 x x = = 分枝3(2) 无可行解 | | 2 x ≤ 3 1 x ≥ 4 分枝 4(1) Z = 7 1 2 3 1 x x = = 分枝 4(2) 无可行解 图 4-4 分枝树 4.3 割平面法 割平面法（又称 Gomory 法）的基本思想，是新增加一些线性（不等式）约束条件， 称为割平面，去“切割”相应的 LP 可行域，并使切掉部分都是非整数解，所有整数解 被保留下来。当这种割平面足够多时，使相应的 LP（被保留下来的可行域）和原 IP 具 有相同的最优解。那么，相应 LP 的最优解也就是原 IP 的最优解。 4.3.1 全部整数型运算方法 例 4.3

maxZ=bx,+4x2 2x1+4x,≤13 x1+x2≤1 > x1,x2为整数 首先,将该问题的限制条件予以整数化,并加松弛变量。 maxZ=6x,+4 (5) 2x1+4x2+x3=13 (1) 2x1+x2=7 x≥0,j=12,34 x为整数 (4) 不考虑整数约束(4),用单纯形方法求解相应LP得最优解表(见表4-2) 表4-2 0 b x1 x2 x2 C x1不合整数要求,于是找(第一个)割平面(即考虑整数要求),由表得 XI x4为整数 使各系数均为正,有: 是整数,因为所有变量均为整数,则上式至少是一,则有: 11 ≥1 (6) x3+2x4≥3 (6)即为切割方程,其通式为:f+∑fkx21 其等式形式就是割平面,为了在图上表示,由约束(1)、(2)可以把(6)变为 x,+x、<4 (7)

1 2 1 2 1 2 1 2 1 2 max 6 4 2 4 13 1 1 1 . 3 6 , 0 , 1 6 Z x x x x x x s t x x x x = +  + ≤   + ≤   ≥   为整数 首先，将该问题的限制条件予以整数化，并加松弛变量。 （ 1 2 1 2 3 1 2 max 6 4 2 4 1 2 7 . 0, 1,2,3,4 j j Z x x x x x x x s t x j x = +  + + =  + =   ≥ =    为整数 3 （5） （1） 2） （3） （4） 不考虑整数约束（4），用单纯形方法求解相应 LP 得最优解表（见表 4-2）。 表 4-2 Cj 6 4 0 0 CB XB b 1 x 2 x 3 x 4 x 4 2 x 2 0 1 1 3 1 3 − 6 1 x 1 2 2 1 0 1 6 2 3 C Z j j − 0 0 1 3 − 2 2 3 − 1 x 不合整数要求，于是找（第一个）割平面（即考虑整数要求），由表得： 1 3 1 1 2 2 2 6 3 4 x = + x − x 为整数 使各系数均为正，有： 3 4 1 1 1 2 6 3 + x + x 是整数，因为所有变量均为整数，则上式至少是一，则有： 3 4 1 1 1 1 2 6 3 + + x x ≥ （6） 即 3 4 x x + ≥ 2 3 （6）即为切割方程，其通式为： 1 j jK K K f f +∑ x ≥ 其等式形式就是割平面，为了在图上表示，由约束（1）、（2）可以把（6）变为 1 2 x x + ≤ 4 （7）

(7)是切割方程的另一种表现形式,割平面就表示为:x+x2=4 它就是图4-5所表示的EF直线。直观地看,它割去了(除EF直线上的所有点) △EFB部分:x1+x2>4 其中不含整数(坐标)点。留下部分是:x+x24 即多边形 OAEFC,从图4-5看,所有整数(坐标)点都保留下来了。 B 图4-5 把切割方程作为新约束条件加入原问题,变为 nax Z=6x,+4x, 2x+4x2≤13 2x1+x2≤7 ≤4 x1,x2≥0 x12x2为整数 按上述步骤,解相应LP得最优解:x=3,x2=1,x=3,x4=x=0,maxZ=22 实际上就是F点。因为它已经满足整数约束,所以就是原IP的最优解。 割平面方程的另一种表达方法也是常用的,再经此法求解例3: 由表4-2知,x不满足整数约束,则 变为 (1+0)x1-1 移项 R x3+x4

（7）是切割方程的另一种表现形式，割平面就表示为： 1 2 x x + = 4 它就是图 4-5 所表示的 EF 直线。直观地看，它割去了（除 EF 直线上的所有点） ∆EFB 部分： x x 1 2 + > 4 其中不含整数（坐标）点。留下部分是： 1 2 x x + ≤ 4 即多边形OAEFC ，从图 4-5 看，所有整数（坐标）点都保留下来了。 2 x d E C 1 x 5 , 2 2       i c A B F 0 图 4-5 把切割方程作为新约束条件加入原问题，变为： 1 2 1 2 1 2 1 2 1 2 1 2 max 6 4 2 4 1 2 7 . 4 , 0 , 3 Z x x x x x x s t x x x x x x = +  + ≤  + ≤    + ≤  ≥   为整数 按上述步骤，解相应 LP 得最优解： 1 2 3 4 5 x x = 3, = = 1， ， x 3, x = x = 0 max Z = 22 。 实际上就是 F 点。因为它已经满足整数约束，所以就是原 IP 的最优解。 割平面方程的另一种表达方法也是常用的，再经此法求解例 3： 由表 4-2 知， 1 x 不满足整数约束，则 1 3 4 1 2 2 6 3 x x − + x = 1 2 变为 1 3 4 5 2 (1 0) 1 0 2 6 3 x x x     + −   − +  +  = +     1 2 移项： 1 3 3 4 1 5 2 2 2 6 3 x x x   − − = −   +   x

因为要求所有变量均为整数,则 x1-x3 为整数 2(6x+3亦为整数 又 2 6+x1为整数,所以有: 此即所求之切割方程,切割平面是 52 x3+,x4 (8)加入松弛变量x作为新约束条件,并入最优解表4-3,得 表4-3 C b Xu x2 2 6 0 6 4_545 2 由表4-3知,此不是可行解,需用对偶单纯形法继续求解。x为出基变量,由 下式确定进基变量为x3 B=m la<o 63 mIn 15 再按原单纯形法计算,得表4-4

因为要求所有变量均为整数，则 x x 1 3 − − 2 为整数， 3 1 5 2 2 6 3 4 x x   − +    亦为整数， 又 3 5 2 6 3 4 x + x 为整数，所以有： 3 4 1 5 2 0 2 6 3 x x   − +   ≤   即 3 4 5 2 6 3 − − x x ≤ 1 2 （8） 此即所求之切割方程，切割平面是： 3 4 5 2 6 3 x x 1 2 + ≥ （8）加入松弛变量 5 x 作为新约束条件，并入最优解表 4-3，得 表 4-3 Cj 6 4 0 0 0 CB XB b 1 x 2 x 3 x 4 x 5 x 4 2 x 2 0 1 1 3 3 5 − 0 6 1 x 2 5 1 0 1 6 − 4 5 0 0 5 x 1 2 − 0 0 5 6 − 4 5 1 C Z j j − 0 0 1 3 − 2 2 3 − 0 由表 4-3 知，此不是可行解，需用对偶单纯形法继续求解。 5 x 为出基变量，由 下式确定进基变量为 3 x ： 1 2 2 3 3 min | 0 min , 5 2 6 3 j j ij j j ij C Z a a θ   −   −   = <   =       − −   − 6 6 min ,4 j 15 15   = =     再按原单纯形法计算，得表 4-4

表4-4 4 b x3 000 6 0 C.-Z 12 0 由表4-4知,基变量均为非整数,需找新的切割方程,取b列中纯分数值(部 分)最大的(x2)得:x2-5535x2-x-、4/2 x1+2x等式两 端均为整数,且要求x都为整数,所以三x45 x为整数,则有 0 (9) 即为新的切割方程。新的切割平面是-2x-2x=-4把(9)加入松弛变量 x6,作为新的约束条件,加入表4-4得: 表45 0 X b x x3 X4 0 0 4 4 45252 0x251565252 0 C-Z 0 0 0 由表4-5知,所得为非可行解,按前面的办法,确定x6出基,x进基,继续按原单 纯形法进行迭代,得

表 4-4 Cj 6 4 0 0 0 CB XB b 1 x 2 x 3 x 4 x 5 x 4 2 x 4 1 5 0 1 0 3 5 − 2 5 6 1 x 3 2 5 1 0 0 4 5 1 5 − 0 3 x 3 5 0 0 1 4 5 6 5 − C Z j j − 0 0 0 12 5 − 2 5 − 由表 4-4 知，基变量均为非整数，需找新的切割方程，取b 列中纯分数值（部 分）最大的（ i 2 x ）得： 2 4 5 3 2 1 5 5 x x − + x = 2 5 即： 2 4 4 5 2 1 5 4 2 5 5 x x x   − − =   +   − x 等式两 端均为整数，且要求 j x 都为整数，所以 4 2 2 5 5 5 x + x 为整数，则有 4 5 4 2 2 0 5 5 5 − − x x ≤ （9） 即为新的切割方程。新的切割平面是： 4 5 2 2 5 5 x x 4 5 − − = − 把（9）加入松弛变量 6 x ，作为新的约束条件，加入表 4-4 得： 表 4-5 Cj 6 4 0 0 0 0 CB XB b 1 x 2 x 3 x 4 x 5 x 6 x 4 2 x 4 1 5 0 1 0 3 5 − 2 5 0 6 1 x 3 2 5 1 0 0 4 5 1 5 − 0 0 3 x 3 5 0 0 1 4 5 6 5 − 0 0 6 x 4 5 − 0 0 0 2 5 − 2 5 − 1 C Z j j − 0 0 0 12 5 − 2 5 − 0 由表 4-5 知，所得为非可行解，按前面的办法，确定 6 x 出基， 5 x 进基，继续按原单 纯形法进行迭代，得：

表4-6 6 0 0 C X X1 x1 0 3 0 23521 (22) 0 检验数均为负,基变量均为正整数,所得为最优解,即为最优解, maxZ=22,X=(3,1,3,0,2 为了便于学习,把割平面法步骤小结于下 1.把整数规划约束不等式的变量系数a和常量b全部整数化,然后加入松弛变量, 且暂不考虑整数约束条件,用单纯形法解相应线性规划得到最优解 2.求割平面 2.1设x为相应线性规划最优解中有分数值的一个变量,并且真分数部分是最大 的,以非基变量表示为 x=b+∑bx 其中:∈B(B是基变量下标集合) k∈K(K是非基变量下标集合) 22将b和b都分解成整数部分N和非整数部分f之和,(N不大于的b最大整 数) b=N+f这里0<f<1 bn=Nk+f这里0<f<1 例如 b=2,则N=2,∫ 则N=-1,f 于是x表示为: x=N+∑N4x+f+∑瓜x

表 4-6 Cj 6 4 0 0 0 0 CB XB b 1 x 2 x 3 x 4 x 5 x 6 x 4 2 x 1 0 1 0 −1 0 1 6 1 x 3 1 0 0 1 0 1 2 − 0 3 x 3 0 0 1 2 0 −3 0 5 x 2 0 0 0 1 1 5 2 − C Z j j − （22） 0 0 0 −2 0 −1 检验数均为负，基变量均为正整数，所得为最优解，即为 IP 最优解， ( ) * max Z X = = 22, 3,1,3,0,2,0 为了便于学习，把割平面法步骤小结于下： 1.把整数规划约束不等式的变量系数 和常量 全部整数化，然后加入松弛变量， 且暂不考虑整数约束条件，用单纯形法解相应线性规划得到最优解； ij a i b 2.求割平面： 2.1 设 i x 为相应线性规划最优解中有分数值的一个变量，并且真分数部分是最大 的，以非基变量表示为： i i ik k x = + b ∑b xk （1） 其中： ( ) ( ) i B B k K K ∈ ∈ 是基变量下标集合 是非基变量下标集合 2.2 将bi 和bik 都分解成整数部分 N 和非整数部分 f 之和，（ 不大于的 最大整 数）： N b 0 1 0 1 i i i i ik ik ik ik b N f f b N f f = + < < = + < < 这里 这里 例如： 1 1 2 , 2, 2 2 b N = 则 = f = 1 5 , 1, 6 6 b N = − 则 = − f = 于是 i x 表示为： i ik k i k k ik k x = + N N ∑ x + f +∑ f x （2）