一类多商品设施选址问题的基于线性松弛解的启发式方法

多商品设施选址问题是众多设施选址问题中一类重要而困难的问题.在这一问题中,顾客的需求可能包含不止一种商品.对于大规模问题,成熟的商业求解器往往不能在满意的时间内找到高质量的可行解.研究了无容量限制的单货源多商品设施选址问题的一般形式,并给出了应用于此类问题的两个启发式方法.这两个方法基于原选址问题的线性规划松弛问题的最优解,分别通过求解紧问题和邻域搜索的方式给出了原问题的一个可行上界.理论分析指出所提方法可以实施于任意可行问题的实例.数值结果表明所提方法可以显著地提高求解器求解此类设施选址问题的求解效率.     

基于创新教育理念的问题解决策略

1.引言在河南省教育学会的大力支持下,我们成立了河南省教育学会创新教育专业委员会,我们对创新教育的研究可以说是刚刚起步.创新教育是以培养学生创新精神和创新能力为基本价值取向的教育.在高中数学教学中如何培养学生的创新意识、创新精神和创新能力是我们专业委员会重点研究的一个课题.当代美国著名数学家哈尔莫斯(P.R.Halmos)曾说:问题是数学的心脏.那么从某种意义上可以进一步说,数学学习的实质就是问题解决.基于创新教育理念,高中数学教学应该通过问题的提出、问题的分析、问题的讨论、问题的解决、问题的运用、问题的发展、问题的反思等七大环节来展开,从而推进整个数学学习过程,以培养学生的创新意识、创新精神和创新能力.本文重点研究了问题意识的培养、问题解决的思路、问题设计的原则、问题解决的误区.     

数学家货郎问题的计算复杂性研究

货郎问题(TSP)是研究计算复杂性理论的经典问题.在货郎问题的基础上,提出"数学家货郎问题"(MTSP).经过研究发现,数学家货郎问题是一个典型的NP类问题,但它却不属于P类问题.因此,数学家货郎问题是一个NP类问题与P类问题不相等的例证.     

基于遗传算法的大学课程表问题研究

课程表问题是时间表问题之一 ,也是 NP难问题 .根据大学授课形式的特点建立了大学课程表问题的数学模型 ,给出了求解该问题的遗传算法 .根据模型和大学课程表问题的特点设计了一种全新的编码 ,提出了一种新形式的交叉方式 .实验结果表明该方法是可行和有效的 .     

空中加油问题的递推模型与调度策略

首先对空中加油问题进行了分析,提取了相关性质,在此基础上建立了问题的递推模型.根据该模型,提出了一种启发式搜索算法.该算法计算复杂度低,适用性好.对应于辅机是否可以多次起飞,该算法分为两子算法.对这两种不同情况下的具体问题,设计了相关的优化函数.所有算法都在计算机中运行,并得到了相应结果.值得指出的是,提出的启发式搜索算法十分高效.对于问题1和问题2,该算法所得解是约束条件下的最优调度策略.对于问题3,问题4,问题5,该算法所得解逼近最优调度策略.     

求线性比试和问题的确定性全局优化算法

为求线性比试和问题的全局最优解,本文给出了一个分支定界算法.通过一个等价问题和一个新的线性化松弛技巧,初始的非凸规划问题归结为一系列线性规划问题的求解.借助于这一系列线性规划问题的解,算法可收敛于初始非凸规划问题的最优解.算法的计算量主要是一些线性规划问题的求解.数值算例表明算法是切实可行的.     

惠更斯的5个概率问题

摘要:惠更斯在第一部概率论著作Ⅸ论赌博中的计算》中提出5个概率问题,但均无求解过程.这5个问题既可看作实际问题,又可看作该书中命题的延伸.这些问题以机会问题为研究对象,把赌博问题的分析提升到一定的理论高度.这就为概率论的进一步发展奠定了坚实基础.本文尝试以惠更斯的方法来解决这些问题,再对比今日所用之法,从中得到若干结论.     

