第三章 整数规划

第三章 整数规划

第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

第三章 整数规划

x2

x3

x4 x4

x5 x5

-My4

?0 ?0 ?0 ?0 ?0 ?0 ?0

-My5

x1 -50y1

-50y2

-50y3

-50y4

-50y1

x1，x2，x3，x4，x5?0，为整数，y1，y2，y3，y4，y5=0,1

取M＝10000，以上整数规划的最优解为：

y1=1，y2=1，y3=1，y4=1，y5=0；

x1=155件，x2=745件，x3=50件，x4=65件，x5=0件 最大利润为z=19285元。

3、 如果产品1安排生产，产品2就不能生产； 相应的约束条件为：

y1+y2?1

完整的整数规划模型为

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 ?1

-My1

-My2

- My3

-My4

-My5

y1 +y2

x1，x2，x3，x4，x5?0，为整数，y1，y2，y3，y4，y5=0,1

取M＝10000，以上整数规划的最优解为：

y1=0，y2=1，y3=1，y4=1，y5=0；

x1=0件，x2=435件，x3=205件，x4=375件，x5=0件 最大利润为z= 18510元。

请注意，问题的条件是“如果产品1安排生产，产品2就不能生产”，而模型的约束条件y1+y2?1的涵义是“产品1和产品2两者最多只能有一个安排生产”，满足

6 第三章 整数规划

这个约束条件的有三种情况：产品1安排生产，产品2不生产；产品1不生产，产品2安排生产；产品1和产品2都不生产。模型的最优解在这三种情况中选择了产品1不安排生产，让产品2生产，这样的经济效益最好。

4、 如果产品4安排生产，产品5必须生产，而且至少生产50件； 相应的约束条件为

y5?y4 x5?50y5

完整的整数规划模型为

max z= 24x1 +18x2 +21x3 +17x4 +22x5 st

5x1 +x2 +3x3 +2x4 +4x5

x1

3x2 +4x3 x2

x3

+x4 +5x5 x4

3x1 +2x2 +x3 +3x4 +2x5

x5 x5

?1800 ?2500 ?2200 +y5

?0 ?0 ?0 ?0 ?0 ?0 ?0

-My1

-My2

-My3

-My4

-y4

-My5 -50y5

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=188件，x2=809件，x3=17件，x4=0件，x5=0件 最大利润为z= 19431元。

和上面一样，整数规划的最优解不让假定的条件（如果产品4安排生产）出现，也就是选择产品4不生产，产品5也不生产。 例3.4 考虑固定成本的最小生产费用问题

在最小成本问题中，设第j种设备（j=1，2，?，n）运行的固定成本为dj，运行的变动成本为cj，则生产成本与产量xj的关系为

0?fj(xj)???dj?cjx当xj?0jfj(xj) 变动成本cjxj 固定成本dj xj

dj 当xj?0

也就是说，一台设备如果不开工，则既

7 第三章 整数规划

没有固定成本，也没有变动成本，成本为0，如果设备开工，无论生产量是多少，就会有固定成本dj，以及变动成本cjxj。设0－1变量yj表示第j台设备（j=1，2，?，n）是否开工，目标函数表示为

nnjjjyjminz??cx??dj?1j?1

同时，为了表示设备开工与否和产量的逻辑关系，建立相应的约束条件

xj≤Myj

j=1，2，?，n

这里M是一个很大的正数。

从以上约束条件可以看出，当yj=0时，xj=0；即第j种设备不运行，相应的运行成本

z=djyj+cjxj=0

当yj＝1时，0≤xj≤M，实际上对产量xj没有限制，这时相应的运行成本为

z=dj+cjxj 请看以下的数字例子。

某炼焦厂用原煤为原料生产焦炭，同时可以得到焦炉煤气和煤焦油。该厂有四台炼焦炉A，B，C，D，四台炼焦炉每吨原煤可以产出的焦炭、煤气和煤焦油以及这四台炼焦炉的固定成本、处理每吨原煤的变动成本如下表所示：

表格 4

炼 焦 炉 产品 成本 A 0.64 23 0.12 400 85 100 B 0.68 25 0.15 1200 81 150 C 0.71 27 0.17 2600 78 200 3

