Affine-scaling for linear programs with free variables

The affine-scaling modification of Karmarkar's algorithm is extended to solve problems with free variables. This extended primal algorithm is used to prove two important results. First the geometrically elegant feasibility algorithm proposed by Chandru and Kochar is the same algorithm as the one obtained by appending a single column of residuals to the constraint matrix. Second the dual algorithm as first described by Adler et al., is the same as the extended primal algorithm applied to the dual.     

A new framework for implicit restarting of the Krylov–Schur algorithm

This paper introduces a new framework for implicit restarting of the Krylov–Schur algorithm. It is shown that restarting with arbitrary polynomial filter is possible by reassigning some of the eigenvalues of the Rayleigh quotient through a rank‐one correction, implemented using only the elementary transformations (translation and similarity) of the Krylov decomposition. This framework includes the implicitly restarted Arnoldi (IRA) algorithm and the Krylov–Schur algorithm with implicit harmonic restart as special cases. Further, it reveals that the IRA algorithm can be turned into an eigenvalue assignment method. Copyright © 2014 John Wiley & Sons, Ltd.     

A posterior error estimates for the nonlinear grating problem with transparent boundary condition

The nonlinear grating problem is modeled by Maxwell's equations with transparent boundary conditions. The nonlocal boundary operators are truncated by taking sufficiently many terms in the corresponding expansions. A finite element method with the truncation operators is developed for solving the nonlinear grating problem. The two posterior error estimates are established. The a posterior error estimate consists of two parts: finite element discretization error and the truncation error of the nonlocal boundary operators. In particular, the truncation error caused by truncation operations is exponentially decayed when the parameter N is increased. Numerical experiment is included to illustrate the efficiency of the method. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 1101–1118, 2015     

Decoupled two‐grid finite element method for the time‐dependent natural convection problem I: Spatial discretization

In this article, a decoupled two grid finite element method (FEM) is proposed and analyzed for the nonsteady natural convection problem using the coarse grid numerical solutions to decouple the nonlinear coupled terms, and the corresponding optimal error estimates are derived. Compared with the standard Galerkin FEM and the usual two‐grid FEM, our algorithm not only keeps good accuracy but also saves a lot of computational cost. Some numerical examples are provided to verify the performances of the decoupled two‐grid FEM. Both theoretical analysis and numerical experiments show the efficiency and effectiveness of the decoupled two‐grid FEM for the nonsteady natural convection problem. © 2015 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 2135–2168, 2015     

具有多个不可用时间段的单机供应链排序问题

在单机供应链排序问题中, 机器会有多个长度确定的不可用时间段,它仅可以在可用时间段内加工工件,且每个可用时间段的长度不大于给定的常数.多个完工工件可组成一批由一个容量无限制的运输工具发送给客户.问题的目标是如何 安排工件的加工、发送以及不可用时间段,以使总发送时间与总发送费用之和达到最小. 对于工件加工可恢复的情况,可在多项式时间 O(n^2) 内得到最优序. 对于工件加工不可恢复的情况,证明了问题是强NP-难的, 并提出了~2-近似算法.     

A conformal mapping approach for investigating the free-boundary seepage from symmetric channels

We present a new method to investigate the two-dimensional free-boundary groundwater seepage from symmetric soil channels into a homogeneous isotropic porous medium. We use Levi–Civitá’s function to construct an integral representation for the conformal mapping of the complex potential domain onto the physical flow domain. A genetic algorithm (GA) is used to calculate the coefficients of the Maclaurin series expansion of Levi–Civitá’s function. The coordinates of the points from the channel contour, calculated by means of the integral representation, must satisfy the analytic equation of the contour. We use this condition to define the objective function of the genetic algorithm. Levi–Civitá’s function is afterwards used to calculate the seepage loss, the free lines, the streamlines, the equipotential lines, the isobars and the velocity field. Some examples illustrate the method.     

一类排序问题的求解及效果评估

对一类排序问题给出了一种有效的排序方法.我们将该类排序问题中的属性分为正向属性和负向属性,建立了属性规范化处理的数学模型,得到属性之间无差异的偏好比重,并对偏好比重进行汇总,得到对象之间的排序.最后,利用带自然边界条件的三次样条插值的三弯矩算法对该排序方法进行误差估计.     

基于模拟植物生长算法构造Steiner最优树问题研究

Steiner最优树问题是指对于给定区域内的点集,通过引入Steiner点集将区域中的点连接并保证连通的网络达到最小.该问题已成为经典的优化组合问题之一.提出一种基于模拟植物生长算法生成Steiner最优树的连通算法来实现网络连通.通过对实例的实验及结果分析,结果表明本算法不仅可获得最优解,精度和性能也有提高,明显优于其它方法.     

求解半定乘性规划的外部逼近算法

定义了半定乘性规划问题,提出一种求解它的外部逼近算法,并通过具体的实例说明算法的可行性.