求解椭圆方程柯西问题的修正吉洪诺夫正则化方法

研究了一类变系数椭圆方程的柯西问题,这类问题出现在很多实际问题领域.由于问题的不适定性,不可能通过经典的数值方法来求解上述问题,必须引入正则化手段.采用了一种修正吉洪诺夫正则化方法来求解上述问题.在一种先验和一种后验参数选取准则下,分别获得了问题的误差估计.数值例子进一步显示方法是稳定有效的.     

不等式恒成立问题中的求参策略

不等式恒成立问题是高考中经常遇到的一类问题,此类问题的应用也相当广泛.但是面对此类问题,同学们往往束手无策,难以顺利解决.现结合实例谈谈不等式恒成立问题中的求参策略.     

一类耦合的有限元-边界元变分不等式的预条件子

本文主要研究一类Signorini 接触条件的非线性传输问题. 这类问题可以用耦合的有限元- 边界元变分不等式来描述. 我们首先提出一种求解变分不等式的预处理梯度投影法. 然后对离散系统构造了有效的区域分解预条件子. 该预条件子能够使耦合的不等式问题分解成等式问题和小规模的不等式问题, 并且这些问题可以并行求解. 最后我们详细研究了该迭代方法的收敛性.     

A Stochastic/Perturbation Global Optimization Algorithm for Distance Geometry Problems

We present a new global optimization approach for solving exactly or inexactly constrained distance geometry problems. Distance geometry problems are concerned with determining spatial structures from measurements of internal distances. They arise in the structural interpretation of nuclear magnetic resonance data and in the prediction of protein structure. These problems can be naturally formulated as global optimization problems which generally are large and difficult. The global optimization method that we present is related to our previous stochastic/perturbation global optimization methods for finding minimum energy configurations, but has several key differences that are important to its success. Our computational results show that the method readily solves a set of artificial problems introduced by Moré and Wu that have up to 343 atoms. On a set of considerably more difficult protein fragment problems introduced by Hendrickson, the method solves all the problems with up to 377 atoms exactly, and finds nearly exact solution for all the remaining problems which have up to 777 atoms. These preliminary results indicate that this approach has very good promise for helping to solve distance geometry problems.     

A Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem

This paper presents an efficient solution algorithm for the multiconstraint zero-one knapsack problem through a branch and bound search process. The algorithm has been coded in FORTRAN; and a group of thirty 5-constraint knapsack problems with 30-90 variables were run on IBM 360/75 using two other codes as well, in order to compare the computational efficiency of the proposed method with that of the original Balas and an improved Balas additive algorithms. The computational results show that the proposed method is markedly faster with regard to the total as well as the individual solution times for these test problems, and such superiority becomes more evident as the number of variables and the difficulty of the problems increase. The results also indicated that the original Balas method is extremely inefficient for the type of problems being considered here. The total solution time for the thirty problems is 13 min for the proposed method, 109 min for the improved Balas algorithm, and over 380 min for the original Balas algorithm. Extension of the solution algorithm to the generalized knapsack problem is also suggested.     

An approach to singular perturbation problems insoluble by asymptotic methods

Singular perturbation problems not amenable to solution by asymptotic methods require special treatment, such as the method of Carrier and Pearson. Rather than devising special methods for these problems, this paper suggests that there may be a uniform way to solve singular perturbation problems, which may or may not succumb to asymptotic methods. A potential mechanism for doing this is the author's boundary-value technique, a nonasymptotic method, which previously has only been applied to singular perturbation problems that lend themselves to asymptotic techniques. Two problems, claimed by Carrier and Pearson to be insoluble by asymptotic methods, are solved by the boundary-value method.     

A generalized conditional gradient method and its connection to an iterative shrinkage method

This article combines techniques from two fields of applied mathematics: optimization theory and inverse problems. We investigate a generalized conditional gradient method and its connection to an iterative shrinkage method, which has been recently proposed for solving inverse problems. The iterative shrinkage method aims at the solution of non-quadratic minimization problems where the solution is expected to have a sparse representation in a known basis. We show that it can be interpreted as a generalized conditional gradient method. We prove the convergence of this generalized method for general class of functionals, which includes non-convex functionals. This also gives a deeper understanding of the iterative shrinkage method.     

