【整数规划】理论

2018年05月28日

Author: Guofei

文章归类: 5-6-最优化，文章编号: 7020

版权声明：本文作者是郭飞。转载随意，但需要标明原文链接，并通知本人
原文链接：https://www.guofei.site/2018/05/28/integerprogramming.html

Edit

整数规划（Integer Programing）是一类离散型最优化问题，这里介绍几种思路

穷举法：由于整数规划的可行方案的数量有限，所以穷举法是一个可以考虑的方法。当然，穷举法往往计算时间过长。
搜索范围法，将搜索范围划分成若干个子集，力图得到如下两个结论之一：最优解肯定不在某个子集内，最优解肯定在某个子集内。

分支法

step1
先按不考虑整数约束，求出最优解，例如，解为x1=103,x2=43x1=103,x2=43
step2
由x1=103x1=103,把可行域分为两部分x1≤[103]=3,x1≥[103]+1=4x1≤[103]=3,x1≥[103]+1=4两部分。如此便把问题转化为两个最优化问题。
step3
反复执行step2，直到得出正确结果。整个算法流程像一个二叉树。

隐枚举法

思路挺简单，就是尽量减少运算。

step1 先任意给一个可行点x0x0，对应函数值f(x0)f(x0)。
step2 对于枚举的点x′x′，求函数值f(x′)f(x′)，如果函数值f(x′)≥f(x0)f(x′)≥f(x0),检查x′x′是否在可行域内，否则就不检查是否在可行域内(通过这一步减少计算量)
stpe3
如果在可行域内，那么赋值x0=x′x0=x′,回到step2继续迭代。

分析上述算法过程，如果有n个变量，每个变量可能取m个值，需要计算mnmn次。所以隐枚举法适用于0-1规划。

参考资料

施光燕：《最优化方法》，高等教育出版社
龚纯：《Matlab最优化计算》，电子工业出版社
David R. Anderson ：《数据、模型与决策–管理科学篇》，机械工业出版社

您的支持将鼓励我继续创作！

【整数规划】理论