切平面在混合整非线性规划中的应用.pdf

中文摘要 摘要：混合整数非线性规划(MixedNonlinear Integer 一类包含连续和整数变量的非线性规划问题。MINLP是整数规划的～个重要分支， 近几十年来MINLP的应用有了快速的发展，其应用领域包括流程工业、金融、工 程、管理科学和运筹学等各个领域。MINLP问题的求解算法包括确定型算法和启 发式算法，确定型算法是将难于求解的MINLP问题分解为相对容易求解的混合整 Linear 数线性规划问题(MixedInteger 过投影及对偶等方法将MINLP问题分解为MILP问题，另外一类是利用迭代构造 切平面的方法将原问题分解为简单问题。 本文的目标是通过对求解凸MINLP问题的各种确定型算法的研究，明确切平 面在确定型算法中的重要作用，利用切平面的构造方法对已知算法进行改进，并 争取构造出新的算法。 本文首先给出了切平面在确定型算法中的作用，给出了切平面构造的位置和 方法与各种算法收敛速度的关系，得出结论：切平面的构造影响算法的收敛速度， 一般来说在非线性可行域边界上构造切平面的算法具有快的收敛速度，非线性可 行域边界上构造的切平面称为支撑超平面；又MINLP问题的性质要求最优解为整 数点，因此如果可以给出在整数点处快速生成支撑超平面的方法，就得到了一个 简洁且收敛速度快的确定型算法。 基于此我们给出了求解MINLP问题的支撑超平面算法的一般形式，并证明了 其收敛性，同时提出了三个具体支撑超平面算法，分别为平行下降支撑超平面算 法，基于内点的支撑超平面算法和不基于内点的支撑超平面算法。 着很广泛的应用，该算法的缺点是需要利用两个NLP问题的求解。我们将SHP算 法的思想引入到OA算法中，给出改进的OA算法，我们称新的算法为 EOA(Extended 规划问题无解时，利用Vinott’sSHP算法生成一个支撑超平面，替换OA算法中通 过求解第二个NLP问题生成的切平面。新算法继承了OA算法在非线性可行域边 界整数点生成切平面的优势，同时减少了NLP问题的求解次数。 启发式算法和确定型算法是求解MINLP问题的两个不同类型的算法，确定型 算法在求解MINLP问题时可以保证解的全局最优性，但对大规模问题的求解需要 很长的计算时间，启发式方法不能保证解的全局最优，但求解问题时具有快速、 简单的特点。本文我们给出了一种将启发式算法转化为确定型算法的切平面方法， 新的算法继承了切平面方法全局收敛和启发式算法效率高的特点，并保证了算法 的收敛速度和全局最优性，我们称这种算法为启发式切平面算法。 关键词：混合整数非线性规划；切平面：支撑超平面算法；确定型算法 分类号：【0221．4】 ABSTRACT Mixed Nonlinear to Integer mathematical Programming(MINLP)refers withcontinuous and variables．MINLPwhichall programming integer is class important ofInteger tremendousinrecent Programming(IP)hasexperience progress years． MIN LPhavebeenusedinvarious applications，includingprocessindustry,financial， scienceand research whichare