两类多目标二层规划问题的数值求解方法

发布时间：2018-05-12 07:47

本文选题：多目标二层规划 + 罚函数　；参考：《长江大学》2016年硕士论文

【摘要】：二层规划问题为一类具有两层阶梯结构的系统决策问题,在该问题的数学模型中,包含了具有不同目标函数与约束条件的上,下两层优化问题.他们既彼此独立,又相互影响.具体表现为：上层问题的约束条件与下层问题的最优解密切相关,下层问题的最优解又受上层给定的决策变量所影响.因为二层规划问题为一类NP-hard问题,所以其在基础理论和求解算法上的发展都较为缓慢,但这并没有影响它在各种实际问题中的应用.目前为止,二层规划问题已经被广泛应用于各种生活领域.如市场竞争,环境保护,交通网设计,资源分配,物流管理,价格控制等.本文在已有的研究基础上,首先对二层规划问题的理论及算法的发展作了简短的综述,然后介绍了与本文研究内容相关的基础知识,最后针对两类多目标二层规划问题,设计了相应的数值求解算法,并通过相关数值实验检验了算法的可行性.论文主要安排如下.第一章简要的介绍了二层规划问题的数学模型,并从理论算法和实际应用两个方面介绍了二层规划问题的研究背景及发展现状.在理论算法上介绍了求解二层规划问题的几种常用方法.包括罚函数法,极点搜索法,智能求解算法,分支定界法等.并对上述方法的求解思路及优缺点作了简单的概括与总结.在实际应用方面介绍了二层规划问题在交通和管理中的应用.最后介绍了本文各章节的具体安排.第二章给出了与本文相关的一系列预备知识,具体内容包括：相关的数学概念,如闭集,凸集,连续函数,可微函数,局部极小(大)值点等；线性及非线性二层规划的数学模型及其解的性质；多目标优化问题的数学模型,最优性条件及主要目标求解方法；模糊集概念及确定隶属函数的方法.为第三,四章求解多目标二层规划问题提供理论依据.第三章针对上层是多目标下层是单目标的一类非线性多目标二层规划问题,设计了主要目标求解法.第一节给出了此类二层规划问题的数学模型及pareto-最优解的概念,并对该模型中的相关变量作了简要说明.第二节在假设下层问题为凸规划问题的基础上,利用下层问题的K-T最优性条件,将原多目标二层规划问题转化为带互补约束的多目标优化问题.将多目标优化问题的互补约束条件作为罚项,构造该多目标规划问题的罚问题.通过证明该罚问题的收敛性可知该罚问题的pareto-最优解一定是原问题的pareto-最优解.随后设计了求解该罚问题的主要目标法,并给出了详细的求解步骤.第三节通过求解相关算例,可证明本文所设计的主要目标求解法是有效且可行的.第四节总结了该算法的优点与不足.第四章针对上层是单目标,下层是多目标的一类线性多目标二层规划问题,即半向量二层规划问题.设计了模糊决策求解法.求解思路为：首先,利用线性加权法将下层多目标规划转化为单目标优化问题,可则将半向量二层规划问题转化为单目标二层规划问题.其次,利用模糊集理论,构造对应的隶属函数用于描述上,下两层目标函数的满意度.然后,构造新的模糊目标评价函数,并在此基础上给出了该模糊决策求解法的具体求解步骤.相关数值实验可证明：本章所设计的模糊决策法是可行的.第五章分析总结了本文所设计的两种算法的优缺点.
[Abstract]:The two layer programming problem is a class of system decision-making problem with two layers of ladder structure. In the mathematical model of the problem, it contains the upper and lower two layers of optimization problems with different objective functions and constraints. They are independent and mutual influence. The concrete performance is that the constraints of the upper questions and the optimal solution of the lower level are closely related. The optimal solution of the lower level problem is influenced by the decision variables of the upper level. Because the two layer programming problem is a class of NP-hard problems, the development of the basic theory and the solution algorithm is slow, but it does not affect its application in various practical problems. So far, the two layer planning problem has been widely used. In various fields of life, such as market competition, environmental protection, traffic network design, resource allocation, logistics management, price control, etc. This paper, based on the existing research, makes a brief overview of the theory and algorithm development of the two layer planning problem, and then introduces the basic knowledge related to the content of this study, and finally to the two categories. The corresponding numerical solution algorithm is designed for the target two layer programming problem, and the feasibility of the algorithm is tested by the relevant numerical experiments. The thesis is mainly arranged as follows. The first chapter briefly introduces the mathematical model of the two layer planning problem, and introduces the research background and development of the two layer planning problem from two aspects of the theoretical algorithm and the practical application. In the theoretical algorithm, some common methods for solving two layer programming problems are introduced, including the penalty function method, the pole search method, the intelligent solution algorithm, the branch and bound method and so on. The solution ideas and advantages and disadvantages of the above methods are briefly summarized and summarized. The two layer planning problems are introduced in traffic and management in practical application. The second chapter gives a series of preparatory knowledge related to this article. The specific contents include: related mathematical concepts, such as closed sets, convex sets, continuous functions, differentiable functions, local minimum (large) value points, linear and nonlinear two layer programming mathematical models and their solutions. The mathematical model of the objective optimization problem, the optimality condition and the main objective solution method, the fuzzy set concept and the method of determining the membership function, provide the theoretical basis for the third, fourth chapter to solve the multi-objective two layer programming problem. The third chapter is designed for a class of nonlinear multi-objective two layer programming problems with a multi objective lower layer is a single objective. The first section gives the mathematical model of the two layer programming problems and the concept of pareto- optimal solution, and gives a brief description of the related variables in the model. The second section, on the basis of the assumption that the lower level is a convex programming problem, uses the K-T optimality condition of the lower level problem to turn the original multiobjective two layer programming problem into a problem. The multi objective optimization problem with complementary constraints is transformed into a penalty term of the complementary constraint condition of the multi-objective optimization problem, and the penalty problem of the multi-objective programming problem is constructed. By proving the convergence of the penalty problem, it is known that the pareto- optimal solution of the penalty problem must be the best solution of the original problem. Then the main solution to the penalty problem is designed. The third section can prove that the main objective solution method of this paper is effective and feasible. The fourth section summarizes the advantages and disadvantages of the algorithm. The fourth chapter is a class of linear multi-objective two layer programming problem with a single objective and the lower layer is multiobjective, that is, half The problem of fuzzy decision solving is designed. The solution method is designed as follows: first, the linear weighted method is used to transform the lower multi-objective programming into a single objective optimization problem. The semi vector two layer programming problem can be transformed into a single target two layer programming problem. Secondly, the corresponding membership function is constructed by using the fuzzy set theory. The satisfaction of the next two layers of objective function is given. Then, a new fuzzy objective evaluation function is constructed, and on this basis, the concrete solution steps of the fuzzy decision solving method are given. The relevant numerical experiments prove that the fuzzy decision method designed in this chapter is feasible. The fifth chapter analyses the advantages and disadvantages of the two algorithms designed in this paper.

【学位授予单位】：长江大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O221

【相似文献】