管理运筹学第06章整数规划

1、管理运筹学第6章 整数规划 整数规划（integer programming简记IP），就是要求一部分或全部决策变量必须取整数值的规划问题。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松驰问题（slack problem）。若松驰问题是一个线性规划，则称该整数规划为整数线性规划（integer linear programming），它实质上是在线性规划的基础上，给一些或全部决策变量附加取整约束得到的。本章主要研究整数线性规划。第6章 整数规划 整数规划分为以下几种类型：（1）所有变量都取整数的规划称为纯整数规划，要求所有变量都取整的规划问题称为纯整数规划问题（

2、pure integer programming）；（2）部分变量取整数的规划称为混合整数线性规划。如果仅仅是要求一部分变量取整，则称为混合整数规划问题（mixed integer programming）。（3）所有变量都取0、1两个值的规划称为0-1型整数线性规划，部分变量取0、1两个值的规划称为0-1混合规划。6.1 整数线性规划的数学模型称所有的变量都限制为非负整数的数学规划为纯整数规划，称部分变量限制为非负整数规划为混合整数规划，所有变量都取0、1两个值的规划称为0-1型整数线性规划。本章仅讨论约束条件和目标函数均为线性的整数规划问题，即整数线性规划问题（以下简称整数规划）。6.1

3、整数线性规划的数学模型其数学模型的一般形式是：Max(或Min)z= 通过整数线性规划模型的一般形式可以看出，整数规划与线性规划既有密切的联系，又有本质的区别，而对于它们解的关系也可以通过下面的例子来说明。6.1 整数线性规划的数学模型 【例6-1】设线性规划问题为: max z=2x1+3x2x1+x24 s.t. -4x1+5x210 x1 x20 相应的整数规划问题为： max z=2x1+3x2 x1+x24 s.t. -4x1+5x210 x1 x20 x1、x2为非负整数6.1 整数线性规划的数学模型由以上例子可以看到，线性规划的可行解的集合是一个凸集，且任意两个可行解的凸组合仍为

4、可行解。但是整数线性规划的可行解集合是线性规划问题可行解集合的一个子集，任意两个可行解的凸组合不一定满足整数约束条件，因而不一定仍为可行解。但由于整数线性规划问题的可行解一定也是它的线性规划问题的可行解，所以整数线性规划最优解的目标函数值不会优于相应线性规划最优解的目标函数值。6.1 整数线性规划的数学模型一般情况下，线性规划问题的最优解不会正好满足变量的整数约束条件，因而不是整数线性规划的可行解， 为了满足整数解的要求，最容易想到的办法就是把求得的非整数解进行四舍五入处理来得到整数解，但这往往是行不通的。通过例题的图示可以看到，舍入处理会出现两方面的问题：一是化整后的解根本不是最优点A，而是

5、解周围的四个整数点；二是化整后，虽然整数点中有可能包含可行解，但在可行域内，这些可行解并非是最优解。因此，有必要另行研究整数线性规划的求解方法，下面主要介绍分枝定界法和割平面法。 6.2 分枝定界法与线性规划不同，整数规划问题中的的变量只能取离散的整数值，也就是可行解的总数是有限的，从有限多的可行解中寻找最优解的最简单的方法就是把问题的解全部列出来，然后找出最优，也就是所谓的枚举法。但对于一般的整数规划问题，由于可行解总数随问题规模的增加（变量的增加）而成指数倍增长，在这种情况下枚举法就失去了意义。针对这种情况，人们在枚举法的基础上提出了分枝定界法（branch and bound metho

6、d），分枝定界法是一种隐枚举法（implicit enumeration），它不是一种有效算法，只是对枚举法的一种改进。6.2 分枝定界法分枝定界法的解题思路由分枝和定界两部分组成。“分枝”就是在整数规划的松驰问题的最优解不符合整数要求时，即 不能满足整数要求时，取不超过 的最大整数 ，并构造两个约束条件： 和 ，把这两个约束条件分别加到上述松驰问题的解空间上，从而产生两个互斥的线性规划子问题。所谓“定界”，是在分枝过程中，若某个子问题恰巧获得了整数规划问题的一个可行解，那么，就可以把它的目标函数值作为一个“界限”，并用这个界限来衡量其它分支。6.2 分枝定界法 【例6-2】 某工厂生产 两种

