On a rational stopping rule for facilities location algorithms

In the multifacility location problem, a number of new facilities are to be located so as to minimize a sum of weighted distances. Recently, a lower bound on the optimal value was developed, for use in deciding when to stop an iterative solution procedure. We develop a stronger bound that allows some computational savings.     

分组坐标轮换法与机械优化设计

minimax 问题是工程优化设计中普遍存在的问题。本文首次采用分组坐标轮换法求解该问题,通过分析获得了该算法收敛的充分条件(如果收敛,还可计算最大轮换次数)。一些数值计算验证了文中的结论,本文还把该算法用于四连杆实现函数机构的优化设计.     

A note on solving multifacility location problems involving euclidean distances

This note considers a recently proposed solution method for a multifacility location problem. It is shown that the method does not always produce an optimal solution.     

Location of regional facilities

In this paper we consider the single-facility and multifacility problems of the minisum type of locating facilities on the plane. Both demand locations and the facilities to be located are assumed to have circular shapes, and demand and service is assumed to have a uniform probability density inside each shape. The expected distance between two facilities is calculated. Euclidean and squared-Euclidean distances are discussed.     

基于改进欧几里得算法的卷积码快速盲识别算法

卷积码盲识别技术在信号截获、智能移动通信、多点广播通信等领域具有广泛应用,针对卷积码的快速盲识别问题,对经典欧几里得算法进行了改进,提出了一种基于改进欧几里得算法的卷积码的快速盲识别方法。算法对卷积码码率进行遍历,通过欧几里得迭代算法求解卷积的校验多项式,实现了任意码率卷积码的快速盲识别。对算法进行了仿真,仿真结果验证了算法的有效性,且算法的计算量小于文献中已有算法。     

minimax问题的广义共轭向量法

本文按照共轭向量法的理论,针对非奇异对称矩阵提出了广义共轭向量的概念,并论述了它的三个重要性质(线性独立性、可寻驻点和可扩展性)。在此基础上,构造了极小极大(minimax)问题的广义共轭向量法。理论分析表明,该算法具有二次终止性质,且在每一维搜索时具有确定的寻优特征(求极小或求极大)。该算法为用拉格朗日乘子法求解数学规划提供了一个可能的途径。计算实例表明该算法是有效的。     

Minimax and maximin facility location problems on a sphere

The problem dealt with in this article is as follows. There are n “demand points” on a sphere. Each demand point has a weight which is a positive constant. A facility must be located so that the maximum of the weighted distances (distances are the shortest arcs on the surface of the sphere) is minimized; this is called the minimax problem. Alternatively, in the maximin problem, the minimum weighted distance is maximized. A setup cost associated with each demand point may be added for generality. It is shown that any maximin problem can be reparametrized into a minimax problem. A method for finding local minimax points is described and conditions under which these are global are derived. Finally, an efficient algorithm for finding the global minimax point is constructed.     

Solution of minisum and minimax location–allocation problems with Euclidean distances

A new method for the solution of minimax and minisum location–allocation problems with Euclidean distances is suggested. The method is based on providing differentiable approximations to the objective functions. Thus, if we would like to locate m service facilities with respect to n given demand points, we have to minimize a nonlinear unconstrained function in the 2m variables x₁,y₁, ?,x_m,y_m. This has been done very efficiently using a quasi-Newton method. Since both the original problems and their approximations are neither convex nor concave, the solutions attained may be only local minima. Quite surprisingly, for small problems of locating two or three service points, the global minimum was reached even when the initial position was far from the final result. In both the minisum and minimax cases, large problems of locating 10 service facilities among 100 demand points have been solved. The minima reached in these problems are only local, which is seen by having different solutions for different initial guesses. For practical purposes, one can take different initial positions and choose the final result with best values of the objective function. The likelihood of the best results obtained for these large problems to be close to the global minimum is discussed. We also discuss the possibility of extending the method to cases in which the costs are not necessarily proportional to the Euclidean distances but may be more general functions of the demand and service points coordinates. The method also can be extended easily to similar three-dimensional problems.     

区间分解组合迭代算法用于非确定结构系统的静力区间分析

对于结构参数向量界限绝对离差较大的非确定结构系统,迭代计算收敛条件难以满足,修正迭代算法不能直接用于其区间有限元静力控制方程的求解。采用区问分解组合求解策略,考虑区间矩阵、向量元素间的相关性,直接对结构参数区间进行区间分解,将非确定结构系统区间有限元控制方程的求解转化为若干个子区间有限元静力控制方程的修正迭代求解,提出了一种求解过程可逆的区间分解组合迭代算法,用于结构参数向量界限绝对离差较大的非确定结构系统的静力区间分析。算例结果表明,该方法是有效的。     

Acceleration of the HAP approach for the multifacility location problem

This article considers the problem of locating multiple new facilities to minimize the cost function consisting of the sum of weighted distances among new facilities and between new and existing facilities. The hyperboloid approximate procedure (HAP) is probably the most widely used approach for solving this problem. In this article, an optimality condition for this problem is derived and a method to accelerate the convergence rate of the HAP for the case of Euclidean distances is presented. From the numerical results presented in this article, it can be concluded that the performance of the new algorithm is superior to the performance of the original HAP.     

