[科普中国]-离散优化

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

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

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

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

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

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

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

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

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

或

或

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

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

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