带约束情形离散切换系统的最优调度

Optimal Scheduling of Discrete Switched Systems with Constraints

在动力系统中,切换系统的最优调度问题是典型的NP难问题,考虑了一种离散时间情形下带约束的线性离散切换系统,为了寻找到全局最优解,分析了系统的动态结构特征和动态约束条件,分别构造了目标函数和约束条件的动态下界;在各个阶段将当前最优值作为系统的上界,通过上下界的比较,提出了一种适应于动力系统的分支定界算法,方法能够精确地搜索到动态系统的全局最优解;数值结果表明:方法是有效的,而且能够搜索到全局最优解.

In dynamic systems,optimal switching for switched systems is a typical NP-hard problem in discrete time,this paper considers a class of linear switched systems with constraints. In order to find the global optimal solution,by analyzing the dynamic constraint and the linear performance of the system,we construct the dynamic lower bounds of the constraint and the objective function,respectively. These lower bounds provide an accelerated rule for tree search methods. Therefore,a depth-first branch and bound algorithm are proposed. The method can exactly find the global optimal solution of the dynamic system. The numerical experiment shows the effectiveness and efficiency of the proposed method.