一类多参数混合整数线性规划问题的计算研究
发布时间：2018-07-23 18:53
【摘要】：参数规划是含有连续变量、离散变量与参数的一类数学规划问题,该问题广泛应用于工程、经济、模型预测控制等领域,对此类问题的研究具有重要的理论意义及实际应用价值.多参数线性规划与多参数混合整数线性规划是参数规划的重要分支,本文针对这两类多参数线性规划的计算问题展开研究:第一部分在Rivotti[1]的多参数线性规划理论基础上,针对约束函数含有参数的多参数线性规划问题,构建了一种新的多参数线性规划算法(multi-parametric linear programming, MPLP).算法的基本思想是基于灵敏度理论,利用最优解的仿射表达式得到初始解,通过一组最优域系统地刻画参数空间,并且在参数空间内递归探索问题的解.通过三个数值算例证明MPLP算法的有效性.第二部分考虑约束函数含有参数的多参数混合整数线性规划问题的计算.把问题分解成混合整数线性规划主问题与多参数线性规划子问题,算法在主问题与子问题之间迭代,直至主问题不可行终止.数值结果表明算法是有效的.
[Abstract]:Parametric programming is a kind of mathematical programming problem with continuous variables, discrete variables and parameters. This problem is widely used in engineering, economy, model predictive control and other fields. The study of this kind of problems has important theoretical significance and practical application value. Multi-parameter linear programming and multi-parameter mixed integer linear programming are important branches of parameter programming. In this paper, the computational problems of these two kinds of multiparameter linear programming are studied. The first part is based on Rivotti's theory of multi-parameter linear programming. A new multi-parameter linear programming algorithm (multi-parametric linear programming, MPLP).) is proposed to solve the problem of multi-parameter linear programming with constraint functions. The basic idea of the algorithm is based on the sensitivity theory, using the affine expression of the optimal solution to obtain the initial solution, and systematically characterizing the parameter space through a set of optimal domains, and recursively exploring the solution of the problem in the parameter space. The effectiveness of MPLP algorithm is proved by three numerical examples. In the second part, we consider the computation of mixed integer linear programming problem with multiple parameters. The problem is decomposed into mixed integer linear programming main problem and multi-parameter linear programming subproblem. The algorithm iterates between the main problem and the subproblem until the main problem is infeasible. Numerical results show that the algorithm is effective.
【学位授予单位】：湘潭大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O221.4
本文编号：2140336
[Abstract]:Parametric programming is a kind of mathematical programming problem with continuous variables, discrete variables and parameters. This problem is widely used in engineering, economy, model predictive control and other fields. The study of this kind of problems has important theoretical significance and practical application value. Multi-parameter linear programming and multi-parameter mixed integer linear programming are important branches of parameter programming. In this paper, the computational problems of these two kinds of multiparameter linear programming are studied. The first part is based on Rivotti's theory of multi-parameter linear programming. A new multi-parameter linear programming algorithm (multi-parametric linear programming, MPLP).) is proposed to solve the problem of multi-parameter linear programming with constraint functions. The basic idea of the algorithm is based on the sensitivity theory, using the affine expression of the optimal solution to obtain the initial solution, and systematically characterizing the parameter space through a set of optimal domains, and recursively exploring the solution of the problem in the parameter space. The effectiveness of MPLP algorithm is proved by three numerical examples. In the second part, we consider the computation of mixed integer linear programming problem with multiple parameters. The problem is decomposed into mixed integer linear programming main problem and multi-parameter linear programming subproblem. The algorithm iterates between the main problem and the subproblem until the main problem is infeasible. Numerical results show that the algorithm is effective.
【学位授予单位】：湘潭大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O221.4
【参考文献】
相关期刊论文 前7条
1 郝建根;侯忠生;柳向斌;;基于多参数规划的单交叉口排队长度均衡控制[J];控制与决策;2013年04期
2 霍永亮;刘三阳;;非线性参数规划问题ε-最优解集集值映射的连续性[J];系统科学与数学;2009年06期
3 霍永亮;;参数规划最优值函数的B-预不变凸凹性[J];工程数学学报;2006年05期
4 侯为根;一类参数规划问题最优解的结构及其应用[J];安徽工业大学学报;2001年03期
5 贾雨文;王容;李冬梅;;多参数线性规划[J];河北机电学院学报;1993年03期
6 游兆永;安和平;;参数规划中最优值函数的ε-凹凸性[J];应用数学;1991年03期
7 游兆永,安和平;参数规划中最优值函数的拟凹性[J];上海第二工业大学学报;1988年03期
，本文编号：2140336
本文链接：https://www.wllwen.com/kejilunwen/yysx/2140336.html
