运筹学难点辅导材料 整数规划补例
1、 对( IP) 整数规划问题12
12121212max 14951631..0,0,z x x x x x x s t x x x x =++≤⎧⎪
-+≤⎪⎨
≥≥⎪⎪⎩为整数, 问用先解相应的线性规划然后凑
整的办法能否求到最优整数解? 再用分支定界法求解。
解 先不考虑整数约束, 得到线性规划问题( 一般称为松弛问题LP)
12
12121
2max 14951..6310,0
z x x x x s t x x x x =++≤⎧⎪
-+≤⎨⎪≥≥⎩用图解法求出最优解12310
,23x x ==且296z =。
如用”舍入取整法”凑整可得到四个点, 即( 1, 3) 、
( 2, 3) 、 ( 1, 4) 、 ( 2, 4) 。
代入约束条件发现她们都不是可行解。
可将可行域内的所有整数点一一列举( 完全枚举法) , 本例中( 2, 2) 、 ( 3, 1) 点为最大值4z =。
令()
0310,23T
X
⎛⎫= ⎪⎝⎭
及最优值()0
296z =。
可行域记为D, 显然()0X 不是整数解。
定界: 取()0296z z ==
, 再用视察法找一个整数可行解()0,0T
X '=及0z '=, 取0z z '==, 即*2906
z ≤≤ 分支: ( 关键点, 在B 的最优解中任选一个不符合整数条件的变量j x , 其值为
j b , 构造两个约束条件1,j j j j x b x b ⎡⎤⎡⎤≥+≤⎣⎦⎣⎦, 这里用了取整函数呵! ) 任取最
优解中一个不为整数的变量值, 例如132x =
, 根据312⎡⎤
=⎢⎥⎣⎦
, 构造两个约束条件,
形成下面两个子问题( IP1) 12121211212max 14951631..10,0,z x x x x x x s t x x x x x =++≤⎧⎪-+≤⎪⎪≤⎨⎪≥≥⎪⎪⎩为整数和( IP2) 12
121221212max 14951631..20,0,z x x x x x x s t x x x x x =++≤⎧⎪-+≤⎪⎪≥⎨⎪≥≥⎪⎪⎩为整数 解( IP1) 和( IP2) , 得最优解分别为()
()11
7101,,33T
X z ⎛⎫==
⎪⎝⎭
和()
()22
23412,,99T
X
z ⎛⎫== ⎪⎝⎭
, 这两个都不是符合整数条件的可行解。
修改上下界: 根据个分支的最优解, 可取新的上界()(){}
1241
min ,9
z z z =
=, *4109
z ≤≤
再分支: 由于()()12z z <, 故先对( IP2) 进行分支, 取2239x =
, 根据2329⎡⎤
=⎢⎥⎣⎦
, 构造两个约束条件, 形成下面两个子问题( IP3) 12
121
2121212max 14951631
2
..2
0,0,z x x x x x x x s t x x x x x =++≤⎧⎪-+≤⎪⎪≥⎪⎨
≤⎪⎪≥≥⎪⎪⎩为整数和( IP4) 12
121
2121212max 14951
631
2..3
0,0,z x x x x x x x s t x x x x x =++≤⎧⎪-+≤⎪⎪≥⎪⎨
≥⎪⎪≥≥⎪⎪⎩为整数。
解相应的松弛问题( IP3) 和( IP4) , 得( IP4) 无可行解, ( IP3) 的最优解为
(
)
()33
3361,2,1414T
X z ⎛⎫== ⎪⎝⎭。
在考虑( IP1) , 由( IP1) 的最优解, 取273x =
, 根据723⎡⎤
=⎢⎥⎣⎦
, 构造两个约束条件, 形成下面两个子问题( IP5) 12
121
2121212max 14951
631
1..2
0,0,z x x x x x x x s t x x x x x =++≤⎧⎪-+≤⎪⎪≤⎪⎨
≤⎪⎪≥≥⎪⎪⎩为整数和( IP6) 12
121
2121212max 14951
631
1..3
0,0,z x x x x x x x s t x x x x x =++≤⎧⎪-+≤⎪⎪≤⎪⎨
≥⎪⎪≥≥⎪⎪⎩为整数, 得( IP6) 无可行解, ( IP5) 的最优解为()()()551,2,3T
X z ==。
在修改上下界: 根据上述两个最优解的情况, 有*61
314
z ≤≤ 再分支: 由( IP3) 的最优解()
333,214T
X
⎛⎫
= ⎪⎝⎭
, 取13314x =, 根据33214⎡⎤=⎢⎥⎣⎦, 构造
两个约束条件, 形成下面两个子问题( IP7) 12
1212121
1212max 149516312
..220,0,z x x x x x x x s t x x x x x x =++≤⎧⎪
-+≤⎪⎪≥⎪
≤⎨⎪≤⎪⎪≥≥⎪
⎩为整数
和( IP8)
121212121
1212max 149516312
..230,0,z x x x x x x x s t x x x x x x =++≤⎧⎪
-+≤⎪⎪≥⎪
≤⎨⎪≥⎪⎪≥≥⎪
⎩为整数
, 得( IP7) 的最优解为()()()772,2,4T
X z ==, ( IP8) 的最优解为
()()()883,1,4T
X z ==。
重新定界: 由于的最优解为()()78
,X X 为整数解, 且()()784z z ==, 故
()**3,1,4T
X z ==
2、 对整数规划问题12
12121212max 32231429..0,0,z x x x x x x s t x x x x =++≤⎧⎪
+≤⎪⎨
≥≥⎪⎪⎩为整数, 问用先解相应的线性规划然后凑整的办
法能否求到最优整数解?
解 用单纯形法解对应的LP 问题, 求到最优解1213559
,,max 424
x x z =
==
当凑为()()12,3,2T
T
x x =时, 为可行解, 13z =; 当凑为()()12,3,3T
T
x x =时, 为非可行解;
当凑为()()12,4,2T
T
x x =时, 为非可行解; 当凑为()()12,4,3T
T
x x =时, 为非可行解;
下面用分支定界法来解整数规划问题。
令594
z =, 显然()()12,0,0T T
x x =为可行解, 从而*5904
z ≤≤。
将原问题分解为下面两个子问题( 用222,3x x ≤≥分支, 复杂些, 不妨去试试! )
( IP1) 121212112max 32231429..30,0z x x x x x x s t x x x =++≤⎧⎪+≤⎪⎨≤⎪⎪≥≥⎩和( IP2) 12
1212112max 322314
29..40,0z x x x x x x s t x x x =++≤⎧⎪+≤⎪⎨
≥⎪⎪≥≥⎩
( IP1) 的最优解为
()
12343,3,,max 83T
T
x x z ⎛⎫
== ⎪⎝⎭
和( IP2) 的为()
()12,4,1,max 14T
T
x x z ==
因为4314,3z z ==, 因此*43
143
z ≤≤, 且*z 为整数, 则*1214,4,1z x x ===为最优解。
3、 用割平面法求解12
1212121212max 3323
5410..25,0,,z x x x x x x s t x x x x x x =--≤⎧⎪
+≥⎪⎨
+≤⎪⎪≥⎩为整数
解 引入松弛变量345,,x x x 和人工变量6x 及一个充分大的数0M >, 先解一个大
M 问题:
126
1231246
1251234567max 3323
5410
..25,,,,,,0z x x Mx x x x x x x x s t x x x x x x x x x x =---+=⎧⎪+-+=⎪⎨
++=⎪⎪≥⎩ 作初始单纯形表, 并进行迭代运算。