D 0.73 28 0.19 3100 76 250 焦炭（吨/吨原煤） 煤气（m3/吨原煤） 煤焦油（吨/吨原煤） 固定成本（元） 变动成本（元/吨原煤） 生产能力（吨原煤） 要求焦炭的产量不低于280吨，煤气的产量不低于10000m，煤焦油的产量不低于60吨，编制使总成本（包括固定成本和变动成本）最低的四台炼焦炉的原煤分配计划。

设分配给四台炼焦炉的原煤分别为x1，x2，x3，x4吨。如果忽略固定成本，这是一个线性规划问题。

min z= s.t.

85x1 0.64x1

+81x2 +78x3 +76x4

+0.68x2 +0.71x3 +0.73x4 ≥ 280

8 第三章 整数规划

23x1 0.12x1

x1

+ 25x2 + 27x3 + 28x4 ≥10000

≥0

+0.15x2 +0.17x3 +0.19x4 ≥ 60

x2

x3

x4

x1≤100 x2≤150 x3≤200 x4≤250

这个线性规划问题的最优解为x1=x2=0，x3=137.32，x4=250，最小总成本为z=29711.27元。

如果考虑固定成本，要引进四个0—1变量y1，y2，y3，y4，和四个约束条件 x1≤My1，x2≤My2，x3≤My3，x4≤My4

并且在目标函数中加上固定成本函数，构成如下的整数规划问题 min z= s.t.

85x1 +81x2 +78x3 +76x4 +400y1 +1200y2 +2600y3 +3100y4

y1

-My2

y2

-My3

y2

-My4

y4

23x1 + 25x2 + 27x3 + 28x4 x1 x1

x2 x2

x3

≥280 ≥60 ≤0 ≤0 ≤0 ≤0

=0,1

0.64x1 +0.68x2 +0.71x3 +0.73x4 0.12x1 +0.15x2 +0.17x3 +0.19x4

x4

≥10000

-My1

x1≤100 x2≤150 x3≤200 x4≤250

x3 x4≥0

令M＝10000，这个0－1混合规划的最优解为

y1=0，y2=1，y3=0，y4=1；x1=0，x2=143.38，x3=0，x4=250

即设备A和设备C不开工，设备B和设备D开工，分别分配原煤143.38吨和250吨给设备B和设备D，最小总成本为34913.97元。其中设备B的固定成本为1200元，变动成本为11613.97元；设备D的固定成本为3100元，变动成本为19000元。

下面我们就来介绍两种整数规划的求解方法。

9 第三章 整数规划

§3.2 割平面法

割平面法是求解正数规划的基本方法之一。割平面得基本思想是：首先放弃变量的整数要求，求得线性规划的最优解。如果最优解恰是一个整数解，则线性规划的最优解就是相应的整数规划的最优解。如果线性规划的最优解不是整数解，则要求构造一个新的约束，对线性规划问题的可行域进行切割，切除已经得到的线性规划的最优解，但保留原可行域中所有的整数解，求解新的线性规划问题，如果最优解仍不是整数解，再增加附加的约束将其切除，但仍保持最初可行域中所有的整数解，如此一直进行，直至得到一个整数的最优解为止。 z x1 … xr … xm

设放弃变量整数要求得到的线性规划的最优单纯形表如下：

xm+1 xj z x1 … xr … xm … … 1 0 … 0 … 0 0 … 0 … 0 … … … 0 … 0 … 1 zm+1-cm+1 y1,m+1 … yr,m+1 … ym,m+1 … … … … zm+1-cm+1 y1,m+1 … yr,m+1 … ym,m+1 … … … … xn zm+1-cm+1 y1,m+1 … yr,m+1 … ym,m+1 RHS zo b1 … br … bm 1 … 0 … … 0 … 1 … … 0 … 0 其中x1，xr，xm为基变量，xm+1，xj，xn为非基变量。设其中基变量xr的值br不是整数，且

br=Ir+Fr

其中Ir是br的整数部分，Fr是小数部分，即

Ir=0，1，2，…，

0

设Irj是yrj的整数部分，Frj是小数部分，则 其中

Irj=0，?1，?2，…， yrj=Irj+Frj

由于yrj可能是整数，因此

0≤Frj≤1 这样，第r个约束成为

10

第三章 整数规划

