第七讲整数规划(一)(运筹学基础-清华大学,王永县)

1、第十四、十五讲第七讲第七讲 1 概述 2 割平面法3 分枝定界法第十四、十五讲 一、定义 规划中的变量（部分或全部）限制为整数时，称为整数规 划。若在线性规划模型中，变量限制为整数，则称为整数 线性规划。 二、整数规划分类 如不加特殊说明，一般指整数线性规划。对于整数线性规 划模型大致可分为两类： 变量全限制为整数的，称纯（完全）整数规划。 变量部分限制为整数的，称混合整数规划。第十四、十五讲 三、整数规划特点 整数规划标准形式（实际为整数线性规划） AX=b，X0，CTX=min，xj为整数（j=1，n） (1) 1原线性规划有最优解，当自变量限制为整数后， 其整数规划解出现下述情况； 原线

2、性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 整数规划无可行解。第十四、十五讲 例2-1 原线性规划为： 2x1+4x2=5，X0，CTX=x1+x2=min 其最优实数解为：x1=0，x2=5/4，min CTX =5/4。 有可行解（当然就存在最优解），但最优解值变差。 例2-2 原线性规划为： 2x1+4x2=6，X0，CTX=x1+x2=min 其最优实数解为：x1=0，x2=3/2，min CTX =3/2。 若限制整数则得：x1=1，x2=1，min CTX =2。 第十四、十五讲 2整数规划最优解不能按照实数最优解简单取整而获得。例2-3 物品装载问题：有若干类物

3、品需一次性装运，每件物品的价值及重量分别，为vj和wj (j=1, ,n)，车辆最大载重量为，试求，每件物品应装多少件才能使总价值最大。解 令xj表示第j类物品的装载件数，则可列写整数规划如下：max1111nnnnxvxvxwxwxj0且取整 (2)第十四、十五讲 若不限制为整数，其最优解的基础分量xm为：当jm，则xj=0当限制为整数时，就需仔细计算（其方法将在后面阐述）。例如，将例2-3具体化为：51x1+50 x2+50 x3100 150 x1+100 x2+99x3=max xj0 jjmmmmwvwvwx/max/，其中，第十四、十五讲 若不限制整数，得出m=1，比率为150/5

4、1max，故最优实数解为：x1=100/51，x2=x3=0，总价值15000/51=294.12。然而，物品不能切开，故限制为整数时，其最优解为：x1=0，x2=2，x3=0；总价值为200。q从该例得出结论，整数规划最优解不能简单的从最优实实数解中4舍5入取整所得。因此，对于整数规划的求解必须开拓新技术。 第十四、十五讲 四、求解方法分类： 1 割平面法主要求解纯整数线性规划 2 分枝定界法可求纯或混合整数线性规划 3 隐枚举法求解“01”整数规划： 过滤隐枚举法； 分枝隐枚举法 4 匈牙利法解决指派问题（“01”规划特殊情形）。 5蒙特卡洛法求解各种类型规划。第十四、十五讲 该法适于求解

5、纯整数规划问题。其基本思路是首先去掉整数约束去求解普通线性规划问题，若获得的最优解全为整数，结束；否则，以此最优非整数变量为基准，在原约束条件下，增加割约束，再继续求解，这样反复下去，直到结束为止。第十四、十五讲 分枝定界法目前已成功地应用于求解整数规划问题、生产进度表问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。因此，分枝定界算法是求解整数规划的最有用的算法之一。现结合例题说是该算法的思路。例2-5求解下述整数规划目标函数 min z =x1+4x2约束条件 2x1+x28 x1+2x26 x1，x20且为整数第十四、十五讲 解1)不受整数限制，作为普通线性规划求解，可得出最优解

