第七讲整数规划(一)(运筹学清华大学,林谦)

第七讲整数规划（一）§1概述

§2割平面法§3分枝定界法§1概述（1）

一、定义规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。二、整数规划分类如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类：Ÿ

变量全限制为整数的，称纯（完全）整数规划。Ÿ

变量部分限制为整数的，称混合整数规划。§1概述（2）

三、整数规划特点整数规划标准形式（实际为整数线性规划）

AX=b，X≥0，CTX=min，xj为整数（j=1，…，n）(1)1．原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况；①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。②整数规划无可行解。§1概述（3）

[例2-1]原线性规划为：2x1+4x2=5，X≥0，CTX=x1+x2=min

其最优实数解为：x1=0，x2=5/4，minCTX=5/4。

③有可行解（当然就存在最优解），但最优解值变差。[例2-2]原线性规划为：2x1+4x2=6，X≥0，CTX=x1+x2=min

其最优实数解为：x1=0，x2=3/2，minCTX=3/2。

若限制整数则得：x1=1，x2=1，minCTX=2。

§1概述（4）

2．整数规划最优解不能按照实数最优解简单取整而获得。[例2-3]物品装载问题：有若干类物品需一次性装运，每件物品的价值及重量分别，为vj和wj(j=1,…,n)，车辆最大载重量为，试求，每件物品应装多少件才能使总价值最大。[解]令xj表示第j类物品的装载件数，则可列写整数规划如下：

xj≥0且取整

(2)§1概述（5）

若不限制为整数，其最优解的基础分量xm为：当j≠m，则xj=0当限制为整数时，就需仔细计算（其方法将在后面阐述）。例如，将例[2-3]具体化为： 51x1+50x2+50x3≤100150x1+100x2+99x3=max

xj≥0

§1概述（6）

若不限制整数，得出m=1，比率为150/51→max，故最优实数解为：x1=100/51，x2=x3=0，总价值15000/51=294.12。然而，物品不能切开，故限制为整数时，其最优解为：x1=0，x2=2，x3=0；总价值为200。从该例得出结论，整数规划最优解不能简单的从最优实实数解中4舍5入取整所得。因此，对于整数规划的求解必须开拓新技术。

§1概述（7）

四、求解方法分类：1．

割平面法——主要求解纯整数线性规划2．

分枝定界法——可求纯或混合整数线性规划3．

隐枚举法——求解“01”整数规划：①过滤隐枚举法；②分枝隐枚举法4．

匈牙利法——解决指派问题（“01”规划特殊情形）。5．蒙特卡洛法——求解各种类型规划。

§2割平面法

该法适于求解纯整数规划问题。其基本思路是首先去掉整数约束去求解普通线性规划问题，若获得的最优解全为整数，结束；否则，以此最优非整数变量为基准，在原约束条件下，增加割约束，再继续求解，这样反复下去，直到结束为止。

§3分枝定界法

（1）

分枝定界法目前已成功地应用于求解整数规划问题、生产进度表问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。因此，分枝定界算法是求解整数规划的最有用的算法之一。现结合例题说是该算法的思路。[例2-5]求解下述整数规划目标函数

minz=x1+4x2约束条件2x1+x2≤8

x1+2x2≥6

x1，x2≥0且为整数

§3分枝定界法

（2）

[解]1)不受整数限制，作为普通线性规划求解，可得出最优解为：x1=10/3，x2=4/3，z=26/3（见图2-1）。该解示如图2-4中的节点①。

1245810123456789x1x22x1+x2=8最优解x1+2x2=6图2-13679§3分枝定界法

（3）

2）因为x1、x2当前均为非整数，故不满足整数要求，任选1个进取分枝。设选x1进行分枝，把可行集分成2个子集：x1≤[10/3]=3及x1≥[10/3]+1=43)x1≤3时目标函数

minz=x1+4x2约束条件2x1+x2≤8

x1+2x2≥6

x1≤3

x1，x2≥0且为整数。§3分枝定界法

（4）

不加整数限制，求出最优解为：x1=3，x2=3/2，z=9（参见图2-2）。该解示如图2-4中的节点②。

图2-2x1=3最优解x1=3

x2=3/2x1+2x2=641258123456789x1x23672x1+x2=8目标函数§3分枝定界法

（5）

4）x1≥4时目标函数minz=x1+4x2约束条件2x1+x2≤8

x1+2x2≥6

x1≥4

x2≥0x1、x2为整数。§3分枝定界法

（6）

不受整数限制，求解相应线性规划，用图解法观察出无解（参见图2-3）。该解示如图2-4中的③。图2-341258123456789x1x2367x1=42x1+x2=8x1+2x2=6§3分枝定界法

（7）

5）节点④，令x2≤[3/2]=1目标函数minz=x1+4x2约束条件2x1+x2≤8

x1+2x2≥6

x1≤3

x2≤1x1、x2≥0，且为整数。用图解法，知该子集无解，读者可以自己作。§3分枝定界法

