整数规划与matlab吴颖丹.ppt

《整数规划与matlab吴颖丹.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学建模培训整数规划专题吴颖丹整数规划整数规划的模型分支定界法割平面法0－1整数规划指派问题例一、合理下料问题设用某型号的圆钢下零件A1,A2,…,Am的毛坯。在一根圆钢上下料的方式有B1,B2,…Bn种，每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量，如表所示。怎样安排下料方式，使得即满足需要，所用的原材料又最少？零件方个数式零件零件毛坯数整数规划的模型设：xj表示用Bj(j=1.2…n)种方式下料根数模型：整数规划的模型例三、机床分配问题设有m台同类机床，要加工n种零件。已知各种零件的加工时间分别为a1,a2,…an，问

2、如何分配，使各机床的总加工任务相等，或者说尽可能平衡。整数规划的模型设：1分配第i台机床加工第j种零件；xij＝（i=1,2,…,m;j=1,2,…,n）0相反。于是，第i台机床加工各种零件的总时间为：因此，求xij，使得又由于一个零件只能在一台机床上加工，所以有整数规划的模型整数规划一般形式依照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、混合整数规划、0－1整数规划。整数规划的数学模型部分或者全部为整数纯整数规划：所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要求取整数）。全整数规划：除所有决策变量

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

4、线性规划问题（一般称为松弛问题）。整数规划与线性规划的关系且为整数用图解法求出最优解x1＝3/2,x2=10/3且有Z=29/6x1x2⑴⑵33(3/2,10/3)现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3),(2，3),(1，4),(2，4)。显然，它们都不可能是整数规划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。整数规划与线性规划的关系因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。如上例：其中（2

5、，2）（3，1）点为最大值，Z=4。目前，常用的求解整数规划的方法有：分支定界法和割平面法；对于特别的0－1规划问题采用隐枚举法和匈牙利法。整数规划与线性规划的关系考虑纯整数问题：整数问题的松弛问题：分枝定界法1、先不考虑整数约束，解(IP)的松弛问题(LP)，可能得到以下情况之一：⑴.若(LP)没有可行解，则(IP)也没有可行解，停止计算。⑵.若(LP)有最优解，并符合(IP)的整数条件，则(LP)的最优解即为(IP)的最优解，停止计算。⑶.若(LP)有最优解，但不符合(IP)的整数条件，转入下一步。为讨论方便，设(LP)的最优解为

6、：分枝定界法2、定界：记(IP)的目标函数最优值为Z*,以Z(0)作为Z*的上界，记为＝Z(0)。再用观察法找的一个整数可行解X′，并以其相应的目标函数值Z′作为Z*的下界，记为Z＝Z′，也可以令Z＝－∞，则有:Z≤Z*≤3、分枝：在(LP)的最优解X(0)中，任选一个不符合整数条件的变量，例如xr=b’r（不为整数），以[b’r]表示不超过b’r的最大整数。构造两个约束条件xr≤[b’r]和xr≥[b’r]＋1分枝定界法将这两个约束条件分别加入问题(IP)，形成两个子问题(IP1)和(IP2)，再解这两个问题的松弛问题(LP1)和(

7、LP2)。4、修改上、下界：按照以下两点规则进行。⑴.在各分枝问题中，找出目标函数值最大者作为新的上界；⑵.从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。5、比较与剪枝：各分枝的目标函数值中，若有小于Z者，则剪掉此枝，表明此子问题已经探清，不必再分枝了;否则继续分枝。如此反复进行，直到得到Z＝Z*＝为止，即得最优解X*。分枝定界法为了更好地说明用分枝定界法求整数规划最优解的过程，我们选择只有两个变量的引例3.2.1进行求解。例3.3.1用分枝定界法求解整数规划问题(P)：maxZ=15x120x2s.t.6x14x2

8、25x13x210xi{0,1,2,…}解：1.求解如下的松弛问题(P0)：(P0)：maxZ=15x120x2s.t.6x14x225x13x210xi0，i=1,2得最优解x1=2.5，x2=2.