7、产品，产品分别由 两种部件组装而成，每件产品所用部件数量和部件的产量限额以及产品利润由表6-1给出。如何安排 的生产量，该厂的获利最大。6.2 分枝定界法通过上面的例题，可以将分支定界法解整数规划问题的步骤总结如下：第一步：称整数规划问题为问题A，它的松驰问题为问题B，以Zb为问题A的目标函数的初始界（如已知问题A的一个可行解，则可取它的目标函数值为Zb）。对最大化问题A，Zb为下界；如果问题A为最小化问题，Zb为上界。对问题B进行求解。第二步：如果问题B无可行解，则问题A也无可行解；如果问题B的最优解符合问题A的整数要求，则它是问题A的最优解。出现上述两种情况时，求解过程到此结束。如果问题B

8、的最优解存在，但不符合问题A的整数要求，则转到第三步。6.2 分枝定界法第三步：对问题B任选一个不符合整数要求的变量进行分支。即选择 ，且取不超过 的最大整数 ，并构造两个约束条件： 和 ，把这两个约束条件分别加到上述松驰问题的解空间上，从而产生两个互斥的线性规划子问题，并对这两个子问题进行求解。第四步：考查所有子问题，如其中有某几个存在最优解，且其最优解满足问题A的整数要求，则以它们中最优的目标函数值和界Zb作比较。若比界Zb更优，则以其取代原来的界Zb，并称其相应的后继问题为问题C。否则，原来的界不变。6.2 分枝定界法第五步：不属于的子问题中，若存在最优解、且其目标函数值比界Zb更优的子

9、问题为待检查的子问题。如不存在待检查的子问题，当问题存在时，问题的最优解就是问题的最优解；当问题不存在时，和界Zb对应的可行解就是问题的最优解。Zb即为问题的最优解的目标函数值，求解结束。如存在待检查的子问题，则选择其中目标函数值最优的一个子问题，改称其为问题。回到第三步重新计算。6.2 分枝定界法当最低一层子问题出现以下三种情况之一时，分枝定界算法终止：（1）子问题无可行解；（2）子问题已获得整数解；（3）子问题的目标函数值超过上界。6.3 割平面法割平面法在1958年由高莫瑞(R.E.Gomory)首先提出，故又称为Gomory 割平面法，是求解整数规划的基本方法之一。割平面得基本思想是：

10、首先放弃变量的整数要求，求得线性规划的最优解。如果最优解恰是一个整数解，则线性规划的最优解就是相应的整数规划的最优解。如果线性规划的最优解不是整数解，则要求构造一个新的约束，对线性规划问题的可行域进行切割，切除已经得到的线性规划的最优解，但保留原可行域中所有的整数解，求解新的线性规划问题，如果最优解仍不是整数解，再增加附加的约束将其切除，但仍保持最初可行域中所有的整数解，如此一直进行，直至得到一个整数的最优解为止。6.3 割平面法设放弃变量整数要求得到的线性规划的最优单纯形表如下：其中x1，xr，xm为基变量，xm+1，xj，xn为非基变量。设其中基变量xr的值br不是整数，且br=Ir+Fr

11、其中Ir是br的整数部分，Fr是小数部分，即Ir=0，1，2，0Fr16.3 割平面法设Irj是yrj的整数部分，Frj是小数部分，则yrj=Irj+Frj其中Irj=0，1，2，由于yrj可能是整数，因此:0Frj1这样，第r个约束成为 （6.1）6.3 割平面法将yrj和br写成整数部分和小数部分:或（6.2）由于 ，以及因此对于（6.2）中的任何（整数或非整数的）可行解，有 （6.3） 6.3 割平面法对于任何可行的整数解，xr和xj都是整数，因此 是整数，即 =，-2，-1，0因此对于整数可行解，约束（3.2.2）可以写成更严格的不等式（6.4）将线性规划（非整数）的最优解（x1xrx

12、m，xm+1xjxn）=（b1br，bm，000）代入（3.4）的左边，得到 6.3 割平面法线性规划（非整数）的最优解不满足（6.4）。因此，约束（6.4）具有以下性质：（1）线性规划可行域中的任何整数解都满足这个约束；（2）线性规划的（非整数）最优解不满足这个约束。这样，在原线性规划的约束条件基础上增加约束（6.4），新的可行域将切除原线性规划非整数的最优解而保留所有整数可行解。6.3 割平面法 【例6-3】 用割平面法求解以下整数：max z=3x1+2x2 2x1+3x210s.t. x1+0.5x23.5 x1 x20 x1，x2为整数6.4 0-1型整数规划及其应用6.4.1 0-

