ee第五章 整数规划

第五章 整数规划主要内容：1、分枝定界法； 2、割平面法； 3、0－1型整数规划； 4、指派问题。

重点与难点：分枝定界法和割平面法的原理、求解方法，0－1型规划模型的建立及求解步骤，用匈牙利法求解指派问题的方法和技巧。

要 求：理解本章内容，熟练掌握求解整数规划的方法和步骤，能够运用这些方法解决实际问题。

§1 问题的提出要求变量取为整数的线性规划问题，称为整数规则问题（简称IP ）。

如果所有的变量都要求为（非负）整数，称之为纯整数规划或全整数规划；如果仅一部分变量要求为整数，称为混合整数规划。

例1 求解下列整数规划问题211020m ax x x z +=⎪⎪⎩⎪⎪⎨⎧≥≤+≤+为整数21212121,0,13522445x x x x x x x x 如果不考虑整数约束，就是一个线性规划问题（称这样的问题为原问题相应的线性规划问题），很容易求得最优解为：96m ax ,0,8.421===z x x 。

用图解法将结果表示于图中画“+”号的点都是可行的整数解，为满足要求，将等值线向原点方向移动，当第一次遇到“+”号点（1,421==x x ）时得最优解为1,421==x x ，最优值为z=90。

由上例可看出，用枚举法是容易想到的，但常常得到最优解比较困难，尤其是遇到变量的取值更多时，就更困难了。

下面介绍几种常用解法。

§2 分枝定界法分枝定界法可用于解纯整数或混合的整数规划问题。

基本思路：设有最大化的整数规划问题A ，与之相应的线性规划问题B ，从解B 开始，若其最优解不符合A 的整数条件，那么B 的最优值必是A 的最优值*z的上界，记为z ；而A 的任意可行解的目标函数值是*z的一个下界z ，采取将B 的可行域分枝的方法，逐步减少z 和增大z ，最终求得*z 。

现举例说明： 例2 求解A219040m ax x x z +=⎪⎪⎩⎪⎪⎨⎧≥≤+≤+为整数21212121,0,702075679x x x x x x x x 解：先不考虑条件⑤，即解相应的线性规划B （①--④），得最优解=1x 4.81, =2x 1.82,①② ③ ④ ⑤=0z 356（见下图）。

，求解过程停止。 3.B有最优解，但不符合A的整数条件，记其目标函数值为z1。
第二步：确定A的最优目标函数值z*的上下界，其上界即为 z ,再用观察法
找到A的一个整数可行解，求其目标函数值作为z*的下界，记为z。
第三步：判断 z 是否等于z 。若相等，则整数规划最优解即为其目标函
数值等于z的A的那个整数可行解；否则进行第四步。
2020/3/2
11
•割平面法，即通过添加约束条件，逐步切割可行区域的 边角余料，让其整数解逐步的露到边界或顶点上来，只要 整数解能曝露到顶点上来，则就可以利用单纯形法求出来。
•关键是通过添加什么样的约束条件，既能让整数解往边 界露，同时又不要切去整数解，这个条件就是Gomory约束 条件。 •Gomory约束只是割去线性规划可行域的一部分，保留了 全部整数解。
2020/3/2
7
7
第二节 割平面法
2x1 2x2 11
13/4,5/2
松弛问题 x1+x2≤5 第二次切割
2020/3/2
第一次切割 4,1
8
设纯整数规划
n
m a x Z c j x j j 1

s
.t
.

n j 1
aij x j

bi

x
j

0且
为
整
数
，
j

1,L
引入约束 xi ≤ M yi ，i =1，2，3，M充分大，以保证yi=0 xi=0 这样我们可建立如下的数学模型：
Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3 s.t. 2x1 + 4x2 + 8x3 ≤ 500

例5.2
选址问题
现准备在几个地点建厂，可供选择的地点有 A1, A2, …, Am，它们的 生产能力分别是 a1, a2, …, am（假设生产同一种产品）.第 i 个工厂 的建设费用为 fi ( i = 1, 2, …, m)，并有 n 个地点 B1, B2, …, Bn， 需要销售这种产品，其销量分别为 b1, b2, …, bn，从工厂 Ai 运往销 地 Bj 的单位运费为 cij（如表所示）.试决定在哪里地方建厂，既能满 足各地的要求，又能使总建设费和总运输费用最省？
min z
i 1
m
c
j 1
n
ij
xij f i yi
i 1
m
s.t.
x
j 1
n
ij
ai yi
i 1, 2,, m (5.2)
xij 0, yi 0或1
i 1, 2, , m; j 1, 2, , n
在本例中，xij可以取非负实数，而yi只能取0或1，这类问题称为 混合整数规划问题.
二、割平面法
整数规划的割平面法是一个有效的求解整数规划的方法，因系 R.E Gomory提出，故称Gomory割平面法（Gomory Cutting Plane Algorithm）.
该方法的基本思想是首先求解整数规划（IP）对应的松弛问题 （LP），如果（LP）的最优解不是整数解，则逐次增加一个新约 束（即割平面），它能割去松弛问题可行域中不含整数解的区域. 逐次切割，直到得到一个整数最优极点（即整数解）为止.
如果其最优解不符合整数条件，则求出整数规划的上下界用增加约 束条件的方法，并把相应的线性规划的可行域分成子区域（称为分 枝），再求解这些子区域上的线性规划问题.

第五章 整数规划整数规划（integer programming ）亦称整数线性规划，它实质上是在线性规划的基础上，给一些或全部决策变量附加取整约束得到的。

在许多情况下，我们都可以把规划问题的决策变量看成是连续的变量；但在某些情况下，规划问题的决策变量 却被要求一定是整数。

例如，完成某项工作所需要的人数或设备台数，进入市场销售的商品件数，以及某一机械设备维修的次数等。

为了满足整数解的要求，最容易想到的办法就是把求得的非整数解进行四舍五入处理来得到整数解，但这往往是行不通的。

舍入处理会出现两方面的问题：一是化整后的解根本不是可行解；二是化整后的解虽是可行解，但并非是最优解。

因此，有必要另行研究整数规划的求解问题。

在线性规划的基础上，要求所有变量都取整的规划问题称为纯整数规划问题（pure integer programming ）；如果仅仅是要求一部分变量取整，则称为混合整数规划问题（mixed integer programming ）。

根据整数规划的定义，可将整数规划的数学模型表示为：0,;{min ≥==X b AX CX w 且（部分）为整数}。

显而易见，整数规划的可行域是其相应线性规划可行域的子集。

§1分枝定界法分枝定界法（branch and bound method ）是求解整数规划常用的一种方法，它具有灵活且便于用计算机求解等优点。

它的一般思想是利用连续的（线性规划）模型来求解非连续的（整数规划）问题。

假定k x 是一个有取整约束的变量，而其最优连续值*k x 是非整数；那么在][*k x （表示*k x 的取整值）和1][*+k x 之间不可能包括任何可行整数解。

因此，k x 的可行整数值必然满足][*k k x x ≤或1][*+≥k k x x 之一。

把这两个条件分别加到原线性规划的解空间上，产生两个互斥的线性规划子问题。

实际上这一过程利用了整数约束条件，在“分割”时删除了不包含可行整数点的部分连续空间（1][][**+<<k k k x x x ）。