西安电子科技大学数学建模讲义第六讲

《西安电子科技大学数学建模讲义第六讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、主讲人:穆学文西安电子科技大学数学系Email:mxw1334@126.com数学建模讲义数学建模专题讲座最优化模型---线性整数规划整数规划是一类要求变量取整数值的数学规划，可分成线性和非线性两类。根据变量的取值性质，又可以分为全整数规划，混合整数规划，0-1整数规划等。整数规划是数学规划中一个较弱的分支，目前只能解中等规模的线性整数规划问题，而非线性整数规划问题，还没有好的办法。整数规划简介线性整数规划1、建模引例。2、线性整数规划模型3、线性整数规划的主要算法。4、0-1规划选讲1、建模引例例1:某厂拟用火车装运甲、乙两种货物集装箱，每箱的体积、重量、可获利润以及装运所受限制

2、如下：货物集装箱体积(米3)重量(百斤)利润(百元)甲5220乙4510托运限制2413问两种货物各装运多少箱，可使获得利润最大？设甲、乙两种货物装运箱数分别为x1和x2。显然，x1、x2都要求为整数,于是可建立整数规划模型如下：Maxz＝20x1+10x2(1)5x1+4x2≤24(2)2x1+5x2≤13(3)x1,x2≥0(4)x1,x2为整数(5)是不是可通过把不考虑整数要求求得的最优解经过“化整”得到满足整数要求的最优解呢？它和线性规划问题的区别在于条件(5)。此例可解得x1=4.8,x2=0，凑整为x1=5,x2=0，这就破坏了条件(2)，因而不是可行解；如截断小数变为

3、x1=4,x2=0，这当然满足所有约束条件，但不是最优解，因为对x1=4,x2=0有z＝80，而对x1=4,x2=1（也是可行解）有z＝90。因此要专门研究整数规划的解法。整数规划(IP)的一般数学模型:max(min)z=Σcjxjs.t.Σaijxjbi(i=1,2,…m)xj0且部分或全部是整数2.线性整数规划模型解法概述当人们开始接触整数规划问题时，常会有如下两种初始想法：因为可行方案数目有限，因此经过一一比较后，总能求出最好方案，例如，背包问题充其量有2n-1种方式；连线问题充其量有n!种方式；实际上这种方法是不可行。设想计算机每秒能比较1000000个方式，那么要比

4、较完20!（大于2*1018）种方式，大约需要800年。比较完260种方式，大约需要360世纪。先放弃变量的整数性要求，解一个线性规划问题，然后用“四舍五入”法取整数解，这种方法，只有在变量的取值很大时，才有成功的可能性，而当变量的取值较小时，特别是0-1规划时，往往不能成功。例2求下列问题：MaxZ=3x1+13x2s.t.2x1+9x24011x1-8x282x1,x20,且取整数值O1234567891054321x1x2I(2,4)B(9.2,2.4)AD可行域OABD内整数点，放弃整数要求后，最优解B(9.2,2.4)Z0=58.8，而原整数规划最优解I(2,4)Z

5、0=58，实际上B附近四个整点(9,2)(10,2)(9,3)(10,3)都不是原规划最优解。3线性整数规划的解法枚举法仅仅对极小规模的问题有效分支定界法应用比较广泛，对中小规模问题割平面法应用比较广泛，对中小规模问题分枝定界法是20世纪60年代由Land-Doig和Dakin等人提出的。这种方法既可用于纯整数规划问题，也可用于混合整数规划问题，而且便于用计算机求解，所以很快成为解整数规划的最主要的方法。3.1分枝定界法分枝定界法步骤原问题的松驰问题：任何整数规划（IP），凡放弃某些约束条件（如整数要求）后，所得到的问题（P）都称为（IP）的松驰问题。一般求解对应的松驰问题，可能会

6、出现下面几种情况：若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计算结束。若松驰问题无可行解，则原整数规划问题也无可行解，计算结束。若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优解，转下一步。从不满足整数条件的基变量中任选一个xl进行分枝，它必须满足xl[xl]或xl[xl]+1中的一个，把这两个约束条件加进原问题中，形成两个互不相容的子问题（两分法）。定界：把满足整数条件各分枝的最优目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。剪枝：把那些子问题的最优值与界值比较，凡不优或不能更优的分枝全剪掉，直到每个分枝都查清为止。例3

7、求解问题Maxz=40x1+90x29x1+7x2≤567x1+20x2≤70x1,x2≥0,整数R0:z0=356x1=4.81x2=1.82R1:z1=349x1=4.00x2=2.10R2:z2=341x1=5.00x2=1.57R12:z12=327x1=1.42x2=3.00x2≥3R11:z11=340x1=4.00x2=2.00R21:z21=308x1=5.44x2=1.00R22:无可行解x1≤4x1≤1x1≥5x1≥2问题R0为:Maxz=40x1