05 整数规划.ppt

文档介绍：


-1型整数规划

第五章整数规划
2017/11/10
整数规划的数学模型
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 且取整数
纯整数规划: 所有变量都有取整约束
混合整数规划: 只有部分变量有取整约束
2017/11/10
分枝定界法

-1

2017/11/10
分枝定界法的基本思路

2017/11/10
分枝定界法的基本思路
2017/11/10
第65页例5-1
Max z = 40x1 + 90x2
9x1 + 7x2  56
7x1 +20x2  70
x1,x2  0且取整

2017/11/10
用分枝定界法解例5-1

Max z = 40x1 + 90x2
9x1 + 7x2  56
7x1 +20x2  70
x1,x2  0

2017/11/10
用分枝定界法解例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* = (, ), Z* =356

2017/11/10
用分枝定界法解例5-1

L1 :
Max z = 40x1 + 90x2
9x1 + 7x2  56
7x1 +20x2  70
x1  4
x1,x2  0
L1 :X* = (4, ), Z* = 349
L2 :X* = (5, ), Z* = 341

L2 :
Max z = 40x1 + 90x2
9x1 + 7x2  56
7x1 +20x2  70
x1  5
x1,x2  0
2017/11/10
用分枝定界法解例5-1
、L4,其中:
L3 = {L1, x22}
L4 = {L1, x23}
L3 : X* = (4, 2), Z* = 340
L4 : X* = (, 3), Z* = 327
(1)取下界min=340(L3);
(2)舍弃L4

2017/11/10