货运列车的编组调度问题的研究

对于货运列车的编组调度问题,建立了以压缩中时和增加运量为双目标、多约束的0-1规划模型,采用逐步紧缩中时约束的方法得到了问题一的调度方案.在此基础上对装载特别物资的车辆施加更强的中时约束得到了问题二的调度方案.提出了列车匹配系数的概念并建立了列车最优配对原则,根据该原则对列车进行优化编组得到了问题三的调度方案.基于问题二的数据转换处理得到了问题四的调度方案.     

一类非单调互补问题的Canonical对偶问题研究

对于一类具有广泛应用背景的非单调互补问题,我们构建了这类问题的Canonical对偶问题。其对偶问题可以写成和原问题类似的互补问题。我们给出了对偶问题和原问题解之间的对偶关系,并且将对偶问题转化成一个一维优化问题,这不但可以方便的求解这类问题,也为研究这类问题性质提供了一个非常直观的研究工具。最后,本文给出了几个算例来演示对偶问题的性质。     

含参向量随机序列的递推估计的统一处理

本文讨论了含参向量随机序列的递推估计问题,将参数估计问题和系统的状态估计问题统一了起来,给出了统一的递推估计公式,还具体地讨论了状态方程与量测方程中均含有参向量时线性离散时间系统的递推估计问题以及部分状态分量缺初始值的递推估计问题。     

基于遗传算法的大学课程表问题研究

课程表问题是时间表问题之一 ,也是 NP难问题 .根据大学授课形式的特点建立了大学课程表问题的数学模型 ,给出了求解该问题的遗传算法 .根据模型和大学课程表问题的特点设计了一种全新的编码 ,提出了一种新形式的交叉方式 .实验结果表明该方法是可行和有效的 .     

优化的合班问题

首次提出了我国高校排课中的合班工作对于排课的影响问题,建立了优化合班问题的数学模型,它是一个非线性的整数规划问题.集中讨论二维合班问题.文章中给出了两个适用于合班模型的其它例子,在此基础上归纳出适用于合班模型的一般数学模式,称之为交叉分类问题.     

灰色TSP问题的研究

在确定型TSP问题的基础上,融合灰色系统的思想提出了灰色TSP问题,构建了灰色TSP问题的动态规划模型,结合动态规划方法利用可能度及排序方法给出了求解灰色TSP问题的算法,并结合数值实例,对算法进行了说明.     

葡萄酒质量的评价模型

针对2012年“高教社杯”全国大学生数学建模竞赛A题“葡萄酒的评价”进行建模,首先介绍了问题的背景;然后分析了对几个问题的理解,并给出部分问题的具体模型和解答结果;接着分析了竞赛论文中普遍存在的问题。最后提出值得进一步研究的几个问题。     

齐次Neumann边界条件非线性抛物方程解的爆破时间的下界

研究了非线性抛物方程具有齐次Neumann边界条件问题解的爆破.在对问题中的f,ρ和g作出适当的假设的前提下,推导出了上述问题解的爆破时间的下界.同时,也得到了问题的解不发生爆破的条件.     

关于HBV及其药物相互作用的反应扩散方程的参数识别

研究具有反应-扩散现象的HBV及其药物相互作用系统的参数识别问题,依该系统正问题解的性质,建立了参数识别问题的数学模型,论证了系统正问题解关于待识别参数的连续依赖性与参数识别问题最优解的存在性.     

铺瓷砖问题的推广

铺瓷砖问题是数学模型中著名的问题,在研究了铺瓷砖问题的基础上,对其进行了推广,并给出了各种推广情形的结果.     

Complexities and algorithms for synchronized scheduling of parallel machine assembly and air transportation in consumer electronics supply chain