nxr??yj?m?1nrjxj?br （3.1）

将yrj和br写成整数部分和小数部分 或 由于

xr??(Ij?m?1nrj?Frj)xj?Ir?Fr

nxr??Ij?m?1rjxj?Ir?Fr?n?Fj?m?1rjxj （3.2）

Fr?1，以及

?Fj?m?1rjxj?0

因此对于（3.2）中的任何（整数或非整数的）可行解，有

nnrjxjxr??Ij?m?1?Ir?Fr??Fj?m?1rjxj?1

n （3.3）

rjxj对于任何可行的整数解，xr和xj都是整数，因此xr?n?Ij?m?1?Ir是整数，即

xr??Ij?m?1nrjxj?Ir=…，-2，-1，0

因此对于整数可行解，约束（3.2.2）可以写成更严格的不等式

nrjxjxr??Ij?m?1?Ir?Fr??Fj?m?1rjxj?0 （3.4）

将线性规划（非整数）的最优解

（x1…xr…xm，xm+1…xj…xn）=（b1…br，…bm，0…0…0）

代入（3.4）的左边，得到

nFr??Fj?m?1rjxj?Fr?0

线性规划（非整数）的最优解不满足（3.4）。因此，约束（3.4）具有以下性质：

1、 线性规划可行域中的任何整数解都满足这个约束； 2、 线性规划的（非整数）最优解不满足这个约束。

这样，在原线性规划的约束条件基础上增加约束（3.4），新的可行域将切除原线性规划非整数的最优解而保留所有整数可行解。 例3.4 用割平面法求解以下整数规划

min

z=

3x1 +4x2

11

第三章 整数规划

s.t.

3x1 x1

+x2 ≥4 x2 ≥0

x1 +2x2 ≥4

x1，x2为整数

先求相应的线性规划问题，得到最优单纯形表

z x1 x2

z 1 0 0 x1 0 1 0 x2 0 0 1 x3 -2/5 -2/5 1/5 x4 -9/5 1/5 -3/5 RHS 44/5 4/5 8/5 选择一个非整数的基变量，例如x2=8/5，构造约束条件（3.4），其中

b2=8/5=1+3/5，I2=1，F2=3/5 y23=1/5=0+1/5，I23=0，F23=1/5 y24=-3/5=-1+2/5，I24=-1，F24=2/5

n附加的约束条件Fr??Fj?m?1rjxj?0为

3/5-（1/3x3+2/5x4）≤0

即

1/5x3+2/5x4≥3/5

将这个约束加到线性规划的最优单纯形表中，并增加一个松弛变量x5，得到

z x1 x2 x5

z 1 0 0 0 x1 0 1 0 0 x2 0 0 1 0 x3 -2/5 -2/5 1/5 [-1/5] x4 -9/5 1/5 -3/5 -2/5 x5 0 0 0 1 RHS 44/5 4/5 8/5 -3/5 用对偶单纯形法，x5离基，x3进基

z x1 x2 x3

z 1 0 0 0 x1 0 1 0 0 x2 0 0 1 0 x3 0 0 0 1 x4 -1 1 -1 2 x5 -2 -2 1 -5 RHS 10 2 1 3

12 第三章 整数规划

已获得整数的最优解。

4 3 2 1 0 1 2 3 4 5 切割约束 整数规划 最优解 线性规划 最优解 为了得到切割约束1/5x3+2/5x4≥3/5在（x1, x2）平面中的表达式，将其中的松弛变量x3x4用 x1x2表示

x3=3x1+x2-4，x4=x1+x2-4

代入切割约束，得到

x1+x2≥3

这个切割的图解如图3.2。

图 3.1

13 第三章 整数规划

§3.3 分支定界法

分枝定界法（Branch and Bound，简称B&B）的基本思想如下：

首先不考虑变量的整数约束，求解相应的线性规划问题，得到线性规划的最优解。设线性规划问题

min s.t.

z= CTX

x2

E D C B Sub2 AX = b

X ≥0

的可行域如图3.3中OABCDE（示意图），并 设最优解位于C。如果这个最优解中所有的变 量都是整数，则已经得到整数规划的最优解。 如果其中某一个变量xr不是整数，则在可行 域中除去一块包含这个最优解但不包含任何整数解的区域Ir

