运筹学第05章整数规划

1、第五章 整数规划(Integer Programming)整数规划的基本问题及其数学模型割平面法分支定界法0-1整数规划指派问题WinQSB软件应用第一节 整数规划的基本问题及其数学模型一、问题的提出 实际工作中的某些规划问题要求部分变量或全部变量取整数值，我们称这样的问题为整数规划问题(Integer Programming，IP)。不考虑整数要求，由其他约束条件和目标函数构成的规划问题称为该整数规划问题的松弛问题(Slack Problem)。若松弛问题是一个线性规划问题，我们称该整数规划问题为整数线性规划(Integer Linear ProgrammingILP)。 【例5-1】某工地

2、需要长度不同、直径相同的成套钢筋，每套钢筋由两根7米长和七根2米长的钢筋组成。现有长15米的圆钢毛坯150根，应如何下料，使废料最少？ 解：本题中没有说明15米长的圆钢毛坯有哪些下料方式，故需要首先找出下料方式。将15米长的圆钢毛坯切割为7米和2米两种长度的钢筋有三种方式，如表5-1所示。 170304121021废料(米)2米长的钢筋(根)7米长的钢筋(根)下料方式 设 分别表示采用第1、2、3种下料方式所切割的圆钢毛坯数目。则废料可表示为下列形式： 看约束条件。首先，工地需要的是成套钢筋，故7米长和2米长的钢筋数之比应满足2：7，用线性方程来表示，即： 整理得： 即： 综合分析，问题的数学

3、模型为： 【例5-2】现有资金总额为B，可供投资项目有 n 个，项目 j 所需投资额和预期收益分别为 aj 和 cj ( j1,2，n )。同时，由于种种原因，有三个附加条件：第一，若选择项目1，就必须同时选择项目2，反之则不一定；第二，项目3和项目4中至少选择一个；第三，项目5、项目6和项目7中恰好选择两个。另外，圆钢毛坯总数为150根，故 还应满足下面这个条件，即： 应当怎样选择投资项目，才能使总预期收益最大？则问题可表示为： 【例5-3】工厂 A1 和 A2 生产某种物资，由于该种物资供不应求，故需要再建一家工厂，相应的建厂方案有A3和A4两个。这种物资的需求地有B1、B2、B3、B4

4、四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij 见表5-2。 解：每一个投资项目都有被选择和不被选择两种可能，令： 表5-2150300400350需求量(千吨/年)2005254A42002167A36007538A24004392A1生产能力(千吨/年)B4B3B2B1 cij BjAi 工厂 A3 或 A4 开工后，每年的生产费用估计分别为1200万元或1500万元。现要决定应该建设工厂 A3 还是 A4 ，才能使今后每年的总费用(即全部物资运费和新工厂生产费用之和)最少。 解：这是一个物资运输问题，其特点是事先不能确定应该建A3 和 A4 中的哪一个，因而不知

5、道新厂投产后的实际生产费用。为此，引入0-1变量： 设 xij 为由 Ai 运往 Bj 物资数量(千吨)，(i,j1,2,3,4)。则问题的数学模型为： 二、整数规划模型的一般形式及解的特点 整数线性规划数学模型的一般形式为： 一般来说，整数线性规划可分为以下几种类型： 1. 纯整数线性规划(Pure Integer Linear Programming)：指全部决策变量都必须取整数值的整数线性规划，也称为全整数规划。 2. 混合整数线性规划(Mixed Integer Linear Programming)：指决策变量中一部分必须取整数值，而另一部分可以不取整数值的整数线性规划。 3. 0-

6、1整数线性规划(Zero-one Integer Linear Programming)：指决策变量只能取 0 或 1 两个值的整数线性规划。 第二节 割平面法 割平面法由高莫累(Gomory)于1958年提出。其基本思想是放宽变量的整数约束，首先求对应的松弛问题最优解，当某个变量xi不满足整数约束时，寻找一个约束方程并添加到松弛问题中，其作用是割掉非整数部分，缩小原松弛问题的可行域，最后逼近整数问题的最优解。一、割平面法的基本思想 ILPLP是整数解？单纯形法求解建立割平面方程，加入LP对偶单纯形法求解计算结束是否 考虑松弛问题为标准形线性规划问题的纯整数规划问题(ILP)： 假设约束条件中

