一种求解随机线性二层规划问题的分支定界粒子群混合算法

张涛

doi:10.13718/j.cnki.xsxb.2018.06.008

西南师范大学学报(自然科学版)

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
	姓名不能为空！
邮箱
	邮箱不能为空！非法的邮箱地址。
手机号码
	电话不能为空！请输入有效手机号!
标题
	标题不能为空！
留言内容
	内容不能为空！
验证码
	验证码不能为空！验证码错误！

一种求解随机线性二层规划问题的分支定界粒子群混合算法

张涛. 一种求解随机线性二层规划问题的分支定界粒子群混合算法[J]. 西南师范大学学报(自然科学版), 2018, 43(6): 37-45. doi: 10.13718/j.cnki.xsxb.2018.06.008

引用本文:

张涛. 一种求解随机线性二层规划问题的分支定界粒子群混合算法[J]. 西南师范大学学报(自然科学版), 2018, 43(6): 37-45. doi: 10.13718/j.cnki.xsxb.2018.06.008

ZHANG Tao. A Particle Swarm Optimization-Branch and Bound Algorithm for the Linear Stochastic Bilevel Programming Problem[J]. Journal of Southwest China Normal University(Natural Science Edition), 2018, 43(6): 37-45. doi: 10.13718/j.cnki.xsxb.2018.06.008

Citation:

ZHANG Tao. A Particle Swarm Optimization-Branch and Bound Algorithm for the Linear Stochastic Bilevel Programming Problem[J]. Journal of Southwest China Normal University(Natural Science Edition), 2018, 43(6): 37-45. doi: 10.13718/j.cnki.xsxb.2018.06.008

一种求解随机线性二层规划问题的分支定界粒子群混合算法

张涛

长江大学信息与数学学院, 湖北荆州 434023

A Particle Swarm Optimization-Branch and Bound Algorithm for the Linear Stochastic Bilevel Programming Problem

ZHANG Tao

School of Information and Mathematics, Yangtze University, Jingzhou Hubei 434023, China

摘要: 将一类随机线性二层规划模型转换为带期望约束的确定性线性二层协方差规划模型，并进一步利用KKT条件将二层协方差规划模型转化为单层规划模型，然后利用分支定界-粒子群混合算法对该模型进行求解.与传统分支定界算法的对比实验表明，该算法有效改善了上层问题的方差结果，且计算效率得到了较显著提高.
- 随机线性二层规划 /
- 带期望约束的二层协方差模型 /
- 粒子群优化算法 /
- 分支定界算法
Abstract: First, a class of stochastic linear bilevel programming models is transformed into a deterministic linear bilevel covariance programming model with expected constraints. Then, using the KKT condition, the deterministic bilevel covariance programming problem is transformed into a deterministic single level programming problem. After that, the single level programming problem is solved by the particle swarm optimization-branch and bound algorithm. The results of a comparative experiment show that the proposed algorithm can improve the variance results of the upper level problem and significantly increase the computational efficiency.
- linear stochastic bilevel programming /
- bilevel variance model with expectation constraints /
- particle swarm optimization algorithm /
- branch and bound method .