（8）

6)节点⑤，令x2≥[3/2]+1=2目标函数minz=x1+4x2约束条件2x1+x2≤8

x1+2x2≥6

x1≤3

x2≥2x1≥0，全取整。其图解法见图2-5，最优解为x1=2，x2=2，z=10。§3分枝定界法

（9）图2-5x1=3x1=2x2＝241258123456789x1x2367最优整数解目标函数x2=2123z=26/3x1=10/3x2=4/3x1≤3

x1≥4

z=9x1=3x2=3/2不可行

图2-4§3分枝定界法

（10）

从对求解[例2-5]的过程，可归纳出求解整数规划的分枝定界法有下述特点：(i)既可求解全整数规划，亦可求解混合整数规划。(ii)求解每个子集的最优整数解，都是首先放弃整数约束，用线性规划解法求出无约束时的最优解，此时的目标函数值即为该子集所有可行解的目标下界（对于求极小值的规划而言）。(iii)如果子集的非整数最优解的下界超过迄今已得到的最好可行整数解目标值，或者子集无解，则这个子集将被剪掉，又称剪枝。§3分枝定界法

（11）

(iv)如果子集的非整数最优解符合变量整数要求，则称为整数规划的可行解，其目标函数值若低于已得的最好可行整数解目标，则取代原最好解，否则，该子集被剪掉。(v)如果子集的非整数最优解不符合整数要求，但又未被剪掉，则任选一个不符合整数要求的变量进行分枝。(vi)该法只能用于整数线性规划。第七讲整数规划（二）§1匈牙利法§2蒙特卡洛法（随机取样法）（略）§1匈牙利法（1）

匈牙利法主要解决指派问题，指派问题是一种特殊的“01”规划。例如指派授课问题，现有A、B、C、D四门课程，需由甲、乙、丙、丁四人讲授，并且规定：每人只讲且必须讲１门课。每门课必须且只需１人讲。四人分别讲每门课的费用示于表2-3中：

§1匈牙利法（2）

表2-3授课费用表

课费用人ABCD甲乙丙丁2109715414813141611415139求何人讲何门课才能使总费用最低？

§1匈牙利法（3）

该例便是指派问题的典型实例，该类问题的典型数学模型为：=1i=1,…,m=1j=1,…,m

xij=minz=§1匈牙利法（4）

其中，cij为效能矩阵（或费用矩阵）元素，表示第i人去完成第j任务时的费用。共有m个人去完成m件工作。该法的主要思路和步骤如下：１．在费用矩阵中，任一行（列）减去或加上１个常数，其最优基础解集不变，只改变费用函数值。从费用矩阵中的i行每个元素减去ai(i=1,…,m)，从j列中每个元素减去bj（j=1,…,m），则新目标函数改变为：min

z=

－

－§1匈牙利法（5）

=

－－显而易见，变化后的目标函数表达式只相差一个常数，则规划的最优解集不可能改变。2．用上述方法变换，使费用矩阵每行每列都至少出现1个零，且能达到全分配时，即可令零元素所对应的变量xij=1（当然分配时，必须使每行每列有且仅有1个xij为1）。于是可获得费用函数值z=0，这必是此次的最优分配，否则，只会使z≥0。例如，由表1所示的授课例子中，经过变换可得最后结果为：§1匈牙利法（6）

当达到右边费用矩阵时，就已达到全分配，用Δ表示之，即，最优解集为：x13=1(甲讲C门课)x22=1（乙讲B门课）x34=1（丙讲D门课）x41=1（丁讲A门课）§1匈牙利法（7）

此时对应的最后规划模型目标函数必为零，但原始规划目标函数最优值为变换中历次从行（列）中减去（或加上的）常数之代数和。该题变换中共减去28，故本例最优费用值为28。3．从前所述，指派问题的关键是如何将原规划的费用矩阵变换成全分配矩阵，现不加证明的阐述其变换步骤（仍结合前例说明）。1)修改费用矩阵，使矩阵的每一行和第一列至少出现1个零元素，处理方法即为每行（每列）都减去该行（列）的最小元素。§1匈牙利法（8）

§5匈牙利法（9）

2)试图制订一个完全分配方案，该方案只与表中零元素相对应。从第１行开始，依次检查各行，直到找出只有一个未标记的零元素的一行为止。如果在零元素上有一个符号Δ或×，则称零元素已标记。符号Δ表示分配Δ所在行的那一位教师担任Δ所在列的那一门课程。对未做标记的零元素标Δ后，应对同一列其它的零元素画×。

§1匈牙利法（10）

现在依次检查每列中只含一个未标记的零元素，并给未标记的零元素标Δ。对同一行其它的零元素画×（如果有的话）。如果有多行多列同时有2个或以上的未标记零元素，则可将其中的任意行或列中一个未标零元素标Δ，并将同行和同列的其他零元素画×。

§1匈牙利法