Sub1 O

x1

Ir xr Ir+1 A 图 3.2

的整数部分），线性规划的可行域被划分成不相交的两部分，分别以这两部分区域作为可行域，用原来的目标函数，构造两个子问题Sub1和Sub2：

Sub1

s.t.

AX xr X

=b ≤Ir ≥0

Sub2

min s.t.

z= CTX

AX xr X

=b ≥Ir ≥0

min z= CTX

由于这两个子问题的可行域都是原线性规划问题可行域的子集，这两个子问题的最优解的目标函数值都不会比原线性规划问题的最优解的目标函数值更小。如果这两个问题的最优解仍不是整数解，则继续选择一个非整数的变量，继续将这个子问题分解为两个更下一级的子问题。这个过程称为“分枝（Branch）”。在分枝过程中，每一次分枝得到的子问题最优解的目标函数值，都大于或等于分枝前问题的最优解的目标函数值。

如果某一个子问题的最优解是整数解，就获得了一个整数可行解，这个子问题的目标函数值要记录下来，作为整数规划最优目标函数值的上界。如果某一个子问

14

第三章 整数规划

题的解还不是整数解，但这个非整数解的目标函数值已经超过和这个上界，那么这个子问题就不必再进行分枝，因为继续分枝即使得到整数解，这个整数解的目标函数值必定要大于（或等于）分枝以前问题的目标函数值，因而也大于（或等于）已经获得的整数规划的目标函数值，因此不可能是最优的整数解。如果在分枝过程中得到新的整数解且该整数解的目标函数值小于已记录的上界，则用较小的整数解的目标函数值代替原来的上界。上界的值越小，就可以避免更多不必要的分枝。这个确定整数解目标函数值上界并不断更新上界，并且不断“剪除”目标函数值超过上界的分枝的过程，称为定界（Bound）。

当最低一层子问题出现以下三种情况之一时，分枝定界算法终止： 1、 子问题无可行解； 2、 子问题已获得整数解；

3、 子问题的目标函数值超过上界。 例3.5 用分枝定界法求解以下整数规划

min z= -2x1 s.t.

1217-3x2 +7x2 +9x2 x2

≤35 ≤36 ≥0

取

x2 4 Sub2 3 2 1 Sub1 x1 0 1 2 3 4 5 6 7

5x1 4x1 x1

x1，x2为整数

617817先求得相应的线性规划的最优解，为

x1?3x2?2617,x2?2,z??14分割可行域，得到以下两个子问题：

-3x2 +7x2 +9x2 x2 x2

≤35 ≤36 ≤2 ≥0

Sub-2

min s.t. z= -2x1 5x1 4x1 x1 -3x2 +7x2 +9x2 x2 x2 ≤35 ≤36 ≥3 ≥0 Sub-1 min s.t. z= -2x1 5x1 4x1 x1 Sub1的最优解为 Sub2的最优解为

15

第三章 整数规划

15251412x1?4,1x2?2,z??14

x1?2,12x2?3,z??13

取x1?4对可行域进行分割，

5z??13>z??14，停止分枝。

得到子问题Sub3和Sub4。

x2 4 3 2 1 Sub3 Sub4 x1

Sub-3 min s.t. -3x2 +7x2 +9x2 x2 x1 x2

≤35 ≤36 ≤2 ≤4 ≥0

Sub-4

min s.t. z= 37

4 3 2 x2 1 x1 0 1 2 3 4 5 6 7 0 1 2 3 4 -2x1 5x1 4x1 x1 27 -3x2 +7x2 +9x2 x2 x1 x2 ≤35 ≤36 ≤2 ≥5 ≥0 z= -2x1 5x1 4x1 x1 Sub-3的最优解为 x1=4，x2=2，z=-14

Sub-4的最优解为 x1=5，x2?1取x2?137，z??14

获得整数解，取得上界z??14 停止分枝。

对可行域进行分割

得到子问题Sub-5和Sub-6

x2 4 3 2 1 Sub-5 x1 0 1 2 3 4 5 6 7 Sub-6 x2 4 3 2 1 Sub-3 x1 0 1 2 3 4 5 6 7 16 第三章 整数规划

