中矿大 运筹学复习.ppt

单纯形法计算框图 已知五人分别完成五项工作耗费如下表，求最优分 配方案。 解：1）变换系数矩阵，增加0元素 重点： 掌握一般整数规划问题概念及模型结构； 2. 掌握整数规划的求解方法：分枝定界法，割平面法，匈牙利法。 第五章 整数规划 利用割平面的思想求解下面的规划问题 例5 割平面法 解：将约束条件的系数化整；去掉“x1, x2是整数”的条件，得到一个线性规划的标准型（LP1）为： 利用单纯形法求解这个线性规划问题，得出最终单纯形表： 0 0 -1/4 -5/4 σj 0 1 1/2 -1/2 1 0 -1/4 3/4 2.5 3.25 x2 x1 x1 x2 x3 x4 3 2 0 0 割平面法 最优解不是整数解，由最终表得到变量之间的关系： 0 0 -1/4 -5/4 σj 0 1 1/2 -1/2 1 0 -1/4 3/4 2.5 3.25 x2 x1 x1 x2 x3 x4 3 2 0 0 将上面的约束条件当中的变量和系数改写成整数与非负真分数的和 把整数部分放在左边，非整数部分放在右边。 割平面法 下面增加割平面，选真分数最大的一个 由于上式左端是整数，因此右端也应是整数，由于变量都是不小于0的整数，所以上式右端必是一个不大于0.5 的整数，即 称这个不等式为一个割平面。 割平面法 引入一个松弛变量，化割平面为： 将它作为一个新增加的约束条件加入线性规划LP1中得到一个新的线性规划LP2 ； 或者直接反映到LP1的最终单纯形表中，得LP2单纯形表： 割平面的处理： 割平面法 LP2 的单纯形表： 0 0 -1/4 -5/4 0 0 1 1/2 -1/2 0 1 0 -1/4 3/4 0 0 0 [-1/2] -1/2 1 5/2 13/4 -1/2 x2 x1 x5 x1 x2 x3 x4 x5 3 2 0 0 0 0 0 -1/4 -5/4 σj 0 1 1/2 -1/2 1 0 -1/4 3/4 2.5 3.25 x2 x1 x1 x2 x3 x4 3 2 0 0 LP1 ： LP2 ： 割平面法 0 0 0 -1 -1/2 σj 0 1 0 -1 1 1 0 0 1 -1/2 0 0 1 1 -2 2 7/2 1 x2 x1 x3 0 0 -1/4 -5/4 0 σj x1 x2 x3 x4 x5 3 2 0 0 0 由于不是整数解，找出不满足条件的基变量 x1. 用对偶单纯型法求解： 割平面法 将它作为一个新增加的约束加到线性规划LP2中又得一个线性规划LP3∶ 构造线性规划LP2的割平面 割平面法 LP3 ： LP3的单纯形表： 0 0 0 -1 0