问题背景与数学模型描述

1.问题的提出

在许多线性规划问题中，涉及人员数量、设备台数等取值必须取整的情况，相应的线性规划的解，如果取值非整，则与现实情境冲突。如果对简单地求得相应线性规划问题的最优解进行四舍五入，或舍零取整化处理，得到的解又可能是非最优解，甚至为非可行解。将线性规划模型中的部分或全部变量限定为整数时，便形成了所谓的整数规划。割平面方法和分支定界法，通过转化为多次线性规划问题的求解过程，实现了对整数规划问题的求解。

整数规划是规划论中的一个重要分支，在经济管理领域的应用非常广泛。所有决策变量均需取整时对应的整数规划问题称为纯整数规划问题，或全整数规划问题。如果并不要求全部决策变量均为整数，则称之为混合整数规划问题。特殊情境下，决策变量取值仅仅为0或1时，形成0-1型整数规划问题。本章所涉及的指派问题就属于一种0-1型整数规划问题。

例3-5某国防企业在“十二五”计划期间内计划生产A、B两种驱逐舰。该企业拥有强大的生产能力来加工制造这两种驱逐舰的所有零部件，相应所需的原材料和能源也可满足供应，不过有T、F两种紧缺物资的供应量受到西方发达国家的严格控制，与此有关的数据如表3-19所示。请问该企业在本计划期内应安排生产A、B驱逐舰各多少艘，使得利润最大化？

表　3-19

整数规划的应用范围极其广泛。它不仅在工业、工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。在现实的经济管理领域中，整数规划的应用涉及生产计划问题、物资运输问题、人员安排问题、投资选择问题等。

严格意义上讲，整数规划是一类要求问题的解中的全部或一部分变量为整数的数学规划问题。因此，从约束条件的构成来看，又可将整数规划细分为线性、二次和非线性的整数规划。本章如无特殊指明，仅讨论整数线性规划，所提到的整数规划是指整数线性规划问题。

2.数学模型描述与求解的特点

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

求解整数规划问题时，最典型的做法是逐步生成一个相关的问题，称它为原问题的衍生问题。对每个衍生问题又伴随一个比它更易于求解的松弛问题（衍生问题称为松弛问题的原问题）。本章中松弛问题由整数规划问题模型除去对决策变量的整数约束取得。

整数规划问题解的特点，与其对应的松弛问题具有密切的关系，但是又有本质上的差异。整数规划问题的可行解集合，是它的松弛问题可行解集合的一个子集。整数规划的可行解，一定是它的松弛问题的可行解，反之则不一定成立。可以确定的是，整数规划问题的最优解的目标函数值不会优于其对应的松弛问题最优解的目标函数值。

整数规划问题对应的松弛问题是一个线性规划问题，任意两个可行解的凸组合仍为可行解，即可行解的集合是一个凸集。对于整数规划问题而言，任意两个可行解的凸组合则不一定满足变量的整数约束条件，因而也就不一定仍为可行解。

通过松弛问题的解来确定它的源问题的归宿，即源问题应被舍弃，还是再生成一个或多个它本身的衍生问题来替代它。在此基础上，选择一个尚未被剔除的或替代的原问题的衍生问题，重复以上步骤直至不再存在未解决的衍生问题为止。

对于整数规划问题的求解而言，有人试图利用穷举法进行处理，但是对于大型问题，即使利用计算机进行穷举计算也不可行。 自上世纪60年代以来，逐步发展出割平面法、分支定界法、求解0-1型整数规划的隐枚举法、分解法、群论法、动态规划法等，以及最近形成的近似算法和计算机模拟法等一系列整数规划的一般解法，这些解法具有重要的实际意义。 目前，比较成功又流行的求解整数规划问题的方法是割平面法和分支定界法，下面我们进行详细研究。