一种求解混合整数非线性规划的新算法

针对混合整数非线性规划求解难的问题,本文给出了一种新的求解策略--混合序列差异演化算法,该算法采取混合编码的形式以便处理连续变量、整数变量以及混合整数变量的优化问题.最后通过数例检验算法的优越性,仿真结果表明该算法求解效率高、收敛速度快、全局搜索能力强.     

关于整数线性规划代理对偶间隙的注记

将有效不等式的概念应用于整数线性规划的代理对偶问题 ,给出弥合整数线性规划的代理对偶间隙的方法 .数值例子表明所给出的方法在改进定界结果方面是有效的 .     

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

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

一种求解整数-非线性规划问题的演化算法

混合整数非线性规划问题为一类富有挑战性的难解问题。本文设计一个混合演化算法求解混合整数非线性规划问题，对于不同变量分别使用二进制和实数编码策略，将约束优化问题转换为多目标优化问题。数值实验验证了算法的有效性、稳健性和通用性。     

整数规划的一种线性规划解法

根据凸分析理论和单纯形法原理，提出了整数规划的一个线性规划解法。该方法主旨是将整数规划问题的离散的可行集填充成一个连续的单纯形，这样原整数规划问题就化为该单纯形上的一个新的线性规划问题。利用单纯形法求解该线性规划问题，便可得到整数规划的最优解。且进一步提出并证明了指派问题的线性规划解法。     

项目多资源均衡——投资成本最小的混合整数线性规划北大核心CSSCI

从项目实施及投资主体的关注点出发,提出资源受限情况下的项目多资源均衡——投资成本优化的混合整数线性规划模型。从关键及非关键活动两部分活动量化项目资源需求,引进0-1变量即活动浮动变量,表示非关键活动的资源需求,借助辅助变量将含绝对值的资源均衡目标函数线性化;通过对资金的折现,提出最小化投资成本的目标函数,并按泰勒公式对其模糊线性化处理。综合资源均衡和投资成本目标函数,在活动浮动、网络逻辑及项目资源约束下,构建一种混合整数线性规划模型。通过PSPLIB标准问题库进行验证,结果表明,较单目标优化,综合优化能生成项目利益相关者均满意的调度计划,实现资源的平稳使用并有效利用项目投入资本。     

一种求解混合非线性整数规划的支撑超平面方法

给出一种在可行域边界生成支撑超平面(Supporting Hyper Plane, SHP)的方法来求解凸混合整数非线性(Mixed Integer Nonlinear Programming, MINLP)问题.扩展切平面(Extended Cutting Plane, ECP)算法作为求解混合整数非线性规划的一种重要方法 ,在算法结构上简单,鲁棒性强,但是该算法收敛速度慢,特别是当被求解问题非线性程度比较高时.SHP算法在每次迭代过程中对可行域的估计比 ECP算法更准确(更小), 从而加快了算法的收敛速度.和ECP方法相比, SHP算法有效的提高了求解MINLP问题的效率,数值试验显示了该方法的有效性.     

两层广义线性规划

给出二层广义线性规划最优解极点可达性的一个充分条件 .此外 ,利用容许集的极点与下层问题可行集的极点间的关系给出“第 k最好”算法的一种快捷、方便的实现 .算例表明算法是有效的 .     

用于过程工程系统设计的MINLP整体最优化方法

本文应用Lagrange对耦函数作为外部近似函数, 对外部近似法进行了推广, 从而建立了一个求解过程工程系统设计中混合整数非线性规划(MINLP)问题的整体最优化方法。除理论分析, 本文还给出方法的几何解释及在工程问题上的应用。     

求解二层线性规划问题的混合粒子群算法

结合粒子群优化方法和单纯形法为二层线性规划构造了一个混合粒子群优化算法.算法具有两层结构,其中粒子群算法用以求解上层规划问题,单纯形法用以求解下层规划问题.设计的粒子群在上层决策变量的可行城内搜索最优解,同时通过单纯形法求解下层规划问题得到每个粒子相应的下层规划问题的解.算法通过初始种群可行化,以及步长控制、不可行粒子淘汰等技巧避免了使用罚函数处理约束带来的困难,提高了粒子群优化算法的计算性能.最后,我们给出算法的数值例子并对该算法的计算性能加以分析.     

不确定环境下战斗机采购效能评估模型

为了处理采购战斗机过程中存在的不确定信息, 首次将偏好规划理论引入到采购效能评估中. 先建立战斗机采购效能评估体系, 指标和偏好的不确定性用区间形式表示, 求解采用RICH法; 针对一些属性只有备选方案的序数信息的情况, 采用混合整数规划进行建模. 模型通过线性不等式与偏好规划方法进行集成. 最后, 通过实例验算表明该方法在不确定环境下的有效性.     

约束规划求解集装箱装卸系统集成调度问题

