第4章整数规划.ppt

1、第五章第五章 整数规划整数规划(Integer Programming)整数规划的基本问题及其数学模型整数规划的基本问题及其数学模型割平面法割平面法分支定界法分支定界法0-10-1整数规划整数规划指派问题指派问题WinQSBWinQSB软件应用软件应用第一节第一节 整数规划的基本问题整数规划的基本问题及其数学模型及其数学模型一、问题的提出一、问题的提出 实际工作中的某些规划问题要求部分变量或全部变量取整实际工作中的某些规划问题要求部分变量或全部变量取整数值，我们称这样的问题为整数规划问题数值，我们称这样的问题为整数规划问题(Integer(Integer ProgrammingProgramm

2、ing，IP)IP)。不考虑整数要求，由其他约束条件和目标不考虑整数要求，由其他约束条件和目标函数构成的规划问题称为该整数规划问题的函数构成的规划问题称为该整数规划问题的松弛问题松弛问题(Slack(Slack Problem)Problem)。若松弛问题是一个线性规划问题，我们称该整数规。若松弛问题是一个线性规划问题，我们称该整数规划问题为整数线性规划划问题为整数线性规划(Integer Linear Programming(Integer Linear ProgrammingILP)ILP)。【例【例5-15-1】某工地需要长度不同、直径相同的成套钢筋，每】某工地需要长度不同、直径相同的成

3、套钢筋，每套钢筋由两根套钢筋由两根7 7米长和七根米长和七根2 2米长的钢筋组成。现有长米长的钢筋组成。现有长1515米的圆米的圆钢毛坯钢毛坯150150根，应如何下料，使废料最少？根，应如何下料，使废料最少？解：解：本题中没有说明本题中没有说明1515米长的圆钢毛坯有哪些下料方式，米长的圆钢毛坯有哪些下料方式，故需要首先找出下料方式。将故需要首先找出下料方式。将1515米长的圆钢毛坯切割为米长的圆钢毛坯切割为7 7米和米和2 2米两种长度的钢筋有三种方式，如表米两种长度的钢筋有三种方式，如表5-15-1所示。所示。表表5-15-1170304121021废料(米)2米长的钢筋(根)7米长的钢

4、筋(根)下料方式321xxx、设设 分别表示采用第分别表示采用第1 1、2 2、3 3种下料方式所切割的种下料方式所切割的圆钢毛坯数目。则废料可表示为下列形式：圆钢毛坯数目。则废料可表示为下列形式：31xxz 看约束条件。首先，工地需要的是成套钢筋，故看约束条件。首先，工地需要的是成套钢筋，故7 7米长和米长和2 2米米长的钢筋数之比应满足长的钢筋数之比应满足2 2：7 7，用线性方程来表示，即：，用线性方程来表示，即：774223221xxxx整理得：整理得：01414321xxx另外，圆钢毛坯总数为另外，圆钢毛坯总数为150150根，故根，故 还应满足下面这个还应满足下面这个条件，即：条件

5、，即：321xxx、150321xxx综合分析，问题的数学模型为：综合分析，问题的数学模型为：31minxxz且均取整数值0,15001414321321321xxxxxxxxx 【例【例5-25-2】现有资金总额为】现有资金总额为B B，可供投资项目有，可供投资项目有n n个，项目个，项目j j所需所需投资额和预期收益分别为投资额和预期收益分别为a aj j和和c cj j(j(j1,21,2，n)n)。同时，由于。同时，由于种种原因，有三个附加条件：第一，若选择项目种种原因，有三个附加条件：第一，若选择项目1 1，就必须同时，就必须同时选择项目选择项目2 2，反之则不一定；第二，项目，反之

6、则不一定；第二，项目3 3和项目和项目4 4中至少选择一中至少选择一个；第三，项目个；第三，项目5 5、项目、项目6 6和项目和项目7 7中恰好选择两个。应当怎样选中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？择投资项目，才能使总预期收益最大？解：解：每一个投资项目都有被选择和不被选择两种可能，为此每一个投资项目都有被选择和不被选择两种可能，为此令：令：），（不投资对项目投资对项目njjjxj2101n,1,2,j10210max765432111或jjnjjnjjjxxxxxxxxBxaxcz则问题可表示为：则问题可表示为：【例【例5-35-3】工厂】工厂A A1 1和和A A

