两阶段特殊结构混合0-1规划的分解算法

本文介绍了一种用于求解具有特殊结构的两阶段混合0-1规划问题的原始-对偶分解算法,并以CPLEX软件作为核心求解器将算法实现.该算法将原问题分解成两个相对简单的子问题,较传统分解算法有更平衡的分解结构和收敛性.实验数据表明,该算法在求解较大规模、稀疏度较大、耦合度较大的复杂两阶段下三角结构混合0-1规划问题时,相比CPLEX提供的分枝剪枝法,在时间效率上有明显提高.算法最后通过固定0-1变量的取值可以得到满足管理精度要求的近似最优解.     

基于集成算法的股票指数预测

利用集成算法中的Bagging、Boosting和Random Forest三个方法,选取股票指数中的中小板指数、深证成指数、上证指数、创业板指数4组数据进行分析,得出Random Forest对上证指数、中小板指预测结果较好;Boosting对创业板指预测结果较好;Bagging对深证成指预测较好.并在4个板指中,随机选取了4支股票数据(分别为大连重工、中南建设、中国医药、东方国信)进行分析,得出集成算法在数据为200个的情况下,预测结果较为准确,其中不同方法对不同股票的适宜程度有所不同.     

基于动态列生成算法的飞机排班问题研究

飞机排班是航空运输生产计划的重要环节,对航空公司的正常运营和整体效益有着决定性影响;飞机排班通常构建为大规模整数规划问题,是航空运筹学研究的重要课题,构建的模型属于严重退化的NP-Hard问题.在考虑对多种机型的飞机进行排班时,大大增加了问题的复杂性.针对航空公司实际情况,建立多种机型的飞机排班模型;为实现模型的有效求解,提出了基于约束编程的动态列生成算法;即用约束编程快速求解航班连线(航班串)并计算航班串简约成本,动态选择列集并与限制主问题进行迭代.最后,利用国内某航空公司干线航班网络实际数据验证模型和算法的有效性.     

关于“算法”的一些认识

<正>随着计算机科学技术的发展,计算机的应用已经深入到了社会生活的方方面面,算法的作用和地位日益突出.如果没有算法,计算机就不能完成指定的任务,不能像今天这样为生活带来各种便利,更不要谈模仿人的行为、代替人去工作.正是基于这个事实,在素质教育     

基于资源受限广义指派问题的分解启发式算法

资源受限广义指派问题(RGAP)是NP-难的,对RGAP问题给出一个分解启发式算法.通过分解目标函数及约束条件,把原问题分解成子问题的集合,并设计分解启发式算法找到该问题的满意解.最后,通过算例说明算法的有效性.     

度约束最小生成树的快速算法

本文对带有顶点度约束的最小生成树问题，给出了一种快速近似算法，并在微机上予以实现，经大量试算，效果良好。     

面向全局优化基于分形的混合混沌优化算法

Julia集具有分形结构,一旦确定吸引域边界上任一点,就可通向任一个吸引周期点的吸引域.Newton-Raphson法利用此性质可计算方程所有根,并可精确计算BFGS法和共轭梯度法中下降方向步长,将两种算法分别与混沌优化算法结合,因而从新的视角建立一种融合分形理论的混合混沌优化算法.研究表明,所提出算法的计算效率高于利用Wolf一维不精确搜索求得步长的混合算法,而且混合混沌BFGS算法的优化能力优于混合混沌共轭梯度算法,也说明BFGS的局部搜索能力比共轭梯度法强.     

数学游戏中的“对称思想”

一些数学游戏,如果我们能领会到其中包含的对称思想,那么在操作中只要充分的利用它,就会获得胜利.请看几例:例1在一圆形桌面上,甲乙轮流地、不重叠地放一枚一枚圆硬币,开始放不下的一方为败,讨论甲获胜的策略.     

“一题多证”的探索与实践——以与数列有关的几道证明题为例

数列是高中数学的重要内容,也是历年数学高考的高频考点之一.关于数列的证明是逻辑推理要求较高、综合性较强、难度较大的一类题型.学生要克服畏难情绪,在平时的备考和复习中加强一题多证的训练,才能不断提高综合解题能力.     

从反证法的渊源透视反证法教学难问题

反证法是数学中,尤其是高等数学中常用的一种证明方法.它是与直接证法相对的间接证法的一种.由于逻辑学中也存在同样的相关概念,所以分清反证法、归谬法以及反驳和证明之间的细微差别和联系很有必要.本文试图讲清这些概念,并指出反证法不但是最重要的证明方法,而且同其它的证明方法一样也是进行知识积累和科学发现的源泉.     

