运筹学 线性整数规划 2018/12/7.

Presentation on theme: "运筹学 线性整数规划 2018/12/7."— Presentation transcript:

1 运筹学 线性整数规划 2018/12/7

2 线性整数规则 (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≥ x≥0 ,x各分量部分或全体取整数 2018/12/7

3 决策变量（部分或全体）取整数的原因：这些决策变量可以是购买的设备数，工作的工人数，设备的工厂数，购买的股票数（1手，2手……）
LIP研究概况 LIP要比LP问题的求解复杂得多，目前尚未找到一个较好的统一的求解方法，目前研究较多的有 穷举法（太繁杂） 取整法（误差不好估计） LIP（分支定界法，割平面法等） NLIP（动态规划法，图论法等） 2018/12/7

4 穷举法思想：设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个格子点验证是否为基本可行解，并比较目标值。 2018/12/7

5 例1：max z=4x1+3x2 s.t 4x1+5x2≤20 2x1+x2 ≤6 x1,x2≥0 x1,x2为整数 A(5/3,8/3)
2018/12/7

6 表1 i x1 xi=(x1,x2) z(xi) 1 (0,0) 2 (0,1) 3 (0,2) 6 4 (0,3) 9 5 (0,4)
(0,0) 2 (0,1) 3 (0,2) 6 4 (0,3) 9 5 (0,4) 12 (1,0) 7 (1,1) 8 (1,2) 10 * (1,3) 13 * 10 (2,0) 11 (2,1) (2,2) 14 * 13 (3,0) 2018/12/7

7 取整法思路：利用单纯形法对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所示，可得多种取整结果，取整法有多种结果，其误差不好估计。 2018/12/7

8 表2 i 1 2 3 4 xi (1,2) (2,3) (1,3) (2,2) z(xi) 10 不满足约束条件 13 14
2018/12/7

9 分支定界法 (Branch and Bound Method)
基本思想：它是一种综合穷举法与取整法求解思想，并采用有序的“分支”和定界（取整）步骤，逐步舍弃非格子点区域，然后来寻求LIP最优解的方法，也是目前较为成功地求解纯整数规划与混合整数规划的方法之一。其基本思路可通过下述案例介绍： 例1：max z=4x1+3x max z=4x1+3x2 s.t 4x1+5x2≤ s.t 4x1+5x2≤20 LIA: x1+x2 ≤ LA: x1+x2 ≤6 x1,x2≥ x1,x2≥0 x1,x2为整数 求最优解 最优值 去掉 整数约束 2018/12/7

10 解Ⅰ： (x1分支) s.t 4x1+5x2≤20 LD1 2x1+x2 ≤6 x1 ≤1 x1,x2≥0 s.t 4x1+5x2≤20
max z=4x1+3x2 s.t 4x1+5x2≤20 LD x1+x2 ≤6 x1 ≤1 x1,x2≥0 max z=4x1+3x2 s.t 4x1+5x2≤20 LD x1+x2 ≤6 x1 ≥2 x1,x2≥0 2018/12/7

11 解Ⅰ（x1分支）： 由图(a)可知LD1与LD2分别有上述xD1与xD2两个最优解，比较两者目标值可知： LIA有最优解 最优值 图(a)
6 图(a) 5 4 3 B(2,2) D1 2 D3 1 D2 1 2 3 4 5 2018/12/7

12 LIP之最优解应在D=D1∪D2∪D3区域上的格子点上达到 (x1,x2) 4x1+5x2≤20
这是由于下述理由： LIP之最优解应在D=D1∪D2∪D3区域上的格子点上达到 (x1,x2) 4x1+5x2≤20 D3= x1+x2 ≤ 中不含格子点，故 1<x1 <20 不可能在D3内达到，而只能在D1或D2的格子点上达到。 D2区域内格子点上的最大值=z(xD2)≥D1区域内最大值= z(xD1)≥D1区域内格子点上的最大值，由此可知对 或D2格子点x之目标值有 * 2018/12/7

13 解Ⅱ： (x2分支) s.t 4x1+5x2≤20 LD6 2x1+x2 ≤6 x2 ≤2 x1,x2≥0 s.t 4x1+5x2≤20
max z=4x1+3x2 s.t 4x1+5x2≤20 LD x1+x2 ≤6 x2 ≤2 x1,x2≥0 max z=4x1+3x2 s.t 4x1+5x2≤20 LD x1+x2 ≤6 x2 ≥3 x1,x2≥0 2018/12/7

14 解Ⅱ（x2分支）： 由图(b)可知LD6与LD4分别有上述xD6与xD4，虽然 两者有相同的目标值14，但由于xD6 =(2, 2)T为整 数解，满足LIA约束，而xD4 =（5/4, 3)T有一分 量为分数，故非LIA可行解。 6 图(b) 5 4 D4 3 D5 2 D6 1 1 2 3 4 5 2018/12/7

15 运用上述同样原理可知，LIA最优解只能在D4与D6上达到，且由于D6内格子点上最大值=z(xD6)=D4上最大值=z(xD4)≥D4内格子点上最大值。
故对 与D6上之格子点x之目标值均有 LIA有最优解 最优值 显然解Ⅰ与解Ⅱ有相同的最优解与最优值。 命题1： * 2018/12/7

