线性规划整数解有简便方法吗

Question

如题所述

Answer 1

整数线性规划的解法总结

0-1整数线性规划是整数线性规划的特殊情况，在实际中有着广泛的应用。虽然变量的取值只有两个，但此类问题的求解却意外的困难，下面把有关的一些解法总结一下。

1.穷举法 把所有可能的解一一代入，然后比较满足约束的解，使目标函数最达到最优的解是最优解。这不失为一种方法，但不是一种好方法。如果问题规模大，则无法在可接受的时间内求得最优解。这也是求解整数规划的困难所在。

2.隐枚举法I 是穷举法的改进，其思路是先给出一个可行解，然后代入目标函数算出函数值得到一个上界（如果求最小值）或下界（如果是求最大值）。然后一一检验其它的解，如果该解大于上界或小于下界，则不用检验可行性，因为它不可能是最优解，否则的话就要检验可行性，如果是可行解，则修改上界或下界，继续检验其它的解，否则不用修改上界或下界，直接检验其它的解。这种方法通过上界或下界来控制是否需要进行可行性检验，提高了效率。但是，要找可行解也得花一定的时间，当约束和变量较多时，工作量异常的大，退一步来说，即使可行解比较容易找到，但其产生的上界太大，或是下界太小，则其过滤的效果也不明显。这是这种方法的缺陷。

3.隐枚举法II 这种方法先把问题转化成标准型，然后按照分枝定界法的思想，尽量少的检验可行解来寻找最优解。这种方法比较麻烦，我在这里也描述不清楚，过几天理解透了再来写这一部分。

4.隐枚举法III 这是在程冬时，张声年在江西电力职业技术学院学报上发表的一篇文章《关于0-1型整数规划的若干问题》中提出来的，大致的思路是：把所有可能的解都代入目标函数算出值，然后把这些目标函数值进行排序，如果是求最大值，则降序排列，如果是求最小值则升序排列。然后按这个顺序一个一个的检验对应的解的可行性，当碰到第一个可行解时即得到最优解，因为其它的解不会优于此解了。这种方法的缺陷也是明显的，如果变量为N个，则需求2的N次个目标函数值，然后还要进行排序，这又是项工作量很大的工作，再一个就是，如果排序结果是把可行解排在最后一个，那还是得进行2的N次方次检验。

4.启发式算法 遗传算法，蚁群算法等都可归于此类。这都是随机算法，说白了就是听天由命，即使算出了最优解你也不知道是不是最优解，因为此类算法的收敛性都只是依概率收敛的，真正在算的过程中是否已得到最优只有上帝知道。启发式算法是万不得已的情况下才使用的，我们用这种方法只能保证得到的解比其它方法得到的好，但不一定就说得到了最优了。

0-1规划的求解方法还在研究之中，也许你会发现一个有效的算法。