Parametric mortality indexes: From index construction to hedging strategies

In this paper, we investigate the construction of mortality indexes using the time-varying parameters in common stochastic mortality models. We first study how existing models can be adapted to satisfy the new-data-invariant property, a property that is required to ensure the resulting mortality indexes are tractable by market participants. Among the collection of adapted models, we find that the adapted Model M7 (the Cairns–Blake–Dowd model with cohort and quadratic age effects) is the most suitable model for constructing mortality indexes. One basis of this conclusion is that the adapted model M7 gives the best fitting and forecasting performance when applied to data over the age range of 40–90 for various populations. Another basis is that the three time-varying parameters in it are highly interpretable and rich in information content. Based on the three indexes created from this model, one can write a standardized mortality derivative called K-forward, which can be used to hedge longevity risk exposures. Another contribution of this paper is a method called key K-duration that permits one to calibrate a longevity hedge formed by K-forward contracts. Our numerical illustrations indicate that a K-forward hedge has a potential to outperform a q-forward hedge in terms of the number of hedging instruments required.     

Interaction of Vortical and Acoustic Waves: From General Equations to Integrable Cases

The equations of the (2+1)-dimensional boundary-layer perturbation split into eigenmodes: a vortex wave and two acoustic waves. We assume that the equations of state (Taylor series approximation) are arbitrary. We realize a mode definition via local-relation equations extracted from the linearization of the general system over the boundary-layer flow. Each such link determines an invariant subspace and the corresponding projector. We examine the nonlinear equation for a vortex wave using a special orthogonal coordinate system based on streamlines. The equations for the orthogonal curves are linked to the Laplace equations via Laplace and Moutard transformations. The nonlinearity determines the proper form of the interaction between vortical and acoustic boundary-layer perturbation fields fixed by projecting to a subspace of the Orr-Sommerfeld equation solutions for the Tollmienn-Schlichting (linear vortical) wave and by the corresponding procedure for the acoustic wave. We suggest a new mechanism for controlling the nonlinear resonance of the Tollmienn-Schlichting wave by sound via a four-wave interaction.__________Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 144, No. 1, pp. 171–181, July, 2005.     

From how to why: A quest for the common mathematical meanings behind two different division algorithms

During their education cycle in mathematics, students are exposed to algorithms as early as primary school. Several studies show how students frequently learn to perform these algorithms without controlling the mathematical meanings behind them. On the other hand, several National Standards have highlighted the need to construct meanings in mathematics from the first cycle of education. In this paper we focus on division algorithms, investigating to what extent 6th graders can be guided to understanding the whys behind an algorithm, through the comparison of two different algorithms for integer division. Our results suggest, on the one hand, that “it could work!”, and on the other hand, that the exposure to different algorithms for the same mathematical operation seems particularly significant for bringing out the whys behind such algorithms, as well as for capturing the difference between a mathematical operation and algorithms for calculating the result of such an operation.     

Quasi-steady flight to quasi-steady flight transition in a windshear: Trajectory optimization and guidance

This paper is concerned with the near-optimum guidance of an aircraft from quasi-steady flight to quasi-steady flight in a windshear. The take-off problem is considered with reference to flight in a vertical plane. In addition to the horizontal shear, the presence of a downdraft is considered. It is assumed that the power setting is held at the maximum value and that the aircraft is controlled through the angle of attack. Inequality constraints are imposed on both the angle of attack and its time derivative.First, trajectory optimization is considered. The optimal transition problem is formulated as a Chebyshev problem of optimal control: the performance index being minimized is the peak value of the modulus of the difference between the absolute path inclination and a reference value, assumed constant. Two types of optimal trajectories are studied: type 1 is concerned with gamma recovery (recovery of the initial value of the relative path inclination); and type 2 is concerned with quasisteady flight recovery (recovery of the initial values of the relative velocity, the relative path inclination, and the relative angle of attack). The numerical results show that the type 1 trajectory and the type 2 trajectory are nearly the same in the shear portion, while they diverge to a considerable degree in the aftershear portion of the optimal trajectory.Next, trajectory guidance is considered. A guidance scheme is developed so as to achieve near-optimum quasi-steady flight recovery in a windshear. The guidance scheme for quasi-steady flight recovery includes three parts in sequence. The first part refers to the shear portion of the trajectory and is based on the result that this portion of the trajectory depends only mildly on the boundary conditions; therefore, any of the guidance schemes already developed for type 1 trajectories can be employed (for instance, variable gamma guidance). The second part (constant gamma guidance) refers to the initial aftershear portion of the trajectory and is designed to achieve almost velocity recovery. The third part (constant rate of climb guidance) refers to the final aftershear portion of the trajectory and is designed to achieve almost complete restoration of the initial quasi-steady state.While the shear guidance and the initial aftershear guidance employ constant gain coefficients, the final aftershear guidance employs a variable gain coefficient. This is done in order to obtain accuracy and prompt response, while avoiding oscillations and overshoots. The numerical results show that the guidance scheme for quasi-steady flight recovery yields a transition from quasi-steady flight to quasi-steady flight which is close to that of the optimal trajectory, ensures the restoration of the initial quasi-steady state, and has good stability properties.This paper is based on Refs. 1 and 2.This research was supported by NASA-Langley Research Center, Grant No. NAG-1-516, and by Boeing Commercial Aircraft Company. The authors are indebted to Dr. R. L. Bowles, NASA-Langley Research Center, for helpful discussions.     

