关于矩阵特征值问题向后误差分析的注记

本文研究实矩阵关于复近似特征对的范数型向后误差．在复扰动情形,这个问题已被Higham 等学者解决．本文研究实扰动情形．结果表明,通常情况下,两种情形差别不大,但在某些情形,二者可以相差很大．作为推广,我们还讨论了矩阵多项式的相应问题．文中的一个结果部分地解决了D．J．Higham和N．J．Higham 1999年提出的一个待解决的问题．     

An Algorithm for Solving Optimization Problems with One Linear Objective Function and Finitely Many Constraints of Fuzzy Relation Inequalities

An optimization model with one linear objective function and fuzzy relation equation constraints was presented by Fang and Li (1999) as well as an efficient solution procedure was designed by them for solving such a problem. A more general case of the problem, an optimization model with one linear objective function and finitely many constraints of fuzzy relation inequalities, is investigated in this paper. A new approach for solving this problem is proposed based on a necessary condition of optimality given in the paper. Compared with the known methods, the proposed algorithm shrinks the searching region and hence obtains an optimal solution fast. For some special cases, the proposed algorithm reaches an optimal solution very fast since there is only one minimum solution in the shrunk searching region. At the end of the paper, two numerical examples are given to illustrate this difference between the proposed algorithm and the known ones.     

Uniform estimates and uniqueness of stationary solutions to the drift–diffusion model for semiconductors

We study the stationary problem of the drift–diffusion model with a mixed boundary condition. For this problem, the existence of solutions was established in general settings, while the uniqueness was investigated only in some special cases which do not entirely cover situations that semiconductor devices are used in integrated circuits. In this paper, we prove the uniqueness in a physically relevant situation. The key to the proof is to derive two-sided uniform estimates for the densities of the electron and hole. We establish a new technique to show the lower bound. This together with the Moser iteration method leads to the upper bound.     

A partial cooperation model for non-unique linear two-level decision problems

This paper examines a linear static Stackelberg game where the follower's optimal reaction is not unique. Traditionally, the problem has been approached using either an optimistic or a pessimistic framework, respectively, representing the two extreme situations of full cooperation and zero cooperation from the follower. However, partial cooperation from the follower is a viable option. For partial cooperation, the leader's optimal strategy may be neither optimistic nor pessimistic. Introducing a cooperation index to describe the degree of follower cooperation, we first formulate a partial cooperation model for the leader. The two-level problem is then reformulated into a single-level model. It is shown that the optimistic and pessimistic situations are special cases of the general model, and that the leader's optimal choice may be an intermediate solution.     

Structural properties of optimal schedules with preemption

Scheduling problems with preemption are considered, where each operation can be interrupted and resumed later without any penalty. We investigate some basic properties of their optimal solutions. When does an optimal schedule exist (provided that there are feasible schedules)? When does it have a finite/polynomial number of interruptions? Do they occur at integral/rational points only? These theoretical questions are also of practical interest, since structural properties can be used to reduce the search space in a practical scheduling application. In this paper we answer some of these basic questions for a rather general scheduling model (including, as the special cases, the classicalmodels such as parallelmachine scheduling, shop scheduling, and resource constrained project scheduling) and for a large variety of the objective functions including nearly all known. For some two special cases of objective functions (including, however, all classical ones), we prove the existence of an optimal solution with a special “rational structure.” An important consequence of this property is that the decision versions of these optimization scheduling problems belong to class NP.     

An inventory–routing problem with the objective of travel time minimization

In this paper, we consider an inventory–routing problem (IRP) in a large petroleum and petrochemical enterprise group. Compared to many other IRPs, the problem in this paper includes some special aspects due to the operational constraints, such as hours-of-service regulations of the company and the industry. Also, in some cases, it is more important to avoid stock out for any station, rather than purely focusing on transportation cost minimization. The objective is to minimize the maximum of the route travel time, which is not addressed in the literature so far. We present a tabu search algorithm to tackle the problem, which builds in an efficient and effective procedure to improve the search quality in each iteration. Moreover, lower bounds of reasonable sized problems, which are intractable in the formulated mathematical model by existing optimization software, are obtained via Lagrangian relaxation technique. Computational results indicate that the lower bounds are tight and the tabu search is capable of providing near optimal, close-to-lower-bound solutions in a computational time effective manner.     

Weighted heuristic search in networks

The evaluation function used in heuristic search algorithms commonly has the form , where n is any node in the network, is the cost of the best path currently known from the start node to n, and is the heuristic estimate associated with node n. A more general form of the evaluation function can be obtained by incorporating a weighting parameter α:

Full-size image

, where 0≤ α ≤1. Such an evaluation function has been used in some recent experimental investigations of the 8-puzzle problem. In this paper a theoretical framework is developed for the analysis of the worst-case behavior of weighted heuristic search algorithms. A new algorithm is proposed whose worst-case performance characteristics are greatly superior to those of earlier algorithms in terms of the following two measures: how good is the solution, and how many nodes are expanded. Bounds are also obtained on some useful network parameters for both general and special types of heuristic estimate functions.     

