当前位置：首页> 求解非线性整数规划全局最优解的填充函数法

求解非线性整数规划全局最优解的填充函数法

时间：下载该word文档

第１０卷第３５期２０１０年１２月　
科学技术与工程　
Ｖｏ１．１０　Ｎｏ．３５　Ｄｅｅ．２０１０　
１６７ｌ一１８１５（２０１０）３５－８６６６—０４　
Ｓｃｉｅｎｃｅ　Ｔｅｃｈｎｏｌｏｇｙ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ　
⑥２０１０　Ｓｃｉ．Ｔｅｃｈ．Ｅｎｇｎｇ．　
求解非线性整数规划全局最优解的填充函数法　
贺向阳
徐
玲　
（上海第二工业大学理学院，上海２０１２０９）　
摘要　提出了一个填充函数，用来求解“严格路径连通域”上的非线性整数规划全局最优解问题。探讨了该填充函数的　非线性整数规划　
Ｏ２４１．７；　
严格路径连通域　
文献标志码
填充函数　
填充函数法　
全局极小点　
理论性质，提出了相应的求解算法，并进行了算例测试。测试结果表明该算法令人鼓舞。　关键词中图法分类号
Ａ　
离散全局优化广泛应用于如排序、物流的供应　这里．厂：　一尺，　是　中的整点集，　是　的一个　
链及工业设计等领域。在过去的整数规划中，人们　大多局限于线性整数规划的研究，对非线性整数规　
子集。事实上，令＿厂（　）＝∞，　∈Ｚ“＼　，则上述问题　等价于：ｍｉｎ｛．厂（　）：　∈Ｚ　｝。　
划的研究甚少。求解线性整数规划有许多的算法，　如分枝定界法、割平面法等，但非线性整数规划问　题则较困难。对于连续的非线性全局优化问题，人　
，　
定义１　序列｛　
“
一
一　在　上如果满足　～＝　
：　
；对于所有ｉ，　∈　；如果ｉ≠　，那么　
≠　；并且对于所有的ｉ，有ｌｌ　。一　ｌＩ＝Ｉｌ　”　一　‘ｌｌ＝ＩＩ　～一　
一
们已找到了许多种确定性算法，如填充函数法　，　打洞函数法　。对于非线性离散全局优化问题，最　初是把非线性整数规划“连续化”　，随后的许多在　文献［４］的基础上给出了离散全局优化问题的填充　函数定义，并给出了填充函数。但把离散问题连续　化有许多弊病。一般地，连续情形的填充函数的第　３个定义条件在离散的情形不适用。文献［５—８］中　提出了一套求解离散全局优化问题的填充函数法。　
ｌｌ＝１，则序列｛　｝　：一　被称为　
个连接不同点Ｘ　和　一的离散路径。如果　和　～之间在　中存在一条离散路径，那么称它们是　
连通的。进一步，如果在　中任意两点都是连通　的，那么称　为连通集。另外，对于所有的ｉ，如果　ｌｌ　一　
ｌｌ＜ｌｌ　
一　
ｌｌ，那么该序列称为严格　
离散路径。如果　和　之问在　中存在一条严格　离散路径，那么称它们是严格连通的。　
定义２　ｄ＝｛－４－ｅ　：ｉ＝１，２，…，ｎ｝称为　中的　坐标轴方向集，这里ｅ　是第ｉ个单位向量，即该向量　的第ｉ分量为１，其余分量为０的向量。　
定义３如果　∈Ｚ“，则集合Ｎ（　）＝｛　，　±ｅ　：　ｉ＝１，２，…，ｎ｝称为点　的离散邻域。　
定义４　如果当　∈Ｘ　ｎ　Ｎ（　）时，有ｆ（　）≥　
本文在文献［４］中定义的填充函数的基础上，构造　
一
个新的填充函数，详细讨论了其理论性质，并给　求解全局优化问题有２个困难要解决，一是如　
出了相应的算法。　
何从一个局部解出发找到更好的局部解；二是如何　
判定一个局部解是全局解。本文探讨第一个问题。　
厂（　），那么称点　∈Ｘ为＿厂在　上的离散局部极小　
１基本知识　
考虑下列离散全局最优化问题：　
点。如果当　∈Ｘ时，有　）　），那么称点　∈　
为．厂在　上的离散全局极小点。　引理
假设　，　∈Ｘ，如果存在ｉ∈｛１，２，…，　
（Ｐ）：ｍｉｎ｛Ｉ厂（　）：　∈ＸＣＺ　｝。　
２０１０年９月１９日收到，１Ｏ月１０　１３修改　
ｎ｝使得　±ｅ　∈Ｘ，那么存在ｄ∈Ｄ，使得ｌＩ　＋ｄ一　
ｌｌ＞ｌｌ　一　＿Ｉ。　
定义５　给定（Ｐ）的一个局小点　，如函数　

阅读全文