求解多项目组合选择问题的奔德斯分解算法

随着我国经济的快速发展,项目组合选择问题所面临的待选项目集日益膨胀.而项目组合选择模型通常表示为整数规划或混合整数规划的形式,过多的待选项目会对项目组合选择模型的高效求解带来巨大的挑战.针对这一问题,本文研究了多项目组合选择模型的奔德斯分解算法.将原问题分解成仅考虑从待选项目集中选出最优组合的主问题与对已选项目进行排序的子问题,通过主子问题间的迭代逐步逼近最优解.通过算法性能分析,发现直接使用奔德斯分解算法存在着收敛速度慢,子问题不可行的缺点.为了加速算法的收敛速度,对主问题进行了修正,提出了一种利用潜在的最优项目及有效不等式改进主问题的新思路.最后,通过算例分析,对比了直接使用分支定界法与使用奔德斯分解算法两类求解方法的求解效率,验证了本文所提出方法的有效性与合理性.     

随机需求条件下生产-库存系统优化与仿真

针对多周期、多产品、有能力约束动态制造系统的生产-库存问题,考虑随机需求条件和产品的需求满足率,建立以系统总成本最低为目标的二级随机线性规划模型,通过随机模拟法将原问题转化为等价的确定性问题,运用对偶理论和Benders分解法把等价问题分解为相互关联的主问题和子问题,然后分别进行求解。最后的实例仿真结果验证了模型和算法的合理有效性,表明了它们在生产实践中的应用性。     

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

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

面向应急成像观测任务的多星协同调度方法

针对应急条件下的成像观测任务,设计了多星协同调度框架,将多星协同调度问题分解为任务排序主问题和资源匹配子问题。分析了多星协同调度中的主要约束条件,以任务收益为优化目标构建问题的约束满足模型,并应用改进粒子群优化算法进行求解。详细介绍了算法中的编码、解码、移动、变异等操作,给出算法时间复杂度的计算公式。通过仿真实验,对算法的有效性进行了验证。     

ATO供应链中航空运输及并行机生产协调调度问题

研究了一类供应链中的生产和航空运输协调调度问题的特点.在此基础上,提出了解决该问题的理论框架.在该理论框架下,协调调度问题被分解为航空运输调度子问题和生产调度子问题.在对各子问题的定义和建模的过程中,考虑彼此之间的制约关系.建立了航空运输调度问题的整数规划模型,并证明了该问题等同于一个运输问题.在生产调度子问题中,考虑并行机的生产调度问题,证明该问题为NP完全问题,提出了解该问题的模拟退火算法.     

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

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

基于正交遗传算法的非线性两层规划问题解法

对于一类非线性两层规划问题,将下层规划分解成几个并列且独立的子问题。对于上层的每一个决策变量,求出下层各子问题的Karush-Kuhn-Tucker(K-K-T)稳定点,作为对上层决策的反应。针对上层问题,设计了自适应的正交遗传算法,并给出其全局收敛性证明。最后数值模拟验证了该算法的高效性及鲁棒性。     

考虑现实约束的模糊多准则投资组合优化模型

针对模糊环境中资产收益和换手率均为模糊变量的投资组合问题, 考虑了资产组合的基数约束、投资比例的边界约束、资产的流动性以及分散化程度约束, 建立了一个以资产组合收益、偏度最大, 同时资产组合风险、不确定性以及模糊性最小为目标的多准则投资组合优化模型. 然后, 利用加权极大-极小模糊目标规划方法将所提出的模型转化为单目标规划问题, 进而设计了一个遗传算法来对其进行求解. 最后, 通过一个实例来阐明所提出模型的实用性以及算法的有效性. 研究结果表明: 本模型能够有效地刻画不同投资者的投资意图, 所设计的算法是有效的.     

New Implicit Enumeration Method for Polynomial 0-1 Programming

A new implicit enumeration method for polynomial zero-one programming is proposed in this article. By adopting the p-norm surrogate constraint method, a polynomial zero-one programming problem with multiple constraints can be converted into an equivalent polynomial zero-one programming problem with a single surrogate constraint. A new solution scheme is then devised to take the advantage of this prominent feature in carrying out the “fathoming” procedure and the “backtrack” procedure in a searching process of an implicit enumeration. We demonstrate the efficiency of this new algorithm by some promising computational results. Finally, we conclude by proposing certain topics for future research.     

多项式0-1规划中隐枚举算法的改进及应用

