将 L0 分解为 L1 和 L2，其中： L1={L0, x2 7} L2={L0, x2 8}

2018/9/17
求解练习题
L1 求解单纯形表 cj 2 5 4 0 0 CB XB x1 x2 x3 x4 x7 4 x3 1/2 0 1 1 -1/2 5 x2 1/2 1 0 0 1/2 0 x6 3/2 0 0 -5 5/2 0 x7 0 1 0 0 0 σ 基变量系数向量单位化 cj 2 5 4 0 0 CB XB x1 x2 x3 x4 x7 4 x3 1/2 0 1 1 -1/2 5 x2 1/2 1 0 0 1/2 0 x6 3/2 0 0 -5 5/2 0 x7 -1/2 0 0 0 -1/2 -5/2 0 0 -4 -1/2 σ
……...
am1 x1+ am2 x2 +…+ amn xn (=,) bm x1~n 0 且取整数 纯整数规划: 所有变量都有取整约束 混合整数规划: 只有部分变量有取整约束
2018/9/17
分枝定界法
1.分枝定界法的基本思路 2.第65页例5-1
3.练习题
2018/9/17
分枝定界法的基本思路
2018/9/17
用割平面法解例
x2 +3/4 x3 +1/4 x4 =7/4 现将各系数分成整数和非负真分数两部分，从而可得： (1+0)x2+(0+3/4) x3+(0+1/4) x4 =(1+3/4) 将整数部分的变量移至等式右端有： 3/4 x3 +1/4 x4 =3/4+（1- x2 ） 非负整数解(1- x2)为整数，左端非负故有： 3/4 x3 +1/4 x4 =3/4+非负整数 从而： 3/4 x3 +1/4 x4 3/4 或 x2 1 以 x2 1为割平面可使可行域减少一个包括A点在内的三角形。 2018/9/17
2018/9/17
第65页例5-1
max z = 40x1 + 90x2 9x1 + 7x2 56 7x1 +20x2 70 x1，x2 0且取整

2018/9/17
用分枝定界法解例5-1
1.求解相应的线性规划L0 max z = 40x1 + 90x2 9x1 + 7x2 56 7x1 +20x2 70 x1，x2 0
利用连续的(线性规划)模型来求解非连续的(整数规划)问题。假设 xr 是一个有取整约束的变量而它的最优连续值 xr 是非整数，那么下列区间
[ xr ] xr [ xr ] 1 不可能包含任何整数解，这里[ xr ] 表示 xr 的取整值。因此，
xr 的可行整数值必然满足此二条件之一： xr [ xr ] 或 xr [ xr ] 1。
L2 ：max z = 40x1 + 90x2 9x1 + 7x2 56 7x1 +20x2 70 x1 5 x1，x2 0
2018/9/17
L1 ：X* = (4, 2.10), Z* = 349 L2 ：X* = (5, 1.57), Z* = 341
用分枝定界法解例5-1
2018/9/17
b 7/4 3/4 1
x2 x1 x5
x2 x1 x3
0 1 0 0
1 0 0 0
0 0 1 0
0 1/3 1/3 -1/3
1 -1/3 -4/3 -2/3
1 1 1 Z= 2
练习题 max z = 2x1 + 5x2 + 4x3 x1 + x2 + x3 12 x1 + 2x2 15 4x1 + 5x3 26 x1~3 0且取整
1.整数规划的数学模型 2.分枝定界法 3.割平面法 4.0-1型整数规划 5.指派问题
2018/9/17
整数规划的数学模型
max(min)(c1 x1+ c2 x2 +…+ cn xn ) a11 x1+ a12 x2 +…+ a1n xn (=,) b1 a21 x1+ a22 x2 +…+ a2n xn (=,) b2
L0
(4.81，1.82)
356
L1 (4，2.1) 349
L2 (5，1.57) 341
L3 (4，2) 340
L4
(1.42，3) 327
L5 (5.44，1) 308
L6 无可行解
2018/9/17
练习题
max z = 2x1 + 5x2 + 4x3 x1 + x2 + x3 12 x1 + 2x2 15 4x1 + 5x3 26 x1~3 0且取整
b 5 7 1 1
已得整数最优解 X* =（0，7，5） ，Z*=55 所以原整数规划的最优解为 X* =（0，7，5） 最优值为 Z* = 55
2018/9/17
4.分解L2形成L5、L6，其中： L5 = {L2, x21} L6 = {L2, x22} L5 : X* = (5.44, 1), Z* = 308 L6 : 无可行解 (1)舍弃L5、L6； (2)得最优解X* = (4, 2), Z* = 340。

