中国邮递员问题50年

首先介绍一般邮递员问题, 涉及费用、服务侧、衔接费用、次序等要素. 然后简要综述过去50年来中国邮递员问题、有向图上中国邮递员问题、带风向的邮递员问题、混合图上邮递员问题以及乡村邮递员问题等一般邮递员问题的特殊情况的研究进展, 突出问题的线性规划描述及相应的组合多面体结构, 着重讨论问题的模型、精确算法及其时间复杂度、NP-困难情形下的近似算法及其性能比.     

图论中若干著名问题的历史注记

考察了哥尼斯堡七桥问题,最小生成树问题,旅行推销员问题,分派问题,最大流问题,中国邮递员问题和四色问题等著名图论问题的历史背景.     

水灾地区邮递员问题

本文首次提出了中国邮递员问题的推广问题－水灾地区邮递员问题,并对解的存在性给出了一系列的充分条件、必要条件及充要条件,得到了求解该问题的一个多项式算法。     

战争地区邮递员问题

本文首次提出了赋权有向图上中国邮递员问题的一个推广－战争地区邮递员问题，并对解的存在性给出了若干充分条件和必要条件，得到了求解该问题的一个多项式算法。     

CARP中一个与Pearn下限等价的新算法

<正> 有约束边运行问题(CARP),包括有约束中国邮递员问题(CCPP)在内,是近年来颇受关注的一个运筹管理问题,该问题通常定义如下:     

约束最优路线问题的模拟退火解法

本以１９９８年全国大学生数模竞赛中的Ｂ题（即“灾情巡视路线”）为例,介绍一种最优路线问题的方法－－模拟退火法＾「１」。该法对旅行推销员、中国邮递员等问题,即使有约束条件,也能求得较好的近似解,具有适用范围广和可拓展的优点。     

阿飞上班记

烧脑指数: 趣味程度: 邮递员阿飞今天第一天上班.下午,他要给华力小镇的四户人家投递信件.华力小镇住着四户相邻的人家,这几户人家经常在一起聚会. 阿飞来到华力小镇,发现信上的地址不全,他只能敲开其中一户人家的门,问问更详细的情况. 这天,这四户人家正好在聚会.小凯打开门,发现是一位新来的邮递员,她决定考...     

离散优化问题最优值函数的连续性质

对优化问题的最优值研究是有意义的, 尽管有时并不知道怎样寻求最优值. 研究了几个重要的组合最优化问题的目标值随着输入值变化的连续化性质, 重点研究几个经典的、有代表性的离散优化问题：极小化最大完工时间的排序问题、背包问题、旅行商问题等, 以连续的数学分析思维模式审视离散问题. 最后, 研究了一些近似算法对应的目标函数的性质.     

算法思想在一些经典数学问题中的渗透

算法思想的渗透帮助学生体会中国古代数学的思想与方法,进而理解中国古代的数学文化算法在中国古代早已有之,其中所蕴涵的丰富的算法思想对今天的数学学习与数学研究都有很大的影响.本文主要是列举算法思想在一些中国古代经典数学问题中的渗透.从而进一步体会算法思想在古代数学中的贡献的同时也认识到中国古代数学的博大精深.     

Busemann-Petty问题及其相关研究综述

Busemann-Petty问题是凸几何及其相关学科中的一个极其重要的问题.在近几十年解决这一问题的过程中,凸几何学的研究领域和研究方法得到了极大的丰富和发展.本文首先阐述了Busemann-Petty问题的历史,然后综述了与Busemann-Petty问题紧密相关的一些公开问题和重要课题的研究现状和最新的进展.     

F-互补问题及其与极小元问题的等价性

本文在Ｂａｎａｃｈ空间中引进了 Ｆ－互补问题,讨论了这一问题解的存在性,在向量格中,给出了Ｆ－互补问题的可行集是 ∧ －子格的条件,研究了Ｆ－互补问题与最小元问题的等价性。     

The Complexity Analysis of the Inverse Center Location Problem

Given a feasible solution, the inverse optimization problem is to modify some parameters of the original problem as little as possible, and sometimes also with bound restrictions on these adjustments, to make the feasible solution become an optimal solution under the new parameter values. So far it is unknown that for a problem which is solvable in polynomial time, whether its inverse problem is also solvable in polynomial time. In this note we answer this question by considering the inverse center location problem and show that even though the original problem is polynomially solvable, its inverse problem is NP–hard.     