In this paper, we study the problem of synchronized scheduling of assembly and air transportation to achieve accurate delivery with minimized cost in consumer electronics supply chain. This problem was motivated by a major PC manufacturer in consumer electronics industry. The overall problem is decomposed into two sub-problems, which consist of an air transportation allocation problem and an assembly scheduling problem. The air transportation allocation problem is formulated as an integer linear programming problem with the objective of minimizing transportation cost and delivery earliness tardiness penalties. The assembly scheduling problem seeks to determine a schedule ensuring that the orders are completed on time and catch the flights such that the waiting penalties between assembly and transportation is minimized. The problem is formulated as a parallel machine scheduling problem with earliness penalties. The computational complexities of the two sub-problems are investigated. The air transportation allocation problem with split delivery is shown to be solvable. The parallel machine assembly scheduling problem is shown to be NP-complete. Simulated annealing based heuristic algorithms are presented to solve the parallel machine problem.     

Some duality relationships for the generalized Neyman-Pearson problem

In 1963, Kuhn presented a dual problem to a relatively well-known location problem, variously referred to as the generalized Fermat problem and the Steiner-Weber problem. The purpose of this paper is to point out how Kuhn's results can be adapted to provide a dual to the generalized Neyman-Pearson problem, a problem of fundamental interest in statistics, which has applications in control theory and a number of other areas. The Neyman-Pearson problem, termed the dual problem, is a constrained maximization problem and may be considered to be a calculus-of-variations analog to the bounded-variable problem of linear programming. When the dual problem has equality constraints, the primal problem is an unconstrained minimization problem. Duality results are also obtained for the case where the dual problem has inequality constraints.This work was partially supported by the National Science Foundation, Grant Nos. NSF-GK-1571 and NSF-GK-3038. The authors would like to acknowledge the very useful comments of one of the referees, which led to more direct and general proofs of Properties 2.3 and 2.6.     

三种新变形的全一问题

该文研究三种新变形的全一问题及最小全一问题. 原始的全一问题可被形象的称为顶点点亮顶点问题, 而这三类新问题则分别被称为顶点点亮边问题,边点亮顶点问题,边点亮边问题. 顶点点亮顶点问题已经得到了广泛的研究. 比如,解的存在性问题和求解的有效算法已经被解决,一般图上的最小顶点点亮顶点问题已经被证明是NP- 完备的,树、单圈图和双圈图上的最小顶点点亮顶点问题的线性时间最优算法也已被给出等. 该文对于顶点点亮边问题,证明一个图有解当且仅当它是二部图,因此只可能有两组解和最优解. 对于边点亮顶点问题,证明一个图有解当且仅当它包含偶数个顶点,并通过将其最优问题多项式变换成最小权的完美匹配问题,得出一般图上的最小边点亮顶点问题可在多项式时间内求解. 边点亮边问题可归约成线图上的顶点点亮顶点问题.     

The Vehicle Routing-Allocation Problem: A unifying framework

Summary In this paper the Vehicle Routing-Allocation Problem (VRAP) is presented. In VRAP not all customers need be visited by the vehicles. However customers not visited either have to be allocated to some customer on one of the vehicle tours or left isolated. We concentrate our discussion on the Single Vehicle Routing-Allocation Problem (SVRAP). An integer linear programming formulation of SVRAP is presented and we show how SVRAP provides a unifying framework for understanding a number of the papers and problems presented in the literature. Specifically the covering tour problem, the covering salesman problem, the median tour problem, the maximal covering tour problem, the travelling salesman problem, the generalised travelling salesman problem, the selective travelling salesman problem, the prize collecting travelling salesman problem, the maximum covering/shortest path problem, the maximum population/shortest path problem, the shortest covering path problem, the median shortest path problem, the minimum covering/shortest path problem and the hierarchical network design problem are special cases/variants of SVRAP.     

Continuous quadratic programming formulations of optimization problems on graphs

