Minimum time output regulation problem of linear discrete-time systems

This paper deals with the minimum time output regulation problem of finite-dimensional linear time-invariant discrete-time systems with an incomplete state observation. First, the necessary and sufficient condition is obtained for the existence of controllers which regulate the system for any arbitrary initial state to a certain given subspace in finite steps. Then, the minimum time is obtained in which the system satisfying the above conditions can be regulated, and a minimum time regulating controller is designed. These are obtained by the geometric approach which is a powerful tool for the investigation of the structural property of linear systems.     

Approximating the Minimum Chain Completion problem

A bipartite graph G=(U,V,E) is a chain graph [M. Yannakakis, Computing the minimum fill-in is NP-complete, SIAM J. Algebraic Discrete Methods 2 (1) (1981) 77–79] if there is a bijection such that Γ(π(1))Γ(π(2))Γ(π(|U|)), where Γ is a function that maps a node to its neighbors.We give approximation algorithms for two variants of the Minimum Chain Completion problem, where we are given a bipartite graph G(U,V,E), and the goal is find the minimum set of edges F that need to be added to G such that the bipartite graph G^′=(U,V,E^′) (E^′=EF) is a chain graph.     

Minimum spanning tree problem of uncertain random network

Minimum spanning tree problem is a typical and fundamental problem in combinatorial optimization. Most of the existing literature is devoted to the case with deterministic or random weights. However, due to lack of data, a proportion of edge weights have to be estimated according to experts’ evaluations, which may be considered as uncertain variables. This paper focuses on the case where some weights are random variables and the others are uncertain variables. The concept of an ideal chance distribution is introduced and its expression is given based on the uncertainty distributions and probability distributions. A model is formulated to find a minimum spanning tree whose chance distribution is the closest to the ideal one. Finally, a numerical example is given to illustrate the modelling idea of the study.     

模糊环境下的最小权顶点覆盖问题*

最小权顶点覆盖问题在实际决策中应用广泛,但顶点上的权值在实际应用中通常代表费用、成本等,在很多情况下是不确定的。关注了最小权顶点覆盖问题中的模糊不确定性,对模糊环境下的最小权顶点覆盖问题进行了研究。引入了可信性理论以描述模糊不确定性,并根据不同的决策准则建立了求解模糊环境下最小权顶点覆盖问题的三个决策模型,结合模糊模拟和遗传算法设计了一种求解所建立模型的混合智能算法,并给出了数值实验。数值实验的结果验证了所提出的决策模型与算法的有效性。     

求解多目标最小生成树的一种新的遗传算法

在改进的非支配排序遗传算法（NSGA-II）的基础上,提出了一种新的基于生成树边集合编码的繁殖算子求解多目标最小生成树问题的遗传算法。通过快速非支配排序法,降低了算法的计算复杂度,引入保存精英策略,扩大采样空间。实验结果表明：对于多目标最小生成树问题,边集合编码具有较好的遗传性和局部性,而且基于此繁殖算子的遗传算法在求解效率和解的质量方面都优于基于PrimRST的遗传算法。     

Minimum time control problems for non-autonomous differential equations

In this paper, we investigate a minimum time problem for controlled non-autonomous differential systems, with dynamics depending on the final time. The minimal time function associated to this problem does not satisfy the dynamic programming principle. However, we will prove that it is related to a standard front propagation problem via the reachability function. Two simple numerical examples are given to illustrate our approach.     

Minimum energy control of systems with time delay

The problem of minimizing the cost functional corresponding to minimum control energyI = intmin{0}max{infty}u^{2} dtfor the linear system with delaydot{x}(t) = Ax(t) + Bx(t - h) + cu(t)is considered. From sufficient conditions for optimality, one obtains a set of algebraic equations. Numerical solution of these equations yields the optimal control law.     

Minimum time loop maneuver with no speed loss

A problem of how to move the center of gravity of the maneuverable aircraft from one given point in the three-dimensional space to another point as quickly as possible with the fixed vectors of the respective velocities is considered. Numerical solutions for coinciding initial and final conditions for trajectories entirely lying in the vertical plane are found. The solution is shown to be non-unique in the general case, with the change of the sign of curvature of the best trajectory being possible. Locally optimal solutions are found. The problem that takes into account the restriction on the sign of curvature of the trajectory is considered, with the respective optimal controls obtained both for fixed and free end point. Examples are given for cases when the velocity vector equals the initial one at the end of motion.     

A synthesis of statistical and deterministic methods in problem of smoothing for time series

In article the minimization problem of the residual for Euler-MacLaurin formula are solved. The solution is used for determination of parameters of a window of sliding summation in smoothing of time series. Results of numerical experiments are given.     

