《运筹学——整数规划 Integer Programming（IP）》课程教学资源（PPT课件）第五章 整数规划

花数规判 Integer Programming(IP) 第五章 整数规划

1 整数规划 Integer Programming（IP） 第五章 整数规划

数规判 Integer programming(IP) 整数规划的数学模型及解的特点 整数规划数学模型的一般形式 (|P)问题Max(min)z=∑c ∑a≤(或=,或2)b1=1,2, S t X20j=1,2,…,n x中部分或全部取整数 松弛问题Max(mi)z=Σc ∑as(或=,或2)bi=1,2,…,m X20j=1,2, n 2

2 整数规划 Integer Programming（IP） 整数规划的数学模型及解的特点 整数规划数学模型的一般形式 （IP）问题 Max（min） z = ∑cjxj ∑aijxj ≤（或=，或≥）bi i=1，2，…，m xj ≥ 0 j=1，2，…，n xj 中部分或全部取整数 s.t. 松弛问题 Max（min） z = ∑cjxj ∑aijxj ≤（或=，或≥）bi i=1，2，…，m xj ≥ 0 j=1，2，…，n

数规判 Integer programming(IP) 整数规划的数学模型及解的特点 整数规划问题的类型 1.纯整数线性规划—— pure integer linear programming:全 部决策变量都必须取整数值 混合整数线性规划— mixed integer linear programming: 决策变量中一部分必须取整数值,另一部分可以不取整数值。 3.0-1型整数线性规划——zero- one integer linear programmIng:决策变量只能取值0或

3 整数规划 Integer Programming（IP） 整数规划的数学模型及解的特点 整数规划问题的类型 1. 纯整数线性规划——pure integer linear programming：全 部决策变量都必须取整数值。 2. 混合整数线性规划——mixed integer linear programming： 决策变量中一部分必须取整数值，另一部分可以不取整数值。 3. 0-1型整数线性规划——zero-one integer linear programming：决策变量只能取值 0 或 1

数规判 Integer programming(IP) 整数规划的例子 例1、Page130 工作时间和人员安排问题 例2、Page130 投资项目选择问题 例3、Page131 建厂选址问题

4 整数规划 Integer Programming（IP） 整数规划的例子 例1、Page 130 工作时间和人员安排问题 例2、Page 130 投资项目选择问题 例3、Page 131 建厂选址问题

数规判 Integer programming(IP) 整数规划问题的求解方法 分支定界法 branch and bound method 分支定界法是一种隐枚举方法( mplicit enumeration)或部 分枚举方法,它不是一种有效的算法,是枚举方法基础上的改进。 其关键是分支和定界。 例 Max Z=X+ x2 14X1+9X2≤51 st -6X1+3X2≤1 X1,X220 X1,X2取整数

5 整数规划 Integer Programming（IP） 整数规划问题的求解方法 分支定界法branch and bound method 分支定界法是一种隐枚举方法（implicit enumeration）或部 分枚举方法，它不是一种有效的算法，是枚举方法基础上的改进。 其关键是分支和定界。 例—— Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ， X2 ≥ 0 X1 ， X2 取整数 s.t

数规判 Integer programming(IP) 整数规划问题的求解方法 松弛问题Maxz=X1+X2 分支定界法图解整数规划 14X1+9X2≤51 6X1+3X≤1 X1,X2≥0 该整数规划松弛问题的解为: (X1,X2)=(3/2,10/3) Z1=29/6 6

6 整数规划 Integer Programming（IP） 整数规划问题的求解方法 分支定界法图解整数规划 松弛问题 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ， X2 ≥ 0 该整数规划松弛问题的解为： （X1 ，X2 ）= （3/2 ，10/3） Z1 = 29/6

数规判 Integer programming(IP) 整数规划问题的求解方法 松弛问题Maxz=X1+X2 14X+9X≤51 分支定界法图解整数规划 -6X1+3X2≤1 (3/2,10/3) X1,X2≥0 Z1=29/6 B1 Max Z=X,+ X2 14X1+9X2≤51 B1:解 -6X1+3X2≤1 B2:解 (2,23/9) X ≥2 (1,713) Z11=41/9 X, x ≥0 Z21=17/3 B2 Max Z=X+ x 14X1+9X2≤51 6X1+3X2≤1 X X1,X2≥0

