多星联合对地观测调度问题的列生成算法

多星联合对地观测调度问题作为一类大规模组合优化问题, 其求解算法往往采用启发式或超启发式. 运用列生成思想对该问题设计了完全搜索算法. 在建立了问题的整数规划模型之后, 将原问题分解为集合配置主问题和含时间窗口的最短路径子问题, 其中集合配置主问题采用主单纯型法通过CPLEX求解, 含时窗的最短路径子问题采用动态规划求解, 该动态规划算法围绕观测冲突时段这一关键资源进行最优子路径的扩展. 只有在子问题的最优解对主问题的优化目标仍有改进时, 主问题的约束矩阵列才被扩展. 该算法针对部分算例得到了最优解, 其余算例也在指定的时间内得到了相比一种基于优先级的启发式算法更优的解.     

缺货补偿条件下的生产规划模型及算法

针对缺货补偿条件下有能力约束、多产品、多阶段制造系统的生产规划问题，以利润最大为目标，建立混合整数规划模型。通过对模型的等价转换，基于对偶理论将等价模型分解为相互关联的生产主问题和库存子问题，设计对偶分解算法进行求解。数值实例的计算结果，说明了算法的收敛趋势以及在计算时间方面的性能。     

MINLP问题全局优化算法的研究

提出了一种求解混合整数非线性规划MINLP问题的混合优化算法GASimplex，由遗传算法模块GAsolver和单纯形算法模块SimplexSolver两部分组成。该算法首先确定MINLP模型的整数变量和复杂变量，使得固定这些变量后可以将原问题转化为一线性规划子问题，在此基础上应用GASolver实现对整数变量和复杂变量的优化，而其适应函数则可以通过求解编码对应的线性规划子问题SimplexSolver来得到。这样，一方面由于在遗传算法中引入了局部搜索过程，极大增加了GASimplex整体收敛速度，而且对于非凸的MINLP问题，可以在理论上保证得到解的全局最优性；另一方面，模型约束条件是通过SimplexSolver求解得到，故约束条件的存在—般不会增加遗传算法处理的复杂度，可有效的处理约束的MINLP问题。通过对一MINLP模型仿真分析，证明该算法不仅具有很决的收敛速度，而且能得到全局的次最优解，更适合处理一类复杂的MINLP问题。     

电子侦察卫星任务合成探测及混合调度

任务合成探测对于提高电子侦察卫星的侦察效益具有重要意义。分析了电子侦察任务合成探测的条件及性质,建立了多星合成探测调度问题的混合整数规划模型。提出了一种基于模型分解的优化求解算法,将模型分解为任务指派主问题与动态合成子问题,任务指派主问题通过遗传算法生成不同卫星的任务分配方案,动态合成子问题则根据指派的任务进行优化,生成完整的卫星侦察计划。测试案例验证了方法的有效性。     

粒子群算法在投资组合中的应用

投资组合面临现实证券市场中大量数据，求解组合模型是一个非线性整数规划问题，传统数学规划算法难以有效求解。为此，本文将粒子群算法应用到基于VaR的投资组合模型中，并通过上海证券交易所的实际数据进行计算机模拟，结果说明该算法所求最优投资组合是实用的和有效的。     

考虑延期交货、转包和非减库存能力约束的单产品批量模型

研究了一个非减库存能力约束下的允许延期交货和转包的单产品动态批量问题.引入子计划概念,通过先求解所有可能的子计划,再基于动态规划搜索子计划的最优组合,得到问题的最优解.给出了所有子计划的通用数学描述,并通过松弛正生产量约束将子计划的计算分成两个子问题;依据子问题和子计划最优解的性质,设计了求解子问题和重新集结松弛约束的多项式算法;在此基础上提出了一个复杂性为O(T4)的求解整个规划问题的多项式动态规划算法,这里T是规划时段上的周期数.最后通过数值试验测试了该算法的性能.     

多星成像调度问题基于分解的优化算法

提出了一种求解多星成像调度问题的基于分解的优化算法,将问题分解为任务分配主问题与单星成像调度子问题.任务分配主问题生成不同卫星的任务分配方案,单星成像调度子问题则根据分配的任务进行优化,生成每颗卫星的成像调度方案.采用自适应的蚁群算法求解任务分配主问题,通过自适应参数调整策略及信息素平滑策略,实现全局搜索和快速收敛间的平衡.采用启发式算法及快速模拟退火算法求解单星成像调度子问题,通过综合多颗卫星的调度结果, 可以对任务分配方案进行评价,引导蚁群算法搜索优化的任务分配方案,最终得到多颗卫星的成像调度方案. 大规模测试算例验证了算法的效率.     

一般两层非线性规划问题的模拟退火全局优化

