最优总装线路安排问题研究

本文研究了自动化生产线中总装线路安排的最优化问题,建立了该问题的数学模型,并提出了两个多项式算法．     

Conditions based on conditional moments for max-stable limit laws

Let X ₁, X ₂, ...X _n be independent and identically distributed random variables with common distribution function F. Necessary and sufficient conditions for F to belong to the domains of attraction of Φ _α and Ψ _α are derived in terms of conditional moments.      

Sampling subproblems of heterogeneous Max‐Cut problems and approximation algorithms

Recent work in the analysis of randomized approximation algorithms for NP‐hard optimization problems has involved approximating the solution to a problem by the solution of a related subproblem of constant size, where the subproblem is constructed by sampling elements of the original problem uniformly at random. In light of interest in problems with a heterogeneous structure, for which uniform sampling might be expected to yield suboptimal results, we investigate the use of nonuniform sampling probabilities. We develop and analyze an algorithm which uses a novel sampling method to obtain improved bounds for approximating the Max‐Cut of a graph. In particular, we show that by judicious choice of sampling probabilities one can obtain error bounds that are superior to the ones obtained by uniform sampling, both for unweighted and weighted versions of Max‐Cut. Of at least as much interest as the results we derive are the techniques we use. The first technique is a method to compute a compressed approximate decomposition of a matrix as the product of three smaller matrices, each of which has several appealing properties. The second technique is a method to approximate the feasibility or infeasibility of a large linear program by checking the feasibility or infeasibility of a nonuniformly randomly chosen subprogram of the original linear program. We expect that these and related techniques will prove fruitful for the future development of randomized approximation algorithms for problems whose input instances contain heterogeneities. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

On the subdifferential regularity of max root functions for polynomials

In 2001, Burke and Overton showed that the abscissa mapping on polynomials is subdifferentially regular on the monic polynomials of degree n. We extend this result to the class of max polynomial root functions which includes both the polynomial abscissa and the polynomial radius mappings. The approach to the computation of the subgradient simplifies that given by Burke and Overton and provides new insight into the variational properties of these functions.     

A comprehensive simplex-like algorithm for network optimization and perturbation analysis

The family of network optimization problems includes the following prototype models: assignment, critical path, max flow, shortest path, and transportation. Although it is long known that these problems can be modeled as linear programs (LP), this is generally not done. Due to the relative inefficiency and complexity of the simplex methods (primal, dual, and other variations) for network models, these problems are usually treated by one of over 100 specialized algorithms. This leads to several difficulties. The solution algorithms are not unified and each algorithm uses a different strategy to exploit the special structure of a specific problem. Furthermore, small variations in the problem, such as the introduction of side constraints, destroys the special structure and requires modifying andjor restarting the algorithm. Also, these algorithms obtain solution efficiency at the expense of managerial insight, as the final solutions from these algorithms do not have sufficient information to perform postoptimality analysis.

Another approach is to adapt the simplex to network optimization problems through network simplex. This provides unification of the various problems but maintains all the inefficiencies of simplex, as well as, most of the network inflexibility to handle changes such as side constraints. Even ordinary sensitivity analysis (OSA), long available in the tabular simplex, has been only recently transferred to network simplex.

This paper provides a single unified algorithm for all five network models. The proposed solution algorithm is a variant of the self-dual simplex with a warm start. This algorithm makes available the full power of LP perturbation analysis (PA) extended to handle optimal degeneracy. In contrast to OSA, the proposed PA provides ranges for which the current optimal strategy remains optimal, for simultaneous dependent or independent changes from the nominal values in costs, arc capacities, or suppliesJdemands. The proposed solution algorithm also facilitates incorporation of network structural changes and side constraints. It has the advantage of being computationally practical, easy for managers to understand and use, and provides useful PA information in all cases. Computer implementation issues are discussed and illustrative numerical examples are provided in the Appendix     

玻恩对于中国物理界的贡献

马克斯·玻恩是20世纪最伟大的物理学家之一,他除了自己在多个物理领域做出了卓越的贡献外,还培养了一大批物理人才．这其中有几位著名的中国物理学家,如王福山、彭桓武、程开甲、杨立铭、黄昆等．他的这一贡献值得写入中国物理学史册．回顾他为中国物理界培养杰出人才的贡献,是中国物理界对他诞辰130周年的最好纪念之一．     

On maximum planar induced subgraphs

The nonplanar vertex deletion or vertex deletion vd(G) of a graph G is the smallest nonnegative integer k, such that the removal of k vertices from G produces a planar graph G^′. In this case G^′ is said to be a maximum planar induced subgraph of G. We solve a problem proposed by Yannakakis: find the threshold for the maximum degree of a graph G such that, given a graph G and a nonnegative integer k, to decide whether vd(G)?k is NP-complete. We prove that it is NP-complete to decide whether a maximum degree 3 graph G and a nonnegative integer k satisfy vd(G)?k. We prove that unless P=NP there is no polynomial-time approximation algorithm with fixed ratio to compute the size of a maximum planar induced subgraph for graphs in general. We prove that it is Max SNP-hard to compute vd(G) when restricted to a cubic input G. Finally, we exhibit a polynomial-time -approximation algorithm for finding a maximum planar induced subgraph of a maximum degree 3 graph.