运筹学.pptVIP

线性整数规则(Linear Integer programming) 基本概念 定义1：在LP中当要求决策变量（部分或全部）取整数值时，此类LP称为线性整数规划（LIP）或整数线性规划(ILP)。对于一个LP，若要求全体决策变量均为整数，则该LP称为纯（Pure）整数线性规划；否则称为混合（mixed）整数线性规划；又若决策变量只能取0与1时，则该LP称为0—1规划。 max z=Cx max z=Cx LP: s.t Ax=b LIP: s.t Ax=b x≥0 x≥0 ,x各分量部分或全体取整数 决策变量（部分或全体）取整数的原因：这些决策变量可以是购买的设备数，工作的工人数，设备的工厂数，购买的股票数（1手，2手……） LIP研究概况 LIP要比LP问题的求解复杂得多，目前尚未找到一个较好的统一的求解方法，目前研究较多的有 穷举法（太繁杂） 取整法（误差不好估计） LIP（分支定界法，割平面法等） NLIP（动态规划法，图论法等） 穷举法思想：设x=(x1,x2,…xn)T，首先将每个xj的整数上界 找出来，使0≤xj≤ ，j=1~n，然后在可行域D中将满足上述条件的整数点全部找出来，共有 个。最后逐个验证其是否为基本可行点(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个格子点验证是否为基本可行解，并比较目标值。 例1：max z=4x1+3x2 s.t 4x1+5x2≤20 2x1+x2 ≤6 x1,x2≥0 x1,x2为整数 取整法思路：利用单纯形法对LIP取消整数约束后的LP求最优解，设为 ，若其中某些分量 非整数，则将其取整 ，并将如此取得的解 作为LIP的近似最优解，如例1，首先去掉x1,x2为整数之约束，求解LP: max z=4x1+3x2 s.t 4x1+5x2≤20 2x1+x2 ≤6 x1,x2≥0 由图解法可得最优点A(5/3,8/3)或 ，注意到1≤5/3≤2， 2≤8/3≤3，故对 两分量取整有如表2所示，可得多种取整结果，取整法有多种结果，其误差不好估计。 分支定界法(Branch and Bound Method) 基本思想：它是一种综合穷举法与取整法求解思想，并采用有序的“分支”和定界（取整）步骤，逐步舍弃非格子点区域，然后来寻求LIP最优解的方法，也是目前较为成功地求解纯整数规划与混合整数规划的方法之一。其基本思路可通过下述案例介绍： 例1：max z=4x1+3x2 max z=4x1+3x2 s.t 4x1+5x2≤20 s.t 4x1+5x2≤20 LIA: 2x1+x2 ≤6 LA: 2x1+x2 ≤6 x1,x2≥0