第四章(整数规划).pptVIP

* 本章学习要求 熟悉分支定界法和割平面法的原理及其应用 掌握求解0-1规划问题的隐枚举法 掌握求解指派问题的匈牙利法 * 5.1整数规划的数学模型及解的特点 整数规划的类型 整数规划的数学模型实例 整数规划解的特点 * 1.整数线性规划（ILP）的类型 要求一部分或全部决策变量必须取整数值的规划问题称为整数规划（integer programming，简记ILP）。 纯ILP： Xj全为整数 混合ILP：部分Xj为整数 0-1 ILP：Xj为0或1 * 线性规划模型 max z=x1+4x2 s.t. 14x1+42x2≤196 -x1+ 2x2≤ 5 x1, x2≥0 整数规划模型 max z=x1+4x2 s.t. 14x1+42x2≤196 -x1+ 2x2≤ 5 x1, x2≥0 x1,x2 为整数 0 1 2 3 4 5 6 7 8 4 3 2 1 A(2.6, 3.8) B(5, 3) 2.整数线性规划（ILP）实例 * 线性规划的最优解A(x1, x2)=(2.6, 3.8)不是整数解，目标函数值为z=17.8。整数规划的最优解B(x1, x2)=(5,3)目标函数值为z=17。线性规划最优解A(2.6, 3.8)四舍五入得到的解为(3,4)，不是可行解；舍去尾数取整的解为(2,3)，目标函数值z=14。 因此整数规划的最优解一般不能由线性规划的最优解通过简单的取整得到。 0 1 2 3 4 5 6 7 8 4 3 2 1 A(2.6, 3.8) B(5, 3) * 3.整数线性规划（ILP）解的特点 ILP是其中LP的一个子问题，所有解也是LP的可行解，所以如果LP的最优解满足ILP的整数条件，则已得最优解。 * 5.2 割平面法和分支定界法 割平面法（Gomory法） 分支定界法 * 1.割平面法 基本原理： 根据单纯形法求得其松弛问题的最优解，若不满足整数条件，则由最优解中选取具有最大真分数部分的非整分量所在行构造割平面约束，将其加入原松弛问题中形成一个新的线性规划求解，逐渐缩小解的范围，又不去掉整数解，直至找到最优解为整数解结束。 * 1.割平面法 割平面束构造： 设具有最大真分数部分的非整分量所在行为： 将该约束方程所含系数和常数分解为整数N和正真分数f之和，即： 则该约束方程等价于： * 1.割平面法 例： Cj 1 1 0 0 CB XB b x1 x2 x3 x4 Θ 0 x3 6 2 1 1 0 0 x4 20 4 5 0 1 δj 1 1 0 0 [ ] [ ] 3 5 x1入 x3出 1 x1 3 1 1/2 1/2 0 0 x4 8 0 3 -2 1 δj 0 1/2 -1/2 0 [ ] [ ] 6 8/3 x2入 x4出 1 x2 8/3 0 1 -2/3 1/3 1 x1 5/3 1 0 5/6 -1/6 δj 0 0 -1/6 -1/6 由右边结果构造割平面束 * 例（接上）： 由上面结果构造割平面束 cj 1 1 0 0 0 CB XB b x1 x2 x3 x4 x5 1 X1 5/3 1 0 5/6 -1/6 0 1 X2 8/3 0 1 -2/3 1/3 0 0 x5 -2/3 0 0 -5/6 -5/6 1 δj 0 0 -1/6 -1/6 0 θ - - 1/5 1/5 - 1 X1 1 1 0 0 -1 1 1 X2 16/5 0 1 0 1 -4/5 0 x3 4/5 0 0 1 1 -6/5 δj 0 0 0 0 -1/5 cj 1 1 0 0 0 0 CB XB b x1 x2 x3 x4 x5 x6 1 X1 1 1 0 0 -1 1 0 1 X2 16/5 0 1 0 1 -4/5 0 0 x3 4/5 0 0 1 1 -6/5 0 0 x6 -4/5 0 0 0 0 -4/5 1 δj 0 0 0 0 -1/5 0 1 X1 0 1 0 0 -1 0 5/4 1 X2 4 0 1 0 1 0 -1 0 X3 2 0 0 1 1 0 -3/2 0 x5 1 0 0 0 0 1 -5/4 δj 0 0 0 0 0 -1/4 * 首先，不考虑变量的整数约束，求解松弛问题线性规划的最优解。如果线性规划的最优解恰好是整数解，则这个解就是整数规划的最优解。 如果线性规划的最优解中至少有一个变量不是整数，把线性规划的可行域切割成两部分，分别求解两个线性规划的最优解。 如果这两个线性规划的最优解还不是整数解，分别把每一个可行域再进行分割。这个过程，