折扣模型最优策略的结构

本文研究了折扣马尔可夫决策规划(以下简记为MDP)最优策略的结构。证明了:任给一策略π^*=(π_G^*,π₁^*,…,π_n^*,π_n+1^*,…),若它是β折扣最优的,则随机平稳策略也是β折扣最优的;对任何n(≥1),我们也给出了随机平稳策略也是β折扣最优的充分条件。还证明了:任给一随机平稳策略π₀     

关于矩阵乘法的一个算法的时间复杂度

两个n阶非负整数方阵相乘,常规算法的时间复杂度为O(n³),文献[1]提出一个“运算次数”为O(n²)的“最佳”算法,本文根据算法分析理论得出此算法的时间复杂度不低于O(n³log₂ⁿ),因而比常规算法的运算量还大.     

确定凸多边形可碰撞区域的快速算法

设P=(p₀,p₁,…,p_n-1)与Q=(q₀,q₁,…,q_n-1)是任二互不相交的凸多边形,本文研究了如何快速确定它们的可碰撞区域和可移动区域的问题. 文中提出了可碰撞性判定的新方法,研究了斜支撑线的基本性质,利用这些性质构造出了求斜支撑线的快速算法,其时间复杂度为O(log²(n+m)),在此基础上给出了确定可碰撞区域和可移动区域的时间复杂度为O(log²(n+m))的快速算法.     

一类半参数回归模型的估计理论

考虑半参数回归模型Y=X’β+g(T)+e,其中(X,T)为取值于R^p×[0,1]上的随机向量,β为p×1未知参数向量,g为定义于[0,1]上的未知函数,e为随机误差,Ee=0,Ee²=σ²>0,且(X,T)与e独立。本文综合最近邻和最小二乘的方法定义了β,g和σ²的估计量,g_n^*和。在适当条件下证明了和的渐近正态性,并得到了g_n^*的最优收敛速度。     

多元 Besov-Wiener 类的无穷维宽度和最优恢复

该文考虑 Besov-Wiener 类S_pqθ^r B(R^d)和 S_pqθ^r B(R^d)在 L_q(R^d) 空间下 (1≤q≤ p <∞ ) 的无穷维σ -宽度和最优恢复问题.通过考虑样条函数逼近和构造一种连续样条算子, 得到了关于无穷维Kolmogorov 宽度、无穷维线性宽度、无穷维 Gel'fand 宽度和最优恢复的弱渐近结果.     

Sobolev-Wiener空间上的无穷维宽度和最优插值问题

本文引入了一类定义在全实数轴上的Sobolev-Wiener空间,在其中讨论了点集的无穷维宽度和最优插值问题.求出了W_∞,p^r(R)在L_p(R)尺度下无穷维Ko-lmogorov宽度、线性宽度的精确值(强渐近精确值),并解决了最优插值问题.     

相对化概率算法类与非确定算法类的强分离

本文提出并讨论了多项式时间概率型算法复杂度语言类与指数时间非确定型算法复杂度语言类的强分离(即带禁集证据的分离)问题,获得并证明了存在一个递归Oracle集A使得在多项式时间有界错误概率复杂度语言类BPP^A中存在NEXT_k^A禁集,这里NEXT_k^A=∪NTIME^A(2^_cnk)表示计算时间限界于O(2^_nk)的指数时间非确定型算法所接受的语言类;我们指出,Oracle集A可以一致地对k构成并列举熟知的语言类P,NP,U,R,BPP,PP,∑₂^p,∏₂^p,Δ₂^p以及交互式证明系统语言类MA,AM,IP等之间的30余种强分离关系作为本文结果的直接推论.     

异或逻辑函数的简化

本文提出了一种简化异或门逻辑函数的计算机算法。这种算法用于简化n个输入变量的异或逻辑函数时,比快速Reed-Muller变换算法快n/[1+(n—1)2^-n]倍。     

线性模型中误差方差估计的相合性

本文研究在条件(1.2)(其中e₁,e₂,…,假定有不同的分布)之下,估计σ²(n)的大样本性质,得到了:
1.σ²(n)为σ²的弱相合估计的必要条件;
2.σ²(n)为σ²的强相合估计的必要条件和充分条件,二者差别不大(有可能,必要条件也是充分条件)。     

关于矩阵乘法的一个改进算法的时间复杂度

两个ｎ阶非负整数方阵相乘,常规算法的时间复杂度为Ｏ（ｎ^３）,文献［１］提出一个“运算次数”为Ｏ（ｎ²）的“最佳”算法,文献［２］对此算法做了进一步研究,提出三种改进策略．本文根据算法分析理论,得出改进后的算法的时间复杂度仍不低于Ｏ（ｎ^３ｌｏｇｎ）,因而其阶仍高于常规算法的运算量的阶．     

Pendants-median支撑树及其一个相关问题:复杂性和算法

The complexity status of Pendants-median spanning tree problem is an open problem. Using the complexity of the X3C problem, the paper proves that Pendants-median spanning tree problem is NP-complete. Global-median spanning tree problem is a related problem. Using the complexity of 3SAT, the paper proves that this problem is also NP-complete, and a polynomial -time algorithm to this problem is given, whose time complexity is O(n^3).     

Unconstrained Methods for Generalized Complementarity Problems

1.IntroductionThecomplementarityproblem,aspecialcaseofvariationalinequalityproblem,hasmanyapplicationsindifferentfieldssuchasmathematicalprogramming,gametheory,economics.Generally,thestandardcomplementarityproblemhasthefollowingform:y=F(x),x20,y20,(y,x)=0,(1.1)where(.,.)denotestheinnerproducts.WhenF(x)isanaffinefunctionofx,itreducestothelinearcomplementarityproblemwhichisdenotedbyLCP.Otherwisewecallitthenonlinearco7nplementaritypro6lemorsimplyNCP.Thecomplementarityproblemhajsattractedmanyr…     