7、 aij(i1,2,m ；j1,2，,n)和 bi(i1,2,m)均为整数(若不为整数，可令等式两边同乘一个倍数化为整数)。 下面先通过一个例子来说明割平面法的基本思想。 【例5-5】 将该问题图示如下图 ： 从图(a)中可以看出，松弛问题的最优解为X*=(5/3，5/2)T，它不是一个整数解。因此我们设法给原线性规划问题增加一个约束条件，从而把包括X*在内的一部分不含整数点的可行域从原可行域中分割出去。再求增加了这个约束条件后的新的线性规划问题的最优解。 在上图的基础上，增加约束条件: 从图5-1(b)中可以看出，当我们增加了约束条件“后，得到新的最优解X* = (2，2)T，它便是整数规划

8、问题最优解。因此，割平面法的关键就在于如何寻找这类新的约束条件。 二、Gomory约束 假设用单纯形法求得的线性规划问题最优解不是整数解，其中必然有某个或某几个基变量不为整数。记 B 为松弛问题的最优基，则问题的基最优解为： (2,2)不妨设第r 个分量 不为整数，根据最优单纯形表可得： (5.1)将 和 分成整数部分和非负真分数之和，即：代入上式得：(5.2)(5.3)(5.4)移项，得：(5.5) 因为变量必须取整数，即上式左边必须是整数，从上式右边看，因为0fr1，所以不能为正，即： 割平面方程(5.6)即: (5.7)三、割平面法的算法步骤 步骤1：将约束条件系数及右端项化为整数，用单

9、纯形法求解整数规划问题(ILP)的松弛问题(LP)。设得到最优基B，相应的基最优解为X*。 步骤2：判别X*的所有分量是否全为整数？如是，则X*即为(ILP)的最优解，算法终止；若否，则取X*中分数最大的分量 ，引入割平面(5.7)。 步骤3：将式(5.7)引入松弛变量后加入原最终单纯形表，用对偶单纯形法继续求解。转步骤2。 【例】用割平面法求解数规划问题不考虑整数要求，化为标准型：标准型的技术系数矩阵为：Cj1100CBXBbx1x2x3x40 x3621100 x420450111001 x15/3105/6-1/61x28/301-2/31/300-1/6-1/61 x1311/21/2

10、00 x4803-2101/2-1/20在松弛问题最优解中，x1, x2 均为非整数解，由上表有：将系数和常数都分解成整数和非负真分数之和: CBXBbx1x2x3x41 x15/3105/6-1/61x28/301-2/31/300-1/6-1/6 以上式子只须考虑一个即可，解题经验表明，考虑式子右端最大真分数的式子，往往会较快地找到所需割平面约束条件。以上两个式子右端真分数相等，可任选一个考虑。 引入松弛变量 x5 后得到下式，将此约束条件加到上表中，继续求解。 现选第二个式子，并将真分数移到右边得： 移项的割平面方程为： 等式右边满足： 0 x5-2/300-1/3-1/31Cj1100

11、0CBXBbx1x2x3x4x51x15/3105/6-1/601x28/301-2/31/30j00-1/6-1/601x10100-15/21x240101-20 x320011-3j0000-1/21 x121010-1/21x2201-1010 x420011-3j0000-1/2【例5-6】用割平面法求解例5-5。 首先，将整数约束去掉，将松弛问题化为标准形: 约束条件的系数为: 因基变量x15/3，x25/2，均为非整数，故该最优解不是整数规划的可行解。若以变量 x1 所在的行为源行，得到相应的割平面为： 001110205x40012310 x30 x4x3x2x1bXBCB00

