第五章:整敢规划(1) 分枝定界法基本原理 分枝定界法在处理整数规划问题时,借用线性 规划单纯形法的基本思想,在求相应的线性模 型解的同时,逐步加入对各变量的整数要求限 制,从而把原整数规划问题通过分枝迭代求最 优解 运学 熊中措教一
运筹学 熊中楷教授 分枝定界法基本原理 分枝定界法在处理整数规划问题时，借用线性 规划单纯形法的基本思想，在求相应的线性模 型解的同时，逐步加入对各变量的整数要求限 制，从而把原整数规划问题通过分枝迭代求最 优解。 第五章：整数规划（1）
第五章:整规劍(2 割平面法(P121例3) 屠夫杀猪,一刀下去,又准又狠 这一刀不能虚,也不能杀错位置 1.原理: 可行域中割去一部分 割去部分不含整数解 剩余部分有一个极点 正好是整数最优解。 “甲号 原有最优解要被割去 运学 熊中措教一
运筹学 熊中楷教授 割平面法（P121例3） 屠夫杀猪，一刀下去，又准又狠 这一刀不能虚，也不能杀错位置 1.原理： 原有最优解要被割去 正好是整数最优解。 剩余部分有一个极点 割去部分不含整数解 可行域中割去一部分 第五章：整数规划（2） X1 X2
第互章:整规劍(2) 切割方程特点: (1)切割方程不包含最优解 (2)切割方程没有切割整数解 运学 熊中措教一
运筹学 熊中楷教授 切割方程特点： （1）切割方程不包含最优解 （2）切割方程没有切割整数解 第五章：整数规划（2）
第五章:整数期划(2 目标函数等值线 割平面法(P121例3) Max z= Xl+X2 X1+X2<=1 非整数最优解 3X1+X2 X1>=0,X2>=0 切割:成为可行域顶点 X1,X2整数 整数最优解 切割方程如何确定? XI 运学 熊中措教提
运筹学 熊中楷教授 Max Z = X1+X2 －X1 + X2 <=1 3X1 + X2 <= 4 X1>=0 , X2 >=0 X1, X2 整数 割平面法（P121例3） 非整数 最优解 切割：成为可行域顶点 整数 最优解 1 1 0 切割方程如何确定？ 第五章：整数规划（2） X1 X2 目标函数等值线
第五章:整数期划(2 目标函数等值线 切割:成为可行域顶点 这样切割行吗? XI 运学 熊中措教提
运筹学 熊中楷教授 切割：成为可行域顶点 1 1 0 这样切割行吗？ 第五章：整数规划（2） X1 X2 目标函数等值线