线性规划整数解有简便方法吗?线性规划整数解除了用画图法还有什么别的方法?有只用代数的方法吗?

Question

线性规划整数解有简便方法吗?
线性规划整数解除了用画图法还有什么别的方法?有只用代数的方法吗?

Answer 1

整数线性规划的解法总结
0-1整数线性规划是整数线性规划的特殊情况,在实际中有着广泛的应用.虽然变量的取值只有两个,但此类问题的求解却意外的困难,下面把有关的一些解法总结一下.
1.穷举法 把所有可能的解一一代入,然后比较满足约束的解,使目标函数最达到最优的解是最优解.这不失为一种方法,但不是一种好方法.如果问题规模大,则无法在可接受的时间内求得最优解.这也是求解整数规划的困难所在.
2.隐枚举法I 是穷举法的改进,其思路是先给出一个可行解,然后代入目标函数算出函数值得到一个上界（如果求最小值）或下界（如果是求最大值）.然后一一检验其它的解,如果该解大于上界或小于下界,则不用检验可行性,因为它不可能是最优解,否则的话就要检验可行性,如果是可行解,则修改上界或下界,继续检验其它的解,否则不用修改上界或下界,直接检验其它的解.这种方法通过上界或下界来控制是否需要进行可行性检验,提高了效率.但是,要找可行解也得花一定的时间,当约束和变量较多时,工作量异常的大,退一步来说,即使可行解比较容易找到,但其产生的上界太大,或是下界太小,则其过滤的效果也不明显.这是这种方法的缺陷.
3.隐枚举法II 这种方法先把问题转化成标准型,然后按照分枝定界法的思想,尽量少的检验可行解来寻找最优解.这种方法比较麻烦,我在这里也描述不清楚,过几天理解透了再来写这一部分.
4.隐枚举法III 这是在程冬时,张声年在江西电力职业技术学院学报上发表的一篇文章《关于0-1型整数规划的若干问题》中提出来的,大致的思路是：把所有可能的解都代入目标函数算出值,然后把这些目标函数值进行排序,如果是求最大值,则降序排列,如果是求最小值则升序排列.然后按这个顺序一个一个的检验对应的解的可行性,当碰到第一个可行解时即得到最优解,因为其它的解不会优于此解了.这种方法的缺陷也是明显的,如果变量为N个,则需求2的N次个目标函数值,然后还要进行排序,这又是项工作量很大的工作,再一个就是,如果排序结果是把可行解排在最后一个,那还是得进行2的N次方次检验.
4.启发式算法 遗传算法,蚁群算法等都可归于此类.这都是随机算法,说白了就是听天由命,即使算出了最优解你也不知道是不是最优解,因为此类算法的收敛性都只是依概率收敛的,真正在算的过程中是否已得到最优只有上帝知道.启发式算法是万不得已的情况下才使用的,我们用这种方法只能保证得到的解比其它方法得到的好,但不一定就说得到了最优了.
0-1规划的求解方法还在研究之中,也许你会发现一个有效的算法.