《第三节割平面法ppt课件.ppt》由会员分享，可在线阅读，更多相关《第三节割平面法ppt课件.ppt（18页珍藏版）》请在三一办公上搜索。
1、割平面法的基本思想是：首先不考虑整数条件，增加另外的约束条件，把原来的可行域切掉一部分，被切掉的部分不包含任何整数可行解. 经过有限次的切割，最终得到某个顶点的坐标恰好是整数，并且是问题的最优解.,3.3 割平面法,例如 求解整数规划问题,为整数,例如 求解整数规划问题,为整数,例如 求解整数规划问题,为整数,割平面,整数规划（A）,松弛问题（B）,且为整数,回到一般问题上：,设松弛问题（B）的最优单纯形表为：,设 不是整数，,再设,表3-1,即,整数,若要决策变量都取整数，则,即,整数,若要决策变量都取整数，则,对上式引入松弛变量,割平面不等式,割平面方程,例1 用割平面法求解整数规划问题,
2、且为整数,解（1）把约束条件中的系数化为整数，加上松弛变量，去掉整数约束，得到相应的松弛问题,用单纯形法求解问题 ，得最优单纯形表,最优解为 ，不是整数,（2）引进以 所在行为来源行的割平面：,表3-2,选择割平面的经验规则：, 选择 的值大的；, 若 相等，则选择 小的,表3-2,最优解为 ，不是整数,（2）引进以 所在行为来源行的割平面：,表3-2,割平面不等式,加入松弛变量 ，得割平面方程,将割平面方程表达的约束条件加到单纯形表的最后一行，并把松弛变量补到最后一列,表3-3,表3-3,用对偶单纯形法求解，得最终单纯形表,表3-4,以 为来源行得割平面不等式：,引进松弛变量 ，得割平面方程,如前所述，修改单纯形表,表3-4,换基迭代，得,表3-5,表3-6,请练习：100页 习题三 第3题（用割平面法求解）,答案：,作业：用割平面法求解整数规划问题,且为整数,答案：,胡运权习题集 5.8(a),