The loader problem: formulation,complexity and algorithms

In this paper we consider a new transportation model, called the loader problem, which is frequently encountered by third-party logistics service providers in practice. It is a tactical staff-planning problem with the objective of minimizing the total labour cost of staffing a sufficient number of loaders on a given fleet of trucks that serve a given set of customer sites. We formulate the problem as an integer program and show that it is strongly NP-hard. We then consider two special cases of the loader problem that occur in certain practical situations, and propose polynomial and pseudo-polynomial time algorithms for solving these cases. We also propose a linear programming relaxation-based random rounding algorithm for the general problem and report the computational results of the algorithm.     

Enumeration of Lozenge Tilings of Hexagons with Cut-Off Corners

Motivated by the enumeration of a class of plane partitions studied by Proctor and by considerations about symmetry classes of plane partitions, we consider the problem of enumerating lozenge tilings of a hexagon with “maximal staircases” removed from some of its vertices. The case of one vertex corresponds to Proctor's problem. For two vertices there are several cases to consider, and most of them lead to nice enumeration formulas. For three or more vertices there do not seem to exist nice product formulas in general, but in one special situation a lot of factorization occurs, and we pose the problem of finding a formula for the number of tilings in this case.     

Optimal investment and premium control in a nonlinear diffusion model

This paper considers the optimal investment and premium control problem in a diffusion approximation to a non-homogeneous compound Poisson process. In the nonlinear diffusion model, it is assumed that there is an unspecified monotone function describing the relationship between the safety loading of premium and the time-varying claim arrival rate. Hence, in addition to the investment control, the premium rate can be served as a control variable in the optimization problem. Specifically, the problem is investigated in two cases: (i) maximizing the expected utility of terminal wealth, and (ii) minimizing the probability of ruin respectively. In both cases, some properties of the value functions are derived, and closed-form expressions for the optimal policies and the value functions are obtained. The results show that the optimal investment policy and the optimal premium control policy are dependent on each other. Most interestingly, as an example, we show that the nonlinear diffusion model reduces to a diffusion model with a quadratic drift coefficient when the function associated with the premium rate and the claim arrival rate takes a special form. This example shows that the model of study represents a class of nonlinear stochastic control risk model.     

截超泊松排队:具有阻碍、放弃和不同服务员H_k/M/2/N系统(英文)

本文讨论具有阻碍、放弃，不同服务员Ｋｋ／Ｍ／２／Ｎ排队系统的解析解．对经典的一种先入先出的修改排队规则在较一般的条件下被采用了，得到了稳态概率和一些有效度量的显式．一些特殊情况也被化简了。     

A tabu search algorithm for the single vehicle routing allocation problem

In the single vehicle routing allocation problem (SVRAP) we have a single vehicle, together with a set of customers, and the problem is one of deciding a route for the vehicle (starting and ending at given locations) such that it visits some of the customers. Customers not visited by the vehicle can either be allocated to a customer on the vehicle route, or they can be isolated. The objective is to minimize a weighted sum of routing, allocation and isolation costs. One special case of the general SVRAP is the median cycle problem, also known as the ring star problem, where no isolated vertices are allowed. Other special cases include the covering tour problem, the covering salesman problem and the shortest covering path problem. In this paper, we present a tabu search algorithm for the SVRAP. Our tabu search algorithm includes aspiration, path relinking and frequency-based diversification. Computational results are presented for test problems used previously in the literature and our algorithm is compared with the results obtained by other researchers. We also report results for much larger problems than have been considered by others.     

需求信息非对称情况下零售商最优订货问题研究

考虑需求信息非对称环境下多个存在竞争的零售商的最优订货问题,每个零售商的需求分布函数未知,传统的通过最大化期望利润来求解最优订货量的方法此时不再适用,转而应用稳健优化中使用的方法-最小化最大后悔值方法.首先给出了零售商最优订货量的一般形式.其次考虑了问题的两种特殊情形:对称博弈、两个零售商的最优订货模型,得到:对称博弈存在Nash平衡点、竞争使得零售商订货量增大、信息不对称使得零售商订货量降低并且零售商的最优订货量在一定条件下会随回收残值的增大而增大;两个零售商最优订货模型下的最优订货量的具体形式.     

Mathematics education: Procedures, rituals and man's search for meaning

An attempt is made to analyze mathematical behavior from more general psychological perspectives. The mathematical language is a special case of the human language, which is a form of expression. Many people use common language in a meaningless way. The same is true about the mathematical language. Rituals are other forms of expression. Many people identify rituals in many mathematical contexts (procedures, argumentation). Thus, quite often, they behave in a meaningless way as required by many rituals. On the other hand, the community of mathematics education struggles for meaningful learning. This can be regarded as a special case of man's search for meaning. The general claims will be illustrated by some examples from various mathematical contexts.     

On the evaluation of fixed permutations as strategies in stochastic scheduling

