极大代数上的双边线性系统的优化

项目名称： 极大代数上的双边线性系统的优化

项目编号： No.61203131

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 自动化学科

项目作者： 李平科

作者单位： 清华大学

项目金额： 23万元

中文摘要： 极大代数上的线性系统理论是离散事件系统分析和控制以及模糊控制系统设计的重要工具。极大代数上的线性系统的优化问题是最近的一个研究热点，目前，一些基本问题，特别是双边线性方程的求解与优化，仍未完全解决。对于这些问题的研究有助于加深理解一些可由离散事件系统和模糊控制系统建模的非线性系统的本质。本项目着眼于具有通常意义下的线性和二次型目标函数的双边线性方程约束的优化问题，根据其结构特点引入新的变量体系进行分解和重构，将原问题转化成线性或非线性的混合整数规划模型从而设计相应的算法求得全局最优解或者近似最优解。另一方面，本项目还将探索双边线性方程约束的优化问题与单边线性方程求近似解之间的联系，进而设计单边线性方程近似求解的算法。此外，还将探讨当目标函数具有"格线性"形式的时候，相应的优化问题是否存在多项式时间算法。

中文关键词： 极大代数；线性系统；模糊关系方程；整数优化；

英文摘要： The theory of linear systems over max algebra provides important tools for the analysis and control of discrete event systems and the design of fuzzy control systems. The optimization of linear systems over max algebra has attracted much attention in recent years, where some basic problems, particularly those constrained by two-sided linear equations, have not been completely solved. The study of these problems would advance our understanding of the nature of some nonlinear systems that can be modeled by discrete event systems or fuzzy control systems. In this research project, we will focus on solving two-sided linear equation constrained optimization problems with linear or quadratic objective functions in usual sense. By introducing new variables to characterize the structure of a system of two-sided linear equations via decomposition and reconstruction, the original optimization problems may be transformed into linear or nonlinear mixed integer programming problems and then solved or approximately solved by specifically designed algorithms. We will also explore the connection between the two-sided linear equation constrained optimization problems and the problem of obtaining approximate solutions of one-sided linear equations, and subsequently solve this problem in the framework of two-sided linear equation

英文关键词： max algebra；linear systems；fuzzy relational equations；integer optimization；