【作者】 王初；

【导师】 吴育华；

【作者基本信息】 天津大学 ， 管理决策与运筹技术， 2004， 博士

【摘要】 项目集合选择问题可以表述为这样一类问题：存在一个含有限项目的备择项目集合，其中每个项目都具有两方面的属性，既耗费一定量的各种资源，又在多个目标上具有产出。那么如何在给定的资源约束下确定一个最优的项目组合，使得该项目组合给决策者带来最大的效用。项目集合选择问题涉及了经济管理领域、工程建设领域、工业生产领域的诸多方面。如投资决策中的投资组合设计，信息化建设中的方案设计，公共财政中的预算制订以及工程建设中的项目优化都离不开项目集合选择理论的支持。但是现有关于项目集合选择的理论研究还比较薄弱，绝大多数研究都只是局限于可表示为线性规划形式的一些简单问题，还远远不能满足实际问题求解的需要。针对这一缺陷，在分析和总结项目集合选择问题一般理论框架的基础上，本文从非线性项目集合选择问题的求解、相关性项目集合选择问题的求解、项目集合选择问题的非参数方法以及序数型指标项目集合选择问题的解法四个方面对项目集合选择的理论进行了一些扩展研究，其具体内容如下： 文章的第一章介绍了项目集合选择问题的定义、一般数学形式以及规划形式，给出了项目集合选择问题求解的一般步骤和常用解法。并且依据项目集合选择问题目标函数和约束条件的特点，构建了项目集合选择问题的分类体系。从整体上研究了项目集合选择问题的一般理论框架。并在分析相关理论的国内外研究现状和缺陷的基础上，给出了本文的研究意义，研究内容、研究思路和主要创新点。随后，文章的第二章分析了投资方案组合选择问题的非线性特性，建立了该类问题的动态规划模型。在此模型的基础上文章给出了基于外点法求解此类问题的改进贪婪搜索算法。并研究了采用surrogate松弛模型确定初始点和运用改进的贪婪算法搜索最优解的具体实现方法，给出了实现算法的具体步骤。在文章第三章中，文章讨论了备择项目之间的相关性对项目集合选择问题的最终结果的影响。并构建了一个改进的项目相关性的定义和度量体系。在此相关性定义体系的基础上，文章构建了相关性条件下项目集合选择问题的非线性模型，并给出了非线性模型的线性化方法和具体的算例。在第四章中，文章分析比较了多目标项目集合选择问题的两类求解方法：参数方法和非参数方法，讨论了参数方法的缺陷。在此基础上，文章提出了多目标项目集合选择问题DEA解法的基本思路，并给出了相应的求解多目标项目集合选择的DEA模型。另外，文章利用第三章中关于相关性项目选择问题建模的有关成<WP=3>果，提出了相关性条件下项目集合选择的DEA方法和模型。许多实际的项目集合选择问题中常常含有序数型的指标，对于这类序数型指标项目集合选择问题，目前还缺乏成熟的解法。对此，在第五章中，文章提出了一种“通过建立序数指标评价模型，将序数型指标项目集合选择问题转化为基数型项目集合选择问题，然后求解”的基本思路。并给出了具体的模型和算例。以上是对项目集合选择问题的一些理论探讨。另外，项目集合选择问题具有一个特性，就是问题的可行解数目随着初始备择项目集合中元素个数的增加呈指数式增长。减少备择项目个数是减少项目集合选择问题计算复杂度的有效手段。文章结合项目集合选择问题的特点改进了单项目选优问题筛选方法中的“有效”，“支配”等概念，提出了“最优筛选”的概念，并在此基础上建立了项目集合选择问题的筛选规则和筛选模型，给出了计算实例。更多还原

【Abstract】 Subset selection problem can be described as: There is a set including limited amount of projects, which have two features, consuming a certain amount of resources and output a certain amount of outcome in given objects. Then how to determine a optimal portfolio of projects, which can maximize the utility of decision-maker, within a given resource constraints. Various fields, including economics management, project construction, industry production, etc., are involving with subset selection problem. For instance, the investment portfolio design in the field of investment decision making, the plan design in the field of information system construction, budgeting problem in the field of public finance and projects optimization in the field of project construction are only a part of the applications of subset selection theory. Nevertheless, the researches on subset selection theory are considerable deficient, and most of them are limited to linear programming form. These researches cannot meet the demand of solving practical problems. Aiming at these weaknesses, the study on non-linear subset selection problem, subset selection problem with interdependence, the non-parametric method for subset selection problem and subset selection problem with ordinal criteria is addressed in this dissertation, based on the analysis and summarizing the general theory framework of subset selection problem.The conception, definition, general mathematic form, and programming form of subset selection problem are addressed in the first chapter of the dissertation. Then, according to the feature of objective function and the constraints, the classification system of the subset selection problem is constructed. The overall theory framework of subset selection theory is introduced. In accordance with the weakness of the researches on the subset selection problem, the purpose, content, outline and innovation of the dissertation is given. Then, based on the analysis of the non-linear feature of the investment portfolio selection problem, a dynamic programming model is formulated. After that, an exterior point heuristic algorithm is constructed to solve the model. The surrogate model to determine original point and advanced greedy search algorithm to obtain optimal point are discussed, and the whole processes of the algorithm are addressed. <WP=5>In the third chapter, the crucial effect of the interdependence among the projects is discussed. And a group of definitions and theorems is given to build a definition and measurement system of interdependence phenomena. After that, a non-linear programming model of subset selection problem with interdependence is formulated, and the linearization method for the non-linear model is given. Finally, an application of the model is given.In the fourth chapter, two methods for solving multi-objective subset selection problem: parametric and nonparametric are compared, and the shortcoming of parametric method is analyzed. Based on these, the general idea of the DEA model to solve multi-objective subset selection problem is proposed and corresponding model is constructed. After that, utilizing the outcome of the chapter three, a DEA model to solve subset selection problem with interdependence is formulated. Ordinal criteria are often used in many practical subset selection problems. There are scarce effective methods to solving this kind of problems. Aiming at this, an idea to solve the problems is proposed. That is transforming the subset selection problem with ordinal criteria to the problem with cardinal criteria and then solving the problem. Finally the concrete model and an application are given. Some theoretical study is give hereinbefore. After that, one feature of the subset selection problem, which is that the number of feasible solutions of the subset selection problem will exponentially increase with the increase of the number original projects for selection. So, the most effective way to decrease the computer complexity of the subset selection problem is eliminating the origin更多还原