花数规判 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