Sub-5 min s.t. 35 -3x2 +7x2 +9x2 x2 x1 x2 x2

15 ≤35 ≤36 ≤2 ≥5 ≤1 ≥0

Sub-6 min s.t. z= -2x1 5x1 4x1 x1 -3x2 +7x2 +9x2 x2 x1 x2 x2 ≤35 ≤36 ≤2 ≥5 ≥2 ≥0 z= -2x1 5x1 4x1 x1 Sub-5的最优解为

x1?5

Sub-6的可行域是空集，停止分枝。

，x2=1，z??1435取x1?5对可行域进行分割，

得到子问题Sub-7和Sub-8。

4 3 2 1 Sub-7 Sub-8 0 1 2 3 4 5 6 7

Sub-7 min s.t. -3x2 +7x2 +9x2 x2 x1 x2 ≤35 ≤36 ≤2 ≥5 ≤1

Sub-8 min s.t. z= -2x1 5x1 4x1 -3x2 +7x2 +9x2 x2 x1 x2 x1 x2 37 ≤35 ≤36 ≤2 ≥5 ≤1 ≥6 ≥0 z= -2x1 5x1 4x1 x1 Sub-7的最优解为 x1=5，x2=1，z=-13

x1 ≤5 x2 ≥0

x1 Sub-8的最优解为 x1=6，x2?57，z??14

17 第三章 整数规划

获得整数解，停止分枝。 由于z=-13>z??14， 上界仍保持为z??14。

Sub-9 -2x1 -3x2

取x2?57对可行域进行分割，

得到子问题Sub-9和Sub-10。

4 3 2 1 0 1 2 3 4 5 6 7 Sub-9 Sub-10

Sub-10 min s.t. z= -2x1 5x1 4x1 x1 -3x2 +7x2 +9x2 x2 x1 x2 x1 x2 x2 ≤35 ≤36 ≥3 ≥5 ≥2 ≥6 ≥1 ≥0 min z= s.t. 5x1 +7x2 ≤35 4x1 +9x2 ≤36 x1 x2 x1 x2 x1 x2 x2 ≥3 ≥5 ≥2 ≥6 ≤0 ≥0 Sub-9的最优解为x1=7，x2=0，z=-14，

Sub-10的可行域是空集，停止分枝。

获得整数解，z=-14=z??14，上界仍为z??14。

至此已将所有可能分解的子问题都已分解到底，最后得到两个目标函数值相等的最优整数解：（x1，x2）=（4，0）和（x1，x2）=(0，7)，他们的目标函数值都是-14。

以上的搜索过程可以用一个树状图表示，由分枝定界算法可以知道，这个搜索树是一个二叉树。

不同的搜索策略会导致不同的搜索树，如果先搜索Sub-1—Sub-3，就得到上界

z??14，然后再搜索Sub-2，就可以知道Sub-2的目标函数值z??1312已经大于上

界z??14，就可以剪去Sub-2以下所有的分枝。如果先搜索Sub-1—Sub-2，这时还没有得到任何一个整数解，因而还没有得到一个上界，因此Sub-2必须继续分枝。

18 第三章 整数规划

一般情况下，同一层的两个子问题，先搜索目标函数比较小的比较有利，因为这样可能得到数值比较小的上界，上界越小被剪去的分枝越多。

分枝定界算法对于混合整数规划特别有效，对没有整数要求的变量就不必分枝，这将大大减少分枝的数量。在以上的例子中，如果x2没有整数限制，只要一次分枝就可以得到最优解。

19 第三章 整数规划

Sub-9 x1?7x2?0z??14z?z??14原问题 x1?3x2?21217617817 z??14 Sub-2 x2≥3 x2≤2 Sub-1 x1?4x2x1?3x21217121525?3?2z??13z?z??14z??14 Sub-4 x1≥5 x1≤4 Sub-3 x1?5,x2?13727 x1?4x2?2z??14 z??14 Sub-6 x2≤1 x2≥2 Sub-5 x1?5x2?1z??141535z??14无可行解 Sub-8 x1≥6 x1≤5 Sub-7 x1?6x2?5737 x1?5x2?1z??13 z??14 x2≤0 x2≥1 Sub-10 z?z??14 无可行解

20

本文来源：https://www.bwwdw.com/article/cdx3.html