第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