论一类资源最优配置问题及应用

本文考虑了一类资源最优配置问题.应用Kuhn-Tucher定理得到了这类问题最优解的充要条件.我们应用这个条件来考虑一类从工业投资、教育投资等问题中导出的最优投资模型,得到了这个问题最优解的充要条件,应用这个条件导出了求解这个模型的具有时间复杂度为o(mn)的多项式型新算法.     

一类不可微规划的多项式型算法

本文考虑了由教育最优投资问题导出的一类不可微规划，讨论了可行解是最优解的充要条件，在对乘子作某些假设下，利用Kuhu－Tucker定理给出了求解的一种多项式算法．     

一类资源最优配置的充要条件及其应用

本文研究了由工业投资、教育投资等问题中导出的一类非线性规划问题,应用Kuhn-Tucher定理得到了Rn中向量x=(x1,x2,…,xn)是这问题最优解的充分必要条件．应用这一结果导出了求解一类资源最优配置问题的新算法．这是一个具有计算复杂度为O(mn(m n))的多项式型算法．     

一类可微规划的多项式型算法

本文考虑了由教育最成投资问题导出的一类不可微规划，讨论了可行解是最优解的充要条件，在对乘子作某些假设下，利用Ｋｕｈ－Ｔｕｃｋｅｒ定理给出了求解的一种多项式算法。     

一类广义分式规划问题的完全多项式时间近似算法

本文对一类广义分式规划问题,提出一种求其全局最优解的完全多项式时间近似算法,给出该算法的理论分析和计算复杂性,通过数值算例验证该算法是有效可行的.     

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

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

一个求线性代数方程组非负解的算法及其在线性规划中的应用

1.引言关于线性规划的多项式算法,哈奇扬于1979年首先把一个线性规划问题化成一个线性不等式组的求解问题,然后用椭球方法求解线性不等式组,并证明是多项式时间可解的。Karmarkar于1984年也给出了一个求解线性规划的多项式时间解法,他     

具一阶奇异性解的奇异积分方程的直接解法

本文研究了一类具有一阶奇异性解的完全奇异积分方程的直接解法.利用推广的留数定理和Hermite插值多项式,得到了其可解的充要条件和解的封闭形式.     

关于最大权k－子集分拆问题

对给定规模为ｎ的集合Ｓ，其每一个规模至多为ｋ的子集对应一个权．本文研究如何将Ｓ分为　个互不相交的规模至多为ｋ的子集且满足权和最大的问题．我们证明了该问题当ｋ＝２时是多项式时间可解的；当ｋ≥３时为ＮＰ－完全的；同时给出了一个Ｏ（ｎ￣（ｋ＋１））时间的启发式算法，所得到的解与最优解之比不小于１／ｋ．     

(m,n,k)指派问题的最小费用流模型及其算法

构造(m,n,k)指派问题的最小费用流模型,并将基于对偶原理的最小费用流的允许边算法求解该模型,提出求解(m,n,k)指派问题的一种算法.算法直接在其对应的网络中保持互补松弛条件不变,通过调整节点势以扩大允许网络从而寻求增广链并进行流量增广,直至在网络中得到流量为k的最小费用流,此时非O流边对应(m,n,k)指派问题的最优解.给出了(m,n,k)指派问题的最优解及多重最优解的重要性质,数值试验表明算法有效可行.     

An inverse model for the most uniform problem

In this paper, we consider a kind of inverse model for the most uniform problem. This model has some practical background. It is shown that the model can be solved in polynomial time whenever an associated min-sum problem can be solved in polynomial time.     

A decomposition algorithm for solving certain classes of production-transportation problems with concave production cost

This paper addresses a method for solving two classes of production-transportation problems with concave production cost. By exploiting a special network structure both problems are reduced to a kind of resource allocation problem. It is shown that the resultant problem can be solved by using dynamic programming in time polynomial in the number of supply and demand points and the total demand.The author was partially supported by Grand-in-Aid for Scientific Research of the Ministry of Education, Science and Culture, Grant No. (C)05650061.     