Minimum cost source location problem with local 3-vertex-connectivity requirements

Let G=(V,E)$G=(V,E)$ be a simple undirected graph with a set V$V$ of vertices and a set E$E$ of edges. Each vertex v∈V$v\in V$ has a demand d(v)∈_Z+$d\left(v\right)\in Z_{+}$ and a cost c(v)∈_R+$c\left(v\right)\in R_{+}$, where _Z+$Z_{+}$ and _R+$R_{+}$ denote the set of nonnegative integers and the set of nonnegative reals, respectively. The source location problem with vertex-connectivity requirements in a given graph G$G$ requires finding a set S$S$ of vertices minimizing _∑v∈Sc(v)${\sum }_{v\in S}c\left(v\right)$ such that there are at least d(v)$d\left(v\right)$ pairwise vertex-disjoint paths from S$S$ to v$v$ for each vertex v∈V−S$v\in V-S$. It is known that if there exists a vertex v∈V$v\in V$ with d(v)≥4$d\left(v\right)\ge 4$, then the problem is NP-hard even in the case where every vertex has a uniform cost. In this paper, we show that the problem can be solved in O(|V|⁴log²|V|)$O\left({\left|V\right|}^4{log}^2\left|V\right|\right)$ time if d(v)≤3$d\left(v\right)\le 3$ holds for each vertex v∈V$v\in V$.     

遗传算法和单体型组装加权最小字符翻转问题

单体型组装加权最小字符翻转（WMLF）问题指定个体联配的加权DNA片断数据,翻转权值和最小的SNP位点以推测出该个体的一对单体型。该问题是NP-难的,至今尚无实用的搜索寻优算法。根据DNA测序片段数据的特点提出了一种遗传算法。对于实际的生物实验数据,即使数据很大,该算法也可以在较短的时间得到WMLF问题的满意解,具有良好的可扩展性和较高的实用价值。     

Minimum of power consumption in the problem of oscillation damping

Consideration was given to minimization of the L ¹-norm of control of the linear oscillatory system. For consumption of the energy resources required to damp oscillations, bilateral estimates were obtained.     

Minimum cost source location problem with vertex-connectivity requirements in digraphs

Given a digraph (or an undirected graph) G=(V,E) with a set V of vertices v with nonnegative real costs w(v), and a set E of edges and a positive integer k, we deal with the problem of finding a minimum cost subset SV such that, for each vertex vV−S, there are k vertex-disjoint paths from S to v. In this paper, we show that the problem can be solved by a greedy algorithm in time in a digraph (or in time in an undirected graph), where n=|V| and m=|E|. Based on this, given a digraph and two integers k and ℓ, we also give a polynomial time algorithm for finding a minimum cost subset SV such that for each vertex vV−S, there are k vertex-disjoint paths from S to v as well as ℓ vertex-disjoint paths from v to S.     

对时间序列查询的最优小波误差估计

使用小波变换缩减维度是解决高维时间序列查询的一个有效方法。传统的算法均使用变换后小波序列的前k个系数作为原始时间序列的一个近似估计。但是由于选择前k个系数不一定能很好地近似原始序列集合。给出相关定理，说明选择小波系数集合的列平方和最大的k列，可以更好近似原始序列集合。实验结果表明，相对于传统算法，该方法可以更好地缩小相对误差。     

Minimum time thrust start-up of a nuclear rocket with integro-differential constraints

The minimum time thrust start-up of a nuclear rocket gives rise to an optimal control problem where the state representing the exhaust propellant must satisfy an integro-differential equation and an inequality constraint.     

基于最小完成时间的车载边缘计算任务流卸载策略

为在具有不稳定网络拓扑结构的车载边缘环境下实现车载任务的顺利卸载,提出一种基于动态优先级的最早完成时间卸载策略.根据车辆的速度、位置以及周围资源的使用状态等多种实时的信息筛选出可用卸载资源,以任务自身属性与可用资源的实际匹配程度作为基础为任务选择合适的卸载策略,实现任务流的完成时间最小化.实验结果表明,与其它策略相比,提出策略可以有效降低任务流的完成时间.     

The synthesis problem of Petri nets

The synthesis problem of concurrent systems is the problem of synthesizing a concurrent system model from sequential observations. The paper studies the synthesis problem for elementary Petri nets and transition systems. A characterization of the class of transition systems which correspond to elementary Petri nets is proven. It is shown how to generate all elementary Petri nets corresponding to a given transition system. If there is any such elementary Petri net, it is proven that there always exists a small one which has only polynomially many elements in the size of the transition system. Received October 5, 1992 / April 11, 1995