线性整数规划

1、2020/9/15,1,运筹学,线性整数规划,2020/9/15,2,线性整数规则(Linear Integer programming),基本概念 定义1：在LP中当要求决策变量（部分或全部）取整数值时，此类LP称为线性整数规划（LIP）或整数线性规划(ILP)。对于一个LP，若要求全体决策变量均为整数，则该LP称为纯（Pure）整数线性规划；否则称为混合（mixed）整数线性规划；又若决策变量只能取0与1时，则该LP称为01规划。 max z=Cx max z=Cx LP: s.t Ax=b LIP: s.t Ax=b x0 x0 ,x各分量部分或全体取整数,2020/9/15,3,决策变

2、量（部分或全体）取整数的原因：这些决策变量可以是购买的设备数，工作的工人数，设备的工厂数，购买的股票数（1手，2手） LIP研究概况 LIP要比LP问题的求解复杂得多，目前尚未找到一个较好的统一的求解方法，目前研究较多的有 穷举法（太繁杂） 取整法（误差不好估计） LIP（分支定界法，割平面法等） NLIP（动态规划法，图论法等）,2020/9/15,4,穷举法思想：设x=(x1,x2,xn)T，首先将每个xj的整数上界 找出来，使0 xj ，j=1n，然后在可行域D中将满足上述条件的整数点全部找出来，共有 个。最后逐个验证其是否为基本可行点(Axb，x0)，并对这些基本可行解通过目标函数值的

3、比较来求最优解 。 例1： 0 x13， 0 x24，故共有(3+1)(4+1)=20个整数点（又称格子点），其中只有13个基本可行点，通过下表1比较目标函数值可知可取 为最优解， ，但穷举法枚举的工作量太大，以n=4， 0 xj 24为例，共有254=390625个格子点验证是否为基本可行解，并比较目标值。,2020/9/15,5,例1：max z=4x1+3x2 s.t 4x1+5x220 2x1+x2 6 x1,x20 x1,x2为整数,0,2020/9/15,6,表1,2020/9/15,7,取整法思路：利用单纯形法对LIP取消整数约束后的LP求最优解，设为 ，若其中某些分量 非整数，

4、则将其取整 ，并将如此取得的解 作为LIP的近似最优解，如例1，首先去掉x1,x2为整数之约束，求解LP: max z=4x1+3x2 s.t 4x1+5x220 2x1+x2 6 x1,x20 由图解法可得最优点A(5/3,8/3)或 ，注意到15/32， 28/33，故对 两分量取整有如表2所示，可得多种取整结果，取整法有多种结果，其误差不好估计。,2020/9/15,8,表2,2020/9/15,9,分支定界法(Branch and Bound Method),基本思想：它是一种综合穷举法与取整法求解思想，并采用有序的“分支”和定界（取整）步骤，逐步舍弃非格子点区域，然后来寻求LIP最优

5、解的方法，也是目前较为成功地求解纯整数规划与混合整数规划的方法之一。其基本思路可通过下述案例介绍： 例1：max z=4x1+3x2 max z=4x1+3x2 s.t 4x1+5x220 s.t 4x1+5x220 LIA: 2x1+x2 6 LA: 2x1+x2 6 x1,x20 x1,x20 x1,x2为整数 求最优解 最优值,去掉 整数约束,2020/9/15,10,解： (x1分支) x11 x12,2020/9/15,11,解（x1分支）： 由图(a)可知LD1与LD2分别有上述xD1与xD2两个最优解，比较两者目标值可知： LIA有最优解 最优值,1,2,3,4,5,1,2,3,

