离散优化问题，又称为整数规划 (线性整数规划)，整数规划是指规划中的变量（全部或部分）限制为整数，若在线性模型中，变量限制为整数，则称为整数线性规划。所流行的求解整数规划的方法往往只适用于整数线性规划，这是一类要求问题的解中的全部或一部分变量为整数的数学规划。从约束条件的构成又可细分为线性，二次和非线性的整数规划。

离散优化问题，又称为整数规划 (线性整数规划)，它是一定全部决策变量取整数值，就称它为 “纯整数规划”；若允许一部分决策变量是连续的， 又限制其余决策变量取整数值，则称它为“混合整数规划”；限制全部决策变量不是0就是1，就称它为 “二进制规划”或“0-1”规划。后者是一类特殊的离散优化问题。

已经发展了很多种建立整数规划的准则，人们运用它取得一些很有用的模型，这通常是指在一个计算机上，模型的求解会在比较短的时间内完成。 下面列举出某些准则。

①如果事先知道一个整数变量会是一个大的数值(通常为20，或者更大)，就把它作为连续变量处理，然后对该变量的解，按照四舍五入原则取整而得到整数解答。

②约束条件系数太繁琐会使求解困难，所以要慎重地把约束条件写成尽可能不复杂的形式。例如，设为非负整数变量，约束条件为

可以换成如下的等价表达式

③由于可行域范围的任何缩小都会减小计算工作量，所以希望对变量取一个较好的上界和下界。

在实践中，为了解决某些问题建立模型的困难，也会引进离散模型。如以下情况：

①研究两个约束条件中至少有一个成立的情况。例如，制造某一产品，我们要从两种资源中选取出一种。这种情况显然包括“两取一”约束条件在内。例如，我们会遇到下列约束条件：

或

或

设M为非常大的正数，又定义y为双值变量(取值 为0或1)，则“两取一”约束条件的等价表达式为

注意在最后的解答中，若y=0，则第一个约束条件成立，第二个约束条件就变得不起作用(因为赋予M非常大的数值)。若y=1，则情况相反。

②推广前面的方法，即研究L个约束条件中至 少有K (K

其中至少有K (K

式中，M是一个非常大的正数，或1，。

③有时会碰到下面这种情况，即某一函数只能取R个特定值中的一个。如果把这个限制写成为

或或或.

那么等价的表达式为

式中，或1，。

还值得指出的是，变量有界(明显或者隐含)的纯整数规划问题，可以用一种称为“二进制分解”方法将其转变为0-1规划，另外，这方法也可把非线性多项式0-1规划转变为线性0-1规划。

例题解析

例1设背包的有限容积为V，现有种物品可以往里面装，第种物品的每件体积为，价值为。装背包的目标，是在背包容积的限制下，怎样的装法可使装进背包的物品总价值最大。如果我们定义为装进背包的第种物品的件数，则这个问题可以写成

约束：

并是整数.

这个模型是推广了的背包问题，其中可以取任意非负整数。换言之，装进背包的某一种物品可以多于1件。背包问题的特殊情况之一，是限制每一个变量取值为0或1，因此装进背包中的每种物品不能多于一件。

背包问题是只有一个约束条件的纯整数规划。 有两点理由说明这种问题是很重要的。第一，很多整数规划问题，诸如资金预算、机床负荷和方案选择等问题，都可以指出它的背包问题等价形式。第二，已经有很多求解背包问题的有效算法，它们已成为求解一般整数规划问题新算法的基础。

已经发展的离散优化问题的算法，典型地分为3类： 枚举法，割平面法和群论法。

参考资料

最新修订时间：2022-08-25 15:57