提出了一种基于模拟退火算法求解一般两层非线性规划问题的全局优化策略.采用模拟退火算法è求解上层问题,用精确惩罚函数处理约束,保证了算法稳定迅速地收敛于全局最优解.为了提高算法的效率,对标准模拟退火算法采取了一些改进措施.下层的非线性规划问题则采用可变容差单纯型算法完成求解.所设计的组合算法思路清晰,编程简单,数值计算结果表明,该算法有着良好的全局收敛可靠性和较高的收敛速度,是求解一般两层非线性规划问题的一种有效算法.     

基于改进列生成算法的受扰航班优化调度

受扰航班恢复问题是一个非常复杂的实时网络优化问题,属于NP-hard问题.同时考虑了飞机资源短缺、机场关闭和计划外的飞机维修情况,并采用航班延误、航班取消、航班交换等多种恢复措施.基于Dantzig-Wolfe分解原理,分别建立主问题和子问题的数学优化模型,采用列生成算法框架求解该大规模整数规划问题.在求解过程中,首先,构造初始可行航线,基于航线调用CPLEX软件对主问题进行求解;其次,针对研究问题的特征,提出一些性质,并采用改进的"label-setting algorithm"对子问题求解,每次迭代过程中加入多条具有简约成本为负的列,降低迭代次数,对于求得的非整数解采用分支定界法进行处理.最后,通过对多种规模的实际算例进行测试,验证了所采用精确算法的正确性及效果,并对测试结果进行分析总结.     

允许缺货和转包的受限批量模型的多项式算法

有效组织带转包的采购计划对企业提高竞争力和参与全球产业分工有重要意义.研究了一个新的非减库存能力约束下的允许缺货和转包的企业采购计划模型,提出了一个基于动态规划的多项式算法.引入子计划概念,将问题归结为有效计算子计划;依据最优解的性质设计了求解子计划的多项式算法;再通过动态规划算法以多项式时间枚举所有可能子计划组合,得到问题的最优解.数值试验显示了该算法的有效性及高效性.     

信息不确定下的主动打断项目组合选择问题鲁棒优化

在项目组合选择问题中,历史数据的缺乏以及预测和估计过程中出现的不可避免的误差,会导致模型中的参数无法被准确地估计,进而给决策带来巨大的风险.因此,构建合适的鲁棒优化模型,为企业提供能有效应对参数不确定性的鲁棒解,对企业的风险防范具有极其重要的现实意义.本文首先对确定参数下的主动打断项目组合选择问题数学模型的特点进行了分析.进一步地,介绍了鲁棒优化问题中不确定情境集的概念,并给出了允许管理者根据其偏好确定不确定情境集大小的方法,构建了全新的基于情境的鲁棒优化模型,进而计算出在所规定的不确定情境集内的最坏情境下能保持可行性与最优性的鲁棒解,实现了鲁棒性与最优性间的权衡,最后,通过GAMS/BARON进行了算例分析,验证了模型的合理性与有效性.从理论上,本文首次将鲁棒优化理论扩展到了主动打断项目组合选择问题中,针对现有的项目组合选择问题鲁棒优化理论仅能应对有限个可行解的不足之处,提出了一类新的鲁棒优化方法,使其能够应对具有无穷多可行解的主动打断项目组合问题.从实践上,随着我国高新产业的发展,具有超前性与特殊性的研究与发展(RD)、信息科技与信息系统(IT/IS)等新兴项目的投资日益受到重视.相较于传统项目,这类项目的高度不确定性使得探究项目组合选择问题的鲁棒优化理论日益迫切.故而本文的研究具有明显的理论价值和现实意义.     

基于复杂网络和随机游走算法的研发项目组合风险分析

针对项目组合中的风险分析问题,本文通过构建"项目组合-风险"双层网络模型,提出了基于随机游走算法的项目组合风险定量分析方法,以更准确地预测项目组合风险.首先,本文在研发项目间依赖关系分析的基础上,构建了项目组合网络,并采用设计结构矩阵(DSM)法建立了基于复杂网络中"邻接节点"的项目间连接强度模型.然后,采用多领域矩阵建立了由风险事件推导风险因素间依赖关系的模型.进一步,通过集成项目组合中项目间依赖关系、项目与风险因素间对应关系、以及风险因素间初始的依赖关系,构建了"项目组合-风险"双层网络模型,采用随机游走算法得到稳定状态下最终的"项目-风险因素"域映射矩阵(DMM)和风险因素DSM.最后,以某研发项目组合为例,采用随机游走算法进行项目组合风险的精准预测,并采用PageRank方法对风险因素进行排序,验证了本文提出模型和方法的有效性.     

Task scheduling for multi-electro-magnetic detection satellite with a combined algorithm