6、4,5,6,B(2,2),图(a),D1,D3,D2,2020/9/15,12,这是由于下述理由： LIP之最优解应在D=D1D2D3区域上的格子点上达到 (x1,x2) 4x1+5x220 D3= 2x1+x2 6 中不含格子点，故 1x1 20 不可能在D3内达到，而只能在D1或D2的格子点上达到。 D2区域内格子点上的最大值=z(xD2)D1区域内最大值= z(xD1)D1区域内格子点上的最大值，由此可知对 或D2格子点x之目标值有,*,2020/9/15,13,解： (x2分支) x22 x23,2020/9/15,14,解（x2分支）： 由图(b)可知LD6与LD4分别有上述xD6与

7、xD4，虽然两者有相同的目标值14，但由于xD6 =(2, 2)T为整数解，满足LIA约束，而xD4 =（5/4, 3)T有一分量为分数，故非LIA可行解。,图(b),1,2,3,4,5,1,2,3,4,5,6,D4,D5,D6,2020/9/15,15,运用上述同样原理可知，LIA最优解只能在D4与D6上达到，且由于D6内格子点上最大值=z(xD6)=D4上最大值=z(xD4)D4内格子点上最大值。 故对 与D6上之格子点x之目标值均有 LIA有最优解 最优值 显然解与解有相同的最优解与最优值。 命题1：,*,2020/9/15,16,例2 人工算法（P160）,2020/9/15,17,m

8、ax z =2x1+3x2 LIA s.t 195x1+273x21365 4x1+40 x2140 x14 x1,x20 x1,x2为整数,max z =2x1+3x2 LA s.t 195x1+273x21365 4x1+40 x2140 x14 x1,x20,A,x23，x24，自己完成,2020/9/15,18,A,max z =2x1+3x2 LA1 s.t 195x1+273x21365 4x1+40 x2140 x14 x12 x1,x20,max z =2x1+3x2 LA2 s.t 195x1+273x21365 4x1+40 x2140 x14 x13 x1,x20,B,x

9、12,x13,2020/9/15,19,B,max z =2x1+3x2 LA21 s.t 195x1+273x21365 4x1+40 x2140 x14 x13 x22 x1,x20,max z =2x1+3x2 LA22 s.t 195x1+273x21365 4x1+40 x2140 x14 x13 x23 x1,x20,x22,x23,无可行解,2020/9/15,20,2020/9/15,21,计算机算法说明,LA22无可行解,2020/9/15,22,分支定界算法与判别准则,max z = Cx LIA s.t Axb x0 x各分量为整数,max z = Cx LA s.t A

10、xb x0,去掉整数约束,求解LA,A,2020/9/15,23,A,LIA无解,y为LIA最优解,根据分支准则进行分支与判别 ， 选bi为分支参量，设分支规划为LB1与LB2,B,F,G,J,D,END,N,N,N,Y,Y,Y,C,2020/9/15,24,2020/9/15,25,对上界 与下界 的处理，该LBi分支有最优解 ，i=1,2， LBi分支有整数可行解yi， i=1,2，则取 亦可有其它的处理方法（对上界、下界的处理） 分支取整数变量选取准则 按决策变量的重要程度决定选取的优先顺序 按各决策变量中具有最大分数值的对应变量作为分支取整变量。 按目标函数值最大的对应子规划进行分支

11、剪枝原则：若某分支最优解 有 或 ，则该分支可剪枝。,2020/9/15,26,判别准则： 若LB1与LB2均无最优解，则LIA无解。 若两分支中一分支有整数最优解 ，另一分支无最优解，则 即为LIA最优解。 若两分支中一分支有非整数最优解 ，另一分支无最优解，则需对前一分支继续分支求解。 判别准则： 若两个分支均有整数最优解，则可通过各平行分支的目标函数值比较，并取目标函数值为最大的对应整数解为LIA最优解。,2020/9/15,27,判别准则： 若某分支I为整数最优解 ，且 ，则 ；否则剪枝；同时若有 （此中 为各平行分支问题所提供的最优解或上界），则 （ 是不可能的，因 是IA最优解，而z是其整数最优解），然后考察另一分支。 若某分支有非整数最优解