当前位置:
文档之家› 运筹学教材编写组《运筹学》课后习题-整数规划(圣才出品)
运筹学教材编写组《运筹学》课后习题-整数规划(圣才出品)
max z=3x1 + 2x2
2x1 + 3x2 + x3 = 14
s.t.
2x1x,1x+2 ,xx23
+ x4 = 9 , x4 0
x1, x2为整数
先不考虑上述模型中的整数约束,利用单纯形法进行求解,如表 6-2 所示:
表 6-2
此时的最优解为 X * = (13 / 4,5 / 2, 0, 0)T ,最优目标值 Z* = 59 / 4 。 对该最优解进行凑整,当凑整为 X (1) = (3, 2, 0, 0)T 时,为可行解,z=13;当凑整为 X (2) = (4,3, 0, 0)T , X (3) = (4, 2, 0, 0)T , X (4) = (3,3, 0, 0)T 时均为非可行解。
题:
B3: max z=3x1 + 2x2
2x1 + 3x2 14
s.t.
2 0
x1
+ x2 x1
3
9
0 x2 2
求得 B3 的最优解 x1 = 3, x2 = 2, z1 =13 z 。
B4: max z=3x1 + 2x2
2x1 + 3x2 14
于是得到 0 z* 44 / 3 ,再将 B1 分解成两个子问题:
B3: max z=3x1 + 2x2
2x1 + 3x2 14.5
s.t.
4 0
x1
+ x2 x1
3
16.5
0 x2 2
求得 B3 的最优解为 (3, 2,5 / 2,5 / 2, 0, 0)T ,max z3 =13。
圣才电子书 十万种考研考证电子书、题库视频学习平台
求得 B1 的最优解 x1 = 4, x2 =1, z1 =14 。
B2: max z=3x1 + 2x2 2x1 + 3x2 14
s.t.2x1x1+3x2 9 x1, x2 0
求得 B2 的最优解 x1 = 3, x2 = 8 / 3, z2 = 43/ 3 。 B1 已求得整数解,则可取 z = z1 =14 ,故14 z* 43 / 3 ,继续将 B2 分解为两个子问
B3 已求得整数解,则可取为 z = z3 =13 ,故13 z* 57 / 4 ,对于 B2 而言,继续分解
已无意义,可舍去。继续将 B4 分解为两个子问题:
B5 无可行解,舍去。
B5: max z=3x1 + 2x2
2x1 + 3x2 14.5
s.t.
04
x1
+ x2 x1
3
16.5
表 6-1
1 / 21
圣才电子书 十万种考研考证电子书、题库视频学习平台
此时的最优解为 X * = (7 / 2,5 / 2, 0, 0)T ,最优目标值 Z* = 31/ 2 。 对该最优解进行凑整,当凑整为 X (1) = (3, 2, 0, 0)T 时,为可行解, z =13 ;当凑整为 X (2) = (4,3, 0, 0)T , X (3) = (4, 2, 0, 0)T , X (4) = (3,3, 0, 0)T 时均为非可行解。
B4: max z=3x1 + 2x2
2 / 21
圣才电子书 十万种考研考证电子书、题库视频学习平台
2x1 + 3x2 14.5
s.t.
4 0
x1
+ x2 x1
3
16.5
x2 3
求得 B4 的最优解为 (11/ 4,3,0,5 / 2,1/ 4,0,0)T ,max z4 = 57 / 4 。
求得 B1的最优解 (3,17 / 6,0,5 / 3,0)T ,max z1 = 44 / 3 。
B2: max z=3x1 + 2x2
s.t.
2 4
x1 x1
+ +
3x2 14.5 x2 16.5
x1 4, x2 0
求得 B2 的最优解为 B2 (4,1/ 2,5, 0, 0)T ,max z2 =13。
x2 3
x1 3
B6: max z=3x1 + 2x2
2x1 + 3x2 14.5
s.t.
4 0
x1
+ x2 x1
2
16.5
x2 3
求得 B6 的最优解 (2, 7 / 2, 0,5, 0,1/ 2, 0)T , z6 =13。
所以,得到最优解 x1 = 3, x2 = 2,与用舍去法得到的最优解一致。所以,用先解相应的
圣才电子书
十万种考研考证电子书、题库视频学习平台
第 6 章 整数规划
6.1 对下列整数规划问题,问用先解相应的线性规划然后凑整的办法能否得到最优整
数解?
(1) max z=3x1 + 2x2
2x1 + 3x2 14.5
s.t.
4x1 + x1, x2
x2 0
16.5
用分支定界法进一步求解此整数规划。
记 z = 59 / 4 ,因为 X = (0, 0, 0, 0)T 为可行解,所以 0 z* 59 / 4 。将原问题分解为两
个子问题:
B1: max z=3x1 + 2x2 2x1 + 3x2 14
s.t.2x2x1+4x2 9 x1, x2 0
4 / 21
x1, x2为整数
解:在该线性规划问题的约束条件中分别加入松弛变43; 2x2
2x1 + 3x2 + x3 = 14.5
s.t.
4x1x,1x+2 ,xx23
+ x4 = 16.5 , x4 0
x1, x2为整数
先不考虑上述模型中的整数约束,利用单纯形法进行求解,如表 6-1 所示:
用分支定界法进一步求解此整数规划。
记 z = 31/ 2 ,因为 X = (0, 0, 0, 0)T 为可行解,所以 0 z* 31/ 2 。将原问题分解为两
个子问题:
B1: max z=3x1 + 2x2
s.t.
42xx11
+ +
3x2 14.5 x2 16.5
0 x1 3, x2 0
线性规划然后凑整的办法能得到最优整数解。
(2) max z=3x1 + 2x2
2x1 + 3x2 14
s.t.
2x1x,1x+2
x2 0
9
x1, x2为整数
3 / 21
圣才电子书 十万种考研考证电子书、题库视频学习平台
解:在该线性规划问题的约束条件中分别加入松弛变量 x3, x4 ,并化为标准型