提出了一个求解多项式0-1规划问题的隐枚举算法.通过应用p次范数约束划归,多项式0-1规划问题的多个约束可以被一单一等价约束来替代.利用这一显著特性,新算法在搜寻最优解过程中,能改进探寻(fathoming)和折返(backtrack)策略以提高隐枚举法的计算效率.通过一个算例说明这个新算法的计算步骤并对随机产生的问题进行了测试,得到了较好的结果.     

可折叠集装箱接驳运输问题的建模与优化

对一类带时间窗的可折叠箱接驳运输问题进行了研究,其中使用可折叠箱在堆场与客户之间集散货物,一辆集卡可装载一个满箱或多个空箱,目标为集卡总工作时间的最小化.借鉴确定的活动在顶点上的图的思想,将该问题分解为满箱子问题和空箱子问题,其中满箱子问题类似于带时间窗的多旅行商问题,空箱子问题因客户的货物量可为负值而显著区别于车辆路径问题,且两个子问题之间存在访问时间耦合等关联.进而建立了问题的数学描述,设计了问题的主动禁忌搜索(reactive tabu search,RTS)求解算法,并基于随机生成的大量算例验证了算法的有效性.结果表明,相比于使用CPLEX等优化软件,RTS算法可以在更短的时间内求得问题的更优解;相比于使用标准箱的情形,使用可折叠箱可节省约13%的接驳成本.     

随机急诊需求下基于分支定价算法的手术计划研究

手术计划是优化医疗资源配置的重要组成部分,涉及众多的不确定性,是目前医疗管理领域研究的热点和难点问题.本文聚焦于考虑急诊病人随机手术时长需求的择期病人手术计划问题研究,在各个手术室具有异质性的情况下,优化手术室的超时成本和闲置成本,并为一个计划周期内的择期手术进行手术室和手术日期的分配.建立了一个0-1整数规划模型,针对问题情境和手术计划特有的约束条件提出了满足问题特性的分支定界和列生成相结合的精确型分支定价求解算法.其中在分支定界算法上,通过对比选择适合问题特性的节点选择策略,并且提出了分步分支策略加快搜索过程.为加快列生成算法的求解,通过数值积分和等价转换将带有不确定性的子问题转变为一个0-1背包问题的变形,然后设计动态规划算法进行求解.数值实验表明,根据问题特性设计的分支定价算法可有效求解具有不同实例规模下的手术计划问题,和CPLEX相比,大规模情形下能够在可接受的计算时间内得到问题最优解.     

An Algorithm to Solve Linear Bilevel Programs

ＡｎＡｌｇｏｒｉｔｈｍｔｏＳｏｌｖｅＬｉｎｅａｒＢｉｌｅｖｅｌＰｒｏｇｒａｍｓＬＩＵＸｉａｏｍｉｎ；ＷＡＮＧＲｉｓｈｕａｎｇ（Ｄｅｐｔ．ｏｆＭａｔｈ．ＢｅｉｊｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＡｅｒｏ．＆Ａｓｔｒｏ．，Ｂｅｉｊｉｎｇ，１０００８３，Ｐ．Ｒ...     

Global convergence of a class of smooth penalty methods for semi-infinite programming

For the semi-infinite programming (SIP) problem, the authors first convert it into an equivalent nonlinear programming problem with only one inequality constraint by using an integral function, and then propose a smooth penalty method based on a class of smooth functions. The main feature of this method is that the global solution of the penalty function is not necessarily solved at each iteration, and under mild assumptions, the method is always feasible and efficient when the evaluation of the integral function is not very expensive. The global convergence property is obtained in the absence of any constraint qualifications, that is, any accumulation point of the sequence generated by the algorithm is the solution of the SIP. Moreover, the authors show a perturbation theorem of the method and obtain several interesting results. Furthermore, the authors show that all iterative points remain feasible after a finite number of iterations under the Mangasarian-Fromovitz constraint qualification. Finally, numerical results are given.     

基于时间反演的上行NOMA系统能效优化算法

为了解决上行非正交多址接入(non-orthogonal multiple access,NOMA)系统在多径环境下传输效率较低问题,提出了一种基于时间反演(time reversal,TR)的上行NOMA网络资源分配算法.首先,利用TR技术独特的空时聚焦特性,增大信号的接收强度.其次,考虑用户最小传输速率约束和用户最...     

Bilevel programming model and solution method for mixed transportation network design problem

