北京交通大学经济管理学院max z = 20x, +10x,School of EgruManagomentI0S4Boiljing JiaopngUniversity5x +4x 242x +5x2 132X,x, 3 0,x,1 14x = 4.8,x2 = 0,z = 96加上整数约束后怎样求解？将松驰问题的最优解取整可以吗？枝举法怎样？北京交通大学
0 1 2 1 2 3 4 加上整数约束后怎样求解？ 将松弛问题的最优解取整可以吗？ 枚举法怎样？
IP比LP更难求解。一般不能“枚举”、不能“四舍五入”。如例1，不考虑整数条件，最优解为x*=(4.8，0)T,Z=96z*=96。四舍五入得X2Z=90x=(5, 0)T,不是可行解(4,1)x=(4, 0)T,不是最优解X1(4.8,0而最优解是)x*=(4， 1)T， z*=90
z=90 z=96 x1 x2 (4.8,0 ) (4,1) IP比LP更难求解。一般不能“枚举” 、不能 “四舍五入”。如例1， 不考虑整数条件，最 优 解 为 x *=(4.8， 0)T ， z *=96。四舍五入得 x=(5，0)T ， 不是可行解 x=(4，0)T ， 不是最优解 而最优解是 x * =(4，1)T ，z *=90
北京交通大学经济管理学院整数规划的数学模型School of Eoics andManagomentBoijingJiaotong University数学模型的一般形式nmax Z(或min Z)=a cjxjj=1n1oa(i=1.2L m)a,x, f(= 3)b:11j-1:1<130（j=1,2L n）且部分或全部为整数t依照决策变量取整要求的不同，整数规划可分为纯（全整数规划）、混合整数规划、0一1整整数规划数规划。北京交通大学
整数规划的数学模型 依照决策变量取整要求的不同，整数规划可分为纯 整数规划（全整数规划）、混合整数规划、0－1整 数规划。 数学模型的一般形式
北京交通大学经济管理学院SchoolotandManagomentBoijingJiaotong University纯整数规划：所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要求取整数）。混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。0一1整数规划：所有决策变量只能取0或1两个整数。北京交通大学
纯整数规划：所有决策变量要求取非负整数 （这时引进的松弛变量和剩余变量可以不要求 取整数）。 混合整数规划：只有一部分的决策变量要求取 非负整数，另一部分可以取非负实数。 0－1整数规划：所有决策变量只能取 0 或 1 两 个整数
北京交通大学整数规划与线性规划的关系经济管理学院School of Econcnics andManagomentBojing Jiaotong University注：从数学模型上看IP似乎是LP的一种特殊形式,但求解并不能在LP的基础上.通过舍入取整得到满足整数要求的解.实际上两者有很大的不同,通过舍入得到的解（整数）不一定就是最优解，有时甚至不能保证所得到的解是整数可行解.（如例1）求解Excel求解IP的常用方法有：分支定界法和割平面法：特别的0一1规划问题采用隐枚举法和匈牙利法北京交通大学
整数规划与线性规划的关系 注：从数学模型上看IP似乎是LP的一种特殊 形式,但求解并不能在LP的基础上,通过舍入 取整得到满足整数要求的解.实际上两者有很 大的不同,通过舍入得到的解（整数）不一定 就是最优解,有时甚至不能保证所得到的解是 整数可行解.（如例1） 求解IP的常用方法有： 分支定界法和割平面法; 特别的0－1规划问题采用隐枚举法和匈牙利法. Excel 求解