整数规划定义分类纯(完全)整数规划混合整数规划全整数规划0-1整数规划特点一般形式与线性规划关系定义数学规划中的变量(部分或全部)限制为整数分类纯(完全)整数规划所有决策变量要求取非负整数(这时引进的松弛变量和剩余变量可以不要求取整数)松弛变量例x 1 x 2 ≤ 10 可引进 x 3 , 使 x 1 x 2 x 3 10 ( x 3 ≥ 0 ) 则 x 3 称为松弛变量 x_1x_2 \le 10 \\ 可引进x_3,使x_1x_2x_310(x_3 \ge 0) \\ 则x_3称为松弛变量x1​x2​≤10可引进x3​,使x1​x2​x3​10(x3​≥0)则x3​称为松弛变量混合整数规划只有一部分决策变量要求取非负整数另一部分决策变量可取非负实数全整数规划除了所有决策变量要求取非负整数外系数aij和常数bi也要求取整数(这时引进的松弛变量和剩余变量同样要求取整数)0-1整数规划所有决策变量只能取0和1两个整数(一般用于工作安排)特点1、原线性规划有最优解当自变量限制为整数后其整数规划解出现下列情况1原线性规划最优解全为整数则整数规划最优解与其保持一致2整数规划无可行解3有可行解(当然就存在最优解)但最优解值变差(效果变差)2、整数规划最优解不能按照实数最优解简单取整而得可能不满足约束条件一般形式m a x ( m i n ) z ∑ j 1 n c j x j s . t . { ∑ j 1 n a i j ≤ ( , ≥ ) b i ( i 1 , 2 , . . . , m ) x j ≥ 0 , x j 为整数 ( j 1 , 2 , . . . , n ) max(min)z \sum_{j1}^nc_jx_j \\ s.t. \left\{ \begin{array}{c} \sum_{j1}^na_{ij} \le (,\ge )b_i(i1,2,...,m)\\ x_j \ge 0,x_j为整数(j1,2,...,n) \end{array} \right.max(min)zj1∑n​cj​xj​s.t.{∑j1n​aij​≤(,≥)bi​(i1,2,...,m)xj​≥0,xj​为整数(j1,2,...,n)​与线性规划关系1、整数规划可行解是松弛问题可行域中的整数格点2、松弛问题无可行解则整数规划无可行解3、ILP(整数规划)最优解小于或等于松弛问题的最优解4、松弛问题最优解满足整数要求则该最优解为整数规划最优解整数规划m a x c T x s . t . { A x b x ≥ 0 , x 为整数 maxc^Tx \\ s.t. \left\{ \begin{array}{c} Axb \\ x \ge 0,x为整数 \end{array} \right.maxcTxs.t.{Axbx≥0,x为整数​松弛问题m a x c T x s . t . { A x b x ≥ 0 maxc^Tx \\ s.t. \left\{ \begin{array}{c} Axb \\ x \ge 0 \end{array} \right.maxcTxs.t.{Axbx≥0​