By handling the travel cost function artfully, the authors formulate the transportation mixed network design problem (MNDP) as a mixed-integer, nonlinear bilevel programming problem, in which the lower-level problem, comparing with that of conventional bilevel DNDP models, is not a side constrained user equilibrium assignment problem, but a standard user equilibrium assignment problem. Then, the bilevel programming model for MNDP is reformulated as a continuous version of bilevel programming problem by the continuation method. By virtue of the optimal-value function, the lower-level assignment problem can be expressed as a nonlinear equality constraint. Therefore, the bilevel programming model for MNDP can be transformed into an equivalent single-level optimization problem. By exploring the inherent nature of the MNDP, the optimal-value function for the lower-level equilibrium assignment problem is proved to be continuously differentiable and its functional value and gradient can be obtained efficiently. Thus, a continuously differentiable but still nonconvex optimization formulation of the MNDP is created, and then a locally convergent algorithm is proposed by applying penalty function method. The inner loop of solving the subproblem is mainly to implement an all-or-nothing assignment. Finally, a small-scale transportation network and a large-scale network are presented to verify the proposed model and algorithm. This research is supported by the National Basic Research Program of China under Grant No. 2006CB705500, the National Natural Science Foundation of China under Grant No. 0631001, the Program for Changjiang Scholars and Innovative Research Team in University, and Volvo Research and Educational Foundations.     

CONVEXIFICATION AND CONCAVIFICATION METHODS FOR SOME GLOBAL OPTIMIZATION PROBLEMS

In this paper, firstly, we propose several convexification and concavification transformations to convert a strictly monotone function into a convex or concave function, then we propose several convexification and concavification transformations to convert a non-convex and non-concave objective function into a convex or concave function in the programming problems with convex or concave constraint functions, and propose several convexification and concavification transformations to convert a non-monotone objective function into a convex or concave function in some programming problems with strictly monotone constraint functions. Finally, we prove that the original programming problem can be converted into an equivalent concave minimization problem, or reverse convex programming problem or canonical D.C. programming problem. Then the global optimal solution of the original problem can be obtained by solving the converted concave minimization problem, or reverse convex programming problem or canonical D.C     

对一类带聚类特征TSP问题的蚁群算法求解

蚁群算法是近几年提出的一种新型的模拟进化算法,初步的研究表明该算法具有极强的鲁棒性和发现较好解的能力,但同时也存在收敛速度慢的缺点。针对带聚类特征的TSP问题,提出了一种新型的蚁群算法。该算法利用TSP问题本身所具有的聚类特征,从数据域上将其分解成多个子问题,对每个子问题分别采用蚁群算法并行求解,最后将所有子问题的解按一定规则合并成问题的解。对带聚类特征TSP问题的仿真实验表明该算法的收敛速度得到了极大的提高。     

舰载机出动离场调度优化算法

出动离场调度是舰载机起降作业中关键一环, 可抽象为NP(non-deterministic pdynoial)难问题的混合车间调度问题。首先，在传统数学规划模型基础上, 引入逻辑约束及间隔变量, 建立了约束规划模型。然后，通过调度分解技术构建多机调度转化为单机调度的启发式规则, 并提出了单机约束引导启发式搜索与约束规划二分法迭代算法, 给出了问题的求解流程。算例仿真表明, 约束规划可有效解决不同规模下的离场调度, 并快速收敛到阈值内; 在中小规模出动时, 所提算法效率比传统智能方法提升约2个数量级, 具有较强实时规划能力, 但随着实验规模增大算法收敛时间呈线性变化趋势, 而在本文研究范围内仍优于传统智能算法, 具有良好实用价值。最后，用起飞位数量对出动效率进行灵敏度分析, 发现C2起飞位对出动效能贡献最大。     

基于IRS辅助多用户通信系统的信道容量优化

智能反射表面(intelligent reflecting surface,IRS)通过对无线传播环境的智能配置进而获得极好的信道容量增益。在IRS辅助多用户下行链路通信中,本文通过共同优化基站处受功率限制的预编码器和IRS处受单位模量约束的相移器来最大化信道容量。针对由此产生的非确定性多项式难问题,首先将其转换成等效问题,再利用交替优化算法来求解预编码矩阵和相移向量。当固定相移向量时,优化问题可转换为二阶锥规划问题后直接使用标准优化包获得最优预编码矩阵。当固定预编码矩阵时,单位模量约束是解决问题的难点,本文将其嵌入搜索空间之后提出黎曼信赖域(Riemannian trust-region, RTR)算法来求解。仿真结果表明,与现有方法相比,RTR算法不仅具有性能的提升,还有更快的收敛速度。