割平面法 运筹学整数规划.ppt

第一节问题的提出例子 某厂拟采用集装箱托运甲乙两种货物 每箱的体积 重量 可获利润以及托运所受限制如下表 问两种货物托运多少箱 可使获得利润为最大 第三章整数规划 IntegerProgramming 分类 1 纯整数线性规划 PureIntegerLinearProgramming 2 混合整数线性规划 MixedIntegerLinearProgramming 3 0 1型整数线性规划 Zero OneIntegerLinearProgramming 分配问题与匈牙利法 21 分配问题与匈牙利法 48 21 答案 解 设x1 x2分别表示两种货物托运的箱数 那么其线性规划为 可得最优解为x 5 3 8 3 T 如果选用 向上凑整 的方法可得到x 1 2 3 T 则此时已破坏了体积约束 超出可行域的范围 如果 舍去小数 可得x 2 1 2 T 则此时虽是可行解 值为10 不是最优解 因为当x 2 2 T是 其利润为14 由于托运的箱数不能为分数 故上述规划问题是整数规划问题 若不考虑整数约束 其相应的线性规划问题为 第二节分枝定界法 BranchandBoundmethod 引言 穷举法对小规模的问题可以 大规模问题则不行 一 基本思想和算法依据基本思想是 先求出相应的线性规划最优解 若此解不符合整数条件 那么其目标函数的值就是整数规划问题最优值的上界 而任意满足整数条件的可行解的目标函数值将是其下界 定界 然后将相应的线性规划问题进行分枝 分别求解后续的分枝问题 如果后续分枝问题的最优值小于上述下界 则剪掉此枝 如果后续某一分枝问题的最优解满足整数条件 且其最优值大于上述下界 则用其取代上述下界 继续考虑其它分枝 直到最终求得最优的整数解 算法的依据在于 整数规划的最优解不会优于相应的线性规划问题的最优解 具体说就是 对极大化问题 与整数规划问题相应的线性规划问题的目标函数值 是该整数规划问题目标函数的上界 任何满足整数条件的可行解的目标函数值将是其下界 二 具体步骤 以例子说明 解 第一步 先不考虑整数约束条件 求解相应的线性规划问题 得最优解和最优值如下x1 4 81 x2 1 82 Z 356此解不满足整数解条件 定出整数规划问题目标函数的上下界 上界为Z 356 用观察法可知x1 0 x2 0是可行解 从而其整数规划问题目标函数的下界应为0 即0 Z 356 第二步 分枝与定界过程 将其中一个非整数变量的解 比如x1 进行分枝 即x1 4 81 4 x1 4 81 5并分别加入LP问题的约束条件中 得两个子LP规划问题LP 1 LP 2 分别求解此两个子线性规划问题 其最优解分别是LP 1 x1 4 x2 2 1 Z1 349LP 2 x1 5 x2 1 57 Z2 341 没有得到全部决策变量均是整数的解 再次定出上下界0 Z 349继续对问题LP 1 LP 2进行分枝 先对目标函数值大的子问题进行分枝 即分别将x2 2 1 2 x2 2 1 3加入到约束条件中去 得子问题LP 3 LP 4 分别求解得LP 3 x1 4 x2 2 Z3 340 是整数解 定下界 LP 4 x1 1 42 x2 3 Z4 327 剪掉 问题LP 3的所有解均是整数解 而问题LP 4还有非整数解 但由于Z3 Z4 对LP 4分枝已没有必要 剪掉 上下界为340 Z 349在对问题LP 2进行分枝 x2 1 57 1 x2 1 57 2 得子问题LP 5 LP 6 求解得LP 5 x1 5 44 x2 1 Z5 308 下界340 剪掉 LP 6 无可行解 剪掉 于是得到原整数规划问题的最优解为LP x1 4 x2 2 Z3 340 整个过程如下 步骤 1求解相应的线性规划问题的最优解和最优值 如果a 没有可行解 停止 b 若有满足整数条件的最优解 则已得到整数规划问题的最优解 停止 c 若有最优解 但不满足整数条件 记此最优值为原整数规划问题Z 的上界 然后 用观察法求出下界 2分枝 定界 直到得到最优解为止 注意 a 在以后的各枝中 若某一子规划问题的最优解满足整数条件 则用其最优值置换Z 的下界 B 若某一分枝的最优值小于Z 的下界 则剪掉此枝 即以后不再考虑此枝 三 算法需要注意的几点 以极大化问题为例 1在计算过程中 若已得到一个整数可行解x 0 其相应的目标函数值为Z0 那么在计算其它分枝过程中 如果解某一线性规划所得的目标函数值Z Z0 即可停止计算 因为进一步的分枝结果的最优值只能比Z更差 2分枝变量的选取 分枝变量的选取方式不同 可使整个问题的求解在简繁程度上有很大的差异 选取原则为 选取相应的线性规划解中具有最大分数值的变量作为分枝变量 对要求取整的变量按其重要程度 比如该变量在整数规划模型中代表比较重要的决策 该变量在目标函数中利润系数远远大于其它变量的利润系数等等 排定优先顺序 按优先顺序的先后选取分枝变量 3若有若干个待求解的分枝 先选取目标函数值最大的那一枝 练习 用分支定界法求解下述整数规划问题 第三节割平面解法 CuttingPlaneApproach 割平面法是1958年美国学者R E Gomory提出的 基本思想是 先不考虑变量的取整数约束 求解相应的线性规划 然后不断增加线性约束条件 即割平面 将原可行域割掉不含整数可行解的一部分 最终得到一个具有整数坐标顶点的可行域 而该顶点恰好是原整数规划问题的最优解 例 求解 加松弛变量x3 x4 使其变成标准形 如有非整数的系数 则将其所在的方程乘以某一常数 变成具有整数系数的约束方程 用单纯形法求解得 最优解x1 3 4 x2 7 4 x3 x4 0 最优值为Z 5 2 是非整数解 寻求割平面 由最终表得x1 1 4x3 1 4x4 3 4x2 3 4x3 1 4x4 7 4任选一取分数值的基变量 比如x1 将该式中所有变量的系数 右端常数项均改写成整数与非负真分数之和的形式 并移项得x1 x3 3 4 3 4x3 1 4x4 注 所有的x均是整数 x3 x4可通过在原约束条件中乘以某一常数变成整数 则整数约束条件可由下式替代3 4 3 4x3 1 4x4 0即得割平面方程 3x3 x4 3引入松弛变量x5 将其加入到原规划的约束条件中 利用上述最终表得 用对偶单纯形算法进行计算 x5作换出变量 x3换入变量 迭代得 已得到整数解 最优解为x1 1 x2 1 最优值为2 注 新约束 3x3 x4 3的几何意义 上述约束中以x1 x2表示x3 x4 得x2 1 其图形见下图 3x1 x2 4 x1 x2 1 x2 1 求切平面的基本步骤 1令xi是相应线性规划问题最优解中为分数解的一个基变量 由单纯形最终表得到xi aikxk bi 其中i为基变量的标号 k为非基变量的标号 2将bi和aik都分解成整数部分N与非负真分数部分f之和 即bi Ni fi 其中0 fi 1aik Nik fik 其中0 fik 1 将上式代入式xi aikxk bi中得xi Nikxk Ni