A general model is proposed for the stochastic version of the single-machine allocation problem. Sufficient conditions are given to ensure that there is an optimal strategy given by a fixed permutation of the job set. Additional results are given for an important special case of the general model involving simple jobs. The paper concludes with material concerning the evaluation of fixed permutations as strategies under conditions more general than the sufficient conditions mentioned above.     

Designing an optimal connected nature reserve

We consider a landscape divided into elementary cells, each of these cells containing some species to be protected. We search to select a set of cells to form a natural reserve in order to protect all the species present in the landscape. A species is considered protected if it is present in a certain number of cells of the reserve. There is an important spatial constraint concerning the set of selected cells: a species must be able to go from any cell to any cell without leaving the reserve. An integer linear programming model was proposed by Önal and Briers [2] for this reserve selection problem, but the size of the problems which can be handled by this model is limited: several hours of computation are required for solving instances with hundred of cells and hundred of species. Having proposed an improvement of this model which reduces appreciably the computation time, we propose another integer linear programming model, easy to carry out, which allows to obtain, in a few seconds of computation, optimal or near-optimal solutions for instances with hundred of cells and hundred of species. However, the computation time becomes prohibitive for instances with more than 200 cells and 100 species. But, this approach can be particularly useful to solve the problem, in an approximate way, by aggregation of cells as proposed by Önal and Briers [2].     

Optimal investment,consumption and proportional reinsurance under model uncertainty

This paper considers the optimal investment, consumption and proportional reinsurance strategies for an insurer under model uncertainty. The surplus process of the insurer before investment and consumption is assumed to be a general jump–diffusion process. The financial market consists of one risk-free asset and one risky asset whose price process is also a general jump–diffusion process. We transform the problem equivalently into a two-person zero-sum forward–backward stochastic differential game driven by two-dimensional Lévy noises. The maximum principles for a general form of this game are established to solve our problem. Some special interesting cases are studied by using Malliavin calculus so as to give explicit expressions of the optimal strategies.     

On the Convergence of Successive Substitution Sampling

Abstract

The problem of finding marginal distributions of multidimensional random quantities has many applications in probability and statistics. Many of the solutions currently in use are very computationally intensive. For example, in a Bayesian inference problem with a hierarchical prior distribution, one is often driven to multidimensional numerical integration to obtain marginal posterior distributions of the model parameters of interest. Recently, however, a group of Monte Carlo integration techniques that fall under the general banner of successive substitution sampling (SSS) have proven to be powerful tools for obtaining approximate answers in a very wide variety of Bayesian modeling situations. Answers may also be obtained at low cost, both in terms of computer power and user sophistication. Important special cases of SSS include the “Gibbs sampler” described by Gelfand and Smith and the “IP algorithm” described by Tanner and Wong. The major problem plaguing users of SSS is the difficulty in ascertaining when “convergence” of the algorithm has been obtained. This problem is compounded by the fact that what is produced by the sampler is not the functional form of the desired marginal posterior distribution, but a random sample from this distribution. This article gives a general proof of the convergence of SSS and the sufficient conditions for both strong and weak convergence, as well as a convergence rate. We explore the connection between higher-order eigenfunctions of the transition operator and accelerated convergence via good initial distributions. We also provide asymptotic results for the sampling component of the error in estimating the distributions of interest. Finally, we give two detailed examples from familiar exponential family settings to illustrate the theory.     

一种部分约束满足车辆路线问题及其求解算法

描述了一类过度约束车辆路线问题，其中可用车辆数较少而时间窗口等其它约束又不允许放松，因而导致不存在满足所有约束的可行解。此时问题求解可以转化为一类部分约束满足问题来处理，相应的优化目标是最小化未访问顾客的损失和。本给出了求解这类特殊问题的一种禁忌搜索算法设计，并通过规模不同的几个算例与其它常用方法进行了比较。最后分析了模型和算法的实用意义。     

Curve and Surface Fitting

The starting point of this paper is the problem of fitting apolynomial to a set of unequally spaced data. Five alternativeschemes which have been proposed for the solution of this problemwith an automatic computer are mentioned, and the one whichseems best suited to serve as a basis for a general purposeprogram is discussed in some detail. A practical assessmentof the accuracy of the computational processes involved in thismethod is included. The problem in which the data are weightedis also considered, as is the problem in which constraints areimposed upon the fitting function. The procedures describedfor the solution of these two cases are shown to be formallyequivalent. The method favoured for curve fitting is shown to possess stillmore advantages in solving certain types of surface fittingproblems. The general problem, in which data are scattered withina finite plane area, is not discussed in this paper, which concentrateson the case, of great practical importance, in which the dataare situated on parallel straight lines. The most general caseconsidered has a "quasi-rectangular" boundary, composed of apair of parallel sides and a pair of smooth curves. The applicationof constraints is again described; the procedures appropriatefor curve fitting are readily generalized. A practical exampleof the application of the techniques for finding a constrainedsurface is described. Finally there is a brief review of the advantages of these proceduresin common practical situations.