整数规划

第五章整数规划(IntegerProgramming)整数规划的基本问题及其数学模型割平面法分支定界法0-1整数规划指派问题WinQSB软件应用第一节整数规划的基本问题及其数学模型一、问题的提出实际工作中的某些规划问题要求部分变量或全部变量取整数值，我们称这样的问题为整数规划问题(IntegerProgramming，IP)。不考虑整数要求，由其他约束条件和目标函数构成的规划问题称为该整数规划问题的松弛问题(SlackProblem)。若松弛问题是一个线性规划问题，我们称该整数规划问题为整数线性规划(IntegerLinearProgramming—ILP)。【例5-1】某工地需要长度不同、直径相同的成套钢筋，每套钢筋由两根7米长和七根2米长的钢筋组成。现有长15米的圆钢毛坯150根，应如何下料，使废料最少？解：本题中没有说明15米长的圆钢毛坯有哪些下料方式，故需要首先找出下料方式。将15米长的圆钢毛坯切割为7米和2米两种长度的钢筋有三种方式，如表5-1所示。表5-1170304121021废料(米)2米长的钢筋(根)7米长的钢筋(根)下料方式321xxx、、设分别表示采用第1、2、3种下料方式所切割的圆钢毛坯数目。则废料可表示为下列形式：31xxz看约束条件。首先，工地需要的是成套钢筋，故7米长和2米长的钢筋数之比应满足2：7，用线性方程来表示，即：774223221xxxx整理得：01414321xxx另外，圆钢毛坯总数为150根，故还应满足下面这个条件，即：321xxx、、150321xxx综合分析，问题的数学模型为：31minxxz且均取整数值0,,15001414321321321xxxxxxxxx【例5-2】现有资金总额为B，可供投资项目有n个，项目j所需投资额和预期收益分别为aj和cj(j＝1,2，…，n)。同时，由于种种原因，有三个附加条件：第一，若选择项目1，就必须同时选择项目2，反之则不一定；第二，项目3和项目4中至少选择一个；第三，项目5、项目6和项目7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？解：每一个投资项目都有被选择和不被选择两种可能，为此令：），，，（不投资对项目投资对项目njjjxj2101n,1,2,j10210max765432111或jjnjjnjjjxxxxxxxxBxaxcz则问题可表示为：【例5-3】工厂A1和A2生产某种物资，由于该种物资供不应求，故需要再建一家工厂，相应的建厂方案有A3和A4两个。这种物资的需求地有B1、B2、B3、B4四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij(j=1,2,3,4)见表5-2。表5-2150300400350需求量(千吨/年)2005254A42002167A36007538A24004392A1生产能力(千吨/年)B4B3B2B1cijBjAi工厂A3或A4开工后，每年的生产费用估计分别为1200万元或1500万元。现要决定应该建设工厂A3还是A4，才能使今后每年的总费用(即全部物资运费和新工厂生产费用之和)最少。解：这是一个物资运输问题，其特点是事先不能确定应该建A3和A4中的哪一个，因而不知道新厂投产后的实际生产费用。为此，引入0-1变量：4301AAy若建工厂若建工厂设xij为由Ai运往Bj的物资数量(千吨)，(i，j＝1,2,3,4)。则问题的数学模型为：]115001200[min4141yyxczijijij35041312111xxxx40042322212xxxx30043332313xxxx15044342414xxxx40014131211xxxx60024232221xxxxyxxxx20034333231yxxxx120044434241)4,3,2,1,(0jixij10或y二、整数规划模型的一般形式及解的特点整数线性规划数学模型的一般形式为：njjjxcz1min)(max或部分或全部取整数、njijnjijxxxnjxmibxa,,,),,2,1(0),,2,1()(211一般来说，整数线性规划可分为以下几种类型：1.纯整数线性规划(PureIntegerLinearProgramming)：指全部决策变量都必须取整数值的整数线性规划，也称为全整数规划。2.混合整数线性规划(MixedIntegerLinearProgramming)：指决策变量中一部分必须取整数值，而另一部分可以不取整数值的整数线性规划。3.0-1整数线性规划(Zero-oneIntegerLinearProgramming)：指决策变量只能取0或1两个值的整数线性规划。（三）整数规划与线性规划的关系从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得倒的解是整数可行解。举例说明。例：设整数规划问题如下且为整数0,13651914max21212121xxxxxxxxZ首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。0,13651914max21212121xxxxxxxxZ用解法求出最优解x1＝3/2,x2=10/3且有Z=29/6x1x2⑴⑵33(3/2,10/3)现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3)(2，3)(1，4)(2，4)。显然，它们都不可能是整数规划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。图因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。如上例：其中（2，2）（3，1）点为最大值，Z=4。⑴.若(LP)没有可行解，则(ILP)也没有可行解，停止计算。⑵.若(LP)有最优解，并符合(ILP)的整数条件，则(LP)的最优解即为(IP)的最优解，停止计算。⑶.若(LP)有最优解，但不符合(ILP)的整数条件，可用相应方法求解。整数规划与其松驰问题解的关系：目前，常用的求解整数规划的方法有：分支定界法和割平面法；对于特别的0－1规划问题采用隐枚举法和匈牙利法。第二节割平面法割平面法由高莫累(Gomory)于1958年提出。其基本思想是放宽变量的整数约束，首先求对应的松弛问题最优解，当某个变量xi不满足整数约束时，寻找一个约束方程并添加到松弛问题中，其作用是割掉非整数部分，缩小原松弛问题的可行域，最后逼近整数问题的最优解。一、割平面法的基本思想考虑松弛问题为标准形线性规划问题的纯整数规划问题(ILP)：njjjxcz1max),,2,1(0),,2,1(1njxmibxajijnjij且均为整数假设约束条件中aij(i＝1,2,…,m；j＝1,2，…,n)和bi(i＝1,2,…,m)均为整数(若不为整数，可令等式两边同乘一个倍数化为整数)。下面先通过一个例子来说明割平面法的基本思想。【例5-5】21maxxxz102321xx522x均取整数0,21xx将该问题图示如下图：从图(a)中可以看出，松弛问题的最优解为X*=(5/3，5/2)T，它不是一个整数解。因此我们设法给原线性规划问题增加一个约束条件，从而把包括X*在内的一部分不含整数点的可行域从原可行域中分割出去。再求增加了这个约束条件后的新的线性规划问题的最优解。从图5-1(b)中可以看出，当我们增加了约束条件“6221xx”后，得到新的最优解X*=(2，2)T，它便是整数规划问题最优解。因此，割平面法的关键就在于如何寻找这类新的约束条件。二、Gomory约束假设用单纯形法求得的线性规划问题最优解不是整数解，其中必然有某个或某几个基变量不为整数。记B为松弛问题的最优基，则问题的基最优解为：01NBXbbBX，不妨设第r个分量不为整数，根据最优单纯形表可得：rbrjNjrjBrbxax(5.1)rjaib将和分成整数部分和非负真分数之和，即：10'iiifbN的整数部分，为10rjrjrjfaN的整数部分，为代入上式得：rjrjrjfNa(5.2)rrrfNb(5.3)NjjrjNjrrjrjBrxffNxNx(5.4)移项，得：jNjrjrrjNjrjBrxffNxNx(5.5)因为变量必须取整数，即上式左边必须是整数，从上式右边看，因为0fi1，所以不能为正，即：割平面方程0jNjrjrxff(5.6)即:rjNjrjfxf(5.7)割平面的两个性质：(1)割平面(5.7)式割去了(ILP)的松弛问题(LP)的基最优解。(2)割平面(5.7)式未割去原问题(ILP)的任一(整数)可行解。三、割平面法的算法步骤步骤1：将约束条件系数及右端项化为整数，用单纯形法求解整数规划问题(ILP)的松弛问题(LP)。设得到最优基B，相应的基最优解为X*。步骤2：判别X*的所有分量是否全为整数？如是，则X*即为(ILP)的最优解，算法终止；若否，则取X*中分数最大的分量，引入割平面(5.7)。*Brx步骤3：将式(5.7)引入松弛变量后加入原最终单纯形表，用对偶单纯形法继续求解。转步骤2。【例5-6】用割平面法求解例5-5。首先，将整数约束去掉，将松弛问题化为标准形，并用单纯形法求解，结果见下表:21maxxxz102321xx522x均取整数0,21xx-1/6-1/300σj-1/31/21/3001105/35/2x1x211x4x3x2x1bxBcB0011cj因基变量x1＝5/3，x2＝5/2，均为非整数，故该最优解不是整数规划的可行解。若以变量x1所在的行为源行，得到相应的割平面为：32323143xx(5.8)对式(5.8)左端加入松弛变量，得到：323231543xxx(5.9)将式(5.9)加入上表中，用对偶单纯形法继续求解如下表：因基变量x1＝5/3，x2＝5/2，均为非整数，故该最优解不是整数规划的可行解。若以分数部分最大的变量x1所在的行为源行，得到相应的割平面为：-1/40-1/400σj-1/23/4-3/20011/2-1/41/2010100221x1x2x41100-1/6-1/300σj001-1/31/21/30-1/30101005/35/2-2/3x1x2x5110x5x4x3x2x1bxBcB00011cj-2/3由上表可知，增加约束条件后的线性规划问题最优解为X*=(2，2，0，1，0)T，因此，原整数规划问题的最优解为X*=(2，2)T，其最优值z*=4。43xx、21xx、如果将式(5.8)中的变量用原问题的决策变量来表示，就得到：322532231031221）（）（xxx整理后得到：6221xx例：用割平面法求解数规划问题且为整数0,205462max21212121xxxxxxxxZCj1100CBXBbx1x2x3x40x3621100x42045011100CBXBbx1x2x3x41x15/3105/6－1/61x28/301－2/31/300－1/6－1/6初始表最终表在松弛问题最优解中，x1,x2均为非整数解，由上表有：383132356165432431xxxxxx将系数和常数都分解成整数和非负真分数之和:32231)311(321)651(65432431xxxxxx以上式子只须考虑一个即可，解题经验表明，考虑