6、为：x1=10/3，x2=4/3，z=26/3（见图2-1）。该解示如图2-4中的节点。 12458101 2 3 4 5 6 7 8 9x1x22x1+x2=8最优解x1+2x2=6图2-13679第十四、十五讲 2）因为x1、x2当前均为非整数，故不满足整数要求，任选1个进取分枝。设选x1进行分枝，把可行集分成2个子集： x110/3=3及x110/3+1=43)x13时目标函数 min z=x1+4x2约束条件 2x1+x28 x1+2x26 x13 x1，x20且为整数。第十四、十五讲 不加整数限制，求出最 优 解 为 ： x1= 3 ，x2=3/2，z=9（参见图2-2）。该解示如图

7、2-4中的节点。 图2-2x1=3最优解x1=3 x2=3/2x1+2x2=6412581 2 3 4 5 6 7 8 9x1x23672x1+x2=8目标函数第十四、十五讲 4）x14时目标函数 min z =x1+4x2约束条件 2x1+x28 x1+2x26 x14 x20 x1、x2为整数。第十四、十五讲 不受整数限制，求解相应线性规划，用图解法观察出无解（参见图2-3）。该解示如图2-4中的。 图2-3412581 2 3 4 5 6 7 8 9x1x2367x1= 42x1+x2=8x1+2x2=6第十四、十五讲 5）节点，令x23/2=1目标函数 min z=x1+4x2约束条件

8、 2x1+x28 x1+2x26 x13 x21x1、x20，且为整数。用图解法，知该子集无解，读者可以自己作。 第十四、十五讲 6)节点，令x23/2+1=2目标函数 min z=x1+4x2约束条件 2x1+x28 x1+2x26 x13 x22x10，全取整。其图解法见图2-5，最优解为x1=2，x2=2，z=10。第十四、十五讲图2-5x1=3x1=2 x22412581 2 3 4 5 6 7 8 9x1x2367最优整数解目标函数x2=2123z =26/3x1=10/3x2=4/3x13 x14 z =9x1=3x2=3/2不可行 图2-4第十四、十五讲 从对求解例2-5的过程，

9、可归纳出求解整数规划的分枝定界法有下述特点：(i) 既可求解全整数规划，亦可求解混合整数规划。(ii)求解每个子集的最优整数解，都是首先放弃整数约束，用线性规划解法求出无约束时的最优解，此时的目标函数值即为该子集所有可行解的目标下界（对于求极小值的规划而言）。(iii)如果子集的非整数最优解的下界超过迄今已得到的最好可行整数解目标值，或者子集无解，则这个子集将被剪掉，又称剪枝。第十四、十五讲 (iv)如果子集的非整数最优解符合变量整数要求，则称为整数规划的可行解，其目标函数值若低于已得的最好可行整数解目标，则取代原最好解，否则，该子集被剪掉。(v)如果子集的非整数最优解不符合整数要求，但又未被

10、剪掉，则任选一个不符合整数要求的变量进行分枝。(vi)该法只能用于整数线性规划。第十四、十五讲第七讲第七讲 1 匈牙利法2 蒙特卡洛法（随机取样法）（略）第十四、十五讲 匈牙利法主要解决指派问题，指派问题是一种特殊的“0 1”规划。例如指派授课问题，现有A、B、C、D四门课程，需由甲、乙、丙、丁四人讲授，并且规定：每人只讲且必须讲门课。每门课必须且只需人讲。四人分别讲每门课的费用示于表2-3中： 第十四、十五讲 表2-3 授课费用表 课 费用 人 A B C D甲乙丙丁 2 10 9 7 15 4 14 8 13 14 16 11 4 15 13 9求何人讲何门课才能使总费用最低？ 第十四、十

11、五讲 该例便是指派问题的典型实例，该类问题的典型数学模型为： =1 i=1,m =1 j=1,m xij=min z = mjijx1miijx1jiji人去完成任务表示人不去完成任务表示 1 0mjijijmixc11第十四、十五讲 其中，cij为效能矩阵（或费用矩阵）元素，表示第i人去完成第j任务时的费用。共有m个人去完成m件工作。该法的主要思路和步骤如下：在费用矩阵中，任一行（列）减去或加上个常数，其最优基础解集不变，只改变费用函数值。从费用矩阵中的i行每个元素减去ai(i=1,m)，从j列中每个元素减去bj（j=1,m），则新目标函数改变为：min z = mjijijmixc11mj

