论文部分内容阅读
摘 要 双层规划问题是一类具有递阶结构的优化问题.在不确定的双层规划优化问题中，目标函数系数或约束条件系数为区间数的双层规划模型在实际问题中有着广泛的应用.在二次-线性双层规划模型的基础上，提出了上、下层目标函数以及约束条件系数均具有区间系数的二次-线性双层规划模型，给出了求解其最好最优解的方法.首先，通过选取约束条件中不同的基矩阵，求得区间二次-线性双层规划的可能最优解.再比较求得的全部可能最优解，便可得到区间二次-线性双层规划模型的最好最优解.最后给出数值算例验证该方法的有效性.
关键词 运筹学与控制论;区间二次-线性双层规划;基矩阵;最好最优解
中图分类号 O221文献标识码 A
Abstract Bi-level programming problem is a class of optimization problems with hierarchical structure.The uncertain bi-level programming optimization problems，in which the coefficients of the objective function or the coefficients of the constraint conditions are interval coefficients，has been widely used in the actual problem.For a kind of quadratic-linear bi-level programming problems with interval coefficients in the objective function and constraint conditions，an algorithm was proposed to solve its best optimal solution on the basis of quadratic-linear bi-level programming problems.First，by choosing the different basis matrix of constraint，we can solve the possible optimal solution of quadratic-linear bi-level programming problems with interval coefficients.Second，compared with all possible optimal solution，we obtain the best optimal solution of the model.Finally，numerical examples are given to demonstrate the effectiveness of the proposed method.
Key words operational research;quadratic-linear bi-level programming with interval;basis matrix;best optimal solution
1 引 言
確定性双层规划问题已经广泛的应用到经济管理、物流领域、交通管理以及其他领域，它是一类具有递阶结构的优化问题。非线性双层规划问题在工程中应用比较广泛，其中二次双层规划问题是非线性双层规划问题中最特殊的一种数学规划。目前，求解二次双层规划的主要算法有分支定界法、罚函数法、信赖域算法和遗传算法。胡（2012）[1]讨论了双层规划的基本理论、算法及其在实际问题中的应用。nal（1993）[2]提出用改进的单纯形法求解线性双层规划，并指出互补旋转算法可以看成是改进的单纯形法。王等人（2007）[3]总结了二层规划的一些性质和算法。Strekalovsky等人（2010）[4]提出了求解二次-线性双层规划的局部搜索方法，利用K-T条件将双层规划转化为单层规划，再通过局部搜索方法得到最优解。Ren等人（2013）[5]提出了基于正态分布的分布估计算法，利用单纯形法最优性条件将双层规划转化为单层规划，求解了上层目标函数为二次的双层规划问题，提高了遗传算法的效率。
虽然确定型双层规划问题得到了解决，但在实际生活中不确定性因素出现的几率越来越大，所以众多学者开始对区间规划模型做出了研究。区间规划是解决不确定规划的重要方法，众多学者已经对区间线性规划模型做出了研究。郭等人（2003）[6]定义了区间线性规划的标准型。郭等人（2004）[7]进一步给出了区间线性规划最好最优值和最差最优值的定义，进而确定了区间线性规划的最优值区间。王等人（2008）[8]提出了用K次最好法求解了上、下层目标函数均带区间系数的线性双层规划的最好最优解，并分析了下层目标函数的系数的变动对最好最优解的影响。Li等人（2013）[9]利用单纯形法的最优性条件，设计了遗传算法，其中把约束域中下层函数的系数列向量作为初始种群，进行交叉和变异，进而求得区间线性双层规划最优解。樊等人（2014）[10]提出了用双适应度函数评估遗传算法求解区间线性双层规划的算法，在一次运算中获得最好最优解和最差最优解。任爱红（2015）[11]利用最近区间近似将一类双层模糊规划问题转化为区间双层规划问题，求解了模糊双层规划问题。对于区间二次规划的研究，Liu等人（2007）[12]讨论了一次项系数具有区间系数的二次规划模型，利用对偶定理将区间规划转化为确定性规划问题，并给出了数值解法求解了模型的上界和下界。Li等人（2008）[13]在Liu的基础上提出了更具一般形式的区间二次规划模型，设计算法求解了模型的上界和下界。Li等人（2016）[14]提出了含有等式和不等式约束的区间二次规划模型，并提出了一种检验零对偶间隙简单有效的方法，最后利用该方法求得了区间二次规划模型的精确上界. 在實际问题中，随着递阶决策过程的复杂化，例如经济中价格的变动，物流中配送成本的变化，生产商实际需求量的变动，都会引起收益的变化，双层规划中的目标函数并非都是线性函数，单纯的区间线性双层规划模型和单层区间二次规划模型已经不能很好的解决这些问题，所以有必要研究区间非线性双层规划模型。目前，对区间二次-线性双层规划做出的研究还很少。在线性双层规划的基础上，提出一类上、下层目标函数系数以及约束条件系数均带区间数的二次-线性双层规划模型。首先给出区间二次-线性双层规划模型，并提出最好最优解的概念;然后借鉴区间线性双层规划求解最好最优解的方法和单纯形法的最优性条件，设计了求解区间二次-线性双层规划最好最优解的算法;最后给出数值算例，验证了模型和算法的有效性.
2 预备知识
6 结 论
在经济学和管理学中，二次双层规划模型的系数不能给出确定值的情况很普遍，从而采用区间数来估计系数的变化范围。物流网络、证券投资组合和资源配置分别是一个动态系统，是在不确定环境中发生的。提出的模型和算法，可以应用到物流网络中，解决物流中总成本最小和用户费用最低的非线性问题;也可以推广到证券投资市场中，使得投资组合中预期收益率提高和风险率降低;也可以进一步应用到水资源等配置问题中，解决调控水价的管理者和各用水部门利益最优问题，等等。在实际问题中，当涉及到不确定二次-线性双层决策时，上述的模型和算法均可应用到实际问题中，解决双层决策优化问题。区间二次-线性双层规划模型和算法的提出，打破了经济学和管理学中只用不确定线性双层规划模型解决实际问题的局限性，推动了非线性不确定双层规划的发展。但是，区间非线性双层规划的研究成果还很少，有待更多的学者在此领域做出更深入的研究.
参考文献
[1] 胡长英.双层规划理论及其在管理中的应用[M].北京：知识产权出版社，2012.
[2] nal H.A modified simplex approach for solving bi-level linear programming problems[J].European Journal of Operational Research，1993（67）：126-135.
[3] 王广民，万仲平，王先甲.二（双）层规划综述[J].数学进展，2007，36（5）：513-529.
[4] Strekalovsky A S，Orlov A V，Malyshev A V.Local search in a quadratic-linear bi-level programming problem[J].Numerical Analysis and Applications，2010，3（1）：59-70.
[5] Aihong REN，Yuping WANG，Fei JIA.A hybrid estimation of distribution algorithm and Nelder-Mead simplex method for solving a class of nonlinear bi-level programming problems[J].Journal of Applied Mathematics，2013（13）：1-10.
[6] 郭均鹏，吴育华.区间线性规划的标准型及其求解[J].系统工程，2003，21（3）：79-82.
[7] 郭均鹏，李汶华.区间线性规划的标准型及其最优值区间[J].管理科学学报，2004，7（3）：59-63.
[8] 王建忠，杜纲.区间线性双层规划的最好最优解[J].系统工程，2009，27（4）：100-103.
[9] Hecheng LI，Fang LEI.An efficient genetic algorithm for interval linear bi-level programming problems[J].Ninth International Conference on Computational Intelligence and Security，2013，41-44.
[10] 樊洋洋，李和成.一类区间系数线性双层规划问题的遗传算法[J].计算机应用，2014，34（1）：185-188.
[11] 任爱红.基于最近区间近似和区间规划方法求解一类模糊双层规划问题[J].模糊系统与数学，2015，29（4）：139-145.
[12] ST LIU，RT WANG.A numerical solution method to interval quadratic programming[J].Applied Mathematics and Computation，2007（189）：1274-1281.
[13] W LI，X TIAN.Numerical solution method for general interval quadratic programming[J].Appl.Math.Comput，2008（202）：589-595.
[14] Wei LI，Mengxue XIA，Haohao LI.Some results on the upper bound of optimal values in interval convex quadratic programming[J].Journal of Computational and Applied Mathematics，2016（302）：38-49.
关键词 运筹学与控制论;区间二次-线性双层规划;基矩阵;最好最优解
中图分类号 O221文献标识码 A
Abstract Bi-level programming problem is a class of optimization problems with hierarchical structure.The uncertain bi-level programming optimization problems，in which the coefficients of the objective function or the coefficients of the constraint conditions are interval coefficients，has been widely used in the actual problem.For a kind of quadratic-linear bi-level programming problems with interval coefficients in the objective function and constraint conditions，an algorithm was proposed to solve its best optimal solution on the basis of quadratic-linear bi-level programming problems.First，by choosing the different basis matrix of constraint，we can solve the possible optimal solution of quadratic-linear bi-level programming problems with interval coefficients.Second，compared with all possible optimal solution，we obtain the best optimal solution of the model.Finally，numerical examples are given to demonstrate the effectiveness of the proposed method.
Key words operational research;quadratic-linear bi-level programming with interval;basis matrix;best optimal solution
1 引 言
確定性双层规划问题已经广泛的应用到经济管理、物流领域、交通管理以及其他领域，它是一类具有递阶结构的优化问题。非线性双层规划问题在工程中应用比较广泛，其中二次双层规划问题是非线性双层规划问题中最特殊的一种数学规划。目前，求解二次双层规划的主要算法有分支定界法、罚函数法、信赖域算法和遗传算法。胡（2012）[1]讨论了双层规划的基本理论、算法及其在实际问题中的应用。nal（1993）[2]提出用改进的单纯形法求解线性双层规划，并指出互补旋转算法可以看成是改进的单纯形法。王等人（2007）[3]总结了二层规划的一些性质和算法。Strekalovsky等人（2010）[4]提出了求解二次-线性双层规划的局部搜索方法，利用K-T条件将双层规划转化为单层规划，再通过局部搜索方法得到最优解。Ren等人（2013）[5]提出了基于正态分布的分布估计算法，利用单纯形法最优性条件将双层规划转化为单层规划，求解了上层目标函数为二次的双层规划问题，提高了遗传算法的效率。
虽然确定型双层规划问题得到了解决，但在实际生活中不确定性因素出现的几率越来越大，所以众多学者开始对区间规划模型做出了研究。区间规划是解决不确定规划的重要方法，众多学者已经对区间线性规划模型做出了研究。郭等人（2003）[6]定义了区间线性规划的标准型。郭等人（2004）[7]进一步给出了区间线性规划最好最优值和最差最优值的定义，进而确定了区间线性规划的最优值区间。王等人（2008）[8]提出了用K次最好法求解了上、下层目标函数均带区间系数的线性双层规划的最好最优解，并分析了下层目标函数的系数的变动对最好最优解的影响。Li等人（2013）[9]利用单纯形法的最优性条件，设计了遗传算法，其中把约束域中下层函数的系数列向量作为初始种群，进行交叉和变异，进而求得区间线性双层规划最优解。樊等人（2014）[10]提出了用双适应度函数评估遗传算法求解区间线性双层规划的算法，在一次运算中获得最好最优解和最差最优解。任爱红（2015）[11]利用最近区间近似将一类双层模糊规划问题转化为区间双层规划问题，求解了模糊双层规划问题。对于区间二次规划的研究，Liu等人（2007）[12]讨论了一次项系数具有区间系数的二次规划模型，利用对偶定理将区间规划转化为确定性规划问题，并给出了数值解法求解了模型的上界和下界。Li等人（2008）[13]在Liu的基础上提出了更具一般形式的区间二次规划模型，设计算法求解了模型的上界和下界。Li等人（2016）[14]提出了含有等式和不等式约束的区间二次规划模型，并提出了一种检验零对偶间隙简单有效的方法，最后利用该方法求得了区间二次规划模型的精确上界. 在實际问题中，随着递阶决策过程的复杂化，例如经济中价格的变动，物流中配送成本的变化，生产商实际需求量的变动，都会引起收益的变化，双层规划中的目标函数并非都是线性函数，单纯的区间线性双层规划模型和单层区间二次规划模型已经不能很好的解决这些问题，所以有必要研究区间非线性双层规划模型。目前，对区间二次-线性双层规划做出的研究还很少。在线性双层规划的基础上，提出一类上、下层目标函数系数以及约束条件系数均带区间数的二次-线性双层规划模型。首先给出区间二次-线性双层规划模型，并提出最好最优解的概念;然后借鉴区间线性双层规划求解最好最优解的方法和单纯形法的最优性条件，设计了求解区间二次-线性双层规划最好最优解的算法;最后给出数值算例，验证了模型和算法的有效性.
2 预备知识
6 结 论
在经济学和管理学中，二次双层规划模型的系数不能给出确定值的情况很普遍，从而采用区间数来估计系数的变化范围。物流网络、证券投资组合和资源配置分别是一个动态系统，是在不确定环境中发生的。提出的模型和算法，可以应用到物流网络中，解决物流中总成本最小和用户费用最低的非线性问题;也可以推广到证券投资市场中，使得投资组合中预期收益率提高和风险率降低;也可以进一步应用到水资源等配置问题中，解决调控水价的管理者和各用水部门利益最优问题，等等。在实际问题中，当涉及到不确定二次-线性双层决策时，上述的模型和算法均可应用到实际问题中，解决双层决策优化问题。区间二次-线性双层规划模型和算法的提出，打破了经济学和管理学中只用不确定线性双层规划模型解决实际问题的局限性，推动了非线性不确定双层规划的发展。但是，区间非线性双层规划的研究成果还很少，有待更多的学者在此领域做出更深入的研究.
参考文献
[1] 胡长英.双层规划理论及其在管理中的应用[M].北京：知识产权出版社，2012.
[2] nal H.A modified simplex approach for solving bi-level linear programming problems[J].European Journal of Operational Research，1993（67）：126-135.
[3] 王广民，万仲平，王先甲.二（双）层规划综述[J].数学进展，2007，36（5）：513-529.
[4] Strekalovsky A S，Orlov A V，Malyshev A V.Local search in a quadratic-linear bi-level programming problem[J].Numerical Analysis and Applications，2010，3（1）：59-70.
[5] Aihong REN，Yuping WANG，Fei JIA.A hybrid estimation of distribution algorithm and Nelder-Mead simplex method for solving a class of nonlinear bi-level programming problems[J].Journal of Applied Mathematics，2013（13）：1-10.
[6] 郭均鹏，吴育华.区间线性规划的标准型及其求解[J].系统工程，2003，21（3）：79-82.
[7] 郭均鹏，李汶华.区间线性规划的标准型及其最优值区间[J].管理科学学报，2004，7（3）：59-63.
[8] 王建忠，杜纲.区间线性双层规划的最好最优解[J].系统工程，2009，27（4）：100-103.
[9] Hecheng LI，Fang LEI.An efficient genetic algorithm for interval linear bi-level programming problems[J].Ninth International Conference on Computational Intelligence and Security，2013，41-44.
[10] 樊洋洋，李和成.一类区间系数线性双层规划问题的遗传算法[J].计算机应用，2014，34（1）：185-188.
[11] 任爱红.基于最近区间近似和区间规划方法求解一类模糊双层规划问题[J].模糊系统与数学，2015，29（4）：139-145.
[12] ST LIU，RT WANG.A numerical solution method to interval quadratic programming[J].Applied Mathematics and Computation，2007（189）：1274-1281.
[13] W LI，X TIAN.Numerical solution method for general interval quadratic programming[J].Appl.Math.Comput，2008（202）：589-595.
[14] Wei LI，Mengxue XIA，Haohao LI.Some results on the upper bound of optimal values in interval convex quadratic programming[J].Journal of Computational and Applied Mathematics，2016（302）：38-49.