当前位置:
文档之家› 例1用分枝定界法求解下面的整数规划
例1用分枝定界法求解下面的整数规划
cj
3
2
1
0
0
0
0
CB
XB
b
x1
x2
x3
x4
x5
x6
x7
2
1
3
0
x2
x3
x1
x7
11/3
4/3
5
3
0
0
1
0
1
0
0
1
0
1
0
0
1/3
-1/12
1/2
0
1/3
1/6
0
0
1/3
5/12
1/2
0
0
0
0
1
cj-zj
0
0
0
-25/12
-5/6
-31/12
0
2
1
3
0
x2
x3
x1
x7
11/3
4/3
5
-2/3
0
0
1
0
1
例1用分枝定界法求解下面的整数规划:
已知其放松的线性规划的最优单纯形表:
cj
3
2
1
0
0
0
CB
XB
b
x1
x2
x3
x4
x5
x6
2
1
3
x2
x3
x1
11/3
4/3
5
0
0
1
1
0
0
0
1
0
1/3
-1/12
1/2
1/3
1/6
0
1/3
5/12
1/2
cj-zj
0
0
0
-25/12
-5/6
-31/12
解:由线性规划的最优单纯形表知其最优解为x1=5,x2=11/3,x3=4/3非整数解,最优值z0=71/3, x1=0,x2=0,x3=0为一整数可行解,目标函数值为z=0,定界 。分枝 ,相应的问题设为 ,解 如下表:
0
0
0
0
1
0
0
1/3
-1/12
1/2
-1/3
1/3
1/6
0
-1/3
1/3
5/12
1/2
-1/3
0
0
0Байду номын сангаас
1
cj-zj
0
0
0
-25/12
-5/6
-31/12
0
2
1
3
0
x2
x3
x1
x5
3
1
5
2
0
0
1
0
1
0
0
0
0
1
0
0
0
-1/4
1/2
1
0
0
0
1
0
1/4
1/2
1
1
1/2
0
-3
cj-zj
0
0
0
-5/4
0
-7/4
-5/2
得到一个整数最优解x1=5,x2=3,x3=1,最优值为22,因该最优解是满足整数条件,所以该整数规划的下界z=22。
同理求解另一个线性规划问题(要写出求解的单纯形表) ,因无可行解,因此该整数规划的上界也为22,所以整数规划的最优值为22,上面的这个解即为最优解。