所有点对之间最快路问题

所有点对之间最快路问题就是要在所有点对(Vs，Vt)之间传送数据δs,t,并找出一条最快的路线．解决所有点对之间最快路问题的关键是产生有效解的等价集合．运用动态点对最短路的算法，本文首先设计了一个时间复杂性为O(mn^2)的产生有效解等价集合的算法，然后研究了静态点对之间最快路问题和动态点对之间最快路问题，其算法的时间复杂性分别为O(mn^2)和O(m^2n^2)．最后本文研究了求和对最小的路问题，证明该问题可以在O(mn^2)时间内解决．     

一个约束乘积最大问题的强多项式时间算法

本文讨论了约束乘积最大问题最优解的结构特征,在此基础上给出了一个计算时间为O(n2)的强多项式时间算法,并且对于单边约束的情形给出了复杂度更低(O(nlnn))的强多项式时间算法.     

有理单变元表示在优化问题上的应用

利用零维多项式系统的有理单变元表示,给出了求多项式在有限点集上的正性判定算法.同时,结合不等式证明,呈现了目标函数在零维系统约束下最优化的一个纯代数算法,从而将多元函数约束优化问题转化为单变元函数在单变元多项式约束下的优化问题.新算法不仅能处理目标函数为多项式的最优化问题,而且还能处理目标函数为有理分式函数和根式函数的的最优化问题,并且给出了目标函数最优值的精确区间表示,使得能任意精度地逼近最优值.     

具有CON/SLK交货期指派的一类单机排序问题

研究工件的实际加工时间既具有指数学习效应,又依赖所消耗资源的准时制排序问题.在模型中,探讨了共同交货期(CON)和松弛交货期(SLK)两种情形.管理者的目标是确定最优序、最优资源分配方案和最佳工期(共同交货期或松弛交货期)以便极小化工件的总延误、总提前、总工期和资源消耗费用的总和.对于工件的实际加工时间是资源消耗量的线性函数的排序问题,通过将其转化为指派模型,给出了时间复杂性为O(n~3)的算法,从而证明该类排序问题是多项式时间可求解的.针对工件的实际加工时间是资源消耗量的凸函数的排序问题,也给出了多项式算法.     

一类齐次多项式优化问题的一个全局优化算法

对图像与信号处理中遇到的一类齐次多项式优化问题,本文首先借助平移技术将目标函数转化为凸函数,然后结合初始点技术提出了求解该类问题的一个全局优化算法.与求解该类问题的幂方法相比,本文给出的方法不但能在一般情形下保证算法的全局收敛性,而且数值结果表明在多数情况下可以得到问题的一个全局最优值解.     

双会议服务器选址问题研究

中位选址问题一直是管理学科的研究热点,本文考虑平面点集选址问题中的双会议服务器选址问题,该问题可以看成是2中位问题的衍生问题。令P为平面上包含n个点的点集,双会议服务器选址问题即为寻找由该点集构成的一棵二星树,使得这棵树上所有叶子之间的距离和最小。本文给出求解该问题的关键几何结构和最优解算法设计,并证明所给算法时间复杂性为O(n³logn)。     

求多目标优化问题Pareto最优解集的方法

主要讨论了无约束多目标优化问题Pareto最优解集的求解方法,其中问题的目标函数是C1连续函数.给出了Pareto最优解集的一个充要条件,定义了α强有效解,并结合区间分析的方法,建立了求解无约束多目标优化问题Pareto最优解集的区间算法,理论分析和数值结果均表明该算法是可靠和有效的.     

Karmarkar算法的一个变形

本文给出了一个解线性规划问题的Karmarkar算法的变形。根据一个不涉及势函数的优化原则,导出一个新的搜索方向,然后将其正交投影得出本文所给算法。该算法的优点是在整个迭代过程中无须对目标函数值加以限制,无须增加对偶变量和对偶约束,也不必采用滑动目标函数技术,且在最优解邻域内的收敛速度与Karmarkar算法相同。     

一类广义线性多乘积问题的完全多项式时间近似算法

本文针对一类广义线性多乘积问题提出一种求其全局最优解的完全多项式时间近似算法,并给出算法的理论分析和计算复杂性,数值结果表明本文算法有效可行.     

广义线性多乘积问题的完全多项式时间近似算法

本文针对广义线性多乘积极小化问题,通过一系列的线性规划问题的解提出一种求其全局最优解的完全多项式时间近似算法,并给出该算法的计算复杂性,且数值算例验证该算法是可行的.     

基于凹性割的线性双层规划全局优化算法