7、2 2生产某种物资，由于该种物资供不应生产某种物资，由于该种物资供不应求，故需要再建一家工厂，相应的建厂方案有求，故需要再建一家工厂，相应的建厂方案有A A3 3和和A A4 4两个。这两个。这种物资的需求地有种物资的需求地有B B1 1、B B2 2、B B3 3、B B4 4四个。各工厂年生产能力、各四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费地年需求量、各厂至各需求地的单位物资运费c cijij(j(j=1,2,3,4)=1,2,3,4)见表见表5-25-2。表表5-25-2150300400350需求量(千吨/年)2005254A42002167A36007538

8、A24004392A1生产能力(千吨/年)B4B3B2B1 cij BjAi 工厂工厂A A3 3或或A A4 4开工后，每年的生产费用估计分别为开工后，每年的生产费用估计分别为12001200万元或万元或15001500万元。现要决定应该建设工厂万元。现要决定应该建设工厂A A3 3还是还是A A4 4，才能使今后每年，才能使今后每年的总费用的总费用(即全部物资运费和新工厂生产费用之和即全部物资运费和新工厂生产费用之和)最少。最少。解：解：这是一个物资运输问题，其特点是事先不能确定应该建这是一个物资运输问题，其特点是事先不能确定应该建A A3 3和和A A4 4中的哪一个，因而不知道新厂投产

9、后的实际生产费用。中的哪一个，因而不知道新厂投产后的实际生产费用。为此，引入为此，引入0-10-1变量：变量：4301AAy若建工厂若建工厂 设设x xijij为由为由A Ai i运往运往B Bj j的物资数量的物资数量(千吨千吨)，(i i，j j1,2,3,4)1,2,3,4)。则问题的数学模型为：则问题的数学模型为：115001200min4141yyxczijijij35041312111xxxx40042322212xxxx30043332313xxxx15044342414xxxx40014131211xxxx60024232221xxxxyxxxx20034333231yxxxx

