资源描述：
《线性整数规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、运筹学线性整数规划10/6/20211线性整数规则(LinearIntegerprogramming)基本概念定义1：在LP中当要求决策变量（部分或全部）取整数值时，此类LP称为线性整数规划（LIP）或整数线性规划(ILP)。对于一个LP，若要求全体决策变量均为整数，则该LP称为纯（Pure）整数线性规划；否则称为混合（mixed）整数线性规划；又若决策变量只能取0与1时，则该LP称为0—1规划。maxz=Cxmaxz=CxLP:s.tAx=bLIP:s.tAx=bx≥0x≥0,x各分量部分或全体取
2、整数10/6/20212决策变量（部分或全体）取整数的原因：这些决策变量可以是购买的设备数，工作的工人数，设备的工厂数，购买的股票数（1手，2手……）LIP研究概况LIP要比LP问题的求解复杂得多，目前尚未找到一个较好的统一的求解方法，目前研究较多的有穷举法（太繁杂）取整法（误差不好估计）LIP（分支定界法，割平面法等）NLIP（动态规划法，图论法等）10/6/20213穷举法思想：设x=(x1,x2,…xn)T，首先将每个xj的整数上界找出来，使0≤xj≤，j=1~n，然后在可行域D中将满足上述条
3、件的整数点全部找出来，共有个。最后逐个验证其是否为基本可行点(Ax≤b，x≥0)，并对这些基本可行解通过目标函数值的比较来求最优解。例1：0≤x1≤3，0≤x2≤4，故共有(3+1)(4+1)=20个整数点（又称格子点），其中只有13个基本可行点，通过下表1比较目标函数值可知可取为最优解，，但穷举法枚举的工作量太大，以n=4，0≤xj≤24为例，共有254=390625个格子点验证是否为基本可行解，并比较目标值。10/6/20214例1：maxz=4x1+3x2s.t4x1+5x2≤202x1+x2
4、≤6x1,x2≥0x1,x2为整数123451234562x1+x2=64x1+5x2=2A(5/3,8/3)010/6/20215ix1xi=(x1,x2)z(xi)10(0,0)02(0,1)33(0,2)64(0,3)95(0,4)1261(1,0)47(1,1)78(1,2)10*9(1,3)13*102(2,0)811(2,1)1112(2,2)14*133(3,0)12表110/6/20216取整法思路：利用单纯形法对LIP取消整数约束后的LP求最优解，设为，若其中某些分量非整数，则将其
5、取整，并将如此取得的解作为LIP的近似最优解，如例1，首先去掉x1,x2为整数之约束，求解LP:maxz=4x1+3x2s.t4x1+5x2≤202x1+x2≤6x1,x2≥0由图解法可得最优点A(5/3,8/3)或，注意到1≤5/3≤2，2≤8/3≤3，故对两分量取整有如表2所示，可得多种取整结果，取整法有多种结果，其误差不好估计。10/6/20217i1234xi(1,2)(2,3)(1,3)(2,2)(2,2)z(xi)10不满足约束条件131414表210/6/20218分支定界法(Bran
6、chandBoundMethod)基本思想：它是一种综合穷举法与取整法求解思想，并采用有序的“分支”和定界（取整）步骤，逐步舍弃非格子点区域，然后来寻求LIP最优解的方法，也是目前较为成功地求解纯整数规划与混合整数规划的方法之一。其基本思路可通过下述案例介绍：例1：maxz=4x1+3x2maxz=4x1+3x2s.t4x1+5x2≤20s.t4x1+5x2≤20LIA:2x1+x2≤6LA:2x1+x2≤6x1,x2≥0x1,x2≥0x1,x2为整数求最优解最优值去掉整数约束10/6/20219解
7、Ⅰ：(x1分支)x1≤1x1≥2maxz=4x1+3x2s.t4x1+5x2≤20LD12x1+x2≤6x1≤1x1,x2≥0maxz=4x1+3x2s.t4x1+5x2≤20LD22x1+x2≤6x1≥2x1,x2≥010/6/202110解Ⅰ（x1分支）：由图(a)可知LD1与LD2分别有上述xD1与xD2两个最优解，比较两者目标值可知：LIA有最优解最优值12345123456B(2,2)图(a)D1D3D210/6/202111这是由于下述理由：LIP之最优解应在D=D1∪D2∪D3区域上的
8、格子点上达到(x1,x2)4x1+5x2≤20D3=2x1+x2≤6中不含格子点，故1
