An upper bound on the minimal total cost of the transportation problem with varying demands and supplies

In general cases, to find the exact upper bound on the minimal total cost of the transportation problem with varying demands and supplies is an NP-hard problem. In literature, there are only two approaches with several shortcomings to solve the problem. In this paper, the problem is formulated as a bi-level programming model, and proven to be solvable in a polynomial time if the sum of the lower bounds for all the supplies is no less than the sum of the upper bounds for all the demands; and a heuristic algorithm named TPVDS-A based on genetic algorithm is developed as an efficient and robust solution method of the model. Computational experiments on benchmark and new randomly generated instances show that the TPVDS-A algorithm outperforms the two existing approaches.     

二十世纪日本学者对云南少数民族历史文化的研究

介绍和评析了鸟居龙藏等日本学者对云南的田野调查、华南民族史、傣族史、南诏和大理国史、倭族之源、照叶树林文化、神话、民间故事、民间信仰和民间祭祀等方面的研究成果,并系统地分析了日本学者对云南少数民族历史文化研究的全貌、学术研究的轨迹及新动向。     

套管的失效分析

通过收集石油套管现场失效数据资料,以套管失效为顶事件建立了石油套管的故障树,该故障树共考虑了47个不同的基本事件。通过对套管故障树的分析,得到了套管失效故障树的一阶最小割集27个,二阶最小割集29个,四阶最小割集1个,确立了套管的主要失效形式为潜在损坏、套管挤毁、套管断裂及严重腐蚀,并提出了提高套管可靠性的措施。     

基准收益率与经济增长的关系依存度研究

基准收益率是厂商投资所要求的回报率,是衡量投资项目在财务上是否达到要求的一个主要标准。在不存在制度性障碍和充分的市场竞争的条件下,根据均衡市场的思想,从理论上导出了基准收益率与经济增长正相关的结论,为基准收益率与经济增长的依附性提供理论基础。     

Alternative Methods for Computing the Sensitivity of Complex Surveillance Systems

Stochastic scenario trees are a new and popular method by which surveillance systems can be analyzed to demonstrate freedom from pests and disease. For multiple component systems—such as a combination of a serological survey and systematically collected observations—it can be difficult to represent the complete system in a tree because many branches are required to represent complex conditional relationships. Here we show that many of the branches of some scenario trees have identical outcomes and are therefore redundant. We demonstrate how to prune branches and derive compact representations of scenario trees using matrix algebra and Bayesian belief networks. The Bayesian network representation is particularly useful for calculation and exposition. It therefore provides a firm basis for arguing disease freedom in international forums.     

On Shortest k-Edge-Connected Steiner Networks in Metric Spaces

Given a set of points P in a metric space, let l(P) denote the ratio of lengths between the shortest k-edge-connected Steiner network and the shortest k-edge-connected spanning network on P, and let r = inf l(P) P for k 1. In this paper, we show that in any metric space, r 3/4 for k 2, and there exists a polynomial-time -approximation for the shortest k-edge-connected Steiner network, where = 2 for even k and = 2 + 4/(3k) for odd k. In the Euclidean plane, and .     

The Steiner Tree Problem in Kalmanson Matrices and in Circulant Matrices

We investigate the computational complexity of two special cases of the Steiner tree problem where the distance matrix is a Kalmanson matrix or a circulant matrix, respectively. For Kalmanson matrices we develop an efficient polynomial time algorithm that is based on dynamic programming. For circulant matrices we give an -hardness proof and thus establish computational intractability.     

On the Complexity of Constructing Evolutionary Trees

In this paper we study a few important tree optimization problems with applications to computational biology. These problems ask for trees that are consistent with an as large part of the given data as possible. We show that the maximum homeomorphic agreement subtree problem cannot be approximated within a factor of , where N is the input size, for any 0 in polynomial time unless P = NP, even if all the given trees are of height 2. On the other hand, we present an O(N log N)-time heuristic for the restriction of this problem to instances with O(1) trees of height O(1) yielding solutions within a constant factor of the optimum. We prove that the maximum inferred consensus tree problem is NP-complete, and provide a simple, fast heuristic for it yielding solutions within one third of the optimum. We also present a more specialized polynomial-time heuristic for the maximum inferred local consensus tree problem.     

A General Model of Some Inverse Combinatorial Optimization Problems and Its Solution Method Under l ∞ Norm

This paper proposes an optimization model and shows that most inverse combinatorial optimization problems so far discussed can be fit into this model as special cases. We propose a Newton-type algorithm for this model under l norm. This algorithm can solve the model in strongly polynomial time if the subproblem involved is solvable in strongly polynomial time for any fixed value of the parameter appearing in the subproblem, and it is shown that most particular inverse optimization problems encountered are this kind. Therefore, through this paper we show that a large group of inverse optimization problems can be handled in a uniform way and solved in strongly polynomial time.     

Finding a Noncrossing Steiner Forest in Plane Graphs Under a 2-Face Condition

Let G = (V,E) be a plane graph with nonnegative edge weights, and let be a family of k vertex sets , called nets. Then a noncrossing Steiner forest for in G is a set of k trees in G such that each tree connects all vertices, called terminals, in net N _i, any two trees in do not cross each other, and the sum of edge weights of all trees is minimum. In this paper we give an algorithm to find a noncrossing Steiner forest in a plane graph G for the case where all terminals in nets lie on any two of the face boundaries of G. The algorithm takes time if G has n vertices and each net contains a bounded number of terminals.