12、1101/32/3110/3x10-1/31/30j10205x401-1/31/3015/3x1-1/6-1/300j1/20105/2x211(5.8)左端加入松弛变量，得到： (5.9)将式(5.9)加入上表中，用对偶单纯形法继续求解如下表： 0-1/6-1/300j1-2/3-1/300-2/3x5001/20105/2x210-1/31/3015/3x11x5x4x3x2x1bxBcB000112x1-1/40-1/400j-3/211/2001x403/40-1/4102x21-1/201/2011因此，原整数规划问题的最优解为X*=(2，2)T，其最优值z*=4。 将上式代入割平

13、面方程：整理后得到： 根据原整数规划问题的约束条件可以得到：得到： 图解法中割平面方程 如何得到？原整数规划问题标准化后其形式为： 第三节 分支定界法 分枝定界法是在20世纪60年代初由Land Doing和Dakin等人提出的适合于解纯整数或混合正数规划问题。 分支定界法实际是一种隐枚举法或部分枚举法，它是在枚举法基础上的改进，在枚举过程中逐批把一部分可行解排斥在考察范围之外，从而大大减少了计算量。分支定界法的关键是分支和定界。 若松弛问题的最优解不符合整数要求，假设变量不符合整数要求， 为不超过 的最大整数，则在松弛问题中分别加入两个约束条件： 和 ，以形成两个子问题。 一、分支定界法的基

14、本思想 两个子问题的可行域的并集包含了原问题(ILP)的全部可行解，而包括原最优解在内的松弛问题的部分非整数解被剔除了。然后分别求解两个子问题，根据需要，各子问题可以再产生自己的子问题。这个过程就是分支。 在分支过程中，若某个子问题的最优解为整数解，其目标函数值就是整数规划问题的一个“界限”，可以此作为判断其他分支优劣的一个依据。二、分支定界法的一般步骤 【例5-7】用分支定界法求解例5-5。 解：根据前面的求解知道，(LP)的最优解为 x15/3，x25/2，z25/6。 若某一子问题最优解(无论是否为整数解)的目标函数值小于或等于该界限，则可以将该子问题剔除而不予考虑了。若有其他子问题的最

15、优解为整数解，则将其目标函数值与原来的界限相比较，取更优的一个作为新的界限。这个过程就是定界。 由于(LP)的最优解不是整数解，可任选一个变量进行分支。若选 x15/3进行分支，则分支出的约束条件为： (5.10)和 (5.10) 分别将上述两个约束条件加入(LP)中，因此原问题的松弛问题(LP)被划分为两个子问题： 0,21xx 再求解(LP2)：最优解为 x11，x25/2，最优值 z7/2最优解为 x12，x22，最优值 z4故取 z4 作为(ILP)最优值的一个下界。 先求解(LP1)： 由于(LP1)的最优值为7/24，故其子问题的目标函数值不会超过7/2，也不会超过4。因此(LP1

16、)是一个失去希望的问题，不必再对它进行分支。若(LP1)的最优值大于4，需要对它进一步分支。 上述求解过程可用图5-4来说明： 分支定界法解整数规划的一般步骤可归结如下： 步骤1：取(ILP)的目标函数值的初始下界 。用单纯形法求解整数规划问题(ILP)的松弛问题(LP)。 步骤2：若问题(LP)不可行，则(ILP)也不可行，算法终止；若问题(LP)的最优解X*为(ILP)的可行解，则它就是(ILP)的最优解，算法终止。若问题(LP)的最优解存在，但不满足(ILP)的整数要求，转步骤3。 步骤3：任选X*中不满足整数要求的一个变量 进行分支，即对问题(LP)分别增加约束条件 和 ，形成两个子问