Bounding methods for facilities location algorithms

Single- and multi-facility location problems are often solved with iterative computational procedures. Although these procedures have proven to converage, in practice it is desirable to be able to compute a lower bound on the objective function at each iteration. This enables the user to stop the iterative process when the objective function is within a prespecified tolerance of the optimum value. In this article we generalize a new bounding method to include multi-facility problems with l_p distances. A proof is given that for Euclidean distance problems the new bounding procedure is superior to two other known methods. Numerical results are given for the three methods.     

基于最小最大决策的三站时差定位布阵优化

提出了一种基于最小最大决策的三站时差定位布阵优化方法,以提高系统对目标区域的整体定位精度。应用基于最小最大决策的最优化理论,建立布阵优化问题的数学模型。该模型以三站坐标为决策变量,以目标区域的最大水平定位误差最小为目标函数,然后运用基于最小最大决策的最优化算法,求解模型的最优解,并将此最优解作为三站时差定位系统的最优布阵。仿真结果与理论计算一致,验证了这种布阵优化结果的最优性。     

超凸度量空间中KKM理论的一些应用

在超凸度量空间利用广义度量KKM映象原理的特性得到一类新的广义极大极小不等式,并进一步借助这类极大极小不等式,在更广泛的条件下,获得鞍点问题的一个新的存在性结果。     

Simple stability of general n- person games

Herein are introduced noncooperative points of n-person games defined on compact and convex sets in a Euclidean space and continuous payoff functions, which are natural extensions of the respective concepts of maximin, minimax strategies and saddle points of two-person games. The conc:ept of equilibrium point appears as a special of one of those. As a particular case, we examine such points for the mixed extension of finite n-person games; finally, a related topic is illustrated. These results represent the first installment of a collection which will be continued in subsequent publications.     

利用几何结构求解欧氏平面TSP的改进遗传算法

TSP是经典的组合优化问题。根据欧氏平面TSP最优环路的性质提出了子路径及相关的概念,利用点集凸壳设计了环路构造算法,并以点集Delaunay三角剖分图为启发信息设计了改进的遗传算法,通过中国144城市TSP等验证了算法的有效性。     

基于改进Markov模型软件测试策略

针对已有软件测试Markov模型与工程实践不符的情况，通过引入软件需求覆盖率改进Markov模型。在改进的Markov模型基础上，本文以软件测试过程中测试总代价最小为控制目标，采用交叉熵方法修正测试剖面，由优化测试剖面生成测试用例序列。仿真结果表明这种方法能够有效地降低软件测试总代价，是一种有效的软件测试方法。     

基于Lambert算法的脉冲精确变轨策略

Lambert问题的求解多以二体假设为基础,从而对精确轨道控制带来不利影响.提出了一种脉冲修正策略,建立了考虑摄动影响的航天器轨道动力学计算模型,在Iambert算法基础上,通过拟牛顿法对变轨脉冲进行修正,消除终端状态误差,从而获得精确的变轨脉冲.将该修正策略用于固定时间精确变轨问题,建立了两层规划模型,并通过算例验证了算法的有效性.     

基于最大信噪比的盲源分离雷达抗主瓣干扰方法

针对现有压制干扰从主瓣进入雷达天线,传统副瓣抗干扰方法失效的问题。提出一种应用最大信噪比准则的盲源分离抗主瓣干扰方法。首先提出了盲源分离应用于雷达抗主瓣干扰的模型,估计信号源个数后构建基于信噪比的目标函数,而后选择求解得到的广义特征向量构造分离矩阵。与传统算法相比,该方法不需要进行迭代运算,有效降低了计算复杂度。经过仿真分析,验证该方法能够有效分离混合信号,具有较高的分离效率。     

A multifacility capacity expansion model with joint expansion set-up costs

This article describes a multifacility capacity expansion model in which the different facility types represent different quality levels. These facility types are used to satisfy a variety of deterministic demands over a finite number of discrete time periods. Applications for the model can be found in cable sizing problems associated with the planning of communication networks. It is assumed that the cost function associated with expanding the capacity of any facility type is concave, and that a joint set-up cost is incurred in any period in which one or more facilities are expanded. The model is formulated as a network flow problem from which properties associated with optimal solutions are derived. Using these properties, we develop a dynamic programming algorithm that finds optimal solutions for problems with a few facilities, and a heuristic algorithm that finds near-optimal solutions for larger problems. Numerical examples for both algorithms are discussed.     

弹道导弹基本诸元的快速装订算法研究

应用牛顿迭代法实现了弹道导弹基本诸元的快速装订。推导了根据落点偏差求飞行程序角和发射方位角的牛顿迭代公式，设计了迭代算法，并给出了实际算例。考虑到迭代算法收敛速度与所给的迭代初值有一定的关系，提出了预先准备简易射表采用反插值算法为牛顿迭代法准备初值的方法，经计算表明可以大大减少迭代次数，从而实现标准弹道的快速设计。