集装箱码头装卸系统中的岸桥、集卡和场桥的集成调度问题本质上是有阻塞、准备时间可分离并且依赖操作顺序的三阶段混合流水车间调度问题,现有文献多采用启发式算法求解该问题.本文先建立了一个紧凑的混合整数规划模型,然后从约束规划的角度建模求解该问题,提出了一个约束规划模型,以区间变量作为决策变量,并采用"扩展操作任务"的概念来定义区间决策变量以提升求解效率.为了展示约束规划的建模灵活性,还扩展了模型以考虑机器效率不同的因素.数值实验显示约束规划模型能够在很短的时间内对大规模算例求出高质量的解.     

ORDERED WEIGHTED AVERAGINGAGGREGATION METHOD FOR PORTFOLIO SELECTION

Portfolio management is a typical decision making problem under incomplete,sometimes unknown, information. This paper considers the portfolio selection problemsunder a general setting of uncertain states without probability. The investor's preferenceis based on his optimum degree about the nature, and his attitude can be described by anOrdered Weighted Averaging Aggregation function. We construct the OWA portfolio selec-tion model, which is a nonlinear programming problem. The problem can be equivalentlytransformed into a mixed integer linear programming. A numerical example is given andthe solutions imply that the investor's strategies depend not only on his optimum degreebut also on his preference weight vector. The general game-theoretical portfolio selectionmethod, max-min method and competitive ratio method axe all the special settings of thismodel.     

A novel mixed integer programming formulation and progressively stochastic search for capacitated lot sizing

The capacitated multi-level lot sizing problem is to schedule a number of different items with a bill-of-materials structure over a horizon of finite periods.To advance techniques of solving this class of problems,this paper proposes a new mixed integer programming formulation.Theoretical proofs and computational tests are provided to show that this formulation is able to provide better linear programming relaxation lower bounds than a previously-proposed strong mixed integer programming formulation.Based on the new strong formulation,a progressively stochastic search approach is proposed for solving the problem.Computational results showed that the approach generates high quality solutions,especially for problems of large sizes.     

多工件族无缓冲混合Flow Shop问题的模型和算法构建

旨在研究并解决一类从集装箱混合装卸作业环境中提取的多工件族无缓冲混合Flow Shop问题. 针对该问题的多工件族、无缓冲、部分专用机、与机器和顺序相关的准备时间和作业时间等特点, 构建了问题的混合整数线性规划模型. 鉴于问题的NP-hard特性, 构造型的启发式算法被构建, 核心思想是基于提出的机器库存和配额等概念, 动态构建含有三元副的调度列表, 三元副表示与其一一对应的工件在3阶混合Flow Shop中的加工轨迹. 通过仿真实验、下界分析, 发现算法能获得好的近优解和低的计算成本. 更为重要的是, 算法尤其适合解决大规模的实际问题.     

一类非线性两级混合整数规划问题的全局最优解的近似算法

讨论了一类非线性两级混合整数规划的求解问题 .基于非线性混合整数规划理论和算法 ,探讨了对上级规划问题采用模拟退火求解混合整数规划的算法 ;对下级规划问题采用内罚函数法 .实际运算证明 ,该算法是有效的.     

用多能工应对需求波动的混流装配线平衡问题

在混流装配线中,需求波动会造成工位负荷的变化并可能产生过载,利用多能工协助装配是解决过载问题的常见方法.多能工的引入会改变装配线平衡的约束,同时平衡方案也会影响应对需求波动所需的多能工数量,然而现有的平衡研究还没有讨论过多能工带来的影响.本文研究了使用多能工应对需求变化的混装线平衡问题,决策者需要决定多能工和普通工人的数量及任务分配.以最小化人工成本并满足不同情境的需求.文章建立了数学模型,分析了问题的复杂性和成本下界,并提出了启发式和精确算法来求解,最后使用数值实验证明了算法的有效性.     

静态武器目标分配问题的攻击界整数规划求解方法

静态武器目标分配(weapon-target assignment, WTA)问题的直接表现形态是非线性.在不丧失模型最优解的前提下,本文把WTA问题建模为整数线性规划(ILP)模型,并提出在最优武器分配方案中攻击特定目标的武器数量存在上界(攻击界).在采用启发式方法限定攻击界后,WTA问题的ILP模型的维数被大规模降低,使得求解能够在短时间内完成.与近年来发表于国内外期刊上的算例进行试算比较,结果显示本文提出的方法在求解速度和求解优化程度方面具有明显的优势.     

Boltzmann Machine Method forSolving Mixed Integer Bilevel Programming Problem

ＢｏｌｔｚｍａｎｎＭａｃｈｉｎｅＭｅｔｈｏｄｆｏｒＳｏｌｖｉｎｇＭｉｘｅｄＩｎｔｅｇｅｒＢｉｌｅｖｅｌＰｒｏｇｒａｍｍｉｎｇＰｒｏｂｌｅｍＺＨＯＮＧＷｅｉｊｕｎ；ＸＵＮａｎｒｏｎｇ；ＳＥＮＨｏｕｃａｉ（ＩｎｓｔｉｔｕｔｅｏｆＳｙｓｔｅｍｓＥｎｇｉｎｅ...     

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

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