第4章：整数规划ppt课件.ppt

《第4章：整数规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

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

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

6、neIntegerLinearProgramming)：指决策变量只能取0或1两个值的整数线性规划。（三）整数规划与线性规划的关系从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得倒的解是整数可行解。举例说明。例：设整数规划问题如下首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。用解法求出最优解x1＝3/2,x2=10/3且有Z=29/6x1x2⑴⑵33(3/2,10/3)现求整数解（最优解）：如用“舍入取整

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