《第4章整数规划》由会员分享，可在线阅读，更多相关《第4章整数规划（77页珍藏版）》请在金锄头文库上搜索。
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、根)下料方式 设设 分别表示采用第分别表示采用第1 1、2 2、3 3种下料方式所切割的圆种下料方式所切割的圆钢毛坯数目。则废料可表示为下列形式：钢毛坯数目。则废料可表示为下列形式：看约束条件。首先，工地需要的是成套钢筋，故看约束条件。首先，工地需要的是成套钢筋，故7 7米长和米长和2 2米米长的钢筋数之比应满足长的钢筋数之比应满足2 2：7 7，用线性方程来表示，即：，用线性方程来表示，即：整理得：整理得：另外，圆钢毛坯总数为另外，圆钢毛坯总数为150150根，故根，故 还应满足下面这个还应满足下面这个条件，即：条件，即：综合分析，问题的数学模型为：综合分析，问题的数学模型为：【例例5-25
5、-2】现有资金总额为现有资金总额为B B，可供投资项目有，可供投资项目有n n个，项目个，项目j j所需所需投资额和预期收益分别为投资额和预期收益分别为a aj j和和c cj j(j(j1,21,2，n)n)。同时，由于。同时，由于种种原因，有三个附加条件：第一，若选择项目种种原因，有三个附加条件：第一，若选择项目1 1，就必须同时，就必须同时选择项目选择项目2 2，反之则不一定；第二，项目，反之则不一定；第二，项目3 3和项目和项目4 4中至少选择一中至少选择一个；第三，项目个；第三，项目5 5、项目、项目6 6和项目和项目7 7中恰好选择两个。应当怎样选中恰好选择两个。应当怎样选择投资项
6、目，才能使总预期收益最大？择投资项目，才能使总预期收益最大？解：解：每一个投资项目都有被选择和不被选择两种可能，为此每一个投资项目都有被选择和不被选择两种可能，为此令：令：则问题可表示为：则问题可表示为：【例例5-35-3】工厂工厂A A1 1和和A A2 2生产某种物资，由于该种物资供不应求，生产某种物资，由于该种物资供不应求，故需要再建一家工厂，相应的建厂方案有故需要再建一家工厂，相应的建厂方案有A A3 3和和A A4 4两个。这种物资两个。这种物资的需求地有的需求地有B B1 1、B B2 2、B B3 3、B B4 4四个。各工厂年生产能力、各地年需四个。各工厂年生产能力、各地年需求
7、量、各厂至各需求地的单位物资运费求量、各厂至各需求地的单位物资运费c cijij(j(j=1,2,3,4)=1,2,3,4)见表见表5-25-2。表表5-25-2150300400350需求量(千吨/年)2005254A42002167A36007538A24004392A1生产能力(千吨/年)B4B3B2B1 cij BjAi 工厂工厂A A3 3或或A A4 4开工后，每年的生产费用估计分别为开工后，每年的生产费用估计分别为12001200万元或万元或15001500万元。现要决定应该建设工厂万元。现要决定应该建设工厂A A3 3还是还是A A4 4，才能使今后每年的，才能使今后每年的总费
8、用总费用(即全部物资运费和新工厂生产费用之和即全部物资运费和新工厂生产费用之和)最少。最少。解：解：这是一个物资运输问题，其特点是事先不能确定应该建这是一个物资运输问题，其特点是事先不能确定应该建A A3 3和和A A4 4中的哪一个，因而不知道新厂投产后的实际生产费用。为中的哪一个，因而不知道新厂投产后的实际生产费用。为此，引入此，引入0-10-1变量：变量：设设x xijij为由为由A Ai i运往运往B Bj j的物资数量的物资数量(千吨千吨)，(i i，j j1,2,3,4)1,2,3,4)。则问题的数学模型为：则问题的数学模型为：二、整数规划模型的一般形式及解的特点二、整数规划模型的
9、一般形式及解的特点 整数线性规划数学模型的一般形式为：整数线性规划数学模型的一般形式为：一般来说，整数线性规划可分为以下几种类型：一般来说，整数线性规划可分为以下几种类型：1.1.纯整数线性规划纯整数线性规划(Pure Integer Linear Programming)(Pure Integer Linear Programming)：指全部决策变量都必须取整数值的整数线性规划，也称为全：指全部决策变量都必须取整数值的整数线性规划，也称为全整数规划。整数规划。2.2.混合整数线性规划混合整数线性规划(Mixed Integer Linear(Mixed Integer Linear Pro
10、gramming)Programming)：指决策变量中一部分必须取整数值，而另一部：指决策变量中一部分必须取整数值，而另一部分可以不取整数值的整数线性规划。分可以不取整数值的整数线性规划。3.0-13.0-1整数线性规划整数线性规划(Zero-one Integer Linear(Zero-one Integer Linear Programming)Programming)：指决策变量只能取：指决策变量只能取0 0或或1 1两个值的整数线性规划。两个值的整数线性规划。（三）整数规划与线性规划的关系三）整数规划与线性规划的关系 从数学模型上看整数规划似乎是线从数学模型上看整数规划似乎是线性规
11、划的一种特殊形式，求解只需在线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚（整数）也不一定就是最优解，有时甚至不能保证所得倒的解是整数可行解。至不能保证所得倒的解是整数可行解。举例说明。举例说明。例：设整数规划问题如下例：设整数规划问题如下 首先不考虑整数约束，得到线性规划问题（一般称首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。为松弛问题）。用用 解法求出最优
12、解解法求出最优解x13/2,x2=10/3且有且有Z=29/6x1x233(3/2,10/3)现求整数解（最优解）：现求整数解（最优解）：如用如用“舍入取整法舍入取整法”可得可得到到4个点即个点即(1，3)(2，3)(1，4)(2，4)。显然，它。显然，它们都不可能是整数规划的们都不可能是整数规划的最优解。最优解。按整数规划约束条件，其可行解肯定在线性规划问题按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。是一个有限集，如图所示。图图 因此，可将集合内的整数点一一找出，其最因此，可
13、将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。大目标函数的值为最优解，此法为完全枚举法。如上例：其中如上例：其中（2，2）（）（3，1）点为最点为最大值，大值，Z=4。.若若(LPLP)没有可行解，则没有可行解，则(ILPILP)也没有可行解，停止计算。也没有可行解，停止计算。.若若(LPLP)有最优解，并符合有最优解，并符合(ILPILP)的整数条件，则的整数条件，则(LPLP)的的最优解即为最优解即为(IPIP)的最优解，停止计算。的最优解，停止计算。.若若(LPLP)有最优解，但不符合有最优解，但不符合(ILPILP)的整数条件，可用相应的整数条件，可用相应方法
14、求解。方法求解。整数规划与其松驰问题解的关系：整数规划与其松驰问题解的关系：目前，常用的求解整数规划的方法有：目前，常用的求解整数规划的方法有：分支定界法和割平面法；分支定界法和割平面法；对于特别的对于特别的0 01 1规划问题采用隐枚举法和匈规划问题采用隐枚举法和匈牙利法。牙利法。第二节第二节 割平面法割平面法 割平面法由高莫累割平面法由高莫累(GomoryGomory)于于19581958年提出。其年提出。其基本思想基本思想是放是放宽变量的整数约束，首先求对应的松弛问题最优解，当某个变宽变量的整数约束，首先求对应的松弛问题最优解，当某个变量量x xi i不满足整数约束时，寻找一个约束方程并
15、添加到松弛问题不满足整数约束时，寻找一个约束方程并添加到松弛问题中，其作用是割掉非整数部分，缩小原松弛问题的可行域，最中，其作用是割掉非整数部分，缩小原松弛问题的可行域，最后逼近整数问题的最优解。后逼近整数问题的最优解。一、割平面法的基本思想一、割平面法的基本思想 考虑松弛问题为标准形线性规划问题的纯整数规划问题考虑松弛问题为标准形线性规划问题的纯整数规划问题(ILP)(ILP)：假设约束条件中假设约束条件中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)均为整数均为整数(若不为整数，可令等式两边同乘一个倍数若不为整数
16、，可令等式两边同乘一个倍数化为整数化为整数)。下面先通过一个例子来说明割平面法的基本思想。下面先通过一个例子来说明割平面法的基本思想。【例例5-55-5】将该问题图示如下图将该问题图示如下图 ：从图从图(a)(a)中可以看出，松弛问题中可以看出，松弛问题的最优解为的最优解为X X*=(5/3=(5/3，5/2)5/2)T T，它不，它不是一个整数解。因此我们设法给原是一个整数解。因此我们设法给原线性规划问题增加一个约束条件，线性规划问题增加一个约束条件，从而把包括从而把包括X X*在内的一部分不含整在内的一部分不含整数点的可行域从原可行域中分割出数点的可行域从原可行域中分割出去。再求增加了这个约束条件后的去。再求增加了这个约束条件后的新的线性规划问题的最优解。新的线性规划问题的最优解。从图从图5-1(b)5-1(b)中可以看出，当我们增加了约束条件中可以看出，当我们增加了约束条件“”后，得到新的最优解后，得到新的最优解X X*=(2=(2，2)2)T T，它便是整数规划问题最优，它便是整数规划问题最优解。因此，割平面法的关键就在于如何寻找这类新的约束条件。解。因此，割平面法的关键就在于
