四整数线性规划.pptVIP

整数线性规划类型 纯整数规划 混合整数规划 0-1整数规划 例1 max ? = 3x1 -x2 s.t. x1 + 2x2 ≥1 x1 - 2x2≤ 2 x1 + x2 ≤ 3 x1，x2为非负整数 * * 线性规划中有一项假设，是决策变量是连续的，且不必为整数。如果某个问题符合线性规划连续性及其他假设，但决策变量却必须是整数，则成为整数线性规划(ILP)。 其一般形式是： min ?= cTx = c1x1 + c2x2 + … + cnxn （1） s.t. A x = b （2） x ≥0， （3） x的分量为整数 （4） 其中x ，c为n维列向量，b为m维列向量，A为m×n矩阵。 第四章 整数线性规划 基本思想：先不考虑整数性要求，用单纯形法求出所给问题的最优解，若每个变量恰好为整数，则问题已解决；否则就设法把这个最优的极点，连同它的一个邻域，从可行解集合中“切除” 。对可行解剩下部分重复上述步骤，范围逐步缩小，直到找到最优解。这将通过一个附加的约束条件（割平面）来实现，故称为割平面法。 §1 割平面法 设上面规划问题中（1）—（3）式所得结果为 （5） 解 先不考虑整数性要求，引入松弛变量x3，x4，x5，用单纯型法求出所给问题的最优解。 x4 x5 x1 x2 x3 8/3 1/3 7/3 1/3 2/3 -1/3 1/3 -1/3 4/3 1 0 0 0 1 0 0 0 1 x1 x2 x3 23/3 4/3 5/3 0 0 0 最优解(8/3,1/3)T作为第一次逼近，它不是整数解，取相应的方程： x1 + x4/3 + 2x5/3 = 8/3 作为诱导方程，从而得到割平面方程： y1 - x4/3 - 2x5/3 = -2/3 两式相加，得：x1 + y1 =2，由于y1≥0，所以x1≤2。可见它“切除”了极点(8/3,1/3)T。 x4 x5 x1 x2 x3 y1 8/3 1/3 7/3 -2/3 1/3 2/3 -1/3 1/3 -1/3 4/3 -1/3 -2/3 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 x1 x2 x3 y1 23/3 4/3 5/3 0 0 0 0 将割平面加入表中： x4 y1 x1 x2 x3 x5 2 0 1 1 0 1 -1/2 1/2 -1 2 1/2 -3/2 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 x1 x2 x3 x5 6 1/2 5/2 0 0 0 0 于是已得整数值的最优解(2,0)T . 对应的目标值为zmax=6. §2 分枝定界法 分枝定界法可用于解纯整数或混合的整数规划问题; 在二十世纪六十年代初由Land Doig和Dakin等人提出; 由于这方法灵活且便于用计算机求解，所以现在它已是解整数