17、题，并求解。转步骤4。 步骤4：考察所有子问题，有以下四种情况： a.若某个子问题的最优解也是问题(ILP)的可行解，则将它的目标函数值与 作比较，并取较优的一个作为新的界限 。如所有子问题都已考察完毕，则保留下来的 及其对应的解即为问题(ILP)的最优解。 b. 若某个子问题的最优解不是(ILP)的可行解，且其最优值不如 ，则将这一分支删掉。 c. 若某个子问题不可行，则将这一分支删掉。 d. 若某个子问题的最优解不是(ILP)的可行解，且其最优值优于 ，则该问题为待考察的问题。如有多个问题待考察，优先对其中最优值最大的一个子问题进行考察，转步骤3。 解：用图解法解对应的(LP)问题，如表所

18、示，获得最优解。【例】用分支定界法求解整数规划问题(3.25,2.5)x1x2 选 x2 进行分支，即增加两个约束，x2 2和 x23，分支出以下两个问题：x1x2x1x2(3.5,2)用图解法求解 LP1 问题：用图解法求解 LP2 问题：x1x2(2.5,3) 对(LP1)继续分支，加入约束 x13和 x14，分支出以下两个问题：x1x2(3,2)用图解法求解 LP3 问题：x1x2(4,1)用图解法求解 LP4 问题：用图解法求得 LP2 问题的目标函数值为：所以 LP2 问题不需要进行继续分支。树形图如下：x22x23x13LPLP1LP2LP3LP4x1=13/4, x2=5/2Z(

19、0) 59/4=14.75x1=7/2, x2=2Z(1) 29/2=14.5x1=5/2, x2=3Z(4) 27/2=13.5x1=3, x2=2Z(2) 13x1=4, x2=1Z(3) 14x14第四节 01整数规划一、0-1变量的应用 第一节中我们讨论过0-1变量，即只能取0或1的变量，它是逻辑变量，通常用来表示在是与否之间二选一的问题，如某个方案A是否被选中，可用下面的0-1变量来表示： 当采取方案A时 当不采取方案A 时【例5-8】含有相互排斥的约束条件的问题。 设某厂生产第j 种产品的数量为 xj (j=1，2，3)，其材料可在甲或乙中选择一种，当选择甲或乙时，相应的材料消耗的

20、约束条件分别为： 和(5.12 a)(5.12 a)试问这类相互排斥的约束条件如何体现在模型中？ 解：引入0-1变量： 和 因而，两个相互排斥的约束条件可用下列线性约束条件统一起来： 其中M是一个充分大的数。 若y1=1，而y2=0，即选用材料乙，由(5.12d) 式得：式(5.12c)自然成立； 若y1=0，而y2=1，即选用材料甲，由(5.12c) 式得：式(5.12d)自然成立. 【例5-9】固定费用问题。有一种自然资源被用于生产三种产品，资源量、产品单件可变费用及售价、资源单位消耗量及组织三种产品生产的固定费用见表5-5。要求制订一个生产计划，使总收益最大。 12108单位售价2001

21、50100固定费用654 单位可变费用100321C300432B500842A资源量IIIIII 单耗量资源产品解：设 xj 表示三种产品的产量(j=1，2，3)。 引入0-1变量： 则问题的数学模型可归结如下： 如果生产第 j 种产品，则其产量xj0，由xjMjyj 知，yj1。相应的固定费用将被考虑，Mj 为 xj 的某个上界。 二、0-1型整数规划的解法 0-1型规划是一类特殊的整数规划，因为变量只有0或1两个可能的取值，故最多有 2n 个可行解，理论上可以用枚举法进行求解。但当 n 较大时，采用完全枚举法求解几乎是不可能的。 隐枚举法是求解0-1整数规划问题的一种比较简便的方法。其实