16 例2 人工算法（P160） x2 x1=4 4x1+40x2=140 195x1+273x2=1365 x1 A(2.44,3.26)
(2,3.3)D B(3,2.86) 7 x1 x2 2018/12/7

17 LIA s.t 195x1+273x2≤1365 4x1+40x2≤140 x1≤4 x1,x2≥0 x1,x2为整数
max z =2x1+3x2 LIA s.t 195x1+273x2≤1365 4x1+40x2≤140 x1≤4 x1,x2≥0 x1,x2为整数 max z =2x1+3x2 LA s.t 195x1+273x2≤1365 4x1+40x2≤140 x1≤4 x1,x2≥0 x2≤3，x2≥4，自己完成 A 2018/12/7

18 A x1≤2 x1≥3 LA1 s.t 195x1+273x2≤1365 4x1+40x2≤140 x1≤4 x1,x2≥0
max z =2x1+3x2 LA1 s.t 195x1+273x2≤1365 4x1+40x2≤140 x1≤4 x1≤2 x1,x2≥0 max z =2x1+3x2 LA2 s.t 195x1+273x2≤1365 4x1+40x2≤140 x1≤4 x1≥3 x1,x2≥0 B 2018/12/7

19 B x2≤2 x2≥3 LA21 s.t 195x1+273x2≤1365 4x1+40x2≤140 x1≤4 x2≤2 x1,x2≥0
max z =2x1+3x2 LA21 s.t 195x1+273x2≤1365 4x1+40x2≤140 x1≤4 x1≥3 x2≤2 x1,x2≥0 max z =2x1+3x2 LA22 s.t 195x1+273x2≤1365 4x1+40x2≤140 x1≤4 x1≥3 x2≥3 x1,x2≥0 无可行解 2018/12/7

20 层次 LP y z(x) 1 LA (2,3)T (2.44,3.26)T 13 14.66 2 LA1 (2,3.3)T 13.9
14.58 LA2 (3,2)T (3,2.86)T 12 3 LA21 (4,2)T 14 LA22 无可行解 -- 2018/12/7

21 计算机算法说明 LA22无可行解 2018/12/7

22 分支定界算法与判别准则 max z = Cx max z = Cx LIA s.t Ax≤b LA s.t Ax≤b x≥0 x≥0
去掉整数约束 任取LA整数可行解y z<==z(y) 求解LA A 2018/12/7

23 选bi为分支参量，设分支规划为LB1与LB2 END G
A D N LIA无解 Y Y N Y y为LIA最优解 J N F 根据分支准则进行分支与判别 ， 选bi为分支参量，设分支规划为LB1与LB2 END G LB1: LA xi≤[bi] LB1: LA xi≥[bi] C B 2018/12/7

24 B LB1与LB2均有最优解 此二最优解均为整数解 此二最优解均为非整数解 判别准则Ⅳ 判别准则Ⅰ 判别准则Ⅱ 判别准则Ⅲ D F E C
G H J 2018/12/7

25 对上界 与下界 的处理，该LBi分支有最优解 ，i=1,2， LBi分支有整数可行解yi， i=1,2，则取
亦可有其它的处理方法（对上界、下界的处理） 分支取整数变量选取准则 按决策变量的重要程度决定选取的优先顺序 按各决策变量中具有最大分数值的对应变量作为分支取整变量。 按目标函数值最大的对应子规划进行分支 剪枝原则：若某分支最优解 有 或 ，则该分支可剪枝。 2018/12/7

26 判别准则Ⅰ： 判别准则Ⅱ： 若LB1与LB2均无最优解，则LIA无解。
若两分支中一分支有非整数最优解 ，另一分支无最优解，则需对前一分支继续分支求解。 判别准则Ⅱ： 若两个分支均有整数最优解，则可通过各平行分支的目标函数值比较，并取目标函数值为最大的对应整数解为LIA最优解。 2018/12/7

27 若某分支I为整数最优解 ，且 ，则 ；否则剪枝；同时若有 （此中 为各平行分支问题所提供的最优解或上界），则
判别准则Ⅲ： 若某分支I为整数最优解 ，且 ，则 ；否则剪枝；同时若有 （此中 为各平行分支问题所提供的最优解或上界），则 （ 是不可能的，因 是IA最优解，而z'是其整数最优解），然后考察另一分支。 若某分支Ⅱ有非整数最优解 ，若 则剪枝（不再继续分支）；若 ，则继续进行分支。 判别准则Ⅳ： 若二个分支最优解均为非整数，则对目标函数较大的分支先进行分支计算，并对 与 作处 理，设最优解为U与V，此时若计算所得最优解为整数U，且z(U)>z(V)，或V分支无最优解，则U为LIA最优解；若z(U)<z(V)，则对V对应分支继续分支求解，且遵循剪枝原则。 2018/12/7

28 属性 xP1 xP2 z(xP1)与z(xP2)比较 判别准则 注 1 非整数 整数 z(xP1)≤z(xP2) ⅢH 例1 2
ⅢG -- 3 z(xP1) z(xP2) Ⅳ 例2 4 Ⅱ 5 无最优解 ⅠF 6 ⅠE 7 ⅠD > < > < 2018/12/7