12、ijmiixa11miijmjjxb11第十四、十五讲 = 显而易见，变化后的目标函数表达式只相差一个常数，则规划的最优解集不可能改变。2用上述方法变换，使费用矩阵每行每列都至少出现1个零，且能达到全分配时，即可令零元素所对应的变量xij=1（当然分配时，必须使每行每列有且仅有1个xij为1）。于是可获得费用函数值z=0，这必是此次的最优分配，否则，只会使z0。例如，由表1所示的授课例子中，经过变换可得最后结果为：mjijijmixc11miia1mjjb1第十四、十五讲 9 13 15 411 16 14 138 14 4 157 9 10 2最后变换28 3 2 9 0 3 44 5 13

13、3 6 0当达到右边费用矩阵时，就已达到全分配，用表示之，即，最优解集为：x13=1 (甲讲C门课) x22=1 （乙讲B门课）x34=1 （丙讲D门课） x41=1 （丁讲A门课）第十四、十五讲 此时对应的最后规划模型目标函数必为零，但原始规划目标函数最优值为变换中历次从行（列）中减去（或加上的）常数之代数和。该题变换中共减去28，故本例最优费用值为28。3从前所述，指派问题的关键是如何将原规划的费用矩阵变换成全分配矩阵，现不加证明的阐述其变换步骤（仍结合前例说明）。1) 修改费用矩阵，使矩阵的每一行和第一列至少出现1个零元素，处理方法即为每行（每列）都减去该行（列）的最小元素。第十四、十五

14、讲 9 13 15 411 16 14 138 14 4 157 9 10 24,114241，分别减行5 9 11 00 5 3 24 10 0 115 7 8 053列减5 4 11 00 0 3 24 5 0 115 2 8 0第十四、十五讲 2) 试图制订一个完全分配方案，该方案只与表中零元素相对应。从第行开始，依次检查各行，直到找出只有一个未标记的零元素的一行为止。如果在零元素上有一个符号或，则称零元素已标记。符号表示分配所在行的那一位教师担任所在列的那一门课程。对未做标记的零元素标后，应对同一列其它的零元素画。 5 4 11 0 0 3 24 5 115 2 8 第十四、十五讲 现

15、在依次检查每列中只含一个未标记的零元素，并给未标记的零元素标。对同一行其它的零元素画（如果有的话）。如果有多行多列同时有2个或以上的未标记零元素，则可将其中的任意行或列中一个未标零元素标，并将同行和同列的其他零元素画。 5 4 11 3 24 5 115 2 8 第十四、十五讲 因为本例此时不可能制定出只包含零元素的完全分配方案，于是画出最少数目的水平线和垂直线，使它们穿过每行每列的零元素至少一次。其画线步骤如下：检查所有尚未分配（即未标记）的行，并记上。5 4 11 3 24 5 115 2 8 第十四、十五讲 检查那些尚未检查过的，而在已检查过的行中有零元素的列，并记上。检查那些尚未检查过的，而在已检查过的列中有标记的行，并记上。 5 4 11 3 24 5 115 2 8 第十四、十五讲 重复步骤和，直到不能进一步检查为止。本例中，第轮检查以后即停止。在所有未检查的行和已检查的列画直线，这些线可覆盖所有的零。5 4 11 3 24 5 115 2 8 第十四、十五讲 在上述最后的缩减矩阵中，检查那些没有线通过的元素。设k为其中最小元素。找出含有未画线元素的各行，将这些行的每个元素减去k。本例中，k=2，因而由第1行、第4行减去2，可得 3 2 9 20 0 3 24 5 0 113 0 6 2第十四、