AN EMBEDDED BOUNDARY METHOD FOR ELLIPTIC AND PARABOLIC PROBLEMS WITH INTERFACES AND APPLICATION TO MULTI-MATERIAL SYSTEMS WITH PHASE TRANSITIONS

The embedded boundary method for solving elliptic and parabolic problems in geometrically complex domains using Cartesian meshes by Johansen and Colella （1998, J. Comput. Phys. 147, 60） has been extended for elliptic and parabolic problems with interior boundaries or interfaces of discontinuities of material properties or solutions. Second order accuracy is achieved in space and time for both stationary and moving interface problems. The method is conservative for elliptic and parabolic problems with fixed interfaces. Based on this method, a front tracking algorithm for the Stefan problem has been developed. The accuracy of the method is measured through comparison with exact solution to a two-dimensional Stefan problem. The algorithm has been used for the study of melting and solidification problems.     

A trajectory-based method for mixed integer nonlinear programming problems

A local trajectory-based method for solving mixed integer nonlinear programming problems is proposed. The method is based on the trajectory-based method for continuous optimization problems. The method has three phases, each of which performs continuous minimizations via the solution of systems of differential equations. A number of novel contributions, such as an adaptive step size strategy for numerical integration and a strategy for updating the penalty parameter, are introduced. We have shown that the optimal value obtained by the proposed method is at least as good as the minimizer predicted by a recent definition of a mixed integer local minimizer. Computational results are presented, showing the effectiveness of the method.     

Embedded diagonally implicit Runge–Kutta–Nystrom 4(3) pair for solving special second-order IVPs

In this paper, third-order 3-stage diagonally implicit Runge–Kutta–Nystrom method embedded in fourth-order 4-stage for solving special second-order initial value problems is constructed. The method has the property of minimized local truncation error as well as the last row of the coefficient matrix is equal to the vector output. The stability of the method is investigated and a standard set of test problems are tested upon and comparisons on the numerical results are made when the same set of test problems are reduced to first-order system and solved using existing Runge–Kutta method. The results clearly shown the advantage and the efficiency of the new method.     

A Globally Convergent Smoothing Newton Method for Nonsmooth Equations and Its Application to Complementarity Problems

The complementarity problem is theoretically and practically useful, and has been used to study and formulate various equilibrium problems arising in economics and engineerings. Recently, for solving complementarity problems, various equivalent equation formulations have been proposed and seem attractive. However, such formulations have the difficulty that the equation arising from complementarity problems is typically nonsmooth. In this paper, we propose a new smoothing Newton method for nonsmooth equations. In our method, we use an approximation function that is smooth when the approximation parameter is positive, and which coincides with original nonsmooth function when the parameter takes zero. Then, we apply Newton's method for the equation that is equivalent to the original nonsmooth equation and that includes an approximation parameter as a variable. The proposed method has the advantage that it has only to deal with a smooth function at any iteration and that it never requires a procedure to decrease an approximation parameter. We show that the sequence generated by the proposed method is globally convergent to a solution, and that, under semismooth assumption, its convergence rate is superlinear. Moreover, we apply the method to nonlinear complementarity problems. Numerical results show that the proposed method is practically efficient.     

一个新的求解线性规划最小二乘算法

§1Introduction Currently,therearetwopopularapproachesinlinearprogramming:pivotalgorithm andinterior-pointalgorithm.Manyoftheirvariantsdevelopedbothintheoryand applicationsarestillinprogress.Thepivotmethodobtainstheoptimalsolutionviamoving consecutivelytoabettercorner-pointinthefeasibleregion,anditsmodificationstryto improvethespeedofattainingtheoptimality.Incontrast,theinterior-pointalgorithmis claimedasaninterior-pointapproach,whichgoesfromafeasiblepointtoafeasiblepoint throughtheinterioroft…