On Smale's 17th Problem: A Probabilistic Positive Solution

Smale's 17th Problem asks “Can a zero of n complex polynomial equations in n unknowns be found approximately, on the average [for a suitable probability measure on the space of inputs], in polynomial time with a uniform algorithm?” We present a uniform probabilistic algorithm for this problem and prove that its complexity is polynomial. We thus obtain a partial positive solution to Smale's 17th Problem.     

A problem that is easier to solve on the unit-cost algebraic RAM

Problem 5.1 in (L. Blum, M. Shub, and S. Smale, 1989, Bull. Amer. Math. Soc. 21(1), 1–46) asks if there is a decision problem that cannot be solved in polynomial time by a Turing machine, but can be solved in polynomial time on a unit-cost algebraic RAM with operations {+,-,*,/,<}, and without the integer division operation. We present a problem that is not known to be solvable in polynomial time on a Turing machine, but can be solved in polynomial time on a unit-cost algebraic RAM. This is strong evidence for an affirmative answer to Problem 5.1.     

The Euclidean Steiner tree problem in Rn: A mathematical programming formulation

A nonconvex mixed-integer programming formulation for the Euclidean Steiner Tree Problem (ESTP) in Rⁿ is presented. After obtaining separability between integer and continuous variables in the objective function, a Lagrange dual program is proposed. To solve this dual problem (and obtaining a lower bound for ESTP) we use subgradient techniques. In order to evaluate a subgradient at each iteration we have to solve three optimization problems, two in polynomial time, and one is a special convex nondifferentiable programming problem. This revised version was published online in June 2006 with corrections to the Cover Date.     

Boundary value problem for a global‐in‐time parabolic equation

The aim of this paper is to draw attention to an interesting semilinear parabolic equation that arose when describing the chaotic dynamics of a polymer molecule in a liquid. This equation is nonlocal in time and contains a term, called the interaction potential, that depends on the time‐integral of the solution over the entire interval of solving the problem. In fact, one needs to know the “future” in order to determine the coefficient in this term, that is, the causality principle is violated. The existence of a weak solution of the initial boundary value problem is proven. The interaction potential satisfies fairly general conditions and can have arbitrary growth at infinity. The uniqueness of this solution is established with restrictions on the length of the considered time interval.     

A Stefan Problem with Curvature Correction in a Concentrated Capacity

We consider a Stefan problem with the curvature correction in a concentrated capacity. It is a kind of phase transition problems, in which the unknown temperature satisfies both the Stefan condition and the curvature correction on the free boundary, and also fulfills a kind of heat equations with special inner heat source. The inner beat source is related to the derivative of the temperature with respect to the direction vertical to the phase regions. The result established in this paper is the existence of a global weak solution of this problem.     

Quasi-translations and counterexamples to the Homogeneous Dependence Problem

In this article, the author gives counterexamples to the Linear Dependence Problem for Homogeneous Nilpotent Jacobians for dimension 5 and up. This problem has been formulated as a conjecture/problem by several authors in connection to the Jacobian conjecture. In dimension 10 and up, cubic counterexamples are given.

In the construction of these counterexamples, the author makes use of so-called quasi-translations, a special type of invertible polynomial maps. Quasi-translations can also be seen as a special type of locally nilpotent derivations.

     

加权完工时间和的调整时间可分离Flow shop排序问题

讨论了2台机器调整时间可分离的FlowShop排序问题,目标函数为极小化加权完工时间和.给出了对于一种特殊情况,问题存在多项式最优算法的充分条件.接着又给出了求解该问题的一个分枝定界法.     

A note on iterative roots of PM functions

In this paper we study iterative roots of PM functions, a special class of non-monotone functions. Problem 2 in [W. Zhang, PM functions, their characteristic intervals and iterative roots, Ann. Polon. Math. LXV (1997) 119-128] is solved partly and Theorem 4 in that paper is generalized.