10、120044434241)4,3,2,1,(0jixij10或y二、整数规划模型的一般形式及解的特点二、整数规划模型的一般形式及解的特点 整数线性规划数学模型的一般形式为：整数线性规划数学模型的一般形式为：njjjxcz1min)(max 或部分或全部取整数、njijnjijxxxnjxmibxa,),2,1(0),2,1()(211一般来说，整数线性规划可分为以下几种类型：一般来说，整数线性规划可分为以下几种类型：1.1.纯整数线性规划纯整数线性规划(Pure Integer Linear Programming)(Pure Integer Linear Programming)：指全部决策

11、变量都必须取整数值的整数线性规划，也称为全整指全部决策变量都必须取整数值的整数线性规划，也称为全整数规划。数规划。2.2.混合整数线性规划混合整数线性规划(Mixed Integer Linear(Mixed Integer Linear Programming)Programming)：指决策变量中一部分必须取整数值，而另一部：指决策变量中一部分必须取整数值，而另一部分可以不取整数值的整数线性规划。分可以不取整数值的整数线性规划。3.0-1 3.0-1整数线性规划整数线性规划(Zero-one Integer Linear(Zero-one Integer Linear Programmin

12、g)Programming)：指决策变量只能取：指决策变量只能取0 0或或1 1两个值的整数线性规划。两个值的整数线性规划。（三）整数规划与线性规划的关系（三）整数规划与线性规划的关系 从数学模型上看整数规划似乎是线从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚（整数）也不一定就是最优解，有时甚至不能保证所得倒的

13、解是整数可行解。至不能保证所得倒的解是整数可行解。举例说明。举例说明。例：设整数规划问题如下例：设整数规划问题如下 且为整数0,13651914max21212121xxxxxxxxZ 首先不考虑整数约束，得到线性规划问题（一般称首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。为松弛问题）。0,13651914max21212121xxxxxxxxZ用用 解法求出最优解解法求出最优解x13/2,x2=10/3且有且有Z=29/6x1x233(3/2,10/3)现求整数解（最优解）：现求整数解（最优解）：如用如用“舍入取整法舍入取整法”可可得到得到4个点即个点即(1，3)(2，3)(1

14、，4)(2，4)。显然，。显然，它们都不可能是整数规它们都不可能是整数规划的最优解。划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。是一个有限集，如图所示。图图 因此，可将集合内的整数点一一找出，其最因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。大目标函数的值为最优解，此法为完全枚举法。如上例：其中如上例：其中（2，2）（）（3，1）点为最点为最大值，大值，Z=4。.若若(LPLP)没有可行

15、解，则没有可行解，则(ILPILP)也没有可行解，停止计算。也没有可行解，停止计算。.若若(LPLP)有最优解，并符合有最优解，并符合(ILPILP)的整数条件，则的整数条件，则(LPLP)的最优解即为的最优解即为(IPIP)的最优解，停止计算。的最优解，停止计算。.若若(LPLP)有最优解，但不符合有最优解，但不符合(ILPILP)的整数条件，可用相的整数条件，可用相应方法求解。应方法求解。整数规划与其松驰问题解的关系：整数规划与其松驰问题解的关系：目前，常用的求解整数规划的方法有：目前，常用的求解整数规划的方法有：分支定界法和割平面法；分支定界法和割平面法；对于特别的对于特别的0 01 1

16、规划问题采用隐枚举法和匈规划问题采用隐枚举法和匈牙利法。牙利法。第二节第二节 割平面法割平面法 割平面法由高莫累割平面法由高莫累(Gomory(Gomory)于于19581958年提出。其年提出。其基本思想基本思想是是放宽变量的整数约束，首先求对应的松弛问题最优解，当某个放宽变量的整数约束，首先求对应的松弛问题最优解，当某个变量变量x xi i不满足整数约束时，寻找一个约束方程并添加到松弛问不满足整数约束时，寻找一个约束方程并添加到松弛问题中，其作用是割掉非整数部分，缩小原松弛问题的可行域，题中，其作用是割掉非整数部分，缩小原松弛问题的可行域，最后逼近整数问题的最优解。最后逼近整数问题的最优解

17、。一、割平面法的基本思想一、割平面法的基本思想 考虑松弛问题为标准形线性规划问题的纯整数规划问题考虑松弛问题为标准形线性规划问题的纯整数规划问题(ILP)(ILP)：njjjxcz1max),2,1(0),2,1(1njxmibxajijnjij且均为整数 假设约束条件中假设约束条件中a aijij(i i1,2,1,2,m m；j j1,21,2，,n n)和和b bi i(i i1,2,1,2,m m)均为整数均为整数(若不为整数，可令等式两边同乘一个倍数若不为整数，可令等式两边同乘一个倍数化为整数化为整数)。下面先通过一个例子来说明割平面法的基本思想。下面先通过一个例子来说明割平面法的基

18、本思想。【例【例5-55-5】21maxxxz102321 xx522x均取整数0,21xx将该问题图示如下图将该问题图示如下图 ：从图从图(a)(a)中可以看出，松弛问中可以看出，松弛问题的最优解为题的最优解为X X*=(5/3=(5/3，5/2)5/2)T T，它，它不是一个整数解。因此我们设法不是一个整数解。因此我们设法给原线性规划问题增加一个约束给原线性规划问题增加一个约束条件，从而把包括条件，从而把包括X X*在内的一部分在内的一部分不含整数点的可行域从原可行域不含整数点的可行域从原可行域中分割出去。再求增加了这个约中分割出去。再求增加了这个约束条件后的新的线性规划问题的束条件后的新

19、的线性规划问题的最优解。最优解。从图从图5-1(b)5-1(b)中可以看出，当我们增加了约束条件中可以看出，当我们增加了约束条件“6221 xx”后，得到新的最优解后，得到新的最优解X X*=(2=(2，2)2)T T，它便是整数规划问题最优，它便是整数规划问题最优解。因此，割平面法的关键就在于如何寻找这类新的约束条件。解。因此，割平面法的关键就在于如何寻找这类新的约束条件。二、二、GomoryGomory约束约束 假设用单纯形法求得的线性规划问题最优解不是整数解，其假设用单纯形法求得的线性规划问题最优解不是整数解，其中必然有某个或某几个基变量不为整数。记中必然有某个或某几个基变量不为整数。记

20、B B为松弛问题的最优为松弛问题的最优基，则问题的基最优解为：基，则问题的基最优解为：01NBXbbBX，不妨设第不妨设第r r个分量个分量 不为整数，根据最优单纯形表可得：不为整数，根据最优单纯形表可得：rbrjNjrjBrbxax(5.1)rjaib将将 和和 分成整数部分和非负真分数之和，即：分成整数部分和非负真分数之和，即：10iiifbN的整数部分，为10rjrjrjfaN的整数部分，为代入上式得：代入上式得：rjrjrjfNa(5.2)rrrfNb(5.3)NjjrjNjrrjrjBrxffNxNx(5.4)移项，得：移项，得：jNjrjrrjNjrjBrxffNxNx(5.5)因

21、为变量必须取整数，即上式左边必须是整数，从上式右边因为变量必须取整数，即上式左边必须是整数，从上式右边看，因为看，因为0f0fi i11，所以不能为正，即：，所以不能为正，即：割平面方程割平面方程0jNjrjrxff(5.6)即即:rjNjrjfxf(5.7)割平面的两个性质：割平面的两个性质：(1)(1)割平面割平面(5.7)(5.7)式割去了式割去了(ILP)(ILP)的松弛问题的松弛问题(LP)(LP)的基最优解。的基最优解。(2)(2)割平面割平面(5.7)(5.7)式未割去原问题式未割去原问题(ILP)(ILP)的任一的任一(整数整数)可行解。可行解。三、割平面法的算法步骤三、割平面

22、法的算法步骤 步骤步骤1 1：将约束条件系数及右端项化为整数，用单纯形法求将约束条件系数及右端项化为整数，用单纯形法求解整数规划问题解整数规划问题(ILP)(ILP)的松弛问题的松弛问题(LP)(LP)。设得到最优基。设得到最优基B B，相应，相应的基最优解为的基最优解为X X*。步骤步骤2 2：判别判别X X*的所有分量是否全为整数？如是，则的所有分量是否全为整数？如是，则X X*即为即为(ILP)(ILP)的最优解，算法终止；若否，则取的最优解，算法终止；若否，则取X X*中分数最大的分中分数最大的分量量 ，引入割平面，引入割平面(5.7)(5.7)。*Brx 步骤步骤3 3：将式将式(5

23、.7)(5.7)引入松弛变量后加入原最终单纯形表，用对引入松弛变量后加入原最终单纯形表，用对偶单纯形法继续求解。转步骤偶单纯形法继续求解。转步骤2 2。【例【例5-65-6】用割平面法求解例】用割平面法求解例5-55-5。首先，将整数约束去掉，将松弛问题化为标准形，并用单首先，将整数约束去掉，将松弛问题化为标准形，并用单纯形法求解，结果见下表纯形法求解，结果见下表:21maxxxz102321 xx522x均取整数0,21xx-1/6-1/300j-1/31/21/3001105/35/2x1x211x4x3x2x1bxBcB0011cj 因基变量因基变量x x1 15/35/3，x x2 2

24、5/25/2，均为非整数，故该最优解不是整数规划的，均为非整数，故该最优解不是整数规划的可行解。若以变量可行解。若以变量x x1 1所在的行为源行，得到相应的割平面为：所在的行为源行，得到相应的割平面为：32323143xx(5.8)对式对式(5.8)(5.8)左端加入松弛变量，得到：左端加入松弛变量，得到：323231543xxx(5.9)将式将式(5.9)(5.9)加入上表中，用对偶单纯形法继续求解如下表：加入上表中，用对偶单纯形法继续求解如下表：因基变量因基变量x x1 15/35/3，x x2 25/25/2，均为非整数，故该最优解不是，均为非整数，故该最优解不是整数规划的可行解。若以

25、分数部分最大的变量整数规划的可行解。若以分数部分最大的变量x x1 1所在的行为源所在的行为源行，得到相应的割平面为：行，得到相应的割平面为：-1/40-1/400j-1/23/4-3/20011/2-1/41/2010100221x1x2x41100-1/6-1/300j001-1/31/21/30-1/30101005/35/2-2/3x1x2x5110 x5x4x3x2x1bxBcB00011cj-2/3 由上表可知，增加约束条件后的线性规划问题最优解为由上表可知，增加约束条件后的线性规划问题最优解为X X*=(2=(2，2 2，0 0，1 1，0)0)T T，因此，原整数规划问题的最优

26、解为，因此，原整数规划问题的最优解为X X*=(2=(2，2)2)T T，其最优值，其最优值z z*=4=4。43xx、21xx、如果将式如果将式(5.8)(5.8)中的变量中的变量 用原问题的决策变量用原问题的决策变量 来表示，就得到：来表示，就得到：322532231031221）（）（xxx整理后得到：整理后得到：6221 xx例：用割平面法求解数规划问题例：用割平面法求解数规划问题 且且为为整整数数0,205462max21212121xxxxxxxxZCj1100CBXBbx1x2x3x40 x3621100 x42045011100CBXBbx1x2x3x41 x15/3105/6

27、1/61x28/3012/31/3001/61/6初初始始表表最最终终表表在松弛问题最优解中，在松弛问题最优解中，x1,x2 均为非整数解，由上表有：均为非整数解，由上表有：383132356165432431 xxxxxx将系数和常数都分解成整数和非负真分数之和将系数和常数都分解成整数和非负真分数之和:32231)311(321)651(65432431 xxxxxx 以上式子只须考虑一个即可，解题经验表明，考虑式子右端以上式子只须考虑一个即可，解题经验表明，考虑式子右端最大真分数的式子，往往会较快地找到所需割平面约束条件。最大真分数的式子，往往会较快地找到所需割平面约束条件。以上两个式子右

28、端真分数相等，可任选一个考虑。现选第二个以上两个式子右端真分数相等，可任选一个考虑。现选第二个式子，并将真分数移到右边得：式子，并将真分数移到右边得：)(313224332xxxx 32)(3143 xx引入松弛变量引入松弛变量s1 后得到下式，将此约束条件加到上表中，继续后得到下式，将此约束条件加到上表中，继续求解。求解。323131143 sxxCj11000CBXBbx1x2x3x4s11 x15/3105/61/601x28/3012/31/300s12/3001/31/31001/61/60Cj11000CBXBbx1x2x3x4s11 x10100101x24010120 x320

29、011300001/2 得到整数最优解，即为整数规划的最优解，而且此整数规划得到整数最优解，即为整数规划的最优解，而且此整数规划有两个最优解：有两个最优解：X=(0,4),z=4,或 X=(2,2),z=4。第三节第三节 分枝定界法分枝定界法 分枝定界法是在分枝定界法是在2020世纪世纪6060年代初由年代初由Land DoingLand Doing和和DakinDakin等人等人提出的适合于解纯整数或混合正数规划问题。提出的适合于解纯整数或混合正数规划问题。分支定界法实际是一种隐枚举法或部分枚举法，它是在枚举分支定界法实际是一种隐枚举法或部分枚举法，它是在枚举法基础上的改进，在枚举过程中逐批

30、把一部分可行解排斥在考法基础上的改进，在枚举过程中逐批把一部分可行解排斥在考察范围之外，从而大大减少了计算量。分支定界法的关键是分察范围之外，从而大大减少了计算量。分支定界法的关键是分支和定界。支和定界。rrbxrNrbrrNx 1rrNx若松弛问题的最优解不符合整数要求，假设变量若松弛问题的最优解不符合整数要求，假设变量不符合整数要求，不符合整数要求，为不超过为不超过 的最大整数，则在松弛问题中的最大整数，则在松弛问题中分别加入两个约束条件：分别加入两个约束条件：和和 ，以形成两个子问，以形成两个子问题。题。一、分支定界法的基本思想一、分支定界法的基本思想 两个子问题的可行域的并集包含了原问

31、题两个子问题的可行域的并集包含了原问题(ILP)(ILP)的全部可行的全部可行解，而包括原最优解在内的松弛问题的部分非整数解被剔除了。解，而包括原最优解在内的松弛问题的部分非整数解被剔除了。然后分别求解两个子问题，根据需要，各子问题可以再产生自然后分别求解两个子问题，根据需要，各子问题可以再产生自己的子问题。这个过程就是己的子问题。这个过程就是分支分支。在分支过程中，若某个子问题的最优解为整数解，其目标在分支过程中，若某个子问题的最优解为整数解，其目标函数值就是整数规划问题的一个函数值就是整数规划问题的一个“界限界限”，可以此作为判断其，可以此作为判断其他分支优劣的一个依据。若某一子问题最优解

32、他分支优劣的一个依据。若某一子问题最优解(无论是否为整无论是否为整数解数解)的目标函数值小于或等于该界限，则可以将该子问题剔的目标函数值小于或等于该界限，则可以将该子问题剔除而不予考虑了。若有其他子问题的最优解为整数解，则将其除而不予考虑了。若有其他子问题的最优解为整数解，则将其目标函数值与原来的界限相比较，取更优的一个作为新的界限。目标函数值与原来的界限相比较，取更优的一个作为新的界限。这个过程就是这个过程就是定界定界。二、分支定界法的一般步骤二、分支定界法的一般步骤 【例【例5-75-7】用分支定界法求解例】用分支定界法求解例5-55-5。21maxxxz102321 xx522x均取整数

33、0,21xx 解：解：首先求解首先求解(LP)(LP)，得到的最优解为，得到的最优解为x x1 15/35/3，x x2 25/25/2，z z25/625/6。由于由于(LP)(LP)的最优解不是整数解，可任选一个变量进行分支。的最优解不是整数解，可任选一个变量进行分支。若选若选x x1 15/35/3进行分支，则分支出的约束条件为：进行分支，则分支出的约束条件为：11x(5.10)和和 22x(5.10)分别将上述两个约束条件加入分别将上述两个约束条件加入(LP)(LP)中，因此原问题的松弛中，因此原问题的松弛问题问题(LP)(LP)被划分为两个子问题：被划分为两个子问题：211max)(

34、xxzLP102321 xx522x0,21xx11x212max)(xxzLP102321 xx522x0,21xx21x 先求解先求解(LP(LP1 1)，最优解为，最优解为x x1 11 1，x x2 25/25/2，最优值，最优值z z7/27/2，仍，仍不是整数解不是整数解(见图见图5-2)5-2)。再求解再求解(LP(LP2 2)，最优解为，最优解为x x1 12 2，x x2 22 2，z z4(4(见图见图5-3)5-3)。故。故取取z z4 4作为作为(ILP)(ILP)最优值的一个下界。最优值的一个下界。由于由于(LP(LP1 1)的最优值为的最优值为7/27/24 4，故

35、其子问题的目标函数值不，故其子问题的目标函数值不会超过会超过7/27/2，也不会超过，也不会超过4 4。因此。因此(LP(LP1 1)是一个失去希望的问题，是一个失去希望的问题，不必再对它进行分支。若不必再对它进行分支。若(LP(LP1 1)的最优值大于的最优值大于4 4，需要对它进一，需要对它进一步分支。步分支。上述求解过程可用图上述求解过程可用图5-45-4来说明：来说明：分支定界法解整数规划的一般步骤可归结如下：分支定界法解整数规划的一般步骤可归结如下：1*1x2*2x 步骤步骤1 1：取取(ILP)(ILP)的目标函数值的初始下界的目标函数值的初始下界 。用单纯形。用单纯形法求解整数规

36、划问题法求解整数规划问题(ILP)(ILP)的松弛问题的松弛问题(LP)(LP)。z 步骤步骤2 2：若问题若问题(LP)(LP)不可行，则不可行，则(ILP)(ILP)也不可行，算法终止；也不可行，算法终止；若问题若问题(LP)(LP)的最优解的最优解X X*为为(ILP)(ILP)的可行解，则它就是的可行解，则它就是(ILP)(ILP)的最的最优解，算法终止。若问题优解，算法终止。若问题(LP)(LP)的最优解存在，但不满足的最优解存在，但不满足(ILP)(ILP)的的整数要求，转步骤整数要求，转步骤3 3。rrbxrrNx 1rrNx 步骤步骤3 3：任选任选X X*中不满足整数要求的一

37、个变量中不满足整数要求的一个变量 进行分进行分支，即对问题支，即对问题(LP)(LP)分别增加约束条件分别增加约束条件 和和 ，形成，形成两个子问题，并求解。转步骤两个子问题，并求解。转步骤4 4。步骤步骤4 4：考察所有子问题，有以下四种情况：考察所有子问题，有以下四种情况：zz a.a.若某个子问题的最优解也是问题若某个子问题的最优解也是问题(ILP)(ILP)的可行解，则将它的可行解，则将它的目标函数值与的目标函数值与 作比较，并取较优的一个作为新的界限作比较，并取较优的一个作为新的界限 。如所有子问题都已考察完毕，则保留下来的如所有子问题都已考察完毕，则保留下来的 及其对应的解即及其对

38、应的解即为问题为问题(ILP)(ILP)的最优解。的最优解。zz b.b.若某个子问题的最优解不是若某个子问题的最优解不是(ILP)(ILP)的可行解，且其最优的可行解，且其最优值不如值不如 ，则将这一分支删掉。，则将这一分支删掉。c.c.若某个子问题不可行，则将这一分支删掉。若某个子问题不可行，则将这一分支删掉。z d.d.若某个子问题的最优解不是若某个子问题的最优解不是(ILP)(ILP)的可行解，且其最优的可行解，且其最优值优于值优于 ，则该问题为待考察的问题。如有多个问题待考察，则该问题为待考察的问题。如有多个问题待考察，优先对其中最优值最大的一个子问题进行考察，转步骤优先对其中最优值

39、最大的一个子问题进行考察，转步骤3 3。且均取整数数值0,5.45.01432)(23max21212121xxxxxxIPxxz 解：解：用图解法解对应的用图解法解对应的(LP)问题，如表所示，获得最优解。问题，如表所示，获得最优解。【例【例】用分枝定界法求解整数规划问题】用分枝定界法求解整数规划问题x1x2(3.25,2.5)(3.25,2.5)x1=13/4 x2=5/2 Z(0)=59/414.75 选选x x2 2进行分枝，即增加两个约束，进行分枝，即增加两个约束，x x2 2 2 2和和x x2 233，分枝出以，分枝出以下两个问题：下两个问题：且为整数0,2 5.45.0143

40、223max2122121121xxxxxxxIPxxz且为整数0,3 5.45.0143 223max2122121221xxxxxxxIPxxzx1x2(3.5,2(3.5,2)用图解法求对应的用图解法求对应的LPLP1 1和和LPLP2 2问题：问题：接接(IP(IP1 1)继续分枝，加入约束继续分枝，加入约束 x x1 133和和x x1 14 4，分枝出以下两个问题：，分枝出以下两个问题：且为整数0,3 2 5.45.0143 2)3(23max2112212121xxxxxxxxIPxxz且为整数0,4 2 5.45.01432)4(23max2112212121xxxxxxxxI

41、Pxxzx1x2(3,2)(3,2)用图解法求对应的用图解法求对应的LPLP3 3和和LPLP4 4问题：问题：树形图如下：树形图如下：LP1x1=7/2,x2=2Z(1)29/2=14.5LPx1=13/4,x2=5/2Z(0)59/4=14.75LP2x1=5/2,x2=3Z(2)27/2=13.5LP3x1=3,x2=2Z(3)13LP4x1=4,x2=1Z(4)14x22x23x13x14第四节第四节 0 01 1整数规划整数规划一、一、0-10-1变量的应用变量的应用 第一节中我们讨论过第一节中我们讨论过0-10-1变量，即只能取变量，即只能取0 0或或1 1的变量，它是的变量，它是

42、逻辑变量，通常用来表示在是与否之间二选一的问题，如某个逻辑变量，通常用来表示在是与否之间二选一的问题，如某个方案方案A A是否被选中，可用下面的是否被选中，可用下面的0-10-1变量来表示：变量来表示：01x当采取方案A时 当不采取方案A 时【例【例5-85-8】含有相互排斥的约束条件的问题。】含有相互排斥的约束条件的问题。设某厂生产第设某厂生产第j j 种产品的数量为种产品的数量为x xj j(j(j=1=1，2 2，3)3)，其材料可，其材料可在甲或乙中选择一种，当选择甲或乙时，相应的材料消耗的约在甲或乙中选择一种，当选择甲或乙时，相应的材料消耗的约束条件分别为：束条件分别为：和和1806

43、52321xxx(5.12 a)300534321xxx(5.12 a)试问这类相互排斥的约束条件如何体现在模型中？试问这类相互排斥的约束条件如何体现在模型中？解：解：引入引入0-10-1变量：变量：当不选用材料甲时当选用材料甲时101y和和当不选用材料乙时当选用材料乙时102y 因而，两个相互排斥的约束条件可用下列线性约束条件统一因而，两个相互排斥的约束条件可用下列线性约束条件统一起来：起来：)12.5(1)12.5(300534)12.5(1806522123211321eyydMyxxxcMyxxx其中其中M M是一个充分大的数。是一个充分大的数。若若y y1 1=1=1，而，而y y2

44、 2=0=0，即选用材料乙，由，即选用材料乙，由(5.12d)(5.12d)式得：式得：300534321xxx式式(5.12c)(5.12c)自然成立；自然成立；若若y y1 1=0=0，而，而y y2 2=1=1，即选用材料甲，由，即选用材料甲，由(5.12c)(5.12c)式得：式得：式式(5.12d)(5.12d)自然成立自然成立.180652321xxx 【例【例5-95-9】固定费用问题。有一种自然资源被用于生产三种产】固定费用问题。有一种自然资源被用于生产三种产品，资源量、产品单件可变费用及售价、资源单位消耗量及组品，资源量、产品单件可变费用及售价、资源单位消耗量及组织三种产品生

45、产的固定费用见表织三种产品生产的固定费用见表5-55-5。要求制订一个生产计划，。要求制订一个生产计划，使总收益最大。使总收益最大。12108单位售价200150100固定费用654 单位可变费用100321C300432B500842A资源量IIIIII 单耗量资源产品解：解：设设x xj j表示三种产品的产量表示三种产品的产量(j j=1=1，2 2，3)3)。引入引入0-10-1变量：变量：)3,2,1(01jjjyj种产品若不生产第种产品若生产第则问题的数学模型可归结如下：则问题的数学模型可归结如下：321321200150100)612()510()48(maxyyyxxxz5008

46、42321xxx300432321xxx10032321xxx)3,2,1(jyMxjjj)3,2,1(0jxj且为整数)3,2,1(10jyj或 如果生产第如果生产第j j种产品，则其产量种产品，则其产量x xj j0 0，由，由x xj jM Mj jy yj j知，知，y yj j1 1。因此，相应的固定费用在目标函数中将被考虑。因此，相应的固定费用在目标函数中将被考虑。同理，如果不生产第同理，如果不生产第j j种产品，则其产量种产品，则其产量x xj j=0=0，由，由x xj jM Mj jy yj j知，知，y yj j可以取可以取0 0或或1 1。因此，相应的固定费用不应在目标函

47、数中将被。因此，相应的固定费用不应在目标函数中将被考虑。考虑。二、二、0-10-1型整数规划的解法型整数规划的解法 0-1 0-1型规划是一类特殊的整数规划，因为变量只有型规划是一类特殊的整数规划，因为变量只有0 0或或1 1两个两个可能的取值，故最多有可能的取值，故最多有2 2n n个可行解，理论上可以用枚举法进行个可行解，理论上可以用枚举法进行求解。但当求解。但当n n较大时，采用完全枚举法求解几乎是不可能的。较大时，采用完全枚举法求解几乎是不可能的。隐枚举法是求解隐枚举法是求解0-10-1整数规划问题的一种比较简便的方法。整数规划问题的一种比较简便的方法。其实质也是一种分支定界法。其实质

48、也是一种分支定界法。隐枚举法是是在隐枚举法是是在2 2n n个可能的变量组合中，只有一部分是可行个可能的变量组合中，只有一部分是可行解。只要发现某个变量组合不满足其中一个约束条件，就不必解。只要发现某个变量组合不满足其中一个约束条件，就不必再检验是否满足其它约束。如所有约束条件都满足，就是再检验是否满足其它约束。如所有约束条件都满足，就是0-10-1规规划的一个可行解，可根据相应的目标函数值产生一个过滤条件，划的一个可行解，可根据相应的目标函数值产生一个过滤条件，对于目标函数值劣于该可行解的变量组合不必再去检验其可行对于目标函数值劣于该可行解的变量组合不必再去检验其可行性。在以后的求解过程中，

49、如发现某个可行解比原来保留的可性。在以后的求解过程中，如发现某个可行解比原来保留的可行解更优，则用它替换原来的过滤条件。行解更优，则用它替换原来的过滤条件。【例【例5-115-11】求解】求解0-10-1整数规划整数规划 10,6434422523max3213221321321321或xxxxxxxxxxxxxxxxz(5.13a)(5.13b)(5.13c)(5.13d)解：解：求解过程可以用表求解过程可以用表5-75-7表示。表示。(1(1，1 1，1)1)(1(1，1 1，0)0)(1(1，0 0，1)1)(1(1，0 0，0)0)(0(0，1 1，1)1)(0(0，1 1，0)0)(

50、0(0，0 0，1)1)(0(0，0 0，0)0)d dc cb ba a过滤条件过滤条件约束条件约束条件z z值值(x x1 1，x x2 2，x x3 3)0 0z z 0 05 5z z 5 5-2-23 33 38 8z z 8 81 16 6所以，最优解所以，最优解(x x1 1，x x2 2，x x3 3)T T=(1=(1，0 0，1)1)T T，max max z z=8=8。为了使最优解尽可能早出现，可先将目标函数中各变量的为了使最优解尽可能早出现，可先将目标函数中各变量的顺序按其系数大小重新排列，这样可进一步减少计算量。例顺序按其系数大小重新排列，这样可进一步减少计算量。例