Four NP-hard optimization problems on graphs are studied: The vertex separator problem, the edge separator problem, the maximum clique problem, and the maximum independent set problem. We show that the vertex separator problem is equivalent to a continuous bilinear quadratic program. This continuous formulation is compared to known continuous quadratic programming formulations for the edge separator problem, the maximum clique problem, and the maximum independent set problem. All of these formulations, when expressed as maximization problems, are shown to follow from the convexity properties of the objective function along the edges of the feasible set. An algorithm is given which exploits the continuous formulation of the vertex separator problem to quickly compute approximate separators. Computational results are given.     

Single machine stochastic JIT scheduling problem subject to machine breakdowns

In this paper we research the single machine stochastic JIT scheduling problem subject to the machine breakdowns for preemptive-resume and preemptive-repeat.The objective function of the problem is the sum of squared deviations of the job-expected completion times from the due date.For preemptive-resume,we show that the optimal sequence of the SSDE problem is V-shaped with respect to expected processing times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.We discuss the difference between the SSDE problem and the ESSD problem and show that the optimal solution of the SSDE problem is a good approximate optimal solution of the ESSD problem,and the optimal solution of the SSDE problem is an optimal solution of the ESSD problem under some conditions.For preemptive-repeat,the stochastic JIT scheduling problem has not been solved since the variances of the completion times cannot be computed.We replace the ESSD problem by the SSDE problem.We show that the optimal sequence of the SSDE problem is V-shaped with respect to the expected occupying times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.A new thought is advanced for the research of the preemptive-repeat stochastic JIT scheduling problem.     

Pendants-median支撑树及其一个相关问题:复杂性和算法

The complexity status of Pendants-median spanning tree problem is an open problem. Using the complexity of the X3C problem, the paper proves that Pendants-median spanning tree problem is NP-complete. Global-median spanning tree problem is a related problem. Using the complexity of 3SAT, the paper proves that this problem is also NP-complete, and a polynomial -time algorithm to this problem is given, whose time complexity is O(n^3).     

线性比式和规划问题的输出空间分支定界算法

本文旨在针对线性比式和规划这一NP-Hard非线性规划问题提出新的全局优化算法.首先,通过引入p个辅助变量把原问题等价的转化为一个非线性规划问题,这个非线性规划问题的目标函数是乘积和的形式并给原问题增加了p个新的非线性约束,再通过构造凸凹包络的技巧对等价问题的目标函数和约束条件进行相应的线性放缩,构成等价问题的一个下界线性松弛规划问题,从而提出了一个求解原问题的分支定界算法,并证明了算法的收敛性.最后,通过数值结果比较表明所提出的算法是可行有效的.     

一些约束规划问题的近似全局最优解

首先将一个具有多个约束的规划问题转化为一个只有一个约束的规划问题,然后通过利用这个单约束的规划问题,对原来的多约束规划问题提出了一些凸化、凹化的方法,这样这些多约束的规划问题可以被转化为一些凹规划、反凸规划问题．最后,还证明了得到的凹规划和反凸规划的全局最优解就是原问题的近似全局最优解．     

Two-level decomposition algorithm for crew rostering problems with fair working condition

A typical railway crew scheduling problem consists of two phases: a crew pairing problem to determine a set of crew duties and a crew rostering problem. The crew rostering problem aims to find a set of rosters that forms workforce assignment of crew duties and rest periods satisfying several working regulations. In this paper, we present a two-level decomposition approach to solve railway crew rostering problem with the objective of fair working condition. To reduce computational efforts, the original problem is decomposed into the upper-level master problem and the lower-level subproblem. The subproblem can be further decomposed into several subproblems for each roster. These problems are iteratively solved by incorporating cuts into the master problem. We show that the relaxed problem of the master problem can be formulated as a uniform parallel machine scheduling problem to minimize makespan, which is NP-hard. An efficient branch-and-bound algorithm is applied to solve the master problem. Effective valid cuts are developed to reduce feasible search space to tighten the duality gap. Using data provided by the railway company, we demonstrate the effectiveness of the proposed method compared with that of constraint programming techniques for large-scale problems through computational experiments.