一、整数规划的定义：

       数学规划中的变量限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划，若是在计算中无特定算法，只能用近似算法，如蒙特卡罗模拟，智能算法等，则称为非线性整数规划。

二、整数规划的特点：

1、原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：

（1）原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。

（2）整数规划无可行解。

（3）有可行解（就会存在最优解），但最优解值变差。

2、整数规划最优解不能按照实数最优解简单取整而获得（即不能四舍五入，因为可能不满足它的条件）。

三、整数规划模型形式：

整数规划一般解决运输问题，指派问题

整数规划的类型与要求：

注：0—1规划一般适用于工作安排

四、整数规划与线性规划的关系：

（1）注：

1、整数规划的可行解是松弛问题可行域中的整数格点

2、松弛问题无可行解时，整数规划也无可行解

3、整数规划的最优值通常是小于或等于松弛问题的最优解

4、如果松弛问题的最优解满足整数要求，则该最优解为整数规划最优解

（2）两者的求解过程

线性规划函数：

【x,fval】 = linprog [ c , A , b , Aeq , beq , lb , ub , X0 ]

【x,fval】 =intlinprog [ c , intcon , A , b , Aeq , beq , lb ,ub ]

注：（1）intlinprog不能指定初始值；

       （2）加入了intcon参数可以指定哪些决策变量是整数。

例如：决策变量有三个：x1 ,x2 ,x3 ;若x1和x3是整数，则intcon = [1,3]

五、目前采用整数规划的方法有：

分枝定界法和割平面法

方案一：

方案二：

解法：