22、质也是一种分支定界法。 隐枚举法是是在 2n 个可能的变量组合中，只有一部分是可行解。只要发现某个变量组合不满足其中一个约束条件，就不必再检验是否满足其它约束。 如所有约束条件都满足，就是0-1规划的一个可行解，可根据相应的目标函数值产生一个过滤条件，对于目标函数值劣于该可行解的变量组合不必再去检验其可行性。在以后的求解过程中，如发现某个可行解比原来保留的可行解更优，则用它替换原来的过滤条件。 确定初始解满足约束？产生界限是停止检查约束否分支，计算目标值目标值优？剪支否是【例5-11】求解0-1整数规划 (5.13a)(5.13b)(5.13c)(5.13d)(1，1，1)(1，1，0)(1，

23、0，1)(1，0，0)(0，1，1)(0，1，0)(0，0，1)(0，0，0)dcba过滤条件约束条件z 值(x1，x2，x3)0z 05z 5-2338z 816【例5-12】求解0-1整数规划 步骤1：将问题转化为如下标准形式： 如目标函数为max z，令 ，可化为 。如某个变量 的系数为负，令 ，使系数变正。 其中cj0，且c1c2cn。 如约束条件为，两边同乘(-1)；如约束条件为等式，可令变量 ，代入目标函数和其它约束条件中，将 xn 消掉。 按目标函数中系数由小到大的顺序重新排列变量，并将约束条件中的排列顺序做相应改变。 目标函数进行调整： (5.14a)(5.14b)数学模型调整

24、为： 步骤2：令所有变量取0，求出目标函数值，代入约束条件检查是否可行，如果可行即为问题的最优解；否则转下一步。 令 ， 得-10，代入两个约束条件： 各约束条件均不满足。 步骤3：分支和定界。 依次令各变量分别取0或1，将问题划分为两个子问题，分别检查是否可行，如不可行继续对边界值较小的子问题分支，直到找出一个可行解为止，这时得到 值的一个上界。步骤4：考察所有子问题，有以下四种情况： 若某个子问题的边界值对应原问题的可行解，则将它的边界值与保留的 值作比较，并取较优的一个作为新的 值。如所有子问题都已考察完毕，则保留下来的 值及其对应的解即为0-1整数规划问题的最优解。 若某个子问题的边界

25、值大于保留下来的 值，不管其是否可行，则将这一分支剪掉。 若某个子问题不可行，则将这一分支剪掉。 若某个子问题可行且边界值优于 值，但该边界值对应的解不是可行解，则该问题待考察。如有多个问题待考察，优先对其中最优值最大的一个子问题进行考察，转步骤3。(0，0，1，0，1)(0，0，1，1，0)(0，0，0，1，0)(0，1，0，1，0)(0，1，1，0，0)(0，0，1，0，0)(1，0，1，0，0)(1，1，0，0，0)(0，1，0，0，0)(1，0，0，0，0)(0，0，0，0，0)(x2，x3，x5，x4，x1)ba备注约束条件z 值序号上述求解过程也可用表格表示： 21-3-1-5-3

26、-4-6-8-10 -4，剪枝 -4，剪枝 可行 -4，剪枝3 -4，剪枝 -4，剪枝 -4，剪枝所以，最优解： 即原问题的最优解为： 第五节 指派问题一、指派问题的数学模型 指派问题又称分配问题，是指将 m 项工作分配 n 个工人去完成(通常mn)，应如何分工使总工时或总费用最少的一类问题。 现有 n 项工作分配 n 个工人去完成，已知工人 j 完成工作i需要花费时间 cij 。要求每项工作只能由一个工人去完成，每个工人只能完成一项工作。应如何分工，使总工时最少？ 在实际中经常会遇到这样的问题，有n 项不同的任务，需要n 个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完

27、成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成 n 项任务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。 这类问题一般有两个要求：一是每项工作只能由一个工人去完成；二是每个工人只能完成一项工作。这类问题的标准提法如下： AnA2A1BnB2B1工作工人设： 则该问题的数学模型可写为： 【例5-13】某工厂要生产四种产品，该工厂有四个车间都可以生产这四种产品。但由于设备情况与技术情况不同，所以生产成本不同，其单位产品的生产成本如下表所示： 问应当怎样分配这四种产品到各车间，才能使总的生产成本最小？试建立该问题的数学模型。

