Capacitated transportation problem with bounds on RIM conditions

Motivated by dead-mileage problem assessed in terms of running empty buses from various depots to starting points, we consider a class of the capacitated transportation problems with bounds on total availabilities at sources and total destination requirements. It is often difficult to solve such problems and the present paper establishes their equivalence with a balanced capacitated transportation problem which can be easily solved by existing methods. Sometimes, total flow in transportation problem is also specified by some external decision maker because of budget/political consideration and optimal solution of such problem is of practical interest to the decision maker and has motivated us to discuss such problem. Various situations arising in unbalanced capacitated transportation problems have been discussed in the present paper as a particular case of original problem. In addition, we have discussed paradoxical situation in a balanced capacitated transportation problem and have obtained the paradoxical solution by solving one of the unbalanced problems. Numerical illustrations are included in support of theory.     

Interface Problems for Elliptic Systems

Interface problems for elliptic systems of second order partial differential equations are studied. The main result is that the solution in the neighborhood of the singular point can be divided into two parts one of which is a solution to the homogeneous system with constant coefficients, and the other one possesses higher regularity.     

平衡和不平衡运输问题与分配问题的通用迭代算法

将不平衡运输问题转化成网络最短路问题,利用Floyd算法规则,给出了一种既可以解平衡和不平衡运输问题,又可以解平衡和不平衡分配问题的通用迭代算法。与专门用于解运输问题的闭合回路法和专门用于解分配问题的匈牙利法相比,这种算法不但具有通用的优点,而且更便于在计算机上运行。     

C运输问题

在传统的运输问题中 ,总假设所有产地 (发点 )的产量之和或所有销地 (收点 )的销量之和就是货物的总运输量 .但在实践中 ,特别是在一些与环境有关的资源、稀有资源或不可再生资源的开发利用过程中 ,由于受环境保护或政策限制 ,常常对这些资源的开采和运输有一定的数量限制 .这一类对总运输量有数量限制的运输问题不同于 A运输问题和 B运输问题 ,我们把它称为 C运输问题 .事实上 ,C运输问题是 A运输问题和 B运输问题的推广 .将给出 C运输问题的数学模型和求解方法 .     

敏感问题研究中从调查问题到目标问题的转换模型

针对社会敏感问题,构建了从调查问题到目标问题的转化模型,并以大学生考试心理问题为例,进行了模拟运算,从模拟结果看,通过无敏感化的调查问卷研究敏感问题在技术上是可行的,能够达到较为理想的信度和效度,从而开辟了量化研究敏感问题的新途径.     

Robust absolute single machine makespan scheduling-location problem on trees

We investigate a robust single machine scheduling-location problem with uncertainty in edge lengths. Jobs are located at the vertices of a given tree. Given a location for a single machine, the jobs travel to the location and are processed there sequentially. The goal is to find a location of the machine and simultaneously a sequence to minimize the makespan value in the worst-case. We use the concept of gamma-robustness to model uncertainty. Our main result is a polynomial time algorithm.     

The weighted Fermat-Torricelli problem on a surface and an “inverse” problem

We study the weighted Fermat-Torricelli (w.F-T) problem for geodesic triangles on a C² complete surface and on an Aleksandrov space of curvature bounded above by a real number K and solve an “inverse” problem on a C² complete surface. The solution of the w.F-T problem and the inverse w.F-T problem on a C² complete surface is based on the differentiation of the length of geodesics with respect to the arc length.     

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

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

A modified quasi-boundary value method for ill-posed problems

In this paper, we study a final value problem for first order abstract differential equation with positive self-adjoint unbounded operator coefficient. This problem is ill-posed. Perturbing the final condition we obtain an approximate nonlocal problem depending on a small parameter. We show that the approximate problems are well posed and that their solutions converge if and only if the original problem has a classical solution. We also obtain estimates of the solutions of the approximate problems and a convergence result of these solutions. Finally, we give explicit convergence rates.     

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.     

