割平面法的几何特征及应用
记纯整数规划(AIP)的可行域为KAIP.若将(AIP)中要求变量为整数这个约束去掉,则得到相应的线性规划(LP),记(LP)的可行域为KLP.割平面法实质上仍然是用解线性规划的方法来求解整数规划问题.其基本思想是:我们对(LP)求解.若(LP)的最优解X*是一个整数解(整数向量),那么X*当然是(AIP)的最优解;若X*不是整数解,我们设法对原线性规划(LP)增加一个线性约束条件(称它为割平面)
理论教育
2023-11-18