毕业论文移动版

第二章整数规划及分支定界法介绍

2.1整数规划

我们在求解线性规划问题时，通常有些最优解会出现分数或者小数的状况，但是对一些实际的问题，我们通常需要求的问题变量的解都必须为整数。例如，所求解是生产货物的工人数目、完成工作的工具需求数目或者控制生产的电脑台数等，这些问题所需要的都是整数，分数或小数的答案就显然是不符合实际要求了，所以我们通常需要求解的结果为整数。为了满足整数解的要求，人们想出了很多的办法，大体一看，似乎我们只需要把已经得到的结果中带有分数或者小数的，经过“化整”就可以完成任务了。但是这往往是行不通的，因为，即使化整后的解，也不见得是原问题的可行解；除此之外，也可能虽然化整后就是可行解，但它也不一定是原问题最优解。因此，对于需要求最优整数解的问题，有必要对它另外进行研究。这样的问题我们称其为整数线性规划（integerlinearprogramming），简称ILP，整数线性规划对我们的实际生活有着很大的作用，它是最近几十年迅速发展起来的，也是数学规划论中的一个分支。

在求解整数线性规划时，要是限制了问题的所有变量都为（非负）整数，就称这样的问题为纯整数线性规划（pureintegerlinearprogramming）；如果所求问题仅仅是限制了一部分的变量为整数，就称这类问题为混合整数线性规划（mixedintegerlinearprogramming）。当然整数规划也是有特殊情况的，0-1规划问题就是整数线性规划的一种特殊情况，这是因为它的变量取值只有0或1。

接下来，我们来通过一个例子来说明用上述线性规划不能保证求得的解是整数最优解的情况。例1某加工厂现在要生产一批商品，目前拟定的商品只有甲乙两种，生产每种商品的原材料数量、储存费用和可以获得的利润以及生产所受限制如表2-1所示。现在求两种商品各生产多少箱，才可以获得最大利润？

由题目，我们不难看出这是一个求整数规划的问题，它最后要求的解只能是整数，现在分析并求解这个问题。第一步：模型建立我们设x1，x2分别是生产甲、乙两种商品的数量（这显然是个非负整数）。仔细阅读这个问题，我们不难发现它是一个（纯）整数规划问题，用数学公式可表达为第二步：解分析及问题引出如果不考虑条件⑤，它就成了一个线性规划问题（将与原问题相对应的这个线性规划问题称为松弛问题），可以求它的线性规划最优解，此最优解不一定是非负整数，这种情况后面再来考虑。这里可求得其最优解为（方法见[1]）

此最优解中x1是小数，但在原问题中x1是甲货物的托运箱数，现在它不是整数，这显然就不合条件⑤。这这种情况下，有人就考虑是不是可以把所得到的这个非整数的最优解“化整”，这样不就可以得带合乎条件⑤的整数最优解吗？如果将（x1凑整为（x1就会破坏了条件②（关于原材料费用的限制），所以它不是原问题的可行解；如果将（x10）舍去尾数0.8，变为0），这样一改，它肯定就满足各个约束条件了，因此它是可行解，但此时它却又不是最优的解了，因为这表现了利润因为“化整问题”而降低了，而引起这种情况的原因就是变量的不可分性（生产个数）。通过上边的例子我们可以看出，虽然，将原问题的相应线性规划的最优解通过“化整”来求解原整数规划问题是最容易想到的，但是即使这样做了，也常常得不到原整数规划问题的最优解，更有甚者根本就脱离了可行域，成了非可行解。因此，对整数规划的算法进行专门的研究是非常有必要的[2]。 (责任编辑：qin)