分支定界法:把全部可行解空间进行恰当地进行系统搜索,这就是分支定界法的基本内容。我们通常把全部可行解空间反复分割为越来越小的子集,这就称为分支;并对每个子集内的解集计算出一个目标下界(针对最小值问题),这称为定界。在每次分支后,凡是界限超过已知可行解集目标值的那些子集不再进行分支,这称为剪枝。
要求x1,x2均为整数求下列的整数规划
我们先不进行考虑X1,X2为整数的约束,解出相应的线性规划B,代码如下:
c=[40;90];
A=[9,7;7,20];
b=[56;70];
x=linprog(-c,A,b,[],[],zeros(2,1));
value=c'*x;
解出来的结果为:
明显可以发现它不满足整数条件,这个时候z是最优目标函数的z*的一个上界,然后又容易发现(0,0)是满足目标函数。所以一个下界的值为0。所以不难得到0<=z*<=356。
我们选择X1进行分支,把可行集分为两个部分X1>=5和X1<=4。
问题B1变成:
c=[40;90];
A=[9,7;7,20];
b=[56;70];
lb=[0;0];
ub=4;
x=linprog(-c,A,b,[],[],lb,ub);
value=c'*x;
得到结果和最佳解:
问题B2变成:
c=[40;90];
A=[9,7;7,20];
b=[56;70];
lb=[5;0];
x=linprog(-c,A,b,[],[],lb);
value=c'*x;
得到结果和最优解:
再定界:0<=z*<=349
对问题B1进行分支得到问题B11和B12,它的约束条件和目标函数分别为:
分别求出最优解:
再对问题B21,B22分别进行分析:
不难得到B21,B22都需要被剪枝。
所以答案为X1=4,X2=2,目标函数的最大值为340。
不难发现:分支定界法就是重复进行定界,分枝和剪枝的过程。最后得到一个满足条件的最优解。