13、1型整数规划0-1型整数规划是一般线性整数规划的特例，它的决策变量 只能取0或1两个值，称这种变量为0-1变量或二进制变量（logical variable）或逻辑变量(binary variable)。0-1变量常被用来表示系统是否处于某个特定状态，或者决策时是否取某个特定方案。例如由于0-1变量可以表示为 ， 取整；因此，0-1型整数规划与一般线性整数规划模型形式上是一致的。0-1型整数规划不仅广泛应用于科学技术问题，在经济管理问题中也有十分重要的应用。6.4 0-1型整数规划及其应用【例6-4】 厂址选择问题。在5个地点中选3处建生产同一产品的工厂，在这5个地点建厂所需投资，占用农田，建

14、成以后的生产能力等数据如表6-2所示：现在有总投资800万元，占用农田指标60亩，应如何选择厂址，使建成后总生产能力最大。6.4 0-1型整数规划及其应用0-1型整数规划是一种特殊形式的线性整数规划，如果一个0-1型整数规划含有n个变量，则可以产生 个可能的变量组合，把所有的可能的情况逐一列举出来，然后检验哪种情况是最优的，这就是所谓的“完全枚举法”。这种方法对变量较少的0-1规划是适用的，但是对于变量很多时，用这种方法就几乎不可能了。下面主要介绍一种对0-1规划的求解存在更简便的方法，称为“隐枚举法”。如果一个0-1型整数规划含有n个变量，则可以产生 个可能的变量组合。6.4 0-1型整数规

15、划及其应用在这 个可能的变量组合中，首先用是否满足约束条件来确定其是否为可行解。如果发现一个可行解，则根据它的目标函数值可以产生一个界限，也就是“定界”，对于目标函数值比它差的变量组合就不必再去检验它的可行性。在以后的求解过程中，每当发现比原来更好的可行解，则以此替代原来的界限，这样就可以减少运算次数，使最优解能较快地被发现。 【例6-5】 用隐枚举法求解0-1规划问题：0或16.4 0-1型整数规划及其应用注意当发生下列三种情形之一时，应该实施剪枝：（1）多个分枝的子问题都是可行解时，保留目标值最大的分枝并将该目标值作为最优目标值的“下界” ，将目标值较小的分枝剪去；（2）将分枝边界值低于最

16、优目标值“下界”的分枝剪去；（3）将无论后续决策变量取什么值都不可能存在可行解的分枝剪去；如某0-1规划的一个约束条件是 ，那么对 的分枝就可以实施剪枝了。6.4 0-1型整数规划及其应用注意当发生下列三种情形之一时，应该实施剪枝：（1）多个分枝的子问题都是可行解时，保留目标值最大的分枝并将该目标值作为最优目标值的“下界” ，将目标值较小的分枝剪去；（2）将分枝边界值低于最优目标值“下界”的分枝剪去；（3）将无论后续决策变量取什么值都不可能存在可行解的分枝剪去；如某0-1规划的一个约束条件是 ，那么对 的分枝就可以实施剪枝了。6.4 0-1型整数规划及其应用6.4.2 指派问题在现实世界经常会

17、遇到这样的问题：有 个人恰好可承担 项任务，一项任务由一个人完成，一个人只完成一项任务；由于个人的专长不同，完成各项任务的效率也就不同，于是产生了应指派哪个人去完成哪项任务，才能使完成 项任务总的效率最高（所需总时间最少）的问题。这类问题称为指派问题或分派问题（assignment problem）。6.4 0-1型整数规划及其应用1. 指派问题的标准形式及数学模型指派问题的标准形式（以人和事为例）是：有n个人和n件事，已知第i个人作第j件事的费用为 ，要求确定人和事之间的一一对应的指派方案，是完成这n件事的总费用最少。为了建立标准指派问题的数学模型，引入 个0-1变量： 若指派第i人作第j件

18、事 若不指派第i人作第j事 i，j=1,2,n 6.4 0-1型整数规划及其应用这样，问题的数学模型可写成 （6.5） （6.6） s.t （6.7） （6.8） 其中，（6.5）表示每件事必有且只有一个人去做，（6.6）表示每个人必做且只做一件事。6.4 0-1型整数规划及其应用注：1 指派问题是产量（ ）、销量（ ）相等，且 = =1，i，j=1,2,n的运输问题。2 有时也称 为第i个人完成第j件工作所需的资源数，称之为效率系数（或价值系数）。并称矩阵 C= = （6.9）为效率矩阵（或价值系数矩阵）。6.4 0-1型整数规划及其应用并称决策变量 排成的nn矩阵X= = （6.10）为决

19、策变量矩阵。(6.10)的特征是它有n个1，其它都是0。这n个1位于不同行、不同列。每一种情况为指派问题的一个可行解。共n!个解。其总的费用 z =CX 这里的表示两矩阵对应元素的积，然后相加。6.4 0-1型整数规划及其应用【例6-6】 已知效率矩阵 C= 则 X（1）= ， X（2）= 都是指派问题的最优解。6.4 0-1型整数规划及其应用【例6-7】 某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司Ai（i=1，2，5）对新商店Bj（1，2，5）的建造费用的报价（万元）为 （i，j=1,2,5）,见表63。商业公司应当对5家建筑公司怎样分派