[1]	BARD J F,FALK J E.An Explicit Solution to the Multilevel Programming Problem[J].Computers and Operations Research,1982,9(1):77-100.
[2]	DEMPLE S.Foundation of Bilevel Programming[M].London:Kluwer Academic,2002.
[3]	藤春贤, 李智慧.二层规划理论与应用[M].北京:科学出版社, 2002.
[4]	BARD J.An Algorithm for Solving the General Bilevel Programming Problem[J].Mathematics of Operations Research,1983,8(2):260-272.
[5]	EDMUNDS T,BARD J.Algorithm for Nonlinear Bilevel Mathematical Programs[J].IEEE Transactions on Systems,Men,and Cybernetics, 1991,21(1):83-89.
[6]	AMOUZEGAR M.A Global Optimization Method for Nonlinear Bilevel Programming Problems[J].IEEE Transactions on Systems,Men,and Cybernetics,1999,29(6):771-777.
[7]	ETOA J.Solving Quadratic Convex Bilevel Programming Problems Using a Smoothing Method[J].Applied Mathematics and Computation,2011,217(15):680-6690.
[8]	BARD J,FALK J.An Explicit Solution to the Multi-Level Programming Problem[J].Computers & Operations Research,1982,9(1):77-100.
[9]	ISHIZUKA Y,AIYOSHI E.A New Computational Method for Stackelberg and Min-Max Problems by Use of a Penalty Method[J].IEEE Transactions on Automatic Control,1981,26(2):460-466.
[10]	AIYOSHI E,SHIMUZU K.A Solution Method for the Static Constrained Stackelberg Problem via Penalty Method[J].IEEE Transactions on Automatic Control,1984,29(12):1112-1114.
[11]	ISHIZUKA Y,AIYOSHI E.Double Penalty Method for Bilevel Optimization Problems[J].Annals of Operations Research,1992,34(1):73-88.
[12]	LV Y,HU T,WANG G,WAN Z.A Penalty Function Method Based on Kuhn-Tucker Condition for Solving Linear Bilevel Programming[J].Applied Mathematics and Computation,2007,188(1):808-813.
[13]	SAVARD G,GAUVIN J.The Steepest Descent Direction for the Nonlinear Bilevel Programming Problem[J].Operations Research Letters,1994,15(5):265-272.
[14]	FALK J,LIU J.On Bilevel Programming,Part I:General Nonlinear Cases[J].Mathematical Programming,1995,70(1-3):47-72.
[15]	PATRIKSSON M,WYNTER L.Stochastic Mathematical Programs with Equilibrium Constraints[J].Operations Research Letters,1999,25(4):159-167.
[16]	GAO J,LIU B,GEN M.A Hybrid Intelligent Algorithm for Stochastic Multilevel Programming[J].IEEE Transactions on Electronics,Information and Systems,2004,24(10):1991-1998.
[17]	万仲平, 肖昌育, 王先甲,等.不确定市场下的一种二层规划最优竞价模型[J].电力系统自动化,2004,28(19):12-16.
[18]	万仲平, 樊恒, 王广民,等.基于随机二层规划的不确定电力市场中交互式模糊竞价决策方法[J].武汉大学学报(工学版), 2006,39(5):85-90.
[19]	何云, 冯春强.带补偿的二层随机规划逼近算法研究[J].纺织高校基础科学学报, 2013,26(1):110-113.
[20]	周婉娜, 霍永亮.二层随机规划逼近最优解集的稳定性分析[J].重庆工商大学学报(自然科学版), 2013, 30(7):19-23.
[21]	周婉娜, 霍永亮,胡之英.二层随机规划逼近ε-最优解集的Hausdorff收敛性[J].湖南师范大学自然科学学报,2016,39(3):80-83.
[22]	刘勇,王慧,徐裕生,等.二层随机规划逼近解的收敛性[J].纯粹数学与应用数学,2008,24(4):768-773.
[23]	BARD J F,MOORE J T.A Branch and Bound Algorithm for the Bilevel Programming Problem[J].SIAM Journal on Scientific and Statistical Computing,1990,11(2):81-292.
[24]	MASATOSHI S,ICHIRO N.Cooperative and Non-cooperative Multi-Level Programming[M].New York:Springer Science,2009.

计量

文章访问数: 1113
HTML全文浏览数: 772
PDF下载数: 141
施引文献: 0

一种求解随机线性二层规划问题的分支定界粒子群混合算法

张涛

长江大学信息与数学学院, 湖北荆州 434023

收稿日期: 2017-12-04

关键词:

摘要: 将一类随机线性二层规划模型转换为带期望约束的确定性线性二层协方差规划模型，并进一步利用KKT条件将二层协方差规划模型转化为单层规划模型，然后利用分支定界-粒子群混合算法对该模型进行求解.与传统分支定界算法的对比实验表明，该算法有效改善了上层问题的方差结果，且计算效率得到了较显著提高.