2018/9/17
例5-1求解过程示意图
cj CB 4 5 0 σ XB x3 x2 x6 2 x1 1/2 1/2 3/2 -5/2 5 x2 0 1 0 0 4 x3 1 0 0 0 0 x4 1 0 -5 -4 0 x5 -1/2 1/2 5/2 -1/2 0 x6 0 0 1 0 b 9/2 15/2 7/2
2018/9/17

求解练习题

用割平面法解例
表 1（线性规划最终单纯形表） cj 1 1 0 0 CB XB x1 x2 x3 x4 1 1 σ x2 x1 0 1 0 1 0 0 3/4 -1/4 -1/2 1/4 1/4 -1/2
b 7/4 3/4 Z=5/2
非整数解，为建立割平面，首先考虑非整数解中余数最大 的基变量，此例中x1、 x2的余数均为3/4，不妨选取x2 ： x2 +3/4 x3 +1/4 x4 =7/4
线性规划 L2 无可行解 所以原整数规划的最优解为 X* =（0，7，5） 最优值为 Z* = 55
2018/9/17

求解练习题
L0 （0，15/2，9/2） 111/2
L1 （0，7，5）
L2
无可行解
55
2018/9/17
割平面法
1.割平面法的基本思路 2.例 3.练习题
2018/9/17
割平面法的基本思路
2018/9/17
求解练习题
首先求解线性规划L0 : max z = 2x1 + 5x2 + 4x3 x1 + x2 + x3 + x 4 = 12 x1 + 2x2 + x5 = 15 4x1 +5x3 + x6 = 26 x1~6 0
2018/9/17
求解练习题
线性规划 L0 的最终单纯形表
2018/9/17
用分枝定界法解例5-1
x2
5 4
9x1+7x2=56
3
2 1
7x1+20x2=70
1 2 3 4 5 6 7 8 9 10
0
x1
L0 : x* = (4.81, 1.82), Z* =356 2018/9/17
用分枝定界法解例5-1
2.将L0分解为L1和L2 L1 ：max z = 40x1 + 90x2 9x1 + 7x2 56 7x1 +20x2 70 x1 4 x1，x2 0
2018/9/17

分枝定界法的基本思路
把这两个约束条件分别加到原来的解空间上， 便产生了两个互斥的子问题。 这便是 分枝的含义。 由于分枝过程是通过增加约束条件来实现的， 因此每一问题的子问题都不 会有比其自身还大（目标函数求极大值）的最优目标值。当所有子问题的解均为非整数 可行解时， 应首先选择具有最大最优目标值的子问题来分枝； 当得到第一个整数可行解 时， 它的相应目标值可作为该整数规划最优值的下界， 舍掉所有最优值不大于该下界的 子问题。 按最优值的大小顺序对保留下来的子问题进行分枝， 如果出现具有更大目标值 的整数可行解，将下界更新为此整数可行解的目标值并进一步剪枝。从复这一过程，最 终保留下来的整数可行解即为整数规划的最优解。
同分枝定界法一样，割平面法也是一种利用连续模 型求解非连续问题的常用方法。割平面法的基本思 路是：当得到的解不满足取整约束时，就设法在问 题上增加一个约束条件，把包含这个非整数解的一 部分可行域从原来的可行域中割除，但不割掉任何 一个整数可行解。这个新增加的约束条件就称为割 平面。
2018/9/17
2018/9/17
0 x5 0 0 1 0 0 x5 0 0 1 0 0
0 x6 0 0 0 1 0 x6 0 0 0 1 0 b 9/2 15/2 7/2 -1/2 b 9/2 15/2 7/2 7

求解练习题
线性规划 L1 的最终单纯形表 cj 2 5 4 0 CB XB x1 4 x3 1 5 x2 0 0 x6 -1 0 x5 1 -2 σ L1 有整数最优解 0 0 0 b 5 7 1 1 x2 x3 x4 x5 x6 x7 0 1 1 0 0 -1 1 0 0 0 0 1 0 0 -5 0 1 5 0 0 0 1 0 -2 0 0 -4 0 0 -1 X* =（0，7，5） ，Z*=55
b 9/2 15/2 7/2 -1/2