第三章 整数规划
第3章 整数规划
Chapter 3 Integer Programming
本章内容提要
本章介绍整数规划模型以及整数规划的求解方法。 学习本章要求掌握以下要点： ?
掌握整数规划模型的建模方法 1、变量为整数的简单整数规划模型； 2、变量为0－1值的0－1规划模型；
3、用0－1变量以及相应的约束条件，定义变量之间逻辑关系的整数规划模型。
?
了解求解整数规划的两种方法—分支定界法和割平面法。
§3.1 整数规划模型
变量取整数值的规划称为整数规划。所有变量都取整数的规划称为纯整数规划，部分变量取整数的规划称为混合整数规划。所有变量都取0、1两个值的规划称为0-1规划，部分变量取0、1两个值的规划称为0-1混合规划。
线性规划和整数规划的关系，我们用以下例子说明。 设线性规划问题为 max s.t. max z= s.t.
z=
x1 -x1 x1 x1 -x1
+4x2
14x1 +42x2 ≤196
+2x2 ≤ 5 x2 +4x2
≥0
5 4 3 2 1 0 012A B 相应的整数规划问题为
14x1 +42x2 ≤196
+2x2 ≤ 5
1 34567 第三章 整数规划
x1 x2
≥0
x1、x2为非负整数
线性规划的可行域如图3.1中阴影部分所示，由图解法可知，线性规划的最优解位于图中的A点，即（x1，x2）=（13/5，19/5）=（2.6，3.8），线性规划最优解的目标函数值为z=89/5=17.8。
而相应的整数规划的可行解是图中线性规划可行域中整数网格的交点。整数规划的最优解位于图的B点，即（x1，x2）=（5，3），整数规划最优解的目标函数值为z=17。
由以上例子可以看到，简单地将线性规划的非整数的最优解，用四舍五入或舍去尾数的办法得到整数解，一般情况下并不能得到整数规划的最优解。整数规划的求解方法要比线性规划复杂得多。
有以下几类整数规划模型：第一类是根据问题要求，定义模型中若干或者所有变量为整数变量；第二类是定义模型中若干或者所有变量为0－1变量；第三类是利用包含0－1变量的约束条件来定义变量之间的逻辑关系。下面是几个属于这两类问题的例子。 例3.1 背包问题
有一只背包，最大装载重量为W公斤，现有k种物品，每种物品数量无限。第i种物品每件重量为wi公斤，价值为vi元。每种物品各取多少件装入背包，使其中物品的总价值最高。
设取第i种物品xi件（i=1，2，…，k），则规划问题可以写为 max s.t.
z=
v1x1 w1x1 x1, x1,
+v2x2 +w2x2 x2, x2,
+…
+… +wkxk ≤W
xk ≥0 … …
xk为整数 +vkxk
如果忽略变量为整数的要求，这个问题成为线性规划问题，k个变量中将只有一个基变量大于0，其余k-1个非基变量都等于0，而且这个大于0的基变量一般情况下是非整数。这样的解显然是没有意义的。例如背包容量为50公斤，三种物品的重量和价值如下表：
表格 1
物 品 单件价值（元/件） 1 17 2 72 3 35 单件总量（公斤/件） 10 41 20 设三种物品分别取x1，x2，x3件，这个背包问题整数规划模型为
2 第三章 整数规划
max z= 17x1
10x1 s.t.
x1, x1,
5041+72x2 +35x3
+41x2 +20x3 ≤50 x2, x2,
x3
≥0
x3为整数
如果忽略变量的整数要求，以上问题是一个线性规划问题，它的最优解为
x1=0，x2=
，x3=0，最优解的目标函数值为 z=72×50÷41＝87.8
而整数规划的最优解是
x1=1，x2=0，x3=2，整数规划最优解的目标函数值为z=87。
例3.2 厂址选择问题
在5个地点中选3处建生产同一产品的工厂，在这5个地点建厂所需投资，占用农田，建成以后的生产能力等数据如下表所示。
表格 2
地点 所需投资（万元） 占用农田（亩） 生产能力（万吨） 产能力最大。
设五个0—1变量x1，x2，x3，x4，x5，其中
?0xi???1表示在i地不建厂表示在i地建厂1 320 20 70 2 280 18 55 3 240 15 42 4 210 11 28 5 180 8 11 现在有总投资800万元，占用农田指标60亩，应如何选择厂址，使建成后总生
i=1，2，3，4，5
整数规划模型为
max z= 70x1 +55x2 +42x3 +28x4 +11x5 s.t.
3 20x1 +280x2+ 240x3 +210x4 +180x5? 800 20x1 +18x2 +15x3 +11x4 +8x5 ? 60 x1 x1
+x2 x2
+x3 x3
+x4 x4
+x5 =3 x5= 0,1
这是一个0—1规划问题。这个0－1规划问题的最优解为
x1=1，x2=0，x3=1，x4=1，x5=0，max z=140万吨。
即在地点1、3、4建厂，地点2、5不建厂。总投资770万元，占用农地46亩，总生产能力可以达到140万吨。
例3.3 变量之间需要满足一定的逻辑关系的问题，例如
3 第三章 整数规划
一个工厂用三种设备生产5种产品，三种设备的总能力（小时），生产每种产品需要占用的各种设备的能力（小时/件）以及三种产品的利润（元/件）如下表所示。 表格 3 设备A 设备B 设备C 产品1 产品2 产品3 产品4 产品5 设备能力（小时） 5 － 3 1 3 2 3 4 1 21 2 1 3 17 4 5 2 22
1,800 2,500 2,200 利润（元/件） 24 18 这个问题的整数规划模型为 max z= 24x1 +18x2 +21x3 +17x4 +22x5 st
5x1 3x1
+x2 3x2 +2x2
+3x3 +4x3 +x3
+2x4 +x4 +3x4
+4x5 ?1800 +5x5 ?2500 +2x5 ?2200
x1，x2，x3，x4，x5?0，变量为整数
如果忽略变量为整数的要求，以上问题成为一个线性规划问题，这个线性规划问题的最优解为x1=187.5件，x2=810.0件，x3=17.5件，x4=0.0件，x5=0.0件。最大利润为z=19447.50元。
如果产品产量必须是整数，以上整数规划的最优解为x1=187件，x2=809件，x3=18件，x4=1件，x5=0件。最大利润为z=19445元。
如果这五种产品的产量之间还要满足一定的逻辑关系，例如分别考虑以下关系： 1、 五种产品中，安排生产的产品不能超过三种； 2、 每一种产品如果生产，最小批量为50件； 3、 如果产品1安排生产，产品2就不能生产；
4、 如果产品4生产，产品5必须生产，而且至少生产50件；
为了实现以上的逻辑关系，需要设5个0－1变量y1，y2，y3，y4，y5。其中一个变量等于0，表示相应的产品不生产；变量等于1，表示相应的产品可以安排生产（也可以不安排生产）。利用这5个0－1变量，设计恰当的线性（注意，必须是线性的等式或不等式）约束条件，就可以表示以上各种逻辑关系。
为了使0－1变量y1，y2，y3，y4，y5起到分别控制x1，x2，x3，x4，x5等于零或不等于0的作用，需要增加以下五个约束条件：
x1?My1，x2?My2，x3?My3，x4?My4，x5?My5
其中M为足够大的正数，例如M＝10000。从以上五个约束条件可以看出，如果yi=0，则相应的约束条件成为xi?0，即xi=0。如果yi=1，则相应的约束条件成为
4 第三章 整数规划
xi ?M，由于M足够大，xi实际上没有任何限制（注意：也可以等于0）。
为了使变量满足以上逻辑关系，需要分别设计相应的约束条件。 1、 五种产品中，安排生产的产品不能超过三种；相应的约束条件为：
y1+y2+y3+y4+y5?3 完整的整数规划模型为
max z= 24x1 +18x2 +21x3 +17x4 +22x5 st
5x1 +x2 +3x3 +2x4 +4x5
3x2 +4x3 +x4 +5x5
+x3 +3x4 +2x5 x3
x4
x5
x2
3x1 +2x2 x1
?1800 ?2500 ?2200
?0 ?0 ?0 ?0 ?0 ?3
-My1
-My2
- My3
-My4
-My5
y1 +y2 +y3 +y4 +y5
x1，x2，x3，x4，x5?0，为整数，y1，y2，y3，y4，y5=0,1
取M＝10000，以上整数规划的最优解为
y1=1，y2=1，y3=1，y4=0，y5=0 x1=187，x2=808，x3=19，x4=0，x5=0
最大利润为z=19431元。也就是第一、第二和第三种产品安排生产，第四和第五种产品不生产。
2、 每一种产品如果生产，最小批量为50件； 相应的约束条件为：
x1?50y1，x2?50y2，x3?50y3，x4?50y4，x5?50y5
由以上约束条件可以看出，如果第i种产品生产，即yi=1，就有xi?50。 完整的整数规划模型为
max z= 24x1+ 18x2 +21x3+ 17x4 +22x5 st
5x1 +x2 +3x3 +2x4 +4x5
3x2 +4x3 +x4 +5x5
x2
x3
3x1 +2x2 +x3 +3x4 +2x5 x1
5 ?1800 ?2500 ?2200
?0 ?0 ?0
-My1
-My2
-My3