整数规划规划论.ppt

《整数规划规划论.ppt》由会员分享，可在线阅读，更多相关《整数规划规划论.ppt（89页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、整 数 规 划(Integer Programming)整数规划的模型分支定界法割平面法01 整数规划指派问题（一）、整数规划问题实例 例一、合理下料问题设用某型号的圆钢下零件A1,A2,Am 的毛坯。在一根圆钢上下料的方式有B1,B2,Bn 种，每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量，如表所示。问怎样安排下料方式，使得即满足需要，所用的原材料又最少？零件 方 个数 式零件零 件毛坯数一、整数规划的模型 设：xj 表示用Bj(j=1.2n)种方式下料根数 模型：例二、某公司计划在m个地点建厂，可供选择的地点有A1,A2Am，他们的生产能力分别是a1,a2,am（假设生产同一产

2、品）。第i个工厂的建设费用为fi(i=1.2m),又有n个地点B1,B2,Bn 需要销售这种产品，其销量分别为b1.b2bn。从工厂运往销地的单位运费为Cij。试决定应在哪些地方建厂，即满足各地需要，又使总建设费用和总运输费用最省？单 销地厂址 价生产能力建设费用销量 设：xij 表示从工厂运往销地的运量(i=1.2m、j=1.2n),1 在Ai建厂 又设 Yi（i=1.2m）0 不在Ai建厂 模型：（二）、整数规划的数学模型一般形式 依照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、混合整数规划、01整数规划。纯整数规划：所有决策变量要求取非负整数（这时引进的松弛变量和剩余变

3、量可以不要求取整数）。全整数规划：除了所有决策变量要求取非负整数外，系数aij和常数bi也要求取整数（这时引进的松弛变量和剩余变量也必须是 整数）。混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。01整数规划：所有决策变量只能取 0 或 1 两个整数。（三）、整数规划与线性规划的关系 从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得倒的解是整数可行解。举例说明。例：设整数规划问题如下 首先不考虑整数约束，得

4、到线性规划问题（一般称为松弛问题）。用 解法求出最优解x13/2,x2=10/3且有Z=29/6x1x233(3/2,10/3)现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3)(2，3)(1，4)(2，4)。显然，它们都不可能是整数规划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。图 因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。如上例：其中（2，2）（3，1）点为最大值，Z=4。目前，常用的求解整数规划的方法有：分支定界法和割平面法；对于特别的01规划问题采用隐枚

5、举法和匈牙利法。（一）、基本思路 考虑纯整数问题：整数问题的松弛问题：二、分枝定界法 1、先不考虑整数约束，解(IP)的松弛问题(LP)，可能得到以下情况之一：.若(LP)没有可行解，则(IP)也没有可行解，停止计算。.若(LP)有最优解，并符合(IP)的整数条件，则(LP)的最优解即为(IP)的最优解，停止计算。.若(LP)有最优解，但不符合(IP)的整数条件，转入下一步。为讨论方便，设(LP)的最优解为：2、定界：记(IP)的目标函数最优值为Z*,以Z(0)作为Z*的上界，记为 Z(0)。再用观察法找的一个整数可行解 X，并以其相应的目标函数值 Z作为Z*的下界，记为Z Z，也可以令Z，则

6、有：Z Z*3、分枝：在(LP)的最优解 X(0)中，任选一个不符合整数条件的变量，例如xr=（不为整数），以 表示不超过 的最大整数。构造两个约束条件 xr 和xr 1如此反复进行，直到得到Z Z*为止，即得最优解 X*。将这两个约束条件分别加入问题(IP)，形成两个子问题(IP1)和(IP2)，再解这两个问题的松弛问题(LP1)和(LP2)。4、修改上、下界：按照以下两点规则进行。.在各分枝问题中，找出目标函数值最大者作为新的上界；.从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。5、比较与剪枝：各分枝的目标函数值中，若有小于Z 者，则剪掉此枝，表明此子问题已经探清，不必再分枝

7、了;否则继续分枝。例一：用分枝定界法求解整数规划问题（用图解法计算）记为（IP）解：首先去掉整数约束，变成一般线性规划问题记为（LP）（二）、例题用图解法求（LP）的最优解，如图所示。x1x233(18/11,40/11)对于x118/111.64，取值x1 1，x1 2对于x2=40/11 3.64，取值x2 3，x2 4先将（LP）划分为（LP1）和（LP2）,取x1 1,x1 2 x118/11,x2=40/11 Z(0)=218/11(19.8)即Z 也是（IP）最小值的下限。有下式：现在只要求出（LP1）和（LP2）的最优解即可。x1x233(18/11,40/11)先求（LP1）,

8、如图所示。此时在B点取得最优解。x11,x2=3,Z(1)16找到整数解，问题已探明，此枝停止计算。11同理求（LP2）,如图所示。在C 点取得最优解。即x12,x2=10/3,Z(2)56/318.7 Z2 Z116 原问题有比（16）更小的最优解，但 x2 不是整数，故利用 3 10/34 加入条件。BAC加入条件：x23,x24 有下式：只要求出（LP3）和（LP4）的最优解即可。x1x233(18/11,40/11)11BAC先求（LP3）,如图所示。此时D 在点取得最优解。即 x112/52.4,x2=3,Z(3)-87/5-17.4Z-19.8但x112/5不是整数，可继续分枝。即

9、 3x12。D求（LP4），如图所示。无可行解，不再分枝。在（LP3）的基础上继续分枝。加入条件3x12有下式：只要求出（LP5）和（LP6）的最优解即可。x1x233(18/11,40/11)11BACD先求（LP5）,如图所示。此时E 在点取得最优解。即 x12,x2=3,Z(5)17找到整数解，问题已探明，此枝停止计算。E求（LP6），如图所示。此时 F在点取得最优解。x13,x2=2.5,Z(6)31/215.5 Z(5)F 如对 Z(6)继续分解，其最小值也不会低于15.5，问题探明,剪枝。至此，原问题（IP）的最优解为：x1=2，x2=3,Z*=Z(5)17以上的求解过程可以用一个

10、树形图表示如右：LP1x1=1,x2=3Z(1)16LPx1=18/11,x2=40/11Z(0)19.8LP2x1=2,x2=10/3Z(2)18.5LP3x1=12/5,x2=3Z(3)17.4LP4无可行解LP5x1=2,x2=3Z(5)17LP6x1=3,x2=5/2Z(6)15.5x11 x12x23 x24x12x13 练习：用分枝定界法求解整数规划问题（图解法）LP1x1=1,x2=7/3Z(1)10/3LPx1=3/2,x2=10/3Z(0)29/6LP2x1=2,x2=23/9Z(2)41/9x11x12LP5x1=1,x2=2Z(5)3LP6无可行解 x22x23LP3x1=33/14,x2=2Z(3)61/14LP4无可行解x22 x23LP7x1=2,x2=2Z(7)4LP8x1=3,x2=1Z(8)4x12x13 01 整数规划是一种特殊形式的整数规划，这时的决策变量xi 只取两个值0或1，一般的解法为隐枚举法。例一、求解下列01 规划问题四、01 整数规划