Task scheduling for electro-magnetic detection satellite is a typical combinatorial optimization problem. The count of constraints that need to be taken into account is of large scale. An algorithm combined integer programming with constraint programming is presented. This algorithm is deployed in this problem through two steps. The first step is to decompose the original problem into master and sub-problem using the logic-based Benders decomposition; then a circus combines master and sub-problem solving process together, and the connection between them is general Benders cut. This hybrid algorithm is tested by a set of derived experiments. The result is compared with corresponding outcomes generated by the strength Pareto evolutionary algorithm and the pure constraint programming solver--GECODE, which is an open source software. These tests and comparisons yield promising effect.     

基于战略一致性的新产品开发项目组合选择

针对新产品开发项目的特点,考虑项目与企业战略的匹配程度及项目间的相互依赖关系研究项目组合选择问题. 首先提出战略一致性的概念来衡量项目与企业战略的匹配程度,并进行定量化描述;然后考虑项目的战略一致性对组合收益的影响,对仅考虑项目间相互依赖性的项目组合选择模型进行改进,建立基于战略一致性的新产品开发项目组合选择模型;从可变邻域构造方面设计改进的模拟退火算法求解模型;最后以轿车整车开发企业为背景进行实例分析,验证了模型和算法的有效性.     

不确定多期滚动项目组合选择优化模型

在经典项目组合选择问题的基础上, 建立了不确定条件下多期滚动项目组合选择模型, 以各期获利最大为优化目标, 以企业战略需求与所选项目合成战略贡献之间的均衡匹配性和资源增益性为关联约束条件. 基于模糊理论提出了上 方贴近度和下方贴近度概念, 用以对战略均衡匹配性进行度量. 应用可能性理论将所建模型转换为确定性模型. 采用遗传算法对模型求解, 并基于路径再连接(path relinking, PR)算法思想, 设计了适合0-1编码的逐次替代法和逐次后移法进行局部搜索, 获得了较好的求解效果. 仿真测试显示, 进行多期滚动项目组合选择时, 在5期以内可以保证获利的稳定性, 获利波动期在第6-8期, 可以帮助企业确定最佳战略调整期. 各期不同类型的项目选择数量也具有较明显的周期性变化规律. 研究结果具有实践指导意义.     

A MODEL FOR MEDIUM-OR LONG-TERM PLANNING

The PDAS(Production Distribution Area,Spatial)is an efficient method for optimalanalysis of the existing industrial production spatial distribution.As the main problem formedium- and long-term programming of the industrial production level isproject investmentanalysis,incorporation of project investment into PDAS to evaluate the project investmentcomprehensively over the whole planned period will be an ideal approach.This.however,changes the linear programming problem into a mixed integer programming problem withconstraints which include a step function.To simplify the algorithm,in light of large scalesystem decomposition,a model and an algorithm with coordinative running of schedulingand distribution optimization are proposed.The new version of PDAS,named PDAS-D,will have more practical use in decision support analysis for the medium-and long-termproduction spatial distribution and optimal adjustment of industrial structure by means ofproject investment.     

An extended model for project portfolio selection with project divisibility and interdependency

In this paper, we develop an extended model for the project portfolio selection problem over a planning horizon with multiple time periods. The model incorporates the factors of project divisibility and interdependency at the same time for real-life applications. The project divisibility is considered as a strategy, not an unfortunate event as in the literature, in choosing the best execution schedule for the projects, and the classical concept of “project interdependencies” among fully executed projects is then extended to the portions of executed projects. Additional constraints of reinvestment consideration, setup cost, cardinality restriction, precedence relationship and scheduling are also included in the model. For efficient computations, an equivalent mixed integer linear programming representation of the proposed model is derived. Numerical examples under four scenarios are presented to highlight the characteristics of the proposed model. In particular, the positive effects of project divisibility are shown for the first time.     

基于下半方差的债券投资组合模型

用下半方差作为风险度量构建了债券投资组合模型,研究投资者的债券投资问题。在理论上分析了模型最优解的存在性,并且证明了模型具有全局最优解。为了得到最优债券投资组合策略,依据模型的随机属性,构造了求解模型的蒙特卡罗罚函数算法,并且证明了算法的收敛性。给出了相应的数值算例验证模型的有效性。     

不同借贷利率下的投资组合选择——-基于均值和VaR的效用最大化模型

用VaR代替方差来度量风险,从而把基于均值和方差的效用函数拓展为基于均值和VaR的一般二元效用函数（关于均值递增,关于VaR递减）,进而研究含无风险资产且具有不同借贷利率时投资组合选择的效用最大化模型.利用均值-VaR模型有效边界的性质,得到了一般效用函数下最大效用存在的条件及最优解的本质特征,并给出了求解的具体方法和数值算法.最后作为结论的直接应用和说明,利用中国股票市场数据给出了一个实例分析.