基于凹性割的线性双层规划全局优化算法

《基于凹性割的线性双层规划全局优化算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第21卷第1期2012年2月运筹与管理OPERATIONSRESEARCHANDMANAGEMENTSCIENCEV01．21，No．1Feb．2012基于凹性割的线性双层规划全局优化算法赵茂先，宋爱美，王向荣(山东科技大学信息科学与工程学院，山东青岛266510)摘要：通过对线性双层规划下层问题对偶间隙的讨论，定义了一种凹性割，利用该凹性割的性质，给出了一个求解线性双层规划的割平面算法。由于线性双层规划全局最优解可在其约束域的极点上达到，提出的算法能求得问题的全局最优解，并通过一个算例说明了算法的有效性。关键词：运筹学；割平面算法；凹性割；线性双层规划中图分类号：0221．1

2、文章标识码：A文章编号：1007—3221(2012)01—0048-05AGlobalOptimizationAlgorithmforSolvingLinearBilevelProgrammingBasedontheCconcavityCutZHAOMao-xian，SONGAi-mei，WANGXiang-rong(CollegeofInformationScienceandEngineering，ShandongUniversityofScienceandTechnology，Qingdao266510，China)Abstract：Aconcavitycutisdefi

3、nedbydiscussingthedualitygapofthelowerproblemofthelinearbilevelpro—gramming．Basedonthefeatureoftheconcavitycut，acuttingplanealgorithmforsolvinglinearbilevelprogram-mingisgiven．Basedontheresultthataglobaloptimalsolutiontolinearbilevelprogrammingoccursatanex—tremepointofitsconstraintregion，the

4、proposedalgorithmcanobtainaglobaloptimalsolution．Finally，aexam—pleisgiventodemonstratetheeffectivenessofthealgorithm．Keywords：operationalresearch；cuttingplanealgorithm；concavitycut；linearbilevelprogramming0引言在许多系统优化问题中，如城市交通⋯、污染控制旧1和价格制定¨1等实际问题中，系统可能涉及到不止一个决策者，并且不同的决策者具有各自的决策变量和目标函数。传统的数学规划技

5、术已不能很好地解决这类问题，多层规划正是为研究系统层次性而产生的，并已形成一个新的运筹学分支。双层规划是研究二层决策的递阶优化问题H】，在多层规划应用中最为常见，研究的两个各具目标函数决策者之间按非合作和有序的方式进行相互作用，上层首先给下层一定的信息，下层基于这些信息依照自身的利益做出反应，上层再根据下层的反应做出符合全局利益的决策。在上述过程中，一方的行为影响另一方的策略选择和目标的实现，但任何一方又不能完全控制另一方的选择行为。线性双层规划(LinearBilevelProgram．ming，简称LBP)是双层规划的一个特例，虽然上、下层问题的目标函数和约束条件都是线性的

6、，但一般情况下它是一个非凸优化问题，并且已证明LBP是NP．Hard问题¨再1。自上世纪70年代以来，已经提出了一些求解LBP的算法，文⋯将其主要分为极点搜索法、分支定界收穑日期：2010．10．12基金项目：国家自然科学基金资助项目(70971079)；山东省自然科学基金资助项目(A2008A01)作者简介：赵茂先(1966·)．男．江苏江都人。博士，教授．主要从事最优化理论、方法及相关问题的研究。第1期赵茂先，等：基于凹性割的线性双层规划全局优化算法49法、罚函数法等。极点搜索法利用LBP的全局最优解可在其约束域的极点上达到这一性质，在约束域的极点上寻找问题的最优解。分支定

7、界法主要思想是利用下层问题的K—T条件，将LBP转化为一个单层数学规划，为了绕开约束条件中的互补松驰项，不同方法提出了不同的分支定界规则。罚函数法是利用数学规划中惩罚函数原理，把不同形式的惩罚项加到上层目标函数中，将LBP转化为一个目标函数带惩罚项的单层问题，通过解转化后的单层问题来获得原问题的局部最优解或全局最优解。除以上主要几类算法外，割平面法是一类求解LBP问题的有效方法¨“⋯。本文用线性规划对偶理论和文¨川中的凹性割技术，通过对LBP下层问题对偶间隙的讨论，给出了一种凹性割定义，利用