7 整数规划 Integer Programming（IP） 整数规划问题的求解方法 分支定界法图解整数规划 松弛问题 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 （ X1 ， X2 ≥ 0 3/2 ，10/3） Z1 = 29/6 B1 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≥ 2 X1 ， X2 ≥ 0 B2 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≤ 1 X1 ， X2 ≥ 0 B2：解 （1，7/3 ） Z21 = 17/3 B1：解 （2，23/9 ） Z11 = 41/9

数规判 Integer programming(IP) 整数规划问题的求解方法 B1 Max Z=x+x 14X+9X2≤51 分支定界法图解整数规划 6X1+3X2≤1 (3/2,10/3) X B1:解 X 1 X,≥0 Z1=29/6 2 (2,23/9) B11 Max Z=X1+ x2 B2:解 Z11=41/9 14X+9X2≤51 6X1+3X2≤1 2 (1,7/3) X ≥2 Z21=1713 X2≥3 B12:解 (33/14,2) X,X,≥0 Z12=61/14 B12 Max Z=x+ X 14X+9X2≤51 6X1+3X2≤1 X 2 X,≤2 X1,X2≥0 8

8 整数规划 Integer Programming（IP） 整数规划问题的求解方法 分支定界法图解整数规划 （3/2 ，10/3） Z1 = 29/6 B1 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≥ 2 X1 ， X2 ≥ 0 B2：解 （1，7/3 ） Z21 = 17/3 B1：解 （2，23/9 ） Z11 = 41/9 B11 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≥ 2 X2 ≥ 3 X1 ， X2 ≥ 0 B12 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≥ 2 X2 ≤ 2 X1 ， X2 ≥ 0 B12：解 （33/14，2 ） Z12 = 61/14

数规判 Integer programming(IP) 整数规划问题的求解方法 B12 Max Z=X,+ x2 14X+9X2≤51 分支定界法图解整数规划 -6X1+3X≤1 (3/2,10/3) X ≥2 X,≤2 Z1=29/6 B1:解 X,X,≥0 (2,23/9) Z11=41/9 B121 Max Z=X+ x2 B2:解 14X1+9X2≤51 (1,713) -6X1+3X2≤1 Z21=17/3 B12:解 X (3314,2) X2≤2 Z12=61114 X1,X2≥0 B122 Max Z=X1+ X2 B121:解 14X1+9X2≤51 B122:解 6X1+3X2≤1 (2,2) Z121=4 X ≤2 Z122=4 X2≤2 X1,Ⅹ2≥0 9

9 整数规划 Integer Programming（IP） 整数规划问题的求解方法 分支定界法图解整数规划 （3/2 ，10/3） Z1 = 29/6 B2：解 （1，7/3 ） Z21 = 17/3 B12 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≥ 2 X2 ≤ 2 X1 ， X2 ≥ 0 B12：解 （33/14，2 ） Z12 = 61/14 B121 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≥ 3 X2 ≤ 2 X1 ， X2 ≥ 0 B122 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≤ 2 X2 ≤ 2 X1 ， X2 ≥ 0 B121：解 （3，1 ） Z121 = 4 B122：解 （2，2 ） Z122 = 4 B1：解 （2，23/9 ） Z11 = 41/9

数规判 Integer programming(IP) 整数规划问题的求解方法 割平面法 cutting plane approach 割平面法求解整数规划问题时,若其松驰问题的最优解X*不 满足整数要求时,则从X*的非整分量中选取一个,用以构造一个 线性约束条件( Gomory割平面),将其加入原松驰问题中,形成 个新的线性规划,然后求解之。其关键在于新增加的这个线性约 束条件将切割掉部分非整数解,至少将当前松驰问题的非整数最优 解切割掉了,而不会切割掉问题的任何整数解。 10

10 整数规划 Integer Programming（IP） 整数规划问题的求解方法 割平面法cutting plane approach 割平面法求解整数规划问题时，若其松驰问题的最优解 X* 不 满足整数要求时，则从 X* 的非整分量中选取一个，用以构造一个 线性约束条件（Gomory 割平面），将其加入原松驰问题中，形成 一个新的线性规划，然后求解之。其关键在于新增加的这个线性约 束条件将切割掉部分非整数解，至少将当前松驰问题的非整数最优 解切割掉了，而不会切割掉问题的任何整数解