2。2 Gomory割平面法

2。2。1 Gomory割平面法的基本思想

以纯整数模型为例:

以为整数向量这个约束,则可得:

为的松弛问题,记为问题。的可行域是一个多面凸集。这两个问题之间具有如下明显的关系:

 ;

 若无可行解,则无可行解;

 的最优值是的最优值的一个下届;

令松弛LP问题的最优值为,Gomory割平面法首先要求,若（表示整数集）,则停止计算,若,则找到恰当的约束条件,再次添加到松弛问题中,继续计算,直至,则结果最优。

2。2。2 Gomory割平面法的计算步骤文献综述

Step 1  首先使用单纯形法来解决整数规划的松弛LP问题。若没有最优解,计算停止,且也没有最优解。若有最优解,假若是整数向量,则为的最优解,计算停止,输出;否则转Step 2。

Step 2  设割平面方程为:

Step 3  将割平面方程加到第1步所得单纯形表中,然后再用对偶单纯形表求解最新得到的松弛问题。若其最优解为整数解,记为,则是问题的最优解,输出这个最优解;反之,则将这个最优解重新记为,再次返回Step 2。若经计算发现该问题是无界的,则原整数线性规划是不可行的,停止计算[1]。

2。3分枝定界法

2。3。1分枝定界法的基本思想

如下为整数线性规划问题:

为整数矩阵,为整数向量。若的某个分量不满足整数要求,则最优解的第个分量定在区域或中,因此被分解为两个子问题。这两个子问题分别为:

和对于和而言,仍是求解其相应的松弛LP问题。假如是的解,且,则的最优值为,不需要再进行计算;若是的解,但,则找出其不属于的分量,按或,将分解分解为和,分法如,如此继续下去。

分枝定界法首先要求出其松弛LP问题的最优解,若该最优解不属于,则将该问题分解为两个子问题,继续求解,一直持续下去,直至结果。

2。3。2分枝定界法计算步骤来自~吹冰、论文|网www.chuibin.com +QQ752018766-

Step 1  假设活点集合:（注:“”为原问题,“”代表子问题,）,,当前最好的整数解:;

Step 2  加入活点集合,则转向Step 7,不然,选取一个分枝点集合点,从集合的活点中去掉;

Step 3  解点对应的松弛LP问题,若此LP问题无解,转回Step 2;

Step 4  若点的最优值,则点被剔除,返回到Step 2;

Step 5  若点的最优解,则: