On Inverse Problems of Optimum Perfect Matching

As far as we know, for most polynomially solvable network optimization problems, their inverse problems under l ₁ or l norm have been studied, except the inverse maximum-weight matching problem in non-bipartite networks. In this paper we discuss the inverse problem of maximum-weight perfect matching in a non-bipartite network under l ₁ and l norms. It has been proved that the inverse maximum-weight perfect matching under l norm can be formulated as a maximum-mean alternating cycle problem of an undirected network, and can be solved in polynomial time by a binary search algorithm and in strongly polynomial time by an ascending algorithm, and under l ₁ norm it can be solved by the ellipsoid method. Therefore, inverse problems of maximum-weight perfect matching under l ₁ and l norms are solvable in polynomial time.     

交通信息条件下道路和停车选择SUE模型及算法

考虑交通信息系统(advanced traveler information system,ATIS)对出行者道路和停车选择行为的影响,并将出行者分成两类:一类出行者使用ATIS,另一类不使用ATIS.在此基础上,构造了一个基于概率的随机用户均衡模型来描述ATIS条件下的道路和停车选择问题,并给出了相应的求解算法.最后,通过一个算例分析了模型及算法的使用效果.     

利用和声分散搜索算法解决动态共乘的乘客选择研究

动态共乘作为一种配合解决城市交通出行难题的新模式近年来引起了人们越来越多的关注，然而在较大范围内选择合适的乘客，以便获得最佳的综合服务效果却具有相当大的挑战性。本文正是针对这一问题，建立了以乘客效用最大化和司机总行程最短为目标函数，以满足司机与乘客的时间要求和司机参与约束为限制条件的多目标0-1规划共乘模型，用于帮助司机选择最合适的乘客。根据该模型的特点，构造了加入了分散搜索机制的新的和声搜索算法。在仿真实验时，针对司机和乘客效用的两种产生方式，在较大规模的路网环境下利用该算法分别对模型进行了求解，得到了Pareto最优解集。仿真结果不仅表明了模型的合理性和算法的可行性，而且还指出基于效用函数可以发现更多合适的潜在乘客。最后，通过与文献中其它算法的对比进一步展示了本文算法的有效性。     

考虑通行约束和运力限制的灾后应急物资联合调度优化研究

考虑到灾后路网受损难以运输应急物资，本文研究了应急响应中车辆-直升机联合调度的路径优化问题。针对受灾地区的实时路况，通往灾区的救援工具受到数量以及装载量的约束，本文将受灾点等待救援的平均时间最短以及应急网络总费用最低设为目标，构建运力受限条件下带通行约束的救援物资联合运输多目标优化模型，然后根据随机邻域搜索变异和分级交叉的思想构建出一种带精英策略的非支配排序混合进化算法（NSHEA-II）得到模型的解，并利用算例分析对该算法进行可行性检验。结果发现，本文构建的NSHEA-II算法相对NSGA-II算法能够得到较好的结果且波动性较小，这为决策者制定救援物资的配送方案提供有效的技术支撑。     

基于柔性资源约束的前摄性项目调度优化研究

不确定环境中，项目进度计划鲁棒性的高低直接影响项目能否顺利实施。本文研究了具有随机活动工期的柔性资源约束下的前摄性项目调度优化问题，目标是在柔性资源和项目工期的约束下，借助对活动开始时间合理的进行安排进而得到拥有最大鲁棒性的进度计划。首先对研究问题进行界定；随后构建优化模型，并根据问题NP-hard属性和模型特点设计了双层嵌套禁忌搜索启发式算法，通过内外两层交互搜索寻找满意解；最后通过一个实际案例对本文研究进行说明，并分析关键参数对进度计划鲁棒性的影响，得到如下结论：相对于资源无柔性情况下的项目进度计划而言，资源具备柔性后得到的项目进度计划的鲁棒性更高，具有更强的抗干扰能力，能够保证项目稳定执行；同时，项目进度计划鲁棒性分别随着项目工期的延长、资源可用量的增加或资源柔性的提高而上升。     

A generating algorithm for linear trend-free and nearly linear trend-free block designs

The theory and properties of trend-free (TF) and nearly trend-free (NTF) block designs are wel1 developed. Applications have been hampered because a methodology for design construction has not been available.

This article begins with a short review of concepts and properties of TF and NTF block designs. The major contribution is provision of an algorithm for the construction of linear and nearly linear TF block designs. The algorithm is incorporated in a computer program in FORTRAN 77 provided in an appendix for the IBM PC or compatible microcomputer, a program adaptable also to other computers. Three sets of block designs generated by the program are given as examples.

A numerical example of analysis of a linear trend-free balanced incomplete block design is provided.     

Estimation under modified Weibull distribution based on right censored generalized order statistics

In this paper, the maximum likelihood (ML) and Bayes, by using Markov chain Monte Carlo (MCMC), methods are considered to estimate the parameters of three-parameter modified Weibull distribution (MWD(β, τ, λ)) based on a right censored sample of generalized order statistics (gos). Simulation experiments are conducted to demonstrate the efficiency of the proposed methods. Some comparisons are carried out between the ML and Bayes methods by computing the mean squared errors (MSEs), Akaike's information criteria (AIC) and Bayesian information criteria (BIC) of the estimates to illustrate the paper. Three real data sets from Weibull(α, β) distribution are introduced and analyzed using the MWD(β, τ, λ) and also using the Weibull(α, β) distribution. A comparison is carried out between the mentioned models based on the corresponding Kolmogorov–Smirnov (K–S) test statistic, {AIC and BIC} to emphasize that the MWD(β, τ, λ) fits the data better than the other distribution. All parameters are estimated based on type-II censored sample, censored upper record values and progressively type-II censored sample which are generated from the real data sets.     

Estimating the propagation rate of a viral infection of potato plants via mixtures of regressions

A problem arising from the study of the spread of a viral infection among potato plants by aphids appears to involve a mixture of two linear regressions on a single predictor variable. The plant scientists studying the problem were particularly interested in obtaining a 95% confidence upper bound for the infection rate. We discuss briefly the procedure for fitting mixtures of regression models by means of maximum likelihood, effected via the EM algorithm. We give general expressions for the implementation of the M-step and then address the issue of conducting statistical inference in this context. A technique due to T. A. Louis may be used to estimate the covariance matrix of the parameter estimates by calculating the observed Fisher information matrix. We develop general expressions for the entries of this information matrix. Having the complete covariance matrix permits the calculation of confidence and prediction bands for the fitted model. We also investigate the testing of hypotheses concerning the number of components in the mixture via parametric and 'semiparametric' bootstrapping. Finally, we develop a method of producing diagnostic plots of the residuals from a mixture of linear regressions.     

Degeneracy in the Maximum Likelihood Estimation of Univariate Gaussian Mixtures for Grouped Data and Behaviour of the EM Algorithm

Abstract.  In the context of the univariate Gaussian mixture with grouped data, it is shown that the global maximum of the likelihood may correspond to a situation where a Dirac lies in any non-empty interval. Existence of a domain of attraction near such a maximizer is discussed and we establish that the expectation-maximization (EM) iterates move extremely slowly inside this domain. These theoretical results are illustrated both by some Monte-Carlo experiments and by a real data set. To help practitioners identify and discard these potentially dangerous degenerate maximizers, a specific stopping rule for EM is proposed.     

Online coupon consumption problem

Nowadays, it is popular that the dealer makes profits by selling a kind of discount coupons, which can be used as money to purchase commodities with total cost less than or equal to the face value of the coupon. We can purchase a coupon at a price of 0<s≤1 times its face value and the number of potential purchasable coupons is a given integer l. The customer has the option to buy the goods by cash completely or by a discount coupon. However, each piece of goods can only use one coupon and the coupon used must have enough balance for the goods. The objective is to minimize the total cost for purchasing all the goods. In this paper, we reduce the problem to a special bin packing model. We consider the online problems for all 0<s≤1 and 1≤l≤∞. We present optimal online algorithms for all 0<s≤1 when l=∞ and l=1. For 2≤l<∞, we give both a lower bound and an algorithm, and show the algorithm is optimal for l=2. A preliminary version of this paper appeared in the proceedings of the 1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, Lecture Notes in Computer Science. Y. Jiang supported by Natural Science Foundation of Zhejiang Province (Y605316). Z. Tan supported by Natural Science Foundation of China (10671177, 60021201).