企业官网建设流程全解析

定义

数学规划中的变量(部分或全部)限制为整数

分类

纯(完全)整数规划

所有决策变量要求取非负整数(这时引进的松弛变量和剩余变量可以不要求取整数)
松弛变量：例：
x 1 + x 2 ≤ 10 可引进 x 3 , 使 x 1 + x 2 + x 3 = 10 ( x 3 ≥ 0 ) 则 x 3 称为松弛变量 x_1+x_2 \le 10 \\ 可引进x_3,使x_1+x_2+x_3=10(x_3 \ge 0) \\ 则x_3称为松弛变量x1​+x2​≤10可引进x3​,使x1​+x2​+x3​=10(x3​≥0)则x3​称为松弛变量

混合整数规划

只有一部分决策变量要求取非负整数，另一部分决策变量可取非负实数

全整数规划

除了所有决策变量要求取非负整数外，系数a_ij和常数b_i也要求取整数，(这时引进的松弛变量和剩余变量同样要求取整数)

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_{j=1}^nc_jx_j \\ s.t. \left\{ \begin{array}{c} \sum_{j=1}^na_{ij} \le (=,\ge )b_i(i=1,2,...,m)\\ x_j \ge 0,x_j为整数(j=1,2,...,n) \end{array} \right.max(min)z=j=1∑n​cj​xj​s.t.{∑j=1n​aij​≤(=,≥)bi​(i=1,2,...,m)xj​≥0,xj​为整数(j=1,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} Ax=b \\ x \ge 0,x为整数 \end{array} \right.maxcTxs.t.{Ax=bx≥0,x为整数​
松弛问题：
m a x c T x s . t . { A x = b x ≥ 0 maxc^Tx \\ s.t. \left\{ \begin{array}{c} Ax=b \\ x \ge 0 \end{array} \right.maxcTxs.t.{Ax=bx≥0​