双权网络中一些组合结构和限制性增广优化问题及其应用

项目名称： 双权网络中一些组合结构和限制性增广优化问题及其应用

项目编号： No.10861012

项目类型： 地区科学基金项目

立项/批准年度： 2009

项目学科： 轻工业、手工业

项目作者： 李建平

作者单位： 云南大学

项目金额： 25万元

中文摘要： 双权网络中的组合结构是网络理论研究的重要问题之一，在组合优化和其它学科分支中有广泛的应用。科学技术的进步极大地促进了图论、组合优化与其它学科的交叉，组合算法理论作为其应用基础倍受重视，已成为研究的热点之一。实际应用与理论研究中的一些基本问题常能转化为双权网络中好的组合结构和相关的优化问题。我们在该项目中着重研究了双权网络中好的组合结构和相关的优化问题，主要从图论和组合算法理论角度来建立相应的数学模型，特别是建立了双权网络上优化问题的数学模型，设计近似算法或随机算法来解决这些难问题，并分析其复杂性，利用计算机及相关的数学软件来进行辅助性模拟计算研究，达到启发式地思考、解决问题的目的；我们还利用得到的算法来研究了一些证券投资组合模型中的部分优化问题，取得一些研究成果,达到总的预期目标。该研究项目已经完成学术研究论文37篇，已正式发表31篇；我们以该研究项目作为平台，通过三年的努力，组建了图论与组合优化方向的研究队伍；共培养了1名博士后，3名博士，24名硕士，目前还有5名博士研究生和19名硕士学位研究生在读。

中文关键词： 图论；组合优化理论；算法；限制性增广优化问题；插点优化问题

英文摘要： The study of combinatorial structures in double weighted networks is one of important topics in network theory, it has some wide applications in combinatorial optimization and other research fields. The science and technology progresses in many fields further accelerate the developments and intersections of graph theory, combinatorial optimization and other branches of science, theory of combinatorial algorithms as the key kernel are deeply studied and emphasized in the world, and it becomes to one of active interesting research themes. Some basic problems in the reality and scientific research fields are merged into some combinatorial structures and the related optimization problems in double weighted networks. In this project, we have deeply studied some combinatorial structures in double weighted networks and the related combinatorial optimization problems in such networks and others. On the aids of graph theory and combinatorial optimization theory to construct some mathematical models and utilizing some strategy and methods, we have designed some combinatorial (or approximation or randomization) algorithms to solve some important research topics, and then analysed the complexity of algorithms we designed. During our study in this project, we have simulated our results by utilizing computing software for the validation to solve some related problems. By utilizing some algorithms we designed, we have obtained the results concerning some optimization problems in investment models field. We have reached our achievement of this project as expected: we have not only finished 37 research papers, 31 of which have been publishable in some journals or some international conferences, but also we have established our team to do research in graph theory, combinatorial optimization problems and other research fields. With the aids of this project, we have supervised a postdoctoral fellow, 3 doctors who received their Ph.D degrees, and 24 graduate students who received their Master degrees, and now, there are still 5 Ph.D candidates and 19 graduate students who are taking part in their study programs.

英文关键词： graph theory; combinatorial optimization theory; algorithms; constrained-augmentation optimization problems; subdivision- optimization problems