Single machine stochastic JIT scheduling problem subject to machine breakdowns

In this paper we research the single machine stochastic JIT scheduling problem subject to the machine breakdowns for preemptive-resume and preemptive-repeat.The objective function of the problem is the sum of squared deviations of the job-expected completion times from the due date.For preemptive-resume,we show that the optimal sequence of the SSDE problem is V-shaped with respect to expected processing times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.We discuss the difference between the SSDE problem and the ESSD problem and show that the optimal solution of the SSDE problem is a good approximate optimal solution of the ESSD problem,and the optimal solution of the SSDE problem is an optimal solution of the ESSD problem under some conditions.For preemptive-repeat,the stochastic JIT scheduling problem has not been solved since the variances of the completion times cannot be computed.We replace the ESSD problem by the SSDE problem.We show that the optimal sequence of the SSDE problem is V-shaped with respect to the expected occupying times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.A new thought is advanced for the research of the preemptive-repeat stochastic JIT scheduling problem.     

三种新变形的全一问题

该文研究三种新变形的全一问题及最小全一问题. 原始的全一问题可被形象的称为顶点点亮顶点问题, 而这三类新问题则分别被称为顶点点亮边问题,边点亮顶点问题,边点亮边问题. 顶点点亮顶点问题已经得到了广泛的研究. 比如,解的存在性问题和求解的有效算法已经被解决,一般图上的最小顶点点亮顶点问题已经被证明是NP- 完备的,树、单圈图和双圈图上的最小顶点点亮顶点问题的线性时间最优算法也已被给出等. 该文对于顶点点亮边问题,证明一个图有解当且仅当它是二部图,因此只可能有两组解和最优解. 对于边点亮顶点问题,证明一个图有解当且仅当它包含偶数个顶点,并通过将其最优问题多项式变换成最小权的完美匹配问题,得出一般图上的最小边点亮顶点问题可在多项式时间内求解. 边点亮边问题可归约成线图上的顶点点亮顶点问题.     

Characterization of duality for a generalized quasi-equilibrium problem

In this paper, the duality theory of a generalized quasi-equilibrium problem (also called generalized Ky Fan quasi-inequality) is investigated by using the image space approach. Generalized quasi-equilibrium problem is transformed into a minimization problem. The minimization problem is further reformulated as an image problem by virtue of linear/nonlinear separation function. The dual problem of the image problem is constructed in the image space, then zero duality gap between the image problem and its dual problem is derived under saddle point condition as well as the equivalent regular linear/nonlinear separation condition. Finally, some more sufficient conditions guaranteeing zero duality gap are also proposed.     

The zero-one knapsack problem with equality constraint

The zero-one knapsack problem is a linear zero-one programming problem with a single inequality constraint. This problem has been extensively studied and many applications and efficient algorithms have been published. In this paper we consider a similar problem, one with an equality instead of the inequality constraint. By replacing the equality by two inequalities one of which is placed in the economic function, a Lagrangean relaxation of the problem is obtained. The relation between the relaxed problem and the original problem is examined and it is shown how the optimal value of the relaxed problem varies with increasing values of the Lagrangean multiplier. Using these results an algorithm for solving the problem is proposed.The paper concludes with a discussion of computational experience.     

Production planning with discounting and stochastic demands

A general continuous review production planning problem with stochastic demand is considered. Conditions under which the stochastic problem may be correctly solved using an equivalent deterministic problem are developed. This deterministic problem is known to have the same solution as the stochastic problem. Moreover, conditions are established under which the deterministic equivalent problem differs from a commonly used deterministic approximation to the problem only in the interest rate used in discounting. Thus, solving the stochastic problem is no more difficult than solving a commonly used approximation of the problem.     

非线性-线性二层规划问题的罚函数方法

利用下层问题的K-T最优性条件将下层为线性规划的一类非线性二层规划转化成相应的单层规划,同时取下层问题的互补条件为罚项,构造了该类非线性二层规划的罚问题.通过对相应罚问题性质的分析,得到了该类非线性二层规划问题的最优性条件,同时设计了该类二层规划问题的求解方法.数值结果表明该方法是可行、有效的.     

Complexities and algorithms for synchronized scheduling of parallel machine assembly and air transportation in consumer electronics supply chain

In this paper, we study the problem of synchronized scheduling of assembly and air transportation to achieve accurate delivery with minimized cost in consumer electronics supply chain. This problem was motivated by a major PC manufacturer in consumer electronics industry. The overall problem is decomposed into two sub-problems, which consist of an air transportation allocation problem and an assembly scheduling problem. The air transportation allocation problem is formulated as an integer linear programming problem with the objective of minimizing transportation cost and delivery earliness tardiness penalties. The assembly scheduling problem seeks to determine a schedule ensuring that the orders are completed on time and catch the flights such that the waiting penalties between assembly and transportation is minimized. The problem is formulated as a parallel machine scheduling problem with earliness penalties. The computational complexities of the two sub-problems are investigated. The air transportation allocation problem with split delivery is shown to be solvable. The parallel machine assembly scheduling problem is shown to be NP-complete. Simulated annealing based heuristic algorithms are presented to solve the parallel machine problem.     

现代物流技术中装卸工问题的拟多项式时间可解情况

装卸工问题是从现代物流技术中提出的一个实际问题，这个问题的雏形早在上个世纪60年代中国科学院数学研究所就提出和研究过。现代物流业的迅速发展，促成和推动装卸工问题的提出和研究。装卸工问题是一个新的NP困难的组合优化问题，本文研究限制情形下的装卸工问题，并证明是拟多项式时间可解的。