PPT《运筹学》

运筹学 线性整数规划 线性整数规则(Linear Integer programming) 基本概念定义1:在LP中当要求决策变量(部分或全部)取整数值时,此类LP称为线性整数规划(LIP)或整数线性规划(ILP).

对于一个LP,若要求全体决策变量均为整数,则该LP称为纯(Pure)整数线性规划;

否则称为混合(mixed)整数线性规划;

又若决策变量只能取0与1时,则该LP称为0―1规划.max z=Cx max z=CxLP: 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为整数

1 2

3 4

5 1

2 3

4 5

6 2x1+x2=6 4x1+5x2=2 A(5/3,8/3)

0 12 (3,0)

3 13

14 * (2,2)

12 11 (2,1)

11 8 (2,0)

2 10

13 * (1,3)

9 10 * (1,2)

8 7 (1,1)

7 4 (1,0)

1 6

12 (0,4)

5 9 (0,3)

4 6 (0,2)

3 3 (0,1)

2 0 (0,0)

0 1 z(xi) xi=(x1,x2) x1 i 表1 取整法思路:利用单纯形法对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所示,可得多种取整结果,取整法有多种结果,其误差不好估计.

14 14

13 不满足约束条件

10 z(xi) (2,2) (2,2) (1,3) (2,3) (1,2) xi

4 3

2 1 i 表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 x1,x2≥0 x1,x2为整数求最优解 最优值 去掉整数约束 解Ⅰx1分支)x1≤1 x1≥2 max z=4x1+3x2 s.t 4x1+5x2≤20LD1 2x1+x2 ≤6 x1 ≤1 x1,x2≥0 max z=4x1+3x2 s.t 4x1+5x2≤20LD2 2x1+x2 ≤6 x1 ≥2 x1,x2≥0 解Ⅰ(x1分支):由图(a)可知LD1与LD2分别有上述xD1与xD2两个最优解,比较两者目标值可知:LIA有最优解 最优值

1 2

3 4

5 1

2 3

4 5

6 B(2,2) 图(a) D1 D3 D2 这是由于下述理由:LIP之最优解应在D=D1∪D2∪D3区域上的格子点上达到 (x1,x2) 4x1+5x2≤20 D3=2x1+x2 ≤6 中不含格子点,故1