线性双层规划的改进PCP全局求解算法

An Extended Global PCPAlgorithm for Linear Bilevel Programming

本文采用K-T条件将线性双层规划模型改写为单层规划后,将参数引入上层目标函数,构造了含参线性互补问题(PLCP)并给出它的一些性质。进而通过改进Lemke算法的进基规则,在保持互补旋转算法原有优势的基础上,引入充分小正数ε,设计了改进参数互补旋转(PCP)算法求取全局最优解,最后通过两个算例说明了其有效性。

After reformulating the linear bilevel programming model into a single level problem with the K-T conditions,we introduce a parameter into the upper level objective function to construct the Parametric Linear Complementary Problem(PLCP),whose properties are discussed in this paper.Then an extended Parametric Complementary Pivot(PCP)algorithm is proposed based on some modifications of the rules for determining the entering basis variable in Lemke’s Algorithm after introducing a sufficiently small positive number ε.The extended PCP algorithm,which maintains the original advantages of the complementary pivoting approach,can achieve the global optimal solution.The computational results of two examples demonstrate that this algorithm is effective.