通过对线性双层规划下层问题对偶间隙的讨论,定义了一种凹性割,利用该凹性割的性质,给出了一个求解线性双层规划的割平面算法。由于线性双层规划全局最优解可在其约束域的极点上达到,提出的算法能求得问题的全局最优解,并通过一个算例说明了算法的有效性。     

Anti-periodic solutions for Rayleigh-type equations via the reproducing kernel Hilbert space method

In this paper, reproducing kernel theorem is employed to solve anti-periodic solutions for Rayleigh-type equations. A simple algorithm is given to obtain the approximate solutions of the equations. By comparing the approximate solution with the exact analytical solution, we find that the simple algorithm is of good accuracy and it can be also applied to some ordinary or partial differential equations with initial-boundary value conditions and nonlocal boundary value conditions.     

精确解析法的子结构算法

文[1]提出精确解析法,用以求解任意变系数常微分方程,并利用初参数算法给出一个解的解析表达式.但利用初参数算法,对某一类问题,如长柱壳弯曲和振动等,它们的解将难以在计算机上得到.本文通过非均匀轴对称长圆柱壳弯曲问题,给出精确解析法的子结构算法,它能够计算初参数算法在计算机上不能解决的问题.问题最后和初参数算法一样能归结为求解一个低阶代数方程组.文末给出算例,表明本文算法的正确性,并和初参数算法作了比较.     

牛顿法和伴随理论在半线性发展方程描述的参数系统的系统辩识中的应用

应用Hilbert空间中的最优化方法的牛顿法和伴随理论来研究一半线性发展方程描述的参数系统的系统参数辩识，并给出了牛顿法二次收敛性的一种证明．利用伴随理论和基本解的方法得到了目标泛函关于参数的海色算子简单表达式．最后给出了一个算法及一简单的数值例子来验证这个算法．     

Left and right inverse eigenpairs problem of generalized centrosymmetric matrices and its optimal approximation problem

In this paper, the left and right inverse eigenpairs problem for generalized centrosymmetric matrices is considered. We obtain the necessary and sufficient conditions for the solvability of the problem, and we present the general expression of the solution. The related optimal approximation problem to a given matrix over the solution set is solved. In addition, a numerical algorithm and examples to solve the problem are given.     

线性流形上广义次对称矩阵的左右逆特征值问题

研究线性流形上广义次对称矩阵的左右逆特征值问题及其最佳逼近问题.利用广义次对称矩阵的性质及矩阵的奇异值分解得到问题的通解表达式.同时,给出其有唯一的最佳逼近解以及求最佳逼近解的算法.     

低阶精确罚函数的一种光滑化逼近

本文对不等式约束优化问题给出了低阶精确罚函数的一种光滑化逼近.提出了通过搜索光滑化后的罚问题的全局解而得到原优化问题的近似全局解的算法.给出了几个数值例子以说明所提出的光滑化方法的有效性.     

Branch-and-price algorithm for a multicast routing problem

This paper considers a multicast routing problem to find the minimum cost tree where the whole communication link delay on each path(route) of the tree is subject to a given delay allowance. The problem is formulated as an integer programming problem by using path variables. An associated problem reduction property is then characterised to reduce the solution space. Moreover, a polynomial time column generation procedure is exploited to solve the associated linear programming relaxation with such solution space reduced. Therefore a branch-and-price algorithm is derived to obtain the optimal integer solution(tree) for the problem. Computational results show that the algorithm can solve practical size problems in a reasonable length of time.     

A Nonsmooth L-M Method for Solving the Generalized Nonlinear Complementarity Problem over a Polyhedral Cone

In this paper the generalized nonlinear complementarity problem (GNCP) defined on a polyhedral cone is reformulated as a system of nonsmooth equations. Based on this reformulation, the famous Levenberg-Marquardt (L-M) algorithm is employed to obtain its solution. Theoretical results that relate the stationary points of the merit function to the solution of the GNCP are presented. Under mild assumptions, we show that the L-M algorithm is both globally and superlinearly convergent. Moreover, a method to calculate a generalized Jacobian is given and numerical experimental results are presented.     

计算一类反应扩散方程分歧问题的Fourier配点法

1引言 关于反应扩散方程的研究由来已久,特别是对一些含参数的非线性反应扩散方程,由于其多解性和丰富的分歧现象,经常受到人们的关注.本文考虑如下非线性反应扩散方程组 {ut=γf(u,v)+uxx, vt=γg(u,v)+dvxx, (1) 相应的边界条件为 ux(t,0):ux(t,π)=vx(t,0)=vx(t,π)=0. (2) 我们选取Gierer-Meinhardt模型[1,2]为研究对象,即 {f(u,V)=a-bu+u2/v, g(u,v)=u2-v, 其中a、b和γ是正常数,d为参数.