经济和管理领域中有些问题抽象为模型时，发现许多量具有不可分割性，因此当它们被作为变量引入到规划中时，常要求满足取整条件。如生产计划中，生产机器多少台(整数)；人力资源管理中，招聘员工多少人(整数)；运输问题中，从一个港口到另一个港口的集装箱调运数量(整数)；另外，运作管理中的决策问题：如工厂选址、超市选址、人员的工作指派、设备购置和配置、系统可靠性设计、机床加工任务的均衡分派、线路设计中的接点串联设计、信号系统的代码设计等等，其规划模型中往往须引入逻辑变量(即变量仅取0或1两个值)来反映冲突因素和抉择。因此，这些问题的规划模型不同于前述的线性规划范畴，而属于一种新的类型——整数规划。

第一节整数规划概念与特点

整数规划(integer programming，简称IP)是指决策变量有整数要求的数学规划问题。整数规划是从1958年由R.E.戈莫里提出割平面法之后形成独立分支的，30多年来发展出很多方法解决各种问题。整数规划分为线性整数规划和非线性整数规划，本章只讨论线性整数规划，后面提到的整数规划若不说明，都是指线性整数规划。线性整数规划中如果所有的决策变量都取整数，就称之为纯整数规划或全整数规划；如果仅一部分决策变量取整数，就称之为混合整数规划；如果决策变量只取0或者1，就称之为的0-1规划，它是整数规划中的特殊情形，在整数规划中占有重要地位，求解方法也与其它的整数规划不一样。

整数线性规划数学模型的一般形式为：

对于整数规划而言，如果放松整数约束，整数规划就变成线性规划。通常我们称放松整数约束得到的线性规划问题为该整数规划的线性规划松弛问题，简称松弛问题。任何一个整数规划都可以看成是一个线性规划松弛问题再加上整数约束构成的。这意味着整数规划是比线性规划约束得更紧的规划问题，它的可行域是其松弛问题的一个离散子集，即只是整数解部分。如线性规划(3-2)是整数规划(3-1)的松驰问题，后者的解集是前者的一个子集。

从整数规划与其松驰问题的定义及模型的一般式来看，整数规划是比线性规划约束得更紧的规划问题，两者的解既有密切的联系，又有本质的区别。整数规划的可行解是其松弛问题的一个离散子集，即只是整数解部分，所以整数规划的最优目标函数值不会优于松驰问题的最优目标函数值。松驰问题作为一个线性规划问题，其可行解的集合是一个凸集，任意两个可行解的凸组合仍为可行解。而由于任意两个整数的凸组合不一定是整数，所以整数规划的的任意两个可行解的凸组合不一定为它的可行解。

对于小型的整数规划，其可行域是有界的，且可行解不多，可以考虑用枚举法，即列举出每一个可行解并求出其目标函数值，一一比较，取其最优值。但这一方法显然不适合求解大型的整数规划问题。对于只有两个决策变量的整数规划问题，也可以考虑使用图解法，其方法与求解一般线性规划的方法一样。对于一般的整数规划问题，为了满足整数解的要求，初看起来，似乎只要把已得到松驰问题的带有分数或小数的解经过“舍入化整”就可以了。但这常常是不行的，因为化整后不见得是可行解，或者虽是可行解，但不一定是最优解。所以单纯形法显然不适合直接求解整数规划。下面各节将介绍几种常用的求解整数规划的方法。