Quasi-steady flight to quasi-steady flight transition for abort landing in a windshear: Trajectory optimization and guidance

This paper is concerned with the optimal transition and the near-optimum guidance of an aircraft from quasi-steady flight to quasi-steady flight in a windshear. The abort landing problem is considered with reference to flight in a vertical plane. In addition to the horizontal shear, the presence of a downdraft is considered.It is assumed that a transition from descending flight to ascending flight is desired; that the initial state corresponds to quasi-steady flight with absolute path inclination of –3.0 deg; and that the final path inclination corresponds to quasi-steady steepest climb. Also, it is assumed that, as soon as the shear is detected, the power setting is increased at a constant time rate until maximum power setting is reached; afterward, the power setting is held constant. Hence, the only control is the angle of attack. Inequality constraints are imposed on both the angle of attack and its time derivative.First, trajectory optimization is considered. The optimal transition problem is formulated as a Chebyshev problem of optimal control: the performance index being minimized is the peak value of the modulus of the difference between the instantaneous altitude and a reference value, assumed constant. By suitable transformations, the Chebyshev problem is converted into a Bolza problem. Then, the Bolza problem is solved employing the dual sequential gradient-restoration algorithm (DSGRA) for optimal control problems.Two types of optimal trajectories are studied, depending on the conditions desired at the final point. Type 1 is concerned with gamma recovery (recovery of the value of the relative path inclination corresponding to quasi-steady steepest climb). Type 2 is concerned with quasi-steady flight recovery (recovery of the values of the relative path inclination, the relative velocity, and the relative angle of attack corresponding to quasi-steady steepest climb). Both the Type 1 trajectory and the Type 2 trajectory include three branches: descending flight, nearly horizontal flight, and ascending flight. Also, for both the Type 1 trajectory and the Type 2 trajectory, descending flight takes place in the shear portion of the trajectory; horizontal flight takes place partly in the shear portion and partly in the aftershear portion of the trajectory; and ascending flight takes place in the aftershear portion of the trajectory. While the Type 1 trajectory and the Type 2 trajectory are nearly the same in the shear portion, they diverge to a considerable degree in the aftershear portion of the trajectory.Next, trajectory guidance is considered. Two guidance schemes are developed so as to achieve near-optimum transition from quasi-steady descending flight to quasi-steady ascending flight: acceleration guidance (based on the relative acceleration) and gamma guidance (based on the absolute path inclination).The guidance schemes for quasi-steady flight recovery in abort landing include two parts in sequence: shear guidance and aftershear guidance. The shear guidance is based on the result that the shear portion of the trajectory depends only mildly on the boundary conditions. Therefore, any of the guidance schemes already developed for Type 1 trajectories can be employed for Type 2 trajectories (descent guidance followed by recovery guidance). The aftershear guidance is based on the result that the aftershear portion of the trajectory depends strongly on the boundary conditions; therefore, the guidance schemes developed for Type 1 trajectories cannot be employed for Type 2 trajectories. For Type 2 trajectories, the aftershear guidance includes level flight guidance followed by ascent guidance. The level flight guidance is designed to achieve almost complete velocity recovery; the ascent guidance is designed to achieve the desired final quasi-steady state.The numerical results show that the guidance schemes for quasi-steady flight recovery yield a transition from quasi-steady flight to quasi-steady flight which is close to that of the optimal trajectory, allows the aircraft to achieve the final quasi-steady state, and has good stability properties.This research was supported by NASA Langley Research Center, Grant No. NAG-1-516, by Boeing Commercial Airplane Company, and by Air Line Pilots Association.The authors are indebted to Dr. R. L. Bowles (NASA-LRC) and Dr. G. R. Hennig (BCAC) for helpful discussions.