28、 6443车间46233车间35415车间210454车间1产品4产品3产品2产品1 产品车间解：这是一个标准形式的指派问题。引入0-1变量： 这个问题的约束条件如下：(1)每个车间只能生产一种产品，即：简写为： （i =1,2,3,4） 则问题的数学模型可归结为： (2)一种产品只能由一个车间生产，即： 简写为：（j =1,2,3,4） (3)变量工 xij 必须等于0或1，即 xij =0或1。 二、匈牙利算法 分配问题是 0-1 规划的特例，也是运输问题的特例，当然可用整数规划，0-1 规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算的。 库恩(W.W.Kuhn)于

29、1955年提出了指派问题的解法，他引用了匈牙利数学家康尼格(D.Konig)的关于矩阵中独立零元素的定理：系数矩阵中独立0元素的最多个数等于能覆盖所有零元素的最小直线数，习惯上称之为匈牙利解法。 分配问题最优解的以下性质：若从系数矩阵(cij)的某行(或某列)各元素分别减去该行（列）的最小元素，得到新矩阵(cij),那么以(cij)为系数矩阵求得的最优解和利用原系数矩阵求得的最优解相同。 匈牙利算法的一般步骤可以表述如下： 步骤1：变换系数矩阵。 先把系数矩阵各行分别减去本行的最小元素，再把各列分别减去本列的最小元素，使系数矩阵中各行各列都至少有一个零元素，且不出现负数。转步骤2。 在新矩阵中

30、找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。找独立0元素，常用的步骤为： 从只有一个0元素的行开始，给这个0元素加。然后划去所在列的其它0元素，记作 ；这表示这列所代表的任务已指派完。 给只有一个0元素的列中的0元素加 ；然后划去所在行的0元素，记作 。 反复进行(1)，(2)两步，直到尽可能多的0元素都被圈出和划掉为止。 步骤2：确定独立零元素。 若仍有没有划的0元素，且同行(列)的0元素至少有两个，则从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加。 若

31、某行(某列)只有一个零元素，将该零元素加一个三角符号()，同时将该零元素所在列(行)的其它零元素划去。如此反复进行，直到系数矩阵中所有零元素都被标注或被划去。 【例5-14】已知指派问题的系数矩阵为： 解：首先，将各行分别减去本行的最小元素，然后对各列也如此，即：4123其次，确立独立零元素。 因独立零元素有4个，故得到最优解： 若元素的数目m 等于矩阵的阶数n，那么这指派问题的最优解已得到。若m n, 则转入下一步。 若独立零元素有 n 个，则令独立零元素位置对应的变量取1，其它变量取0，这样得到的矩阵X即为最优分配方案。若独立零元素不足 n 个，转步骤3。 步骤3：做能覆盖所有零元素的最少

32、直线组合。 最优解表明：车间1生产产品1，车间2生产产品2，车间3生产产品3，车间4生产产品4，得到最优值为: 对没有标的行打“”； 对打“”行中被划掉的零元素所在列打“”； 对打“”列中标的零元素所在行打“”； 重复和，直到再也不能找到可打“”行或列为止。 对未打“”的行画一直线，对打“”的列画一直线，这样就得到覆盖所有零元素的最少直线组合。转步骤4。 步骤4：继续变换系数矩阵。 【例5-15】已知指派问题的系数矩阵如下：用匈牙利算法求解。 取未被直线覆盖的元素中的最小值，令打“”行中各元素减去该最小值，同时令打“”列中各元素加上该最小值以消除负数。转步骤2。 解：首先，变换成本矩阵。 其次

33、，确立独立零元素。 因独立零元素只有3个，故不能得到最优分配方案。需要继续进行下面的步骤。 第三步，做能覆盖所有零元素的最少直线组合。 第四步，变换矩阵。在新的系数矩阵中确定独立零元素。 未被直线覆盖的元素中的最小值为2，将第一、四行各元素减2，再将第一列各元素加2，得到： 由于独立零元素有4个，因此得到最优分配方案： 最优值: 【例】有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示：求解过程如下：52895丁41013丙8954乙21176甲DCBA任务人员第一步，变换系数矩阵：问如何分派任务，可使总时间最少？ 找到 3 个独立零元素，但 m