Inverse sorting problem by minimizing the total weighted number of changes and partial inverse sorting problems

In this paper, we consider two types of inverse sorting problems. The first type is an inverse sorting problem by minimizing the total weighted number of changes with bound constraints. We present an O(n ²) time algorithm to solve the problem. The second type is a partial inverse sorting problem and a variant of the partial inverse sorting problem. We show that both the partial inverse sorting problem and the variant can be solved by a combination of a sorting problem and an inverse sorting problem. Supported by the Hong Kong Universities Grant Council (CERG CITYU 103105) and the National Key Research and Development Program of China (2002CB312004) and the National Natural Science Foundation of China (700221001, 70425004).     

Persistency in the assignment and transportation problems

LetG = (U,V,E) be a bipartite graph with weights of its edgesc _ij . For the assignment and transportation problem given by such a graph we propose efficient procedures for partitioning the edge setE into three classes:E _o is the set of edgesij withx _ij = 0 for each optimum solution (0-persistent edges);E ₁ is the set of edges withx _ij > 0 and constant for each optimum (1-persistent edges) andE _w is the set of edges such that there are two optimum solutions x, x withx _ij x _ij ¹ (weakly persistent edges).     

The Perturbation of the Interface of the Two-dimensional Diffraction Problem and an Approximating Muskat Modal

ln this paper, a new transformation is found out to straighten the interface Γ_2 x = f(y), f ∈ C^{2+a}([0, a]), f_y|_y =0, δ < f < l-δ,δ > 0,δ,l=constants and a perturbation of the interface is considered for a two dimensional diffraction problem. And the existence, uniqueness and regularity of an appeoximating Muskat model are proved.     

Transportation problems which can be solved by the use of hirsch-paths for the dual problems

Balinski uses his signature method for the proof of the Hirsch-conjecture for dual transportation polyhedra to obtain an efficient algorithm for the assignment problem. We will show how to extend this method to other primal transportation problems, including transportation problems with unit demands. We then prove that Balinski's assignment algorithm is equivalent, cycle by cycle, to that of Hung and Rom. We demonstrate that, under some assumptions for our probability model, a modification of the latter algorithm has an average complexity of O(n ²logn) and present some computational results confirming this. We also present results that indicate that this modification compares favorably with Balinski's algorithm and other codes. Research of both authors supported, in part, by grants of the Alexander von Humboldt-Stiftung. Supported, in part, by NSF grant DMS-8504050.     

A symmetry problem from probability

We examine solutions of two related boundary value problems for smooth domains in Euclidean space which arise from variational problems in probability. We show that the existence of solutions to each problem implies that the domain is a sphere.

     

Bandwidth of bipartite permutation graphs in polynomial time

We give the first polynomial-time algorithm that computes the bandwidth of bipartite permutation graphs. Bandwidth is an NP-complete graph layout problem that is notorious for its difficulty even on small graph classes. For example, it remains NP-complete on caterpillars of hair length at most 3, a very restricted subclass of trees. Much attention has been given to designing approximation algorithms for computing the bandwidth, as it is NP-hard to approximate the bandwidth of general graphs with a constant factor guarantee. The problem is considered important even for approximation on restricted classes, with several distinguished results in this direction. Prior to our work, polynomial-time algorithms for exact computation of bandwidth were known only for caterpillars of hair length at most 2, chain graphs, cographs, and most interestingly, interval graphs.     

Random homogenization of an obstacle problem

We study the homogenization of an obstacle problem in a perforated domain, when the holes are periodically distributed and have random shape and size. The main assumption concerns the capacity of the holes which is assumed to be stationary ergodic.     

Asymptotics of the solution to Robin problem

Convergence of the solution to the exterior Robin problem to the solution of the Dirichlet problem, as the impedance tends to infinity, is proved. The rate of convergence is established. A method for deriving higher order terms of the asymptotics of the solution is given.     

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

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