A school bus scheduling problem

This paper introduces a school bus scheduling problem wherein trips for each school are given. A trip consists of a sequence of bus stops and their designated school. Each school has its fixed time window within which trips should be completed. A school bus can serve multiple trips for multiple schools. The school bus scheduling problem seeks to optimize bus schedules to serve all the given trips considering the school time windows. We first model the problem as a vehicle routing problem with time windows (VRPTW) by treating a trip as a virtual stop. Two assignment problem based exact approaches are then proposed for special cases and a heuristic algorithm is proposed for more general cases. Benchmark problems and computational experiments are presented. Computational experiments show the effectiveness of the proposed approaches.     

On the Explicit Reconstruction of a Riemann surface from its Dirichlet–Neumann operator

This article gives a complex analysis lighting on the problem which consists in restoring a bordered connected riemaniann surface from its boundary and its Dirichlet–Neumann operator. The three aspects of this problem, unicity, reconstruction and characterization are approached. Received: May 2005 Revision: October 2005 Accepted: October 2005     

Pauli problem and related mathematical problems

We formulate several mathematical modifications of the Pauli problem of recovering the particle state from the results of measuring its coordinates and momenta, including the most abstract statement of the problem for two projection-valued measures. We describe how the Pauli problem reduces to the problem of finding the eigenvectors of certain operators. The performed analysis introduces the problems of modifications of Pauli pairs, and the considered topics and formulated problems require further study. __________ Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 157, No. 1, pp. 3–7, October, 2008.     

Minimum power multicasting problem in wireless networks

In this paper we deal with the minimum power multicasting (MPM) problem in wireless ad-hoc networks. By using an appropriate choice of the decision variables and by exploiting the topological properties of the problem, we are able to define an original formulation based on a Set Covering model. Moreover, we propose for its solution two exact procedures that include a preprocessing technique that reduces the huge number of the model’s constraints. We also report some experimental results carried out on a set of randomly generated test problems.     

分裂可行问题(SFP)的投影算法

本文探讨了分裂可行问题(SFP)的投影算法．我们先定义了(SFP)的反问题(ISFP), 然后利用正交投影性质,给出了(SFP)与(ISFP)及某些投影不动点问题之间的关系．随后, 给出了求解(SFP)的几种正交投影算法,其中包括精确和不精确投影格式．基于变分不等式中投影算法收敛性的证明思路和分裂可行问题的特有形式,证明了这几种算法的收敛性．最后通过几个算例对讨论的方法进行了初步比较．     

Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems

Whether or not the general asymmetric variational inequality problem can be formulated as a differentiable optimization problem has been an open question. This paper gives an affirmative answer to this question. We provide a new optimization problem formulation of the variational inequality problem, and show that its objective function is continuously differentiable whenever the mapping involved in the latter problem is continuously differentiable. We also show that under appropriate assumptions on the latter mapping, any stationary point of the optimization problem is a global optimal solution, and hence solves the variational inequality problem. We discuss descent methods for solving the equivalent optimization problem and comment on systems of nonlinear equations and nonlinear complementarity problems.     

Riemann‐Hilbert problems and soliton solutions of a multicomponent mKdV system and its reduction

An arbitrary order matrix spectral problem is introduced and its associated multicomponent AKNS integrable hierarchy is constructed. Based on this matrix spectral problem, a kind of Riemann‐Hilbert problems is formulated for a multicomponent mKdV system in the resulting AKNS integrable hierarchy. Through special corresponding Riemann‐Hilbert problems with an identity jump matrix, soliton solutions to the presented multicomponent mKdV system are explicitly worked out. A specific reduction of the multicomponent mKdV system is made, together with its reduced Lax pair and soliton solutions.     

实轴上的双解析函数Riemann边值逆问题

提出了一类实轴上的双解析函数Riemann边值逆问题.先消去参变未知函数,再采用易于推广的矩阵形式记法,可把问题转化为两个实轴上的解析函数Riemann边值问题.利用经典的Riemann边值问题理论,讨论了该问题正则型情况的解法,得到了它的可解性定理.