分枝定界法3.平面法4.0-1型整数规划5.指派问题.ppt

1.整数规划的数学模型 2.分枝定界法 3.割平面法 4.0-1型整数规划 5.指派问题 整数规划的数学模型 max(min)(c1 x1+ c2 x2 +…+ cn xn ) a11 x1+ a12 x2 +…+ a1n xn ? (=,?) b1 a21 x1+ a22 x2 +…+ a2n xn ? (=,?) b2 ……... am1 x1+ am2 x2 +…+ amn xn ? (=,?) bm x1~n ? 0 且取整数 纯整数规划: 所有变量都有取整约束 混合整数规划: 只有部分变量有取整约束 分枝定界法 1.分枝定界法的基本思路 2.第65页例5-1 3.练习题 分枝定界法的基本思路 ? 分枝定界法的基本思路 第65页例5-1 max z = 40x1 + 90x2 9x1 + 7x2 ? 56 7x1 +20x2 ? 70 x1，x2 ? 0且取整 ? 用分枝定界法解例5-1 1.求解相应的线性规划L0 max z = 40x1 + 90x2 9x1 + 7x2 ? 56 7x1 +20x2 ? 70 x1，x2 ? 0 用分枝定界法解例5-1 x2 5 9x1+7x2=56 4 3 2 7x1+20x2=70 1 0 1 2 3 4 5 6 7 8 9 10 x1 L0 : x* = (4.81, 1.82), Z* =356 ? 用分枝定界法解例5-1 2.将L0分解为L1和L2 L1 ：max z = 40x1 + 90x2 9x1 + 7x2 ? 56 7x1 +20x2 ? 70 x1 ? 4 x1，x2 ? 0 用分枝定界法解例5-1 3.分解L1形成L3、L4，其中： L3 = {L1, x2?2} L4 = {L1, x2?3} L3 : X* = (4, 2), Z* = 340 L4 : X* = (1.42, 3), Z* = 327 (1)取下界min=340(L3); (2)舍弃L4 用分枝定界法解例5-1 4.分解L2形成L5、L6，其中： L5 = {L2, x2?1} L6 = {L2, x2?2} L5 : X* = (5.44, 1), Z* = 308 L6 : 无可行解 (1)舍弃L5、L6； (2)得最优解X* = (4, 2), Z* = 340。 ? 例5-1求解过程示意图 练习题 max z = 2x1 + 5x2 + 4x3 x1 + x2 + x3 ? 12 x1 + 2x2 ? 15 4x1 + 5x3 ? 26 x1~3 ? 0且取整 求解练习题 首先求解线性规划L0 : max z = 2x1 + 5x2 + 4x3 x1 + x2 + x3 + x 4 = 12 x1 + 2x2 + x5 = 15 4x1 +5x3 + x6 = 26 x1~6 ? 0 求解练习题 ? 求解练习题 ? 求解练习题 ? 求解练习题 ? 求解练习题 割平面法 1.割平面法的基本思路 2.例 3.练习题 割平面法的基本思路 同分枝定界法一样，割平面法也是一种利用连续模型求解非连续问题的常用方法。割平面法的基本思路是：当得到的解不满足取整约束时，就设法在问题上增加一个约束条件，把包含这个非整数解的一部分可行域从原来的可行域中割除，但不割掉任何一个整数可行解。这个新增加的约束条件就称为割平面。 例 max z = x1 + x2 - x1 + x2 ? 1 3x1 + x2 ? 4 x1，x2 ? 0且取整 ? 用割平面法解例 1.求解相应的线性规划L0 max z = x1 + x2 - x1 + x2 ? 1 3x1 + x2 ? 4 x1，x2 ? 0 ? 用割平面法解例 非整数解，为建立割平面，首先考虑非整