1、2018/10/13 1.整数规划的数学模型 2.分枝定界法 3.割平面法 4.0-1型整数规划 5.指派问题 2018/10/13 整数规划的数学模型 max(min)(c1 x1+ c2 x2 + cn xn ) a11 x1+ a12 x2 + a 1n xn (=,) b1 a21 x1+ a22 x2 + a 2n xn (=,) b2 . am1 x1+ am2 x2 + a mn xn (=,) bm x1n 0 且取整数 纯整数规划 : 所有变量都有取整约束 混合 整数规划 : 只有部分变量有取整约束 2018/10/13 分枝定界法 1.分枝定界法的基本思路 2.第 65页例
2、 5-1 3.练习题 2018/10/13 分枝定界法的基本思路 利用连续的 ( 线性规划 ) 模型来求解非连续的 ( 整数规划 ) 问题。假设rx是一个有取整约束的变量而它的最优连续值rx是非整数，那么下列区间1 rrr xxx不可能包含任何整数解，这里 rx表示rx的取整值。因此，rx的可行整数值必然满足此二条件之一： rr xx或1 rr xx。 2018/10/13 把这两个约束条件分别加到原来的解空间上，便产生了两个互斥的子问题。这便是分枝的含义。由于分枝过程是通过增加约束条件来实现的，因此每一问题的子问题都不会有比其自身还大（目标函数求极大值）的最优目标值。当所有子问题的解均为非整
3、数可行解时，应首先选择具有最大最优目标值的子问题来分枝；当得到第一个整数可行解时，它的相应目标值可作为该整数规划最优值的下界，舍掉所有最优值不大于该下界的子问题。按最优值的大小顺序对保留下来的子问题进行分枝，如果出现具有更大目标值的整数可行解，将下界更新为此整数可行解的目标值并进一步剪枝。 从复这一过程，最终保留下来的整数可行解即为整数规划的最优解。 分枝定界法的基本思路 2018/10/13 第 65页例 5-1 max z = 40x1 + 90x2 9x1 + 7x2 56 7x1 +20x2 70 x1， x2 0且取整 2018/10/13 用分枝定界法解例 5-1 1.求解相应的线
4、性规划 L0 max z = 40x1 + 90x2 9x1 + 7x2 56 7x1 +20x2 70 x1， x2 0 2018/10/13 用分枝定界法解例 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 2018/10/13 用分枝定界法解例 5-1 2.将 L0分解为 L1和 L2 L1 ： max z = 40x1 + 90x2 9x1 + 7x2 56 7x1 +20x2 70 x1 4 x1， x2 0 L2 ： max z = 40x1 + 90x2 9x1 + 7x2 56 7x1 +20x2 70 x1 5 x1， x2 0 L1 ： X* = (4, 2.10), Z* = 349 L2 ： X* = (5, 1.57), Z* = 341 2018/10/13 用分枝定界法解例 5-1 3.分解 L1形成 L3、 L4， 其中： L3 = L1, x22 L4 = L1, x23 L3 : X* = (4, 2), Z* = 340 L4 : X* = (1.42, 3), Z* = 327 (1)取下界 min=340(L3); (2)舍弃 L4
