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

An Extended Global PCPAlgorithm for Linear Bilevel Programming

作　　者：杨静蕾 罗梅丰[2] 袁帅石 YANG Jing-lei;LUO Mei-feng;YUAN Shuai-shi(Department of Management science and Engineering,Business School,Nankai University,Tianjin 300071,China;Department of Logistics and Maritime Studies,The Hong Kong Polytechnic University,Hong Kong,China)

机构地区：[1]南开大学商学院管理科学与工程系,中国天津300071 [2]香港理工大学物流及航运系,中国香港

出　　处：《运筹与管理》2021年第1期23-28,共6页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(NSFC61772290)。

摘　　要：本文采用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.

关 键 词：线性双层规划 PCP算法 互补旋转 线性互补问题 

分 类 号：O221.1[理学—运筹学与控制论]