20、建筑任务，才能使总的建筑费用最少？6.4 0-1型整数规划及其应用2. 匈牙利解法原理【定理6.1】 设指派问题的效率矩阵为C= ，若将该矩阵的某一行（或某一列）的各个元素都减去统一常数t（t可正可负），得到新的效率矩阵 ，则以 为效率矩阵的新的指派问题与原指派问题的最优解相同。但其最优解比原最优解之减少t.【推论6.1】 若将指派问题的效率矩阵每一行即每一列分别减去各行及各列的最小元素，则得到新指派问题与原指派问题有相同的最优解。6.4 0-1型整数规划及其应用定义：在效率矩阵C中，有一组在不同行不同列的零元素，称为独立零元素组，此时每个元素称为独立零元素。【例6-8】 已知： C= 则 =

21、0， =0， =0， =0是一个独立零元素组 ， =0， =0， =0， =0分别称为独立零元素。 =0， =0， =0， =0也是一个独立零元素组，而 =0， =0， =0， =0就不是一个独立零元素组，因为 =0与 =0这两个零元素位于同一列中。6.4 0-1型整数规划及其应用 【例6-9】 已知矩阵 C1= ，C2= ，C3= 【定理6.2】 效率矩阵C中独立零元素的最多个数等于能覆盖所有零元素的最少直线数。6.4 0-1型整数规划及其应用分别用最少直线去覆盖各自矩阵中的零元素：可见，C1最少需要4条线，C2最少需要4条线，C3最少需要5条线，方能划掉矩阵中所有的零。即它们独立零元素组中

22、零元素最多分别为4，4，5。6.4 0-1型整数规划及其应用【例6-10】 给定效率矩阵 C= 求解该指派问题。6.4 0-1型整数规划及其应用【例6-11】 某工厂有4名工人A1，A2，A3，A4，分别操作4台车床B1，B2，B3，B4。每小时单产量如表6-5所示，求产值最大的分配方案。6.4 0-1型整数规划及其应用【例6-12】 现有4个人，5件工作。每人做每件工作所耗时间如表6-6所示：问指派那个人去完成哪项工作，可是总消耗最小？6.4 0-1型整数规划及其应用【例6-13】 对例6.7的指派问题，为了保证工程质量，经研究决定，舍弃建筑公司A4和A5，让技术力量较强的建筑公司A1、A2

23、、A3来承建。根据实际情况，可以允许每家建筑公司承建一家或两家商店。求使总费用最少的指派方案。6.4 0-1型整数规划及其应用【例6-14】 分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务，每人完成各项任务的时间如表6-7所示。由于任务重，人数少，考虑：a) 任务E必须完成，其它4项任务可选3项完成。但甲不能做A项工作。b) 其中有一人完成两项，其他人每人完成一项。试分别确定最优分配方案，使完成任务的总时间最少。6.5 整数线性规划问题的计算机求解 6.5.1 利用Excel求解整数线性规划【例6-15】 公司的研发部最近开发出了三种新产品，但是，为了防止生产线的过度多元化，公司管理

24、层增加了如下的约束： 约束1:在三种新产品中，最多只能选择两种进行生产。 这些产品都可以在两个工厂中生产，但是，为了管理方便，管理层加入第二个约束。 6.5 整数线性规划问题的计算机求解约束2:两个工厂中必须选出一个专门生产新产品。 两个工厂中各种产品的单位生产成本是相同的，但是，由于生产设备的不同，每单位产品所需要的生产时间是不同的。下表给出了这方面的相关数据， 包括生产出来的产品每周内估计的可销售量。管理层制定的目标是通过选择产品、工厂以及确定各种产品的周产量，使得总利润最大化。6.5 整数线性规划问题的计算机求解可以得到该问题的整数规划模型如下：6.5 整数线性规划问题的计算机求解其电子表格模型见图6-5：6.5 整数线性规划问题的计算机求解其中，决策变量为浅黄色表示，给定的条件为黄色表示，目标函数用红色表示。具体可以用表达式表达如下：工厂1实际使用E6:=SUMPRODUCT(C6:E6,C10:E10);工厂2实际使用E7: =SUMPRODUCT(C7:E7,C10:E10);工厂1修正可用工时H6:I6+20*D17；工厂2修正可用工时H7：=I7+20*(1-D17)；可销售限制My: =